融合KNN優化的密度峰值和FCM聚類算法

蘭 紅，黃 敏

江西理工大學 信息工程學院，江西 贛州341000

聚類（clustering）就是將一個數據集分成多個簇（cluster）或類，使得在同一類簇中的數據樣本點之間具有相對高的相似度，而不同類簇中的數據樣本點差別較大。根據聚類的結果可以從數據中發現規律和知識，探索出藏在數據之后的規律和模式。聚類算法被普遍地運用在數據科學分析和實際工程領域中[1-4]，經過許多國內外研究人員的努力，產生了許多優秀的聚類算法，根據研究方向和算法實現原理的不同，目前聚類算法可劃分為基于密度的方法、基于網格的方法、基于層次的方法、基于模型的方法和基于劃分式方法等五種主流方法[5]。

模糊C 均值（Fuzzy C-Means，FCM）算法[6]是基于劃分式的聚類算法，此算法的基本思想是引入隸屬度概念來量化樣本點從屬于每個類簇的數值大小，由此進行劃分判斷，使得劃分到同一類簇的樣本間相似度最大、不同類簇的樣本間相似度最小，已達到對數據集劃分為各類簇的目的，在模式識別、數據挖掘、數據分析、矢量量化以及圖像分割等領域應用比較廣泛[7-8]。FCM算法是C-Means算法的衍生改進算法，C-Means算法對數據集劃分屬于硬性、具體的劃分，但FCM算法對數據集的劃分屬于軟（柔）性、模糊的劃分。FCM 算法沒有考慮到樣本點的鄰域關系和局部信息，容易導致算法對噪聲敏感。此外，FCM 算法在初始聚類中心的選取原則上是隨機選取，若初始聚類中心選擇不理想甚至選擇了噪聲點作為聚類中心，將導致算法收斂于局部極值點或得到錯誤的聚類結果。面對以上問題，許多科研專家使用不同的方法來改進FCM 算法。文獻[9-10]采用改良模糊加權指數的計算方法，聚類效果良好；文獻[11-12]通過改變數據加權的策略來優化迭代過程從而提高聚類的效果；文獻[13-14]從初始中心點的選擇出發，使用各種方法優化初始中心點的選擇來避免選中噪聲點，提高聚類的準確性；文獻[15-16]是根據數據集的空間分布信息，改變目標函數從而得到新的隸屬度計算方法；文獻[17-18]則是通過把密度峰值算法與FCM算法相結合的方法來優化FCM算法，達到了較好的效果。

文獻[9-16]這些改進方法都是根據模糊C均值算法某個方面的不足朝特定的方向優化改良FCM 算法，聚類效果在一定程度上得到了提升和改善，但是未綜合考慮到數據樣本中的樣本數據和噪聲數據點的空間分布信息對聚類效果的影響。文獻[17-18]主要是利用樣本的局部密度信息，使用密度峰值算法來優化初始中心的選擇，從而使得改進后的算法在抗噪性和全局收斂能力上超過其他算法，但是在使用密度峰值算法時保留了需要主觀選擇的截斷距離dC，影響了聚類效果，尤其在數據集樣本規模較小時影響較大。因此，本文提出了一種融合KNN優化的密度峰值和FCM聚類的改進算法，使用KNN來代替截斷距離dC，既解決了需要主觀選擇截斷距離的問題又使得在樣本密度度量方面有了統一的密度度量準則，進一步提升了FCM算法的性能。

1 KNN優化的DPC算法

1.1 算法基本思想

快速搜索和查找樣本密度峰值的聚類算法[19]（clustering by fast search and find of density peaks，DPC算法）可以快速地找到任意形態、規模數據集樣本的密度峰值即類簇中心點，在大規模聚類處理分析方面表現出色，其基本思想是，在理想情況下，類簇中心周圍的樣本點的局部密度要小于類簇中心的局部密度，且不同類簇中心間應有較遠的距離。根據這兩個特點，設計了兩個變量，一個是樣本i 的局部密度ρi；另一個是樣本i到距離它最近且局部密度比它大的樣本i 的距離δi，它們的定義如公式（1）和（2）所示：

