基于多指標投票的粒子群聚類優化算法

李瑞珠 劉錫鵬

摘要：針對不同的數據特點，已有多種用于算法優化的聚類評價指標被提出。大量數據測試發現，僅使用單一評價指標無法可靠地體現數據的聚類劃分優劣，傳統的單一指標聚類優化算法在聚類準確度上還有待提高。一種新型的多指標投票評價策略被提出，并應用于粒子群聚類優化算法中。多指標投票評價的設計思路是依靠過半數的評價指標對解的優劣進行判定，從而避免單一指標的錯誤評價影響優化算法中的群體更新。經多份數據測試，與單指標評價的聚類算法進行對比，多指標評價粒子群聚類優化算法獲得更優的聚類結果。

關鍵詞：多指標投票;粒子群算法;聚類優化;單指標;指標評價

中圖分類號：TP301.6? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）13-0184-04

Abstract： For different data characteristics， a variety of clustering evaluation indicators for algorithm optimization have been proposed. A large number of data tests have found that only a single evaluation index cannot reliably reflect the pros and cons of data clustering. The traditional single index clustering optimization algorithm needs to be improved in clustering accuracy. A new multi-index voting evaluation strategy is proposed and applied to the particle swarm optimization algorithm. The design idea of multi-index voting evaluation is to rely on more than half of the evaluation indexes to judge the pros and cons of the solution， so as to avoid the wrong evaluation of a single index from affecting the group update in the optimization algorithm. After multiple data tests， compared with the single-index evaluation clustering algorithm， the multi-index evaluation particle swarm optimization algorithm obtains better clustering results.

Key words： multi-index voting; PSO; clustering optimization; single index; index evaluation

1 背景

聚類分析提供由個別數據對象到數據對象所指派到簇的抽象。而目前已有的算法面對日前趨于多樣化的數據集，仍然存在可提高的空間。

基于粒子群優化（Particle Swarm Optimization， PSO）的聚類算法已在UCI標準數據集iris與wine上做了測試，并與K-means算法、粒子群 K-means算法進行對比[1]，對比結果仍可優化。爾后，一種自適應慣性權重函數對粒子群算法進行動態調整的設計被提出，并融入K-means算法，幫助初始化聚類中心，應用于電子病歷聚類分析，提高了聚類準確率和效率[2]。

Omran等人[3]提出了一種基于粒子群優化的無指導圖像分類算法。這是最早提出的基于粒子群的聚類算法的應用，之后的粒子群聚類算法大都遵循其基本思想。Elhabyan等人[4]將基于PSO算法的聚類方法應用于無線傳感網，并在傳感網絡的生命周期上取得更優的效果。Santar等人[5]提出了針對無線傳感的能量有效性的粒子群聚類算法，提高能量優化率。Kaur等人[6]繼續將PSO算法應用于無線傳感網中，完成了群集內和群集間能耗的平衡。Vidyadhari等人[7]將PSO算法用于自適應文本聚類，在標準數據集的測試上，提高了文本聚類的正確率。綜上，無論國內抑或是國外，對于有關粒子群的聚類算法的研究都是針對具體某一應用，聚類的綜合性能還存在提高的空間，且對比對于單一評價標準來說還可拓展。

本文對7種常用的聚類內部指標，與4個外部指標進行聚類分析比較，通過對7份經典數據集的聚類分析發現單一指標值的優劣不一定代表聚類質量的優劣，因此認為對于目前單指標評價的聚類存在缺陷。

為解決單指標單一的指導問題，提高結合基于PSO算法的聚類方法的綜合性能，本文設計了多指標綜合評價機制，提出一種基于多指標投票綜合評價的粒子群聚類方法，集成多個內部指標，基于優化歷史信息與當前種群的解質量，自適應選擇對當前解最合理的聚類評價結果，并與單指標的基于粒子群的聚類算法進行多數據集實驗測試對比。實驗數據表明，多指標綜合評價機制的加入能有效提高聚類的準確度，相較單指標評價，多指標評價表現更優。

2 相關工作

2.1 聚類有效性指標

內部指標的選擇有很多，本文選擇應用較為廣泛的、針對類間距與類內距的7個指標，如表1所示。

其中CH[8]、Dunn[9]、SIL[10]、DB[11]、CS[12]提出較早，都已在具體的數據問題上得到了應用[13]，因此作為多指標評價機制主要成員較為可靠。GD33與GD53，提高了Dunn指標的抗噪能力，選擇二者旨在克服多樣化數據集的噪聲特點，完成對優化聚類的指導。

