融合流形距離與標簽傳播的改進密度峰值聚類

陳超泉，王佳明，謝曉蘭*

(1.廣西嵌入式技術與智能系統重點實驗室，桂林 541006；2.桂林理工大學信息科學與工程學院，桂林 541006)

聚類是一種將若干數據依據其本身的數據特性劃分為若干簇的算法，使得相似性較好的數據能夠聚集為同一類，相似性較差的數據聚集為另一類，使得不同類簇之間具有顯著差異。

在機器學習[1]、數據挖掘、生物醫療[2]和無監督學習[3]等領域中，聚類算法占據了重要的位置。聚類算法大致可以分為基于劃分的聚類、基于密度的聚類、層次聚類、基于圖的聚類等。基于劃分的聚類典型的算法有Queen[4]基于空間劃分的K-means聚類算法，該算法為使用歐氏距離的聚類算法，該算法易于實現，可解釋性較好。但是K-means算法對于離群點與噪聲點敏感，難以識別非凸形狀的簇，同時對簇的大小也不敏感。大量的學者在此基礎上做了改進的工作。宋仁旺等[5]將K-means算法與數據集的空間分布結合起來，能夠準確地發現聚類中心。

相比于K-means算法，基于密度的聚類DBSCAN(density-based algorithm for discovering clusters in large spatial databases with noise)算法[6]不需要提前設置簇的個數，可以適應各種形狀大小的簇，能夠脫敏于噪聲點。但是在處理高維數據上效果不好，同時對于超參數距離閾值、鄰域樣本數閾值對聚類結果影響很大。密度峰值算法(clustering by fast search and find of density peaks, DPC)由Rodriguez等[7]提出。該方法相較于其他種類的算法，超參數的設置較少，能夠快速地達到理想聚類效果。DPC算法也得到了許多的應用，如陸春光等[8]將DPC算法用于電力大數據的異常檢測中。DPC算法的核心思想是尋找局部密度高且相較于其他類簇中心的距離較遠的點作為類簇的中心點。通過計算每個數據點的局部密度以及每個數據點相較于密度比其大的最小距離，來實現二維決策圖的繪制。在決策圖中，局部密度較大且最小距離較大的數據點常常用來作為類簇的中心點。DPC算法通常使用歐氏距離[9]數據來進行數據點相似度的計算。此外，截斷距離δ的選取一定程度上對DPC算法最終的結果影響很大。

為了解決上述問題，諸多學者對DPC算法作了許多改進。Du等[10]提出一種基于KNN(K-nearest neighbor)改進的密度峰值聚類算法(DPC-KNN)，在進行局部密度的計算中加入了KNN，充分考慮了數據的鄰域分布特征。Xie等[11]提出了一種基于模糊加權K近鄰改進的DPC算法,該算法使用數據點在截斷距離內的距離之和作為該數據點的局部密度，數據點的局部密度融合了周圍臨近點的距離信息。Du等[12]對DPC算法中的距離度量由傳統的歐氏距離替換為測地線距離，在一定程度上能夠適應流形空間的數據。同時，測地線距離在高維數據下能夠保留數據點之間的全局距離信息。Sevedi等[13]將DPC算法與動態圖的標簽傳播結合起來，在歐式距離度量的基礎上實現動態圖標簽的傳播。該算法將數據的全局信息與數據點局部信息融合，一定程度上增強了模型的魯棒性。但是該算法采用歐氏距離度量，在大部分統計中，隨著數據維度的增加，數據點在其鄰域內樣本稀少，故歐氏距離對模型的作用也越小。

針對以上問題，現提出一種融合流形距離[14]與標簽傳播[15]的改進密度峰值聚類，通過計算流形數據的距離，實現算法截斷距離d與局部密度ρ的計算；將每個數據點截斷距離內的距離之和作為該數據點的局部密度；將每個數據點看作圖的頂點兩個數據點的測地線距離看作雙方連接邊的權重，通過構造圖進行動態圖的標簽傳播，充分融合數據的全局信息與數據點的局部信息，進而達到良好的聚類效果。

1 DPC算法介紹

