基于多任務(wù)協(xié)同的粒子群聚類優(yōu)化算法

顏志鵬

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州 510006)

0 引言

多任務(wù)學(xué)習(xí)(Multi-Task Learning)[1-2]是機(jī)器學(xué)習(xí)，特別是遷移學(xué)習(xí)中的一個(gè)子領(lǐng)域。多任務(wù)優(yōu)化(Multi-Task Optimization)[3-5]應(yīng)用多任務(wù)學(xué)習(xí)優(yōu)化，以研究如何有效地同時(shí)解決多個(gè)優(yōu)化問題。在多任務(wù)學(xué)習(xí)中，多個(gè)相關(guān)學(xué)習(xí)任務(wù)使用(部分)共享的模型表示并同時(shí)進(jìn)行訓(xùn)練。子問題之間也是相互關(guān)聯(lián)的，通過一些共享因素實(shí)現(xiàn)知識(shí)遷移從而有效促進(jìn)單個(gè)任務(wù)的學(xué)習(xí)效率和泛化能力。

多任務(wù)優(yōu)化和多目標(biāo)優(yōu)化[6-7]之間有相似的地方，但存在根本性的差異。多任務(wù)優(yōu)化的目的是利用種群間個(gè)體在多個(gè)不同任務(wù)之間同時(shí)搜索各個(gè)目標(biāo)值對(duì)應(yīng)的最優(yōu)值，利用潛在的遺傳互補(bǔ)性實(shí)現(xiàn)互相之間的遷移學(xué)習(xí)；多目標(biāo)優(yōu)化則試圖解決同一個(gè)任務(wù)下競(jìng)爭(zhēng)目標(biāo)之間的沖突，尋找帕累托前沿上所有的解[8]。如圖1的最小值優(yōu)化問題，在多目標(biāo)優(yōu)化中，P2、P3、P4和P5組成了帕累托前沿，它們被認(rèn)為是當(dāng)前解集合中互不支配的最優(yōu)解；而在多任務(wù)進(jìn)化中，P1、P2、P5和P6組成了最優(yōu)解，因?yàn)檫@些解都各自有一個(gè)目標(biāo)值達(dá)到了最小值。

圖1 動(dòng)態(tài)演示程序界面

多任務(wù)優(yōu)化最早用于進(jìn)化算法中的是多任務(wù)進(jìn)化算法(Evolutionary Multi-Tasking)[9]，它將多任務(wù)學(xué)習(xí)的方法結(jié)合進(jìn)化算法來解決各類優(yōu)化問題。Gupta等人[9]提出了多因子進(jìn)化算法MFEA(Multi-Factorial Evolution Algorithm)，在測(cè)試了多因子進(jìn)化算法效果后驗(yàn)證了多因子進(jìn)化算法的有效性，證明新算法比單一目標(biāo)優(yōu)化更快收斂，更容易找到全局最優(yōu)值。多因子進(jìn)化后來得到了發(fā)展，不斷有學(xué)者改進(jìn)算法，也衍生出了更多新算法。Gupta等人[10]又將多因子進(jìn)化算法中單任務(wù)只有單個(gè)目標(biāo)拓展到每個(gè)任務(wù)具有多個(gè)目標(biāo)。Liaw和Ting[11]模仿了生物共生關(guān)系為進(jìn)化算法提出了一個(gè)通用的框架，并表明其性能可能比多因子進(jìn)化算法更好。Cheng等人[12]提出一種多任務(wù)協(xié)同進(jìn)化算法(Co-Evolutionary Multi-Tasking)。多任務(wù)優(yōu)化算法可以同時(shí)優(yōu)化多個(gè)目標(biāo)，這點(diǎn)和協(xié)同進(jìn)化算法類似。

