密度峰值自動檢測聚類算法*

吳 昊 周建濤 祁瑞東

（內蒙古大學計算機學院 呼和浩特 010021）

1 引言

聚類分析是數(shù)據(jù)挖掘［1］領域中的一種數(shù)據(jù)分析方法，它根據(jù)數(shù)據(jù)特征，利用相似性度量規(guī)則，將未被預先標記的數(shù)據(jù)對象相似的數(shù)據(jù)集歸到同一組中?，F(xiàn)在，聚類方法已經(jīng)成為一個重要的研究領域，在互聯(lián)網(wǎng)［2］、地質［3］和材料學［4］等多個領域都有廣泛的應用。為了解決經(jīng)典聚類算法［5~7］存在參數(shù)設置復雜、需要預先輸入分類數(shù)、無法識別任意形狀簇等局限性，2014年Alex與Alessandro在《Science》提出密度峰值聚類算法（CFSFDP）［8］，該算法不需要設置初始簇數(shù)量，只需設置一個參數(shù)且聚類結果對該參數(shù)的選擇并不敏感，聚類過程中可以自發(fā)地發(fā)掘數(shù)據(jù)集內部結構，并具有非常好的魯棒性。但密度峰值聚類算法還存在一個問題，初始簇中心的確定需要人工手動選擇。

為了彌補密度峰值聚類存在的缺陷，本文基于最小二乘法結合決策圖選點提出一種自動選擇聚類中心方法，并結合此方法提出自動聚類算法，實驗結果表明，該算法可有效地自動識別初始簇中心，并有較好的聚類效果。

2 研究現(xiàn)狀與基本知識

2.1 初始簇中心選擇

初始簇中心選擇的方法大致分為三類，結合其他聚類方法結果兩階段聚類、計算閾值對決策點劃分以及尋找區(qū)域對決策圖劃分。結合其他聚類方法兩階段聚類的方法通常要先運行可確定簇數(shù)的聚類算法，Sun［9］等使用min-max聚類結果指導密度峰值聚類初始簇的選擇，在一定程度上可以找到合適的簇，但時間成本相當高，Zhou［10］等則使用Canopy進行初始簇識別也存在以上問題。閾值計算方法與b-ayes信息準則相類似，迭代計算閾值進行參考簇中心的選擇，2019年Sun和Jiang［11］提出使用高斯分布異常點檢測思想迭代概率閾值對初始簇進行劃分，雖可以較有效地確定簇數(shù)，但在計算過程中引入了新的參數(shù)需要選擇，這淡化了密度峰值聚類算法的優(yōu)勢。尋找區(qū)域的方法參照S.Salavador［12］所述Gap檢驗，通過結合決策圖的圖像特征計算來找到下降劇烈和平緩之間的分界區(qū)域，如2017年Wang［13］等使用點組角度余弦最大值來界定區(qū)域。尋找區(qū)域的方法往往需要設置少量參數(shù)，更適用于對密度峰值聚類算法初始簇的選擇，但現(xiàn)有的區(qū)域尋找方法計算量較大。本文提出使用擬合直線的方法且對該方法進行優(yōu)化，并結合新的選點策略提出自動聚類算法，下一小節(jié)介紹密度峰值聚類算法的基礎知識。

2.2 密度峰值聚類算法

本節(jié)介紹密度峰值聚類算法中的一些定義、算法思想和具體算法過程，并分析算法過程中存在的問題。

算法思想基于一個觀察：每一個簇中的密度大的區(qū)域總被密度小的區(qū)域包圍。算法的聚類中心滿足局部密度較大且離比它局部密度大的點較遠。

密度峰值聚類算法首先需要選擇初始聚類中心，在簇中心的選擇過程中，設數(shù)據(jù)點i，需要計算局部密度ρi和到密度比自身高的點的距離δi，數(shù)據(jù)點i的局部密度的計算公式為

其中，dij為點i到點j的距離，dc為截斷距離，χ(x)在當x<0時χ(x)=1其他情況χ(x)=0，局部密度ρi也就等于點i在dc范圍內的點的數(shù)目。

