邱保志，程 欒

(鄭州大學(xué) 信息工程學(xué)院，鄭州 450001)

0 引言

聚類是將相似的數(shù)據(jù)對象聚集在一起，而相異的數(shù)據(jù)對象盡可能地分離[1]。聚類技術(shù)在數(shù)據(jù)挖掘、模式識(shí)別、圖像處理、信息檢索等領(lǐng)域有著廣泛的應(yīng)用，是數(shù)據(jù)分析的基礎(chǔ)。在現(xiàn)有的聚類算法中，基于聚類中心的聚類算法由于其應(yīng)用廣泛而備受人們的關(guān)注，例如K-means[2]、具有噪聲的基于密度的聚類方法(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)[3]、密度峰值聚類(Clustering by fast search and find of Density Peaks, DPC)算法[4]等，這些算法都是以選擇初始聚類中心作為聚類的起始點(diǎn)，通過迭代或擴(kuò)展進(jìn)行聚類。選擇聚類中心的準(zhǔn)確性對聚類的迭代效率、聚類個(gè)數(shù)的確定和聚類精度有著重要的影響，如何準(zhǔn)確地選擇聚類中心、提高聚類精度成為聚類技術(shù)研究的關(guān)鍵問題。

以K-means為代表的基于劃分的聚類首先初始化聚類中心，然后通過聚類中心的反復(fù)迭代的方式進(jìn)行聚類，這類算法由于初始聚類中心選擇的任意性，導(dǎo)致聚類結(jié)果精度不高；以DBSCAN為代表的基于密度聚類的算法是以任一個(gè)核心點(diǎn)作為聚類的起始點(diǎn)，將密度可達(dá)的對象集合看作一個(gè)聚類[5]，由于其中心點(diǎn)選擇的隨意性和密度定義的全局性，造成該類聚類算法不能對多密度數(shù)據(jù)集和高維數(shù)據(jù)集進(jìn)行有效的聚類；基于密度峰值的聚類算法DPC以局部密度峰值為聚類中心，將包圍密度峰值的低密度區(qū)域看成一個(gè)聚類[6-7]，雖然能準(zhǔn)確地確定聚類的中心，但在確定密度峰值時(shí)需人工選取相應(yīng)的參數(shù)，在沒有先驗(yàn)知識(shí)的情況下，很難確定聚類的中心[8-9]。為了解決DPC算法存在的問題，拉普拉斯中心峰聚類(Laplace centrality Peaks Clustering, LPC)算法[10]將數(shù)據(jù)集轉(zhuǎn)換為加權(quán)完全圖，通過計(jì)算節(jié)點(diǎn)拉普拉斯中心性評估每個(gè)節(jié)點(diǎn)在加權(quán)圖中的重要性，并計(jì)算一個(gè)節(jié)點(diǎn)到更高拉普拉斯中心性的節(jié)點(diǎn)的相對距離，將擁有較大拉普拉斯中心性且較大相對距離的對象確定為聚類中心，以此來進(jìn)行聚類，但這一過程需要建立決策圖人工選擇聚類中心。

針對上述問題，本文通過引入圖的拉普拉斯能量，綜合考量每個(gè)節(jié)點(diǎn)的拉普拉斯中心性和該節(jié)點(diǎn)到具有更高拉普拉斯中心性的節(jié)點(diǎn)的相對距離，將數(shù)據(jù)集映射到由數(shù)據(jù)對象的拉普拉斯中心性和該對象的相對距離組成的二維特征空間中；進(jìn)而構(gòu)造決策圖，依據(jù)正態(tài)分布的“3σ”準(zhǔn)則提取聚類中心，從而自動(dòng)確定聚類中心；最后將非聚類中心點(diǎn)指派到距離最近的數(shù)據(jù)對象所屬聚類中，完成整個(gè)數(shù)據(jù)集的聚類。

1 相關(guān)定義

