基于密度可達的密度峰值聚類算法

劉 美，王全民

(北京工業(yè)大學信息學部，北京 100020)

1 引言

2014年，Rodriguez等在Science上發(fā)表《Clustering by fast search and find of density peaks》，提出DPC[1]算法，為聚類的簇中心選擇提供了新思路。近年來，圍繞DPC算法展開的研究主要有兩個方面，一是簇中心選擇的優(yōu)化，二是剩余點分配策略的改進。

簇中心選擇優(yōu)化角度各不相同，馬春來[2]等提出簇中心權值概念，根據(jù)簇中心權值的變化趨勢搜索“拐點”，并確定各簇中心，減少人為操作的誤差；蔣禮青[3]等提出基于近鄰距離曲線和類合并優(yōu)化DPC(簡稱NM-CFSFDP)的聚類算法，用近鄰距離曲線變化情況自動確定密度閾值dc，以dc指導聚類中心選擇。Wang等[4]則通過非參數(shù)多元核估計來估計局部密度，通過最大化平均輪廓指數(shù)自動選擇聚類質心。王洋等[5]提出了基于基尼指數(shù)的自適應截斷距離和自動獲取聚類中心的方法。楊震[6]等提出一種基于信息熵的截斷距離自適應算法，實現(xiàn)了DPC算法截斷距離的自適應；然后根據(jù)排序圖中權值的斜率變化趨勢確定拐點，自動劃分出聚類中心與非聚類中心的界限，實現(xiàn)聚類中心的自動選擇。

在剩余點分配問題上，K近鄰及其優(yōu)化算法是目前的主流改進方向。謝娟英等[7]提出基于K近鄰的密度峰值聚類算法，算法利用樣本點的K近鄰信息定義樣本局部密度，發(fā)現(xiàn)聚類中心并進行剩余點分配。Du 等[8]在謝娟英的基礎上引入主成分分析(PCA)對高緯度數(shù)據(jù)的處理，使其適用于高緯度數(shù)據(jù)。Xie等[9]提出DPC分配策略的“多米諾效應”，并利用模糊加權K-近鄰技術(FKNN-DPC)來分配離群點問題，解決了誤差傳遞問題。但K近鄰算法聚類結果依賴于K值的選擇，湯鑫瑤等[10]提出基于自然最近鄰的密度峰值算法(NNN-DPC)，可以自動獲取每個樣本的緊鄰數(shù)，解決了k值敏感問題。Liu等[11]提出基于共享最近鄰的快速密度峰搜索聚類算法(SNN-DPC)，通過計算兩點間共享鄰居的個數(shù)，快速、準確地識別和分配屬于一個簇的點。此外，Pizzagalli[12]認為剩余點分配應該從全局出發(fā)，基于最短路徑來確定點的歸屬，以此提出TP-DPC算法。以虛假節(jié)點S為根節(jié)點，并將聚類中心連接到S，目的是找到最小生成樹，以確定最短路徑；胡恩祥等[13]在TP-DPC基礎上提出剪枝策略，進一步提升了算法的效率。

2 相關研究

2.1 DPC算法

DPC的主要思想是：集群中心應該被不超過其密度的數(shù)據(jù)點包圍，并且遠離比它密度更高的數(shù)據(jù)點。基于這個思想，DPC基于密度ρ和距離δ構造決策圖，并手動選擇距離ρ和密度δ相對較大的點作為聚類中心。

假設存在數(shù)據(jù)集S={xi}ni=1，n為S內數(shù)據(jù)的個數(shù)，定義S中兩點間距離為

(1)

其中m為數(shù)據(jù)維度，則第i個點的密度計算公式為

(3)

這里的dc人為定義，稱為截斷距離，通常是將所有樣本點的di，j從小到大排列，取其前1%～2%[14]。因此，ρi是指距離xi小于dc的數(shù)據(jù)點的數(shù)目。

對于密度最高的數(shù)據(jù)點，距離δ是數(shù)據(jù)點對之間所有距離的最大值。對于任何其它數(shù)據(jù)點，距離δ是從它到比它更密集的數(shù)據(jù)點的所有距離的最小值。數(shù)據(jù)點xi的距離可以在兩種情況下計算如下

(4)

為盡可能減少為人干預，論文[2]中引入簇中心權值γ，并根據(jù)簇中心權值變化趨勢確定各簇中心，其中γ定義為：

γi=δi·ρi

(5)

2.2 密度可達

