基于CDbw和人工蜂群優(yōu)化的密度峰值聚類算法

姜建華, 吳 迪, 郝德浩, 王麗敏, 張永剛, 李克勤

(1. 吉林財經(jīng)大學 數(shù)據(jù)科學系, 吉林省互聯(lián)網(wǎng)金融重點實驗室, 長春 130117;2. 吉林大學 符號計算與知識工程教育部重點實驗室, 長春 130012;3. 紐約州立大學 計算機系, 美國 紐約 12561)

聚類分析可在沒有任何先驗信息下對數(shù)據(jù)進行分析, 識別數(shù)據(jù)空間的潛在結(jié)構(gòu)[1], 廣泛應用于模式識別和市場研究等領(lǐng)域[2]. Hartigan等[3]提出的基于歐氏距離的K-means聚類算法, 由于算法簡單、 高效而被廣泛使用; Frey等[4]提出了近鄰傳播(affinity propagation, AP)算法, 并應用于圖像識別[5]中; Rodriguez等[6]提出了一種基于密度峰值的聚類(DPC)算法, 因其能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點, 并能高效進行樣本分配和離群點剔除, 已引起廣泛關(guān)注[7-8], 但該算法對于類簇間數(shù)據(jù)點的識別與分類有待商榷.

本文以DPC算法為基礎, 提出一種基于人工蜂群與CDbw聚類指標優(yōu)化的密度峰值(BeeDPC)算法, 繼承了DPC算法在聚類中心點自動識別、 自動聚合的優(yōu)勢, 通過計算數(shù)據(jù)點到近鄰的最高密度點和次高密度點距離之間的關(guān)系, 提升類簇間數(shù)據(jù)點類別判斷決策的科學性.

1 BeeDPC算法

DPC算法的核心是通過聚類中心點主動吸附與其距離較近且密度更小的點, 實現(xiàn)任意分布數(shù)據(jù)集的聚類, 但其存在一定的局限： 1)dc值的選取極大影響聚類結(jié)果； 2) 相鄰聚類間的點存在類別判斷不合理問題； 3) 聚類結(jié)果依賴于已完成類別判斷的高密度點, 一旦存在錯誤類別判斷的高密度點即直接導致所跟隨的低密度數(shù)據(jù)點的誤判, 并產(chǎn)生連帶效應.

圖1為R15數(shù)據(jù)集的密度峰值聚類結(jié)果. 由圖1可見, 當dc=0.728 8時, 聚類結(jié)果接近合理聚類結(jié)果(圖1(A)); 當dc=1.419 6時, 聚類結(jié)果不理想(圖1(B)), 表現(xiàn)為在類簇間存在一定數(shù)量點的誤判.

圖1 R15數(shù)據(jù)集的密度峰值聚類結(jié)果Fig.1 Density peak clustering results of R15 data set

本文BeeDPC算法在充分繼承DPC算法優(yōu)勢的基礎上, 對其聚合原則做出相應調(diào)整, 以提高DPC算法對類簇間數(shù)據(jù)點的敏感度, 給出更合理的類簇間點聚合原則. BeeDPC算法步驟如下：

1) 計算數(shù)據(jù)點的密度并生成決策圖.

首先計算數(shù)據(jù)點間的距離, 將降序排列后得到的截斷距離作為dc值, 并計算各數(shù)據(jù)點密度. 第i個數(shù)據(jù)點的密度值為

(1)

其中dij表示第i個數(shù)據(jù)點到第j個數(shù)據(jù)點間的距離, 當dij-dc<0時,χ(dij-dc)=1； 否則,χ(dij-dc)=0. 第i個數(shù)據(jù)點到全部比其密度值高點的距離最小值為

(2)

2) 按聚類原則對數(shù)據(jù)點初步聚類.

BeeDPC算法在聚類原則上借鑒三角穩(wěn)定性思想, 在每個數(shù)據(jù)點聚類前, 不僅簡單考慮與該點距離最小的相對高密度值點(nneigh1), 還考慮與該點距離次小的相對高密度值點(nneigh2). 當nneigh1和nneigh2屬同一類時, 可認為該數(shù)據(jù)點有較明確的聚類歸屬; 當nneigh1和nneigh2為不同類時, 認為該數(shù)據(jù)點的聚類結(jié)果可能存在由其特殊位置導致的爭議情形, 它既可與nneigh1屬同一類, 也可與nneigh2屬同一類.

