結合鯨魚優化算法的自適應密度峰值聚類算法

王芙銀，張德生，張 曉

西安理工大學 理學院，西安710054

隨著互聯網技術的飛速發展，隨之產生的數據也以驚人的速度增加，這些海量的數據包含著豐富的信息。人們的日常活動都可以在一定形式上量化為數據的方式，但這些數據通常是毫無規律、雜亂無章的，隨著時間的推移，這些數據的積累就更加龐大，大數據的時代也就應運而生。怎樣從這些數據中獲得有價值的信息就變成了當今時代研究的熱點[1]。

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

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

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

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

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

1 預備知識

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

密度峰值聚類算法（DPC）原理主要依據兩個直觀的假設：（1）聚類中心被一群密度較低的鄰居點包圍著；（2）聚類中心離比它密度更高的點的距離相對較大。該算法只需輸入截斷距離dc這一個參數，通過人工手動選取聚類中心點，然后根據一步分配策略完成對剩余點的聚類和分配。DPC算法中，局部密度的計算有兩種方式，當數據集較大時，局部密度的計算如下：

當數據集較小時，局部密度的定義如下：

其中截斷距離：

式中，di為所有數據點中任意兩點間歐氏距離的升序排列。

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

DPC算法根據式（4）得出截斷距離dc，再將其代入局部密度ρ和距離δ的計算公式，根據ρ和δ繪制出一個二維空間的決策圖，通過決策圖手動選取出ρ和δ相對較大的值作為聚類中心，最后，根據一步分配策略，將剩余點分配到密度比它高且距離其最近的類簇當中。

1.2 鯨魚優化算法（WOA）

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

1.2.1 獵物包圍階段

在這個階段，鯨魚能夠識別獵物的位置并包圍它們以捕獲獵物。此階段鯨魚個體向當前最優解移動并更新其位置，該行為的數學模型[7]如下：

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

1.2.2 氣泡襲擊階段

在此階段，通過收縮環繞和螺旋形路徑來設計鯨魚捕食吐氣泡的行為，其數學模型[7]為：

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

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

式中，變量p是[0,1]之間的隨機數。

1.2.3 食物搜索階段

當|A|≥1 時，種群個體隨機選擇鯨魚個體作為參照更新其位置，強迫鯨魚個體遠離最優參考鯨魚，這樣可以有效增強算法的全局探索能力，數學模型[7]如下：

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

WOA算法具體步驟如下：

步驟1在解空間中隨機初始化S個鯨魚個體位置，給出最大迭代次數T及當前迭代次數t。

步驟2通過目標函數計算每個個體適應度值，并保留最優個體為X*(t)。

步驟3更新系數向量A及隨機數p，根據A及p的取值情況對所有個體進行相應的位置更新：

當|A|≥1，p ＜0.5 時，執行公式（12）進行位置更新；

當|A|＜1，p ＜0.5 時，執行公式（6）進行位置更新；

當p≥0.5 時，執行公式（9）進行位置更新。

步驟4計算更新后個體的適應度值，并更新保留最優個體位置及最優適應度值。

步驟5判斷t ＜T是否成立，若成立，令t=t+1，轉步驟2；否則，算法結束，輸出最優解及最優值。

2 結合鯨魚優化算法的自適應密度峰值聚類算法

本文主要從以下兩個方面進行改進：首先通過加權的局部密度和相對距離乘積的斜率變化趨勢實現聚類中心的自動選擇；其次，利用鯨魚優化算法較強的尋優能力對DPC算法中的截斷距離dc進行優化。

2.1 聚類中心的自適應選取策略

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

圖1 Aggregation數據集的聚類決策圖

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

其中N為數據集中樣本點個數。

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

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

圖2 GDP數據集的γ 降序排列圖

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

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

（2）將降序排列的前i0個γ值所對應的數據點選為聚類中心。

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

圖3 GDP數據集的加權γ 斜率變化趨勢圖

圖4 Spiral數據集的聚類中心選取效果對比圖

圖5 D31數據集的聚類中心選取效果對比圖

2.2 截斷距離dc 的優化選取策略

原DPC 算法中截斷距離dc需要人為設定，且取值較為敏感。為了更直觀地反映此問題，以圖6中給出的R15數據集所得到的聚類結果圖為例，可以得出，dc的細微不同所得到的聚類結果存在較大的差異。因此，對截斷距離dc進行優化就變得很有必要。

圖6 不同dc 所對應的聚類結果圖

本文利用WOA 算法較強的尋優能力，來選取最佳的截斷距離dc。ACC 指標[21-23]是廣泛應用于統計學和信息檢索領域的評價指標，對聚類結果能夠產生準確的評判，假設Pj為已知人工標注的簇，Cj為經過聚類后的簇，則ACC指標的計算公式如下：

