基于密度二分法的密度峰值聚類方法

許朝陽，林耀海，張 萍

1.莆田學院 信息工程學院，福建 莆田 351100

2.福建農林大學 計算機與信息學院，福州 350002

1 引言

近年，密度峰值聚類方法（Density Peaks Clustering，DPC）[1]得到了廣泛的研究和應用，例如，在電力消費行為的聚類[2]，文本聚類[3]，無監督的聲學單詞發現計算[4]，批處理建模和在線監測[5]，醫療數據[6]，城市出租車熱點區域發現[7]，異常值檢測[8]和超光譜段選擇[9]等領域。密度峰值聚類方法以它不需要迭代、不需要太多參數等優點，備受歡迎。

學者們也對密度峰值聚類方法本身做了一些改進，以適應應用領域中的新情況，包括在聚類中心的判斷，截斷距離dc的選擇，密度計算方法的修改等。如Ma等在文獻[10]中設定，并按照從大到小排列，取前m個最大值作為聚類中心，Mehmood等提出了一種模糊CFSFDP方法[11]，用于有效地自適應地選擇聚類中心；Wang和Xu[12]引入了一種基于熵的截斷距離dc的選擇方法；Wang等[13]使用多變量的核密度估計方法自動選擇截斷距離dc。Mehmood等[14]，基于熱方程，使用另一個非參數密度估計器進行密度估計；Yan等[15]提出了基于點與其第k個最近鄰點之間的距離（稱為半徑）來估計每個點的局部密度。Du等[16]在高維數據點情況下使用PCA降維，然后在降維后的空間中使用KNN計算每個點的密度。高詩瑩等[17]通過計算數據樣本中的密度比，以避免低密度的類在決策圖上被遺漏，從而提高聚類準確率。李建勛等[18]充分利用屬性數據提高聚類質量。

密度峰值聚類方法基于這樣的假設：聚類中心被鄰近地區密度較低的鄰居所圍繞，并且與具有更高局部密度的任何點具有相對較大的距離。但密度峰值聚類方法確實存在一些缺點。作為聚類中心的數據點密度的差異程度，是影響密度峰值聚類方法聚類效果的一個關鍵原因。包含兩個方面：不同類的數據點密度差異過大，同一類中多個密度聚類中心密度值差異過小。已有的方法，有的沒考慮到這些問題，有的只處理了一種情況，而本文方法能夠較好地兼顧兩種情況的處理。

在上述問題中，數據點的密度不均衡是個關鍵，因此，本文提出了基于數據點密度二分法的密度峰值聚類方法。首先，將聚類過程視作兩部分：聚類中心的確定、其他數據點歸并到相應聚類中心。相應的，在本文算法中將數據分為高密度點和低密度點。一方面，對高密度的點進行聚類，根據決策圖識別出聚類中心；另一方面，根據本文提出的分配策略，使高密度點和低密度點都歸并到合適的聚類中心，從而實現聚類。

2 相關研究與問題分析

2.1 基于k-近鄰與聚合策略的自適應密度峰聚類

基于k-近鄰與聚合策略的自適應密度峰聚類（ADPC-KNN）[19]所針對的問題是，密度峰值聚類方法所提出的dc的確定方案，難以適應眾多類型的待聚類數據；該文章指出，dc的確定需要考慮到每個數據點的k近鄰距離，并與所有數據點的k近鄰距離、k近鄰距離的標準差都正向相關。其具體的公式描述如下：

其中N是數據點的數量，是點i和k最近鄰居之間的距離，定義如下，=maxj∈KNNi(dij)，μk是其中定義的所有點均值：