3) 識別類簇間數(shù)據(jù)點.

經(jīng)過對數(shù)據(jù)點的初步分類, 所有數(shù)據(jù)點主要分為兩類： 已明確類別判定數(shù)據(jù)點集和類簇間未判定數(shù)據(jù)點集. 在聚合操作上, 對已明確類別判定數(shù)據(jù)點集使用DPC方法進行直接聚類, 但對類簇間未判定數(shù)據(jù)集則需進行二次類別判定.

第i個數(shù)據(jù)點最小距離與次小距離的差值為

γi=|Disti,nneigh1-Disti,nneigh2|,

(3)

其中： Disti,nneigh1表示第i個數(shù)據(jù)點到與其最近的高密度值點nneigh1的距離； Disti,nneigh2表示第i個數(shù)據(jù)點到與其次近的高密度值點nneigh2的距離. 對于γi的不同取值, 有：

① 當γi>dc時, 認為第i個數(shù)據(jù)點到nneigh1和nneigh2之間的距離有顯著性差別, 則該數(shù)據(jù)點處于距離nneigh1和nneigh2中較小距離的聚類邊緣位置, 故該數(shù)據(jù)點的所屬類簇應與距離較近的聚類一致;

② 當γi

4) 尋找所有類簇間數(shù)據(jù)點可能的所屬類簇標號.

在使用蜂群算法尋優(yōu)前, 首先要確定類簇間數(shù)據(jù)點最可能的所屬類簇標號. 對于每個類簇間數(shù)據(jù)點, 根據(jù)其與nneigh1和nneigh2的已知關(guān)系可確定其最可能的所屬類簇標號.

① 當nneigh1和nneigh2所處類簇標號均已知時, 直接記錄兩個類簇標號作為該數(shù)據(jù)點的可能類簇集;

② 當nneigh1和nneigh2中任意一個所處類簇標號未知時, 計算該數(shù)據(jù)點到各類簇中心點距離, 選出距離最近的類簇標號和另一個已知類簇標號作為該數(shù)據(jù)點的可能類簇集;

③ 當nneigh1和nneigh2的所處類簇標號均未知時, 計算該數(shù)據(jù)點到各類簇中心點距離, 選出距離最近的類簇標號和距離次近的類簇標號作為該數(shù)據(jù)點的可能類簇集.

5) 以CDbw值為目標函數(shù), 使用人工蜂群算法對類簇間數(shù)據(jù)點進行二次類別判定.

基于聚類間的緊密度和分離度計算的分類評價指標(CDbw), 可有效測量任意分布數(shù)據(jù)集的分類效果. 蜂群算法是模擬蜜蜂采蜜行為的優(yōu)化方法[9], Karaboga等[10]研究表明, 蜂群算法可廣泛應用于特征選擇[11]、 參數(shù)優(yōu)化[12]、 作業(yè)調(diào)度[13]和旅行推銷員[14]等問題. 識別待分類中數(shù)據(jù)點的歸屬問題也可視為一個優(yōu)化問題, 針對數(shù)據(jù)點的不同取值, 使用以CDbw為目標函數(shù)的人工蜂群算法對待分類數(shù)據(jù)點的所屬類簇標號求解可較好地解決該問題.

CDbw主要依賴簇間的分離程度和簇內(nèi)的緊密程度：

(4)

(5)

整體類簇間的密度為

(6)

(7)

當分類效果較好時, 不同類簇間的距離更遠, 密度值也相對較小; 反之, 當分類效果較差時, 不同類簇間的距離相對較小, 密度值相對較高.

相對類簇內(nèi)密度為

(8)

(9)

其中:s為伸縮系數(shù); stdev為數(shù)據(jù)點的密度標準差； cardinality(vij)表示類簇間密度值, 計算公式為

(10)