密度峰值算法(DPC)基于兩點假設：①類簇中心點的密度相較于其周圍數據點的密度最大；②對于不同的類簇中心的距離總是相隔較遠。通過對每個數據點xi∈{x1,x2,…,xn}的距離值δ與局部密度ρ參數的分析，完成決策圖的繪制。每個數據點在高斯核下的局部密度參數定義為

(1)

式(1)中：dij為數據點xi與數據點xj之間的歐氏距離；d為截斷距離。通常情況下將形成的歐氏距離矩陣升序，并選取前1%～2%的距離值作為截斷距離d。

數據點在截斷核下的局部密度定義為

(2)

每個數據點與比其局部密度大的數據點之間的最小距離值δi為

(3)

式中:j：ρj>ρi為比數據點xi局部密度更大的數據點集合。在計算出每個數據點的局部密度ρi的前提下，找到比數據點xi局部密度更大的點，然后計算這些數據點中距離數據點xi的最小距離值δi。最后繪制決策圖來選擇類簇的中心點。該算法也可以自己手動選擇聚類中心點，通過計算決策值來選取數據局部密度大，且相較于密度比其大的距離足夠遠的點作為類簇的聚類中心。該算法計算決策值為

θi=δiρi

(4)

在確定類簇中心之后，對類簇中心點分配標簽。然后對未分配標簽的數據點進行標簽分配，其標簽分配為已經分配過標簽，距離最近，且密度比其大的數據點，完成聚類。

2 融合流形距離與標簽傳播的改進密度峰值聚類

2.1 流形距離度量

針對歐氏距離在處理復雜數據上的局限性，流形距離能夠精確度量數據點之間的距離。然而在DPC算法中，距離矩陣的計算全部采用歐氏距離進行距離度量。本文提出的算法采用流形距離進行 距離度量。首先根據算法輸入的近鄰點的個數k讓每個數據點與周圍k個數據點連接生成連通圖。圖1為iris數據集所生成的無向連通圖。圖1為無向連通圖。數據點距離最近的點之間的流形距離等于雙方的歐氏距離，而相距較遠的點的流形距離為連通圖中所經過數據點之間的歐氏距離總和。數據點xi與數據點xj之間的流形距離具體定義為

點表示數據集中數據點的分布

(5)

式(5)中：l為數據點xi到xj所需要的跳數；pij為數據點xi與xj數據點能到達的路徑集合；L(x,y)為兩點之間的歐氏距離；pk為路徑p中的包含的數據點。通過流形距離，本文算法能夠有效地融合數據集的全局信息與數據點的局部信息。

2.2 改進局部密度

在DPC算法中，局部密度的計算僅僅統計截斷距離內數據點的個數。而截斷距離的選取考慮到數據集的全局距離分布，忽略了數據點的局部距離分布。

針對以上問題，DPC-ML算法為了融合流形距離與截斷距離內數據點數量之間的關系，提高DPC算法在計算局部密度步驟時對局部距離的敏感性。對于數據集{x1,x2,…,xn}中的xi數據點，本文算法中的局部密度定義為

(6)

式(6)中：Rij為數據點xi與數據點xj之間的流形距離；r為選取的截斷距離。

為了能夠提高算法在不同類簇密度分布的適應性。本文所提出的改進局部密度首先計算數據點截斷距離內的個數，然后計算該數據點到截斷距離內的數據距離總和。由于數據點數量與截斷距離內的融合，其數據更加依賴于數據的局部性，從而提高了樣本類簇間的區分度。

圖2為Jain數據集分布圖，圖3為Jain數據集決策圖。由圖3可知，使用了流形距離與式(6)計算的局部密度所繪制的決策圖相較于DPC算法的決策圖，在選擇類簇中心點上更加有區分度。在Jain數據集上實現了決策圖的繪制。在相同的參數條件下，本文算法相較于DPC算法能夠有效地實現決策點的選擇。

橫、縱坐標的數字來表示數據集的數據分布；不同顏色表示數據集中各數據點的類別標簽

圖3 Jain數據集決策圖(k=2)

2.3 半監督標簽傳播

