結(jié)合鯨魚優(yōu)化算法的自適應(yīng)密度峰值聚類算法

王芙銀，張德生，張 曉

西安理工大學(xué) 理學(xué)院，西安710054

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，隨之產(chǎn)生的數(shù)據(jù)也以驚人的速度增加，這些海量的數(shù)據(jù)包含著豐富的信息。人們的日?；顒?dòng)都可以在一定形式上量化為數(shù)據(jù)的方式，但這些數(shù)據(jù)通常是毫無規(guī)律、雜亂無章的，隨著時(shí)間的推移，這些數(shù)據(jù)的積累就更加龐大，大數(shù)據(jù)的時(shí)代也就應(yīng)運(yùn)而生。怎樣從這些數(shù)據(jù)中獲得有價(jià)值的信息就變成了當(dāng)今時(shí)代研究的熱點(diǎn)[1]。

聚類分析[2]在數(shù)據(jù)挖掘中扮演著重要的角色，它是無監(jiān)督機(jī)器學(xué)習(xí)的一種，在不需要先驗(yàn)知識(shí)的情況下，根據(jù)數(shù)據(jù)的分布，計(jì)算數(shù)據(jù)間的相似性，將數(shù)據(jù)劃分成不同的集合，成為類簇。同一類簇間的數(shù)據(jù)有著較高的相似性，不同類簇間的數(shù)據(jù)有著較低的相似性。按照數(shù)據(jù)分布方式以及算法原理，目前常見的聚類算法大體可分為：基于劃分的聚類、基于層次的聚類、基于密度的聚類[3-4]、基于網(wǎng)格的聚類及基于模型的聚類等[3]。其中，基于密度的聚類算法可以在不同數(shù)據(jù)中發(fā)現(xiàn)各種形狀及各種大小的簇，其思想是在選定較高密度點(diǎn)后，將周邊與高密度點(diǎn)相近的點(diǎn)聚集為一類。

2014 年意大利學(xué)者Rodriguez 和Laio 在Science雜志上提出了一種快速搜索發(fā)現(xiàn)密度峰值聚類算法（Clustering by fast search and find of density peaks），這是一種基于密度的聚類算法，簡稱密度峰聚類算法（Density Peaks Clustering algorithm，DPC）[5]。該算法不需要事先確定類簇的個(gè)數(shù)，在各種復(fù)雜的數(shù)據(jù)集中能有效識(shí)別出類簇，對噪聲點(diǎn)的識(shí)別也有一定的優(yōu)越性，且對于任意形狀的數(shù)據(jù)集都能達(dá)到很好的聚類效果，適用于大規(guī)模數(shù)據(jù)的聚類分析?；谶@些優(yōu)勢，DPC算法目前越來越多地被應(yīng)用于各個(gè)領(lǐng)域，其涉及的領(lǐng)域包括機(jī)器學(xué)習(xí)、模式識(shí)別、人工智能、圖像處理等多個(gè)方面[6]。

鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）[7]是Mirjalili等人于2016年所提出的一種新型元啟發(fā)式算法，與其他智能算法相比具有多方面的優(yōu)勢。例如，文獻(xiàn)[7]通過對29 個(gè)數(shù)值優(yōu)化問題和6 個(gè)工程優(yōu)化問題進(jìn)行測試，驗(yàn)證了WOA 算法比模擬退火算法和差分進(jìn)化算法等元啟發(fā)式算法具有更強(qiáng)的競爭力。另外，如文獻(xiàn)[8]所指出的那樣，與典型的群智能優(yōu)化算法相比，WOA 算法具有原理簡單、調(diào)節(jié)參數(shù)少、尋優(yōu)能力強(qiáng)等特點(diǎn)，且在收斂速度與收斂精度方面均明顯優(yōu)于引力搜索算法和粒子群優(yōu)化算法等。除此之外，WOA 算法在求解優(yōu)化問題時(shí)表現(xiàn)優(yōu)異，且應(yīng)用領(lǐng)域廣泛。目前，國內(nèi)外的研究學(xué)者將鯨魚優(yōu)化算法廣泛應(yīng)用于生產(chǎn)優(yōu)化[8]、負(fù)載預(yù)測[9]、二次分配[10]、圖像分割[11]、社團(tuán)檢測[12]等領(lǐng)域，在這些應(yīng)用領(lǐng)域中，鯨魚優(yōu)化算法發(fā)揮了重要的作用，為各領(lǐng)域的優(yōu)化問題尋求了較好的解。