文獻[19]提出了新的dc確定方案，然后基本沿用密度峰值聚類方法計算δi和ρi。為了克服由于同一個類中存在多個峰值點，而被劃分為多個類，該文獻還提出了數據歸并算法。它拓寬了聚類間的密度核心類和類之間的邊界（異常值）。在聚類中心的判斷上，它將δi大于平均值的點作為初始的聚類中心之后，利用密度可達作為條件判斷，將滿足該條件的合并為一個類。它的不足是，對于類與類之間距離較小但有明顯邊界的類，也常被誤判為同一類。同時，由于該歸并算法將所有密度大于密度均值的點都作為可能的密度中心，然后進行迭代歸并、判斷，因此，算法復雜度較高。

2.2 基于密度歸一化的密度峰值聚類

基于密度歸一化的密度峰值聚類（DNDPC）[20]所針對的問題是，當不同類的數據的密度差異過大時，低密度的聚類中心難以通過密度峰值聚類方法的決策圖識別出來。該文的解決思路是，用當前點的最近30個鄰居的密度均值進行密度歸一化后，代替當前點的密度值ρi，用ρ'i在決策圖中輔助判斷聚類中心點。其歸一化公式描述如下：

其中，ρi表示點i的密度，定義如公式（3）；Dinn表示當前點i的30個最近鄰。歸一化密度僅用于選擇聚類中心。其他非中心數據的處理，仍以原始密度的決策圖上的關系為基礎。這種歸一化密度的思路，使得低密度的中心點能有比原來密度峰值聚類方法更多的機會，從決策圖中被識別出來。但是，同一類數據點中存在多個密度峰值而被誤判的情況仍然是文獻[20]沒有解決的一個問題。

2.3 關鍵問題分析

當密度峰值聚類方法對同一批待聚類數據中各個類的密度差異過大，或者不同批次待聚類的數據密度差異過大，通過密度峰值聚類方法的決策圖難以得到聚類中心，或者同一個類中產生多個聚類中心。這是影響密度峰值聚類方法得出準確聚類結果的一種常見情況。

如果這個問題沒有得到有效處理，往往可能產生諸多的錯誤聚類。例如，密度較大的類可能被劃分為多個類，或密度較大的類與其他類合并，或同一個聚類中包含多個密度中心。如圖1（a），來自于Compound數據集，內圓和外圓應該屬于不同類，但是由于外圓具有多個高密度點，并且比內圓的密度高，導致內圓被錯誤歸類到外圓的類上如圖1（c）。如圖1（b），來自于Jain數據集，上面的圓弧和下面的圓弧也應該屬于不同類，但是由于密度不同，導致錯誤的聚類結果，如圖1（d）。

針對這種情況，學者們給出的方法[19-20]能夠某種程度上解決這個問題，但仍有所不足（如2.1、2.2節的分析）。本文基于這兩個工作給出的工作結果和分析角度，既要使dc根據數據的特征而作相應變化[19]，也要使得密度峰值聚類方法能夠兼顧到低密度數據在聚類過程中容易被忽視的情況[20]。

圖1 密度不均衡數據集的聚類情況

因此，本文將聚類過程視為兩個步驟：產生聚類中心、將數據點聚類到最為合適的聚類中心。相應的，求出所有數據點的密度平均值后，將數據點分為高密度數據點和低密度數據點。正因如此，本文所提方法稱為“基于數據點密度二分法的密度峰值聚類”。在聚類之前去除低密度的點。然后對高密度的點進行聚類，使用一維高斯離散點檢測，識別出聚類中心。分別對高密度點和低密度點提出了兩個新的分配策略。

除了將數據分為高密度、低密度以便得到更好的聚類結果以外，本文的另外一個創新點是，本文認為在使用密度峰值聚類方法得到聚類結果后，要有相應的歸并策略。如圖2所示，上圖被正確識別為兩類，下圖由于存在一條稀疏的數據帶，在實際應用中很可能需要被識別為同一類。而到達到這個效果，就需要對密度峰值聚類方法的識別結果進行歸并。

3 基于數據點密度二分法的密度峰值聚類方法

