一種自動確定密度峰值的聚類算法改進

許青林 羅煒平 陳烈鋒

摘要：相比較于其它聚類算法，密度峰值聚類算法可將任意形狀的數據與較少的參數和高效的聚類速度結合起來。針對當某個類中出現多個密度峰值時，聚類結果缺乏準確性的問題，提出一種改進的密度峰值聚類算法（ CFSFDP）。該算法從決策點數值變化的角度，考慮3個點（當前數據點、當前點的前一數據點與當前點的后一數據點）連線形成夾角的變化情況實現算法自主選取聚簇中心;同時為減少人為因素對聚類結果有效性造成的影響，算法通過比較類簇之間的密度屬性，實現動態的子簇合并，減少主觀因素對算法結果的影響。通過實驗與已有密度聚類算法對比，改進算法不僅很好地避免了原算法人為確定參數給實驗結果造成的影響，而且具有更好的聚類性能。

關鍵詞：聚類算法;密度峰值;決策點;夾角;密度

DOI： 10. 11907/rjdk.191281

開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312

文獻標識碼：A

文章編號：1672-7800（2020）001-0075-05

0 引言

聚類分析是數據挖掘中一種無監督的分類方法，其利用一定的準則將數據集劃分為多個類或簇，可滿足最大化不同類數據對象相異度，最小化同類數據對象相似度[1-4]。聚類分析在模式識別、機器學習、圖像分析、神經網絡、生物醫學及客戶細分等眾多領域有廣泛應用]5-7]。聚類方法一般可分為5類：基于劃分的方法、基于層次的方法、基于密度的方法及基于模型的方法[8，9]。其中，層次聚類和密度聚類是聚類效果較好、能夠發現任意形狀簇的聚類算法。

經典密度聚類算法DBSCAN需根據用戶事先確定的密度參數定義低密度數據和高密度數據，將高密度數據集作為聚類，然而合適的密度參數往往很難快速找到[10-11]。為了降低初始閾值參數對結果的影響，Alex等[12]提出一種新的基于密度峰值的聚類算法（CFSFDP）。該算法可簡單、快速找到密度峰值點，但它將密度峰值點直接作為聚類中心，容易使一個類被劃分為多個子類。算法側重于點與點之間的距離以及點在一定范圍內具有的密度屬性。算法假設聚類中心點周圍都是密度比它低的點，且這些點距離該聚類中心的距離相比其它類中心點更近。

雖然該算法簡單，不需要迭代，時耗低，適用于多種類型數據集且效率高，但同時在自主選擇聚類中心點以及在處理一個類中存在多密度峰值點的問題上，并不能做到有效避免或解決。Wang等¨糾提出一種利用原始數據集數據場的潛在熵自動提取最優閾值的新方法，可實現更好更快的簇中心點自主選取;針對多密度峰值的問題，Zhang等[14-15]在參考CHAMELEON算法思想的前提下，實現多密度峰點自主合并;為了使CFSFDP能夠更好地應用于高維數據，Du等[16]結合k近鄰以及主成分分析的思想對算法進行優化;為了提高聚類精度，Cao等[17]提出基于密度比例的CFSFDP，使用密度作為區別不同類簇的特征屬性，提高密度較小類的辨識度;Zhang等[18]結合CFSFDP算法和CHA-MELEON算法，提出了E_CFSFDP，對原始算法生成的初始類簇進行合并從而實現優化;Liu[19]引進K最近鄰思想，計算全局參數DC和本地每個點的密度p，采用一種新的方法自動選擇初始聚類中心，最后匯總集群的算法KNN-DPC.解決了CFSFDP算法聚類結果對截斷距離de比較敏感和因為進一步分配帶來的連帶分配錯誤的問題。

本文在引入一個新的變量將算法中兩個較重要的參數（密度以及距離）進行歸一化處理之后，通過新變量的變化情況確定參考聚類中心點個數;在層次聚類思想下，提出合適的合并準則，簇間邊界局部密度大于近鄰簇的平均密度，即可考慮兩個簇進行合并，且合并過程無需人為輸入指定參數即可自動結束算法，獲得更好的聚類效果與準確率。

1 快速密度峰值搜索算法及改進

1.1 傳統密度峰值搜索算法

1.2 改進的密度峰值搜索算法

