何凱琳，張正軍+，位 雅，唐 莉

(1.南京理工大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，江蘇 南京 210094；2.景德鎮(zhèn)學(xué)院 信息工程學(xué)院，江西 景德鎮(zhèn) 333000)

0 引 言

聚類分析作為一種重要的數(shù)據(jù)挖掘技術(shù)，能夠在無監(jiān)督的條件下探索數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律。密度峰值聚類算法(clustering by fast search and find of density peaks algorithm，DPC)[1，2]是從樣本點密度的角度出發(fā)，通過快速搜索找到密度峰值作為聚類中心來進(jìn)行聚類，能夠快速地識別任意形狀數(shù)據(jù)集的密度峰值點，直觀地找到聚類中心，因而受到了廣泛的關(guān)注。

然而，DPC算法也存在不足，如需要人為指定截斷距離dc和聚類中心、對存在多密度峰值的數(shù)據(jù)無法準(zhǔn)確聚類等。國內(nèi)外專家學(xué)者已提出了一些優(yōu)化算法。王洋等[3]選擇基尼指數(shù)達(dá)到最小值時最優(yōu)影響因子σ的值作為dc的取值。Ding等[4]構(gòu)造了近似遵循GEV分布的判斷指數(shù)，將判斷指數(shù)值大于GEV上分位數(shù)的樣本點作為聚類中心。Yang等[5]構(gòu)造加權(quán)完全圖，利用拉普拉斯中心性取代局部密度評價網(wǎng)絡(luò)節(jié)點的局部重要性。章曼等[6]利用非參數(shù)核密度估計計算局部密度，并通過自適應(yīng)可達(dá)距離分配樣本點。還有一些學(xué)者將樣本點的近鄰信息引入到局部密度度量當(dāng)中，杜明晶等[7]使用樣本點xi的k個最近鄰kNN(xi) 信息計算局部密度。覃華等[8]基于最優(yōu)Oracle逼近構(gòu)造馬氏距離，結(jié)合k近鄰算法實現(xiàn)密度最優(yōu)估計。湯鑫瑤等[9]根據(jù)樣本點的自然最近鄰計算局部密度，并設(shè)計了兩步分配策略。

為了進(jìn)一步增強DPC算法的自適應(yīng)性，針對密度峰值聚類算法需要人為指定截斷距離dc、 根據(jù)決策圖人工選擇聚類中心、對一個簇中存在多密度峰值的數(shù)據(jù)無法準(zhǔn)確聚類的問題，本文提出了基于人工魚群的自適應(yīng)密度峰值聚類算法(adaptive density peaks clustering algorithm based on artificial fish swarm，AFSADPC)，將簇中心權(quán)值γ大于冪律分布上分位數(shù)的樣本點作為聚類中心，根據(jù)兩個相鄰簇的簇間邊界區(qū)域密度與簇平均密度構(gòu)造簇間合并規(guī)則，并且利用人工魚群算法尋找使改進(jìn)輪廓系數(shù)指標(biāo)達(dá)到最大值時的最優(yōu)截斷距離dc， 從而進(jìn)行密度峰值聚類。

1 相關(guān)知識

1.1 密度峰值聚類算法與分析

1.1.1 密度峰值聚類算法的基本概念

DPC算法識別聚類中心主要基于以下假設(shè)：①聚類中心的局部密度高于其周圍樣本點；②聚類中心距離密度更高樣本點較遠(yuǎn)。設(shè)有數(shù)據(jù)集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)

對比兩種定義可知，截斷核為離散值，而高斯核為連續(xù)值，采用高斯核函數(shù)來估計不同樣本點的局部密度得到相同值的概率更小，因此通常選擇高斯核的計算方式來計算局部密度ρi， 但無論選擇哪種方式計算ρi都與截斷距離dc有關(guān)。

dc的計算方式如下

dc=dPN

(3)

點xi與密度更高樣本點間距離δi的計算方式如下

(4)

