一種分布式的模糊聚類方法

閻俊梅

（山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西大同 037009）

一種分布式的模糊聚類方法

閻俊梅

（山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西大同 037009）

由于FCM算法中的初始值需要隨機的設(shè)定，這種隨機性不能保證每次都能達到全局最優(yōu)，也就是說如果初始聚類中心的設(shè)置具有全局的特點，那么聚類的結(jié)果才能達到全局最優(yōu)。因此主要針對模糊c-均值（FCM）聚類算法對初始值很敏感，而且容易陷入局部最優(yōu)解的這一特點，提出了一種分布式的模糊聚類方法。首先用分治法得到模糊聚類的全局的聚類中心值，然后再用FCM進行聚類，從而克服FCM算法對初始值敏感和容易陷入局部最優(yōu)解的缺陷，達到全局最優(yōu)。經(jīng)仿真實驗證明結(jié)果是很理想的。

聚類分析；分治方法；大數(shù)據(jù)集

聚類分析［1］就是通過無監(jiān)督訓(xùn)練將樣本按相似性分類，把相似性大的樣本歸為一類，占據(jù)特征空間的一個局部區(qū)域，而每個局部區(qū)域的聚類中心又起著相應(yīng)類型的代表的作用。聚類［2］可以采用不同的算法過程，但歸結(jié)起來大致可分為3類方法：系統(tǒng)聚類、逐步分解和判別聚類。

系統(tǒng)聚類和逐步分解，都是一種局部的考慮，在實現(xiàn)過程中均沒有考慮保持群體的全局分布特性；判別聚類［3］雖然當(dāng)聚類中心的選取符合全局分布特性時也會產(chǎn)生很好的結(jié)果，但是由于這種選取的隨機性，不可能每次都能選到符合全局分布特性［4］的聚類中心點。因此，我們需要尋找一種考慮保持群體全局分布特征的方法，而尋找具有全局分布［5］特征的聚類中心點就是一條很好的捷徑。鑒于此，提出了一種分布式的聚類方法從而得到全局的聚類中心值。

1 分布式聚類方法的基本思想

將大數(shù)據(jù)集隨機分成若干個子集，再對每個子集利用硬k-均值或者是FCM算法［6］進行聚類，且每個子集的聚類中心數(shù)的設(shè)置與原來用FCM算法聚類時設(shè)置的聚類中心數(shù)一樣。計算每兩個子集之間的距離矩陣，然后局部合并，即每一子集的每一個類應(yīng)該與另一個子集的哪一個類相合并，最后進行全局合并。由全局合并的結(jié)果計算初始的全局聚類中心值，然后再用FCM算法進行聚類。

1.1 距離矩陣的建立

距離矩陣存放的是任何兩個子集之間的歐氏距離，距離矩陣中的每一維存放的是一個子集中的一個類的聚類中心與另一子集中的一個類的聚類中心的歐氏距離。

如果在每個子集中有C類，那么一個距離矩陣的維數(shù)為C×C。如果一共有N個子集，那么一共有個距離矩陣。

例表1為A子集與B子集之間的距離矩陣：A子集和B子集分別有3類，在距離矩陣中的每一行代表A子集中所有類，每一列代表B子集中所有類。

其中A1，A2，A3分別代表A子集的第一類，第二類，第三類；B1，B2，B3分別代表B子集的第一類，第二類，第三類。

那么AiBj代表A的第i類的距離中心與B的第j類的距離中心之間的歐氏距離。

如A2B3代表A子集的第2類與B子集的第3類的聚類中心的歐氏距離。

表1 A，B子集之間的距離矩陣

1.2 局部矩陣的建立

根據(jù)一個距離矩陣得到兩個子集之間的相應(yīng)關(guān)系。即第一個子集的某一個類應(yīng)該與第二個子集的哪一個類相合并。

因為由一個距離矩陣可得到一個局部矩陣，所以如果一共有N個子集，那么局部矩陣的個數(shù)為，即與距離矩陣的個數(shù)相同。

局部矩陣的建立過程：

1）首先遍歷一個距離矩陣的所有維，找到歐氏距離值最小的一個，記下它的行數(shù)和列數(shù)，并存在局部矩陣中。

2）在距離矩陣中除去已經(jīng)找到的那個維，然后繼續(xù)搜索其他所有的維，然后再找到值最小的一個維。

3）同理直到把局部矩陣所有的維填滿為止。

1.3 全局矩陣的建立

假如一共有3個子集S1，S2，S3，且每個子集有3類。得到的局部矩陣如表2和表3所示。其中S1中的第二類和S2中的第二類為一類；S1中的第一類與S2中的第一類為一類；S1中的第三類與S2中的第三類為一類。S2中的第三類與S3中的第一類為一類；S2中的第一類與S3中的第三類為一類；S2中的第二類與S3中的第二類為一類。以S2為中介來進一步建立S1、S2與S3之間的關(guān)系。

表2 S1，S2子集之間的局部矩陣