相較于其它密度聚類算法，CFSFDP能夠快速實現聚類且適用于各種形狀，然而在聚類中心決策時，一般選取沿坐標軸正45。方向偏離原點最遠的一組數據點，這需要在人工輔助下實現，對于聚類結果的客觀性有一定影響。如圖2所示，在不同主觀因素影響下，得到的聚類中心不同。

文獻[10]針對無法正確選擇聚類中心的情形，為使聚類中心能夠正確判定，將p和δ兩個值轉化到同一量綱上考慮，轉換計算方式為：

顯然，λ值越大，表示該點越可能為聚類中心。因此，對所有λ值進行降序排列，結合數據集情況顯示到二維平面坐標上，如圖3所示為A數值的變化情況。

圖3以數據集數量為橫軸，λ值為縱軸，從中可以看出非聚類中心點的λ數值較為平滑，而從聚類中心點過渡到非聚類中心有一個較為明顯的跳躍，這時只需確定^值發生明顯跳躍時對應的點，在該點之前的數據點均可考慮為聚類中心。而得到的聚類中心點在聚類過程中可能發生同一類中出現多密度峰值點的現象，可利用參考文獻[15]的類合并思想，實現子類合并從而優化聚類結果。

1.2.1 改進的聚類中心選擇方法

為避免人為因素對聚類結果的影響，將參數_pi和δi轉換為λ之后，以該新參數的變化趨勢為新的聚類初始點選取標準確定初始聚類點。在上述歸一化處理基礎上，對圖3作局部細化，以便更好地觀察數據點變化趨勢。選取前面一定數量的數據點加以實現并不會影響圖像整體趨勢，選取前n（以n=25為例）個數據點，細化橫軸數據區間，以更好地觀察跳躍現象。結果如圖4所示。

觀察可知圖像前半段下降趨勢不一但整體呈現下降趨勢，而在后半段基本趨于平滑，變化不大。前后變化的轉折點有一個明顯的下降跳躍，故定義一個變量記錄決策值變化趨勢。

此時，拐點可理解為相對之前數據點下降趨勢最大的點。

觀察決策值λ的變化趨勢可知，一定數量的點之后數據點變化趨勢趨近于0，即k i+1基本為0，故在考慮向量夾角時應考慮前后決策值變化是否已接近為0，以此減少時間消耗。圖5給出向量夾角變化趨勢，其中白色點即為拐點。

1.2.2 子簇合并處理

原始密度峰值算法在實現聚類過程中會出現屬于同一個類的數據點被劃分為多個子類的情況，即多密度峰值現象，在經過上述聚類初始點選取之后，也可能存在同樣問題，使聚類結果缺乏準確性。聚類結果需實現類間差異度最大、類內相似度最大，因而本文認為類的邊界區域密度大于或等于近鄰類平均密度時，該近鄰類即是被錯誤劃分的子類。基于該思想，給出以下定義：

定義1邊界局部密度。確定好每個簇的邊界集后，根據簇中點的局部密度值按大小排列，取其中最大值作為該簇局部密度，參考式（1）的定義形式，進行如下變形：假設簇標號為A，則EA為類A的邊界點集，找出邊界點集中局部密度最大的點，記為pb：

輸出：滿足目標函數的k個簇

1.數據預處理，讀取數據

2.相關計算量計算

求出各數據點之間的距離dij，得到距離矩陣。并通過計算確定截斷距離dc

計算每個數據點的局部密度ρi與高密度距離δi

3.確定聚類中心

求取每個點的λ值，然后降序排列

計算每個點的決策值向量夾角cosa大小，確定拐點位置

以跳躍點之前的數據點為參考聚類中心

4.類合并判斷