針對DPC 算法自身所存在的問題，許多學(xué)者對其做了相應(yīng)的改進(jìn)以適應(yīng)不同的應(yīng)用領(lǐng)域。例如，丁志成等人[13]提出一種基于KL 散度的密度峰值算法，該算法提出一種自動(dòng)選取聚類中心的方法，利用KL 散度的差異性度量準(zhǔn)則對聚類中心和非聚類中心進(jìn)行清晰的劃分，以KL 排序圖中的拐點(diǎn)作為分界點(diǎn)實(shí)現(xiàn)對聚類中心的自動(dòng)選??；文獻(xiàn)[14]在原算法確定類簇中心時(shí)，將模糊規(guī)則應(yīng)用于其中，提出一種Fuzzy-CFSFDP算法，更有利于類簇中心的選擇，同時(shí)提高了聚類結(jié)果的準(zhǔn)確率；文獻(xiàn)[15]提出將網(wǎng)格劃分和圓劃分的方法應(yīng)用于DPC算法來篩選點(diǎn)，提出了GDPC 算法和CDPC 算法，都有效地降低了算法的復(fù)雜度，其中GDPC算法相比于DPC算法的計(jì)算時(shí)間更短，CDPC算法相對于DPC算法在大規(guī)模數(shù)據(jù)集上的準(zhǔn)確度更高；杜沛等人[16]提出了基于K近鄰的比較密度峰值聚類算法，該算法結(jié)合K近鄰概念重新定義了截?cái)嗑嚯x和局部密度的度量方法，對任意數(shù)據(jù)集能自適應(yīng)地生成截?cái)嗑嚯x，并使局部密度的計(jì)算結(jié)果更符合數(shù)據(jù)的真實(shí)分布，同時(shí)在決策圖中引入距離比較量代替原距離參數(shù)，使類簇中心在決策圖上更加明顯；蔣禮青等人[17]提出基于近鄰距離曲線和類合并優(yōu)化的聚類算法，此算法利用近鄰距離曲線變化情況自動(dòng)確定截?cái)嗑嚯x，并利用計(jì)算值的方法指導(dǎo)類的合并，引入內(nèi)聚程度衡量參數(shù)解決了類合并后不能撤銷的難題，從而實(shí)現(xiàn)對多密度峰值數(shù)據(jù)的正確聚類；高詩瑩等人[18]提出了基于密度比例峰值聚類算法，該算法將密度比例引入到密度峰值聚類算法中，通過計(jì)算樣本數(shù)據(jù)的密度比峰值來提高數(shù)據(jù)中密度較小類簇的辨識(shí)度，進(jìn)而提升整體聚類的準(zhǔn)確率。

以上幾種改進(jìn)算法雖然較原DPC算法都具有較好的聚類表現(xiàn)，但也存在著一定的問題：（1）沒有很好地克服原算法對截?cái)嗑嚯x的依賴性，人為設(shè)定截?cái)嗑嚯x使得最終的聚類結(jié)果具有很大的隨機(jī)性和主觀因素，不能保證截?cái)嗑嚯x選取的有效性[19-20]；（2）在決策圖生成后，需手動(dòng)選擇聚類中心[19]，對于某些數(shù)據(jù)集而言，可能會(huì)導(dǎo)致聚類中心多選或漏選的情況，這將會(huì)直接影響聚類結(jié)果。針對以上問題，本文提出了一種結(jié)合鯨魚優(yōu)化算法的自適應(yīng)密度峰值聚類算法（WOA-DPC）。該算法首先根據(jù)加權(quán)的局部密度和相對距離乘積的斜率變化趨勢實(shí)現(xiàn)聚類中心的自動(dòng)選擇，再建立以ACC 指標(biāo)為目標(biāo)函數(shù)的優(yōu)化問題，利用鯨魚優(yōu)化算法（WOA）有效地尋優(yōu)能力對目標(biāo)函數(shù)進(jìn)行優(yōu)化，尋找最佳的截?cái)嗑嚯xdc。

1 預(yù)備知識(shí)

1.1 密度峰值聚類算法（DPC）

