丁松陽，田青云

河南財經(jīng)政法大學 計算機與信息工程學院，鄭州 450046

聚類分析是數(shù)據(jù)挖掘領域一個重要的研究方向，聚類分析無需先驗知識，根據(jù)數(shù)據(jù)之間的相似性將數(shù)據(jù)集劃分成合理類簇，使得相似度高的數(shù)據(jù)劃分為同一類簇，相似度較低的數(shù)據(jù)屬于不同的類簇[1-3]。聚類分析可以從大量數(shù)據(jù)中挖掘有用的信息，揭示了數(shù)據(jù)內(nèi)在的模式和規(guī)律，廣泛應用于信息檢索、圖像分割、模式分類等領域[4-6]。

聚類算法根據(jù)原理不同主要可分為劃分式聚類[7-8]、密度聚類[9]、層次聚類[10]和網(wǎng)格聚類[11]等，每種聚類算法都有其優(yōu)缺點。其中基于密度的聚類算法不需要指定類簇的個數(shù)，能夠識別任意形狀的類簇，是聚類算法中被廣泛使用的一種方法。DPC[12]聚類（clustering by fast search and find of density peaks）是由Rodriguez和Laio于2014年發(fā)表在Science上的一種新型聚類算法，該算法能夠發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點，根據(jù)決策圖選擇類簇數(shù)量，并具有高效的樣本點分配策略。然而，DPC算法仍存在以下局限：（1）時間復雜度O(n2)較高，不適用于大規(guī)模的聚類分析；（2）對所有樣本點采用同一種分配策略容易產(chǎn)生“多米諾骨牌效應”，當一個樣本被錯分，則會產(chǎn)生一系列的誤差傳播現(xiàn)象。

針對上述問題，已有許多學者對DPC算法進行優(yōu)化改進。Zhang等人[13]將DPC算法與Chameleon算法相結(jié)合，提出了E_CFSFDP算法，在DPC算法聚類的基礎上增加了類簇合并過程，有效解決了一個類簇中存在多個密度峰值的現(xiàn)象。該算法在多密度峰值的數(shù)據(jù)集上取得了更好的效果，但同時增加了模型的復雜度，時間開銷巨大。謝娟英等人結(jié)合k近鄰的思想分別提出了KNN-DPC[14]算法和FKNN-DPC[15]算法，利用k近鄰的加權(quán)距離代替樣本的局部密度，然后采用兩種不同的分配策略來完成樣本點的類簇分配。實驗表明該算法解決了樣本分配過程中的“多米諾骨牌”效應，提高了聚類精度。Chen等人[16]基于KNN搜索，應用cover tree對密度和距離計算進行加速，避免了全局范圍內(nèi)計算樣本點的密度和距離，將算法的時間復雜度降低至O(nlbn)。繼霞等人[17]運用相對距離將樣本映射到相對領域中，從而縮減了樣本點密度計算的范圍，然后通過剪枝策略來提高樣本點距離計算的效率。該方法在保證聚類質(zhì)量的同時提高了算法的時間性能。賈露等人[18]用物理學中的萬有引力替代參數(shù)截斷距離d c計算樣本的密度，并在樣本分配過程中進行優(yōu)化，然而，該算法的時間復雜度仍然較高。

本文綜合考量算法的時間性能和聚類質(zhì)量提出了基于Ball-Tree改進的密度峰值算法BT-DPC。算法首先通過構(gòu)建Ball-Tree加速了ρ和δ的計算，避免全局范圍內(nèi)計算各個樣本點的密度和距離；然后在樣本點分配階段采用統(tǒng)計學習策略對邊界點進行分配。在UCI數(shù)據(jù)集上的實驗結(jié)果表明：BT-DPC算法不僅在時間性能方面得到了提升，同時取得了更好的聚類效果。

1 DPC算法

DPC算法能夠?qū)⒍嗑S的數(shù)據(jù)映射到二維空間，從而識別特定的密度峰值作為類簇中心，類簇中心一般具有兩個基本特征：（1）局部密度高于周邊樣本的密度；（2）類簇中心之間的距離相對較遠。為了準確找到類簇中心，DPC需要計算樣本i的局部密度ρi和距離樣本i最近且密度比其大的樣本j之間的距離δi。局部密度計算如式（1）：