局部密度較大且δi較大的點將被選為簇中心，δi的計算公式為

在當前計算點為密度最大點時δi=maxj(dij)。選擇初始聚類中心的具體步驟需要依照上述密度和距離組成的決策圖，通過在決策圖中選取離群較遠的點。決策圖是選擇聚類中心的關鍵，Alex給我們提供的決策圖由ρ和δ組成，他同時給出的手動選點方法是盡量選擇決策圖右上方區(qū)域中的離群點，也就是ρ和δ同時顯著大的點，但這些點可能僅僅是部分而不是全部的簇中心，如圖1。

圖1 Iris數(shù)據(jù)集手動選擇決策圖

圖中右上角兩個實心點是非常突出的更容易被人為視作僅有的兩個初始簇中心，但Iris數(shù)據(jù)集正確分類數(shù)應為3，可見出現(xiàn)了簇中心少選的情況，而這種情況在手動選擇簇中心時是很常見的。找到初始簇中心之后，其他點歸于最臨近且局部密度最大的簇。對于每個簇都需要一個邊界區(qū)域來對不同簇進行劃分，邊界區(qū)域（border region）為每個簇的劃分界限，每個簇的邊界區(qū)域由該簇中的點集組成，點集中成員點滿足距其他簇中點的距離在dc之內。

不屬于該簇且未被劃入邊界區(qū)域的點則為該簇的環(huán)（halo），環(huán)點則適合選為噪聲點。

根據(jù)上述算法思想，密度峰值聚類算法的關鍵步驟如下：

1）輸入數(shù)據(jù)集S的距離矩陣

2）使用式（1）計算每個點的局部密度ρ。

3）使用式（2）計算距離密度較大點的距離δ。

4）根據(jù)計算結果構造ρ-δ決策圖，選擇ρ和δ都明顯大于其他點的數(shù)據(jù)點作為初始簇中心。

5）將簇中心外的數(shù)據(jù)對象歸到距離較近且局部密度大于它的簇。

6）輸出數(shù)據(jù)對象的聚類結果。

3 自動聚類算法

本節(jié)將針對密度峰值聚類算法存在的手動選擇簇中心的問題，使用最小二乘法結合決策圖進行選點自動化。并且，為了提高運算速度，使自動選點更快速，同時使選點策略脫離經(jīng)驗化，使用了新的選點策略。以此又提出密度峰值自動聚類算法ADPCA（A-utomatic Density Peak Clustering Algorithm），在無需人為干預的情況下取得更好的聚類效果。

為了減小計算誤差同時便于實現(xiàn)自動選擇簇中心，本文在計算局部密度和決策圖的使用與上文介紹方法有所不同，局部密度計算使用了高斯核，相比式（1），高斯核計算數(shù)據(jù)點有相同局部密度的概率較小，從而有效避免沖突；決策圖方面使用γ-n決策圖。具體公式見式（3）。

其中di，j表示di和dj之間的距離，dc表示截斷距離。γ計算公式見式（4）。

在γ-n決策圖中，γ分布曲線特點總體呈單調遞減，且在下降過程中存在一個位置，該位置我們稱為中間位置，它將圖像分為左右兩部分，左半部分下降速度快點較為稀疏，右半部分點較為密集下降更平緩。我們想要求得的簇中心特點是局部密度ρi和δi都較大的點，即γ值較大點，也即是要求左半部分的所有點作為簇中心點，由于簇中心點相比于其他點會大很多，那么我們接下來的工作就要尋找中間位置從而找到中間位置左側曲線上的點作為簇中心，γ-n決策圖例如圖2所示。

圖2 γ-n決策圖在Aggregation數(shù)據(jù)集中使用

本文中我們選擇使用兩條直線來表示左右兩部分區(qū)域，并在兩直線交點處作為中間位置［11］。擬合直線時我們使用最小二乘法［14］，對于曲線左右兩部分分別使用最小二乘法尋找擬合直線，對于每條擬合直線，我們設直線通過計算最小化平方誤差和來解得直線，平方誤差和如式（5）。

要想求得式（5）的最小值，對式（5）中a和b分別求偏導數(shù)，讓它們分別等于零。推導后得出正規(guī)方程（6）和（7）。