聚類通過對(duì)沒有標(biāo)簽的數(shù)據(jù)劃分為若干相似對(duì)象組成的多個(gè)簇或類，使得同一類中對(duì)象間的相似度最大化，不同類中對(duì)象間的相似度最小化。有很多學(xué)者提出了基于進(jìn)化算法進(jìn)行的聚類，它們大多需要根據(jù)一個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化，包括一些經(jīng)典的聚類內(nèi)部指標(biāo)。多目標(biāo)優(yōu)化也被應(yīng)用于聚類問題，例如基于2個(gè)目標(biāo)優(yōu)化的MOCK(Multi-Objective Clustering with Automatic K-determination)算法[13-14]和基于多目標(biāo)進(jìn)化算法的多距離度量聚類[15]。但多目標(biāo)聚類優(yōu)化算法為找到帕累托前沿的所有解使用的優(yōu)化目標(biāo)往往需要互為沖突，找到的解個(gè)數(shù)越多，對(duì)優(yōu)質(zhì)解的篩選難度也越大。多任務(wù)學(xué)習(xí)可以將對(duì)不同指標(biāo)的優(yōu)化視作不同的任務(wù)，分別找到各個(gè)任務(wù)下最優(yōu)個(gè)體并用專家知識(shí)找出最適合數(shù)據(jù)集的那個(gè)聚類指標(biāo)，對(duì)結(jié)果的篩選比起基于多目標(biāo)的方法更容易。

本文針對(duì)基于優(yōu)化算法的聚類和其指標(biāo)選擇問題以自動(dòng)聚類粒子群優(yōu)化ACPSO(Automatic Clustering Approach Based on PSO)[16]為基礎(chǔ)算法，提出了基于多任務(wù)協(xié)同的粒子群聚類優(yōu)化算法。算法通過對(duì)多個(gè)聚類指標(biāo)優(yōu)化任務(wù)的學(xué)習(xí)，可以一次性得到多個(gè)指標(biāo)的優(yōu)化結(jié)果。實(shí)驗(yàn)分析發(fā)現(xiàn)采用多任務(wù)協(xié)同優(yōu)化的方法，可以有效地得到更優(yōu)的聚類結(jié)果。

1 背景

1.1 粒子群算法

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法[17-18]是一種模擬鳥群的演化算法，通過記錄種群中每一個(gè)粒子經(jīng)過的歷史最優(yōu)位置和當(dāng)前位置來探索全局最優(yōu)解。本文算法使用的是局部鄰域粒子群算法，即采用環(huán)形拓?fù)涞牧Ｗ尤航Y(jié)構(gòu)[19]。粒子在迭代中的更新公式為：

xij(t+1)=xij(t)+vij(t+1)

(1)

