密度峰值優(yōu)化初始中心的K-means算法

李 敏 張桂珠

(江南大學物聯(lián)網(wǎng)工程學院 江蘇 無錫 214122)

密度峰值優(yōu)化初始中心的K-means算法

李 敏 張桂珠

(江南大學物聯(lián)網(wǎng)工程學院 江蘇 無錫 214122)

K-means算法隨機選取初始聚類中心，容易導致聚類結果不穩(wěn)定。為此，提出一種快速密度峰值搜索算法CFSFDP(clustering by fast search and find of density peaks)優(yōu)化初始中心的K-means算法。首先針對CFSFDP算法中截斷距離的選取影響局部密度的計算這一缺點，提出用動力學中的勢能替換數(shù)據(jù)點的局部密度；在此基礎上，利用改進的CFSFDP算法選取初始聚類中心，實現(xiàn)K-means聚類。在UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集上的測試結果表明，優(yōu)化后的新算法具有更好的聚類結果。

K-means算法 CFSFDP算法 密度峰值 引力勢能

0 引 言

聚類分析是一種無監(jiān)督的分類方法，是數(shù)據(jù)挖掘中的重要研究方向之一[1]。聚類分析是通過一定的準則將一個數(shù)據(jù)集劃分成不同的類或簇，使相同類或簇內的數(shù)據(jù)對象之間具有較高的相似性，而不同的類或簇之間的相異性則盡可能的大。目前在諸如模式識別、機器學習、圖像分析、神經網(wǎng)絡、客戶細分以及生物醫(yī)學等其他領域被廣泛應用[2]。傳統(tǒng)的聚類分析方法大致分為五類：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法[3]。

在聚類分析方法中， K-means算法是最著名和最常用的基于劃分的聚類算法[4]，K-means具有簡單、速度快的優(yōu)點，并且能夠有效地處理大文本集。但K-means算法要求事先選取初始聚類中心，初始聚類中心的選取嚴重影響聚類結果的好壞和算法的迭代次數(shù)。為此，很多學者致力于K-means算法初始聚類中心優(yōu)化研究。文獻[5]提出一種確定性的方法，計算樣本點的局部密度，以密度為根據(jù)選擇K-means算法的K個初始聚類中心。文獻[6]利用譜方法估計特征中心尋求初始聚類中心。文獻[7]采用密度敏感度量樣本相似性來計算對象密度，啟發(fā)性地生成初始聚類中心。文獻[8-10]使用不同的數(shù)據(jù)點密度計算方法，選擇互相距離最遠的K個位于高密度區(qū)域的數(shù)據(jù)點作為初始中心。上面所述的方法在一定程度上優(yōu)化了K-means算法的性能，但這些算法都需要通過人工選取參數(shù)，缺少客觀性。為此，本文基于數(shù)據(jù)點本身的密度大，且與比其密度大的其他點有相對更大的距離原理，提出利用密度峰值優(yōu)化初始中心的K-means算法。

快速密度峰值搜索算法CFSFDP[11]是一種基于密度的聚類算法。該算法思想簡單新穎，對于任意形狀的數(shù)據(jù)集，該算法能夠快速發(fā)現(xiàn)其密度峰值點。CFSFDP算法可以很好地剔除孤立點，并且能很好地處理大規(guī)模數(shù)據(jù)集。然而該算法也存在一些缺陷：該算法的成敗在某種意義上依賴于用于計算局部密度的截斷距離dc，文獻[11]中對dc的選取只是提供了一個參考建議，沒有給出一個計算方法；其次，對同一個類存在多密度峰值[12]的情況，該算法聚類并不理想。

綜合上述問題，本文提出了優(yōu)化方案。首先，利用勢能[13]代替局部密度來優(yōu)化CFSFDP算法，優(yōu)化后的算法(P-CFSFDP)解決了算法的好壞取決于參數(shù)dc的問題，然后用P-CFSFDP算法來確定初始聚類中心，最后用K-means算法進行迭代聚類。KP-CFSFDP算法可以自主地確定合適的初始聚類中心，解決了K-means算法隨機選取初始聚類中心而導致聚類結果不穩(wěn)定[14]的問題，且避免了聚類結果嚴重依賴于參數(shù)的選取問題，同時有效減少迭代次數(shù)。測試結果證實，KP-CFSFDP算法有更好的聚類效果。