對于已知聚類分類類別，用于檢驗算法聚類結果優劣的指標，稱為外部指標。常用的外部指標有調整的蘭德系數（Adjust Rand Index，簡稱ARI），Jaccard系數（簡稱JacI）和Fowlkes and Mallows 系數（簡稱FMI）。這些指標值都是越大越好，當值為1時表示完全正確的分類。其中ARI是對蘭德系數R指標的調整，改進了隨機產生聚類時，指標值不為0的情況[18]。Jaccard系數[19]不注重聚類使用的方法，只注重結果，符合針對聚類結果的評價要求。FMI結合查準率與查全率的思想完成聚類性能的評價[20]。本文綜合上述3個外部指標，較為全面地完成聚類結果與性能的評價。

2.2 粒子群聚類算法

本文采用基于粒子群聚類算法[21]，結合6份經典數據集，進行聚類測試，分析聚類測試結果，計算7個內部指標，并計算該聚類結果與標記數據對比獲得的3個外部指標，驗證單指標聚類存在的缺陷。

2.2.1 編碼方案

設定聚類類別數的最大值[Kmax]，種群的個體編碼為D=[Kmax+Kmax*d]維的向量

[Zi=（Ti1，Ti2，...，TiKmax，mi1，mi2，...，miKmax）]，[d]為數據維度數，[mij]是簇中心的坐標向量，[Tij（j=1，...，Kmax）]是得到類別質心點的激活閾值。如果[Tij]大于0.5，則對應簇的質心點[mij]被激活，否則不被激活。

如圖1所示，一個維度[d]為2，最大聚類類別數[Kmax]為4的某個個體，0.5為激活閾值，第二個位置0.4小于0.5，因此它對應的第二個質心為未激活狀態，以此類推，其他位置的閾值大于0.5從而被激活。因此，這個個體的聚類數目為3。

2.2.2 算法流程

下面簡要介紹PSO算法流程：

1）在[0，1]范圍內初始化每個粒子的激活閾值。

2）在每個維度的變量動態范圍的10%-20%左右隨機初始化每個粒子的速度。

3）對于種群中的每一個粒子，提取聚類中心，并將每個對象分配給特定的集群中心形成集群，然后計算適應度。

4）更新全局與局部最優解，根據如下公式（1）與公式（2）更新粒子的速度與位置。

其中，[vkid]表示第k次迭代粒子i速度矢量的第d維分量; [xkid]表示第k次迭代粒子i位置矢量的第d維分量;[c1]，[c2]表示加速度常數;[r1]，[r2]表示兩個隨機參數，取值范圍[0，1];[ω]表示慣性權重。粒子i的歷史最優解用pbesti=（pbesti1， pbesti2，…， pbestid）表示，整個群體找到的已知最優解用gbest=（ gbest1， gbest2，…， gbestd）表示。

5）循環執行步驟3）與步驟4），直到從全局獲得最佳的集群分區，達到最終終止條件時獲得最終解決方案，該條件為所需的最大迭代次數。

3 單指標實驗分析

本文首先研究了多種內部指標在聚類優化中的評價能力。基于PSO的聚類測試實驗數據參數設置如表2所示：

用于單指標實驗的6份經典數據集信息如表3所示。其中包括用于二分類的經典數據集breastcancer、banknotes，常用于分類學習的標準數據集iris、wine，多變量分類數據集faults，以及雙月數據集half-ring。

下面將各個指標值做了標準化計算繪制于同一坐標系中，具體標準化公式如下所示：

[nindexi=indexi/max（index1，index2，...，indexL）] （3）

其中，[L]表示測試的指標總數，[indexi]表示當前指標值。

圖2是以wine數據集為例，以迭代代數為橫坐標，以CH指標越大越好為PSO聚類算法的優化目標下，得到的最優解對應各個內外部指標根據標準化公式計算得到的相對值為縱坐標繪制的迭代變化趨勢圖，用于觀察每一個內部指標在聚類評價時的表現。

當外部指標已經達到最優值的時候單內部指標評價并沒有達到最優，如圖2（a）中的CH指標等，而當內部指標評價達到最優的時候，外部指標甚至僅有0.5的表現，例如圖2（b）與（c）等。這個結果反映出了單一內部指標在找到較優的聚類解時，其對解質量好壞的區分能力不足，單一指標值的優劣不一定代表聚類質量的優劣， 單內部指標指導下的聚類存在缺陷。