vij(t+1)=ωvij+c1r1(pbestij-xij(t)+c2r2(lbestij-xij(t)

(2)

其中xij(i=1，…，m;j=1，…，d)和vij(i=1，…，m;j=1，…，d)分別對(duì)應(yīng)粒子的位置和速度，m為種群中的粒子個(gè)數(shù)，d為數(shù)據(jù)維度，t為算法迭代次數(shù)，t從0開始算法逐次對(duì)整個(gè)粒子群的速度和位置向量進(jìn)行迭代優(yōu)化，r1和r2是0到1之間的隨機(jī)數(shù)。pbesti為粒子i自身的歷史最優(yōu)位置，lbesti為粒子i與其鄰近的粒子組成的區(qū)域局部最優(yōu)位置。在頭尾相連的環(huán)形拓?fù)浣Y(jié)構(gòu)的粒子群中，局部區(qū)域由該粒子和其前后相鄰的2個(gè)粒子組成。w為慣性系數(shù)控制粒子位置更新時(shí)pbest和lbest的權(quán)重。較大的慣性系數(shù)有利于全局搜索，而較小的慣性系數(shù)一個(gè)有利局部搜索，c1和c2為加速常數(shù)，分別控制粒子朝全局最優(yōu)和局部最優(yōu)收斂的速度。粒子群算法可以用作聚類，如文獻(xiàn)[20]提出的使用量子行為粒子群的動(dòng)態(tài)聚類算法。

1.2 聚類評(píng)價(jià)指標(biāo)

聚類集合的優(yōu)劣評(píng)價(jià)指標(biāo)，根據(jù)是否需要知道真實(shí)的樣本分類標(biāo)簽，分為內(nèi)部指標(biāo)和外部指標(biāo)。通過對(duì)數(shù)據(jù)分布的進(jìn)一步研究，人們提出了一些量度數(shù)據(jù)分布特點(diǎn)的指標(biāo)，用于聚類算法對(duì)聚類集合的優(yōu)劣評(píng)價(jià)。

1.2.1 聚類內(nèi)部指標(biāo)

內(nèi)部指標(biāo)通常用于評(píng)估聚類質(zhì)量或者簇劃分的效果，可以用作優(yōu)化算法聚類中的目標(biāo)函數(shù)。本文中使用的內(nèi)部指標(biāo)包括分析簇劃分提出的較低計(jì)算復(fù)雜度的CH(Calinski-Harabasz)指標(biāo)[21]，研究模糊聚類算法提出的Dunn指標(biāo)[22]，以及聚類有效性的評(píng)估方法SIL(Silhouette Statistic)指標(biāo)[23]。下面給出各個(gè)指標(biāo)的計(jì)算公式。

(1)CH指標(biāo)

(3)

(2)Dunn指標(biāo)

(4)

其中Ci代表簇i中的樣本數(shù)據(jù)點(diǎn)組成的集合，D(Ci，Cj)代表不同類別簇i和j間的距離，該值是兩個(gè)簇中最靠近的數(shù)據(jù)點(diǎn)之間的距離，公式表達(dá)如下：

(5)

δ(Cl)為簇l的兩個(gè)最遠(yuǎn)距離點(diǎn)間的距離：

(6)

Dunn指標(biāo)對(duì)數(shù)據(jù)噪聲比較敏感，數(shù)值越大傾向于聚類效果越好。

(3)SIL指標(biāo)

(7)

(8)

(9)

(10)

其中sj代表數(shù)據(jù)點(diǎn)xj的輪廓寬度(Silhouette Width)，數(shù)據(jù)點(diǎn)x到它所屬簇i的其他數(shù)據(jù)點(diǎn)的平均距離為aj，x到其他類別數(shù)據(jù)點(diǎn)的最小距離為bj。

SIL指標(biāo)為正數(shù)或者負(fù)數(shù)分別表示相應(yīng)的劃分分別是很好的聚類或者錯(cuò)誤的聚類。SIL指標(biāo)在零附近被認(rèn)為對(duì)數(shù)據(jù)沒有明確區(qū)分。SIL指標(biāo)越大傾向于聚類效果越好。

1.2.2 聚類外部指標(biāo)

聚類外部指標(biāo)的計(jì)算需要知道真實(shí)分類情況，因此往往用于檢驗(yàn)聚類的實(shí)際效果。本文使用聚類外部指標(biāo)調(diào)整蘭德系數(shù)ARI(Adjusted Rand Index)[24]作為聚類結(jié)果的質(zhì)量評(píng)價(jià)。ARI是對(duì)Rand提出的聚類評(píng)價(jià)系數(shù)蘭德系數(shù)(Rand Index)[25]改進(jìn)后的指標(biāo)，使得聚類結(jié)果在隨機(jī)產(chǎn)生的情況下指標(biāo)能接近于零。ARI假設(shè)隨機(jī)模型采用廣義超幾何分布，將數(shù)據(jù)集N個(gè)樣本真實(shí)劃分表示為P，根據(jù)算法聚類得到的劃分為Q，Xi和Xj為數(shù)據(jù)集的兩個(gè)不同樣本?，F(xiàn)在按照這兩個(gè)樣本在劃分P和C的分布得到以下4種不同的情形：

(1)Xi和Xj在Q中屬于同一個(gè)簇，同時(shí)它們?cè)赑中也屬于同一個(gè)類別；

(2)Xi和Xj在Q中屬于同一個(gè)簇，但它們?cè)赑中屬于不同的類別；

(3)Xi和Xj在Q中屬于不同的簇，但它們?cè)赑中屬于同一個(gè)類別；

(4)Xi和Xj在Q中屬于不同的簇，它們?cè)赑中也不屬于同一個(gè)類別。

將以上四種情形成對(duì)的樣本數(shù)統(tǒng)計(jì)并表示為a，b，c和d，可得ARI值：

(11)

