基于多指標(biāo)投票的粒子群聚類優(yōu)化算法

李瑞珠 劉錫鵬

摘要：針對不同的數(shù)據(jù)特點(diǎn)，已有多種用于算法優(yōu)化的聚類評價指標(biāo)被提出。大量數(shù)據(jù)測試發(fā)現(xiàn)，僅使用單一評價指標(biāo)無法可靠地體現(xiàn)數(shù)據(jù)的聚類劃分優(yōu)劣，傳統(tǒng)的單一指標(biāo)聚類優(yōu)化算法在聚類準(zhǔn)確度上還有待提高。一種新型的多指標(biāo)投票評價策略被提出，并應(yīng)用于粒子群聚類優(yōu)化算法中。多指標(biāo)投票評價的設(shè)計(jì)思路是依靠過半數(shù)的評價指標(biāo)對解的優(yōu)劣進(jìn)行判定，從而避免單一指標(biāo)的錯誤評價影響優(yōu)化算法中的群體更新。經(jīng)多份數(shù)據(jù)測試，與單指標(biāo)評價的聚類算法進(jìn)行對比，多指標(biāo)評價粒子群聚類優(yōu)化算法獲得更優(yōu)的聚類結(jié)果。

關(guān)鍵詞：多指標(biāo)投票;粒子群算法;聚類優(yōu)化;單指標(biāo);指標(biāo)評價

中圖分類號：TP301.6? ? ? 文獻(xiàn)標(biāo)識碼：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 背景

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

基于粒子群優(yōu)化（Particle Swarm Optimization， PSO）的聚類算法已在UCI標(biāo)準(zhǔn)數(shù)據(jù)集iris與wine上做了測試，并與K-means算法、粒子群 K-means算法進(jìn)行對比[1]，對比結(jié)果仍可優(yōu)化。爾后，一種自適應(yīng)慣性權(quán)重函數(shù)對粒子群算法進(jìn)行動態(tài)調(diào)整的設(shè)計(jì)被提出，并融入K-means算法，幫助初始化聚類中心，應(yīng)用于電子病歷聚類分析，提高了聚類準(zhǔn)確率和效率[2]。

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

本文對7種常用的聚類內(nèi)部指標(biāo)，與4個外部指標(biāo)進(jìn)行聚類分析比較，通過對7份經(jīng)典數(shù)據(jù)集的聚類分析發(fā)現(xiàn)單一指標(biāo)值的優(yōu)劣不一定代表聚類質(zhì)量的優(yōu)劣，因此認(rèn)為對于目前單指標(biāo)評價的聚類存在缺陷。

為解決單指標(biāo)單一的指導(dǎo)問題，提高結(jié)合基于PSO算法的聚類方法的綜合性能，本文設(shè)計(jì)了多指標(biāo)綜合評價機(jī)制，提出一種基于多指標(biāo)投票綜合評價的粒子群聚類方法，集成多個內(nèi)部指標(biāo)，基于優(yōu)化歷史信息與當(dāng)前種群的解質(zhì)量，自適應(yīng)選擇對當(dāng)前解最合理的聚類評價結(jié)果，并與單指標(biāo)的基于粒子群的聚類算法進(jìn)行多數(shù)據(jù)集實(shí)驗(yàn)測試對比。實(shí)驗(yàn)數(shù)據(jù)表明，多指標(biāo)綜合評價機(jī)制的加入能有效提高聚類的準(zhǔn)確度，相較單指標(biāo)評價，多指標(biāo)評價表現(xiàn)更優(yōu)。

2 相關(guān)工作

2.1 聚類有效性指標(biāo)

內(nèi)部指標(biāo)的選擇有很多，本文選擇應(yīng)用較為廣泛的、針對類間距與類內(nèi)距的7個指標(biāo)，如表1所示。

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

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

2.2 粒子群聚類算法

本文采用基于粒子群聚類算法[21]，結(jié)合6份經(jīng)典數(shù)據(jù)集，進(jìn)行聚類測試，分析聚類測試結(jié)果，計(jì)算7個內(nèi)部指標(biāo)，并計(jì)算該聚類結(jié)果與標(biāo)記數(shù)據(jù)對比獲得的3個外部指標(biāo)，驗(yàn)證單指標(biāo)聚類存在的缺陷。

2.2.1 編碼方案

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

[Zi=（Ti1，Ti2，...，TiKmax，mi1，mi2，...，miKmax）]，[d]為數(shù)據(jù)維度數(shù)，[mij]是簇中心的坐標(biāo)向量，[Tij（j=1，...，Kmax）]是得到類別質(zhì)心點(diǎn)的激活閾值。如果[Tij]大于0.5，則對應(yīng)簇的質(zhì)心點(diǎn)[mij]被激活，否則不被激活。

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

2.2.2 算法流程

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

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

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

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

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

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

5）循環(huán)執(zhí)行步驟3）與步驟4），直到從全局獲得最佳的集群分區(qū)，達(dá)到最終終止條件時獲得最終解決方案，該條件為所需的最大迭代次數(shù)。

3 單指標(biāo)實(shí)驗(yàn)分析

本文首先研究了多種內(nèi)部指標(biāo)在聚類優(yōu)化中的評價能力。基于PSO的聚類測試實(shí)驗(yàn)數(shù)據(jù)參數(shù)設(shè)置如表2所示：

用于單指標(biāo)實(shí)驗(yàn)的6份經(jīng)典數(shù)據(jù)集信息如表3所示。其中包括用于二分類的經(jīng)典數(shù)據(jù)集breastcancer、banknotes，常用于分類學(xué)習(xí)的標(biāo)準(zhǔn)數(shù)據(jù)集iris、wine，多變量分類數(shù)據(jù)集faults，以及雙月數(shù)據(jù)集half-ring。