4 多指標評價聚類優化投票評價策略

為了更加合理地利用指標的指示能力，本文提出多指標評價的聚類優化投票評價策略。

具體做法就是在粒子群算法的迭代過程中，把傳統的根據單一內部指標計算適應度進行粒子更新的步驟，更改為多指標評價的方式。7個內部指標作為選擇更優解的7個評委，分別對所有解進行自己獨立的評價，根據指標值的大小完成評價，類似于投票，將自己的一票投給各自認為更好的解，根據解所得到的票數多少，確定局部最優解，再與全局最優解進行對比，從而確定全局最優解。

步驟1：初始化方式與PSO算法相同。此外，初始化7個指標評價信息indexi（i=1，…，7）;記錄所有個體i的pbesti都為初始解xi;

步驟2：進入算法迭代過程：

while（迭代次數小于最大迭代次數）do {

a.采用PSO迭代過程更新種群。對于每一個粒子i，根據指標公式計算得到7個新的指標值indexj（j=1，…，7）;

b.初始化當前種群的最優個體號bi = 0，初始化全局最優gbest的7個指標值indexn（n=1，…，7）;

c.所有指標對解質量優化與否進行評價：

indexi與計算得到的指標值indexj進行比較，CH、Dunn、SIL、GD33、GD53值較大的個體得到對應指標的支持，DB、CS值較小的個體得到對應指標的支持，更新得到對應指標支持的評價信息indexi，未得到支持的評價信息不做更新;

d.匯總多指標評價結果：①超過一半的內部指標（≥4）認為解質量變優則用當前解替換pbest;

②超過一半的內部指標（≥4）認為當前解優于全局最優解，則將當前個體的個體號作為當前種群的最優個體號，bi = 當前個體號，同時更新當前種群最優內部指標indexn（n=1，…，7）， bi個體更新為全局最優指代gbest;

}

end while

5 實驗測試與比較

5.1 實驗數據

為增加不同分布類型的數據拓展算法綜合性能測試，本實驗除了表3中標準數據集UCI中的經典數據與多變量數據、環形數據，還使用了如表4所示的人工生成數據，其中50d4c、50d10c、100d4c三份數據集用于高維空間的測試，是以高維度創建的橢圓形簇;2d4c、2d10c、2d20c、10d20c是由標準聚類模型生成的聚類。

5.2 實驗設置

本實驗測試了PSO聚類算法，并加入本文提出的多指標評價方法進行實驗測試，對比其分別使用單指標CH，Dunn和SIL進行優化的結果。外部指標AR、FM、Jaccard用于聚類優化算法的評價對比標準。

5.3 結果對比與分析

為展示多指標評價這一步驟的加入對聚類算法的影響，下面將基于PSO的聚類分別對比增加了多指標評價步驟的PSO聚類，仍然以三個外部指標作為對比標準。表5是多指標評價PSO聚類優化算法與單指標PSO聚類算法的外部指標對比，以CH、Dunn、SIL指標為例。

觀察單指標聚類的外部指標結果，可以發現在單指標的指導聚類下，部分數據集的聚類結果十分不理想，例如：表5中transfution、banknotes等數據集，3個外部指標的評價未到達0.6，甚至僅有0.11的評價。而且，單指標指導聚類在不同數據集的測試中表現也較為不穩定。

最后，綜合觀察表5，可以很清晰地看出，13份數據集中，11份數據集（84.62%的數據集）的聚類結果外部指標值在加入多指標評價后大于未加入該步驟的聚類方法的外部指標，這表示多指標評價機制在提高聚類的準確度上具有優勢，有助于優化聚類，且面對多樣化的數據集，包括：標準數據集、人工生成數據集，多指標評價機制的加入都大大提高了聚類優化能力。

為了進一步分析算法迭代收斂情況，圖3給出了iris數據集的多指標評價PSO與單指標（CH、Dunn、SIL）評價的PSO算法的最優解在外部指標ARI下的變化趨勢對比圖。圖中可以發現，單指標ARI指標值僅在0.7左右，而多指標綜合評價下的聚類結果相對比單指標的聚類結果更優，達到了0.9的效果，與單指標的結果對比可以更快獲得更優的結果。加入多指標評價策略的PSO收斂速度更快，結果也優于相同迭代次數下的PSO算法。