ARI為1表示兩個(gè)劃分之間的完美一致性，值越小表示它們之間的差異越大。其值也可以為負(fù)，表示比隨機(jī)得到的分類效果還差。

2 基于多任務(wù)協(xié)同的粒子群聚類優(yōu)化

這部分首先描述本文提出的基于多任務(wù)協(xié)同的ACPSO算法，簡(jiǎn)稱MT-CACPSO的粒子編碼及其初始化方法，然后介紹算法聚類時(shí)的聚類規(guī)則。最后給出算法的多任務(wù)協(xié)同實(shí)現(xiàn)具體流程。

2.1 種群個(gè)體的編碼

粒子被編碼為Kmax+Kmax*d維的向量，其中d是樣本點(diǎn)的維度，Kmax是程序定義的聚類樣本簇?cái)?shù)的最大值。對(duì)于每個(gè)粒子的前Kmax個(gè)值分別代表后續(xù)Kmax個(gè)類別中心點(diǎn)的激活閾值。如果該值大于0.5，則對(duì)應(yīng)簇的中心點(diǎn)被激活，相當(dāng)于該簇被納入聚類的計(jì)算，否則不被激活也就是不納入計(jì)算。如果該值在優(yōu)化過程中被修改為大于1或?yàn)樨?fù)數(shù)，則重置該值為1或0，如果得到的中心點(diǎn)數(shù)量小于設(shè)置的最小類別數(shù)Kmin，則隨機(jī)選取足夠的激活閾值改為大于0.5的隨機(jī)值。例如，對(duì)于一個(gè)維度d為2，最大聚類類別數(shù)Kmax為4的個(gè)體，前面4個(gè)值為激活閾值，第二個(gè)位置0.4小于0.5，因此它對(duì)應(yīng)的第二個(gè)中心為未激活狀態(tài)，以此類推，其他位置的閾值大于0.5從而被激活。因此，這個(gè)個(gè)體的聚類簇?cái)?shù)目為3。

2.2 種群的初始化

每個(gè)個(gè)體的激活閾值控制著聚類數(shù)目，為了讓種群的所有個(gè)體不會(huì)因隨機(jī)性出現(xiàn)偏向，在初始化時(shí)會(huì)讓個(gè)體從最小聚類數(shù)Kmin到Kmax均勻分布，因此要控制激活閾值部分的編碼，其余位置則隨機(jī)設(shè)置為數(shù)據(jù)各維度所處的范圍內(nèi)。種群所有個(gè)體的初始聚類數(shù)K在Kmin到Kmax間呈均勻分布。

2.3 聚類規(guī)則

傳統(tǒng)的粒子群優(yōu)化方式應(yīng)用于聚類優(yōu)化時(shí)，對(duì)于聚類形態(tài)非圓形的聚類問題，效果不佳。文獻(xiàn)[16]提出NMP(Nearest Multiple Prototypes)規(guī)則用于提升聚類優(yōu)化中的性能。

首先，每個(gè)樣本被分配到最近的簇中，所有被分配到同一個(gè)簇的樣本組成了一個(gè)候選樣本集。這里，我們把這個(gè)簇稱為這些樣本的一個(gè)未確定簇。然后，對(duì)每一個(gè)簇，從候選樣本集中選一個(gè)最近的樣本，所有簇的這種最近樣本點(diǎn)合并稱為最近樣本集。最后，在最近樣本集中找到一個(gè)樣本，這個(gè)樣本離它所在的未確定簇距離是最近樣本集中最小的，就將該樣本分配到它的未確定簇中。不斷重復(fù)上述步驟直到所有樣本被分配完畢。相比確定樣本所在類別的傳統(tǒng)方法，NMP是一個(gè)動(dòng)態(tài)的過程，更加靈活。

2.4 多任務(wù)協(xié)同優(yōu)化

多任務(wù)協(xié)同優(yōu)化[12]不僅有多任務(wù)的特性，還使用了協(xié)同進(jìn)化讓兩個(gè)子群進(jìn)行交流，而不是對(duì)單個(gè)種群的優(yōu)化。本文對(duì)算法進(jìn)行了調(diào)整，能夠?qū)Ω鄡?yōu)化任務(wù)進(jìn)行優(yōu)化，實(shí)驗(yàn)中的任務(wù)數(shù)等于聚類優(yōu)化任務(wù)中的指標(biāo)個(gè)數(shù)。下文中用集合S表示整個(gè)種群，它由被L個(gè)任務(wù)分割的子種群sk(k=1，2，…，L)組成，即S={s1，s2，…，sL}。