密度峰值聚類算法（DPC）原理主要依據(jù)兩個(gè)直觀的假設(shè)：（1）聚類中心被一群密度較低的鄰居點(diǎn)包圍著；（2）聚類中心離比它密度更高的點(diǎn)的距離相對較大。該算法只需輸入截?cái)嗑嚯xdc這一個(gè)參數(shù)，通過人工手動(dòng)選取聚類中心點(diǎn)，然后根據(jù)一步分配策略完成對剩余點(diǎn)的聚類和分配。DPC算法中，局部密度的計(jì)算有兩種方式，當(dāng)數(shù)據(jù)集較大時(shí)，局部密度的計(jì)算如下：

當(dāng)數(shù)據(jù)集較小時(shí)，局部密度的定義如下：

其中截?cái)嗑嚯x：

式中，di為所有數(shù)據(jù)點(diǎn)中任意兩點(diǎn)間歐氏距離的升序排列。

定義相對距離為樣本點(diǎn)與最近高密度樣本點(diǎn)之間的距離，如式（5）所示：

DPC算法根據(jù)式（4）得出截?cái)嗑嚯xdc，再將其代入局部密度ρ和距離δ的計(jì)算公式，根據(jù)ρ和δ繪制出一個(gè)二維空間的決策圖，通過決策圖手動(dòng)選取出ρ和δ相對較大的值作為聚類中心，最后，根據(jù)一步分配策略，將剩余點(diǎn)分配到密度比它高且距離其最近的類簇當(dāng)中。

1.2 鯨魚優(yōu)化算法（WOA）

WOA算法是通過模擬鯨魚捕食行為而提出的一種新型仿生算法，主要分為三個(gè)階段：獵物包圍階段、氣泡襲擊階段、獵物搜索階段[7]。

1.2.1 獵物包圍階段

在這個(gè)階段，鯨魚能夠識(shí)別獵物的位置并包圍它們以捕獲獵物。此階段鯨魚個(gè)體向當(dāng)前最優(yōu)解移動(dòng)并更新其位置，該行為的數(shù)學(xué)模型[7]如下：

式中，t是當(dāng)前迭代次數(shù)，X*(t) 是目前最優(yōu)解位置，X(t)是當(dāng)前鯨魚位置，A、C是系數(shù)向量，r為[0,1]之間的隨機(jī)數(shù)，a為從2到0的線性遞減參數(shù)。

1.2.2 氣泡襲擊階段

在此階段，通過收縮環(huán)繞和螺旋形路徑來設(shè)計(jì)鯨魚捕食吐氣泡的行為，其數(shù)學(xué)模型[7]為：

式中，b是定義對數(shù)螺旋線形狀的常量，l是[-1,1]之間的隨機(jī)數(shù)。

假設(shè)座頭鯨收縮環(huán)繞和螺旋形位置更新的概率均為50%。建立如下位置更新模型[7]：

式中，變量p是[0,1]之間的隨機(jī)數(shù)。

1.2.3 食物搜索階段

當(dāng)|A|≥1 時(shí)，種群個(gè)體隨機(jī)選擇鯨魚個(gè)體作為參照更新其位置，強(qiáng)迫鯨魚個(gè)體遠(yuǎn)離最優(yōu)參考鯨魚，這樣可以有效增強(qiáng)算法的全局探索能力，數(shù)學(xué)模型[7]如下：

式中，Xrand(t)是從當(dāng)前種群中隨機(jī)選擇鯨魚個(gè)體。在具體問題優(yōu)化過程中，鯨魚個(gè)體根據(jù)不同的位置更新方式不斷向最優(yōu)解靠近。

WOA算法具體步驟如下：

步驟1在解空間中隨機(jī)初始化S個(gè)鯨魚個(gè)體位置，給出最大迭代次數(shù)T及當(dāng)前迭代次數(shù)t。

步驟2通過目標(biāo)函數(shù)計(jì)算每個(gè)個(gè)體適應(yīng)度值，并保留最優(yōu)個(gè)體為X*(t)。

步驟3更新系數(shù)向量A及隨機(jī)數(shù)p，根據(jù)A及p的取值情況對所有個(gè)體進(jìn)行相應(yīng)的位置更新：

當(dāng)|A|≥1，p ＜0.5 時(shí)，執(zhí)行公式（12）進(jìn)行位置更新；

當(dāng)|A|＜1，p ＜0.5 時(shí)，執(zhí)行公式（6）進(jìn)行位置更新；

當(dāng)p≥0.5 時(shí)，執(zhí)行公式（9）進(jìn)行位置更新。

步驟4計(jì)算更新后個(gè)體的適應(yīng)度值，并更新保留最優(yōu)個(gè)體位置及最優(yōu)適應(yīng)度值。