1 快速密度峰值搜索算法及其改進

1.1 快速密度峰值搜索算法(CFSFDP)

CFSFDP算法的核心思想在于對聚類中心的刻畫上。聚類中心同時具有兩個特點：一是數(shù)據(jù)點本身的密度大，即它被密度小于它的鄰居包圍；二是與比它本身密度更大的數(shù)據(jù)點之間有相對更大的距離。

在文獻[5]中，對于數(shù)據(jù)集s={xi|xi∈Rn,i=1,2,…,n}，Is={1,2,…,N}為相應的指標集。數(shù)據(jù)集s中的每個數(shù)據(jù)點xi，定義兩個計算量：局部密度ρi和距離δi。

局部密度ρi有兩種計算公式，包括Cut-offkernel和Gaussiankernel。

Cut-offkernel：

(1)

其中dij=dist(xi,xj)代表數(shù)據(jù)點xi與xj之間的(某種)距離。函數(shù)χ(x)定義為：

(2)

截斷距離參數(shù)dc>0，需要通過人工選取。

Gaussiankernel：

(3)

對比式(1)和式(3)可知，Cut-offkernel為離散值，Gaussiankernel為連續(xù)值。

距離δi是通過計算數(shù)據(jù)點xi到任何比其密度大的點的最小距離得到的：

(4)

圖1 數(shù)據(jù)點分布

圖2 決策圖

由圖2可以發(fā)現(xiàn)，編號為1和10號的數(shù)據(jù)點由于同時具有較大的ρ值和δ值，于是脫穎而出，而這兩個點恰巧是圖1中的數(shù)據(jù)集的兩個聚類中心。而編號為26、27、28數(shù)據(jù)點是離群點，它們有共同的特點是：ρ值很小、但δ值很大。

為了能自動確定聚類中心的個數(shù)，本文提出計算一個綜合考慮ρ值和δ值的量γ。

γi=ρiδii∈IS

(5)

圖3所示為γ值降序排列結果。其中，下標為橫軸，γ值為縱軸。由圖可知，非聚類中心的γ值比較平滑，而從非聚類中心過渡到聚類中心時γ值有一個明顯的跳躍，這個跳躍可以明顯判斷出來。

圖3 γ值降序排列

1.2P-CFSFDP算法

文獻[5]中對于截斷距離參數(shù)dc，在沒有人工介入的情況下，對于如何選取dc值是不清楚的。然而，參數(shù)dc的選取對于局部密度的影響是很大的。例如，當dc取值過大時，ρi的值就會很接近而使區(qū)分度不高，極端情況是當dc>dmax時，數(shù)據(jù)集中的所有點被分為一個簇；而當dc取值過小時，同一個簇就可能被分成多個簇，極端情況是當dc

文獻[5]中必須通過人工選取一個敏感參數(shù)的情況是遺憾的，我們更希望文中的算法對參數(shù)不敏感，甚至希望參數(shù)可以被一個不變的或者一個自動選取值來代替。因此本文使用引力勢能代替數(shù)據(jù)點的局部密度，提出一種基于勢能的優(yōu)化的快速密度峰值搜索算法(P-CFSFDP算法)。在物理學中勢能概念的基礎上，將數(shù)據(jù)集假想為一個勢能場，所有的數(shù)據(jù)點對其它任何一個數(shù)據(jù)點都會有影響，所以能夠計算出每一個數(shù)據(jù)點的勢能。

由萬有引力定律，空間中的兩點i和j之間的引力為：

(6)

其中，G是萬有引力常量，mi和mj分別是質點i和j的質量，rij為質點i和質點j之間的距離。

根據(jù)勢能義可知，質點j對質點i產生的勢能為：

(7)

這里假設在歐氏空間中，每個數(shù)據(jù)點的質量都取1。為避免由于數(shù)據(jù)點i和數(shù)據(jù)點j之間的距離無限接近于零，使結果產生奇異值，這里通過設置閾值λ進行修正。則引力公式為：

(8)

相應的，勢能公式則變?yōu)椋?/p>

(9)

令G=1，則式(9)變?yōu)椋?/p>

(10)

那么在假想的這個勢能場中，所有數(shù)據(jù)點對數(shù)據(jù)點i產生的勢能總和為：

(11)