式中:vij為對每個類簇內(nèi)數(shù)據(jù)點使用伸縮系數(shù)s調(diào)整后的數(shù)據(jù)點；xl為類簇內(nèi)的數(shù)據(jù)點；ni為類簇內(nèi)數(shù)據(jù)點的數(shù)目. 類簇C的緊密度為

(11)

為了抵消簇內(nèi)緊密程度和類簇形狀、 位置間的相互影響, 根據(jù)伸縮系數(shù)s引入ns作為影響因子, 本文設ns=8. 在考慮到類簇內(nèi)緊密度的基礎上計算出的類簇間分離度為

(12)

計算聚類結(jié)果的CDbw值為

CDbw(C)=Cohesion(C)·SC(C),c>1.

(13)

由考慮到類簇內(nèi)緊密度的類簇間分離度和類簇內(nèi)緊密度組成CDbw評價系數(shù). 分類效果越好, CDbw值越大. 本文提出以CDbw為目標函數(shù)的蜂群算法, 針對每次類簇間數(shù)據(jù)點的聚類結(jié)果, 根據(jù)CDbw取值尋優(yōu)求解, 最終得到最優(yōu)解, 即類簇間數(shù)據(jù)點的最佳聚類結(jié)果.

6) 反復評估, 直至完成全部數(shù)據(jù)點的聚類.

將得到的可明確分類數(shù)據(jù)點的聚類結(jié)果與類簇間數(shù)據(jù)點的聚類結(jié)果整合出最終結(jié)果, 并用輪廓系數(shù)(Sil)和F值評價聚類結(jié)果.

2 實驗結(jié)果與分析

為了測試BeeDPC聚類算法的有效性和穩(wěn)定性, 在數(shù)據(jù)集上, 選取部分已知數(shù)據(jù)集和自定義二維數(shù)據(jù)集作為輸入數(shù)據(jù)； 在聚類算法上, 將本文算法與K-means,AP和DPC等算法進行對比. 選用的測試數(shù)據(jù)集參數(shù)列于表1.

表1 測試數(shù)據(jù)集參數(shù)Table 1 Parameters of testing data sets

2.1 自動識別類簇間數(shù)據(jù)點

BeeDPC算法克服了DPC算法在類簇間數(shù)據(jù)點聚類不合理的缺陷. 在DPC算法中, 聚類結(jié)果極大地依賴dc的取值, 導致許多類簇間數(shù)據(jù)點的聚類極不合理, BeeDPC算法較好地解決了該問題. 圖2為自動識別不同數(shù)據(jù)集中類簇間數(shù)據(jù)點的結(jié)果, 其中: (A),(B),(C)為已知數(shù)據(jù)集類簇間數(shù)據(jù)點的識別結(jié)果; (D),(E),(F),(G)為自定義數(shù)據(jù)集類簇間數(shù)據(jù)點的識別結(jié)果.

圖2 自動識別不同數(shù)據(jù)集中類簇間數(shù)據(jù)點的結(jié)果Fig.2 Results of automatic identification of data points between clusters of different data sets

2.2 自動識別任意形狀數(shù)據(jù)集的類簇中心點和類簇數(shù)目

BeeDPC和DPC算法在識別任意形狀數(shù)據(jù)集的類簇中心點和類簇數(shù)目上都有顯著效果. 憑借原DPC算法的優(yōu)勢, 考慮到各點的密度和點間距離關(guān)系, 可清晰地確定數(shù)據(jù)集的類簇中心點和類簇數(shù)目. 在決策圖中, 無論是已知數(shù)據(jù)集(Flame), 還是自定義數(shù)據(jù)集, 相比于其他數(shù)據(jù)點, 類簇中心點在決策圖中都較凸顯. 顯然, 比預設定類簇個數(shù)的K-means算法和偏向參數(shù)的AP算法更有優(yōu)勢, 因其可容易確定類簇數(shù)目及中心點.

2.3 處理不同形狀和大小的數(shù)據(jù)集

BeeDPC和DPC算法在處理不同形狀、 大小的數(shù)據(jù)集都有顯著效果. 已知數(shù)據(jù)集Aggregation具有大小、 形狀不同的7個類簇, 由K-means,AP,DPC和BeeDPC算法聚合的結(jié)果如圖3所示.