即對于非密度最高的樣本點xi，δi是計算點xi和其它密度更高樣本點之間的最小距離；對于密度最高的點xi，δi是點xi與最遠(yuǎn)樣本點之間的距離。

計算出上述參數(shù)后，以ρi為橫軸，δi為縱軸繪制決策圖，從決策圖中選擇ρi較大且δi也較大的樣本點作為聚類中心，然后按照密度大小將剩余點分配到密度較高的最近鄰所屬簇。若兩個屬于不同簇的樣本點間距離小于截斷距離dc， 則被稱為其所屬簇的邊界點。簇的邊界區(qū)域是該簇邊界點的集合，若簇中某樣本點的局部密度大于簇邊界區(qū)域內(nèi)的局部密度最大值，則該點被稱為所屬簇的核心點，其余點則被稱為光暈點。

1.1.2 密度峰值聚類算法的缺陷

本文主要針對DPC算法以下缺陷進(jìn)行研究。

(1)dc取值問題。在實際處理數(shù)據(jù)時通常難以根據(jù)經(jīng)驗確定截斷距離dc， 不同的dc取值會獲得不同的聚類結(jié)果，如圖1所示，在p=1%和p=2%的情況下DPC算法都能識別出Spiral數(shù)據(jù)集的聚類中心，但只有在p=2%的情況下得到了正確的聚類結(jié)果；

圖1 不同dc下DPC算法在Spiral數(shù)據(jù)集上的聚類結(jié)果

(2)聚類中心選擇問題。DPC算法根據(jù)決策圖人工選擇聚類中心，容易受主觀因素影響，且對于某些復(fù)雜的決策圖難以找到合理的聚類中心，如圖2(a)所示，根據(jù)Aggregation數(shù)據(jù)集的決策圖主觀判斷可能選取3個、7個或10個聚類中心，錯誤選擇非聚類中心進(jìn)行聚類將會引起樣本點分配錯誤，影響聚類結(jié)果；

圖2 Aggregation數(shù)據(jù)集的決策圖和聚類結(jié)果(DPC，p=2%)

(3)多密度峰值問題。當(dāng)數(shù)據(jù)集的一個簇中存在兩個或者多個的密度峰值時，DPC算法會選擇多個聚類中心從而誤將一個簇劃分成兩個或多個簇，造成過度劃分的情況，如圖2(b)所示，存在將一個簇錯誤劃分為兩個簇的情況。

1.2 人工魚群算法的基本概念

受到自然界中某些動物群體行為的啟發(fā)，學(xué)者們提出了群智能優(yōu)化算法，通過模擬生物群體行為來實現(xiàn)優(yōu)化。人工魚群算法(artificial fish swarm algorithm，AFSA)是一種基于魚群行為的隨機搜索優(yōu)化算法[10，11]，采用自下而上的尋優(yōu)策略，通過魚群中各個體的局部尋優(yōu)實現(xiàn)全局尋優(yōu)，具有并行性、簡單性、全局性、快速性和跟蹤性等特點，廣泛應(yīng)用于通信系統(tǒng)、圖像處理、機器學(xué)習(xí)等領(lǐng)域。

人工魚的狀態(tài)定義為X={X1，X2，…，Xn}， 算法的參數(shù)有人工魚的視野范圍Visual、 步長Step、 擁擠度因子δ和重復(fù)次數(shù)Try_number。 設(shè)人工魚當(dāng)前狀態(tài)為Xi， 其食物濃度(目標(biāo)函數(shù)值)為Yi=f(Xi)。 人工魚群算法主要通過模擬魚群的四大基本行為實現(xiàn)全局尋優(yōu)：

2 基于人工魚群算法改進(jìn)的密度峰值聚類算法

2.1 自動選擇聚類中心策略