di,j表示樣本i和樣本j之間的距離，dc為截斷距離，當x<0時，χ(x)=1，否則χ(x)=0。對于式（1），當數(shù)據(jù)規(guī)模較小時，樣本密度的估計會受到影響，此時，可采用高斯核定義樣本的密度，其公式如下：

樣本i到局部密度比其大且距離最近的樣本之間的距離參數(shù)可定義為：

對于局部密度ρi最大的樣本i，其計算每個點的局部密度和距離后，由這兩個屬性為坐標畫出如圖1（a）所示的決策圖，然后人工選取都比較大的點作為類簇中心，同時也可以利用γ(γi=ρi×δi)曲線來選擇類簇中心。選取類簇中心之后，按照密度降序的方法將非類簇中心樣本點分配到密度比其大且距離最近的樣本點所在的類簇，聚類結(jié)果如圖1（b）所示。

圖1 決策圖和聚類結(jié)果Fig.1 Decision graph and clustering result

其算法描述如下：

2 BT-DPC算法

DPC算法主要可分為兩個階段：（1）密度及距離的計算，以便聚類中心的選擇；（2）樣本點的分配。本文將從這兩個階段分別優(yōu)化DPC算法，在第一階段，通過構(gòu)建Ball-Tree來加速密度及距離的計算，在第二階段，通過對數(shù)據(jù)分層來優(yōu)化樣本點的分配。

2.1 Ball-Tree

Ball-Tree[19]是一個輕量級的二叉樹，相較于kd-tree和cover-tree等，其具有在高維數(shù)據(jù)集上性能良好、操作簡單、查詢效率高等優(yōu)點。因此，Ball-Tree被廣泛應用于聚類[20]和分類[21]等問題。

在Ball-Tree結(jié)構(gòu)中，每一個節(jié)點都包含了數(shù)據(jù)集中的一部分數(shù)據(jù)點，用N.S表示。對于每一個內(nèi)部節(jié)點，又有左右兩個子節(jié)點，分別用N.lc和N.rc表示，且滿足：

當N為根節(jié)點時，N.S=S。

Ball-Tree中的每一個節(jié)點都表示了由一個超球體所包含的空間，其圓心N.c為節(jié)點中所有數(shù)據(jù)點的中點，而半徑N.r則表示圓心到數(shù)據(jù)點的最大距離，其定義如下：

在Ball-Tree的構(gòu)建過程中，首先選擇一個距離當前圓心最遠的觀測點i，然后選擇一個距離i最遠的觀測點j，根據(jù)就近原則，將圓中的數(shù)據(jù)劃分到最近的觀測點中形成兩個子節(jié)點，最后計算節(jié)點中的中心和半徑，當一個節(jié)點所包含的樣本點數(shù)量小于指定N0時，則不再對該節(jié)點劃分。其算法描述如下：

2.2 密度和距離的加速計算

DPC算法用截斷距離dc衡量樣本的密度，截斷距離d c需根據(jù)經(jīng)驗人工設置，使得平均每個樣本在一定范圍內(nèi)樣本數(shù)量占總樣本數(shù)量的1%～2%。然而，該方法在數(shù)據(jù)規(guī)模不統(tǒng)一的前提下魯棒性較差。近年來，不少學者利用knn代替截斷距離dc計算樣本密度[22]，knn中參數(shù)k值的設置更加簡單，然而，該方法在給定范圍內(nèi)，樣本的密度隨著knn中樣本的分布不同而產(chǎn)生變化，兩個樣本在第k距離相同的情況下，密度有可能不同。因此，本文選擇用第k距離的倒數(shù)定義樣本的密度，給定參數(shù)k值的前提下，樣本的第k距離越小，則其密度越大，不受knn中樣本分布的影響，其定義如下：

為了高效地計算出樣本點的局部密度，需要基于Ball-Tree查詢每一個樣本點的k近鄰。在給出Ball-Tree的查詢算法之前，這里首先給出一個查詢點在某個節(jié)點的上界。所謂的上界就是查詢點在節(jié)點中距離最近的觀測點之間的距離，在檢查兄弟節(jié)點時，如果查詢點距離兄弟節(jié)點的圓心的距離大于兄弟圓半徑加上上界值，則說明兄弟節(jié)點中不可能存在最近鄰點。