本文所提的基于數據點密度二分法的密度峰值聚類方法，包含以下內容：（1）基于k個最近鄰居提出了截止距離dc的定義及計算；（2）基于一維離散點檢測算法，能夠有效和正確地發現密度峰值（聚類中心）；（3）介紹了高密度點和低密度點的聚類分配新策略。這些新策略是連續應用的。

圖2 兩類數據需要歸并的情況

3.1 截斷距離和數據點二分法

為了使得dc能夠根據數據集的不同形態而作相應修改，本文所提方法中dc的計算，參考了文獻[19]。由于本文所提方法的dc主要用于對高密度數據點計算聚類中心，數據集更少，數據密度更高（相對于還未將數據分為高密度和低密度時的數據集），所以本文的dc在公式（1）的基礎上乘以一個系數a。經過多次實驗對比，系數a為0.25時效果最好。

然后在密度峰值聚類方法的框架下，利用公式（3）計算 ρi。

本文高密度和低密度的分界值為全體數據點的密度值的均值，計算公式如公式（5）：

然后，將點的密度值大于密度分界值ρˉ的點為高密度點，點密度值小于密度分界值ρˉ的點為低密度點。

3.2 聚類中心的計算

先對高密度數據點進行處理，計算出它們的聚類中心。

密度峰值聚類方法本質是一個二維度量的聚類算法，除了計算每個點的密度峰值之外，還需要計算每個點的距離，距離的定義如下：

根據密度和距離的值，計算γi的值

DPC算法的提出者[1]給出的選擇聚類密度中心的方法是，通過人機交互的方式；也有眾多學者對如何選擇合適的聚類中心給出了自己的方案[10-11]，由于這個不是本文的研究重心，這里選擇的方案是在正態分布的假設下，如果i對應γi的值大于所有數據點的γ方差的3倍，那么i就可以被認為是一個聚類中心點[21]。聚類中心點構成一個集合，用C表示。

3.3 數據點分配策略

本文所謂的分配策略是指，在確定完聚類中心點以后，將每個點與最合適它的聚類中心點聯系起來。從而，實現最終的聚類過程。

數據點的分配策略有兩種，分別適用于高密度點和低密度點。

總體上來說，對高密度數據點的分配策略仍用原密度峰值聚類方法算法的方式。根據高密度點得到的決策圖，會求出一系列的聚類中心點。整個數據集的聚類中心，也將在這一系列聚類中心中產生。為了后續將其他非聚類中心點歸并中相應的聚類中心上，將上述這一系列聚類中心進行編號。對于密度最高的點，設置分配編號值為0；從密度第二大的點開始，設置分配編號值為密度比它大并且距離最小的點的編號。該分配策略優先考慮密度比較大的點，而后再尋找距離小的點。

與高密度點的分配策略不同，對于低密度點的分配策略需要同時考慮密度和距離兩個因素。所以，定義了歸屬概率，用來表示，如公式（9）。低密度點i的分配策略是，分配到歸屬概率比i大的相鄰點。

其中wij定義為代表點i和 j之間的相似度wij，這意味著點i和 j之間的距離越小，它們越相似。并將它們歸一化。

除此以外，還作了密度中心合并策略，以避免同一個類中，由于存在多個峰值，而被錯誤劃分。首先，定義了兩個點的dc可達，即這兩個點在所有的高密度點間存在一條路徑，該路徑上的點的兩兩之間的距離都小于dc。然后，在所有的高密度聚類中心點兩兩之間計算是否dc可達，如果可達則合并。

如圖3，針對高密度點，如圖3（b）中藍色的點，對高密度點進行聚類，如圖3（c），可以聚成4類，分別對這4類的中心點如圖3（d），中心點合并后的效果如圖3（e），最后低密度點聚類，如圖3（f）。

3.4 算法流程

下面從4個方面來描述本文所提方法：算法主體、密度中心計算、數據點分配、密度中心合并。

算法1給出了本文算法的整體流程。

算法1算法主體

輸入：待聚類數據集。

