融合密度峰值和模糊C-均值聚類算法*

任新維， 張桂珠

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122)

0 引 言

各類聚類分析的算法中，模糊聚類可以描述樣本類的中介性，從而更客觀地反映真實(shí)的世界，成為非監(jiān)督模式識別的一個重要分支，其中模糊C—均值(fuzzy C-means,FCM)聚類算法是運(yùn)用最廣泛的模糊聚類算法[1～3],但算法也存在著很多不足，如：對初始值過于敏感，容易陷入局部最優(yōu)，整體效率不高等[4,5]。密度峰值聚類[3](density peaks clustering,DPC)算法是Alex Rodriguez和Alessandro Laio提出的一種新的基于密度的聚類算法，其基本思想簡單且效率高，對于任意形狀的數(shù)據(jù)集，能夠快速發(fā)現(xiàn)其密度峰值點(diǎn)，但算法聚類效果在某種意義上依賴于用于計(jì)算局部密度的截?cái)嗑嚯xdc，而文獻(xiàn)[6]并沒有給出dc的計(jì)算方法；其次，對同一個類存在多密度峰值的情況，該算法聚類效果并不理想。

針對FCM算法和DPC算法存在的上述缺點(diǎn)，本文提出了DPC-FCM算法。實(shí)驗(yàn)結(jié)果表明DPC-FCM算法具有更好的聚類效果。

1 DPC算法及其改進(jìn)

1.1 算法基本思想[6]

理想的類簇中心周圍有局部密度較低的相鄰點(diǎn)圍繞，且與更高密度的任何點(diǎn)有相對較大的距離。為了準(zhǔn)確找到上述條件的類簇中心，需要計(jì)算每個數(shù)據(jù)點(diǎn)i的兩個量：局部密度ρi和數(shù)據(jù)點(diǎn)i到更高局部密度點(diǎn)j的最短距離δi，以刻畫聚類中心。ρi有Cut-off kernel和Gaussian kernel兩種計(jì)算方式，Cut-off kernel為

(1)

(2)

(3)

分別計(jì)算出樣本數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)xi的ρi，δi。然后再計(jì)算一個將ρ值和δ值綜合考慮的量γ

γi=ρiδi,i∈Is

(4)

將余下的數(shù)據(jù)點(diǎn)分配到與其距離最近且密度較其更高的點(diǎn)所屬的簇。然后算法定義每個簇的邊界區(qū)域密度ρb：屬于某個簇并且與屬于其他簇的數(shù)據(jù)點(diǎn)之間的距離小于截?cái)嗑嚯xdc的數(shù)據(jù)點(diǎn)總數(shù)。密度較ρb高的點(diǎn)視為核心點(diǎn)，其余的點(diǎn)視為噪聲點(diǎn)，由此得到聚類的最終結(jié)果。

1.2 算法的局限性[6]分析

1)關(guān)于數(shù)據(jù)集規(guī)模的大小判斷沒有確切的衡量標(biāo)準(zhǔn)，導(dǎo)致樣本密度計(jì)算方式的選取可能影響聚類的結(jié)果。

2)如果有一個樣本數(shù)據(jù)的聚類中心歸類出現(xiàn)了錯誤，即導(dǎo)致最終的聚類結(jié)果千差萬別。

3)對于比較復(fù)雜的數(shù)據(jù)集，由于不同類簇之間密度可能會有較大的差異，此時DPC算法如果繼續(xù)在歐氏距離測度下進(jìn)行聚類[7,8]，取值不同的截?cái)嗑嚯xdc就會產(chǎn)生不同的聚類結(jié)果，很容易得到錯誤結(jié)果。

1.3 DPC算法的改進(jìn)

本文采用了一種新的自適應(yīng)度距離來對DPC算法進(jìn)行改進(jìn)。在現(xiàn)有多種相似度度量中，自調(diào)節(jié)相似度[9]計(jì)算方法考慮到了鄰域數(shù)據(jù)分布對兩點(diǎn)相似度的影響，準(zhǔn)確反映復(fù)雜結(jié)構(gòu)數(shù)據(jù)集的分布特點(diǎn)

(5)