步驟5判斷t ＜T是否成立，若成立，令t=t+1，轉(zhuǎn)步驟2；否則，算法結(jié)束，輸出最優(yōu)解及最優(yōu)值。

2 結(jié)合鯨魚優(yōu)化算法的自適應(yīng)密度峰值聚類算法

本文主要從以下兩個(gè)方面進(jìn)行改進(jìn)：首先通過加權(quán)的局部密度和相對距離乘積的斜率變化趨勢實(shí)現(xiàn)聚類中心的自動(dòng)選擇；其次，利用鯨魚優(yōu)化算法較強(qiáng)的尋優(yōu)能力對DPC算法中的截?cái)嗑嚯xdc進(jìn)行優(yōu)化。

2.1 聚類中心的自適應(yīng)選取策略

原DPC 算法在選取聚類中心時(shí)，需要在決策圖中手動(dòng)截取那些局部密度ρ和相對距離δ大的點(diǎn)為聚類中心，而截取過程中帶有一定的主觀性，例如，圖1所示類別數(shù)為7的Aggregation數(shù)據(jù)集的聚類決策圖，但從圖中看出同時(shí)具有較大的ρ和δ值的點(diǎn)并不容易確定，手動(dòng)截取容易造成聚類中心個(gè)數(shù)選取不準(zhǔn)確的問題，若選取聚類中心時(shí)出現(xiàn)了錯(cuò)誤，那么在接下來的數(shù)據(jù)點(diǎn)分配類簇上會(huì)產(chǎn)生連鎖反應(yīng)，最終使得聚類效果不理想。

圖1 Aggregation數(shù)據(jù)集的聚類決策圖

在實(shí)際問題中，也可能存在一些具有較大ρ與較小δ或有較小ρ與較大δ的數(shù)據(jù)點(diǎn)也為聚類中心。因此，需綜合考慮局部密度ρ和相對距離δ，定義如下度量：

其中N為數(shù)據(jù)集中樣本點(diǎn)個(gè)數(shù)。

為避免不同量級間的相互影響，對ρ和δ進(jìn)行歸一化處理，得到新的γ定義如下：

將經(jīng)歸一化處理所得到的γi(i=1,2,…,N)進(jìn)行降序排列，取前40個(gè)點(diǎn)。下文中，為了記號方便，仍用γ1,γ2,…,γ40表示由大到小排序后的前40 個(gè)γ值。根據(jù)γ降序排列圖選取聚類中心，γ值越大的點(diǎn)越有可能是聚類中心，可以有效避免由于單獨(dú)考慮ρ和δ所帶來的誤差。然而，對于一些數(shù)據(jù)集使用該方法也會(huì)存在聚類中心選取不準(zhǔn)確的問題。以文獻(xiàn)[5]中使用的類別為5 的GDP數(shù)據(jù)集為例，圖2為該數(shù)據(jù)集的γ降序排列圖。圖中γ值呈現(xiàn)先快速下降，再趨于穩(wěn)定變化的趨勢，且圖中存在多個(gè)拐點(diǎn)。直觀來看γ7之后的值趨于穩(wěn)定，會(huì)誤以為聚類中心的個(gè)數(shù)為7個(gè)，而實(shí)際上聚類中心只有5個(gè)。因此，僅根據(jù)γ降序排列圖有時(shí)也很難準(zhǔn)確地選取出聚類中心。

圖2 GDP數(shù)據(jù)集的γ 降序排列圖

對此，本文將根據(jù)γ的斜率來選取聚類中心。一般地，對于歸一化到[0,1] 上的斜率值最大的點(diǎn)可選作聚類中心和其他點(diǎn)的分界點(diǎn)，即將所對應(yīng)的數(shù)據(jù)點(diǎn)選取為聚類中心。但考慮到的前幾個(gè)值一般很大且呈現(xiàn)較強(qiáng)的跳躍性，仍不易準(zhǔn)確選取聚類中心。如圖2 所示，容易看出γ1到γ2差值最大，而將γ1所對應(yīng)的數(shù)據(jù)點(diǎn)選作聚類中心顯然是錯(cuò)誤的。因此，這里引入加權(quán)的斜率度量如下：

其中，(i-1)可看作權(quán)值，隨著i的增大而增大，這樣可使γi值大的點(diǎn)擁有較小的權(quán)值，而γi值小的點(diǎn)擁有較大的權(quán)值，以降低前面一些過大值對聚類中心選取的影響，從而實(shí)現(xiàn)了聚類中心的自適應(yīng)準(zhǔn)確選取。綜上，本文所提的聚類中心選取策略分為兩步：