下面將各個指標(biāo)值做了標(biāo)準(zhǔn)化計(jì)算繪制于同一坐標(biāo)系中，具體標(biāo)準(zhǔn)化公式如下所示：

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

其中，[L]表示測試的指標(biāo)總數(shù)，[indexi]表示當(dāng)前指標(biāo)值。

圖2是以wine數(shù)據(jù)集為例，以迭代代數(shù)為橫坐標(biāo)，以CH指標(biāo)越大越好為PSO聚類算法的優(yōu)化目標(biāo)下，得到的最優(yōu)解對應(yīng)各個內(nèi)外部指標(biāo)根據(jù)標(biāo)準(zhǔn)化公式計(jì)算得到的相對值為縱坐標(biāo)繪制的迭代變化趨勢圖，用于觀察每一個內(nèi)部指標(biāo)在聚類評價時的表現(xiàn)。

當(dāng)外部指標(biāo)已經(jīng)達(dá)到最優(yōu)值的時候單內(nèi)部指標(biāo)評價并沒有達(dá)到最優(yōu)，如圖2（a）中的CH指標(biāo)等，而當(dāng)內(nèi)部指標(biāo)評價達(dá)到最優(yōu)的時候，外部指標(biāo)甚至僅有0.5的表現(xiàn)，例如圖2（b）與（c）等。這個結(jié)果反映出了單一內(nèi)部指標(biāo)在找到較優(yōu)的聚類解時，其對解質(zhì)量好壞的區(qū)分能力不足，單一指標(biāo)值的優(yōu)劣不一定代表聚類質(zhì)量的優(yōu)劣， 單內(nèi)部指標(biāo)指導(dǎo)下的聚類存在缺陷。

4 多指標(biāo)評價聚類優(yōu)化投票評價策略

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

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

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

步驟2：進(jìn)入算法迭代過程：

while（迭代次數(shù)小于最大迭代次數(shù)）do {

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

b.初始化當(dāng)前種群的最優(yōu)個體號bi = 0，初始化全局最優(yōu)gbest的7個指標(biāo)值indexn（n=1，…，7）;

c.所有指標(biāo)對解質(zhì)量優(yōu)化與否進(jìn)行評價：

indexi與計(jì)算得到的指標(biāo)值indexj進(jìn)行比較，CH、Dunn、SIL、GD33、GD53值較大的個體得到對應(yīng)指標(biāo)的支持，DB、CS值較小的個體得到對應(yīng)指標(biāo)的支持，更新得到對應(yīng)指標(biāo)支持的評價信息indexi，未得到支持的評價信息不做更新;

d.匯總多指標(biāo)評價結(jié)果：①超過一半的內(nèi)部指標(biāo)（≥4）認(rèn)為解質(zhì)量變優(yōu)則用當(dāng)前解替換pbest;

②超過一半的內(nèi)部指標(biāo)（≥4）認(rèn)為當(dāng)前解優(yōu)于全局最優(yōu)解，則將當(dāng)前個體的個體號作為當(dāng)前種群的最優(yōu)個體號，bi = 當(dāng)前個體號，同時更新當(dāng)前種群最優(yōu)內(nèi)部指標(biāo)indexn（n=1，…，7）， bi個體更新為全局最優(yōu)指代gbest;

}

end while

5 實(shí)驗(yàn)測試與比較

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

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

5.2 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)測試了PSO聚類算法，并加入本文提出的多指標(biāo)評價方法進(jìn)行實(shí)驗(yàn)測試，對比其分別使用單指標(biāo)CH，Dunn和SIL進(jìn)行優(yōu)化的結(jié)果。外部指標(biāo)AR、FM、Jaccard用于聚類優(yōu)化算法的評價對比標(biāo)準(zhǔn)。

5.3 結(jié)果對比與分析

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

觀察單指標(biāo)聚類的外部指標(biāo)結(jié)果，可以發(fā)現(xiàn)在單指標(biāo)的指導(dǎo)聚類下，部分?jǐn)?shù)據(jù)集的聚類結(jié)果十分不理想，例如：表5中transfution、banknotes等數(shù)據(jù)集，3個外部指標(biāo)的評價未到達(dá)0.6，甚至僅有0.11的評價。而且，單指標(biāo)指導(dǎo)聚類在不同數(shù)據(jù)集的測試中表現(xiàn)也較為不穩(wěn)定。

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

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

綜上可以認(rèn)為：多指標(biāo)綜合評價下的聚類結(jié)果在準(zhǔn)確率與尋優(yōu)效率上得到了理想提高。

6 結(jié)束語

多指標(biāo)評價粒子群自適應(yīng)聚類優(yōu)化算法通過多指標(biāo)評價機(jī)制與粒子群聚類算法的結(jié)合，提高粒子群聚類算法的聚類準(zhǔn)確度，此外，實(shí)驗(yàn)結(jié)果還發(fā)現(xiàn)，加入多指標(biāo)評價能有效改善單指標(biāo)對聚類的單一化指導(dǎo)，讓數(shù)據(jù)從歷史解過程中向所屬類別靠攏。后續(xù)，在不影響算法準(zhǔn)確率的基礎(chǔ)上提高算法的效率問題是重點(diǎn)需要研究的內(nèi)容。

參考文獻(xiàn)：

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

[2] 沐燕舟，丁衛(wèi)平，高峰，等.基于自適應(yīng)PSO的改進(jìn)K-means算法及其在電子病歷聚類分析應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程，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，F(xiàn)uzziness 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.

【通聯(lián)編輯：謝媛媛】