一種改進的模糊聚類算法研究

郭文卓

摘 要：針對模糊C-均值聚類算法不能很好對非橢球形分布，或結構形狀不對稱分布的數據進行聚類的問題，文章提出了一種基于點密度的模糊C-均值聚類算法PD-FCM，該算法利用數據的點密度能夠反映其對不同數據密度分類的符合程度的這一特性，構造了修正參數來改進基于歐幾里德距離度量方式，從實現對FCM算法的優化。在人造數據集和知名數據集上的實驗結果該算法在準確率和隸屬度的準確s性方面優于模糊C-均值聚類算法。

關鍵詞：聚類分析；模糊聚類；點密度；隸屬度

中圖分類號：TP311 文獻標識碼：A 文章編號：1006-8937（2016）02-0055-03

1 概 述

作為一種無監督的學習方法，聚類是根據數據集中樣本之間的相似度將數據集劃分為若干個簇的過程，在圖像處理、生物信息學、目標識別、醫學診斷等領域有著極其廣泛的應用[1，2，3]。按照樣本的隸屬度劃分，可以將聚類方法分為硬聚類和模糊聚類。硬聚類將樣本屬于某一簇的隸屬度設為0或1，其中取值為1表示該樣本完全屬于某一個簇，反之則完全不屬于，即樣本的類別是分明的。然而，在現實生活中，很多事物的屬性帶有模糊性，因此模糊聚類將每個樣本對各個簇的隸屬度擴展到區間[0，1]上來表示模糊性，對于簇彼此之中有噪聲和交集數據的數據集，模糊聚類的結果在一定程度上要比硬聚類方法更加科學[4]，可以滿足廣泛的應用需求。

Dunn對硬C-均值算法HCM進行了堅實的分析后，提出了新的模糊劃分概念，采用了Ruspini定義的集合，用目標函數的方式表達出硬C-均值算法，且可以應用到模糊性的環境，得到了更簡單和易懂的模糊C-均值聚類算法FCM[5]。這種類聚算法可以依據隸屬度而知道每個數據點隸屬哪個聚類的聚類算法。Bezdek為硬C均值聚類（HCM）方法改進提出了這種方法。隨后，Bezdek對算法持續改進，且證明了算法的收斂性[6]。Bezdek的貢獻為聚類問題提供了一個很實際且有效的辦法，為未來模糊集理論的發展奠定了基礎。

在聚類算法中用于度量樣本相似性或相異性的距離函數對于聚類結果有著重要的影響。經典模糊C-均值算法使用Euclid distance度量樣本的相似度，優點是簡單運算。缺點是對簇的大小/形狀，算法初始值都比較敏感，如在某些特定情況下，不能很好的劃分，Euclid distance方式也不能劃分密度接近的簇。通常，改變這一距離度量方式[7，8]可以部分的控制這些因素的影響。本文沿襲了這一思路，提出了改進的基于點密度的模糊C均值聚類算法PD-FCM，即根據點密度信息生成一個修正參數來彌補Euclid distance的缺陷，形成樣本與聚類中心的距離矩陣，從實現對FCM算法的優化。

2 PD-FCM算法

給定由n個樣本組成的數據集X={x1，x2，...，xn}，xi∈Rs，以及簇個數k。模糊聚類的基本思想是將數據集X劃分為k個簇s1，s2，...sk，使得公式（1）所示的目標函數最小。

Euclid distance方法計算樣本和樣本的相似性，由于簡單運算比較，不能處理形狀不對稱或者不是橢球形的簇，且不能劃分簇間數據密度不同的數據集。為此，引入點密度的概念，表示任意樣本點的密度，用于對距離度量方式進行改進，其計算方法如公式（2）：

3 實驗部分

為了驗證算法的有效性，將本文提出的PD-FCM與經典的模糊C-均值算法FCM進行對比分析，實驗中采用了兩種來源的數據集，一類是人造數據集，另一類是從UCI中選取的知名的數據集。所有實驗程序采用JDK 1.6版本開發，關鍵的參數模糊系數m設為2.0。每次實驗重復10次，實驗結果取平均值，評價標準采用準確率precision：

3.1 人造數據集

采用隨機產生數據的方式構造了1組人造數據集，該數據集包含兩個簇，兩個簇中的數據點的分布均采用二維正態分布，樣本個數均為100個，其中第1個簇中樣本點分布在坐標原點為圓心，半徑為1的圓內，而第2個簇中樣本點分布在以（5.5，0）為圓心，半徑為5的圓內。顯然，第1簇中的數據密度大于第2組的。實驗結果，如圖1所示。

