許青林 羅煒平 陳烈鋒

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

關(guān)鍵詞：聚類算法;密度峰值;決策點(diǎn);夾角;密度

DOI： 10. 11907/rjdk.191281

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A

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

0 引言

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

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

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

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

1 快速密度峰值搜索算法及改進(jìn)

1.1 傳統(tǒng)密度峰值搜索算法

1.2 改進(jìn)的密度峰值搜索算法

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

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

顯然，λ值越大，表示該點(diǎn)越可能為聚類中心。因此，對所有λ值進(jìn)行降序排列，結(jié)合數(shù)據(jù)集情況顯示到二維平面坐標(biāo)上，如圖3所示為A數(shù)值的變化情況。

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

1.2.1 改進(jìn)的聚類中心選擇方法

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

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

此時，拐點(diǎn)可理解為相對之前數(shù)據(jù)點(diǎn)下降趨勢最大的點(diǎn)。

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

1.2.2 子簇合并處理

原始密度峰值算法在實(shí)現(xiàn)聚類過程中會出現(xiàn)屬于同一個類的數(shù)據(jù)點(diǎn)被劃分為多個子類的情況，即多密度峰值現(xiàn)象，在經(jīng)過上述聚類初始點(diǎn)選取之后，也可能存在同樣問題，使聚類結(jié)果缺乏準(zhǔn)確性。聚類結(jié)果需實(shí)現(xiàn)類間差異度最大、類內(nèi)相似度最大，因而本文認(rèn)為類的邊界區(qū)域密度大于或等于近鄰類平均密度時，該近鄰類即是被錯誤劃分的子類?；谠撍枷?，給出以下定義：

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

輸出：滿足目標(biāo)函數(shù)的k個簇

1.數(shù)據(jù)預(yù)處理，讀取數(shù)據(jù)

2.相關(guān)計(jì)算量計(jì)算

求出各數(shù)據(jù)點(diǎn)之間的距離dij，得到距離矩陣。并通過計(jì)算確定截?cái)嗑嚯xdc

計(jì)算每個數(shù)據(jù)點(diǎn)的局部密度ρi與高密度距離δi

3.確定聚類中心

求取每個點(diǎn)的λ值，然后降序排列

計(jì)算每個點(diǎn)的決策值向量夾角cosa大小，確定拐點(diǎn)位置

以跳躍點(diǎn)之前的數(shù)據(jù)點(diǎn)為參考聚類中心

4.類合并判斷

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

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

異常點(diǎn)或異常子類處理。除去異常點(diǎn)并將簇平均密度遠(yuǎn)小于其它高密度子簇的低密度異常子類篩選出來，去除簇標(biāo)記后，形成新的低密度數(shù)據(jù)集。聚類，重新計(jì)算簇局部區(qū)域密度以及簇平均密度

子類合并。依據(jù)本文提出的合并準(zhǔn)則實(shí)現(xiàn)子類合并，并將異常點(diǎn)或者樣本數(shù)量過低的點(diǎn)歸為噪聲點(diǎn)。

聚類結(jié)果不再發(fā)生變化，輸出。

2 實(shí)驗(yàn)與討論

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

2.1 人工數(shù)據(jù)集結(jié)果分析

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

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

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

人工數(shù)據(jù)集Jain數(shù)據(jù)集的數(shù)據(jù)點(diǎn)分布呈現(xiàn)出密度不均勻的特點(diǎn)，利用該數(shù)據(jù)檢驗(yàn)兩算法性能差異性。

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

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

2.2 UCI數(shù)據(jù)集結(jié)果分析

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

分別利用每個算法對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行聚類實(shí)驗(yàn)并統(tǒng)計(jì)兩實(shí)驗(yàn)結(jié)果的聚類準(zhǔn)確率[20]，本文選用Micro-precision標(biāo)準(zhǔn)[21]，通過對分類信息的處理評價聚類結(jié)果好壞。當(dāng)標(biāo)記矢量中某聚類標(biāo)記和類別屬性中某已存在的類別覆蓋的相同對象個數(shù)最多，則將該聚類標(biāo)記對應(yīng)為相應(yīng)已知類別。計(jì)算公式為：

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

驗(yàn)證改進(jìn)后算法對于密度分布不均勻數(shù)據(jù)的聚類結(jié)果，使用6個UCI數(shù)據(jù)集進(jìn)行對比測量，調(diào)整所需參數(shù)，分別記錄算法在調(diào)參后最優(yōu)聚類結(jié)果和調(diào)參后算法最優(yōu)聚類結(jié)果的準(zhǔn)確率。對比發(fā)現(xiàn)，在處理大密度數(shù)據(jù)時，使用改進(jìn)后的算法處理效果更好，聚類準(zhǔn)確率相對較高。

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

本文改進(jìn)算法在處理密度變化較大類簇上的不足時，通過利用CFSFDP算法中數(shù)據(jù)點(diǎn)的密度屬性，實(shí)現(xiàn)類簇合并，相較于傳統(tǒng)的CFSFDP，在某些大密度數(shù)據(jù)集下可以準(zhǔn)確抓取到類簇中心，改善數(shù)據(jù)集聚類結(jié)果。

3 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

[5]許麗利.聚類分析的算法及應(yīng)用[D].長春：吉林大學(xué)，2010.

[6]李斌，郭劍毅.聚類分析在客戶關(guān)系管理中的研究與應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005（2）：540-542.

[7] 曹樹貴，李文，陳軍霞，等.聚類分析在高考成績研究主題發(fā)現(xiàn)中的應(yīng)用[J].軟件導(dǎo)刊，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] 周世兵.聚類分析中的最佳聚類數(shù)確定方法研究及應(yīng)用[D].無錫：江南大學(xué)，2011.

[10] 宋董飛，徐華.DBSCAN算法研究及并行化實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（ 24）：52-56+122.

[11] 李雙慶，慕升弟.一種改進(jìn)的DBSCAN算法及其應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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].西安：西安理工大學(xué)，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].計(jì)算機(jī)工程與應(yīng)用，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].系統(tǒng)工程理論與實(shí)踐.2014. 34（9）：2417-2431.

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

（責(zé)任編輯：江艷）

基金項(xiàng)目：廣東省科技計(jì)劃項(xiàng)目（ 20168030306003）

作者簡介：許青林（1963-），男，廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院副教授、碩士生導(dǎo)師，研究方向?yàn)檐浖こ?、云?jì)算和企業(yè)信息化等;羅煒平（1993-），男，廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，研究方向?yàn)榇髷?shù)據(jù)、云計(jì)算;陳烈鋒（1993-），男，廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，研究方向?yàn)榇髷?shù)據(jù)、云計(jì)算。