郭文卓

摘 要：針對(duì)模糊C-均值聚類算法不能很好對(duì)非橢球形分布，或結(jié)構(gòu)形狀不對(duì)稱分布的數(shù)據(jù)進(jìn)行聚類的問(wèn)題，文章提出了一種基于點(diǎn)密度的模糊C-均值聚類算法PD-FCM，該算法利用數(shù)據(jù)的點(diǎn)密度能夠反映其對(duì)不同數(shù)據(jù)密度分類的符合程度的這一特性，構(gòu)造了修正參數(shù)來(lái)改進(jìn)基于歐幾里德距離度量方式，從實(shí)現(xiàn)對(duì)FCM算法的優(yōu)化。在人造數(shù)據(jù)集和知名數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果該算法在準(zhǔn)確率和隸屬度的準(zhǔn)確s性方面優(yōu)于模糊C-均值聚類算法。

關(guān)鍵詞：聚類分析；模糊聚類；點(diǎn)密度；隸屬度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2016）02-0055-03

1 概 述

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

Dunn對(duì)硬C-均值算法HCM進(jìn)行了堅(jiān)實(shí)的分析后，提出了新的模糊劃分概念，采用了Ruspini定義的集合，用目標(biāo)函數(shù)的方式表達(dá)出硬C-均值算法，且可以應(yīng)用到模糊性的環(huán)境，得到了更簡(jiǎn)單和易懂的模糊C-均值聚類算法FCM[5]。這種類聚算法可以依據(jù)隸屬度而知道每個(gè)數(shù)據(jù)點(diǎn)隸屬哪個(gè)聚類的聚類算法。Bezdek為硬C均值聚類（HCM）方法改進(jìn)提出了這種方法。隨后，Bezdek對(duì)算法持續(xù)改進(jìn)，且證明了算法的收斂性[6]。Bezdek的貢獻(xiàn)為聚類問(wèn)題提供了一個(gè)很實(shí)際且有效的辦法，為未來(lái)模糊集理論的發(fā)展奠定了基礎(chǔ)。

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

2 PD-FCM算法

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

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

3 實(shí)驗(yàn)部分

為了驗(yàn)證算法的有效性，將本文提出的PD-FCM與經(jīng)典的模糊C-均值算法FCM進(jìn)行對(duì)比分析，實(shí)驗(yàn)中采用了兩種來(lái)源的數(shù)據(jù)集，一類是人造數(shù)據(jù)集，另一類是從UCI中選取的知名的數(shù)據(jù)集。所有實(shí)驗(yàn)程序采用JDK 1.6版本開(kāi)發(fā)，關(guān)鍵的參數(shù)模糊系數(shù)m設(shè)為2.0。每次實(shí)驗(yàn)重復(fù)10次，實(shí)驗(yàn)結(jié)果取平均值，評(píng)價(jià)標(biāo)準(zhǔn)采用準(zhǔn)確率precision：

3.1 人造數(shù)據(jù)集

采用隨機(jī)產(chǎn)生數(shù)據(jù)的方式構(gòu)造了1組人造數(shù)據(jù)集，該數(shù)據(jù)集包含兩個(gè)簇，兩個(gè)簇中的數(shù)據(jù)點(diǎn)的分布均采用二維正態(tài)分布，樣本個(gè)數(shù)均為100個(gè)，其中第1個(gè)簇中樣本點(diǎn)分布在坐標(biāo)原點(diǎn)為圓心，半徑為1的圓內(nèi)，而第2個(gè)簇中樣本點(diǎn)分布在以（5.5，0）為圓心，半徑為5的圓內(nèi)。顯然，第1簇中的數(shù)據(jù)密度大于第2組的。實(shí)驗(yàn)結(jié)果，如圖1所示。

從圖中可以直觀地看出PD-FCM更為準(zhǔn)確地將人造數(shù)據(jù)集劃分為了兩個(gè)簇。進(jìn)一步地，計(jì)算得到的準(zhǔn)確率如表1所示，同樣驗(yàn)證了PD-FCM對(duì)于FCM而言在針對(duì)第2簇的分類準(zhǔn)確率上有較大優(yōu)勢(shì)，這是因?yàn)閰⒖济芏葋?lái)更新距離的密度因子，因此提高FCM算法的準(zhǔn)確性。兩種算法的準(zhǔn)確率，見(jiàn)表1。

3.2 UCI數(shù)據(jù)集

從UCI數(shù)據(jù)集中選擇了兩組用于聚類任務(wù)的知名數(shù)據(jù)集，Wine和IRIS數(shù)據(jù)集，對(duì)PD-FCM和FCM算法進(jìn)行對(duì)比實(shí)驗(yàn)。IRIS數(shù)據(jù)集一共有150個(gè)樣本，維數(shù)為4，類別為3類，每類均有50個(gè)樣本。

第一類為Iris Setosa，該類別的樣本與其它類別的樣本的距離較大，而第2類Iris Versicolour和第3類Iris Virginica對(duì)應(yīng)的數(shù)據(jù)相距則較為接近，而且有一部分?jǐn)?shù)據(jù)是交叉或者重疊的。

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

首先對(duì)算法的有效性進(jìn)行分析。在這兩組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，見(jiàn)表2。

從表中可以看出，對(duì)于IRIS數(shù)據(jù)集，由于第1類數(shù)據(jù)距離其他兩組數(shù)據(jù)較遠(yuǎn)，所以2種算法均能很好地將其分離出來(lái)，對(duì)于數(shù)據(jù)之間存在融合的第2類和第3類數(shù)據(jù)，PD-FCM算法表現(xiàn)出更高的準(zhǔn)確性，較FCM算法提高了1%。但是，第2類的分類正確數(shù)有所下降。

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

隸屬度的準(zhǔn)確性也是評(píng)價(jià)模糊聚類算法的有效性的一個(gè)重要度量。下面以wine數(shù)據(jù)集為例，對(duì)兩種算法的最終隸屬度進(jìn)行分析。首先給出兩種算法正確分類樣本的隸屬度分布圖，如圖2所示。

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

4 結(jié) 語(yǔ)

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

實(shí)驗(yàn)結(jié)果也發(fā)現(xiàn)PD-FCM并不是總是優(yōu)于FCM算法，因此未來(lái)的工作可以考慮如何集成多種類型的模糊聚類算法，充分利用每種算法的優(yōu)勢(shì)進(jìn)一步提高算法的分類準(zhǔn)確性。

參考文獻(xiàn)：

[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] 陳科尹，鄒湘軍，熊俊濤，等.基于視覺(jué)顯著性改進(jìn)的水果圖像模糊聚類 分割算法[J].農(nóng)業(yè)工程學(xué)報(bào)，2013，（6）.

[3] 李波，邱紅艷.基于雙層模糊聚類的多車場(chǎng)車輛路徑遺傳算法[J].計(jì)算 機(jī)工程與應(yīng)用，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.，F(xiàn)ull，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）.