在DPC算法中需要在決策圖中人工選擇聚類中心，容易受到主觀因素影響，且對于某些復(fù)雜的決策圖難以找到合理的聚類中心，根據(jù)非聚類中心進(jìn)行聚類將會進(jìn)一步引起樣本點分配錯誤，從而得到錯誤的聚類結(jié)果。針對此缺陷，本節(jié)提出一種自動選擇聚類中心的策略，綜合考慮樣本點的ρ值和δ值構(gòu)造簇中心權(quán)值γ， 將γ值大于冪律分布上分位數(shù)的樣本點作為聚類中心。

定義1 簇中心權(quán)值。為了便于描述同時具有高ρ值和高δ值的樣本點，對ρ值和δ值進(jìn)行歸一化處理，并綜合考慮這兩個值構(gòu)造簇中心權(quán)值γ

γ=ρ′·δ′

(5)

其中，ρ′=(ρ-ρmin)/(ρmax-ρmin)，δ′=(δ-δmin)/(δmax-δmin)。

在p=2%的情況下，以局部密度ρi為橫軸，距離δi為縱軸繪制Aggregation數(shù)據(jù)集的決策圖，如圖3(a)所示。人工選擇聚類中心時通常選擇決策圖右上角同時具有高ρ值和高δ值的樣本點作為聚類中心，對于這樣的樣本點來說，其γ值通常也相對較大，因此可將γ值作為一種選擇聚類中心的指標(biāo)，γ圖如圖3(b)所示。根據(jù)文獻(xiàn)[1]可知，對于隨機分布的樣本點，簇中心權(quán)值γ近似服從冪律分布(power-law distribution)。由圖4可以看出，Aggregation數(shù)據(jù)集γ值的經(jīng)驗分布與冪律分布的累積分布函數(shù)(CDF)基本吻合。

圖3 Aggregation數(shù)據(jù)集的決策圖和γ圖

圖4 Aggregation數(shù)據(jù)集γ值的經(jīng)驗分布與冪律分布的累積分布函數(shù)

定義2 冪律分布的概率密度函數(shù)(PDF)

(6)

其中，α是冪律分布中的尺度參數(shù)，xmin是數(shù)據(jù)集的冪律下界。根據(jù)文獻(xiàn)[12]，一般情況下隨機變量中只有大于某個冪律下界xmin的尾部數(shù)據(jù)服從冪律分布。

定義3 冪律分布的累積分布函數(shù)(CDF)

(7)

定義4 Kolmogorov-Smirnov統(tǒng)計量(K-S statistic)

(8)

其中，S(X) 是x≥xmin的數(shù)據(jù)的CDF，F(xiàn)(X) 是最適合x≥xmin的冪律模型的CDF。

定義5 冪律分布尺度參數(shù)α的極大似然估計

(9)

定義6 生成冪律分布隨機數(shù)

(10)

其中，r是[0，1]區(qū)間上均勻分布的隨機數(shù)。

為了實現(xiàn)自動選擇聚類中心的目的，首先計算數(shù)據(jù)集的簇中心權(quán)值γ并擬合最優(yōu)的xmin和α值，然后根據(jù)最優(yōu)參數(shù)值生成符合冪律分布的隨機數(shù)，從而計算冪律分布的q分位數(shù)，選擇γ值大于所得q分位數(shù)的樣本點作為潛在聚類中心，獲得潛在聚類中心集合C={c1，c2，…，cn}， 然后進(jìn)一步篩選出樣本點間距離dci，cjρcj， 則從潛在聚類中心集合中剔除密度較小的cj， 僅選擇密度較大的ci作為聚類中心。本文上分位數(shù)q取0.99，根據(jù)上述策略，Aggregation數(shù)據(jù)集自動選擇聚類中心結(jié)果如圖5所示，不同顏色樣本點表示不同的聚類中心，黑色樣本點表示非聚類中心?？梢钥闯?，所選擇的γ值較大的聚類中心正是決策圖右上角同時具有高ρ值和高δ值的樣本點。

圖5 Aggregation數(shù)據(jù)集自動選擇的聚類中心

2.2 簇合并策略