在最后的傳播標簽步驟中，本文算法在DPC算法中分配標簽步驟的基礎上融合標簽傳播。DPC算法首先將選取的中心點依次賦值標簽，然后將剩余數據點的標簽賦值為距離最近且局部密度比其大的數據點標簽。DPC算法中對于截斷距離的選擇是十分重要的，不同的數據集可能需要不同的截斷距離。對于需要先行聚類的數據點定義為

ρj≥Rank(ρi)nP

(7)

式(7)中：n為數據點的個數；P為選擇截斷距離時所使用的百分比；Rank(x)為對集合x進行降序排列。

首先使用DPC算法中選擇截斷距離所設置的百分比，用此值為局部密度高的部分數據點先行分配標簽，然后使用標簽傳播算法實現完全聚類。

在DPC算法的聚類任務中，選擇截斷距離時所設置的百分比一定程度上反映了數據點之間的距離信息。因為DPC算法是選擇比當前點密度高且距離最近的數據點進行聚類，所以本文算法在最后聚類階段使用截斷距離所設置的百分比能夠分散地對數據集密度高的部分進行先行聚類，為標簽傳播提供基礎。

2.4 算法流程

本文算法通過融合流形距離與標簽傳播算法完成聚類任務，克服歐氏距離的局限性，使用數據點之間的最短流形距離的計算精確度量兩點之間的最短距離。簇類中心的選擇與最終標簽的傳播都是基于同一個連通圖上，相較于K-means等算法，降低了聚類任務中選取中心點的隨機性。融合上述思想實現聚類算法的詳細流程如下。

算法融合流形距離與標簽傳播的改進密度峰值聚類算法。

輸入數據{x1,x2,…,xn}，近鄰點的個數k，截斷距離百分比P。

輸出聚類結果標簽。

步驟1根據近鄰點的個數k，構建連通圖。

步驟2通過連通圖，使用弗洛伊德算法計算兩點之間的最短路徑，形成流形距離矩陣。

步驟3通過截斷距離百分比P,選擇截斷距離r。

步驟4使用式(6)計算各數據點的局部密度ρi。

步驟5計算每個數據點與比其密度大的點的最小距離值δi。

步驟6繪制決策圖，選取類簇中心點。

步驟7使用截斷距離百分比P，選擇比當前點密度高且距離最近的部分數據點進行先行聚類。

步驟8剩下未聚類的數據點通過標簽傳播實現完全聚類。

步驟9輸出聚類結果。

本文算法相較于DPC算法在參數的設置上多了近鄰點的個數k，而且該參數在流形距離的計算與標簽傳播中發揮著作用。從理論上來說，當近鄰點的個數k太大為數據集中數據點的個數時，其數據點兩兩之間的流形距離值等于其兩點之間的歐氏距離值。而近鄰點的個數k太小時，數據集不能夠形成為連通圖，進而造成數據點兩兩之間不可達的現象。如圖4所示，隨著近鄰點數k的增長，當數據集剛成為連通圖時能夠取得最好結果。隨著圖的連通程度的加強，聚類結果趨向穩定。

圖4 鄰近點對聚類結果的影響

3 實驗與分析

3.1 數據集與實驗環境

通過人工數據集與真實數據集的實驗來證明本文算法的有效性，數據集詳細信息如表1所示。同時，本文算法與DBSCAN、DPC、K-means算法進行比較。平臺環境為Windows，編程環境為python3.6，運行內存為16 GB，CPU為AMD 3200 G。

表1 數據集

3.2 評價指標

通過對各算法進行調試，保證最好情況下的各算法聚類結果。分別使用4個人工數據集與3個高維數據集進行實驗驗證。同時使用調整互信息(adjusted mutual information,AMI)、調整蘭德系數(adjusted rand index,ARI)、Fowlkes-Mallows指數(FMI)、準確率(ACC)進行聚類結果綜合度量。

假設U為數據擬合結果集合，Ui為屬于集合U中第i類的集合，|U|為Ui的集合總數。V為數據集標簽的真實分布集合，Vj為屬于集合V中第j類的集合，|V|為Vi的集合總數。N(N>0)為數據集中數據點的個數。互信息(mutual information，MI)用來描述兩個數據分布之間的擬合程度。集合U的信息熵定義為

