基于密度可達(dá)的密度峰值聚類算法

劉 美，王全民

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

1 引言

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

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

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

2 相關(guān)研究

2.1 DPC算法

DPC的主要思想是：集群中心應(yīng)該被不超過(guò)其密度的數(shù)據(jù)點(diǎn)包圍，并且遠(yuǎn)離比它密度更高的數(shù)據(jù)點(diǎn)?；谶@個(gè)思想，DPC基于密度ρ和距離δ構(gòu)造決策圖，并手動(dòng)選擇距離ρ和密度δ相對(duì)較大的點(diǎn)作為聚類中心。

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

(1)

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

(3)

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

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

(4)

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

γi=δi·ρi

(5)

2.2 密度可達(dá)

圖1 紅色為核心點(diǎn)，黃色為邊屆點(diǎn)，藍(lán)色為噪聲點(diǎn)(來(lái)自Wiki)

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

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

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

定義4：邊界點(diǎn)與噪聲：邊界點(diǎn)不是核心點(diǎn)，但落在某個(gè)核心點(diǎn)的鄰域內(nèi)；噪聲既不是核心點(diǎn)也不是邊界點(diǎn)。

3 基于密度可達(dá)的密度峰值聚類

3.1 DPC算法缺陷

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

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

3.2 基于密度可達(dá)的剩余點(diǎn)分配

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

(6)

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

算法1：密度可達(dá)剩余點(diǎn)分配算法DT：

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

輸出：所有生成的簇C

1) DO

2) 首先將X中所有對(duì)象標(biāo)記為unvisited；

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

4) DO

5) 從C中取出一個(gè)unvisited對(duì)象q，并標(biāo)記為visited；

6) IF q是核心對(duì)象

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

8) 將這些點(diǎn)加入C

9) END

10) UNTILL C中沒(méi)有被標(biāo)記為unvisited的對(duì)象

11) UNTILL 沒(méi)有未被訪問(wèn)的聚類中心。

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

圖3 簇邊界點(diǎn)處理

算法2：基于密度可達(dá)的密度峰值算法：

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

輸出：分類標(biāo)志flag

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

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

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

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

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

6) %處理異常邊界點(diǎn)

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

8) WHILE i=1：length(X)

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

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

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

12) 將xi歸屬于A所在簇

13) END

14) END

3.3 復(fù)雜度分析

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

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

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境、數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

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

(8)

map(x)是一個(gè)映射函數(shù)，以真實(shí)標(biāo)簽yi作為參考標(biāo)簽，用來(lái)解決標(biāo)簽不一致問(wèn)題，其中zi為聚類結(jié)果標(biāo)簽。

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

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

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

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

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

4.2.1 人工數(shù)據(jù)實(shí)驗(yàn)結(jié)果分析

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

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

與K-means算法相反，DBSCAN算法在非凸數(shù)據(jù)集上(圖4(c)(d))展現(xiàn)出優(yōu)越的性能，但如果兩簇間有相連的點(diǎn)(圖4(a))，或類邊緣點(diǎn)密度較核心點(diǎn)下降較大(圖4(b))，會(huì)將兩類合成一類，或?qū)⒁活惙譃槎鄠€(gè)類的情況，且較依賴于參數(shù)調(diào)整。

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

4.2.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)結(jié)果分析

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

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

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

5 結(jié)論

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