輸出：每個數據點的聚類結果。

1.根據公式（1）計算截止距離dc。

2.根據公式（5）計算高低密度分界值。

3.調用算法2，對高密度點進行密度中心計算。

4.調用算法3，實現聚類中心合并。

5.調用算法4，實現數據點的分配。

算法2，是根據3.2節的分析而實現，屬于密度二分法中的第一個關鍵步驟。

算法2密度中心計算

輸入：所有高密度數據點。

輸出：聚類中心點的編號。

1.使用公式（3），重新計算高密度點的ρi。

2.使用公式（6），計算 δi。

3.使用公式（8），計算聚類中心點。

算法3，可以有效避免，同一個類中，由于存在多個密度峰值點，而被誤判為多個類。

算法3聚類中心合并

輸入：所有聚類中心點的編號。

輸出：新的聚類中心。

1.計算聚類中心點兩兩之間，是否dc可達。

2.如果兩個點之間dc可達，把兩者中密度較小點從集合C中刪除。

算法4，是根據3.3節的分析而實現。

算法4數據點分配

輸入：所有數據點和聚類中心。

圖3 高密度點和低密度點計算示意圖

輸出：所有點的歸類。

1.對于高密度點使用與原密度峰值聚類方法算法同樣的策略。

2.對于低密度點做如下操作

2.1首先通過以下公式定義點i和 j之間的相似度wij。

2.2定義類歸屬的概率，點i到點c的概率。

2.3對進行排序升序排序，點i歸屬到比它大一些的那個點 j。

3.5 算法復雜度分析

本文所提算法主要有4個部分組成：算法1中的dc的計算，算法2中的密度和距離的計算，算法3中的dc可達性計算，算法4中的類歸屬概率的排序。下面就從這4部分對算法的時間復雜度進行分析。

假設樣本數為N，需要計算所有點對之間的截止距離dc，計算復雜度為O(N2)。

接下來算法的其余3部分的計算復雜度從最好情況、最壞情況、平均情況這3類進行分析。

在最好的情況下，高密度點只有m個，其中m?N,則計算密度和距離的復雜度為O(m2)，且O(m2)?O(N2)。每個聚類中心搜索路徑的計算復雜度為O(m2),dc可達性計算的計算復雜度為其中mc為聚類中心的數目，類歸屬概率的排序的計算復雜度為O( )NlogN 。通過計算，本文所提算法整體上計算復雜度為O(N2)。

最壞的情況下，高密度點有N-1，則密度和距離的計算復雜度為O((N-1)2)；對于每個聚類中心搜索路徑的計算復雜度為O((N-2)2)，dc可達性計算復雜度由于不存在低密度點，因此沒有必要對算法4中的類歸屬概率進行排序。所以整體上計算復雜度為O(mcN2)。

平均情況下，高密度點有mh,則低密度點有N-mh,密度和距離的計算復雜度為O((mh)2)；對于每個聚類中心搜索路徑的計算復雜度為O((mh-1)2)，dc可達性的計算復雜度為類歸屬概率的排序計算復雜度為由數學歸納法可證明，算法整體計算復雜度為O(N2logN)。

通過分析，可以看出，在所有類間距足夠大且每類高密度點只有一個的情況下，算法時間復雜度將達到最優；在類與類之間邊界交叉較多且類中包含多個高密度點的情況下，成為最壞時間復雜度。這兩種情況都屬于比較少見的情況。大部分情況下，趨近于平均時間復雜度O(N2logN)。

4 實驗與分析

本章在合成的和真實的數據集上完成了一系列實驗，將基于數據點密度二分法的密度峰值聚類方法（以下簡稱 DD-DPC）與 DPC[1]、ADPC-KNN[17]、DNDPC[18]等算法作了分析和對比。采用了聚類算法常用的對比指標調整后的蘭特指數（ARI），每個基準值的范圍從0到1，值越大，表示聚類效果越好。