（2）將降序排列的前i0個(gè)γ值所對應(yīng)的數(shù)據(jù)點(diǎn)選為聚類中心。

根據(jù)公式（15）得到的ki值描點(diǎn)作圖，稱其為加權(quán)γ斜率變化趨勢圖。圖3 為GDP 數(shù)據(jù)集的加權(quán)γ斜率變化趨勢圖。由此易知k5最大，故聚類中心個(gè)數(shù)為5，且將前5個(gè)γ值所對應(yīng)的數(shù)據(jù)點(diǎn)選為聚類中心，解決了利用公式（14）選取聚類中心的問題。類似地，圖4、圖5分別為Spiral數(shù)據(jù)集和D31數(shù)據(jù)集利用公式（14）和（15）選取聚類中心的效果對比圖。由圖4（b）易知聚類中心個(gè)數(shù)為3，這和Spiral數(shù)據(jù)集的類別數(shù)3是一致的，而由圖4（a）在γi值趨于穩(wěn)定前會(huì)誤以為聚類中心的個(gè)數(shù)為5。雖然D31數(shù)據(jù)集的類別數(shù)較多，為31個(gè)，但由圖5（b）亦可準(zhǔn)確選取出聚類中心的個(gè)數(shù)。此外，通過大量模擬試驗(yàn)表明，利用公式（15）對大部分?jǐn)?shù)據(jù)集均可客觀選取出聚類中心的個(gè)數(shù)。

圖3 GDP數(shù)據(jù)集的加權(quán)γ 斜率變化趨勢圖

圖4 Spiral數(shù)據(jù)集的聚類中心選取效果對比圖

圖5 D31數(shù)據(jù)集的聚類中心選取效果對比圖

2.2 截?cái)嗑嚯xdc 的優(yōu)化選取策略

原DPC 算法中截?cái)嗑嚯xdc需要人為設(shè)定，且取值較為敏感。為了更直觀地反映此問題，以圖6中給出的R15數(shù)據(jù)集所得到的聚類結(jié)果圖為例，可以得出，dc的細(xì)微不同所得到的聚類結(jié)果存在較大的差異。因此，對截?cái)嗑嚯xdc進(jìn)行優(yōu)化就變得很有必要。

圖6 不同dc 所對應(yīng)的聚類結(jié)果圖

本文利用WOA 算法較強(qiáng)的尋優(yōu)能力，來選取最佳的截?cái)嗑嚯xdc。ACC 指標(biāo)[21-23]是廣泛應(yīng)用于統(tǒng)計(jì)學(xué)和信息檢索領(lǐng)域的評價(jià)指標(biāo)，對聚類結(jié)果能夠產(chǎn)生準(zhǔn)確的評判，假設(shè)Pj為已知人工標(biāo)注的簇，Cj為經(jīng)過聚類后的簇，則ACC指標(biāo)的計(jì)算公式如下：

在優(yōu)化過程中，以ACC指標(biāo)作為WOA算法的目標(biāo)函數(shù)，對DPC算法中的截?cái)嗑嚯xdc進(jìn)行優(yōu)化，所選取的目標(biāo)函數(shù)ACC 指標(biāo)是關(guān)于dc的一維函數(shù)，即給定一個(gè)dc便可得到一個(gè)ACC 指標(biāo)值，ACC 指標(biāo)的取值范圍在[0,1]之間，其值越接近于1，說明聚類結(jié)果越好。

利用WOA算法多次迭代尋優(yōu)，找出使DPC算法中ACC指標(biāo)最大時(shí)的dc作為當(dāng)前數(shù)據(jù)集最優(yōu)的dc，從而實(shí)現(xiàn)算法的聚類。

2.3 WOA-DPC算法描述

本文所提出的WOA-DPC算法的基本思想：首先根據(jù)γ的斜率變化趨勢圖選取聚類中心，從而避免了聚類中心需要手動(dòng)選擇的缺陷；其次，將鯨魚優(yōu)化算法和聚類中心自適應(yīng)的密度峰值聚類算法根據(jù)ACC指標(biāo)函數(shù)有效地結(jié)合起來，對參數(shù)dc進(jìn)行了優(yōu)化，克服了DPC算法對參數(shù)選取敏感的缺陷。算法具體步驟如下，流程圖如圖7所示。