2.4.1 不同優(yōu)化任務(wù)間粒子群的協(xié)同進(jìn)化

在某個(gè)優(yōu)化任務(wù)下的粒子群，如果在對(duì)其指標(biāo)優(yōu)化任務(wù)的搜索陷入停滯時(shí)則激活該步驟進(jìn)行跨任務(wù)的知識(shí)轉(zhuǎn)移，將粒子的位置偏向另一個(gè)被隨機(jī)選中的任務(wù)的全局最優(yōu)位置。

假設(shè)某個(gè)優(yōu)化任務(wù)序號(hào)為k，來自該任務(wù)的種群內(nèi)的某個(gè)粒子為xi(k)，粒子的個(gè)體最優(yōu)值在經(jīng)歷γ1次迭代后依然沒找到更優(yōu)的個(gè)體最優(yōu)值，將對(duì)該粒子編碼執(zhí)行下面的更新操作：

(12)

其中，r1和r2都是[0，1]之間的隨機(jī)變量，r3∈[1，L]，且r3≠k，而gbest(r3)表示另一個(gè)隨機(jī)選中的任務(wù)r3的全局最優(yōu)位置，j=1，2，…，d(d表示粒子編碼的維度個(gè)數(shù))。如果粒子更新后得到的優(yōu)化指標(biāo)比粒子的歷史最優(yōu)值更好則更新歷史最優(yōu)位置，否則不更新。

2.4.2 優(yōu)化任務(wù)內(nèi)的粒子間雜交

某個(gè)種群所代表的優(yōu)化任務(wù)在γ2次迭代后依然沒找到更優(yōu)的全局最優(yōu)位置時(shí)會(huì)隨機(jī)從該種群內(nèi)抽取2個(gè)粒子進(jìn)行雜交，如果雜交得到的后代的適應(yīng)值大于當(dāng)前粒子的適應(yīng)值，則用雜交得到的后代替換父代。雜交的更新公式如下：

(13)

(14)

2.5 MT-CACPSO具體流程

本算法包括4個(gè)主要步驟，下面以最大化問題為例展示算法流程下：

輸入：數(shù)據(jù)特征。

輸出：L個(gè)指標(biāo)下對(duì)應(yīng)的聚類結(jié)果。

a) 讀入數(shù)據(jù)集并做歸一化處理，為L(zhǎng)個(gè)優(yōu)化指標(biāo)產(chǎn)生L個(gè)個(gè)體數(shù)為m的粒子群s1，s2，…，sL并初始化；

b) 評(píng)估更新每個(gè)任務(wù)k下每個(gè)粒子的pbesti和lbesti(i=1，2，…，m)，k=1，2，…，L;

c) 獲取各個(gè)任務(wù)的當(dāng)前的全局最優(yōu)位置gbestk(迭代次數(shù)t←0)，k=1，2，…，L；

e)while(t沒有達(dá)到最大迭代次數(shù))t←t+1；

fork=1，2，…，Ldo

更新完該種群下所有粒子后，獲取任務(wù)k的全局最優(yōu)位置gbestk的適應(yīng)值fk(t)；

if(fk(t)≤fk(t-1))counterk←counterk+1；

if(counterk=γ2)在該任務(wù)粒子群中隨機(jī)抽取2個(gè)粒子根據(jù)公式(13)和(14)進(jìn)行雜交；counterk=0；

f) 輸出各個(gè)任務(wù)的全局最優(yōu)位置作為結(jié)果。