設(shè)數(shù)據(jù)集D={x1,x2,…,xn}，其中xi=(xi1,xi2,…,xim),i=1,2,…,n，m為數(shù)據(jù)對象的維度。用wi, j表示數(shù)據(jù)對象xi和xj之間的歐幾里得距離，首先把數(shù)據(jù)集轉(zhuǎn)換為加權(quán)完全圖，數(shù)據(jù)集中每個(gè)數(shù)據(jù)對象作為圖G中的一個(gè)節(jié)點(diǎn)，數(shù)據(jù)對象xi和xj之間的歐幾里得距離作為圖G中節(jié)點(diǎn)xi和xj之間邊的權(quán)值。

定義1 相異度矩陣[10]。設(shè)加權(quán)完全圖G是由數(shù)據(jù)集D轉(zhuǎn)換得到的，則圖G的相異度矩陣記為W(G)，定義如下：

(1)

其中，wi, j為節(jié)點(diǎn)xi和xj之間的歐幾里得距離，對任意的1≤i，j≤n都有：wi, j≥0，wi, j=wj,i,wi,i=0。

Z(G)=diag(Z1,Z2,…,Zn)

(2)

定義3 拉普拉斯矩陣[10]。給定加權(quán)完全圖G，它的拉普拉斯矩陣定義為:L(G)=Z(G)-W(G)。其中：Z(G)為圖的和對角矩陣，W(G)為圖的相異度矩陣。

定義4 拉普拉斯能量[11]。對于給定數(shù)據(jù)集D轉(zhuǎn)換的加權(quán)完全圖G，圖G的拉普拉斯能量LEL(G)定義為其拉普拉斯矩陣的特征值的平方和，即：

(3)

其中,λ1,λ2,…,λn是圖G的拉普拉斯矩陣L(G)的特征值。

定義5 拉普拉斯中心性[11]。給定加權(quán)完全圖G，刪除節(jié)點(diǎn)xi及其所有相連的邊之后的圖記為圖Gi，給定xi∈G，節(jié)點(diǎn)xi的拉普拉斯中心性ci定義為：

ci=(LEL(G)-LEL(Gi))/LEL(G)

(4)

LEL(Gi)是刪除節(jié)點(diǎn)xi之后圖Gi的拉普拉斯能量。節(jié)點(diǎn)的重要性往往體現(xiàn)在該節(jié)點(diǎn)被移除之后對圖的拉普拉斯能量的影響，因此可以用圖中刪除某節(jié)點(diǎn)后拉普拉斯能量的相對下降來度量一個(gè)節(jié)點(diǎn)的重要性(中心性)，拉普拉斯中心性越高，則該節(jié)點(diǎn)越重要。

當(dāng)數(shù)據(jù)對象xi為聚類中心時(shí)，ci和δi具有較大的值，令γi=ci*δi，這時(shí)，γi具有較大的值。為了從數(shù)據(jù)對象中分離出聚類中心，采用式(5)對γi進(jìn)行放大[12]，加大聚類中心與其他數(shù)據(jù)對象的差別，從而便于識(shí)別真正的聚類中心。

(5)

定義7 正態(tài)分布[13]。若隨機(jī)變量X服從一個(gè)數(shù)學(xué)期望為μ、標(biāo)準(zhǔn)差為σ的概率分布，且其概率密度函數(shù)為:

則這個(gè)隨機(jī)變量X就稱為正態(tài)隨機(jī)變量，正態(tài)隨機(jī)變量服從的分布就稱為正態(tài)分布。

在正態(tài)分布中，隨機(jī)變量X落在(μ-3σ，μ+3σ)以外的概率僅為0.002 7，基本上可以把區(qū)間(μ-3σ，μ+3σ)看作是隨機(jī)變量X實(shí)際可能的取值區(qū)間，這稱之為正態(tài)分布的“3σ”準(zhǔn)則。