輸入：實(shí)驗(yàn)數(shù)據(jù)集U(x)={x1,x2,…,xn}。

輸出：聚類結(jié)果H={h1,h2,…,hm}，m為數(shù)據(jù)集聚類結(jié)果類別數(shù)。

步驟1設(shè)置WOA算法的種群規(guī)模為S，最大迭代次數(shù)T。

步驟2數(shù)據(jù)預(yù)處理，計(jì)算數(shù)據(jù)集中樣本間的歐氏距離，確定dc的取值范圍。

步驟3初始化WOA算法的種群位置，即dc的值。

步驟4將dc代入式（3）及式（5）中，分別計(jì)算出所有點(diǎn)的局部密度ρi與相對距離δi。

步驟5根據(jù)式（15）得到γ斜率變化趨勢圖，并自動(dòng)選取聚類中心。

步驟6引入如式（16）所示的評價(jià)指標(biāo)ACC 作為WOA 的目標(biāo)函數(shù)，記ACC 指標(biāo)最大時(shí)所對應(yīng)的dc為。

步驟7利用WOA算法更新dc。

步驟8判斷WOA算法是否滿足迭代終止條件，若是，則結(jié)束迭代并轉(zhuǎn)步驟9。若否，則跳轉(zhuǎn)至步驟4繼續(xù)優(yōu)化尋優(yōu)。

步驟9將最優(yōu)截?cái)嗑嚯xdc所對應(yīng)的聚類結(jié)果進(jìn)行除噪，得到最終聚類結(jié)果，完成聚類。

圖7 WOA-DPC算法流程圖

2.4 算法復(fù)雜度分析

對于含有N個(gè)樣本點(diǎn)的數(shù)據(jù)集，DPC 算法的時(shí)間復(fù)雜度主要來自計(jì)算樣本點(diǎn)間的距離矩陣D的復(fù)雜度O(N2)，對歐氏距離進(jìn)行快排的復(fù)雜度O(N2lbN)，計(jì)算局部密度ρ和最短距離δ的復(fù)雜度O(N2)組成。對于本文所提WOA-DPC 算法，算法復(fù)雜度主要體現(xiàn)在優(yōu)化過程。假設(shè)鯨魚群體規(guī)模為S，最大迭代系數(shù)為T，優(yōu)化截?cái)嗑嚯xdc問題時(shí)維度為1，故優(yōu)化dc的復(fù)雜度為O(S·T)。在優(yōu)化過程中，由于dc的變化會(huì)導(dǎo)致局部密度ρ和相對距離δ的改變，故此過程的復(fù)雜度為O(N2·T)。綜上，本文所提算法的時(shí)間復(fù)雜度為。

3 仿真實(shí)驗(yàn)結(jié)果及其分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了評估本文所提算法的可行性和有效性，采用如表1所示的9個(gè)數(shù)據(jù)集對其進(jìn)行驗(yàn)證。

表1 人工合成數(shù)據(jù)集以及UCI數(shù)據(jù)集描述

3.2 評價(jià)指標(biāo)

為避免重復(fù)使用ACC 指標(biāo)，本實(shí)驗(yàn)采用FM 指數(shù)（FMI）、調(diào)整蘭德系數(shù)（ARI）和調(diào)整互信息（AMI）[21-23]三個(gè)評價(jià)指標(biāo)來對各算法的聚類結(jié)果進(jìn)行評估。假設(shè)C代表樣本真實(shí)標(biāo)簽，C*代表聚類產(chǎn)生的結(jié)果。

（1）FMI指標(biāo)

FMI是成對精度與召回率的幾何均值，定義式如下：

其中，a表示在C和C*中屬于同一類數(shù)據(jù)點(diǎn)的對數(shù)，b表示在C中屬于同一類但在C*中不屬于同一類的數(shù)據(jù)點(diǎn)的對數(shù)，c表示在C*中屬于不同類但在C中屬于同一類的數(shù)據(jù)點(diǎn)的對數(shù)。FMI 指標(biāo)的取值范圍是[0,1]，其數(shù)值越大代表聚類效果越好。

（2）ARI指標(biāo)

蘭德指數(shù)（RI）的定義式為：