求解得a和b的表達式（8）和（9）。

從而得出左右直線。

下面的工作我們需要通過式（11）計算每條直線的均方根誤差（RMSE）并通過式（12）計算結果求得全局均方根誤差，從而在全局均方根誤差最小處找到合適的分界點C。其中xl=[2 ，3，…，c]，xr=[c +1，c+2，…，m]。

我們設左直線為L右直線為R，以左直線L（右同理）為例的RMSE計算式（11）：

總的RMSE計算公式為式（12）：

我們要求的目標C為式（13）：

上述過程中由于分界點更容易偏向于左半部分分布，我們不使用所有點進行迭代，從而將有限的計算力集中于最可能出現(xiàn)分界點C的區(qū)域，因此我們從x=2開始向x軸正向選m-1個點。因為c是區(qū)分是否為簇中心的分界點，我們的選點策略根據(jù)這一點首先要計算最可能成為簇中心的點的個數(shù)，然后將求得的個數(shù)乘以倍數(shù)k以覆蓋潛在的分界點C，選點策略過程在算法計算ρi和γi時同時完成，選點策略主要步驟如下：

1）計算平均局部密度mp，和δ值的標準差sδ。

2）統(tǒng)計點集

{x|ρ(x)>mp，且δ(x)>1.5sδ}中的點的數(shù)量n。

3）當 數(shù) 據(jù) 集 大 小DT<1000時m=6n，當DT≥1000時m=10n。

策略中第一步與第二步意在找出近似簇中心的點的數(shù)量，而在第三步中對可能存在的分界點C進行覆蓋，且保證不選擇過多的點造成計算壓力，同時在實際應用過程中m應小于，N為數(shù)據(jù)集大小。最終的自動聚類算法關鍵步驟如下：

1）輸入數(shù)據(jù)集S的距離矩陣；

2）計算數(shù)據(jù)點i的ρi和γi通過式（3）、（4）；

3）通過γ值構造γ-n決策圖；

4）使用選點策略計算m，設RMSEC={}；

5）使用式（8）~（12）迭代計算每個選點處的RMSEC加入到RMSEC向量；

6）使用式（13）計算C的位置；

7）在γ-n決策圖中選擇[1 ，2，…，C]點作為初始簇中心；

8）分配非簇中心點到最近且ρ較大的簇中；

9）輸出簇k的點集a。

算法流程圖3所示。

圖3 ADPCA算法流程圖

4 實驗分析

本文實驗環(huán)境為，3.5GHz CPU，16GB內存，Windows10操作系統(tǒng)下，使用Matlab2020a完成。實驗選用6個UCI常用數(shù)據(jù)集來驗證自動密度峰值聚類算法對于聚類工作的有效性，數(shù)據(jù)集包括二維數(shù)據(jù)和多維數(shù)據(jù)，使實驗過程盡可能廣泛含蓋數(shù)據(jù)的各種分布形式。

具體數(shù)據(jù)集信息見表1其中數(shù)據(jù)集都有不同的分布特征。Aggregation數(shù)據(jù)集有7個類圓形的分布，其中兩個類圓形之間有連接部分；Iris是一種常用的多重變量分析的數(shù)據(jù)集，在統(tǒng)計學和機器學習領域都很常用的數(shù)據(jù)集，通過它既可測試算法的準確度，也可以檢驗算法識別噪聲的能力；R15是生成用以測試多個聚類數(shù)的數(shù)據(jù)集，它包含15個不同形狀的簇；Spiral數(shù)據(jù)集呈旋渦形狀分布，其中組成旋渦的每一條圓弧曲線為同一簇，數(shù)據(jù)集用以測試不規(guī)則曲線形簇是否能準確聚類；Ruspini數(shù)據(jù)集成四部分較分散分布，用以測試對不規(guī)則分布的數(shù)據(jù)集聚類效果；Sonar數(shù)據(jù)集用以測試在較高維度情況下的聚類效果。

表1 數(shù)據(jù)集信息

