物理學優(yōu)化的密度峰值聚類算法

賈 露，張德生，呂端端

西安理工大學 理學院，西安 710054

1 引言

2014 年，《Science》上發(fā)表了題為《Clustering by Fast Search and Find of Density Peaks》[1]的論文。首次提出了密度峰值聚類算法（DPC），與DBSCAN 算法[2]、AP算法[3]、K-Means算法[4]等經(jīng)典的聚類算法相比，該算法能夠發(fā)現(xiàn)任意形狀的類簇，不僅能夠自動確定類簇質(zhì)心，而且使剩余樣本點的分配更加快速高效。該算法已被成功地應用于多文檔文摘聚類[5]、場景圖像分類[6]、社交網(wǎng)絡中社交圈的發(fā)現(xiàn)[7]等諸多領域。但是該算法自身也存在著一定的問題：（1）在局部密度的計算過程中需要人為設置截斷距離，存在人為參與的隨機因素；（2）對于剩余樣本點采用“一步分配”策略，雖然該策略簡單、高效，但是會導致剩余樣本點的分配不夠精準，易引起“多米諾骨牌”效應。

針對DPC算法存在的不足之處，薛小娜等[8]提出了結合K近鄰改進的密度峰值聚類算法，該算法利用K近鄰的思想設計全局分配策略；王洋等[9]提出了自動確定類簇中心的密度峰值聚類算法，該算法基于基尼指數(shù)自適應的確定截斷距離及自動獲取類簇質(zhì)心；金輝等[10]提出了自然最近鄰優(yōu)化的密度峰值聚類算法，該算法采用自然最近鄰的思想優(yōu)化局部密度，并提出一種新的類簇間相似度來解決流形數(shù)據(jù)問題；Liu 等[11]提出了基于K近鄰聚類策略的自適應密度峰值聚類算法，該算法通過K近鄰的密度峰來計算截斷距離和局部密度，并自動選擇初始聚類中心的新方法，若聚類可達，則繼續(xù)進行聚類；Wang 等[12]提出了基于數(shù)據(jù)場理論的密度峰值聚類算法，該算法引入了信息熵的概念，借此來優(yōu)化密度峰值聚類算法中的截斷距離dc，避免了該參數(shù)根據(jù)經(jīng)驗來設定所導致的隨機性；謝娟英等[13]提出了K近鄰優(yōu)化的密度峰值聚類搜索算法（KNN-DPC），該算法通過引入K近鄰的思想，重新定義樣本的局部密度，采用兩步分配的策略對剩余樣本點進行分配，但是該算法對近鄰數(shù)k值的選取較為敏感；Xie等[4]又提出了模糊加權K近鄰優(yōu)化的密度峰值搜索聚類算法（FKNN-DPC），該方法針對KNN-DPC 中的兩步分配策略進行改進，采用模糊隸屬度來判斷樣本屬于哪一個類簇；蔣禮青等[14]提出了快速搜索與發(fā)現(xiàn)密度峰值聚類算法的優(yōu)化，該算法根據(jù)近鄰距離曲線來自動的確定截斷距離dc，利用衡量參數(shù)解決了類合并后無法撤銷的難題，實現(xiàn)了對多密度峰值數(shù)據(jù)的正確聚類。

上述幾種改進算法雖然都具有較好的聚類效果，但是并未實現(xiàn)數(shù)據(jù)自發(fā)的聚合與離散。本文在DPC算法的基礎上進行改進，提出了一種物理學優(yōu)化的密度峰值聚類算法W-DPC。

2 DPC算法

DPC算法設計的主要思想：類簇質(zhì)心的局部密度高于周圍鄰居的密度，而且與密度較高點的距離都比較大。該算法思想的實現(xiàn)主要運用了兩個概念：樣本的局部密度和樣本的距離（這兩個概念正好對應算法的兩個假設）。假設：（1）類簇質(zhì)心被低密度的鄰域所包圍；（2）類簇質(zhì)心與比它密度更大的數(shù)據(jù)點之間的距離更遠。在這里，假設S為待聚類的數(shù)據(jù)集。

對于樣本i，局部密度ρi的定義有兩種方式，第一種是：

其中：

dij代表樣本i和樣本j之間的距離，為截斷距離（需要事先人為確定）。

由于式（1）估計樣本的局部密度可能會受到統(tǒng)計誤差的影響，且該式適合于對離散的數(shù)值進行計算，故采用第二種，即式（3）估計連續(xù)值樣本的局部密度：

對于樣本i，其距離定義為：