由公式（1）～（3）可知，當數據樣本點i 的局部密度ρi最大時，它的δi距離將遠大于其他樣本點的δi距離，δi距離異常大的點往往是該數據樣本集的類簇中心，其樣本點的局部密度也相對較大，因此，DPC 算法是用構造樣本點的局部密度ρi和樣本距離δi值二維決策圖的方法來選擇數據集樣本的類簇中心（ρi和δi值都較大時對應的點）。但是當每個類簇數據集規模都較小時，樣本的稀疏性會導致類簇中心點模糊，要找到其密度峰值點是十分困難的[19]，這時將采用綜合變量γi構成的曲線決策圖來尋找密度峰值點[19]，其公式如式（4）所示：

γi值越大則為密度峰值點的可能性越大，對γi排序再從中選擇最大的若干個點作為密度峰值點，其余的樣本點分配到與其最近的密度峰值點形成類簇。為了避免樣本噪聲點的影響，DPC算法給每個類簇定義了邊界區域：由屬于該類簇但與其他類簇數據樣本點的距離小于截斷距離dc的數據樣本點構成[21]。設置一個閾值ρb：每個類簇邊界區域數據樣本點總數值[17]。每個類簇中的數據樣本點的局部密度大于ρb值則視為核，反之則視為噪聲樣本點，由此得到最終的聚類結果。

1.2 算法局限性分析

（1）根據數據集樣本規模的大小不同，采用了兩種不同度量樣本局部密度的方法，但是沒有一個客觀科學的標準來判定數據集規模的大小，導致聚類結果受樣本局部密度度量方法的影響。

（2）當數據集相對復雜時，不同類簇的密度會有較大的差異，使用歐氏距離進行密度度量，取不同的截斷距離將會導致完全不同的聚類結果，容易出錯，并且截斷距離是人為設定，沒有一個明確的標準和規范。

（3）DPC 聚類算法在樣本聚類時具有連錯效應，即若有一個樣本分類錯誤，其他樣本接著分類錯誤，將導致千差萬別的聚類結果。

2 KDPC和FCM的融合算法

2.1 DPC算法的改進KDPC

本文引入了樣本的K 近鄰信息來對DPC算法進行改進優化（KDPC），為了統一DPC聚類算法中兩種計算樣本局部密度的方法準則，提出了一種新的不受dc影響的樣本局部密度計算方法，該方法適用于不同規模的數據集。

使用樣本點的K 鄰近信息來計算樣本的局部密度ρi值，其定義如式（5）所示：

當樣本點的K 鄰近距離越大時，其ρi值就越小，否則反之。與式（1）和式（3）相比較，參與式（5）的計算范圍要小很多，原本需要樣本點與數據集其他所有樣本點之間的距離參與密度計算，現在只要樣本點與之相鄰的K 個樣本點之間的距離參與密度計算即可，更加能夠反映出樣本點的局部密度信息。

為了減少噪聲樣本的干擾，在計算數據樣本點的局部密度之前，要將噪聲樣本剔除，為了識別出噪聲樣本，本文對其有如下定義：若樣本點的KNN 距離大于數據集中所有樣本點的平均KNN 距離，則該樣本點被認定為噪聲樣本點。樣本點的KNN距離Kd(i)計算如式（6）所示，數據集中所有樣本點的平均KNN距離M 計算如式（7）所示，噪聲樣本點的識別函數N 如式（8）所示。

上式中K( i )為數據樣本點i 的K 鄰近點集合，N 表示數據集中總樣本數。

KDPC 算法首先運用式（6）～（8）識別標記噪聲樣本，減少噪聲對整體算法的影響，其次用引入K 鄰近信息的式（5）來代替式（1）和（3）計算出數據集中每個樣本點的局部密度值，接著用式（2）計算出每個樣本點的δi值，最后使用式（4）來選取數據集中的若干密度峰值即聚類中心點。KDPC 算法避免了DPC 算法需要主觀判斷數據集規模、人工設定截斷距離dc等問題，從而更加精準地找到數據集的密度峰值點。