Ball-Tree查詢最近鄰采用深度優(yōu)先原則順序檢查節(jié)點，從根節(jié)點開始，直到找到包含查詢點的節(jié)點。在查詢過程中，算法始終維護一個降序列表Q來表示當前遇到的k個近鄰點，Q[0]表示當前k個近鄰中點的最大距離，搜索每一個節(jié)點時，通常執(zhí)行下列三種情況之一，然后返回一個最終的優(yōu)先隊列。

（1）如果查詢點q到當前節(jié)點N的距離大于Q中最遠的點，則返回Q。

（2）如果N是一個葉子節(jié)點，則掃描N中的每個數(shù)據(jù)點，然后更新隊列Q。

（3）如果N是一個內(nèi)部節(jié)點，遞歸調(diào)用N的兩個子節(jié)點算法，優(yōu)先搜索圓心更靠近查詢點q的子節(jié)點，更新列表Q。

算法描述如下：

對于每一個樣本i，都可以在Ball-Tree中找到由圓心N.c和半徑N.r定義的節(jié)點，由式（3）的定義可知：如果一個樣本i在其節(jié)點內(nèi)的密度不是最大的，則其最短距離一定在該節(jié)點內(nèi)，因此，計算樣本的相對距離時只需查找該節(jié)點內(nèi)密度比其大且距離最近的樣本即可。基于此推論，又可分為兩種情況：（1）若樣本i的密度在其鄰域內(nèi)是最大的，則該點的距離需要在密度高于該點的樣本中去查找；（2）若樣本i的密度在其鄰域內(nèi)不是最大的，只需在其鄰域中查找密度大且距離最近的樣本即可。其算法描述如下：

2.3 分配策略

為了解決DPC算法中的分配策略易產(chǎn)生誤差傳播現(xiàn)象，本文將文獻[14]中對邊界點的分配策略引用到BT-DPC中，邊界點的定義如下：

文獻[14]中，針對邊界點的分配策略主要可分為三個階段：（1）統(tǒng)計未分配樣本i的k近鄰中屬于類簇c(c=1,2,…,|cl|)的樣本點個數(shù)V c(i)，構(gòu)成一個1×|cl|的向量，對于所有未分配樣本會構(gòu)成一個nr×|cl|的識別矩陣M，其中，nr為未分配樣本規(guī)模，m(i,j)=V j(i),j=1,2,…,|cl|,i=1,2,…,nr。（2）從識別矩陣M中選擇一個最大的分量V c(i)，則把其對應的樣本i分配到相應的類簇中。（3）更新識別矩陣，對于剛分配的樣本i，若i的k近鄰N k(i)中有未分配樣本j，則Nk(j)=N k(j)+1，返回第二階段，直到識別矩陣中的最大值為0終止。

該方法實際上是一種統(tǒng)計分配策略，即統(tǒng)計每個未分配樣本的k近鄰中屬于各類簇的樣本點個數(shù)，然后將未分配樣本分配到其k近鄰所屬最多的類簇中。然而，階段（2）中剛分配的樣本會使得未分配樣本的k近鄰中已分配樣本點數(shù)發(fā)生變化，若使得N k(j)=N k(j)+1，顯然是不合理的，因為剛分配的樣本i未必是N k(i)中未分配樣本j的k近鄰N k(j)，所以在階段（3）中更新識別矩陣之前需要重新遍歷每一個未分配樣本，統(tǒng)計其k近鄰中屬于每一個類簇的點數(shù)。而這樣做無疑增加了算法的時間復雜度，假設未分配點數(shù)為||C，則其時間復雜度為O(||

C n)。為了高效而合理地更新識別矩陣，需統(tǒng)計每個未分配樣本的逆k近鄰信息，而該過程可以在階段（1）中統(tǒng)計每個未分配樣本點的k近鄰中完成，并未增加算法的時間復雜度，若某邊界樣本i被優(yōu)先分配，則只需從其逆k近鄰中循環(huán)更新識別矩陣即可，逆k近鄰定義如下：

