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

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

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

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

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

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

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

1 DPC算法介紹

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

(1)

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

數(shù)據(jù)點在截斷核下的局部密度定義為

(2)

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

(3)

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

θi=δiρi

(4)

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

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

2.1 流形距離度量

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

點表示數(shù)據(jù)集中數(shù)據(jù)點的分布

(5)

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

2.2 改進局部密度

在DPC算法中，局部密度的計算僅僅統(tǒng)計截斷距離內(nèi)數(shù)據(jù)點的個數(shù)。而截斷距離的選取考慮到數(shù)據(jù)集的全局距離分布，忽略了數(shù)據(jù)點的局部距離分布。

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

(6)

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

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

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

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

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

2.3 半監(jiān)督標簽傳播

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

ρj≥Rank(ρi)nP

(7)

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

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

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

2.4 算法流程

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

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

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

輸出聚類結果標簽。

步驟1根據(jù)近鄰點的個數(shù)k，構建連通圖。

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

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

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

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

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

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

步驟8剩下未聚類的數(shù)據(jù)點通過標簽傳播實現(xiàn)完全聚類。

步驟9輸出聚類結果。

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

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

3 實驗與分析

3.1 數(shù)據(jù)集與實驗環(huán)境

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

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

3.2 評價指標

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

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

(8)

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

(9)

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

調(diào)整互信息是結合互信息與信息熵所提出的，其定義為

(10)

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

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

(11)

式(11)中：TP為在U中為同一類且在V中為同一類別的數(shù)據(jù)點對數(shù);TN為在U中為同一類但在V中卻隸屬于不同類別的數(shù)據(jù)點對數(shù)；FP為在U中不在同一類但在V中為同一類別的數(shù)據(jù)點對數(shù)，F(xiàn)N為在U中不在同一類且在V中也不屬于同一類別的數(shù)據(jù)點對數(shù)。

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

(12)

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

(13)

準確率定義為

(14)

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

3.3 實驗結果分析

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

不同顏色表示不同的類簇

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

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

不同顏色表示不同的類簇

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

不同顏色表示不同的類簇

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

不同顏色表示不同的類簇

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

表2 人工數(shù)據(jù)集在各算法上的實驗數(shù)據(jù)

表3 高維數(shù)據(jù)集在各算法上的實驗數(shù)據(jù)

4 結論

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