2.2 FCM聚類算法

FCM聚類算法將數據集樣本點之間的相似程度定義為隸屬度，假設數據集為X={x1,x2,…,xn}，被劃分為i 類，聚類中心點為ci，則數據集中任意樣本點j 與某個類中心點ci的隸屬度為uij，其目標函數（9）和約束條件（10）如下所示：

式中，m 為隸屬度uij的指數權重因子，n 為數據集樣本總數。采用拉格朗日乘數法及其他數學運算方法，當目標函數最小時，解出uij的值為式（11）所示，ci的值為式（12）所示。

FCM 算法的步驟為：先隨機初始化一個滿足約束條件（10）的uij值，然后根據式（12）計算出ci的值，其次將得到的ci作為輸入，根據式（11）計算出新的uij值，此時根據式（9）計算出目標函數J 值。再次根據式（12）、（11）和（9）迭代計算出ci、uij和J 的值，如此循環迭代計算，當J 達到最小值時停止計算，輸出ci和uij的值，完成聚類。

2.3 算法思想

算法總體可分為兩部分，（1）KDPC 部分：運用KDPC算法思想計算出數據集中所有樣本點的γi值，根據γi值大小進行排序（從大到小排序），假設數據集可分為c 類，則選取γi值排序后的前c 個樣本點作為該數據集的聚類中心點；（2）FCM部分：運用第（1）部分獲得的聚類中心，計算出對應的隸屬度uij，開始循環迭代計算，滿足終止條件完成聚類，獲得更加精準的聚類結果。

2.4 算法步驟

KDPC-FCM算法步驟如下：

KDPC部分：運用改進的密度峰值算法初始化數據集的聚類中心，具體步驟如算法1所示。

算法1KDPC部分算法步驟

輸入：樣本數據集X ，類別數c。

輸出：初始化聚類中心集ci(0)。

處理過程：

步驟1數據預處理：對數據進行歸一化處理。

步驟2根據式（6）～（8）對數據集中的噪聲樣本進行識別并標記，去除噪聲樣本點。

步驟3計算數據集中非噪聲樣本間的歐式距離，根據式（5）計算出非噪聲樣本點的局部密度ρi值。

步驟4根據步驟3 中獲得的ρi值，運用式（2）計算出非噪聲樣本點的δi值。

步驟5根據式（4）計算出非噪聲樣本點的γi值，由該值大小將非噪聲樣本點進行從大到小排序。

步驟6在排序后的非噪聲樣本點中選取前c 個樣本點，得到該數據集的初始化聚類中心集ci(0)。

FCM部分：根據KDPC部分得到的聚類中心集ci(0)，使用FCM 算法進行循環迭代計算，獲取聚類結果。具體步驟如算法2所示。

算法2FCM部分算法步驟

輸入：樣本數據集X，初始化聚類中心集ci(0)，指數權重因子m（一般選取m=2 效果最佳）。

輸出：聚類中心集ci，隸屬度矩陣uij。

處理過程：

步驟1初始化迭代次數t，令t=0。

步驟2根據初始化聚類中心集ci(t)，由式（11）計算出隸屬度矩陣uij(t)。

步驟3根據ci(t)、uij(t)，由式(9)計算出目標函數J(t)值。

步驟4根據隸屬度矩陣uij(t)，由式(12)計算出新的聚類中心集ci(t+1)。

步驟5根據聚類中心集ci(t+1)，由式(11)計算出新的隸屬度矩陣uij(t+1)。

步驟6根據ci(t+1)、uij(t+1)，由式（9）計算出新的目標函數J(t+1)值。

步驟7判斷J(t)-J(t+1)＞0 是否成立，若是，則t=t+1 并轉到步驟4繼續執行；否則，終止運算。