為了比較候選聚類算法的優點，在實驗中使用的數據列于表1。包括9個來自東芬蘭大學1http：//cs.joensuu.fi/sipu/datasets/的shape數據集。表1總結了所有數據集的屬性數量和類數。

表1 9個實驗數據集的信息

4種聚類算法都需要設置多種參數。DD-DPC和ADPC-KNN只需要一個參數即k近鄰點個數，可預先指定。DPC和DNDPC都需要設置截止距離dc，初始聚類中心，由密度ρ和距離δ決策圖手動選擇。對于4種聚類算法在每個數據集上執行了多次，列出了每個方法的最佳結果。實驗中4種聚類算法的參數都是精心挑選的。

4.1 聚類結果分析

將對DD-DPC、DPC、ADPC-KNN、DNDPC這4種算法在3種典型的二維數據集（Aggregation、Jain、Compound）上進行聚類分析比較。每個圖像分別顯示4種算法的聚類結果，使用不同的顏色和形狀代表不同的聚類，如圖4～6所示，其中子圖（a）表示數據的真實結果，圖（b）表示新算法的聚類結果，（c）～（e）子圖分別表示DPC、ADPC-KNN、DNDPC算法的聚類結果。每個聚類中心每個聚類中心分別使用菱形方塊表示。

圖4中的Aggregation數據集，它有7個不同大小和形狀的類，兩對聚類相互連接。DD-DPC和DNDPC都可以找到正確的聚類中心和聚類，并獲得與數據幾乎一致的聚類結果，這個從4.2節的指標比較中也能看出。而DPC聚類算法由于無法處理類中擁有兩個高密度點的情況，導致左下角的大類被分割成兩類；ADPC-KNN由于計算出來的dc過大，導致左下角3個類都被誤分為同一類。在表2中，DD-DPC和DNDPC的ARI都是將近100%準確，而DPC和ADPC-KNN則相對正確率低很多。

圖5中的Jain數據集，它有2類373點構成，每個類中密度相對均勻，每個類都有多個高密度的點，在聚類中心決策圖上可能會被認為聚類中心，導致聚類成多個類。圖5分別顯示了聚類中心和聚類效果。DD-DPC通過去除低密度點和合并聚類中心點可以獲得良好效果。而DPC，DNDPC則會認為多個高密度點都是聚類中心，導致聚類成多個類。ADPC-KNN雖然能夠合并，但是由于下方類的上半部分與上方類相對較近，導致聚類錯誤。

對于圖6中的Compound數據集，它有399個點6類不同形狀的聚類，點分布不均勻，其中有的類被另外一個類包含在中間。DD-DPC能夠識別出包含在中間的類，但是識別不出分別在右邊的那個密度相對小得多的類。而DPC、ADPC-KNN和DNDPC在對包含在里面的類無能為力。

圖4 Aggregation數據集

圖5 Jain數據集

圖6 Compound數據集

4.2 算法指標對比與分析

本節分別對4種算法，對調整后的蘭特指數（ARI）指標進行比較。每個基準值的范圍從0到1，值越大聚類效果越好。粗體表示結果最好。

表2表明，DD-DPC算法在unbalance數據集上表現略遜色于NDDPC，即說明也能處理類密度分布不均衡的情況。但是在其他數據集上，本文提出的DD-DPC在數據集上的表現良好，特別是Jain和Compound數據集上。因為該數據集中包含多個高密度峰值。

表2 4種聚類算法在合成數據集上的ARI指標比較

5 結論

本文的核心工作在于將密度峰值聚類方法的聚類過程視為聚類中心確定、每個數據點的聚類歸屬兩個環節，然后提出將數據按照密度分為高密度和低密度分別聚類，提出了基于數據點密度二分法的密度峰值聚類方法。