通過大量選取不同的λ值嘗試發(fā)現(xiàn)，在避免結果產生奇異值得情況下，閾值λ越小，找出初始聚類中心的能力越強。

(12)

(13)

其中，MinDi是數(shù)據(jù)點i與其他數(shù)據(jù)點之間距離的最小值，通過式(12)和式(13)便能計算出閾值λ。

2 改進的K-means算法

2.1KP-CFSFDP算法思想

本文KP-CFSFDP(密度峰值優(yōu)化初始中心的K-means算法)算法，是為了解決快速密度峰值搜索算法和K-means存在的問題而提出的。其貢獻是利用勢能Wi代替CFSFDP算法中數(shù)據(jù)點xi的局部密度ρi，通過CFSFDP算法生成的決策圖確定類個數(shù)k，以及初始聚類中心。然后使用K-means算法進行聚類。

2.2KP-CFSFDP算法描述

輸入：具有N個對象的待分類的數(shù)據(jù)集

輸出：滿足目標函數(shù)最小化的k個簇

Step1 初始化及預處理

1) 計算距離dij，令dji=dij，i

Step3 計算每個數(shù)據(jù)點和每個類的聚類中心的距離，將數(shù)據(jù)點歸類到與其距離最小的類中。

Step4 重新計算每個簇的質心，并計算聚類誤差平方和。

Step5 使用新的質心進行重新聚類，并計算聚類誤差平方和。

Step6 當聚類誤差平方和不再發(fā)生明顯變化，則算法終止，否則轉Step3。

3 實驗結果與分析

為了驗證本文算法的優(yōu)越性，分別在UCI數(shù)據(jù)集和經典人工模擬數(shù)據(jù)集上進行測試，并對算法進行了對比試驗。實驗環(huán)境為Intel(R) Core(TM) i3 CPU M 380 @ 2.53 GHz 2.53 GHz，內存2.0 GB，操作系統(tǒng)為Windows 7，使用 MATLAB R2011a進行仿真試驗。

3.1 P-CFSFDP算法實驗結果與分析

本文提出的P-CFSFDP算法使用勢能代替數(shù)據(jù)點的局部密度計算，下面將用Aggregation、Example和Flame這3個數(shù)據(jù)集對P-CFSFDP算法進行測試。Aggregation和Flame數(shù)據(jù)集為經典人工模擬數(shù)據(jù)集，Example數(shù)據(jù)集來自文獻[5]，數(shù)據(jù)集的構成描述如表1所示。將本文提出的P-CFSFDP算法與快速密度峰值搜索算法進行比較，驗證本文提出的P-CFSFDP算法的優(yōu)越性。

表1 數(shù)據(jù)集描述

圖4到圖9展示的上述三個數(shù)據(jù)集分別在快速密度峰值搜索算法(CFSFDP算法)和本文提出P-CFSFDP算法的實驗生成的決策圖。圖4和圖5對比，圖6和圖7對比，圖8和圖9對比。在CFSFDP算法中，截斷距離dc的選取滿足每個數(shù)據(jù)點的平均鄰居個數(shù)約為數(shù)據(jù)點總數(shù)的2%。

圖4 Aggregation數(shù)據(jù)集在CFSFDP算法中的決策圖

圖5 Aggregation數(shù)據(jù)集在P-CFSFDP算法中的決策圖

圖6 Example數(shù)據(jù)集在CFSFDP算法中的決策圖

圖7 Example數(shù)據(jù)集在P-CFSFDP算法中的決策圖

圖8 Flame數(shù)據(jù)集在CFSFDP算法中的決策圖

圖9 Flame數(shù)據(jù)集在P-CFSFDP算法中的決策圖

通過對比，本文P-CFSFDP算法在不需要人工介入選取參數(shù)的情況下能很好地找到初始聚類中心及類簇個數(shù)。尋找聚類中心的能力并不比CFSFDP算法差。綜合可知，本文P-CFSFDP算法能更好地選擇初始聚類中心。

3.2KP-CFSFDP算法實驗結果與分析

采用的實驗數(shù)據(jù)為UCI機器學習數(shù)據(jù)庫的Iris、Wine、Balance-scale和New-thyroid，并把本文算法與文獻[9-10]以及傳統(tǒng)K-means算法進行比較。