當(dāng)數(shù)據(jù)對象xi為聚類中心時(shí)，該對象具有較高的拉普拉斯中心性ci和較大的相對距離δi兩個(gè)特征。潛在聚類中心點(diǎn)所對應(yīng)的E值遠(yuǎn)遠(yuǎn)大于非聚類中心點(diǎn)所對應(yīng)的E值。由于聚類中心點(diǎn)擁有較大的E值，而非聚類中心點(diǎn)的E值較小這一特點(diǎn)，依據(jù)正態(tài)分布“3σ”準(zhǔn)則篩選出那些E值大于μ+3σ的數(shù)據(jù)對象，將其設(shè)為聚類中心。圖1是Sprial數(shù)據(jù)集所對應(yīng)的分布直方圖及其正態(tài)分布曲線。從圖1中可以看出，Sprial數(shù)據(jù)集中有3個(gè)數(shù)據(jù)對象的E值大于μ+3σ，這3個(gè)數(shù)據(jù)對象就是數(shù)據(jù)集Sprial的3個(gè)類中心。

圖1 數(shù)據(jù)集Sprial的分布直方圖和正態(tài)分布曲線

2 ALPC描述

基于拉普拉斯中心性和密度峰值的無參數(shù)聚類算法(Parameter-free Clustering Algorithm based on Laplace centrality and density peaks, ALPC)首先把數(shù)據(jù)集轉(zhuǎn)換為無向完全圖G，得到圖的拉普拉斯矩陣L(G)；然后根據(jù)刪除某個(gè)數(shù)據(jù)對象后所引起的拉普拉斯能量變化，來得到數(shù)據(jù)對象的拉普拉斯中心性ci，并計(jì)算得到該數(shù)據(jù)對象的相對距離δi，接著通過式(5)擴(kuò)大γ值之間的差別，通過正態(tài)分布，選取E值大于μ+3σ的數(shù)據(jù)對象為聚類中心,然后按照最近鄰分類完成對整個(gè)數(shù)據(jù)集的聚類。ALPC算法描述如算法1所示。

算法1 ALPC。

輸入 數(shù)據(jù)集D;

輸出 聚類結(jié)果。

步驟1 將數(shù)據(jù)集D轉(zhuǎn)換為帶權(quán)完全圖根據(jù)定義1～3計(jì)算W(G)、Z(G)和L(G)。

步驟2 根據(jù)式(3)、式(4)計(jì)算各數(shù)據(jù)對象的拉普拉斯中心性。

步驟3 提取數(shù)據(jù)集聚類中心：

a)根據(jù)定義6計(jì)算各數(shù)據(jù)對象的相對距離δi；

b)根據(jù)式(5)計(jì)算各數(shù)據(jù)對象的E值；

c)運(yùn)用正態(tài)分布的3σ準(zhǔn)則，將E值大于μ+3σ的數(shù)據(jù)對象作為聚類中心。

步驟4 按照最近鄰分類完成對整個(gè)數(shù)據(jù)集的聚類。

在ALPC中，首先需要將待聚類的數(shù)據(jù)集轉(zhuǎn)換為帶權(quán)的無向完全圖，圖中的每個(gè)節(jié)點(diǎn)代表數(shù)據(jù)集中每個(gè)對象，利用拉普拉斯中心性來度量對象的重要性。拉普拉斯中心性基本思想是：通過刪除某個(gè)節(jié)點(diǎn)后所引起的圖的拉普拉斯能量的相對下降來度量該節(jié)點(diǎn)的中心性。然后計(jì)算該對象到具有更高拉普拉斯中心性的對象的相對距離，在聚類中心選取時(shí)，ALPC不再手動(dòng)選取那些具有較大拉普拉斯中心性和較大相對距離的數(shù)據(jù)對象作為聚類中心，而是采用概率統(tǒng)計(jì)中正態(tài)分布理論選取聚類中心，避免了手動(dòng)選取聚類中心時(shí)因視覺誤差所帶來的聚類結(jié)果的不準(zhǔn)確問題。ALPC綜合考慮對象的拉普拉斯中心性和該對象到更高拉普拉斯中心性的對象的相對距離，通過式(5)加大潛在聚類中心與待聚類數(shù)據(jù)集中其他對象的差別，利用概率統(tǒng)計(jì)中的正態(tài)分布理論選取具有較大E值，即E值大于μ+3σ的數(shù)據(jù)對象為聚類中心,然后按照最近鄰分類原則將其余的點(diǎn)分配到相應(yīng)的聚類中心，從而完成聚類并輸出聚類結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析

