一種混合模糊聚類算法

袁桂蓉

【摘要】將傳遞閉包方法與FCM方法結(jié)合，提出一種混合模糊聚類算法，使其不需要預(yù)先設(shè)定聚類數(shù)目，并且能夠降低它對(duì)初始化的敏感程度，收斂速度更快，且不用人為給定聚類類別數(shù)，不容易受初始化的影響。

【關(guān)鍵詞】傳遞閉包 -統(tǒng)計(jì)量 模糊-均值聚類

聚類是按照一定的要求和規(guī)律對(duì)事物進(jìn)行分類的過(guò)程，它根據(jù)研究對(duì)象的某些特性，運(yùn)用數(shù)學(xué)方法對(duì)給定對(duì)象進(jìn)行區(qū)分和分類。自Zadeh提出模糊集理論以來(lái)，人們開始用模糊的方法來(lái)處理聚類問(wèn)題，并稱之為模糊聚類分析。

現(xiàn)有的模糊聚類算法都是以某種準(zhǔn)則來(lái)評(píng)價(jià)一個(gè)己給定劃分的特性的，通常在參數(shù)輸入、停機(jī)條件上存在諸多人為控制因素，這導(dǎo)致了用戶在使用聚類方法時(shí)需要大量的數(shù)據(jù)分析領(lǐng)域知識(shí)。另外，有些聚類算法只能對(duì)某種分布數(shù)據(jù)聚類效果較好，對(duì)其它分布的數(shù)據(jù)聚類效果則很差。許多聚類算法是根據(jù)歐氏距離和Manhattan距離來(lái)進(jìn)行聚類的，基于這類距離的聚類方法一般只能發(fā)現(xiàn)具有類似大小和密度的圓形或球狀聚類。比如現(xiàn)在比較流行的-Means和模糊-Means聚類算法，既需要提供參數(shù)—聚類數(shù)目，而且對(duì)非球狀或橢球型分布的數(shù)據(jù)集聚類效果不理想。因而需要設(shè)計(jì)一種好的聚類算法來(lái)提高算法的自主性和適應(yīng)性，減少用戶的參與。

一、傳遞閉包法聚類

（1）建立模糊相似矩陣。設(shè)X= {x1，x2，…，xn}為被分類對(duì)象的全體，設(shè)每一對(duì)象xi由一組特征數(shù)據(jù)（xi1，xi2，…，xim）來(lái)表征，于是可以得到原始數(shù)據(jù)矩陣Xnxm=[xij]。

為了使不同量綱的數(shù)據(jù)也能進(jìn)行比較，常常需要將原始數(shù)據(jù)矩陣進(jìn)行極差化或標(biāo)準(zhǔn)化。這里先將原始數(shù)據(jù)矩陣統(tǒng)一趨勢(shì)化，得到無(wú)量綱矩陣X'nxm=（x"ij），其中x.ij=|xij-ui0|/iqr（xij）

iqr（xij）表示四分位極差。

按照普通的聚類方法中相似系數(shù)確定方法，建立模糊相似矩陣與，xi與xj的相似程度rij可根據(jù)實(shí)際情況采用相似系數(shù)法、距離法以及其它方法。

（2）由相似矩陣求等價(jià)矩陣。因?yàn)槟：葍r(jià)矩陣能對(duì)論域進(jìn)行等價(jià)的劃分，這就能滿足聚類分析的需要。然而，通常情況下，由標(biāo)定過(guò)程構(gòu)造出的模糊關(guān)系僅僅能滿足自反性和對(duì)稱性，而不滿足傳遞性，所以生成的只是一個(gè)模糊相似矩陣R。為了進(jìn)行分類，需要根據(jù)標(biāo)定所得模糊矩陣R，求出其傳遞閉包t（R）。R=t（R）為模糊等價(jià)矩陣。

（3）進(jìn)行聚類。將λ從1依次取到0，依次截得等價(jià)關(guān)系Rλ，并按Rλ將X分成等價(jià)類。

二、利用FCM算法得到最終分類

（1）確定FCM的聚類類別數(shù)c。將人從1依次取到0，形成一種動(dòng)態(tài)聚類，便于全面了解樣本聚類，然后根據(jù)實(shí)際需要選擇某閾值λ，確定樣本一種分類。如何合理選擇閾值λ，筆者用F-統(tǒng)計(jì)量選擇λ最佳值。F值越大，分類越合理，將這時(shí)的分類數(shù)目作為FCM的聚類類別數(shù)c。

（2） FCM算法。Step1：將F-統(tǒng)計(jì)值最大的閾值λ對(duì)應(yīng)的分類數(shù)目r作為聚類類別數(shù)c，2≤c≤n，n是數(shù)據(jù)個(gè)數(shù)，給定加權(quán)指數(shù)m，設(shè)定迭代停止閾值ε，初始化聚類中心V（0），設(shè)置迭代計(jì)數(shù)器b=0；

Step2：根據(jù)（式1.1）計(jì)算或更新劃分矩陣U（b）=[μik]；

其中，dik為無(wú)量綱矩陣中X.第k個(gè)序列到第i類中心vi的歐氏距離。

Step3：根據(jù)（式1.2）更新聚類中心V（b+1）：

Step4：如果‖V（b）-V（b+1）‖≤ε，則算法停止并輸出劃分矩陣U和聚類中心V；否則令b=b+1，轉(zhuǎn)向執(zhí)行Step2。

若μjk=max{μjk}，則xk∈第j類。

同樣，該算法也具有另一種形式，即從初始化模糊劃分矩陣開始，先用（式1.2）計(jì)算聚類中心矩陣，然后用（式1.1）更新模糊分類矩陣，直到滿足停止準(zhǔn)則為止。

對(duì)比可知，這種混合模糊聚類法比傳統(tǒng)FCM方法更切合實(shí)際，收斂速度更快，且不用人為給定聚類類別數(shù)，不容易受初始化的影響。

三、結(jié)論

本文針對(duì)經(jīng)典的模糊C均值聚類算法需要事先確定聚類類數(shù)，設(shè)定初始聚類中心的缺點(diǎn)，提出改進(jìn)的FCM算法，即一種混合模糊聚類算法。先利用傳遞閉包法得到一系列分類，再引入F-統(tǒng)計(jì)量，根據(jù)F-統(tǒng)計(jì)值的大小確定一種分類，以最大的F-統(tǒng)計(jì)值對(duì)應(yīng)的一種分類的類數(shù)作為FCM聚類的類別數(shù)C，以這種分類的聚類中心作為FCM算法的初始聚類中心。此方法能夠反映出原始數(shù)據(jù)的真實(shí)特性，真正達(dá)到聚類分析的無(wú)監(jiān)督性；同時(shí)也降低了由于人為因素造成的不確定性影響，增強(qiáng)了聚類結(jié)果的準(zhǔn)確性和可信度。

參考文獻(xiàn)：

[1]高新波.模翊聚類分析及其英語(yǔ)[M].西安：西安電子科技大學(xué)出版社，2004.

[2]王洪春，彭宏.一種基于嫡的聚類算法[J].計(jì)算機(jī)科學(xué)，2007.

[3]路金芳，孫雙全，楊建燕，伍化巖.統(tǒng)計(jì)學(xué)原理[M].河南：黃河水利出版社，2006.

[4]HALKIDI M，VAZIRGIANNIS M.A data set oriented approachfor clustering algorithm selection[C]//Proc of the 5th EuropeanConference on Principles of Data Mining and Knowledge Discov-ery.London：Springer Verlag，2001.