聚類評判結果使用聚類誤差平方和、聚類準確率，以及Rand指數(shù)和Jaccard系數(shù)進行評價[15]。一個聚類j及與此相關的分類i的準確率定義為：

準確率：Precision(i,j)=Nij/Ni

其中，Nij是在聚類j中分類i的數(shù)目；Ni是分類i中所有對象的數(shù)目。

Rand指數(shù)和Jaccard系數(shù)定義如下：設U和V分別是基于數(shù)據(jù)集的兩種劃分，其中U是已知正確劃分，而V是通過聚類算法得到的劃分，對于數(shù)據(jù)集中的任一對數(shù)據(jù)點，計算下列項：

SS：兩個點在V中同一簇，且在U中同一簇；

SD：兩個點在V中同一簇，但U中不同簇；

DS：兩個點不在V中同一簇，但在U中同一簇；

DD：兩個點不在V中同一簇，且不在U中同一簇。

設a、b、c、d分別表示SS、SD、DS、DD的數(shù)目，則a+b+c+d=M是數(shù)據(jù)集中所有樣本對的個數(shù)，即M=N(N-1)/2。其中，N為數(shù)據(jù)集的樣本數(shù)。Rand指數(shù)和Jaccard系數(shù)的定義如下：

Rand指數(shù)：R=(a+d)/M

Jaccard系數(shù)：J=a/(a+b+c)

其中，R表示Rand指數(shù)；J表示Jaccard系數(shù)。

由上述定義可知，Rand指數(shù)表示聚類結果與原始數(shù)據(jù)樣本分布的一致性；Jaccard系數(shù)表示正確聚類的樣本對越多，聚類效果越好。

UCI數(shù)據(jù)集的描述如表2所示。

表2 UCI數(shù)據(jù)集描述

下面用本文算法以及其他優(yōu)化初始中心的K-means算法進行測試，其他算法均使用最佳參數(shù)設置。其他算法對參數(shù)很敏感，本文使用其他算法的最佳結果與本文算法比較。表3為每個算法在UCI數(shù)據(jù)集上運行100次后的平均聚類誤差平方和。

表3 各算法在UCI數(shù)據(jù)集的聚類誤差平方和

由表3可知，本文算法在自動確定所給數(shù)據(jù)集的類簇個數(shù)和初始聚類中心的情況下，聚類誤差平方和明顯優(yōu)于傳統(tǒng)K-means算法、文獻[10]和文獻[9]算法。文獻[9]通過密度參數(shù)計算數(shù)據(jù)點所在區(qū)域的密度，選擇互相距離最遠的K個位于高密度區(qū)域的數(shù)據(jù)點作為K-means算法的初始聚類中心。文獻[10]以數(shù)據(jù)點為中心，計算以某一正數(shù)為半徑的球形域內數(shù)據(jù)點的個數(shù)，作為數(shù)據(jù)點密度，選擇互相距離最遠的K個位于高密度區(qū)域的數(shù)據(jù)點作為K-means算法的初始聚類中心。

圖10-圖12分別是每個算法的聚類準確率、聚類結果的RandIndex參數(shù)和Jaccard系數(shù)。

圖10 聚類準確率

圖11 聚類結果的Rand Index參數(shù)

圖12 聚類結果的Jaccard系數(shù)

由圖10可知，本文算法在New-thyroid數(shù)據(jù)集上盡管與文獻[9]有一樣的聚類效果，但在其他數(shù)據(jù)集上的聚類效果明顯優(yōu)于其他算法。圖11是關于數(shù)據(jù)集在四種算法上的聚類結果的Rand參數(shù)，由圖可知，本文算法在各個測試數(shù)據(jù)集上都有更好的聚類結果，在Balance-scale數(shù)據(jù)集上的聚類結果尤為突出。圖12是關于數(shù)據(jù)集在不同算法上的聚類結果的Jaccard系數(shù)，由圖可知，本文算法在每個測試數(shù)據(jù)集上的聚類結果都是較好的。通過分析可知，本文算法在沒有人工參與確定參數(shù)的情況下，能夠取得更好的聚類效果。

4 結 語