圖3 Aggregation數(shù)據(jù)集的聚合效果Fig.3 Clustering effets of Aggregation data set

2.4 分類效果評價

輪廓系數(shù)(Sil)是結(jié)合內(nèi)聚度和分離度的評價方式, 常用于表示評估聚合效果, 定義如下:

(14)

其中:a(t)表示向量t到其簇內(nèi)其他點的距離；b(t)表示向量t到其他簇內(nèi)各點的平均距離. 輪廓系數(shù)(Sil)的值域為[-1,1], 值越大表明分類結(jié)果的內(nèi)聚度和分離度都相對較優(yōu), 聚合效果相對較好.

本文選用K-means,AP,DPC聚類算法與BeeDPC算法分別針對3個已知數(shù)據(jù)集(Flame,Aggregation,R15)進行對比實驗, 實驗結(jié)果列于表2. 由表2可見, 本文算法的聚類效果整體最優(yōu).

表2 不同數(shù)據(jù)集聚類結(jié)果的Sil值Table 2 Sil values of clustering results for different data sets

2.5 結(jié)果分析

本文提出的BeeDPC算法是以DPC算法的假設為基礎, 但聚類原則上與DPC算法截然不同. BeeDPC算法在對數(shù)據(jù)點聚類的同時更注重類簇間數(shù)據(jù)點的聚合處理. 本文對已知的數(shù)據(jù)集和特殊的自定義數(shù)據(jù)集都進行了測試, 并與K-means,AP,DPC三種聚類方法進行了對比. 對比結(jié)果表明, 本文方法主要有以下優(yōu)點:

1) 自動識別類簇間數(shù)據(jù)點. 由于DPC算法對待分類數(shù)據(jù)點的類別判斷僅依據(jù)單個已確定的點, 一旦存在某個數(shù)據(jù)點的判斷不合理就會極大影響其余待分類數(shù)據(jù)點的聚合效果. 因此, 本文將三角形穩(wěn)定性原理的思想引入DPC算法中, 同時考慮待分類數(shù)據(jù)點及其與最高密度點、 次高密度點之間距離的相互關(guān)系, 實現(xiàn)類簇間數(shù)據(jù)點的識別. 特別地, 所提出的BeeDPC算法是在對普通數(shù)據(jù)點聚類的同時可實現(xiàn)對類簇間數(shù)據(jù)點的識別.

2) 聚類類簇間數(shù)據(jù)點的合理性. 在聚類原則上, 本文摒棄了DPC算法的弊端, 同時引入最高密度點和次高密度點到待分類數(shù)據(jù)點的距離, 充分考慮三點之間距離相對關(guān)系所對應的不同情形, 針對數(shù)據(jù)點的不同特性使用不同的處理方法. 在對類簇間數(shù)據(jù)點處理時, 引入了優(yōu)化算法----蜂群算法, 并以CDbw值為目標函數(shù), 極大提高了對類簇間數(shù)據(jù)點所屬類簇的科學聚類.

3) 處理任意分布的數(shù)據(jù)集. BeeDPC算法是對DPC算法在聚類原則上的進一步改進, 因此, 本文算法很好地保留了DPC算法的優(yōu)勢, 能處理任意形狀及任意密度的數(shù)據(jù)集.

綜上所述, 本文提出的BeeDPC算法在保留DPC自動識別類簇中心和可處理任意分布數(shù)據(jù)集優(yōu)點的基礎上, 引入三角形穩(wěn)定性原理, 通過比較待分類數(shù)據(jù)點和最高密度數(shù)據(jù)點、 較高密度數(shù)據(jù)點三者距離上的相互關(guān)系, 得到類簇間數(shù)據(jù)點可能的聚類結(jié)果的集合, 使用以CDbw值為目標函數(shù)的蜂群算法求得類簇間數(shù)據(jù)點聚類的最優(yōu)解, 得到全部數(shù)據(jù)點的聚類結(jié)果. 實驗結(jié)果表明, BeeDPC算法對任意分布的數(shù)據(jù)集, 在類簇間數(shù)據(jù)點的識別和分類上都有較大優(yōu)勢.