在上述步驟中，共有L個(gè)粒子種群，分別對(duì)應(yīng)前文提到的L個(gè)內(nèi)部聚類指標(biāo)。當(dāng)種群內(nèi)的粒子陷入停滯時(shí)將使用公式(12)更新粒子位置實(shí)現(xiàn)種群間的協(xié)同進(jìn)化。判斷粒子是否停滯需要先設(shè)定一個(gè)系統(tǒng)參數(shù)γ1，當(dāng)某個(gè)粒子經(jīng)歷了γ1次迭代后依然無法獲取到更優(yōu)的適應(yīng)值才執(zhí)行該步驟。此外，某個(gè)粒子群的全局最優(yōu)在經(jīng)歷γ2次迭代后沒有獲得新的全局最優(yōu)位置將在該粒子群內(nèi)進(jìn)行內(nèi)部的雜交。

3 算法實(shí)驗(yàn)測(cè)試

3.1 測(cè)試數(shù)據(jù)集

數(shù)據(jù)集選用了人工數(shù)據(jù)和真實(shí)數(shù)據(jù)，表1中Banknotes和Vertebral Column數(shù)據(jù)集為真實(shí)數(shù)據(jù)集，它們來自UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)集(http://archive.ics.uci.edu/ml/index.html)。

表1 測(cè)試的數(shù)據(jù)集

表1中序號(hào)3到12的數(shù)據(jù)集均為人工數(shù)據(jù)，它們有著不一樣的形狀的簇，是通過由Handl和Knowles提出的簇生成器[13]得到的，生成器為高維的橢圓形簇，長(zhǎng)軸方向上任意分布，2d4c代表這個(gè)數(shù)據(jù)集維度為2，類別數(shù)為4。

3.2 參數(shù)設(shè)置

本實(shí)驗(yàn)比較了3種聚類算法。其中ACPSO是單任務(wù)算法，實(shí)驗(yàn)中分別對(duì)其采用了不同的聚類內(nèi)部指標(biāo)作為優(yōu)化目標(biāo)進(jìn)行測(cè)試。ACPSO的種群規(guī)模為40，本文提出的MT-CACPSO同時(shí)優(yōu)化多個(gè)內(nèi)部指標(biāo)任務(wù)，每個(gè)任務(wù)的種群規(guī)模為40。最大聚類數(shù)Kmax為30，最小聚類數(shù)Kmin為2。慣性系數(shù)w為0.75，加速度常數(shù)c1和c2為2，粒子的最大速度控制在數(shù)據(jù)范圍的20%內(nèi)。系統(tǒng)參數(shù)γ1=γ2=15。

實(shí)驗(yàn)將MFEA算法用于聚類，即多因子進(jìn)化聚類算法。MFEA算法的RMP(Random Mating Probability)控制著不同任務(wù)之間交流程度，取值范圍為(0，1)，值越大則跨任務(wù)間的交流越頻繁[9]。本文實(shí)驗(yàn)中RMP參數(shù)取值為0.3。以上3種算法最大迭代次數(shù)都為2000次，每個(gè)算法都獨(dú)立運(yùn)行10次。

3.3 MT-CACPSO與單任務(wù)算法的結(jié)果比較

ACPSO是先后選取了不同的3個(gè)優(yōu)化目標(biāo)(CH、DUNN、SIL)單獨(dú)運(yùn)行而得到的結(jié)果，MT-CACPSO是一次運(yùn)行后得到的3個(gè)不同優(yōu)化任務(wù)對(duì)應(yīng)的結(jié)果。

表2比較了MT-CACPSO和單任務(wù)的ACPSO的實(shí)驗(yàn)結(jié)果的內(nèi)部指標(biāo)，結(jié)果取10次運(yùn)行的平均值。其中，加粗的結(jié)果為同一個(gè)內(nèi)部指標(biāo)下，兩種算法的優(yōu)勝結(jié)果。多任務(wù)MT-CACPSO算法比單任務(wù)ACPSO算法獲得更多的優(yōu)勝解。例如在CH指標(biāo)上，MT-CACPSO算法在12個(gè)實(shí)例中有7個(gè)實(shí)例找到更優(yōu)的解，而ACPSO算法有6個(gè)實(shí)例找到了更優(yōu)的解，其中主要是在維度相對(duì)低的數(shù)據(jù)集上MT-CACPSO表現(xiàn)更優(yōu)。而在DUNN和SIL指標(biāo)的優(yōu)化中，MT-CACPSO算法獲得更多的最優(yōu)解。在對(duì)DUNN指標(biāo)的優(yōu)化結(jié)果中，MT-CACPSO的優(yōu)化得到的指標(biāo)值大都不低于單任務(wù)ACPSO，只有2d20c例外，在SIL指標(biāo)上大部分?jǐn)?shù)據(jù)集也優(yōu)于ACPSO的優(yōu)化結(jié)果，說明MT-CACPSO在這些指標(biāo)的優(yōu)化任務(wù)上，發(fā)生了不同優(yōu)化任務(wù)間的知識(shí)遷移，從而得到更好的收斂結(jié)果。