該算法的實(shí)驗(yàn)環(huán)境為：CPU為AMD 3.4 GHz，4 GB內(nèi)存，操作系統(tǒng)為Windows 7(64 bit)，算法的編寫使用Matlab R2014a軟件。

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評價(jià)指標(biāo)

實(shí)驗(yàn)選用 10個(gè)數(shù)據(jù)集，其中 4個(gè)人工數(shù)據(jù)集分別用于驗(yàn)證ALPC識(shí)別橋接簇、螺旋形、球形簇和非球形簇的能力；6個(gè)真實(shí)數(shù)據(jù)集來源于 UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫，用于驗(yàn)證ALPC對高維數(shù)據(jù)處理的有效性。表1詳細(xì)描述了實(shí)驗(yàn)數(shù)據(jù)集的基本信息。

表1 實(shí)驗(yàn)數(shù)據(jù)集基本信息

實(shí)驗(yàn)的評價(jià)指標(biāo)采用準(zhǔn)確率(ACCuracy, ACC)[10]、調(diào)整蘭德系數(shù)(Adjusted Rand Index，ARI)[5]和歸一化互信息(Normalized Mutual Information, NMI)[5]度量ALPC聚類的有效性。準(zhǔn)確率衡量聚類結(jié)果與實(shí)際結(jié)果的符合程度，其取值范圍為[0,1],當(dāng)算法的聚類結(jié)果與真實(shí)情況完全一致時(shí)準(zhǔn)確率為1，兩者越不一致，準(zhǔn)確率越低；調(diào)整蘭德系數(shù)的計(jì)算需要待聚類數(shù)據(jù)集的真實(shí)分類結(jié)果，其取值范圍為[-1,1]，調(diào)整蘭德系數(shù)越高意味著算法的聚類結(jié)果與數(shù)據(jù)集的實(shí)際分類情況越吻合，從廣義的角度看，調(diào)整蘭德系數(shù)衡量的是算法聚類結(jié)果與數(shù)據(jù)集實(shí)際分類情況的吻合程度；歸一化互信息是衡量聚類結(jié)果與數(shù)據(jù)集實(shí)際分類情況的相近程度，同樣需要待聚類數(shù)據(jù)集的真實(shí)分類結(jié)果，歸一化互信息的取值范圍為[0,1]，值越大意味著聚類結(jié)果與真實(shí)情況越相近，聚類效果越好。

3.2 聚類結(jié)果分析

首先在二維數(shù)值屬性數(shù)據(jù)集上與DBSCAN、DPC和LPC算法進(jìn)行聚類有效性的比較，然后在高維數(shù)據(jù)集上與DBSCAN、DPC和LPC算法進(jìn)行聚類有效性的比較。

圖2依次是DBSCAN、DPC、LPC和ALPC在4k2_far、Aggregation、Spiral和Ring數(shù)據(jù)集上的聚類結(jié)果，不同的灰度值代表不同的聚類。