在優化過程中，以ACC指標作為WOA算法的目標函數，對DPC算法中的截斷距離dc進行優化，所選取的目標函數ACC 指標是關于dc的一維函數，即給定一個dc便可得到一個ACC 指標值，ACC 指標的取值范圍在[0,1]之間，其值越接近于1，說明聚類結果越好。

利用WOA算法多次迭代尋優，找出使DPC算法中ACC指標最大時的dc作為當前數據集最優的dc，從而實現算法的聚類。

2.3 WOA-DPC算法描述

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

輸入：實驗數據集U(x)={x1,x2,…,xn}。

輸出：聚類結果H={h1,h2,…,hm}，m為數據集聚類結果類別數。

步驟1設置WOA算法的種群規模為S，最大迭代次數T。

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

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

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

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

步驟6引入如式（16）所示的評價指標ACC 作為WOA 的目標函數，記ACC 指標最大時所對應的dc為。

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

步驟8判斷WOA算法是否滿足迭代終止條件，若是，則結束迭代并轉步驟9。若否，則跳轉至步驟4繼續優化尋優。

步驟9將最優截斷距離dc所對應的聚類結果進行除噪，得到最終聚類結果，完成聚類。

圖7 WOA-DPC算法流程圖

2.4 算法復雜度分析

對于含有N個樣本點的數據集，DPC 算法的時間復雜度主要來自計算樣本點間的距離矩陣D的復雜度O(N2)，對歐氏距離進行快排的復雜度O(N2lbN)，計算局部密度ρ和最短距離δ的復雜度O(N2)組成。對于本文所提WOA-DPC 算法，算法復雜度主要體現在優化過程。假設鯨魚群體規模為S，最大迭代系數為T，優化截斷距離dc問題時維度為1，故優化dc的復雜度為O(S·T)。在優化過程中，由于dc的變化會導致局部密度ρ和相對距離δ的改變，故此過程的復雜度為O(N2·T)。綜上，本文所提算法的時間復雜度為。

3 仿真實驗結果及其分析

3.1 實驗數據集

為了評估本文所提算法的可行性和有效性，采用如表1所示的9個數據集對其進行驗證。

表1 人工合成數據集以及UCI數據集描述

3.2 評價指標

為避免重復使用ACC 指標，本實驗采用FM 指數（FMI）、調整蘭德系數（ARI）和調整互信息（AMI）[21-23]三個評價指標來對各算法的聚類結果進行評估。假設C代表樣本真實標簽，C*代表聚類產生的結果。

（1）FMI指標

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

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

（2）ARI指標

蘭德指數（RI）的定義式為：

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

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

（3）AMI指標

與ARI 相似，AMI 也是一種常見的聚類評價指標，它的定義式為：

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

3.3 實驗結果及分析

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

圖8 四種算法在Spiral數據集上的聚類效果圖

圖9 四種算法在Aggregation數據集上的聚類效果圖

圖10 四種算法在Flame數據集上的聚類效果圖

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

在圖9 的Aggregation 數據集聚類效果圖中，WOADPC算法和DPC算法均得到了正確的類簇，WOA-DPC算法也更精準地識別了聚類中心點。DBSCAN 算法雖然能夠識別出正確的聚類數目，但其中某些點被其標記為了噪聲點，導致聚類效果略差。而K-Means算法在一個集群中出現了兩個聚類中心，并出現了在三個藍色類簇之間選擇聚類中心的情況。從而使得聚類結果產生了較大的錯誤。因此，WOA-DPC算法能夠準確地識別出聚類中心，并有效地優化了dc，從而得到了更加精準的聚類結果。

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

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

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

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

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

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

從圖11～13 中可以更直觀看出，WOA-DPC 算法不論是在人工數據集還是UCI 數據集上的聚類指標值明顯高于其他三種對比算法。相對于原DPC 算法，本文算法避免了人為設定截斷距離和手動選取聚類中心的缺陷，其聚類效果也遠遠優于DPC算法。

4 結束語

本文針對DPC 算法存在的問題，從聚類中心自適應和優化截斷距離兩個方面進行了改進。

（1）首先，引入局部密度和距離的乘積γ，來擴大聚類中心的選取范圍。其次，根據γ的加權斜率變化趨勢來選取正確的聚類中心個數，從而實現聚類中心的自動選取。

（2）利用鯨魚優化算法較強的尋優能力來優化截斷距離dc，將ACC 指標作為目標函數，針對不同的數據集，尋找出使聚類準確率指標值最大時所對應的dc，從而避免了聚類結果對截斷距離dc較為敏感的問題。

通過實驗驗證，本文算法相較于原算法，不僅避免了人工選取截斷距離dc和手動選取聚類中心的缺陷，而且具有更高的準確率和更優的聚類結果。下一步的研究目標是針對DPC對高維數據集聚類效果不佳和對剩余點的分配策略容錯性較高的問題進行改進，使其更好地應用于復雜結構的數據集。