綜上可以認為：多指標綜合評價下的聚類結果在準確率與尋優效率上得到了理想提高。

6 結束語

多指標評價粒子群自適應聚類優化算法通過多指標評價機制與粒子群聚類算法的結合，提高粒子群聚類算法的聚類準確度，此外，實驗結果還發現，加入多指標評價能有效改善單指標對聚類的單一化指導，讓數據從歷史解過程中向所屬類別靠攏。后續，在不影響算法準確率的基礎上提高算法的效率問題是重點需要研究的內容。

參考文獻：

[1] 姚麗娟，羅可，孟穎.一種基于粒子群的聚類算法[J].計算機工程與應用，2012，48（13）：150-153，175.

[2] 沐燕舟，丁衛平，高峰，等.基于自適應PSO的改進K-means算法及其在電子病歷聚類分析應用[J].計算機與數字工程，2019，47（8）：1861-1865.

[3] Omran M G， Engelbrecht A P， Salman A.Image classification using particle swarm optimization[C]//Proc of the 4th Asia-Pacific Conference on Simulated Evolution and Learning，2002：370-374.

[4] Elhabyan R S， Yagoub M C E.PSO-HC：Particle swarm optimization protocol for hierarchical clustering in Wireless Sensor Networks[C]//International Conference on Collaborative Computing： Networking.IEEE，2015.

[5] Santar Pal Singh，Subhash Chander Sharma.PEECA：PSO-Based energy efficient clustering algorithm for wireless sensor networks[C]// International Journal of Computer Network and Information Security，2017，5（9）：31-37.

[6] Kaur T，Kumar D.Particle swarm optimization-based unequal and fault tolerant clustering protocol for wireless sensor networks[J].IEEE Sensors Journal，2018，18（11）：4614-4622.

[7] Vidyadhari C，Sandhya N，Premchand P.Particle grey wolf optimizer （PGWO） algorithm and semantic word processing for automatic text clustering[J].International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems，2019，27（2）：201-223.

[8] Caliński T，Harabasz J.A dendrite method for cluster analysis[J].Communications in Statistics，1974，3（1）：1-27.

[9] Dunn J C.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J].Journal of Cybernetics，1973，3（3）：32-57.

[10] Rousseeuw P J.Silhouettes：a graphical aid to the interpretation and validation of cluster analysis[J].Journal of Computational and Applied Mathematics，1987（20）：53-65.

[11] Davies D L，Bouldin D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1979，PAMI-1（2）：224-227.

[12] Chou C H，Su M C，Lai E.A new cluster validity measure and its application to image compression[J].Pattern Analysis and Applications，2004，7（2）：205-220.

[13] Lord E，Diallo A B，Makarenkov V.Classification of bioinformatics workflows using weighted versions of partitioning and hierarchical clustering algorithms[J].BMC Bioinformatics，2015，16（1）：1-19.

[14] Rathore P，Ghafoori Z，Bezdek J C，et al.Approximating dunn's cluster validity indices for partitions of big data[J].IEEE Transactions on Cybernetics，2019，49（5）：1629-1641.

[15] Xu R，Xu J，Wunsch D C.A comparison study of validity indices on swarm-intelligence-based clustering[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B （Cybernetics），2012，42（4）：1243-1256.

[16] Hang W L，Choi K S，Wang S T.Synchronization clustering based on central force optimization and its extension for large-scale datasets[J].Knowledge-Based Systems，2017，118：31-44.

[17] Kim M，Ramakrishna R S.New indices for cluster validity assessment[J].Pattern Recognition Letters，2005，26（15）：2353-2363.

[18] Rand W M.Objective criteria for the evaluation of clustering methods[J].Journal of the American Statistical Association，1971，66（336）：846-850.

[19] Halkidi M，Batistakis Y，Vazirgiannis M.On clustering validation techniques[J].Journal of Intelligent Information Systems，2001，17（2/3）：107-145.

[20] Fowlkes E B，Mallows C L.A method for comparing two hierarchical clusterings[J].Journal of the American Statistical Association，1983，78（383）：553-569.

[21] Chen G B，Song A，Zhang C J，et al.Automatic clustering approach based on particle swarm optimization for data with arbitrary shaped clusters[C]//2016 Seventh International Conference on Intelligent Control and Information Processing （ICICIP）.December 1-4，2016，Siem Reap.IEEE，2016：41-48.

【通聯編輯：謝媛媛】