針對K-means算法隨機選取初始聚類中心導致聚類結果不好，且已有的對K-means優(yōu)化初始聚類中心的算法須要設置參數(shù)，且算法嚴重依賴參數(shù)的選取。本文利用快速密度峰值搜索算法對聚類中心刻畫的原理，將勢能的概念引入，避免了快速密度峰值搜索算法的聚類結果取決于截斷距離參數(shù)的選取問題。使用優(yōu)化的快速密度峰值搜索算法對數(shù)據(jù)集預處理，得到初始聚類中心，提出了基于密度峰值優(yōu)化的K-means算法。在UCI機器學習數(shù)據(jù)庫數(shù)據(jù)集和經典人工模擬數(shù)據(jù)集上的實驗結果證明，優(yōu)化后的新算法在不需要人為確定參數(shù)的情況下，不但能更好地確定類簇數(shù)和初始聚類中心，且比已有優(yōu)化初始中心K-means算法聚類結果更加精確。

[1]DattaSouptik,GiannellaChris,KarguptaHillol,etal.ApproximateDistributedK-MeansClusteringoveraPeer-to-PeerNetwork[J].IEEETransactionsonKnowledgeandDataEngineering,2009,21(10):1372-1388.

[2]ZhouTao,LuHuiling.Clusteringalgorithmresearchadvancesondatamining[J].ComputerEngineeringandApplications,2012,48(12):100-111.

[3]WangJun,WangShitong,DengZhaohong,etal.Surveyonchallengesinclusteringanalysisresearch[J].ControlandDecision,2012,27(3):321-328.

[4] 楊小兵.聚類分析中若干關鍵技術的研究[D].杭州:浙江大學,2005.

[5]KaufmanL,RousseeuwPJ.FindingGroupsinData:AnIntroductiontoClusterAnalysis[M].NewYork,USA:JohnWiley&Sons,Inc.,1990.

[6] 錢線,黃萱菁,吳立德.初始化K-means的譜方法[J].自動化學報,2007,33(4):342-346.

[7] 汪中,劉貴全,陳恩紅.一種優(yōu)化初始中心點的K-means算法[J].模式識別與人工智能,2009,22(2):299-304.

[8] 賴玉霞,劉建平.K-means算法的初始聚類中心的優(yōu)化[J].計算機工程與應用,2008,44(10):147-149.

[9] 袁方,周志勇,宋鑫.初始聚類中心優(yōu)化的K-means算法[J].計算機工程,2007,33(3):65-66.

[10] 王塞芳,戴芳,王萬斌,等.基于初始聚類中心優(yōu)化的K-均值算法[J].計算機工程與科學,2010,32(10):105-107.

[11]Rodriguez,Alex,AlessandroLaio.Clusteringbyfastsearchandfindofdensitypeaks[J].Science,2014,344(6191):1492-1496.

[12] 譚穎,胡瑞飛,殷國富.多密度閾值的DBSCAN改進算法[J].計算機應用,2008,28(3):745-748.

[13] 廖禮.一種新的基于密度的聚類算法研究[D].蘭州:蘭州大學,2013.

[14]PenaJM,LozanoJA,LarranagaP.AnEmpiricalComparisonofFourInitializationMethodsfortheK-MeansAlgorithm[J].PatternRecognitionLetters,1999,20(10):1027-1040.

[15] 楊燕,靳蕃,KamelM.聚類有效性評價綜述[J].計算機應用研究,2008,41(6):1631-1632.

K-MEANS ALGORITHM OF OPTIMIZED INITIAL CENTER BY DENSITY PEAKS

Li Min Zhang Guizhu

(SchoolofIOTEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)

K-means algorithm randomly selects the initial cluster centers, which can easily lead to the instability of clustering results. To overcome this deficiency, a K-means algorithm named clustering by fast search and find of density peaks (CFSFDP) is proposed to optimize the initial center. Firstly, aiming at the disadvantage that the selection of truncated distance in CFSFDP algorithm affects the local density, it is proposed that the local density of each point can be replaced by gravitational potential energy. Based on this, K-means clustering can be implemented by using the optimized CFSFDP algorithm to select initial cluster centers. The proposed algorithm is tested on UCI data sets and synthetic data sets. Experimental results show that the new algorithm can achieve better clustering.

K-means algorithm CFSFDP algorithm Density peak Gravitational potential energy

2016-04-06。江蘇省自然科學

BK20140165)。李敏，碩士生，主研領域：數(shù)據(jù)挖掘。張桂珠，副教授。

TP18

A

10.3969/j.issn.1000-386x.2017.03.038