表3 S2，S3子集之間的局部矩陣

那么根據(jù)局部矩陣可得到的全局矩陣為表4所示：

表4 由表2和表3的局部矩陣得到的全局矩陣

表4表明子集S1的第二類、子集S2的第二類以及子集S3的第二類合并為一類；子集S1的第一類、子集S2的第一類以及子集S3的第三類合并為一類；子集S1的第三類、子集S2的第三類以及子集S3的第一類合并為一類。

2 基于分治法的初始化算法

1）把數(shù)據(jù)隨機分成M個子集。

2）對每個子集用FCM算法或者是C-均值聚類算法去聚類。

3）按照1.1建立距離矩陣。

4）按照1.2建立局部矩陣。

5）按照1.3建立全局矩陣。

6）對全局矩陣?yán)眉訖?quán)算術(shù)平均數(shù)來計算全局的聚類中心。

以圖4表示的全局矩陣為例來說明聚類中心的計算過程：

如果S1中的第二類有L1個數(shù)據(jù)，聚類中心為（x1，y1）；S2中第二類有L2個數(shù)據(jù)，聚類中心為（x2，y2）；S3中第二類有L3個數(shù)據(jù)，聚類中心為（x3，y3）。那么由這幾個類組成的類的全局聚類中心為：

（L1×（x1，y1）+L2×（x2，y2）+L3×（x3，y3））/（L1+L2+L3）

同理可以得到另外兩個全局聚類中心點。

7）利用模糊c-均值進行聚類。

通過上述算法得出的聚類中心點的初始坐標(biāo).將其代入到FCM算法中進行聚類。

3 仿真實驗

從不同的起始群體出發(fā)，多次運用分治法，然后將找到的最優(yōu)的初始值代入到FCM算法繼續(xù)進行聚類分析。

經(jīng)過統(tǒng)計分析，分類結(jié)果中有80％比單一使用FCM算法的分類結(jié)果要好。

圖1是其中的一次基于分治法的初始化方法的聚類結(jié)果，聚類結(jié)果比較清晰，效果較好。且速度比直接用FCM算法聚類快。

圖1 基于分治法的初始化方法聚類效果

4 實驗結(jié)論

通過對基于分治法的初始化方法進行數(shù)據(jù)仿真實驗，我們可以看出該聚類方法找到了保持全局特性的聚類中心初值，而將其與FCM算法結(jié)合起來進行處理，克服了FCM算法對初始值敏感和容易陷入局部最優(yōu)解的缺陷，從而得到了理想的結(jié)果。通過實驗表明，利用基于分治法的初始化方法進行模糊聚類分析尋找到的空間聚類中心保持了很好的全局分布特性，使聚類效果更加理想。

［1］鄭巖，黃蓉懷，站曉蘇.基于遺傳算法的動態(tài)模糊聚類［J］.北京郵電大學(xué)學(xué)報，2005，28（1）：23-27.

［2］Hoppner F.Speeding up fuzzy c-Means：using a hierarchical data organization to control the precision of membership calculation［J］.Fuzzy Sets and Systems，2002，128（3）：30-50.

［3］張莉，周偉達，焦李成.核聚類算法［J］.計算機學(xué)報，2002，25（6）：587-590.

［4］董云影，張運杰，暢春玲.改進的遺傳模糊聚類算法［J］.模糊系統(tǒng)與數(shù)學(xué)，2005，5（10）：12-15.

［5］韓璞，張欣，王兵，等.基于神經(jīng)網(wǎng)絡(luò)的交互式爐膛火焰圖像識別［J］.中國電機工程學(xué)報，2008，28（20）：19-25.

［6］李培強，李欣然.模糊神經(jīng)網(wǎng)絡(luò)負(fù)荷模型的內(nèi)插外推能力［J］.高電壓技術(shù)，2008，34（6）：82-85.

〔編輯 高?！?/p>

A Distributed Fuzzy Clustering Method

YAN Jun-mei
（School of Mathematics and Computer Science，Shanxi Datong University，Datong Shanxi，037009）

The initial values in FCM algorithm are setted randomly，so it can not ensure to get to globle optimization.That is，if the initial clustering center values are globle，the clustering results can get to globle optimization.So this paper proposes a distributed fuzzy clustering method.Firstly get the globle clustering center values of FCM using distributed method，then cluster the datas using the globle clustering center values in FCM.So it can overcome the sensitive of FCM algorithm to initial values and the fault of easily to get local optimization，and get to globle optimization.Experimental results show the method has exact clustering result.

clustering analysis；distributed method；large data set

TP18

A

1674-0874（2011）01-0003-02

2010-10-20

國家科技部高新技術(shù)計劃資助項目［2005EJ000017］；河北省科技研究與發(fā)展計劃資助項目［02547015D］；河北省普通高等學(xué)校博士科研資助基金［B2002118］

閻俊梅（1981-），女，山西天鎮(zhèn)人，碩士，助教，研究方向：數(shù)據(jù)挖掘。