一種混合模糊聚類算法

袁桂蓉

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

【關鍵詞】傳遞閉包 -統計量 模糊-均值聚類

聚類是按照一定的要求和規律對事物進行分類的過程，它根據研究對象的某些特性，運用數學方法對給定對象進行區分和分類。自Zadeh提出模糊集理論以來，人們開始用模糊的方法來處理聚類問題，并稱之為模糊聚類分析。

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

一、傳遞閉包法聚類

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

為了使不同量綱的數據也能進行比較，常常需要將原始數據矩陣進行極差化或標準化。這里先將原始數據矩陣統一趨勢化，得到無量綱矩陣X'nxm=（x"ij），其中x.ij=|xij-ui0|/iqr（xij）

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

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

（2）由相似矩陣求等價矩陣。因為模糊等價矩陣能對論域進行等價的劃分，這就能滿足聚類分析的需要。然而，通常情況下，由標定過程構造出的模糊關系僅僅能滿足自反性和對稱性，而不滿足傳遞性，所以生成的只是一個模糊相似矩陣R。為了進行分類，需要根據標定所得模糊矩陣R，求出其傳遞閉包t（R）。R=t（R）為模糊等價矩陣。

（3）進行聚類。將λ從1依次取到0，依次截得等價關系Rλ，并按Rλ將X分成等價類。

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

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

（2） FCM算法。Step1：將F-統計值最大的閾值λ對應的分類數目r作為聚類類別數c，2≤c≤n，n是數據個數，給定加權指數m，設定迭代停止閾值ε，初始化聚類中心V（0），設置迭代計數器b=0；

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

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

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

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

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

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

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

三、結論

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

參考文獻：

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

[2]王洪春，彭宏.一種基于嫡的聚類算法[J].計算機科學，2007.

[3]路金芳，孫雙全，楊建燕，伍化巖.統計學原理[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.