當(dāng)一個簇中存在兩個或多個密度峰值時，使用DPC算法可能會選擇兩個或多個聚類中心，導(dǎo)致過度劃分的情況。如圖5所示，根據(jù)2.1節(jié)提出的自動選擇聚類中心策略為Aggregation數(shù)據(jù)集選擇了10個聚類中心，以此進(jìn)行聚類并分配剩余樣本點，聚類結(jié)果如圖6(a)所示，圖中不同顏色和形狀的點表示不同的簇，“+”表示各簇中心點，黑色點表示噪聲點?？梢悦黠@看出，聚類結(jié)果與圖6(b)所示的Aggregation數(shù)據(jù)集的真實分類標(biāo)簽不符，其中有兩個簇存在被誤分為多個簇的情況。為了提高聚類的準(zhǔn)確度，需要進(jìn)一步進(jìn)行簇合并。

圖6 Aggregation數(shù)據(jù)集初步聚類結(jié)果和真實分類標(biāo)簽

聚類的目的是使同一簇內(nèi)相似程度高而不同簇間相似程度低?；谶@個基本要求，可以認(rèn)為兩個相鄰簇間不應(yīng)該存在相交的邊界區(qū)域，而當(dāng)兩個相鄰簇的邊界區(qū)域存在大量樣本點時，則認(rèn)為這兩個相鄰簇具有一定的相似性，應(yīng)該將其合并。因此本節(jié)考慮根據(jù)兩個相鄰簇的簇間邊界密度和簇平均密度構(gòu)造簇合并規(guī)則[13]。為了便于闡述簇合并規(guī)則，首先提出以下基本定義：

定義7 簇間邊界區(qū)域

Ctwo_bord(i，j)={i∈Ci，j∈Cj，dij≤dc}

(11)

其中，簇Ci，Cj∈，i≠j，={C1，C2，…，Ck} 為聚類所得的簇劃分。

定義8 簇間邊界密度

(12)

其中，Nij表示簇i和簇j的邊界區(qū)域Ctwo_bord(i，j) 中樣本點的個數(shù)。

定義9 簇間邊界比重

(13)

其中，|Ci| 和 |Cj| 分別為簇i和簇j中樣本點個數(shù)。

定義10 簇平均密度

(14)

其中，Ci_core和Cj_core分別為簇i和簇j核心點集合，|Ci_core| 和 |Cj_core| 分別為簇i和簇j的核心點個數(shù)。

定義11 簇合并規(guī)則。根據(jù)兩個相鄰簇的簇間邊界密度和簇平均密度構(gòu)造簇合并規(guī)則，若簇i和簇j的簇間邊界密度和簇平均密度滿足簇間邊界比重wtwo_bord(i，j)>0.3且ρtwo_bord(Ci，Cj)>wtwo_bord(i，j)×ρtwo_core(Ci，Cj)， 則認(rèn)為兩相鄰簇間相似度較高，可以將簇i和簇j進(jìn)行合并。

如圖7(a)所示，左上角的簇被劃分為兩個簇，下方中間的簇被劃分為3個簇。根據(jù)定義11提出的簇合并規(guī)則處理Aggregation數(shù)據(jù)集的初步聚類結(jié)果，將相似程度較高的簇合并，結(jié)果如圖7(b)所示?？梢钥闯觯鶕?jù)簇合并規(guī)則合并后，圖7(a)左上角的兩個簇合并為一個簇，下方中間的3個簇合并為一個簇，則合并后的聚類結(jié)果將數(shù)據(jù)集分為7個簇，基本符合真實分類標(biāo)簽，提高了聚類精度。

圖7 Aggregation數(shù)據(jù)集初步聚類結(jié)果和合并聚類結(jié)果

2.3 改進(jìn)輪廓系數(shù)