觀察上式可以看出：如果樣本i的局部密度是最大的，那么該樣本的距離是該樣本到其余所有樣本之間的最大距離；否則，該樣本的距離是該樣本和它距離最近且密度高于它的樣本距離。也就是說，局部密度越大的樣本其距離越大，因此，DPC 算法將密度較大和距離較大的樣本選作類簇質(zhì)心。

DPC 算法提出了決策圖的概念和一步分配策略。決策圖是將樣本的密度ρ和距離δ分別作為x軸和y軸構成的一個二維空間，故決策圖右上角的點選作為類簇質(zhì)心。一步分配策略就是將剩余的樣本分配到與它距離最近且密度比它高的類簇中。

3 本文算法

3.1 定義描述

本文算法利用物理學中的萬有引力定律[15]和第一宇宙速度對DPC 算法進行改進，重新定義了算法的局部密度以及分配策略，現(xiàn)將本文相關概念定義如下。

定義1 樣本a的鄰域其中S表示數(shù)據(jù)集，表示樣本a和b之間的距離，r表示掃描半徑。

參數(shù)m、n表示數(shù)據(jù)集的行數(shù)與列數(shù)，max表示數(shù)據(jù)集的最大值，min表示數(shù)據(jù)集的最小值，k表示類簇中最少包含的樣本數(shù)目。

定義2 樣本a的質(zhì)量：

考慮到樣本a所處的局部情況，這里將樣本a的鄰域，其周圍鄰居的個數(shù)作為質(zhì)量。

定義3 樣本a的吸引力：

任何物體之間都存在著相互吸引力，將吸引力作為衡量樣本的局部密度，如果距離越小，則吸引力即局部密度越大；距離越大，局部密度越小，增大了樣本之間的密度差異，提高了樣本的質(zhì)量，易于識別高密度樣本點且有利于確定類簇質(zhì)心。

定義4 樣本a的第一宇宙速度：

其中Mc是類簇質(zhì)心c的質(zhì)量，Rac是樣本a到類簇質(zhì)心c之間的距離。對于聚類而言，如果將類簇的質(zhì)心比作地球，那么樣本就相當于其他星體。如果一個樣本屬于某個類簇，那么該樣本對于該類簇質(zhì)心的速度就比較大，從而，該樣本就越不容易脫離該類簇對其的吸引力，相反，如果一個樣本不屬于某個類簇，則樣本對于該類簇質(zhì)心的速度就比較小，很容易脫離類簇質(zhì)心對它的吸引。

3.2 算法步驟

本文算法主要分成六個步驟完成：

算法1 W-DPC算法

輸入：數(shù)據(jù)集S，類簇中最少包含的樣本數(shù)目k

輸出：聚類結果

1.對原始數(shù)據(jù)集進行標準化處理。

2.根據(jù)公式（8）計算樣本的局部密度，根據(jù)公式（4）和（5）計算樣本的距離。

3.根據(jù)上述計算的結果，以樣本的局部密度為x軸，樣本的距離為y軸構造決策圖。

4.選取決策圖右上角的點作為數(shù)據(jù)集的類簇質(zhì)心，選取點的個數(shù)作為數(shù)據(jù)集的類簇數(shù)目。

5.根據(jù)算法2對剩余必須屬于的數(shù)據(jù)點進行分配。

6.根據(jù)算法3對剩余可能屬于的數(shù)據(jù)點進行分配。

算法2 必須屬于數(shù)據(jù)點的分配

1.從類簇集合當中隨機選擇一個未被分配的樣本數(shù)據(jù)點a。

2.根據(jù)公式（9）計算a與每一個選定的類簇質(zhì)心之間的第一宇宙速度。

3.如果a與每一個類簇質(zhì)心計算的第一宇宙速度不相等，則將該樣本數(shù)據(jù)點歸屬于第一宇宙速度計算值最大的類簇；否則將該數(shù)據(jù)點歸屬于可能屬于的樣本數(shù)據(jù)點集。

4.重復上述的分配步驟，直到每一個未被分配的樣本數(shù)據(jù)點皆被訪問過。

算法3 可能屬于數(shù)據(jù)點的分配

1.將掃描半徑按照步長為0.1進行自增操作。

2.從可能屬于的樣本數(shù)據(jù)點集中隨機選取一個樣本數(shù)據(jù)點，執(zhí)行算法2的第2、3步。

3.重復算法3的第1、2步。

4.所有的樣本數(shù)據(jù)點全部分配，算法結束。

