一種融合K-means和快速密度峰值搜索算法的聚類方法

盛　華　張桂珠

1(江南大學物聯網工程學院　江蘇 無錫 214122)2(江南大學輕工過程先進控制教育部重點實驗室　江蘇 無錫 214122)

?

一種融合K-means和快速密度峰值搜索算法的聚類方法

盛華1張桂珠2

1(江南大學物聯網工程學院江蘇 無錫 214122)2(江南大學輕工過程先進控制教育部重點實驗室江蘇 無錫 214122)

K-means算法的初始聚類中心是隨機選取的，不同的初始中心輸入會得出不同的聚類結果。針對K-means算法存在的問題，提出一種融合K-means算法與聚類的快速搜索和發現密度峰算法的聚類算法(K-CBFSAFODP)。該算法是這樣考慮的：類簇中心被具有較低局部密度的鄰居點包圍，且與具有更高密度的任何點都有相對較大的距離，以此來刻畫聚類中心；再運用K-means算法進行迭代聚類，彌補了K-means聚類中心隨機選取導致容易陷入局部最優的缺點；并且引入了熵值法用來計算距離，從而實現優化聚類。在UCI數據集和人工模擬數據集上的實驗表明，融合算法不僅能得到較好的聚類結果，而且聚類很穩定，同時也有較快的收斂速度，證實了該融合算法的可行性。

聚類K-means算法CBFSAFODP算法初始聚類中心密度信息熵

0　引　言

聚類分析是一種無監督的機器學習方法，是數據挖掘中的重要研究方向之一[1]。它基于“物以類聚”原理，即在同一個簇中的數據對象之間具有較高的相似度，而在不同簇數據對象間具有較低的相似度。目前聚類分析已經廣泛地應用到許多領域，如模式識別、數據分析、圖像處理、市場分析、客戶關系管理等[2]。聚類分析的常用方法可大致劃分為五類：基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法和基于模型的方法[3]。

在數據挖掘下的聚類分析方法中，K-means算法是運用最廣泛的基于劃分的算法。它理論證實可靠、算法簡單可行、收斂速度很快，對大數據集的處理很有效果。但K-means算法也存在一些缺陷：對K值的選擇沒有準確依據、聚類結果的好壞嚴重依賴初始聚類中心的設定、容易陷入局部最優解、只能處理數值屬性的數據以及無法檢測到的非球形簇[4]。

CBFSAFODP算法(Alex Rodriguez 和 Alessandro Laio 在 Science 上發表了一篇名為《Clustering by fast search and find of density peaks》的文章，本文姑且稱這篇文章中的算法為CBFSAFODP)是屬于數據挖掘下聚類分析方法中一種應用廣泛的基于密度的算法。該算法簡單新穎、對初始值不敏感、靈活性好、能檢測非球形簇以及能有效地處理大數據集，在解決聚類初始中心[5]選取方面很有針對性，目前已被應用到數據挖掘。然而一些單一的聚類方法往往得不到最佳的聚類效果。

為了克服CBFSAFODP算法在聚類效果上的不足，本文提出一種融合K-means算法與聚類的快速搜索和發現密度峰算法的聚類算法。K-CBFSAFODP是把K-means算法融入到CBFSAFODP中去，在執行CBFSAFODP算法選取好聚類中心后，再運用K-means算法進行迭代聚類，彌補了K-means聚類中心隨機選取導致容易陷入局部最優的缺點。該算法為聚類算法選擇初始聚類中心提供了一種新的思路，能夠更加合理地選取聚類數K以及初始聚類中心，極大程度上減少K-means算法因初始聚類中心的不合理選取導致聚類結果的不穩定性[6]，以及過多依賴參數選擇問題。實驗結果表明，K-CBFSAFODP比單獨的K-means、CBFSAFODP具有更好的聚類效果。

1　聚類的快速搜索和發現密度峰算法

1.1算法思想

CBFSAFODP算法[7]基于這樣的設想：類簇中心被具有較低局部密度的鄰居點包圍，且與具有更高密度的任何點都有相對較大的距離。對于每一個數據點需要計算兩個量(ρi和δi)：一是局部密度；二是與高于該點的所有局部密度中與該點距離[8]的最小值，來刻畫聚類中心。然后對每個cluster確定其邊界區域[9]，再將其中的數據點進一步分為cluster core和cluster halo，從而實現聚類的方法。