輪廓系數(shù)作為聚類算法中一種常用的內(nèi)部評價指標(biāo)，不需要考慮數(shù)據(jù)集的真實標(biāo)簽，僅通過考察簇的緊湊情況和分離情況來評估聚類結(jié)果的質(zhì)量。但是傳統(tǒng)的輪廓系數(shù)只考慮聚類所劃分的簇中所有樣本點，而沒有考慮各簇中的光暈點，不太適合評價DPC算法的結(jié)果，因此本節(jié)中提出了一種結(jié)合簇核心點和光暈點改進(jìn)的輪廓系數(shù)。

定義12 輪廓系數(shù)(silhouette coefficient，sil)[14]。對于樣本點o∈Ci(1≤i≤k)， 定義a(o) 為點o與點o所屬簇的其它樣本點之間的平均距離，反映o所屬簇的緊湊程度；定義b(o) 為點o到不包含點o的所有簇樣本點的最小平均距離，反映點o與其它簇的分離程度；定義樣本點o的輪廓系數(shù)為

(15)

定義13 改進(jìn)輪廓系數(shù)(improved silhouette coef-ficient，isil)。對于樣本點o∈Ci_core(1≤i≤k)， 定義a(o) 為點o與點o所屬簇的其它核心點之間的平均距離；定義b(o) 為點o到不包含點o的所有簇核心點的最小平均距離；定義c(o) 為點o與點o所屬簇的光暈點之間的平均距離。定義改進(jìn)輪廓系數(shù)isil(o) 以及a(o)，b(o)，c(o) 為

(16)

(17)

其中，wc(i)=|Ci_core|/|Ci| 表示簇內(nèi)核心點占簇內(nèi)樣本點總數(shù)的比例，wh(i)=|Ci_halo|/|Ci| 表示簇內(nèi)光暈點占簇內(nèi)樣本點總數(shù)的比例，W表示數(shù)據(jù)集總體光暈點數(shù)占總體樣本點數(shù)的比例。改進(jìn)輪廓系數(shù)isil(o) 結(jié)合了簇核心點和噪聲點的距離信息，其數(shù)值越接近1，說明簇內(nèi)越緊湊且與其它簇越分離，則聚類效果越好。

2.4 基于人工魚群的自適應(yīng)密度峰值聚類算法

在DPC算法中通常選取距離dij前1%～2%的值作為截斷距離dc的取值，但在實際處理一些真實數(shù)據(jù)集時常常難以根據(jù)人為經(jīng)驗確定dc的取值，不同的dc取值會獲得不同的聚類結(jié)果。本文提出了基于人工魚群的自適應(yīng)密度峰值聚類算法(AFSADPC)，以改進(jìn)輪廓系數(shù)isil為目標(biāo)函數(shù)，利用人工魚群算法尋找使改進(jìn)輪廓系數(shù)指標(biāo)達(dá)到最大值時的最優(yōu)截斷距離dc。 算法步驟如下：

輸入：數(shù)據(jù)集X={x1，x2，…，xn}

過程：

(1)計算數(shù)據(jù)集X任意兩點之間的歐式距離dij， 得到兩兩樣本點之間所有距離集合D；

(2)對人工魚群算法進(jìn)行初始化設(shè)置，包括種群規(guī)模X、 人工魚的視野范圍Visual、 步長Step、 擁擠度因子δ、 重復(fù)次數(shù)Try_number和最大迭代次數(shù)MAXGEN， 并根據(jù)式(3)選擇p=0-5%作為截斷距離dc的取值范圍；

(3)根據(jù)式(2)和式(4)分別計算各樣本點的局部密度ρi和距離δi；

(4)根據(jù)2.1節(jié)給出的自動選擇聚類中心策略，將γ值大于冪律分布上分位數(shù)的樣本點作為聚類中心，然后按照密度大小將剩余點分配到密度較高的最近鄰所屬簇；

(5)根據(jù)2.2節(jié)給出的簇間合并規(guī)則對相似度較高的相鄰簇進(jìn)行簇合并；

(6)找出每個簇的核心點和光暈點，根據(jù)式(16)計算聚類結(jié)果的改進(jìn)輪廓系數(shù)值；