圖2(a)是DBSCAN算法的聚類結(jié)果，它在Aggregation和Ring數(shù)據(jù)集上的聚類結(jié)果不正確，說明DBSCAN算法不能識(shí)別橋接簇和非球形簇，這是因?yàn)镈BSCAN算法的半徑閾值和密度閾值定義的全局性，當(dāng)待聚類數(shù)據(jù)集的密度不均勻、聚類間距差很大時(shí)，參數(shù)選取困難，半徑閾值和密度閾值選取不合適會(huì)造成聚類結(jié)果的不準(zhǔn)確；圖2(b)是DPC算法在4個(gè)人工數(shù)據(jù)集上的聚類結(jié)果，它在Ring數(shù)據(jù)集上的聚類結(jié)果不正確，這是因?yàn)镈PC算法需要人工輸入截?cái)嗑嚯x和手動(dòng)選取聚類中心，截?cái)嗑嚯x定義的全局性和視覺誤差造成的聚類中心選取不準(zhǔn)確，就會(huì)影響聚類結(jié)果的準(zhǔn)確性；圖2(c)是LPC算法的聚類結(jié)果，它在4k2_far數(shù)據(jù)集上聚類結(jié)果不正確，這是因?yàn)長PC算法人為分析決策圖，手動(dòng)選取聚類中心時(shí)視覺誤差造成的聚類中心選取不準(zhǔn)確，使聚類結(jié)果不準(zhǔn)確；圖2(d)是算法ALPC的聚類結(jié)果，表明ALPC可以準(zhǔn)確識(shí)別出數(shù)據(jù)集中的球形簇、橋接簇、螺旋形和非球形簇。上述四個(gè)二維數(shù)據(jù)集上的聚類結(jié)果驗(yàn)證了ALPC的有效性。

表2給出了4種算法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從表2中可以看出：與其他三個(gè)算法相比，ALPC的ACC值有10項(xiàng)為最高，NMI值有7項(xiàng)為最高，ARI值有7項(xiàng)為最高;雖然ALPC在Iris、Seed和Sonar這三個(gè)數(shù)據(jù)集上的歸一化互信息和調(diào)整蘭德系數(shù)不是最高值，但與評價(jià)指標(biāo)最高值接近。

ALPC對于Spiral、Ring和4k2_far這三個(gè)數(shù)據(jù)集的執(zhí)行能力最好，其聚類結(jié)果完全正確；與LPC算法相比較，ALPC在不需要人為干預(yù)的情況下對于Spiral、Aggregation、Ring、Wine、Seed和Wdbc這六個(gè)數(shù)據(jù)集自動(dòng)劃分的效果與人為劃分效果一致，實(shí)現(xiàn)了自動(dòng)聚類的目標(biāo)；ALPC對4k2_far、Iris、Glass和Sonar這四個(gè)數(shù)據(jù)集自動(dòng)劃分的聚類結(jié)果的精度比LPC算法人為劃分的聚類結(jié)果的精度要高，說明ALPC在應(yīng)對一些數(shù)據(jù)集時(shí)，具有更優(yōu)秀的性能，能得到較好的聚類效果。綜上所述，ALPC對人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集均有良好的聚類結(jié)果。

3.3 時(shí)間復(fù)雜度分析

對于對象數(shù)量為n的數(shù)據(jù)集D:1)DPC算法的時(shí)間復(fù)雜度主要來自于距離矩陣、局部密度和相對距離的計(jì)算過程，其中計(jì)算距離矩陣和相對距離的時(shí)間復(fù)雜度為O(n2)，計(jì)算局部密度需要依次尋找與該對象相對距離小于截?cái)嗑嚯x的對象的時(shí)間復(fù)雜度最壞為O(n2)，所以DPC算法的時(shí)間復(fù)雜度為O(n2)。2)DBSCAN算法的時(shí)間復(fù)雜度為O(n2)；LPC算法的時(shí)間復(fù)雜度主要來自于距離矩陣、拉普拉斯中心性和相對距離的計(jì)算過程，其中計(jì)算距離矩陣和相對距離的時(shí)間復(fù)雜度為O(n2)，計(jì)算對象拉普拉斯中心性需要依次刪除該對象并計(jì)算拉普拉斯能量的相對下降，時(shí)間復(fù)雜度最壞為O(n3)，所以LPC算法的時(shí)間復(fù)雜度為O(n3)。3)ALPC與LPC算法類似，所以ALPC算法的時(shí)間復(fù)雜度同樣為O(n3)。

LPC算法不需要人工輸入?yún)?shù)，但仍然需要人工選取聚類中心，雖然ALPC和LPC算法的時(shí)間復(fù)雜度相同，但ALPC可以自動(dòng)選取聚類中心，避免了人工選取聚類中心的不準(zhǔn)確問題。

圖2 4種算法在人工數(shù)據(jù)集上聚類結(jié)果比較