式中σi=d(si,sk)，其中點(diǎn)sk為si的第K個近鄰點(diǎn);σi為點(diǎn)si與sk的歐氏距離，根據(jù)文獻(xiàn)[9]令K=7，可以在高維數(shù)據(jù)的條件下得到較好的結(jié)果。在自適應(yīng)相似度測度下查看Jain數(shù)據(jù)集，設(shè)點(diǎn)a處在高密度簇中而點(diǎn)c處在低密度簇中，顯然σa<σc，可以推出σaσb<σcσb，從而得到Aab>Abc，由此可以看出,采用自適應(yīng)相似度的計(jì)算方法可以更好地度量不同密度簇之間點(diǎn)的相似度。本文將自適應(yīng)相似度轉(zhuǎn)換為權(quán)值加入到歐氏距離公式中，生成了一種新的加權(quán)歐氏距離公式

(6)

式中Aij∈[0,1]為點(diǎn)i和點(diǎn)j的自適應(yīng)相似度。

權(quán)值wi=1-Aij

(7)

在采用具有加權(quán)歐氏距離公式計(jì)算相似度后，各個對象之間的差異可以更準(zhǔn)確地算出來，DPC算法可以基于此公式計(jì)算每個數(shù)據(jù)點(diǎn)的局部密度ρi和點(diǎn)i到局部密度更高點(diǎn)的最近距離 ，從而更準(zhǔn)確地選取聚類中心點(diǎn)，提高聚類結(jié)果的準(zhǔn)確率。

2 FCM聚類算法

FCM聚類算法描述為：

1)確定類的個數(shù)k，指數(shù)權(quán)重α，初始化隸屬度矩陣U(0)。令m=1表示第一步迭代。

2)計(jì)算聚類中心。給定C(m)，計(jì)算U(m)。

3)重新計(jì)算隸屬度。給定U(m)，計(jì)算C(m)。

經(jīng)過上述4步的多次迭代，可以得到最終的隸屬度矩陣U和聚類中心V，使得目標(biāo)函數(shù)J(U,V)最小，再根據(jù)隸屬度矩陣U劃分樣本的最終分類。

3 DPC和FCM的融合算法

3.1 算法思想

算法分為2個階段：1)對每個數(shù)據(jù)計(jì)算兩個量ρi和δi,刻畫聚類中心，ρiδi值越大，該點(diǎn)越可能是聚類中心；2)運(yùn)用標(biāo)準(zhǔn)的FCM算法進(jìn)行迭代，獲得更好的聚類結(jié)果。

3.2 算法步驟

DPC-FCM算法總體如下：

階段一:執(zhí)行DPC算法，確定初始聚類中心。

輸入:樣本數(shù)據(jù)集X

輸出:聚類中心ci(k)。

1)根據(jù)加權(quán)歐氏距離公式計(jì)算數(shù)據(jù)點(diǎn)之間的距離；

2)根據(jù)步驟(1)計(jì)算的m=n(n-1)/2個距離進(jìn)行升序排列，設(shè)得到的序列為d1≤d2≤…≤dM,取該序列前2 %的數(shù)據(jù)，確定截?cái)嗑嚯xdc;

3)在步驟(1)得出的距離基礎(chǔ)上，計(jì)算每個數(shù)據(jù)點(diǎn)的局部密度ρi和數(shù)據(jù)點(diǎn)到局部密度較其大且距其最近的點(diǎn)的距離δi；

4)計(jì)算γi=ρiδi，繪制決策圖，γ越大越有可能是聚類中心，由此得到ci(k)。

階段二:執(zhí)行FCM算法。

輸入:迭代終止條件ε、模糊指數(shù)α、樣本數(shù)據(jù)集X、聚類中心ci(k);

輸出:隸屬度矩陣U、聚類中心C。

5)在完成上述4步的多次迭代后，根據(jù)最終得到的隸屬度矩陣U劃分樣本的最終分類。

4 實(shí)驗(yàn)分析

為了證明DPC-FCM算法的有效性，采用Iris數(shù)據(jù)集和Wine數(shù)據(jù)集以及一組人工數(shù)據(jù)集Dataset對2種算法進(jìn)行仿真實(shí)驗(yàn)。使用MATLAB R213a進(jìn)行實(shí)驗(yàn)，表1為用于實(shí)驗(yàn)的各個數(shù)據(jù)集構(gòu)成。

表1 實(shí)驗(yàn)數(shù)據(jù)集的構(gòu)成描述