從圖中可以直觀地看出PD-FCM更為準確地將人造數據集劃分為了兩個簇。進一步地，計算得到的準確率如表1所示，同樣驗證了PD-FCM對于FCM而言在針對第2簇的分類準確率上有較大優勢，這是因為參考密度來更新距離的密度因子，因此提高FCM算法的準確性。兩種算法的準確率，見表1。

3.2 UCI數據集

從UCI數據集中選擇了兩組用于聚類任務的知名數據集，Wine和IRIS數據集，對PD-FCM和FCM算法進行對比實驗。IRIS數據集一共有150個樣本，維數為4，類別為3類，每類均有50個樣本。

第一類為Iris Setosa，該類別的樣本與其它類別的樣本的距離較大，而第2類Iris Versicolour和第3類Iris Virginica對應的數據相距則較為接近，而且有一部分數據是交叉或者重疊的。

WINE數據集有178個樣本，維數為13，類別也為3類，三類樣本數分別是59、71和48，該數據集存在高維稀疏的特性。

首先對算法的有效性進行分析。在這兩組數據集上的實驗結果，見表2。

從表中可以看出，對于IRIS數據集，由于第1類數據距離其他兩組數據較遠，所以2種算法均能很好地將其分離出來，對于數據之間存在融合的第2類和第3類數據，PD-FCM算法表現出更高的準確性，較FCM算法提高了1%。但是，第2類的分類正確數有所下降。

對于Wine數據集而言，由于數據集本身具有高維稀疏的特性，這導致兩種算法的準確率都比較低；但PD-FCM算法由于采用了密度調節因子，所以準確率提升了4.9%，同樣地對第2類的分類結果也有影響，正確個數也小幅下降，但并未影響算法的準確率。

隸屬度的準確性也是評價模糊聚類算法的有效性的一個重要度量。下面以wine數據集為例，對兩種算法的最終隸屬度進行分析。首先給出兩種算法正確分類樣本的隸屬度分布圖，如圖2所示。

圖上的隸屬度越接近于1，則代表該算法的隸屬度的準確性越高。從圖中可以看出，在PD-FCM算法在第1類和第3類數據上獲得的隸屬度均較FCM算法有所提高，而第2類的隸屬度則有所下降，這就表明采用了密度信息的PD-FCM算法更加適用于模糊信息系統的生成。

4 結 語

相似性度量方法是聚類算法的重要組成部分，對于聚類結果有著重要的影響。本文為了克服歐氏距離度量方法對于簇的形狀、大小都比較敏感的問題，從優化相似性度量方法著手，提出了改進的基于點密度的模糊C均值聚類算法PD-FCM，該算法將樣本點的密度信息融入到距離度量方法和優化目標函數中，能否適應多種不同的簇形狀和大小，實驗結果也表明改進后的算法在準確率和隸屬度的準確性方面優于模糊C-均值聚類算法。

實驗結果也發現PD-FCM并不是總是優于FCM算法，因此未來的工作可以考慮如何集成多種類型的模糊聚類算法，充分利用每種算法的優勢進一步提高算法的分類準確性。

參考文獻：

[1] Sajith， A. G.， & Hariharan， S. Spatial fuzzy C-means clustering base

ed segmentation on CT images[A].The 2nd IEEE International Confer

ence on Electronics and Communication Systems （ICECS）[C].2015.

[2] 陳科尹，鄒湘軍，熊俊濤，等.基于視覺顯著性改進的水果圖像模糊聚類 分割算法[J].農業工程學報，2013，（6）.

[3] 李波，邱紅艷.基于雙層模糊聚類的多車場車輛路徑遺傳算法[J].計算 機工程與應用，2014，（5）.

[4] Velmurugan， T. Performance based analysis between k-Means and F

uzzy C-Means clustering algorithms for connection oriented telecomm

unication data.[J].Applied Soft Computing 2014，（19）.

[5] Bezdek，J.C.，Ehrlich，R.，Full，W.FCM：The fuzzyc-mean sclustering algorit

hm[J].Computers & Geosciences，1984，（2）.

[6] Pal， Nikhil R.， and James C. Bezdek. On cluster validity for the fuz

zy c-means model[J].IEEE Transactions on Fuzzy Systems，1995，（3）.

[7] WuKL， YangMS. Alternative c-means clustering algoritllms.[J] Pattem

Recognition.2002，（10）.

[8] Menard M， Courboulay V， Dardignac P. Possibilistic and probabililist

ic fuzzy clustering： Unification within the framework of the non-exte

nsive thermostatistics.[J]Pattern Recognition.2003，（6）.