圖1 紅色為核心點，黃色為邊屆點，藍色為噪聲點(來自Wiki)

定義1：核心對象：如果一個對象的ε鄰域至少包含最小數(shù)目MinPts個對象，則稱該對象為核心對象。

定義2：直接密度可達：給定一個對象集合D，如果p是在q的ε鄰域內，而q是一個核心對象，對象p從對象q出發(fā)是直接密度可達的。

定義3：密度可達的：如果存在一個對象鏈p1，p2，…，pn，p1=q，pn=p，對pi∈D，(1<=i<=n)，pi+1是從pi關于ε和MinPts直接密度可達的，則對象p是從對象q關于ε和MinPts密度可達的。

定義4：邊界點與噪聲：邊界點不是核心點，但落在某個核心點的鄰域內；噪聲既不是核心點也不是邊界點。

3 基于密度可達的密度峰值聚類

3.1 DPC算法缺陷

密度峰值聚類算法主要問題聚焦于聚類中心的選擇與剩余點如何分配的問題上。對于聚類中心的選擇，本文2.1節(jié)中使用γ來進行聚類中心的選擇，減少了人為的參與。剩余點分配問題，對于凸數(shù)據(jù)，DPC的分配策略能起到很好的效果，如圖2(a)所示，但對于非凸數(shù)據(jù)，如圖2(b)，有兩個數(shù)據(jù)中心A 與B，對于密度僅次于A和B的C點來說，它與A的歐式距離要小于B，根據(jù)式(4)，C點被錯誤的歸屬于A所在簇，而比C點密度低，又距離C的點D也會歸屬于A所在簇，由此導致分類錯誤。

圖2 DPC在不同數(shù)據(jù)集上聚類效果

3.2 基于密度可達的剩余點分配

針對剩余點分配問題，本文提出使用密度可達的分配策略。密度可達的分配策略以聚類中心pi為起點創(chuàng)建新簇Ci，依據(jù)2.2節(jié)中密度可達策略從p向四周擴展。先將P的ε鄰域中包含的對象全部加入到簇Ci，然后從Ci中尋找未被處理的對象q，如果q是核心對象(定義1)，則對q進一步擴展，如此反復，直到沒有新的點可以被添加到任何簇時該過程結束。擴展過程中的設置ε=dc，MinPts值參考文獻[15]為

(6)

n為ρi≠0的數(shù)量。

算法1：密度可達剩余點分配算法DT：

輸入：數(shù)據(jù)集X，距離矩陣D，ε=dc，MinPts，聚類中心P

輸出：所有生成的簇C

1) DO

2) 首先將X中所有對象標記為unvisited；

3) 從聚類中心P中選取一對象p，并創(chuàng)建簇C；

4) DO

5) 從C中取出一個unvisited對象q，并標記為visited；

6) IF q是核心對象

7) 從距離矩陣D中找出距離p小于ε的點

8) 將這些點加入C

9) END

10) UNTILL C中沒有被標記為unvisited的對象

11) UNTILL 沒有未被訪問的聚類中心。

此時會存在屬于多個簇的邊界點，成其為光暈點，如圖3(a)中綠色圈內紅點；也會存在在簇邊界較為分散的點(距離核心點大于dc)，如3(a)中其它紅點。這兩類點在本算法中都按照DPC的分配策略進行分配：即先將所有點密度的密度進行降序排序，再將這些點分配到距離最近，密度更高的點所屬的類中，分類結果如圖3(b)所示。

圖3 簇邊界點處理

算法2：基于密度可達的密度峰值算法：

輸入：數(shù)據(jù)集X

輸出：分類標志flag

1) 計算X中所有對象的距離，生成距離矩陣D

2) 根據(jù)D，計算各個對象密度ρ和距離δ

3) 根據(jù)式(5)，找到聚類中心P，并計算MinPts

4) 簇C=DT(X，D，ε=dc，MinPts，聚類中心P)

5) 新建分類標志行矩陣flag=zeros(1，length(X))

6) %處理異常邊界點

7) 將對象根據(jù)按密度ρ降序排列，索引為order

8) WHILE i=1：length(X)

9) xi=X(ordrho(i)，：)；

10) IF (xi屬于兩個及以上C) OR (xi不屬于任一簇)

11) 查找距離xi最近，密度更高的點A

12) 將xi歸屬于A所在簇

13) END

14) END

3.3 復雜度分析