W-DPC算法的流程圖如圖1所示。

圖1 W-DPC算法

3.3 算法復雜度分析

假設數(shù)據(jù)集的規(guī)模為n，W-DPC 算法存儲每個樣本到類簇質(zhì)心的距離以及分配策略中的識別矩陣，但是增加的空間復雜度不超過，其中m代表類簇質(zhì)心集合且m通常較小，因此，W-DPC算法的空間復雜度與DPC算法空間復雜度的量級相同。

W-DPC 算法的時間復雜度主要來源于四部分：（1）計算樣本之間的距離，時間復雜度為Ο( )n2；（2）計算每一個樣本的局部密度Ο( )n2，萬有引力計算中使用的距離是前面已經(jīng)計算過的距離矩陣；（3）計算每一個樣本的δ距離，時間復雜度為Ο(n2)；（4）分配樣本：時間復雜度為其中k1代表必然屬于點的規(guī)模，k2代表可能屬于點的規(guī)模，所以總的時間復雜度為雖然W-DPC 算法的時間復雜度大于傳統(tǒng)的DPC 算法，但是算法在運行上進行很好地優(yōu)化，故數(shù)據(jù)集上的實際運行時間不像預期的那么大。

W-DPC 算法利用物理學公式重新定義局部密度，不僅到考慮樣本周圍的情況，而且有助于精準識別高密度樣本；將剩余樣本分為必須屬于點及可能屬于點兩種不同情況，針對不同的情況，采用不同的分配策略，能夠提高剩余樣本的分配精度，且實現(xiàn)數(shù)據(jù)自發(fā)的聚合與離散，更好地體現(xiàn)了兩種不同學科之間地交叉與融合。

4 實驗結果及其分析

對數(shù)據(jù)集進行預處理，消除缺失值和維數(shù)差異的影響，采用相同維度的所有有效值的平均值替換缺失值。對于數(shù)值范圍上的差異，使用公式（10）將所有數(shù)據(jù)線性地映射到[0,1] 范圍，提高計算效率。

為了驗證W-DPC 算法的有效性和可行性，將W-DPC算法分別與KNN-DPC算法、DPC算法、DBSCAN算法、AP 算法、K-Means 算法在人工合成的數(shù)據(jù)集Flame People、Spiral People 以及 UCI 上的真實數(shù)集進行實驗評估，在所有的實驗中，距離度量都使用歐氏距離。使用的數(shù)據(jù)集在表1進行了展示，包括數(shù)據(jù)集的名稱、規(guī)模、維度以及類別數(shù)。

表1 人工合成數(shù)據(jù)集以及UCI數(shù)據(jù)集

4.1 實驗設計

本文使用調(diào)整蘭德系數(shù)（ARI）、調(diào)整互信息（AMI）、FM指數(shù)（FMI）等[16-18]三個評價指標。

蘭德指數(shù)（Rand Index，RI）需要給定實際的類別信息C，假設C*是聚類所產(chǎn)生的結果，a表示在C和C*中都是同一個類別的元素對數(shù)，b表示在C和C*中都是不同類別的元素對數(shù)，那么RI為：

但是對于隨機結果，RI 并不能保證分數(shù)接近于零，故為了實現(xiàn)“在聚類結果隨機產(chǎn)生的情況下，指標應該接近零”，調(diào)整蘭德指數(shù)ARI被提出，ARI是具有更高的區(qū)分度：

父親什么時候回來的，我不知道。第二天我醒的時候，父親坐在床邊，問我昨晚的事，我只好如實說了。他對我講，不能把這事再告訴任何人，包括祖父。我說為啥啊?！叭绻麆e人知道了，咱家的糧食就不夠吃了，就要挨餓，懂嗎？”我沒有說話，堅定地點了點頭。

AMI是一種有用的信息度量，它是指兩個事件集合之間的相關性，類似于ARI，內(nèi)部使用的是信息熵：

利用基于互信息的方法來衡量聚類效果所需要實際類別的信息。AMI 的取值范圍是值越大意味著聚類的效果越好，也就是說數(shù)據(jù)之間分布的相似度越高。

FMI是成對精度與召回率的幾何均值：

假設通過聚類劃分的簇為C*，參考模型給出類簇的劃分結果為C。其中a表示在C*中屬于同一個類別且同時在C中屬于同一個類別的樣本對數(shù)量；b表示在C*中屬于同一個類別但是在C中屬于不同類別的樣本對數(shù)量；c表示的是在C*中屬于不同的類別但是在C中屬于同一個類別的樣本對數(shù)量。