步驟8完成上述7 步，多次迭代后得到最終的聚類中心集ci值和隸屬度矩陣uij，由此劃分數據集，得到聚類結果。

2.5 算法具體流程

KDPC-FCM算法的總體流程如圖1所示，首先對數據進行歸一化預處理，減少后續運算量，運用自定義的噪聲識別函數N將數據集中的噪聲樣本標記剔除，然后利用式（5）計算出每個非噪聲樣本點的局部密度ρi，接著使用式（2）和（4）分別計算出非噪聲樣本點的δi值和γi值，根據γi值的大小排序得到數據集的初始化聚類中心點集合ci(0)，到此KDPC 部分結束；開始FCM 部分：初始化指數權重因子令m=2，根據KDPC部分得到的ci(0)開始循環迭代計算聚類中心集ci的值和隸屬度矩陣uij的值，當目標函數穩定不變時終止迭代，根據最終得到的ci和uij劃分數據集輸出最后的聚類結果。

圖1 KDPC-FCM算法總體流程圖

3 實驗分析

為了驗證本文KDPC-FCM 算法的有效性，在加利福尼亞大學爾灣分校（University of California，Irvine，簡稱UC Irvine 或UCI）的機器學習數據庫上的多個真實數據集和人造數據集上進行實驗，對比算法有FCM聚類算法，以及文獻[18]提出的DSFCM 聚類算法。采用Python進行仿真實驗，各數據集的情況如表1所示。

表1 各數據集的情況

其中，Iris 和Wine 數據集都是UCI 上的真實數據集，C5數據集是人造數據集。Iris數據集是鳶尾花樣本分類數據集，包含4 個屬性分別是：萼片長度、萼片寬度、花瓣長度和花瓣寬度；分為3 類：Setosa、Versicolour和Virginica，每個類別都有50個樣本，共150個樣本；C5數據集是個二維數據集，包含形狀類似5 個圓的樣本點，即5個類簇，每個類簇又由20個樣本點組成，并且在這5 個類簇周圍有200 個隨機噪聲點樣本。Wine 數據集是葡萄酒分類數據集，由組成葡萄糖的13 種物質含量作為其屬性，分為3 類：Class1、Class2 和Class3，分別包含59、71和48個樣本。

3.1 初始化聚類中心對比分析

為了驗證DPC的改進算法KDPC算法的有效性，運用KDPC 算法對Iris 數據集進行初始化聚類中心的選取，并與Iris數據集的實際中心作對比，如表2所示。

表2 初始化聚類中心對比

從表2可以看出，KDPC算法初始化Iris數據集聚類中心結果與Iris 數據集的真實聚類中心非常近似，誤差在百分數級別，這證明了KDPC算法能夠優化初始聚類中心的求取結果，為后續FCM 算法聚類打下了較好的基礎，驗證了KDPC算法的有效性。

圖2 C5數據集上各算法聚類結果圖

3.2 抗噪性對比分析

C5數據集是本文人造數據集，由樣本分布在5個半徑都為0.2的圓上以及周圍的隨機噪聲樣本組成，其中5個圓是圓心點分別為（1，2），（2，2），（0，2），（1，3），（1，1）。樣本的分布特征為每個圓上均勻分布20 個樣本點，分布在5個圓周圍的200個隨機噪聲樣本點滿足在5個圓之外，中心點位于（1，2）、寬為5高為4的矩形之內，并且服從均勻分布。具體分布情況如圖2（a）所示。使用C5 數據集對FCM 算法、DSFCM 算法和本文提出的KDPC-FCM算法進行抗噪性對比試驗。三種算法分別在該數據集上運行100次，觀察記錄其聚類結果。實驗結果如下：FCM算法在100次聚類過程中，有23次實驗聚類結果不理想，其中一次的聚類結果如圖2（b）所示；DSFCM算法和本文KDPC-FCM算法在100次實驗中都取得了不錯的聚類結果，圖2（c）和圖2（d）分別為兩種聚類算法的某一次聚類結果。