時間復雜度：一、密度峰值聚類中心選擇：a.計算距離矩陣D，時間復雜度為O(N2)；b.計算γ時間復雜度O(N2)；二、密度可達剩余點分配，時間復雜度為O(m*N)，m為聚類中心數(shù)目，N為數(shù)據(jù)點個數(shù)。由于m是常數(shù)且通常較小，所以時間復雜度為O(N)；三、光暈點處理：O(N)。因此總的時間復雜度為O(N2)，與DPC算法相同。

空間復雜度：一、距離矩陣D存儲O(N2)；二、簇矩陣C復雜度O(m*N)≈O(N)。因此總的空間復雜度為O(N2)，與DPC算法相同。

4 實驗

4.1 實驗環(huán)境、數(shù)據(jù)集與評價指標

為驗證DTDPC在凸數(shù)據(jù)與非凸數(shù)據(jù)上都有較好的聚類性能，將DTDPC與CDP、DBSCAN、k-means等經典聚類算法在人工數(shù)據(jù)和真實數(shù)據(jù)集上進行比較，并使用聚類精度(Acc)[16]衡量聚類性能。其中Acc公式為

(8)

map(x)是一個映射函數(shù)，以真實標簽yi作為參考標簽，用來解決標簽不一致問題，其中zi為聚類結果標簽。

實驗環(huán)境為matlab2018 、Windows10；數(shù)據(jù)集見表1、2。此外，為避免其它因素影響，本實驗距離均使用歐氏距離。

表1 人工數(shù)據(jù)集

圖4 不同算法在人工數(shù)據(jù)集上的聚類效果

表2 真實數(shù)據(jù)集

4.2 實驗結果分析

4.2.1 人工數(shù)據(jù)實驗結果分析

為直觀表現(xiàn)聚類效果，實驗對聚類結果進行可視化展示。在圖4中分別為統(tǒng)一數(shù)據(jù)集在不同聚類方法下的聚類效果，其中每種顏色代表一類。

K-means算法，雖然預先提供了正確的k值，但由于隨機選擇聚類中心，導致其在凸數(shù)據(jù)集上(圖4(a))的表現(xiàn)并不穩(wěn)；此外，由于依據(jù)距離遠近進行剩余點分配，在非凸數(shù)據(jù)集上(圖4(b)(c)(d))聚類效果不理想。

與K-means算法相反，DBSCAN算法在非凸數(shù)據(jù)集上(圖4(c)(d))展現(xiàn)出優(yōu)越的性能，但如果兩簇間有相連的點(圖4(a))，或類邊緣點密度較核心點下降較大(圖4(b))，會將兩類合成一類，或將一類分為多個類的情況，且較依賴于參數(shù)調整。

DTDPC算法是從DPC和DBSCAN思想中而來，繼承了DPC在凸數(shù)據(jù)集中的優(yōu)秀表現(xiàn)(圖4(a))，又改進其在非凸數(shù)據(jù)集上的性能(圖4(c)(d))，又不會如圖4(b)DBSCAN中在邊界點較為分散的情況下造成多種聚類的情況。因此DTDPC聚類性能相比下較為完善。

4.2.2 真實數(shù)據(jù)實驗結果分析

本節(jié)選取5組真是數(shù)據(jù)，測試DTDPC在真是數(shù)據(jù)集中的表現(xiàn)，結果如表3所示。

表3 不同聚類算法在真實數(shù)據(jù)集中的表現(xiàn)

實驗分別將本文DTDPC算法和 K-menas算法以及DBSCAN、DPC算法在以上 4 個數(shù)據(jù)集上進行了聚類，可以看出，DTDPC算法整體的聚類效果較 K-menas、DBSCAN、DPC算法更好。在不同維度不同簇的數(shù)據(jù)集上表現(xiàn)出出色的穩(wěn)定性。

5 結論

針對DPC由于分配策略導致在非凸集上聚類效果不佳的問題，提出一種基于密度可達的優(yōu)化密度峰值算法DTDPC。實驗表明，該算法在凸數(shù)據(jù)與非凸數(shù)據(jù)集上均表現(xiàn)良好，能夠處理光暈點和簇邊緣擴散等問題。較K-means、DBSCAN、DPC聚類算法更加穩(wěn)定。但該算法中未明確區(qū)分擴散的邊界點與噪聲點，導致噪聲點被歸類于相近的簇。因此，區(qū)分噪聲點與擴散的邊界點將是下一步的研究工作。