(7)利用人工魚群算法重復(fù)步驟(3)～(6)，更新并尋找使改進(jìn)輪廓系數(shù)指標(biāo)達(dá)到最大值時的最優(yōu)截斷距離dc；

(8)若達(dá)到最大迭代次數(shù)MAXGEN或最優(yōu)解在誤差范圍內(nèi)，則結(jié)束迭代并輸出聚類結(jié)果；否則跳轉(zhuǎn)至步驟(3)繼續(xù)尋優(yōu)。

2.5 復(fù)雜度分析

對于樣本量為n的數(shù)據(jù)集，AFSADPC算法的時間復(fù)雜度主要由以下兩個部分組成：

(1)DPC部分：①計算樣本點間距離矩陣的時間復(fù)雜度為O(n2)； ②計算各樣本點局部密度ρi和距離δi的時間復(fù)雜度為O(n2)； ③在自動選擇聚類中心時計算上分位數(shù)值的時間復(fù)雜度為O(n)； ④在進(jìn)行簇合并時的時間復(fù)雜度為O(n2)； ⑤計算輪廓系數(shù)的時間復(fù)雜度為O(n2)。 因此，DPC部分的時間復(fù)雜度為O(n2)；

(2)AFSA部分：假設(shè)人工魚群體大小為m， 重復(fù)次數(shù)為T， 最大迭代次數(shù)為I， ①由于在計算食物濃度時將調(diào)用改進(jìn)的DPC算法，則計算食物濃度的時間復(fù)雜度為O(m×n2)； ②執(zhí)行聚群行為和追尾行為的時間復(fù)雜度為O(m2×n2)； ③執(zhí)行覓食行為的時間復(fù)雜度為O(T×m×n2)。 因此，經(jīng)過I次迭代后，AFSADPC算法的時間復(fù)雜度為O(I×m2×n2)， 由于I和m均為常數(shù)，因此AFSADPC算法時間復(fù)雜度為O(n2)， 但迭代次數(shù)I和人工魚群體大小m將會影響運行時間。

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

3.1 評價指標(biāo)

為了驗證本文提出的AFSADPC算法的有效性，本節(jié)選取了6個合成數(shù)據(jù)集和6個真實數(shù)據(jù)集進(jìn)行實驗，并且選取了原始DPC算法、DPC-KNN算法、DBSCAN算法、k-means算法和AP算法與本文提出的AFSADPC算法進(jìn)行對比。其中，AFSADPC算法、DPC算法、DPC-KNN算法和k-means算法在MatlabR2017a上編寫相關(guān)代碼進(jìn)行實驗，DBSCAN算法和AP算法使用Python的sklearn-library庫進(jìn)行實驗。實驗環(huán)境為Windows10系統(tǒng)，處理器為Intel(R) Core(TM)i5-7200U CPU @2.50 GHz，內(nèi)存為8.00 GB。

現(xiàn)針對上述聚類算法的參數(shù)設(shè)置做如下說明：

(1)AFSADPC算法中設(shè)置人工魚群規(guī)模X=10、 人工魚的視野范圍Visual=1、 步長Step=0.7、 擁擠度因子δ=1、 重復(fù)次數(shù)Try_number=5、 最大迭代次數(shù)MAXGEN=5；

(2)根據(jù)式(3)計算DPC算法中截斷距離dc時將比例p設(shè)置為2%，并根據(jù)決策圖人工選擇聚類中心；

(3)DPC-KNN算法在實驗中取局部最優(yōu)的結(jié)果，其中參數(shù)K∈{3，6，9，12，15}；

(4)DBSCAN算法中實驗中取局部最優(yōu)的結(jié)果，其中參數(shù)ε∈{0.02，0.04，…，0.08，1}， 參數(shù)MinPts∈{2，3，…，20}；

(5)將k-means算法中的參數(shù)k設(shè)置為數(shù)據(jù)集真實標(biāo)簽的聚類數(shù)；