式中，a代表在C和C*中屬于同一類數(shù)據(jù)點(diǎn)的對數(shù)，b代表在C*中屬于不同類但在C中屬于同一類的數(shù)據(jù)點(diǎn)的對數(shù)，代表數(shù)據(jù)集中可組成總元素的對數(shù)。使用RI指標(biāo)時(shí)，不能保證類別標(biāo)簽在隨即分配的情況下，其值接近0。故引入調(diào)整蘭德指數(shù)（ARI）來解決這一問題，ARI指標(biāo)的定義式為：

其中，E(RI) 表示RI 的數(shù)學(xué)期望，ARI 的取值范圍為[-1,1]，值越大表示聚類結(jié)果越精準(zhǔn)。

（3）AMI指標(biāo)

與ARI 相似，AMI 也是一種常見的聚類評價(jià)指標(biāo)，它的定義式為：

式中，H(A),H(B)表示兩個(gè)類別標(biāo)簽的熵，AMI是基于互信息（MI）來衡量聚類效果的類別信息，E(MI)表示MI 的數(shù)學(xué)期望。AMI 的取值范圍是[-1,1]，值越接近于1，表示聚類結(jié)果越好，即與真實(shí)結(jié)果越吻合。

3.3 實(shí)驗(yàn)結(jié)果及分析

對表1 所給出的數(shù)據(jù)集，使用WOA-DPC 算法與DPC 算法、DBSCAN 算法和K-Means 算法對其進(jìn)行聚類，圖8～10 分別為四種對比算法在Spiral、Aggregation和Flame三種人工數(shù)據(jù)集上聚類效果圖，這三種數(shù)據(jù)集的總體分布情況和聚類的數(shù)目是截然不同的，它們可以更直觀地反映出四種聚類算法的聚類性能。圖中顏色不同的點(diǎn)被分配到不同的類簇中，其中，藍(lán)色星形表示聚類中心點(diǎn)，叉形表示噪聲點(diǎn)。

圖8 四種算法在Spiral數(shù)據(jù)集上的聚類效果圖

圖9 四種算法在Aggregation數(shù)據(jù)集上的聚類效果圖

圖10 四種算法在Flame數(shù)據(jù)集上的聚類效果圖

從圖8 對Spiral 數(shù)據(jù)集的螺旋形聚類效果圖中看出，除K-Means 算法外，其他三個(gè)算法均能夠準(zhǔn)確地對其進(jìn)行聚類，K-Means 算法的聚類結(jié)果出現(xiàn)明顯的錯(cuò)誤，它將該數(shù)據(jù)集平均分為了三部分，且將每個(gè)部分的中心當(dāng)作聚類中心。盡管K-Means 算法在該數(shù)據(jù)集上得到了正確的聚類數(shù)目，但無法進(jìn)行正確的聚類，這表明K-Means 算法不能很好地對非凸分布的數(shù)據(jù)進(jìn)行聚類。同時(shí)，其余三種算法均得到了正確的聚類結(jié)果，也可明顯可看出WOA-DPC 算法比DPC 算法的聚類中心的識(shí)別更為準(zhǔn)確。

在圖9 的Aggregation 數(shù)據(jù)集聚類效果圖中，WOADPC算法和DPC算法均得到了正確的類簇，WOA-DPC算法也更精準(zhǔn)地識(shí)別了聚類中心點(diǎn)。DBSCAN 算法雖然能夠識(shí)別出正確的聚類數(shù)目，但其中某些點(diǎn)被其標(biāo)記為了噪聲點(diǎn)，導(dǎo)致聚類效果略差。而K-Means算法在一個(gè)集群中出現(xiàn)了兩個(gè)聚類中心，并出現(xiàn)了在三個(gè)藍(lán)色類簇之間選擇聚類中心的情況。從而使得聚類結(jié)果產(chǎn)生了較大的錯(cuò)誤。因此，WOA-DPC算法能夠準(zhǔn)確地識(shí)別出聚類中心，并有效地優(yōu)化了dc，從而得到了更加精準(zhǔn)的聚類結(jié)果。

從圖10 的Flame 數(shù)據(jù)集的流形聚類效果圖可知，WOA-DPC 算法、DPC 算法和DBSCAN 算法都可正確地識(shí)別聚類數(shù)目，而DBSCAN 算法將左上邊的兩個(gè)點(diǎn)識(shí)別為了噪聲點(diǎn)，導(dǎo)致聚類準(zhǔn)確率降低。K-Means算法將本該屬于紅色類簇的點(diǎn)分配給了綠色類簇，以使整個(gè)數(shù)據(jù)集看起來像是從對角線斜率切開的，從而產(chǎn)生了錯(cuò)誤的聚類結(jié)果。因此，可以看出WOA-DPC算法不僅能夠得到正確的聚類數(shù)目，而且可以更精準(zhǔn)地識(shí)別出聚類中心的位置，從而得到更佳的聚類效果圖。