表2 ACPSO與MT-CACPSO運(yùn)行結(jié)果的平均內(nèi)部指標(biāo)

續(xù)上表

表3給出了兩種算法的外部聚類指標(biāo)結(jié)果?；诙嗄繕?biāo)的聚類方法[13-14]中得到的帕累托前沿上所有聚類結(jié)果需要進(jìn)行篩選，類似的，由于使用了多個(gè)指標(biāo)，所以采用多任務(wù)的聚類方法也需要引入專家知識(shí)對(duì)結(jié)果進(jìn)行篩選，而且因?yàn)榻饧瘋€(gè)數(shù)只等于優(yōu)化目標(biāo)個(gè)數(shù)，所以篩選難度低于基于多目標(biāo)的方法。通過引入專家知識(shí)，我們將最合適該數(shù)據(jù)集的結(jié)果作為最終的聚類結(jié)果，表格中加粗的結(jié)果表示同一行中最優(yōu)的ARI值。

對(duì)于真實(shí)數(shù)據(jù)集Banknotes和Vertebral Column，MT-CACPSO的CH指標(biāo)優(yōu)化任務(wù)取得了更好的聚類結(jié)果。人工數(shù)據(jù)集2d4c兩個(gè)算法的結(jié)果一樣，在DUNN指標(biāo)優(yōu)化上獲得了最優(yōu)結(jié)果。其余人工數(shù)據(jù)集中MT-CACPSO有6個(gè)更優(yōu)的聚類結(jié)果，ACPSO則是3個(gè)，其中2d10c是SIL優(yōu)化任務(wù)獲得了最好的結(jié)果，其他數(shù)據(jù)集則是CH指標(biāo)優(yōu)化結(jié)果更好。這體現(xiàn)了不同指標(biāo)優(yōu)化對(duì)于同一個(gè)數(shù)據(jù)集的不同影響。

表3 ACPSO與MT-CACPSO運(yùn)行結(jié)果的平均外部指標(biāo)ARI

3.4 MT-CACPSO與多因子進(jìn)化聚類算法的結(jié)果比較

表4和表5比較了MT-CACPSO和多因子進(jìn)化聚類(MFEA)算法的實(shí)驗(yàn)結(jié)果，每個(gè)算法共運(yùn)行了10遍，結(jié)果取十次運(yùn)行的平均值，兩個(gè)多任務(wù)聚類算法都是一次運(yùn)行后得到的3個(gè)不同優(yōu)化任務(wù)對(duì)應(yīng)的結(jié)果。兩種算法都是基于多任務(wù)的聚類算法，該實(shí)驗(yàn)的結(jié)果體現(xiàn)了采用協(xié)同多任務(wù)相對(duì)于多因子進(jìn)化算法的優(yōu)勢(shì)。