4.2 實驗結果

針對表1給出的人工合成數(shù)據(jù)集，首先利用W-DPC算法與KNN-DPC 算法、DPC 算法、DBSCAN 算法、AP算法、K-Means 算法進行比較，圖2 給出了這六種算法在Flame People 數(shù)據(jù)集上聚類的效果圖。

圖2 六種算法在Flame數(shù)據(jù)集上的聚類效果圖

如表2 列出了三種評價指標的結果；如圖3給出了評價指標之間的比較。

表2 Flame數(shù)據(jù)集上的聚類結果比較

圖3 表2中的三種評價指標散點圖

為了進一步驗證W-DPC算法的性能，Spiral People數(shù)據(jù)集上聚類的效果圖以及評價指標如圖4所示。

圖4 六種算法在Spiral數(shù)據(jù)集上的聚類效果圖

從表 3 中可以看到，KNN-DPC 算法、DPC 算法、DBSCAN算法的AMI、ARI、FMI都達到了100%；圖4中這三種算法將該數(shù)據(jù)集分成正確的類簇數(shù)目、能夠準確識別質(zhì)心并且剩余數(shù)據(jù)點的分配也很精準，聚類效果較好；AP算法將該數(shù)據(jù)集分成多個類簇，識別出多個類簇中心，進而使得部分樣本點分配到錯誤的類簇中，影響最終的聚類效果；K-Means算法將數(shù)據(jù)集分成了正確的類簇數(shù)目，但是類簇質(zhì)心識別的差異較大，導致剩余樣本中本該屬于同一類簇的卻被錯誤的分配到多個類簇中，其AMI、ARI達到負數(shù)，超出這兩種評價指標的取值范圍。從圖4、表3、圖5 可以看出W-DPC 算法對Spiral數(shù)據(jù)集聚類效果更優(yōu)，AMI、ARI、FMI 都達到了100%，高于AP 算法70%左右，更高于K-Means 算法，W-DPC算法將Spiral數(shù)據(jù)集聚類成正確的類簇數(shù)目，精準識別質(zhì)心位置及分配剩余樣本點。

表3 Spiral數(shù)據(jù)集上聚類結果的比較

表4 W-DPC與其他算法在七個數(shù)據(jù)集上的聚類結果比較

圖5 表3中的三種評價指標散點圖

本文選取UCI上的七個真實數(shù)據(jù)集對W-DPC算法以及其他算法進行實驗，實驗結果如表4所示。

從表4中可以看出，W-DPC算法的聚類性能要明顯優(yōu)于其余的幾種聚類算法。

W-DPC算法幾乎對所有的數(shù)據(jù)集都具有更優(yōu)的聚類效果，對于類簇數(shù)目及其質(zhì)心的識別更加準確；對于FMI 以及互信息AMI，W-DPC 算法的這兩項指標均高于其余算法10%～20%，對于數(shù)據(jù)集中局部密度的計算更加高效，使得樣本之間的密度差異性更明顯，W-DPC算法所產(chǎn)生的聚類結果與原始數(shù)據(jù)集之間的相似度更高，整體上來看，W-DPC 算法的各項評價指標系數(shù)較高，且該算法性能較為穩(wěn)定。

從上述理論分析和實驗評估可以得出結論：與其他算法相比，W-DPC 算法的聚類表現(xiàn)最好，平均性能穩(wěn)定，所定義的局部密度使得樣本之間密度差異性增大，有利于識別高密度的樣本；兩步分配策略更有助于實現(xiàn)樣本自發(fā)的聚合與離散。

表5顯示表1所提供數(shù)據(jù)集平均的運行時間。為了降低結果對意外事件的敏感性，對于每個數(shù)據(jù)集，應用最佳參數(shù)并執(zhí)行相同的過程50次。由于只有W-DPC算法、KNN-DPC 算法和傳統(tǒng)的DPC 算法是在matlab2017中實現(xiàn)的，因而表格省略了其他算法的運行時間。

由表5 可知，W-DPC 算法的運行時間大約是DPC算法的7倍左右，但是根據(jù)表4可以看出W-DPC算法的聚類精度要遠遠高于DPC算法。

5 結束語

本文針對DPC 算法存在的問題，從局部密度和分配策略這兩個方面進行了改進：

（2）根據(jù)第一宇宙速度來改進分配策略，將所有的剩余樣本點根據(jù)必然從屬于和可能從屬于某個類簇進行劃分，避免了一步分配策略導致的容錯性等問題。