依據參考聚類中心生成初始類{C1，C2，…，Cn）

計算每個子類Ci局部區域密度pb以及Ci的簇平均密度pavg（i）

異常點或異常子類處理。除去異常點并將簇平均密度遠小于其它高密度子簇的低密度異常子類篩選出來，去除簇標記后，形成新的低密度數據集。聚類，重新計算簇局部區域密度以及簇平均密度

子類合并。依據本文提出的合并準則實現子類合并，并將異常點或者樣本數量過低的點歸為噪聲點。

聚類結果不再發生變化，輸出。

2 實驗與討論

使用MATLAB對算法進行仿真。分別在人工數據集以及UCI數據集上對算法（原始算法，改進的算法）性能進行比較。人工數據集選取文獻[12]中提到的R15數據集以及Jain數據集，UCI數據集選取Iris以及Wine數據。人工數據集的比較通過對比傳統CFSFDP、改進后的CFSFDP的聚類效果圖實現。采用聚類準確率進行實驗結果比較。實驗結果均以多次不同參數的試驗中最好的結果進行結果對比，以便更好地說明類間相異度較大（密度相差較大）時，本文算法性能更佳。

2.1 人工數據集結果分析

首先考慮在人工數據集上的比較。數據集信息如表1所示。

人工數據集R15數據分析有明顯的三層特征，外圍數據類間間隔大，里面兩層數據分布集中但類間間隔不明顯，這使得該數據集的類別較多，可以很好地驗證一個聚類算法有效性。R15數據集運行結果如圖6所示。

對比圖6、圖7可以看出，R15數據集中間部分數據點在CFSFDP算法實現過程中被錯誤地分配到了同一個類，而本文改進算法通過對數據點密度與距離的綜合考慮，準確識別出了數據集R15類別數，避免了人工選擇初始簇中心點給實驗結果造成的影響。從圖7-圖9可以看出DB-SCAN算法在不同輸入參數下聚類結果不同，而本文算法和CFSFDP算法均對輸入參數不敏感，原因是本文算法只對每個數據點局部密度相對值敏感，對選出來的密度峰值點劃分的初始子簇進行合并處理，增強了本文算法對密度峰值點選擇的魯棒性。

人工數據集Jain數據集的數據點分布呈現出密度不均勻的特點，利用該數據檢驗兩算法性能差異性。

從實驗結果圖10、圖11可以看出，CFSFDP將低密度數據集劃分為多個聚類，而本文改進算法可以有效地將低密度數據集合并到同一個密度值相對較高的區域中，且無需用戶輸入任何參數即可對結果進行控制。這說明在密度不均勻的條件下，本文算法結果仍具有一定的有效性;從圖11-圖13可以看出，DBSCAN算法不適用于密度分布不均勻的數據集，容易將低密度聚類劃分為多個子簇，并且將低密度聚類中的點當作噪聲點進行處理。

從以上兩個實驗結果可看出，本文算法根據兩個子簇密度分布情況采用合并子簇策略進行聚類，不依賴于用戶輸入的全局參數，與其它兩個聚類算法相比，本文算法適用于密度分布不均勻的數據集和任意形狀的聚類。

2.2 UCI數據集結果分析

在UCI數據集上對算法（比較的算法包括原CFSFDP、改進的CFSFDP、K-means、DBSCAN）進行比較。采用的數據集信息如表2所示。

分別利用每個算法對實驗數據進行聚類實驗并統計兩實驗結果的聚類準確率[20]，本文選用Micro-precision標準[21]，通過對分類信息的處理評價聚類結果好壞。當標記矢量中某聚類標記和類別屬性中某已存在的類別覆蓋的相同對象個數最多，則將該聚類標記對應為相應已知類別。計算公式為：

其中，k為分類數量，ai表示正確分類到類簇Ci的樣本數量，X為全體樣本。為了得到更好的實驗結果，采取對多次實驗結果取平均值的方式（實驗次數選定為10），各算法在不同的輸入參數下輸出結果，最終算法準確性表示為各算法在不同輸入參數下的平均聚類準確性。實驗結果如表3所示。

驗證改進后算法對于密度分布不均勻數據的聚類結果，使用6個UCI數據集進行對比測量，調整所需參數，分別記錄算法在調參后最優聚類結果和調參后算法最優聚類結果的準確率。對比發現，在處理大密度數據時，使用改進后的算法處理效果更好，聚類準確率相對較高。

表3為4種算法對6個UCI數據集聚類準確率的對比。從準確率可以看出，對于密度分布較不均勻的數據集，K-means、DBSCAN和CFSFDP算法的聚類效果都不理想。K-means算法無法有效作用于非球類數據的聚類，而其它兩個算法的算法效率則受限于既定的全局閾值。

本文改進算法在處理密度變化較大類簇上的不足時，通過利用CFSFDP算法中數據點的密度屬性，實現類簇合并，相較于傳統的CFSFDP，在某些大密度數據集下可以準確抓取到類簇中心，改善數據集聚類結果。

3 結語

本文介紹了一種基于新的決策值變化趨勢以及邊界簇屬性的快速聚類算法，針對CFSFDP存在的無法自主選擇聚類簇中心點及同一類中存在多密度峰值而無法正確聚類的問題，提出從決策值變化趨勢的角度確定密度峰值點及考慮簇邊界密度與近鄰簇平均密度之間的關系實現子類合并。改進之后的算法無需人工輔助即可選擇聚類中心點，且可以實現更好的聚類效果。仿真實驗從人工數據集和UCI數據集對比本文算法與其它3個算法的性能差異。結果表明，改進后的算法能在密度分布不均勻的情況下實現較好的聚類效果，且在計算量方面也比CFSFDP算法更優，因此本文對具有自然簇屬性、任意形狀簇數據的聚類具有一定的參考研究價值。

參考文獻：

[1]伍育紅.聚類算法綜述[J].計算機科學，2015，42（ Sl）：491-499.

[2]JAIN A K.Data clustering： 50 years heyond K-means[ M]. Berlin：Springer，2008.

[3] 金建國.聚類方法綜述[J].計算機科學，2014，41（ S2）：288-293.

[4] 王駿，王士同，鄧趙紅.聚類分析研究中的若干問題[J].控制與決 策，2012，27（3）：321-328.

[5]許麗利.聚類分析的算法及應用[D].長春：吉林大學，2010.

[6]李斌，郭劍毅.聚類分析在客戶關系管理中的研究與應用[J].計算機工程與設計，2005（2）：540-542.

[7] 曹樹貴，李文，陳軍霞，等.聚類分析在高考成績研究主題發現中的應用[J].軟件導刊，2017，16（5）：135-137.

[8]ESTER M. KRIECEL H P，XU X.A density-based algorithm for dis-covering clusters a density-based algorithm for discovering clusters inarge spatial databases with noise [C]. International Conference on Knowledge Discovery and Data Mining， 1996： 226-231.

[9] 周世兵.聚類分析中的最佳聚類數確定方法研究及應用[D].無錫：江南大學，2011.

[10] 宋董飛，徐華.DBSCAN算法研究及并行化實現[J].計算機工程與應用，2018，54（ 24）：52-56+122.

[11] 李雙慶，慕升弟.一種改進的DBSCAN算法及其應用[J].計算機工程與應用，2014，50（8）：72-76.

[12]RODRICUEZ A， LAIO A.Clustering by fast search and find of densi- ty peaks[J]. Science， 2014， 344（ 6191）： 1492.

[13]WANC S， WANG D，CAOYUAN LI，et al.Clustering hy fast searchand find of density peaks with data field[J].Chinese Journal of Elec-tronics， 2016， 25（3）：397-402.

[14]KARYPIS G，Han E H，Kumar V.Chameleon： hierarchical cluster-ing using dynamic modeling[M]. IEEE Computer Society Press，1999.

[15]陳恒飛.Chameleon聚類算法研究[D].西安：西安理工大學，2017.

[16]DU M， DING S，JIA H.Study on density peaks clustering based onk-nearest neighbors and principal component analysis [Jl. Knowl-edge-Based Systems， 2016， 99： 135-145.

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

[18]ZHANC W. LI J. Extended fast search clustering algorithm：Widelydensitv clusters， no density peaks [J]. Computer Science， 2015，5（7）：1-17.

[19] LIU Y， MA Z，YU F.Adaptive density peak clustering based onK-nearest neighbors with aggregating strategy[J].Knowledge-BasedSystems. 2017. 133（ 10）： 208-220.

[20]周開樂，楊善林，丁帥，等，聚類有效性研究綜述[J].系統工程理論與實踐.2014. 34（9）：2417-2431.

[21] 王蘭.基于層次聚類的簇集成方法研究[D].保定：河北大學，2010.

（責任編輯：江艷）

基金項目：廣東省科技計劃項目（ 20168030306003）

作者簡介：許青林（1963-），男，廣東工業大學計算機學院副教授、碩士生導師，研究方向為軟件工程、云計算和企業信息化等;羅煒平（1993-），男，廣東工業大學計算機學院碩士研究生，研究方向為大數據、云計算;陳烈鋒（1993-），男，廣東工業大學計算機學院碩士研究生，研究方向為大數據、云計算。