2.4 BT-DPC算法分析

BT-DPC算法描述如下：

Ball-Tree是一個二叉樹，其中每個節(jié)點定義了一個多維的超球體，構(gòu)造過程中，采用遞歸函數(shù)將數(shù)據(jù)點不斷的劃分為兩個不相交的集合，其時間復雜度為O(nlbn)。算法3的k近鄰搜索算法采用深度優(yōu)先的原則檢查節(jié)點，其時間復雜度為O(nlbn)。算法4計算每個樣本點的距離δi，時間復雜度為O(n1lbn1+kn2)，其中n1為局部密度峰值點的數(shù)量，n2為非局部峰值點的數(shù)量，且滿足n1+n2=n，在文獻[16]中詳細地給出了如何查找密度峰值點的最小距離。算法5中9～14行，首先分配非邊界點，其時間復雜度為O(k|C|)；15～23行更新了識別矩陣，并完成了邊界點的逆k近鄰搜索，其時間復雜度為O(k|B|)；24～33行是對邊界點的分配，由于每一個邊界點的逆k近鄰點已經(jīng)搜索完成，所以其時間復雜度也為O(k1|B|)，k1為邊界點的逆k近鄰點數(shù)量(k1

3 實驗結(jié)果與分析

為了測試BT-DPC算法的聚類性能，本文從UCI數(shù)據(jù)庫中選取6個經(jīng)典的常用于測試聚類算法性能的真實數(shù)據(jù)集進行實驗，其基本信息如表1所示。對比算法為DPC算法、RP-DPC算法、FKNN-DPC算法、DBSCAN算法和K-means算法。本文算法采用PYTHON3.7實驗，實驗環(huán)境為Windows 10操作系統(tǒng)，Intel?coreTMi5 CPU，2.50 GHz。

表1 實驗數(shù)據(jù)集Table 1 Data sets used in experiments

3.1 評價指標

實驗結(jié)果評價選取3個常用于測試聚類結(jié)果好壞的指標：聚類精度（ACC）、調(diào)整互信息系數(shù)（AMI）和調(diào)整蘭德系數(shù)（ARI），三種指標的上界為1，其值越大則表明聚類結(jié)果越好。

聚類精度（ACC）表示被正確聚類的樣本點個數(shù)N1與樣本總數(shù)N的比值，其定義如式（11）所示：

調(diào)整互信息系數(shù)（AMI）常用來衡量兩組數(shù)據(jù)的吻合程度。假設U={U1,U2,…,U R}為數(shù)據(jù)集實際的類別標簽，V={V1,V2,…,Vc}為聚類結(jié)果，則U和V的熵分別為：

則U和V之間的互信息為：

設a表示在U和V中均屬于同一類簇的樣本點對數(shù)，b表示在U中屬于同一類簇但在V中不屬于同一類簇的樣本點對數(shù)，c表示在U中不屬于同一類簇但在V中屬于同一類簇的樣本點對數(shù)，d表示U和V中均不屬于同一類簇的樣本點對數(shù)，則其定義如式（16）所示：

3.2 聚類質(zhì)量分析

表2給出了6個算法在UCI數(shù)據(jù)集上的聚類結(jié)果，聚類結(jié)果取各種算法運行20次的平均值，同時表2中也給出了每種算法聚類結(jié)果對應的最優(yōu)參數(shù)Par。

表2 數(shù)據(jù)集上各算法的ACC、AMI和ARI評價指標比較Table 2 Comparison of clustering algorithms in terms of ACC，AMI and ARI on datasets

從表2可以看出本文提出的BT-DPC算法在六個UCI數(shù)據(jù)集上的聚類質(zhì)量要高于DPC算法，在Wine、Seeds和Ionosphere上取得了最好的聚類結(jié)果；在Iris和Waveform數(shù)據(jù)集上本文算法僅次于FKNN-DPC算法；在WDBC數(shù)據(jù)集上，本文算法僅僅高于DPC算法，因為本文對非邊界點的分配依然保留原文獻中的就近分配原則，導致了誤差傳播現(xiàn)象，而FKNN-DPC算法的第一種分配策略為有效解決“多米諾骨牌”效應，采用了一種類似于基于圖的廣度優(yōu)先搜索算法，因此在該數(shù)據(jù)集上取得了最好的聚類效果。本文算法對文獻[14]中第二種分配策略的更新識別矩陣進行優(yōu)化，所以在Wine、Seeds和Ionosphere上取得了最優(yōu)的聚類結(jié)果。

3.3 聚類效率分析

本節(jié)將詳細分析比較六種算法的聚類效率，表3給出了六種算法在6個UCI數(shù)據(jù)集上的運行時間。

表3 六種算法在數(shù)據(jù)集上的運行時間Table 3 Run time of six algorithms on several datasets s

DPC算法的時間復雜度主要來源于以下三個方面：（1）距離矩陣的計算，時間復雜度為O(n2)；（2）計算每個樣本點的密度ρi，時間復雜度為O(n2)；（3）計算每個樣本點的距離δi，時間復雜度也是O(n2)，所以DPC算法總的時間復雜度為O(n2)。FKNN-DPC算法相較于DPC算法，多了兩種樣本分配策略，雖然其時間復雜度仍然為O(n2)，但其運行時間要高于DPC算法。而本文BT-DPC算法的時間復雜度主要來源于Ball-Tree的構(gòu)建和k近鄰的查找，且受密度峰值點的影響，密度峰值點越多，則在查找過程中消耗的時間越多，而密度峰值點又受k值的影響，k值越小，密度峰值點越多。但BTDPC算法總的時間復雜度為O(nlbn)。

理論分析BT-DPC算法的時間復雜度低于DPC算法的時間復雜度，在表3中也得到了同樣的證實。從表3可以看出本文BT-DPC算法的運行時間是要低于DPC算法的，且隨著數(shù)據(jù)規(guī)模的增大，該算法的時間性能提升越高。FKNN-DPC算法在各數(shù)據(jù)集上的運行時間高于DPC，且隨著數(shù)據(jù)規(guī)模的增大，其與DPC算法運行時間的差距也在增大。

3.4 參數(shù)k對聚類結(jié)果的影響

本文通過γ(γi=ρi×δi)曲線來選擇聚類中心，γ值越高，則表示該點成為聚類中心的可能性越大，而非聚類中心的γ值較小且呈平滑趨勢，二者存在明顯的跳躍現(xiàn)象。參數(shù)k值的大小會影響聚類中心的選擇，進而影響聚類精度。本文選擇經(jīng)典的聚類數(shù)據(jù)集Iris和Wine來討論參數(shù)k值對聚類精度的影響和k值的選取方法。如圖2所示，對于Iris數(shù)據(jù)，當k值從3到9時，聚類精度從60%增加到了96%，并在該點達到了頂峰，隨著k值的繼續(xù)增加，聚類精度呈現(xiàn)下降趨勢。對于Wine數(shù)據(jù)，隨著k值的增加，聚類精度也出現(xiàn)了先增加后降低的趨勢。因此，對于參數(shù)k值的選擇，可以在一定范圍內(nèi)，逐漸增大k值，當聚類精度出現(xiàn)明顯下滑時，即可停止實驗。相較于DPC算法中的截斷聚類d c，BT-DPC算法中的參數(shù)k值更好設置。

圖2 k值對聚類結(jié)果的影響Fig.2 Influence of k value on ACC

4 結(jié)語

本文提出了一種基于Ball-Tree的密度峰值聚類算法BT-DPC，該算法通過構(gòu)建Ball-Tree縮小了樣本局部密度ρi和距離δi的計算范圍，減少了DPC算法全局范圍內(nèi)搜索ρi和δi的計算量。同時，為了解決樣本點在分配過程中產(chǎn)生的誤差傳播現(xiàn)象，給出了一種優(yōu)化的邊界點分配策略。UCI數(shù)據(jù)集上的實驗結(jié)果表明，本文提出的BT-DPC算法不僅能夠有效降低DPC算法的時間復雜度，而且提高了算法的聚類精度。然而，DPC算法及其改進算法聚類結(jié)果的好壞取決于類簇中心點的選擇，如何有效地選擇聚類中心是需要進一步研究的問題。