在多個合成及實際數據集上，從聚類可視化結果以及調整后的蘭特指數（ARI）指標上進行比較，實驗結果表明，本文所提方法，能夠有效地處理聚類中心的數據點密度差異較大，或者同一個聚類中包含多個密度中心等情況下，密度峰值聚類方法聚類效果受到影響的問題。

[1]Rodriguez A，Laio A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.

[2]Wang Y，Chen Q，Kang C，et al.Clustering of electricity consumption behavior dynamics toward big data applications[J].IEEE Transactions on Smart Grid，2016，7（5）：2437-2447.

[3]Liu P，Liu Y，Hou X，et al.A text clustering algorithm based on find of density peaks[C]//2015 7th International Conference on Information Technology in Medicine and Education（ITME），2015：348-352.

[4]Yu J，Xie L，Xiao X，et al.A density peak clustering approach to unsupervised acoustic subword units discovery[C]//2015 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference（APSIPA），2015：178-183.

[5]Qin Y，Zhao C，Gao F.An iterative two-step sequential phase partition（ITSPP） method for batch process modeling and online monitoring[J].AIChE Journal，2016，62（7）：2358-2373.

[6]Li S，Zhou X，Shi H，et al.An efficient clustering method for medical data applications[C]//2015 IEEE International Conference on Cyber Technology in Automation，Control，and Intelligent Systems（CYBER），2015：133-138.

[7]Liu Dongchang，Cheng S F，Yang Yiping.Density peaks clustering approach for discovering demand hot spots in city-scale taxi fleet dataset[C]//2015 IEEE 18th International Conference on Intelligent Transportation Systems，2015：1831-1836.

[8]Du H.Robust local outlier detection[C]//2015 IEEE International Conference on Data Mining Workshop（ICDMW），2015：116-123.

[9]Jia S，Tang G，Hu J.Band selection of hyperspectral imagery using a weighted fast density peak-based clustering approach[C]//International Conference on Intelligent Science and Big Data Engineering，2015：50-59.

[10]Ma C，Ma T，Shan H.A new important-place identification method[C]//2015 IEEE International Conference on Computer and Communications（ICCC），2015：151-155.

[11]Mehmood R，Bie R，Dawood H，et al.Fuzzy clustering by fast search and find of density peaks[C]//2015 International Conference on Identification，Information，and Knowledge in the Internet of Things（IIKI），2015：258-261.

[12]Wang X F，Xu Y.Fast clustering using adaptive density peak detection[J].Statistical Methods in Medical Research，2015，26（6）：2800-2811.

[13]Wang S，Wang D，Li C，et al.Clustering by fast search and find of density peaks with data field[J].Chinese Journal of Electronics，2016，25（3）：397-402.

[14]Mehmood R，Zhang G，Bie R，et al.Clustering by fast search and find of density peaks via heat diffusion[J].Neurocomputing，2016，208：210-217.

[15]Yan Z，Luo W，Bu C，et al.Clustering spatial data by the neighbors intersection and the density difference[C]//2016 IEEE/ACM 3rd International Conference on Big Data Computing Applications and Technologies（BDCAT），2016：217-226.

[16]Du M，Ding S，Jia H.Study on density peaks clustering based on k-nearest neighbors and principal component analysis[J].Knowledge-Based Systems，2016，99：135-145.

[17]高詩瑩，周曉鋒，李帥.基于密度比例的密度峰值聚類算法[J].計算機工程與應用，2017，53（16）：10-17.

[18]李建勛，申靜靜，李維乾，等.基于趨勢函數的空間數據聚類方法[J].計算機工程與應用，2017，53（6）：22-28.

[19]Liu Y，Ma Z，Yu F.Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy[J].Knowledge-Based Systems，2017，133.

[20]Hou J，Cui H.Density Normalization in density peak based clustering[C]//International Workshop on Graphbased Representations in Pattern Recognition，2017：187-196.

[21]Barany I，Vu V H.Central limit theorems for Gaussian polytopes[J].Annals of Probability，2006，35（4）：1593-1621.