(8)

式(8)中：P(i)=|Ui|/N。集合V的信息熵同理可得。同時互信息(MI)的定義為

(9)

式(9)中：P(i,j)為|Ui∩Vj|/N。

調整互信息是結合互信息與信息熵所提出的，其定義為

(10)

式(10)中：E{MI(U,V)}為求互信息MI(U,V)的期望；H(U)為求集合U的信息熵。

蘭德系數(Rand index, RI)通常 也用來評估聚類模型的性能，其定義為

(11)

式(11)中：TP為在U中為同一類且在V中為同一類別的數據點對數;TN為在U中為同一類但在V中卻隸屬于不同類別的數據點對數；FP為在U中不在同一類但在V中為同一類別的數據點對數，FN為在U中不在同一類且在V中也不屬于同一類別的數據點對數。

調整蘭德系數的定義類似式(10)，如式(12)所示：

(12)

Fowlkes-Mallows指數定義為準確率和召回率的幾何平均值，計算公式為

(13)

準確率定義為

(14)

式(14)中：當Vk=Uk時δ(Vk,Uk)取值為1，其余為0。

3.3 實驗結果分析

由圖5可知，K-means算法與DBSCAN算法在Aggregation數據集上均不能夠很好地完成聚類。

不同顏色表示不同的類簇

DBSCAN算法由于自動識別簇機制，將兩個有連通的類簇識別為一個。DPC算法與本文算法能夠精準地識別密度中心，進而完成聚類。從圖5(e)和圖5(f)的決策圖可以看出本算法相較DPC算法在聚類中心點的選擇上更加具有區分度。

圖6為Spiral數據集上聚類結果。基于密度的聚類算法在該數據集上都取得了良好的效果。K-means算法在此數據集上的表現差強人意。DBSCAN算法將各個邊界點識別為噪聲點，降低了聚類精度。如圖6(e)和圖6(f)所示，從聚類結果所對應的決策圖上看，DPC-ML算法所實現的決策圖相較于DPC算法所實現的決策圖，類簇中心點的特征更加明顯。同時也證明了DPC-ML算法中改進局部密度的有效性。

不同顏色表示不同的類簇

使用三個高維數據集進行實驗，本文算法在WDBC數據集上的聚類效果與決策圖如圖7所示。DPC聚類結果與本文算法聚類結果相比，DPC-ML算法能夠更加準確地完成高維數據的聚類。其中DBSCAN算法的聚類結果將原本兩類的數據聚為三類，不能夠很好地完成聚類。K-means算法與DPC算法雖然能夠完成一部分數據集聚類，但是數據集中簇的邊界仍然不能被準確識別出來。

不同顏色表示不同的類簇

圖8為在數據集Wine上的聚類結果。由圖8看出在高維數據集上，本文算法具有一定的優越性。DPC聚類結果將原本是三類的數據聚為兩類。K-means算法與DBSCAN算法在Wine數據集上都展示了良好的性能。但是與DPC-ML算法相比，聚類精度還有待提高。

不同顏色表示不同的類簇

由表2可以看出，本文算法在各個高維數據集上都取得了不錯的效果。其綜合性能最優，能夠適應高維數據。人工數據集在各算法上的實驗數據如表3所示。本文算法在人工數據集上也取得了不錯的效果。其中K-means算法與DBSCAN算法在各項指標上的表現都沒有DPC算法與本文算法優越。

表2 人工數據集在各算法上的實驗數據

表3 高維數據集在各算法上的實驗數據

4 結論

在DPC算法的基礎上做了改進，提出了一種基于流形距離與標簽傳播的改進密度峰值聚類算法。將流形距離與標簽傳播融入密度峰值算法中，同時重新定義了局部密度。從多種數據集的實驗上看，本文提出的局部密度在決策圖上顯示有著更好的區分度。在人工數據集與高維數據集中的實驗表明，本文所提出的算法能夠順利適應高維數據，同時對各種形狀的人工數據集也有不錯的適應性能。本文研究雖然在參數的設置上多了一個K近鄰數，但是經過實驗表明，只需建立起數據集的連通圖便可取得理想的效果。