圖2（a）中的每個黑色點代表著C5 數據集中的每個數據樣本。圖2（b）～（d）中的不同彩色點代表不同的類簇，即相同的顏色為一類，黑色樣本點為識別出的噪聲樣本點，其中分類錯誤樣本點被紅色矩形框標注。圖2（b）中有29 個樣本點被標注紅色矩形框，圖2（c）和圖2（d）分別有11個和5個樣本點被標注。

實驗結果分析：FCM 算法不僅將數據集外圍的許多噪聲樣本進行了分類，其內部類簇數據樣本點也存在著分類錯誤的情況，這是由于FCM 算法初始化隸屬度矩陣uij是隨機的，這導致了得到的初始化聚類中心也是隨機的，一旦初始化聚類中心點選擇不當，將導致聚類結果出現大量的錯誤分類；DSFCM 算法將一小部分靠近C5 最大的圓型類簇噪聲樣本進行了錯誤分類，總體聚類效果良好，這是由于DSFCM 算法采用了結合密度峰值和樣本空間信息的方式來優化初始化聚類中心的選擇，因此取得了較好的實驗結果；KDPC-FCM算法僅將逼近圓樣本的5個噪聲樣本誤識別屬于樣本類簇，聚類效果較好，這是由于KDPC-FCM 算法在初始化聚類中心時，先對噪聲進行了定義和識別，降低了噪聲樣本對聚類結果的影響。

從上述實驗結果及分析可以得出結論：FCM 算法對噪聲敏感，DSFCM算法和KDPC-FCM算法都具有良好的抗噪性，并且KDPC-FCM 算法要略優于DSFCM算法。

表3 Wine數據集上各聚類算法三種聚類評價指標值對比%

3.3 聚類效果及魯棒性對比分析

為了驗證三種算法的聚類效果及魯棒性，本文采用UCI 數據庫中的Wine 數據集進行仿真對比實驗，該數據集同Iris 數據集一樣，是聚類算法實驗中常用的數據集。采用F-measure指標、蘭德指數（Rand Index，RI）和Jaccard系數來評價三種算法在Wine數據集上的聚類效果，三項檢測指標數越大證明聚類效果越好。

F-measure指標計算公式為：

式中，β為參數變量，本文使用β=1 進行計算，P是精準率，R是召回率，F-measure 的取值范圍為[0，1]。T表示數據集的真實分布，F表示算法聚類結果分布，P和R的取值范圍均為[0，1]。

蘭德指數及Jaccard系統計算公式為：

式中，TP表示同一類的樣本被分到同一類簇的對數；TN表示不同類的樣本被分到不同類簇的對數；FP表示不同類的樣本被分到同一類簇的對數；FN表示同一類的樣本被分到不同類簇的對數。RI和Jaccard的取值范圍也都為[0，1]。

使用FCM算法、DSFCM算法以及本文KDPC-FCM算法分別對Wine 數據集進行聚類，使用上述三項聚類結果檢測指標分別對三種算法的聚類結果進行檢測運算，其檢測的結果如表3 所示。從表中可以看出：在F-measure 指標下，FCM 算法在Class2 類別處的值要略高于DSFCM算法，其他類別均是KDPC-FCM＞DSFCM＞FCM；在RI指數下，FCM算法在Class3類別處的值要高于DSFCM 和KDPC-FCM 算法，其他類別均是KDPCFCM＞DSFCM＞FCM；在Jaccard 系數下，三類別均是KDPC-FCM＞DSFCM＞FCM。綜合來看，在Wine數據集下總體各指標值均是KDPC-FCM＞DSFCM＞FCM，表明本文KDPC-FCM 在Wine 數據集下聚類效果方面要優于DSFCM和FCM算法。