1.2算法聚類中心的選取

S={xi|xi∈Rn,i=1,2,…,n},IS={1,2,…,n}。設ρi包含Cj(j=1,2,…,k)個簇，Cj(j=1,2,…,k)表示初始的聚類中心，dij=dist(xi,xj)表示數據點xi與xj之間的(某種)距離。

(1) 樣本xi與xj之間的歐氏距離：

(1)

(2) xi局部密度ρi：包括Cut-off kernel 和 Gaussian kernel兩種計算方式。

Cut-off kernel:

(2)

其中，如果x<0，那么χ(x)=1，否則χ(x)=0;dc是一個截斷距離。其實就是與點xi的距離小于dc的點的個數(不包括自己)，這意味著對于大數據集，分析結果對于dc的選擇具有很好的魯棒性。根據大量實驗表明，dc一般取聚類中所有數據點之間相互距離按升序排列的2%位置的距離數值定義為dc。

Gaussian kernel:

(3)

對比定義可知，cut-off kernel為離散值，Gaussian kernel為連續值。相對而言，后者產生沖突的概率較小，即不同數據點具有相同局部密度之概率更小。

(3) 數據點xi的δi是點到任何比其密度大的點的距離的最小值。

則可定義如下：

(4)

圖1　數據點按照密度降序排列　　圖2　圖1中數據的決策圖

由圖2不難發現，第1號和第10號數據點由于同時具有較大的ρ值和δ值，于是從數據集中脫穎而出，而這兩個數據點恰好是圖1所示數據集中的兩個聚類中心。此外，編號為26、27、28的三個數據點在原始數據集中是“離群點”，它們在圖2中也有特點：其δ值很大，但ρ值很小。

(5) 由于圖2對確定聚類中心起到決定作用，因此也將這種由(ρi,δi)對應的圖稱為決策圖。然后，需要注意的是，在確定聚類中心時，采用的是定性分析而不是定量分析，且包含了主觀因素，如圖3所示。不同的人可能得出不同的結果，聚類中心就很難分辨了。

圖3　決策圖中聚類中心難以確定例子

對于這些在決策圖中無法用肉眼判斷出聚類中心的情形(CBFSAFODP算法聚類中心個數的確定用“automatically”確實不太合適)，給出一種確定聚類中心個數的方法，即計算一個將ρ值和δ值綜合考慮的量：

γi=ρiδii∈IS

(6) 然而“若干個”到底是取多少個？本文算法首先把降序排列好的γ在坐標平面上畫出來，以下標為橫軸，γ為縱軸，如圖4所示。非聚類中心的γ值比較平滑，而從非聚類中心過渡到聚類中心時γ值有一個明顯的跳躍，這個跳躍用肉眼或數值檢測都可以判斷出來。

圖4　降序排列γ值示意圖

1.3CBFSAFODP算法步驟

Step1初始化及預處理：

Step1.1給定用于確定截斷距離dc的參數t∈(0,1)；

Step1.2計算距離dij，并令dij=dji,i

Step1.3確定截斷距離dc；

ni=0,i∈IS;

for i=1,2,…,N

{δqi=dmax;

for j=1,2,…,i-1

{

if(dist(xqi,xqi)<δqi)

{

δqi=dist(xqi,xqj);

nqi=qj;

}

}

}

Step3對非聚類中心數據點進行歸類：

for i=1,2,…,N

if(cqi=-1)cqi=cnqi

Step4若nc>1，則將每個cluster中的數據點進一步分為cluster core和cluster halo：

Step4.1初始化標記hi=0,i∈IS；

for i=1,2,…,N-1