表4給出的是兩個(gè)算法結(jié)果的內(nèi)部聚類指標(biāo)，加粗的結(jié)果為同一個(gè)內(nèi)部指標(biāo)下，兩種算法的優(yōu)勝結(jié)果。經(jīng)過對(duì)比，MT-CACPSO在3個(gè)指標(biāo)的優(yōu)化上都獲得了比多因子進(jìn)化聚類算法更多的優(yōu)勝次數(shù)。其中，在3個(gè)指標(biāo)優(yōu)化上MT-CACPSO分別獲得了10、10、11次最優(yōu)解，而多因子進(jìn)化聚類算法是3、7、3次。在CH指標(biāo)優(yōu)化任務(wù)上，MT-CACPSO的結(jié)果優(yōu)越性主要體現(xiàn)于適合使用CH指標(biāo)優(yōu)化的超球形或超橢圓形簇人工數(shù)據(jù)集(序號(hào)3到12)，除2d20c外均取得了最優(yōu)的解。在DUNN指標(biāo)的優(yōu)化上MT-CACPSO只有2d20c和10d20c這2個(gè)實(shí)例沒有取得最優(yōu)解。SIL指標(biāo)優(yōu)化上MT-CACPSO除2d20c外的實(shí)例上都獲得了最優(yōu)解。綜上，使用環(huán)形拓?fù)淞Ｗ尤旱膮f(xié)同多任務(wù)算法獲得了更好的收斂結(jié)果，是比多因子進(jìn)化算法更加容易突破局部最優(yōu)值的多任務(wù)優(yōu)化算法。

表4 多因子進(jìn)化聚類算法與MT-CACPSO運(yùn)行結(jié)果的平均內(nèi)部指標(biāo)

表5中給出了多因子聚類算法和MT-CACPSO的聚類結(jié)果的外部指標(biāo)，加粗的結(jié)果表示同一行中最優(yōu)的ARI值。真實(shí)數(shù)據(jù)集中，MT-CACPSO聚類結(jié)果均取得了最優(yōu)解。人工數(shù)據(jù)集中，除2d4c、10d20c和100d4c外，MT-CACPSO均獲得比多因子進(jìn)化聚類算法更優(yōu)的聚類結(jié)果，其中10d20c則是兩種算法都獲得了完全正確的聚類結(jié)果?？梢钥闯?，基于多任務(wù)協(xié)同的聚類算法的聚類效果優(yōu)于多因子進(jìn)化聚類算法。

表5 MT-CACPSO與多因子進(jìn)化聚類算法結(jié)果的平均外部ARI值

3.5 算法收斂曲線圖

圖2選取了個(gè)別有代表性的數(shù)據(jù)集，并畫出了3個(gè)算法在各個(gè)優(yōu)化指標(biāo)下的收斂曲線，結(jié)果取十次運(yùn)行的平均值。在2d10c的CH指標(biāo)優(yōu)化中，ACPSO在前期的迭代中收斂速度最快，但后續(xù)的迭代中MT-CACPSO通過不同任務(wù)間的交流實(shí)現(xiàn)了局部最小值的突破從而得到了更優(yōu)的CH指標(biāo)結(jié)果。在10d20c數(shù)據(jù)集Dunn優(yōu)化和10d4c數(shù)據(jù)集SIL優(yōu)化中，兩種基于多任務(wù)的聚類算法都在前期迭代中得到了比ACPSO更優(yōu)的目標(biāo)值，而MT-CACPSO的收斂性能又好于多因子聚類算法。

(a) 2d10c CH指標(biāo)收斂曲線

(b) 10d20c Dunn指標(biāo)收斂曲線

(c) 10d4c SIL指標(biāo)收斂曲線

4 結(jié)語

本文中提出了基于多任務(wù)的聚類算法MT-CACPSO，并與單任務(wù)的ACPSO和同樣是基于多任務(wù)優(yōu)化的多因子進(jìn)化聚類算法進(jìn)行了比較。雖然不同內(nèi)部指標(biāo)適用于不同數(shù)據(jù)集，但基于多任務(wù)的聚類算法同時(shí)完成對(duì)3個(gè)不同內(nèi)部指標(biāo)的優(yōu)化后可以用專家知識(shí)從中選出一個(gè)最優(yōu)的聚類結(jié)果。通過與單任務(wù)ACPSO的聚類算法結(jié)果對(duì)比發(fā)現(xiàn)，多任務(wù)聚類算法受益于多個(gè)指標(biāo)的不同環(huán)境，有機(jī)會(huì)通過任務(wù)間的知識(shí)遷移獲得更好的聚類結(jié)果。與多因子進(jìn)化聚類算法的結(jié)果對(duì)比則說明基于協(xié)同多任務(wù)進(jìn)化的聚類算法優(yōu)于基于多因子進(jìn)化的聚類算法。