為了檢驗三種算法的魯棒性能，本文采用的方法是：將三種算法在Wine數據集上各進行50次運算實驗，然后計算出每個算法在上述三種聚類評價指標的標準差，標準差越小，證明算法的波動性越小，穩定性和魯棒性越強。經過實驗的結果并運算得出各算法的標準差，三種對比算法在三種不同聚類評價指標上的標準差結果如表4所示。

表4 各算法在各評價指標的標準差對比

從表4 的結果可以看出KDPC-FCM 算法的標準差在三種評價指標上均要小于其他兩種算法，為了進一步驗證KDPC-FCM 算法的聚類效果和魯棒性，分別使用三種對比算法在表5所示的6個基準數據集上進行聚類實驗。

表5 各基準數據集

經過實驗，在以上六種基準數據集上的聚類效果如圖3所示。

圖3 各算法在六種基準數據集上聚類效果對比圖

圖3中的不同彩色點代表不同的類簇，即相同彩色點為同一類簇，其中灰色點為識別出的噪聲樣本點。根據圖3 可以看出，在Aggregation、R15 及D31 三種基準數據集上DSFCM 算法和KDPC-FCM 算法的聚類效果差不多，而FCM 算法聚類效果較以上兩種算法效果較差；在Flame、Blobs 及Compound 三種基準數據集上，DSFCM算法要比FCM算法效果稍好一點，而KDPC-FCM算法的聚類效果最好。

綜合在Wine數據集和六種基準數據集上的實驗對比分析，可以得出初步結論：在三種對比算法中，FCM算法的聚類效果和魯棒性較差，DSFCM算法次之，本文KDPC-FCM算法聚類效果和魯棒性較強。

3.4 性能對比分析

為了對本文提出的算法進行性能對比分析，在不同規模的數據集上分別進行實驗，用于實驗的數據集如表6所示。

表6 性能對比實驗數據集

User等6個的數據集來自微軟亞洲研究院的Geolife項目[22]。該項目數據集包含182個用戶在超過五年（2007年4月至2012年8月）時間里的戶外活動。該數據集的GPS軌跡由一系列帶有時間戳的點表示，每個點包含緯度、經度和高度信息。User000表示為使用了編號為000的用戶所有活動數據，User000-002表示使用編號從000至002的三個用戶的所有活動數據，其他數據集依次類推。

采用Geolife項目數據集測試數據規模對性能的影響實驗，即表6 中的6 個User 數據集，分別使用FCM、DSFCM以及本文KDPC-FCM算法在這6個數據集上進行聚類，并記錄在每個數據集上運行的時間，得到如表7所示的實驗結果。

表7 規模性能實驗結果s

由于本文主要是針對FCM 算法進行對比分析，因此表7 中KDPC-FCM 的實驗結果并未加上KDPC 運行的時間。

從表7 可以看出，隨著數據集的樣本數的規模增加，三種算法的時間也隨之增加，且KDPC-FCM算法的聚類速度明顯要快于其他兩種算法，且隨著數據集的樣本數量達到百萬級別時，FCM 算法的聚類時間將非常漫長，本文由于時間限制，用“—”表示其時間暫時無法計算，而DSFCM和KDPC-FCM算法在數據達到千萬級別時，速度仍比較快，且KDPC-FCM算法保持在1 min內。

4 總結

本文針對FCM 算法對噪聲點敏感、容易局部收斂等問題，提出了融合KNN優化的密度峰值和FCM聚類算法KDPC-FCM，該算法先將噪聲樣本識別去除后，在使用引入的樣本的K近鄰信息來計算樣本的局部密度，對DPC算法進行了改進，使得初始化中心點更加接近真實數據中心點，從而使得FCM算法可以更加精準快速地得到較好的聚類結果。為了驗證算法的有效性，本文在UCI中的多個數據集、一個人工數據集、多個基準數據集以及微軟亞洲研究院的Geolife項目數據集上進行實驗，并與傳統FCM算法和DSFCM算法進行了對比分析，得出結論：KDPC-FCM算法能夠有效提高聚類的抗噪性、準確性和全局收斂能力，達到了較好的聚類效果。