該算法只需設置一個參數(shù)截斷距離dc，聚類結果對該參數(shù)設置不敏感，此參數(shù)的選擇時使在每個數(shù)據(jù)點的截斷距離范圍內的鄰居點數(shù)應占數(shù)據(jù)點總數(shù)的2%~3%［8］，本文在實驗過程中將此值選擇范圍定在4%。ADPCA算法在計算距離矩陣、局部密度、較高密度距離時的時間復雜度為O(n2)，選點策略實施包含在上述計算中。類算法必在降序排γ值時的時間復雜度為O(n log(n))，而聚類時的時間復雜度為O(n)，綜上ADPCA算法的時間復雜度為O(n2)，而距離矩陣是每個聚須計算的一步，因此如果不考慮參數(shù)計算，ADPCA算法在時間復雜度僅為O(n log(n))［15］。

我們使用DBSCAN、K-Means、DPC、ADPCA算法并使用ARI［16］（調蘭德指數(shù)）對相同數(shù)據(jù)集聚類結果進行對比分析。

表2所示結果中，DBSCAN想要趨近期望結果，需要不斷調整兩個參數(shù)，可見該算法結果對參數(shù)設置的敏感性，如果提供的數(shù)據(jù)集預先未知期望簇數(shù)的情況下想要較為準確的聚類難度較大。K-Means算法需設置初始k值，從表中可以看出聚類效果相比其他三種算法較差，實際實驗過程中在識別任意形狀的簇時效果較差，如在Spiral旋渦型數(shù)據(jù)集中，在輸入k正確的情況下，存在將不同曲線的點劃分到同一簇中的情況。DPC在初始簇數(shù)選擇正確的情況下對任意形狀的數(shù)據(jù)聚類效果較好，在手動選擇初始簇時不可避免會出現(xiàn)多選或少選。ADPCA無需人為干預的情況下即可獲得較好的聚類結果，對參數(shù)的設置不敏感，參數(shù)設置都較為相似情況下也能取得期望的結果。ADPCA算法通過自動尋找初始簇中心進行有效聚類，我們使用UCI常用數(shù)據(jù)集測試該算法。圖4為ADPCA聚類結果，可見不同形狀的簇也可以有良好的聚類效果，從圖4（a）聚類結果中，可見ADPCA可準確識別任意形狀的簇；對于在圖4（b）聚類結果中存在的連通點干擾的兩個簇也有較好的聚類效果；圖4（c）中的螺旋形數(shù)據(jù)與圖4（e）的非規(guī)則數(shù)據(jù)集可準確聚類；圖4（d）為ADPCA面對多分類數(shù)時的聚類結果表現(xiàn)，綜上說明ADPCA可以自動準確地計算簇數(shù)，同時可以將每個點正確地分配到任意數(shù)據(jù)集形狀的類中。

表2 聚類算法對相同數(shù)據(jù)集聚類數(shù)對比

圖4 ADPCA在UCI常用數(shù)據(jù)集決策圖和聚類結果

從圖5中數(shù)據(jù)分布無特定形狀，密度較高的點分配在一個簇中，而黑色數(shù)據(jù)點被識別為噪聲點，可見ADPCA對任意形狀數(shù)據(jù)識別能力和對噪聲點的識別能力較強。

圖5 文獻［8］數(shù)據(jù)集聚類結果

5 結語

本文提出了一種自動選擇密度峰值聚類算法ADPCA，該算法在聚類過程無需人工參與，能夠在聚類前自動識別簇數(shù)，無需結合聚類結果分析簇數(shù)，同時我們對該算法聚類過程進行優(yōu)化，提出選點策略減少需要考慮的數(shù)據(jù)量來減少算法運行時間。為了證明ADPCA算法有效性，我們使用6種UCI數(shù)據(jù)集進行測試，并測試了在高位數(shù)據(jù)集下的性能表現(xiàn)，實驗結果看來算法的表現(xiàn)良好，在達到有效聚類的同時發(fā)現(xiàn)數(shù)據(jù)集的內部規(guī)律，并對噪聲點進行識別。

在未來的工作中我們想進一步改進dc選取方法，并解決可能出現(xiàn)的簇中心多選問題，使算法更具魯棒性。