{

for j=i+1,i+2,…,N

{

if(ci≠cj且dist(xi,xj)

{

}

}

}

Step4.3標識cluster halo：

for i=1,2,…,N

2　K-means算法

2.1K-means算法的思想

K-means算法[10]是以k為參數，把n個數據對象分為k個簇，每個簇內的數據對象具有較高的相似度，而不同簇之間具有相對較低的相似度。相似度是通過計算一個簇內數據對象的平均值得來的，相似度的定義是劃分關鍵，本文中是計算數據對象之間的賦權歐式距離[11]。K-means算法的基本思想是：首先在n個數據對象中隨機地選擇k個對象作為初始聚類中心;接著按最小距離原則來計算每個數據對象到聚類中心的距離，將其賦給最近的簇。然后，重新計算每個簇的平均值，計算收斂函數，直到各個聚類的中心不再變化，算法則終止。否則，重復上述過程。

2.2K-means算法的一般過程

輸入：簇的數目k以及n個數據對象的數據集。

輸出：E不變時滿足目標函數值最小的k個簇。

Step1從給出的n個數據對象中隨機選出k個對象作為初始聚類中心來執行；

Step2計算數據對象與各個簇的聚類中心的距離，將每個數據對象賦給與其距離最近的簇；

Step3重新計算每個新簇的均值，作為新的簇的聚類中心，nj表示第j個簇數據對象個數，Cj表示第j個簇；

(5)

(6)

Step5直到E不再發生明顯的變化時，算法終止；否則轉向Step2。

3　融合K-means算法與聚類的快速搜索和發現密度峰算法

3.1K-CBFSAFODP算法思想

針對K-means算法隨機選取k個點作為初始聚類中心進行迭代操作而導致聚類結果的不穩定，本文提出了融合K-means算法與聚類的快速搜索和發現密度峰算法。該算法首先需要對每個數據計算兩個量，即ρi和δi,通過這兩個量來刻畫聚類中心。 ρi和δi值越大，該點越是可能是聚類中心。再運用K-means算法進行迭代聚類，且引入信息熵計算賦權歐式距離來更準確地規范各對象的差異程度，從而更好地聚類。

3.2使用熵值法確定各數據對象間賦權歐氏距離

由于要對初始聚類中心以及k值做大量的預處理，來提高聚類的質量，本文引入了信息熵來度量各屬性權重，計算各數據對象之間的權重系數。熵是體系混亂程度的度量。一個屬性的變異程度越大，則整個系統越是有序的，且該對象屬性的信息熵會越小，它提供的信息量就會越大，權重也就會變得越大；反之亦然。

(1) 設數據集有m個對象、n維屬性：

本文引入信息熵，計算各數據對象的賦權歐氏距離，可以更加入微地分析各個對象的差異程度。

(2) 首先對數據對象屬性進行標準化處理，使不同量綱的數據可以進行比較：

(7)

其中，Mij為數據對象xi的第j維屬性值比重，xij為屬性值。

(3) 分別計算第j維屬性的熵值和權值：

熵值：

(8)

權值：

(9)

(4) 賦權歐氏距離的計算公式為：

(10)

在選擇賦權歐氏距離作為相似性度量后，各個對象之間的差異程度能夠準確地計算出來，從而可以提高聚類的準確度。

3.3K-CBFSAFODP算法描述

輸入：待聚類的n個數據對象的數據集。

輸出：滿足目標函數最小的k個簇。

Step1使用熵值法計算數據對象賦權歐式距離dij,并令dij=dji,i

Step5令γi=ρiδi， i∈IS， γ值越大，越有可能是聚類中心；

Step7計算數據對象與各個簇的聚類中心的距離，將每個數據對象賦給與其距離最近的簇；

Step8根據式(5)重新計算每個新簇的均值，作為新的簇的聚類中心；

Step9根據式(6)計算E值；

Step10直到E不再發生明顯的變化時，算法終止；否則轉向Step7。

4　實驗分析

為了驗證融合算法的效果，本文對CBFSAFODP算法 、K-means算法以及K-CBFSAFODP算法進行了對比實驗。實驗采用了Matlab R2013a開發環境，Intel(R) Core(TM)2 Duo CPU 2.20 GHz,6 GB 內存，在Windows 7操作系統上運行。

實驗使用了UCI機器學習數據庫中的Iris、Wine和自定義人工數據集Dataset作為實驗數據。對K-means算法、CBFSAFODP以及本文改進的算法K-CBFSAFODP在選取不同初始聚類中心運行100次后進行比較鑒定，發現融合的K-CBFSAFODP算法在聚類誤差平方和、迭代次數、聚類時間和聚類的準確率等方面有極大的優化提升。實驗的數據集概述情況如表1所示。

表1　實驗數據集的構成描述

為了說明初始中心選取的有效性，本文選取UCI 上Iris數據進行驗證。Iris數據集包含150條樣本記錄，分別取自3種不同的鳶尾花的花朵樣本，每一類各50條記錄，其中每一條記錄都含有4個屬性：sepal length、sepal width、petal width和petal length，共聚成3類。初始聚類中心選取對比如表2所示。

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

由表2可以看出，本文算法的Iris數據集初始化聚類中心與實際數據中心非常接近，表明該算法對Iris數據比較有效，同理對于Wine和dataset數據集也有一樣的效果。

由圖5可得知，聚類的每條屬性在聚類過程中作用是真實不同的，應加以區分對待。K-means算法恰恰忽略了數據對象屬性對聚類作用的差異度，使得聚類結果與本來聚類結果之間存在很大差異。

圖5　計算得到Iris數據集各屬性對應的權值

如表3所示，可以看出本文算法在誤差平方和以及迭代次數上明顯優于K-means算法。

表3　比較兩個算法在UCI數據集的誤差平方和以及迭代次數

關于算法聚類結果的評價，除了常用的聚類誤差平方和、聚類時間和聚類準確率評價方法之外，還可以采用F-measure指標、Rand指數和Jaccard系數對聚類結果進行比較分析。后三個評價指標都是在已知正確分類信息的前提下對聚類算法的聚類結果進行評價的有效指標。

F-measure采用信息檢索的精確率和召回率思想。數據所屬的類i可看作是集合Ni中等待查詢的項；由算法產生的簇Ck可看作是集合Nk中檢索到的項；Nik是簇Ck中類i的數量。類i和簇Ck的精確率和召回率分別是：

精確率:Precision(i,Ck)=Nik/Nk

召回率:Recall(i,Ck) = Nik/Ni

F-Measure是Precision和Recall的加權調和平均(α是參數):

當α=1時，就是最常見的F1，即：

F-measure可看成分類i的評判分值。對聚類結果來說，其總F-measure可由每個分類i的F-measure加權平均得到：

其中：|i|為分類i中所有對象的數目。

Rand指數和Jaccard系數評價指標的定義如下：設U和V分別是基于數據集的兩種劃分；其中U是已知正確劃分，而V是通過聚類算法得到的劃分，定義a、b、c、d四個參數。設a表示U和V都在同一類的樣本對數目；b表示在U中為同一類，而在V中卻不是同一類的樣本對數目；c表示在V中為同一類，而在U中卻不是同一類的樣本對數目；d表示U和V都不在同一類的樣本對數目。n(n-1)/2=a+b+c+d,其中，n為數據集中所有樣本數。令M=a+b+c+d，則M表示所有的樣本對。Rand指數和Jaccard系數的定義如下：

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

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

其中，R表示Rand指數；J表示Jaccard系數。

由上述定義可知，F-Measure是Precision和Recall的加權調和平均，最優劃分期望其值盡可能大；Rand指數表示聚類結果與原始數據樣本分布的一致性；Jaccard系數表示正確聚類的樣本對越多，聚類效果越好。

由圖6、圖7和圖8可知，F-measure、Rand指數和Jaccard系數的三個聚類有效性指標顯示，K-CBFSAFODP算法優于K-means算法和CBFSAFODP算法。圖9、圖10和圖11是對Iris、Wine和自定義數據集Dataset分別應用K-means、CBFSAFODP和K-CBFSAFODP聚類準確率對比圖。從圖中可以看出，K-CBFSAFODP算法的聚類準確率要明顯優于K-means算法和CBFSAFODP算法。且融合算法K-CBFSAFODP首先進行了一個優化初始聚類中心的過程，因此比原有算法更加穩定，能得到更準確的聚類中心，快速地到達收斂。總之，實驗結果表明，本文提出的K-CBFSAFODP具有穩定性強、準確率高、收斂速度快的優點。

圖6　聚類結果的F-measure指標　　圖7　聚類結果的Rand指數

圖8　聚類結果的Jaccard系數　　圖9　Iris數據集上的測試

圖10　Wine數據集上的測試　　圖11　dataset數據集上的測試

5　結　語

K-means算法初始聚類中心選取的隨機性所帶來的聚類結果的不穩定性，以及要求用戶事先指定K值，限制了許多實際應用。本文引入了信息熵以及快速搜索和查找聚類的密度峰，用信息熵對數據對象屬性進行賦權來計算對象間的距離，來規范數據的屬性，提高聚類的準確率；然后利用數據點的局部密度以及高于該點的所有局部密度中與該點距離的最小值，對數據集的初始中心進行預處理，來刻畫初始聚類中心。提出了融合CBFSAFODP算法和K-means算法的聚類算法K-CBFSAFODP。融合的算法給聚類中心以及聚類個數K值的選取提供了新的有效依據，從而擺脫了隨機選取聚類中心導致的聚類結果的不穩定性和用戶操作的難度，大大提高了聚類的質量和穩定性。

[1] Datta Souptik,Giannella Chris,Kargupta Hillol.Approximate Distributed K-Means Clustering over a Peer-to-Peer Network[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1372-1388.

[2] Zhou Tao,Lu Huiling.Clustering algorithm research advances on data mining[J].Computer Engineering and Applications,2012,48(12):100-111.

[3] Wang Jun,Wang Shitong,Deng Zhaohong.Survey on challenges in clustering analysis research[J].Control and Decision,2012,27(3):321-328.

[4] 於躍成,劉彩生,生佳根.分布式約束一致高斯混合模型[J].南京理工大學學報,2013,37(6):799-806.[5] 黃敏,何中市,邢欣來,等.一種新的K-means聚類中心選取算法[J].計算機工程與應用,2011,47(35):132-134.

[6] Fahim A M,Salem A M,Torkey F A,et al.An efficient enhanced k-means clustering algorithm[J].Journal of Zhejiang University SCIENCE A,2006,7(10):1626-1633.

[7] Rodriguez A,Liao A.Machine Learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[8] 陳磊磊.不同距離測度的K-Means文本聚類研究[J].軟件,2015,36(1):56-61.

[9] Qiu Baozhi,Wang Bo.Cluster boundary detection technology for categorical data[J].Journal of Computer Applications,2012,32(6):1654-1656.

[10] 吳夙慧,成穎,鄭彥寧,等.K-means算法研究綜述[J].現代圖書情報技術,2011(5):28-35.

[11] 高孝偉.熵權法在教學評優中的應用研究[J].中國地質教育,2008,17(4):100-104.

A CLUSTERING METHOD COMBINING K-MEANS AND FAST SEARCH ALGORITHM OF DENSITY PEAKS

Sheng Hua1Zhang Guizhu2

1(SchoolofIoTEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(KeyLaboratoryofAdvancedProcessControlforLightIndustry(MinistryofEducation),JiangnanUniversity,Wuxi214122,Jiangsu,China)

The initial clustering centre of K-means algorithm is selected randomly, different initial centre inputs will get different clustering results. Aiming at this problem of K-means algorithm, we proposed a clustering algorithm which combines K-means algorithm and clustering with the fast density peaks search and finding algorithm (K-CBFSAFODP). This algorithm has the following considerations: the class cluster centre is surrounded by neighbour points with lower local density, and has relatively larger distance to any point with higher density, this is used to depict the cluster centre; then the K-means algorithm is employed for iterative clustering, this makes up the defect that to randomly select K-means clustering centre leads to falling into local optima easily. Moreover, the algorithm introduces entropy method to calculate the distance, thereby realises the optimisation of clustering. It is demonstrated by the experiments on UCI datasets and artificial simulation dataset that this combination algorithm can get better clustering results, and the clusters is very stable as well; meanwhile it also has fast convergence speed. These confirm the feasibility of the combination algorithm.

ClusteringK-means algorithmCBFSAFODP algorithmInitial clustering centresDensityInformation entropy

2015-07-01。江蘇省自然科學基金項目(BK201401 65)。盛華，碩士生，主研領域：數據挖掘，大數據。張桂珠，副教授。

TP18

A

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