數(shù)據(jù)集類別數(shù)據(jù)集名稱DBSCANACCNMIARIDPCACCNMIARILPCACCNMIARIALPCACCNMIARI人工合成真實(shí)4k2_far0.99000.95000.91001.00001.00001.00000.66750.66480.52021.00001.00001.0000Aggregation0.82740.86900.85390.94290.93580.92140.98730.97000.97400.98730.97000.9740Spiral 1.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.0000Ring0.68610.56560.32310.57550.67490.49621.00001.00001.00001.00001.00001.0000Iris0.66670.76120.56810.66670.65860.45310.65330.64090.52520.69330.72290.5609Wine0.53370.21000.01540.58430.28020.17940.64610.36330.33800.64610.36330.3380Seed0.39050.02830.00420.62060.75600.73400.74760.50320.46150.74760.50320.4615Glass0.38320.22390.10550.45790.24190.09240.35050.14340.05250.48600.29380.1552Sonar0.55770.04310.05690.45240.10560.01910.53850.00610.00110.56730.01810.0134Wdbc0.62740.00000.00000.61300.0090-0.0110.63270.01120.01090.63270.01120.0109

4 結(jié)語

本文應(yīng)用拉普拉斯理論和正態(tài)分布的“3σ”準(zhǔn)則，提出了一種無參數(shù)聚類算法，實(shí)現(xiàn)了聚類中心的自動(dòng)選擇和無參數(shù)聚類，解決了LPC算法人工選取聚類中心的不準(zhǔn)確性問題，為基于中心的聚類技術(shù)的聚類中心選取提供了理論基礎(chǔ)，提高了聚類精度。

[4] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(6191): 1492-1496.

[5] 邱保志,唐雅敏.快速識(shí)別密度骨架的聚類算法[J].計(jì)算機(jī)應(yīng)用,2017,37(12):3482-3486.(QIU B Z, TANG Y M. Efficient clustering algorithm for fast recognition of density backbone [J]. Journal of Computer Application, 2017, 37(12): 3482-3486.)

[6] 蔣禮青,張明新,鄭金龍,等.快速搜索與發(fā)現(xiàn)密度峰值聚類算法的優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用研究,2016,33(11):3251-3254.(JIANG L Q, ZHANG M X, ZHENG J L, et al. Optimization of clustering by fast search and find of density peaks [J]. Application Research of Computers, 2016, 33(11): 3251-3254.)

[7] 馬春來,單洪,馬濤.一種基于簇中心點(diǎn)自動(dòng)選擇策略的密度峰值聚類算法[J].計(jì)算機(jī)科學(xué),2016,43(7):255-258.(MA C L, SHAN H, MA T. Improved density peaks based clustering algorithm with strategy choosing cluster center automatically [J]. Computer Science, 2016, 43(7): 255-258.)

[8] BIE R, MEHMOOD R, RUAN S S, et al. Adaptive fuzzy clustering by fast search and find of density peaks [J]. Personal and Ubiquitous Computing, 2016, 20 (5): 785-793.

[9] XU J, WANG G, DEND W. DenPEHC: density peak based efficient hierarchical clustering [J]. Information Sciences, 2016, 373(12): 200-218.

[10] YANG X H, ZHU Q P, HUANG Y J, et al. Parameter-free Laplacian centrality peaks clustering [EB/OL]. [2017- 12- 05]. https://www.researchgate.net/publication/320602767_Parameter-free_Laplacian_centrality_peaks_clustering.

[11] QI X, FULLER E, WU Q, et al. Laplacian centrality: a new centrality measure for weighted networks [J]. Information Sciences, 2012, 194(5): 240-253.

[12] YE X, LI D, HE X. An algorithm for automatic recognition of cluster centers based on local density clustering [C]// Proceedings of the 2017 29th Chinese Control and Decision Conference. Piscataway, NJ: IEEE, 2017: 1347-1351.

[13] STEIN C M. Estimation of the mean of a multivariate normal distribution [J]. Annals of Statistics, 1981, 9(6): 1135-1151.