基于人工魚群的自適應密度峰值聚類算法
2024-01-22 07:16:44何凱琳張正軍
計算機工程與設計 2024年1期
何凱琳，張正軍+，位 雅，唐 莉
(1.南京理工大學 數學與統計學院，江蘇 南京 210094；2.景德鎮學院 信息工程學院，江西 景德鎮 333000)
0 引 言
聚類分析作為一種重要的數據挖掘技術，能夠在無監督的條件下探索數據的內在性質及規律。密度峰值聚類算法(clustering by fast search and find of density peaks algorithm，DPC)[1，2]是從樣本點密度的角度出發，通過快速搜索找到密度峰值作為聚類中心來進行聚類，能夠快速地識別任意形狀數據集的密度峰值點，直觀地找到聚類中心，因而受到了廣泛的關注。
然而，DPC算法也存在不足，如需要人為指定截斷距離dc和聚類中心、對存在多密度峰值的數據無法準確聚類等。國內外專家學者已提出了一些優化算法。王洋等[3]選擇基尼指數達到最小值時最優影響因子σ的值作為dc的取值。Ding等[4]構造了近似遵循GEV分布的判斷指數，將判斷指數值大于GEV上分位數的樣本點作為聚類中心。Yang等[5]構造加權完全圖，利用拉普拉斯中心性取代局部密度評價網絡節點的局部重要性。章曼等[6]利用非參數核密度估計計算局部密度，并通過自適應可達距離分配樣本點。還有一些學者將樣本點的近鄰信息引入到局部密度度量當中，杜明晶等[7]使用樣本點xi的k個最近鄰kNN(xi) 信息計算局部密度。覃華等[8]基于最優Oracle逼近構造馬氏距離，結合k近鄰算法實現密度最優估計。湯鑫瑤等[9]根據樣本點的自然最近鄰計算局部密度，并設計了兩步分配策略。
為了進一步增強DPC算法的自適應性，針對密度峰值聚類算法需要人為指定截斷距離dc、 根據決策圖人工選擇聚類中心、對一個簇中存在多密度峰值的數據無法準確聚類的問題，本文提出了基于人工魚群的自適應密度峰值聚類算法(adaptive density peaks clustering algorithm based on artificial fish swarm，AFSADPC)，將簇中心權值γ大于冪律分布上分位數的樣本點作為聚類中心，根據兩個相鄰簇的簇間邊界區域密度與簇平均密度構造簇間合并規則，并且利用人工魚群算法尋找使改進輪廓系數指標達到最大值時的最優截斷距離dc， 從而進行密度峰值聚類。
1 相關知識
1.1 密度峰值聚類算法與分析
1.1.1 密度峰值聚類算法的基本概念
DPC算法識別聚類中心主要基于以下假設：①聚類中心的局部密度高于其周圍樣本點；②聚類中心距離密度更高樣本點較遠。設有數據集X={x1，x2，…，xn}，xi={xi1，xi2，…，xim}，i=1，2，…，n，xij表示第i個樣本點的第j維屬性，j=1，2，…，m。 對于每個樣本點xi計算點xi的局部密度ρi以及xi與密度更高樣本點之間的距離δi來識別聚類中心[1，2]。
點xi的局部密度ρi有兩種計算方式：
(1)截斷核
(1)
(2)高斯核
(2)
對比兩種定義可知，截斷核為離散值，而高斯核為連續值，采用高斯核函數來估計不同樣本點的局部密度得到相同值的概率更小，因此通常選擇高斯核的計算方式來計算局部密度ρi， 但無論選擇哪種方式計算ρi都與截斷距離dc有關。
dc的計算方式如下
dc=dPN
(3)
點xi與密度更高樣本點間距離δi的計算方式如下
(4)
即對于非密度最高的樣本點xi，δi是計算點xi和其它密度更高樣本點之間的最小距離；對于密度最高的點xi，δi是點xi與最遠樣本點之間的距離。
計算出上述參數后，以ρi為橫軸，δi為縱軸繪制決策圖，從決策圖中選擇ρi較大且δi也較大的樣本點作為聚類中心，然后按照密度大小將剩余點分配到密度較高的最近鄰所屬簇。若兩個屬于不同簇的樣本點間距離小于截斷距離dc， 則被稱為其所屬簇的邊界點。簇的邊界區域是該簇邊界點的集合，若簇中某樣本點的局部密度大于簇邊界區域內的局部密度最大值，則該點被稱為所屬簇的核心點，其余點則被稱為光暈點。
1.1.2 密度峰值聚類算法的缺陷
本文主要針對DPC算法以下缺陷進行研究。
(1)dc取值問題。在實際處理數據時通常難以根據經驗確定截斷距離dc， 不同的dc取值會獲得不同的聚類結果，如圖1所示，在p=1%和p=2%的情況下DPC算法都能識別出Spiral數據集的聚類中心，但只有在p=2%的情況下得到了正確的聚類結果；
圖1 不同dc下DPC算法在Spiral數據集上的聚類結果
(2)聚類中心選擇問題。DPC算法根據決策圖人工選擇聚類中心，容易受主觀因素影響，且對于某些復雜的決策圖難以找到合理的聚類中心，如圖2(a)所示，根據Aggregation數據集的決策圖主觀判斷可能選取3個、7個或10個聚類中心，錯誤選擇非聚類中心進行聚類將會引起樣本點分配錯誤，影響聚類結果；
圖2 Aggregation數據集的決策圖和聚類結果(DPC，p=2%)
(3)多密度峰值問題。當數據集的一個簇中存在兩個或者多個的密度峰值時，DPC算法會選擇多個聚類中心從而誤將一個簇劃分成兩個或多個簇，造成過度劃分的情況，如圖2(b)所示，存在將一個簇錯誤劃分為兩個簇的情況。
1.2 人工魚群算法的基本概念
受到自然界中某些動物群體行為的啟發，學者們提出了群智能優化算法，通過模擬生物群體行為來實現優化。人工魚群算法(artificial fish swarm algorithm，AFSA)是一種基于魚群行為的隨機搜索優化算法[10，11]，采用自下而上的尋優策略，通過魚群中各個體的局部尋優實現全局尋優，具有并行性、簡單性、全局性、快速性和跟蹤性等特點，廣泛應用于通信系統、圖像處理、機器學習等領域。
人工魚的狀態定義為X={X1，X2，…，Xn}， 算法的參數有人工魚的視野范圍Visual、 步長Step、 擁擠度因子δ和重復次數Try_number。 設人工魚當前狀態為Xi， 其食物濃度(目標函數值)為Yi=f(Xi)。 人工魚群算法主要通過模擬魚群的四大基本行為實現全局尋優：
2 基于人工魚群算法改進的密度峰值聚類算法
2.1 自動選擇聚類中心策略
在DPC算法中需要在決策圖中人工選擇聚類中心，容易受到主觀因素影響，且對于某些復雜的決策圖難以找到合理的聚類中心，根據非聚類中心進行聚類將會進一步引起樣本點分配錯誤，從而得到錯誤的聚類結果。針對此缺陷，本節提出一種自動選擇聚類中心的策略，綜合考慮樣本點的ρ值和δ值構造簇中心權值γ， 將γ值大于冪律分布上分位數的樣本點作為聚類中心。
定義1 簇中心權值。為了便于描述同時具有高ρ值和高δ值的樣本點，對ρ值和δ值進行歸一化處理，并綜合考慮這兩個值構造簇中心權值γ
γ=ρ′·δ′
(5)
其中，ρ′=(ρ-ρmin)/(ρmax-ρmin)，δ′=(δ-δmin)/(δmax-δmin)。
在p=2%的情況下，以局部密度ρi為橫軸，距離δi為縱軸繪制Aggregation數據集的決策圖，如圖3(a)所示。人工選擇聚類中心時通常選擇決策圖右上角同時具有高ρ值和高δ值的樣本點作為聚類中心，對于這樣的樣本點來說，其γ值通常也相對較大，因此可將γ值作為一種選擇聚類中心的指標，γ圖如圖3(b)所示。根據文獻[1]可知，對于隨機分布的樣本點，簇中心權值γ近似服從冪律分布(power-law distribution)。由圖4可以看出，Aggregation數據集γ值的經驗分布與冪律分布的累積分布函數(CDF)基本吻合。
圖3 Aggregation數據集的決策圖和γ圖
圖4 Aggregation數據集γ值的經驗分布與冪律分布的累積分布函數
定義2 冪律分布的概率密度函數(PDF)
(6)
其中，α是冪律分布中的尺度參數，xmin是數據集的冪律下界。根據文獻[12]，一般情況下隨機變量中只有大于某個冪律下界xmin的尾部數據服從冪律分布。
定義3 冪律分布的累積分布函數(CDF)
(7)
定義4 Kolmogorov-Smirnov統計量(K-S statistic)
(8)
其中，S(X) 是x≥xmin的數據的CDF，F(X) 是最適合x≥xmin的冪律模型的CDF。
定義5 冪律分布尺度參數α的極大似然估計
(9)
定義6 生成冪律分布隨機數
(10)
其中，r是[0，1]區間上均勻分布的隨機數。
為了實現自動選擇聚類中心的目的，首先計算數據集的簇中心權值γ并擬合最優的xmin和α值，然后根據最優參數值生成符合冪律分布的隨機數，從而計算冪律分布的q分位數，選擇γ值大于所得q分位數的樣本點作為潛在聚類中心，獲得潛在聚類中心集合C={c1，c2，…，cn}， 然后進一步篩選出樣本點間距離dci，cj
圖5 Aggregation數據集自動選擇的聚類中心
2.2 簇合并策略
當一個簇中存在兩個或多個密度峰值時，使用DPC算法可能會選擇兩個或多個聚類中心，導致過度劃分的情況。如圖5所示，根據2.1節提出的自動選擇聚類中心策略為Aggregation數據集選擇了10個聚類中心，以此進行聚類并分配剩余樣本點，聚類結果如圖6(a)所示，圖中不同顏色和形狀的點表示不同的簇，“+”表示各簇中心點，黑色點表示噪聲點。可以明顯看出，聚類結果與圖6(b)所示的Aggregation數據集的真實分類標簽不符，其中有兩個簇存在被誤分為多個簇的情況。為了提高聚類的準確度，需要進一步進行簇合并。
圖6 Aggregation數據集初步聚類結果和真實分類標簽
聚類的目的是使同一簇內相似程度高而不同簇間相似程度低。基于這個基本要求，可以認為兩個相鄰簇間不應該存在相交的邊界區域，而當兩個相鄰簇的邊界區域存在大量樣本點時，則認為這兩個相鄰簇具有一定的相似性，應該將其合并。因此本節考慮根據兩個相鄰簇的簇間邊界密度和簇平均密度構造簇合并規則[13]。為了便于闡述簇合并規則，首先提出以下基本定義：
定義7 簇間邊界區域
Ctwo_bord(i，j)={i∈Ci，j∈Cj，dij≤dc}
(11)
其中，簇Ci，Cj∈，i≠j，={C1，C2，…，Ck} 為聚類所得的簇劃分。
定義8 簇間邊界密度
(12)
其中，Nij表示簇i和簇j的邊界區域Ctwo_bord(i，j) 中樣本點的個數。
定義9 簇間邊界比重
(13)
其中，|Ci| 和 |Cj| 分別為簇i和簇j中樣本點個數。
定義10 簇平均密度
(14)
其中，Ci_core和Cj_core分別為簇i和簇j核心點集合，|Ci_core| 和 |Cj_core| 分別為簇i和簇j的核心點個數。
定義11 簇合并規則。根據兩個相鄰簇的簇間邊界密度和簇平均密度構造簇合并規則，若簇i和簇j的簇間邊界密度和簇平均密度滿足簇間邊界比重wtwo_bord(i，j)>0.3且ρtwo_bord(Ci，Cj)>wtwo_bord(i，j)×ρtwo_core(Ci，Cj)， 則認為兩相鄰簇間相似度較高，可以將簇i和簇j進行合并。
如圖7(a)所示，左上角的簇被劃分為兩個簇，下方中間的簇被劃分為3個簇。根據定義11提出的簇合并規則處理Aggregation數據集的初步聚類結果，將相似程度較高的簇合并，結果如圖7(b)所示。可以看出，根據簇合并規則合并后，圖7(a)左上角的兩個簇合并為一個簇，下方中間的3個簇合并為一個簇，則合并后的聚類結果將數據集分為7個簇，基本符合真實分類標簽，提高了聚類精度。
圖7 Aggregation數據集初步聚類結果和合并聚類結果
2.3 改進輪廓系數
輪廓系數作為聚類算法中一種常用的內部評價指標，不需要考慮數據集的真實標簽，僅通過考察簇的緊湊情況和分離情況來評估聚類結果的質量。但是傳統的輪廓系數只考慮聚類所劃分的簇中所有樣本點，而沒有考慮各簇中的光暈點，不太適合評價DPC算法的結果，因此本節中提出了一種結合簇核心點和光暈點改進的輪廓系數。
定義12 輪廓系數(silhouette coefficient，sil)[14]。對于樣本點o∈Ci(1≤i≤k)， 定義a(o) 為點o與點o所屬簇的其它樣本點之間的平均距離，反映o所屬簇的緊湊程度；定義b(o) 為點o到不包含點o的所有簇樣本點的最小平均距離，反映點o與其它簇的分離程度；定義樣本點o的輪廓系數為
(15)
定義13 改進輪廓系數(improved silhouette coef-ficient，isil)。對于樣本點o∈Ci_core(1≤i≤k)， 定義a(o) 為點o與點o所屬簇的其它核心點之間的平均距離；定義b(o) 為點o到不包含點o的所有簇核心點的最小平均距離；定義c(o) 為點o與點o所屬簇的光暈點之間的平均距離。定義改進輪廓系數isil(o) 以及a(o)，b(o)，c(o) 為
(16)
(17)
其中，wc(i)=|Ci_core|/|Ci| 表示簇內核心點占簇內樣本點總數的比例，wh(i)=|Ci_halo|/|Ci| 表示簇內光暈點占簇內樣本點總數的比例，W表示數據集總體光暈點數占總體樣本點數的比例。改進輪廓系數isil(o) 結合了簇核心點和噪聲點的距離信息，其數值越接近1，說明簇內越緊湊且與其它簇越分離，則聚類效果越好。
2.4 基于人工魚群的自適應密度峰值聚類算法
在DPC算法中通常選取距離dij前1%～2%的值作為截斷距離dc的取值，但在實際處理一些真實數據集時常常難以根據人為經驗確定dc的取值，不同的dc取值會獲得不同的聚類結果。本文提出了基于人工魚群的自適應密度峰值聚類算法(AFSADPC)，以改進輪廓系數isil為目標函數，利用人工魚群算法尋找使改進輪廓系數指標達到最大值時的最優截斷距離dc。 算法步驟如下：
輸入：數據集X={x1，x2，…，xn}
過程：
(1)計算數據集X任意兩點之間的歐式距離dij， 得到兩兩樣本點之間所有距離集合D；
(2)對人工魚群算法進行初始化設置，包括種群規模X、 人工魚的視野范圍Visual、 步長Step、 擁擠度因子δ、 重復次數Try_number和最大迭代次數MAXGEN， 并根據式(3)選擇p=0-5%作為截斷距離dc的取值范圍；
(3)根據式(2)和式(4)分別計算各樣本點的局部密度ρi和距離δi；
(4)根據2.1節給出的自動選擇聚類中心策略，將γ值大于冪律分布上分位數的樣本點作為聚類中心，然后按照密度大小將剩余點分配到密度較高的最近鄰所屬簇；
(5)根據2.2節給出的簇間合并規則對相似度較高的相鄰簇進行簇合并；
(6)找出每個簇的核心點和光暈點，根據式(16)計算聚類結果的改進輪廓系數值；
(7)利用人工魚群算法重復步驟(3)～(6)，更新并尋找使改進輪廓系數指標達到最大值時的最優截斷距離dc；
(8)若達到最大迭代次數MAXGEN或最優解在誤差范圍內，則結束迭代并輸出聚類結果；否則跳轉至步驟(3)繼續尋優。
2.5 復雜度分析
對于樣本量為n的數據集，AFSADPC算法的時間復雜度主要由以下兩個部分組成：
(1)DPC部分：①計算樣本點間距離矩陣的時間復雜度為O(n2)； ②計算各樣本點局部密度ρi和距離δi的時間復雜度為O(n2)； ③在自動選擇聚類中心時計算上分位數值的時間復雜度為O(n)； ④在進行簇合并時的時間復雜度為O(n2)； ⑤計算輪廓系數的時間復雜度為O(n2)。 因此，DPC部分的時間復雜度為O(n2)；
(2)AFSA部分：假設人工魚群體大小為m， 重復次數為T， 最大迭代次數為I， ①由于在計算食物濃度時將調用改進的DPC算法，則計算食物濃度的時間復雜度為O(m×n2)； ②執行聚群行為和追尾行為的時間復雜度為O(m2×n2)； ③執行覓食行為的時間復雜度為O(T×m×n2)。 因此，經過I次迭代后，AFSADPC算法的時間復雜度為O(I×m2×n2)， 由于I和m均為常數，因此AFSADPC算法時間復雜度為O(n2)， 但迭代次數I和人工魚群體大小m將會影響運行時間。
3 實驗結果與分析
3.1 評價指標
為了驗證本文提出的AFSADPC算法的有效性，本節選取了6個合成數據集和6個真實數據集進行實驗，并且選取了原始DPC算法、DPC-KNN算法、DBSCAN算法、k-means算法和AP算法與本文提出的AFSADPC算法進行對比。其中，AFSADPC算法、DPC算法、DPC-KNN算法和k-means算法在MatlabR2017a上編寫相關代碼進行實驗，DBSCAN算法和AP算法使用Python的sklearn-library庫進行實驗。實驗環境為Windows10系統，處理器為Intel(R) Core(TM)i5-7200U CPU @2.50 GHz，內存為8.00 GB。
現針對上述聚類算法的參數設置做如下說明：
(1)AFSADPC算法中設置人工魚群規模X=10、 人工魚的視野范圍Visual=1、 步長Step=0.7、 擁擠度因子δ=1、 重復次數Try_number=5、 最大迭代次數MAXGEN=5；
(2)根據式(3)計算DPC算法中截斷距離dc時將比例p設置為2%，并根據決策圖人工選擇聚類中心；
(3)DPC-KNN算法在實驗中取局部最優的結果，其中參數K∈{3，6，9，12，15}；
(4)DBSCAN算法中實驗中取局部最優的結果，其中參數ε∈{0.02，0.04，…，0.08，1}， 參數MinPts∈{2，3，…，20}；
(5)將k-means算法中的參數k設置為數據集真實標簽的聚類數；
(6)AP算法的參數為程序中的默認參數。
本文采用以下3個聚類算法中常用的外部評價指標來評估聚類結果。
(1)調整蘭德系數(adjusted Rand index，ARI)
蘭德系數(Rand index，RI)計算決策正確的比率，其表達式為
(18)
調整蘭德系數ARI提升了蘭德系數RI的區分度，其表達式為
(19)
其中，E(RI) 是RI的數學期望。ARI的取值范圍為[-1，1]，越接近1意味著聚類結果越接近真實標簽。
(2)調整互信息(adjusted mutual information，AMI)
互信息(mutual information，MI)利用數據的信息熵，其表達式為
(20)
其中，|U| 是真實標簽的簇數，|V| 是聚類結果的簇數，N是數據集的樣本點總數，ni是真實標簽中簇i的點個數，nj是聚類結果中簇j的點個數，ni，j是真實標簽中屬于簇i且聚類結果中屬于簇j的點個數。
調整互信息AMI提升了互信息MI的區分度，其表達式為
(21)
(3)Fowlkes-Mallows指數(Fowlkes-Mallows index，FMI)
FMI是成對精度和召回率的幾何平均值，其表達式為
(22)
3.2 合成數據集實驗
為了驗證本文提出的AFSADPC算法的有效性，本節選取了6個二維合成數據集進行聚類，數據集基本信息見表1。
表1 合成數據集基本信息
對表1列出的6個合成數據集分別使用AFSADPC算法和其它對比算法對其進行聚類。圖8是DPC算法(p=2%)和AFSADPC算法在以上6個合成數據集上聚類效果的對比圖，其中圖8(a)～圖8(f)是DPC算法聚類結果圖，圖8(g)～圖8(l)是AFSADPC算法聚類結果圖，圖中不同顏色和形狀的點表示不同的簇，“+”表示各簇中心點，黑色點表示噪聲點。如圖8所示，DPC算法(p=2%)在Aggregation數據集和Flame數據集上的聚類結果并不準確，都存在將一個簇錯誤劃分為兩個簇的情況；而在D31數據集上，DPC算法雖然識別出了正確的聚類中心和聚類數，但是其聚類結果中存在大量的噪聲點。相比之下，AFSADPC算法在Aggregation、Flame數據集上均有較為良好的表現，并且在D31數據集上不存在大量噪聲點，但在Compound數據集和Pathbased數據集上同樣沒有給出正確的聚類結果。另外，根據AFSADPC算法尋優得到的最優截斷距離dc在Aggregation、D31、Flame、Compound數據集上與默認參數條件下的DPC算法dc值存在很大差異，說明dc的取值對聚類結果影響很大，合適的dc取值將會給聚類效果帶來很大的提升。
圖8 DPC算法與AFSADPC算法在合成數據集上的聚類結果
為了更客觀地對比6種算法的聚類效果，表2列出了各算法在各數據集上的聚類評價指標ARI、AMI、FMI值和聚類數，并加粗相對最優指標值。從聚類評價指標值上來看，在Aggregation、D31、R15和Flame這4個數據集上AFSADPC算法均優于其它對比算法，可以認為該算法有著更好的聚類效果，但在Compound和Pathbased數據集上無法識別出正確的聚類結果，說明AFSADPC算法在處理同時擁有環形簇和塊狀簇或者密度分布不均的數據集時仍需進一步改進，如圖8(l)所示，雖然AFSADPC算法識別出3個聚類中心，與真實標簽聚類數相符，但由于剩余點最近鄰分配的方式導致外圈的環形簇有一部分被分到了中間兩個塊狀簇中，因此聚類結果不理想。
表2 各算法在合成數據集上的評價指標值對比
3.3 真實數據集實驗
為了驗證本文提出的AFSADPC算法的有效性，本節從UCI數據庫中選取6個真實數據集進行聚類，這些真實數據集的基本信息見表3。由于真實數據集維度較高，不便于在二維平面繪制聚類圖，在此僅對比各算法的ARI、AMI、FMI值。
表3 真實數據集基本信息
對表3列出的6個真實數據集分別使用AFSADPC算法和其它對比算法對其進行聚類。表4列出了各算法在各數據集上的聚類評價指標ARI、AMI、FMI值和聚類數，并加粗相對最優指標值。從表4的聚類評價指標值上來看，在Ecoli、optdigits和vertebral這3個數據集上AFSADPC算法均優于其它對比算法，可以認為該算法有著更好的聚類效果。而在seeds、waveform和wifi這3個數據集上，雖然AFSADPC算法的聚類評價指標值略低于對比算法，但它能夠識別出這3個數據集正確的聚類數，且其評價指標與最優值相差不超過0.1，也獲得了較好的聚類結果。
4 結束語
針對密度峰值聚類算法需要人為指定截斷距離dc、 根據決策圖人工選擇聚類中心、對一個簇中存在多密度峰值的數據無法準確聚類的問題，本文提出了基于人工魚群的自適應密度峰值聚類算法(AFSADPC)，將簇中心權值γ大于冪律分布上分位數的樣本點作為聚類中心，根據兩個相鄰簇的簇間邊界區域密度與簇平均密度構造簇間合并規則，并且利用人工魚群算法尋找使改進輪廓系數指標達到最大值時的最優截斷距離dc。 在合成數據集和UCI真實數據集上的實驗結果表明，AFSADPC算法對DPC算法存在的部分缺陷進行改進，提高了DPC算法的聚類精度，其算法效果優于其它對比算法，但由于剩余點最近鄰分配的方式，AFSADPC算法在處理同時擁有環形簇和塊狀簇或者密度分布不均的數據集時仍需進一步改進。因此，下一步的研究工作主要在于如何改進對剩余點的分配策略和對不同形狀數據集的識別與聚類。