表2 給出了WOA-DPC 算法與其他對比算法在各數(shù)據(jù)集上的聚類評價(jià)指標(biāo)值。圖11～13 分別為四種算法在各種數(shù)據(jù)集上的指標(biāo)對比圖。從表2 所得的評價(jià)指標(biāo)值可以看出，通過對聚類中心選取策略改進(jìn)和利用鯨魚優(yōu)化算法對截?cái)嗑嚯x的優(yōu)化，WOA-DPC算法對九種數(shù)據(jù)集進(jìn)行聚類所得的FMI、ARI和AMI指標(biāo)值均得到了更好的結(jié)果。在Spiral 數(shù)據(jù)集和Flame 數(shù)據(jù)集中，WOA-DPC 算法和DPC 算法的聚類指標(biāo)值都為1，而在其他幾個(gè)數(shù)據(jù)集上DPC 算法的聚類表現(xiàn)略差于WOADPC 算法，但優(yōu)于K-Means 算法。尤其在Jain 數(shù)據(jù)集中，WOA-DPC算法相較于DPC算法的AMI指標(biāo)值提高了大概40%。DBSCAN 算法在九種數(shù)據(jù)集的聚類表現(xiàn)中，Spiral 數(shù)據(jù)集的聚類指標(biāo)為1，表明對其聚類效果良好，在Jain數(shù)據(jù)集上，DBSCAN算法表現(xiàn)優(yōu)于DPC算法，而在另外七種數(shù)據(jù)集中，其聚類效果均差于WOA-DPC算法和DPC算法。K-Means算法在四種對比算法中，整體表現(xiàn)差于其他三種算法。同時(shí)，在維數(shù)比較大的Seeds和Waveform 數(shù)據(jù)集中，WOA-DPC 算法的準(zhǔn)確率也較其他三種算法有了較大的提高，說明本文所提算法無論對于高維數(shù)據(jù)集還是低維數(shù)據(jù)集都有較好的聚類結(jié)果。

表2 WOA-DPC算法與其他算法的聚類結(jié)果比較

圖11 四種算法的FMI值對比圖

圖12 四種算法的ARI值對比圖

圖13 四種算法的AMI值對比圖

從圖11～13 中可以更直觀看出，WOA-DPC 算法不論是在人工數(shù)據(jù)集還是UCI 數(shù)據(jù)集上的聚類指標(biāo)值明顯高于其他三種對比算法。相對于原DPC 算法，本文算法避免了人為設(shè)定截?cái)嗑嚯x和手動(dòng)選取聚類中心的缺陷，其聚類效果也遠(yuǎn)遠(yuǎn)優(yōu)于DPC算法。

4 結(jié)束語

本文針對DPC 算法存在的問題，從聚類中心自適應(yīng)和優(yōu)化截?cái)嗑嚯x兩個(gè)方面進(jìn)行了改進(jìn)。

（1）首先，引入局部密度和距離的乘積γ，來擴(kuò)大聚類中心的選取范圍。其次，根據(jù)γ的加權(quán)斜率變化趨勢來選取正確的聚類中心個(gè)數(shù)，從而實(shí)現(xiàn)聚類中心的自動(dòng)選取。

（2）利用鯨魚優(yōu)化算法較強(qiáng)的尋優(yōu)能力來優(yōu)化截?cái)嗑嚯xdc，將ACC 指標(biāo)作為目標(biāo)函數(shù)，針對不同的數(shù)據(jù)集，尋找出使聚類準(zhǔn)確率指標(biāo)值最大時(shí)所對應(yīng)的dc，從而避免了聚類結(jié)果對截?cái)嗑嚯xdc較為敏感的問題。

通過實(shí)驗(yàn)驗(yàn)證，本文算法相較于原算法，不僅避免了人工選取截?cái)嗑嚯xdc和手動(dòng)選取聚類中心的缺陷，而且具有更高的準(zhǔn)確率和更優(yōu)的聚類結(jié)果。下一步的研究目標(biāo)是針對DPC對高維數(shù)據(jù)集聚類效果不佳和對剩余點(diǎn)的分配策略容錯(cuò)性較高的問題進(jìn)行改進(jìn)，使其更好地應(yīng)用于復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集。