(6)AP算法的參數(shù)為程序中的默認(rèn)參數(shù)。

本文采用以下3個聚類算法中常用的外部評價指標(biāo)來評估聚類結(jié)果。

(1)調(diào)整蘭德系數(shù)(adjusted Rand index，ARI)

蘭德系數(shù)(Rand index，RI)計算決策正確的比率，其表達(dá)式為

(18)

調(diào)整蘭德系數(shù)ARI提升了蘭德系數(shù)RI的區(qū)分度，其表達(dá)式為

(19)

其中，E(RI) 是RI的數(shù)學(xué)期望。ARI的取值范圍為[-1，1]，越接近1意味著聚類結(jié)果越接近真實標(biāo)簽。

(2)調(diào)整互信息(adjusted mutual information，AMI)

互信息(mutual information，MI)利用數(shù)據(jù)的信息熵，其表達(dá)式為

(20)

其中，|U| 是真實標(biāo)簽的簇數(shù)，|V| 是聚類結(jié)果的簇數(shù)，N是數(shù)據(jù)集的樣本點總數(shù)，ni是真實標(biāo)簽中簇i的點個數(shù)，nj是聚類結(jié)果中簇j的點個數(shù)，ni，j是真實標(biāo)簽中屬于簇i且聚類結(jié)果中屬于簇j的點個數(shù)。

調(diào)整互信息AMI提升了互信息MI的區(qū)分度，其表達(dá)式為

(21)

(3)Fowlkes-Mallows指數(shù)(Fowlkes-Mallows index，F(xiàn)MI)

FMI是成對精度和召回率的幾何平均值，其表達(dá)式為

(22)

3.2 合成數(shù)據(jù)集實驗

為了驗證本文提出的AFSADPC算法的有效性，本節(jié)選取了6個二維合成數(shù)據(jù)集進(jìn)行聚類，數(shù)據(jù)集基本信息見表1。

表1 合成數(shù)據(jù)集基本信息

對表1列出的6個合成數(shù)據(jù)集分別使用AFSADPC算法和其它對比算法對其進(jìn)行聚類。圖8是DPC算法(p=2%)和AFSADPC算法在以上6個合成數(shù)據(jù)集上聚類效果的對比圖，其中圖8(a)～圖8(f)是DPC算法聚類結(jié)果圖，圖8(g)～圖8(l)是AFSADPC算法聚類結(jié)果圖，圖中不同顏色和形狀的點表示不同的簇，“+”表示各簇中心點，黑色點表示噪聲點。如圖8所示，DPC算法(p=2%)在Aggregation數(shù)據(jù)集和Flame數(shù)據(jù)集上的聚類結(jié)果并不準(zhǔn)確，都存在將一個簇錯誤劃分為兩個簇的情況；而在D31數(shù)據(jù)集上，DPC算法雖然識別出了正確的聚類中心和聚類數(shù)，但是其聚類結(jié)果中存在大量的噪聲點。相比之下，AFSADPC算法在Aggregation、Flame數(shù)據(jù)集上均有較為良好的表現(xiàn)，并且在D31數(shù)據(jù)集上不存在大量噪聲點，但在Compound數(shù)據(jù)集和Pathbased數(shù)據(jù)集上同樣沒有給出正確的聚類結(jié)果。另外，根據(jù)AFSADPC算法尋優(yōu)得到的最優(yōu)截斷距離dc在Aggregation、D31、Flame、Compound數(shù)據(jù)集上與默認(rèn)參數(shù)條件下的DPC算法dc值存在很大差異，說明dc的取值對聚類結(jié)果影響很大，合適的dc取值將會給聚類效果帶來很大的提升。

圖8 DPC算法與AFSADPC算法在合成數(shù)據(jù)集上的聚類結(jié)果