選取UCI中的Iris數(shù)據(jù)集進(jìn)行驗(yàn)證，此數(shù)據(jù)集包含150個樣本，來自于三類鶯尾花的花朵樣本，每一類包含50個樣本，每個樣本又包含4個屬性：sepal length，sepal width，petal width，petal length，利用改進(jìn)的DPC算法選取聚類初始中心，然后與Iris實(shí)際的數(shù)據(jù)集進(jìn)行對比，如表2所示。

可以看出，本文提出的改進(jìn)算法選取的聚類初始中心與Iris數(shù)據(jù)集實(shí)際的中心非常接近，驗(yàn)證了本文算法有效性。

表2 初始聚類中心選取對比

在MATLAB仿真實(shí)驗(yàn)中，對原始的FCM算法、DPC-FCM算法在Dataset，Wine，Iris數(shù)據(jù)集逐個進(jìn)行50次試驗(yàn)，計(jì)算聚類正確數(shù)的平均值，得到的實(shí)驗(yàn)結(jié)果如表3所示。

表3 聚類正確結(jié)果對比

可以看出，F(xiàn)CM算法對初始值比較敏感，聚類效果比較差，尤其是在Wine這種相對復(fù)雜的數(shù)據(jù)集上，隨機(jī)選取聚類中心導(dǎo)致最終聚類結(jié)果不理想；而DPC-FCM算法將DPC與FCM結(jié)合，利用了DPC算法的選取聚類中心較為準(zhǔn)確的優(yōu)勢，與傳統(tǒng)的FCM算法相比，聚類效果得到了提升。

圖1為對Iris，Wine和自定義數(shù)據(jù)集Dataset分別應(yīng)用FCM，DPC-FCM算法的收斂速度對比。由圖可知，F(xiàn)CM尋優(yōu)能力較差，過分依賴于初始的聚類中心。而DPC-FCM算法，能更準(zhǔn)確地得到聚類中心，收斂速度更快，在尋優(yōu)效果和全局搜索能力上均有較好的表現(xiàn)。

圖1 在不同數(shù)據(jù)集上的測試

采用F-measure指標(biāo)、Rand指數(shù)和Jaccard系數(shù)對聚類結(jié)果進(jìn)行評估。

F-measure計(jì)算公式如下

(8)

式中P為精確率；R為召回率。F-measure指標(biāo)取值范圍為[0,1]，值越大表明聚類效果越好。

此外，Rand指數(shù)可以反映出聚類結(jié)果與最初數(shù)據(jù)集之間的分布；而Jaccard系數(shù)越大代表聚類效果越好。

表4 FCM算法實(shí)驗(yàn)結(jié)果

表5 DPC-FCM算法實(shí)驗(yàn)結(jié)果

從表4和表5可以看出，DPC-FCM算法的聚類結(jié)果優(yōu)于FCM算法。

5 結(jié) 論

通過實(shí)驗(yàn)數(shù)據(jù)的分析可知，DPC-FCM算法提高了聚類正確率、全局收斂速度和優(yōu)化精度，有效地提高了聚類的穩(wěn)定性和準(zhǔn)確性。

[1] 付爭方,朱 虹.基于模糊理論的低照度彩色圖像增強(qiáng)算法[J].傳感器與微系統(tǒng),2014,33(5)：121-124.

[2] 張國鎖,周創(chuàng)明,雷英杰.改進(jìn)FCM聚類算法及其在入侵檢測中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2009,29(5):1336-1338.

[3] Rodriguez Alex,Alessandro Laio.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[4] Zelnik-Manor L,Perona P.Self-tuning spectral clustering[J].Advances in Neural Information Processing Systems,2004,17:1601-1608.

[5] 李文杰，廖曉緯，束仁義，等.基于ZigBee和模糊C均值聚類算法在火警中的應(yīng)用[J].傳感器與微系統(tǒng)，2012,31(10):143-152.

[6] 楊 燕，靳 蕃，Kamel M. 聚類有效性評價綜述[J].計(jì)算機(jī)應(yīng)用研究,2008,41(6):1631-1632.

[7] 韓曉慧，王聯(lián)國.一種基于改進(jìn)混合蛙跳的聚類算法[J].傳感器與微系統(tǒng)，2012,31(4):137-139.

[8] 高孝偉.權(quán)熵法在教學(xué)評優(yōu)中的應(yīng)用研究[J].中國地質(zhì)教育,2008,17(4):100-104.

[9] 華 漫,李燕玲,魏永超.基于自適應(yīng)相似度距離的改進(jìn)FCM圖像分割[J].電視技術(shù),2016,40(2):33-36.