為了更客觀地對比6種算法的聚類效果，表2列出了各算法在各數(shù)據(jù)集上的聚類評價指標(biāo)ARI、AMI、FMI值和聚類數(shù)，并加粗相對最優(yōu)指標(biāo)值。從聚類評價指標(biāo)值上來看，在Aggregation、D31、R15和Flame這4個數(shù)據(jù)集上AFSADPC算法均優(yōu)于其它對比算法，可以認(rèn)為該算法有著更好的聚類效果，但在Compound和Pathbased數(shù)據(jù)集上無法識別出正確的聚類結(jié)果，說明AFSADPC算法在處理同時擁有環(huán)形簇和塊狀簇或者密度分布不均的數(shù)據(jù)集時仍需進(jìn)一步改進(jìn)，如圖8(l)所示，雖然AFSADPC算法識別出3個聚類中心，與真實標(biāo)簽聚類數(shù)相符，但由于剩余點最近鄰分配的方式導(dǎo)致外圈的環(huán)形簇有一部分被分到了中間兩個塊狀簇中，因此聚類結(jié)果不理想。

表2 各算法在合成數(shù)據(jù)集上的評價指標(biāo)值對比

3.3 真實數(shù)據(jù)集實驗

為了驗證本文提出的AFSADPC算法的有效性，本節(jié)從UCI數(shù)據(jù)庫中選取6個真實數(shù)據(jù)集進(jìn)行聚類，這些真實數(shù)據(jù)集的基本信息見表3。由于真實數(shù)據(jù)集維度較高，不便于在二維平面繪制聚類圖，在此僅對比各算法的ARI、AMI、FMI值。

表3 真實數(shù)據(jù)集基本信息

對表3列出的6個真實數(shù)據(jù)集分別使用AFSADPC算法和其它對比算法對其進(jìn)行聚類。表4列出了各算法在各數(shù)據(jù)集上的聚類評價指標(biāo)ARI、AMI、FMI值和聚類數(shù)，并加粗相對最優(yōu)指標(biāo)值。從表4的聚類評價指標(biāo)值上來看，在Ecoli、optdigits和vertebral這3個數(shù)據(jù)集上AFSADPC算法均優(yōu)于其它對比算法，可以認(rèn)為該算法有著更好的聚類效果。而在seeds、waveform和wifi這3個數(shù)據(jù)集上，雖然AFSADPC算法的聚類評價指標(biāo)值略低于對比算法，但它能夠識別出這3個數(shù)據(jù)集正確的聚類數(shù)，且其評價指標(biāo)與最優(yōu)值相差不超過0.1，也獲得了較好的聚類結(jié)果。

4 結(jié)束語

針對密度峰值聚類算法需要人為指定截斷距離dc、 根據(jù)決策圖人工選擇聚類中心、對一個簇中存在多密度峰值的數(shù)據(jù)無法準(zhǔn)確聚類的問題，本文提出了基于人工魚群的自適應(yīng)密度峰值聚類算法(AFSADPC)，將簇中心權(quán)值γ大于冪律分布上分位數(shù)的樣本點作為聚類中心，根據(jù)兩個相鄰簇的簇間邊界區(qū)域密度與簇平均密度構(gòu)造簇間合并規(guī)則，并且利用人工魚群算法尋找使改進(jìn)輪廓系數(shù)指標(biāo)達(dá)到最大值時的最優(yōu)截斷距離dc。 在合成數(shù)據(jù)集和UCI真實數(shù)據(jù)集上的實驗結(jié)果表明，AFSADPC算法對DPC算法存在的部分缺陷進(jìn)行改進(jìn)，提高了DPC算法的聚類精度，其算法效果優(yōu)于其它對比算法，但由于剩余點最近鄰分配的方式，AFSADPC算法在處理同時擁有環(huán)形簇和塊狀簇或者密度分布不均的數(shù)據(jù)集時仍需進(jìn)一步改進(jìn)。因此，下一步的研究工作主要在于如何改進(jìn)對剩余點的分配策略和對不同形狀數(shù)據(jù)集的識別與聚類。