顏志鵬

(廣東工業(yè)大學計算機學院，廣州 510006)

0 引言

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

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

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

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

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

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

1 背景

1.1 粒子群算法

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法[17-18]是一種模擬鳥群的演化算法，通過記錄種群中每一個粒子經(jīng)過的歷史最優(yōu)位置和當前位置來探索全局最優(yōu)解。本文算法使用的是局部鄰域粒子群算法，即采用環(huán)形拓撲的粒子群結構[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)分別對應粒子的位置和速度，m為種群中的粒子個數(shù)，d為數(shù)據(jù)維度，t為算法迭代次數(shù)，t從0開始算法逐次對整個粒子群的速度和位置向量進行迭代優(yōu)化，r1和r2是0到1之間的隨機數(shù)。pbesti為粒子i自身的歷史最優(yōu)位置，lbesti為粒子i與其鄰近的粒子組成的區(qū)域局部最優(yōu)位置。在頭尾相連的環(huán)形拓撲結構的粒子群中，局部區(qū)域由該粒子和其前后相鄰的2個粒子組成。w為慣性系數(shù)控制粒子位置更新時pbest和lbest的權重。較大的慣性系數(shù)有利于全局搜索，而較小的慣性系數(shù)一個有利局部搜索，c1和c2為加速常數(shù)，分別控制粒子朝全局最優(yōu)和局部最優(yōu)收斂的速度。粒子群算法可以用作聚類，如文獻[20]提出的使用量子行為粒子群的動態(tài)聚類算法。

1.2 聚類評價指標

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

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

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

(1)CH指標

(3)

(2)Dunn指標

(4)

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

(5)

δ(Cl)為簇l的兩個最遠距離點間的距離：

(6)

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

(3)SIL指標

(7)

(8)

(9)

(10)

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

SIL指標為正數(shù)或者負數(shù)分別表示相應的劃分分別是很好的聚類或者錯誤的聚類。SIL指標在零附近被認為對數(shù)據(jù)沒有明確區(qū)分。SIL指標越大傾向于聚類效果越好。

1.2.2 聚類外部指標

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

(1)Xi和Xj在Q中屬于同一個簇，同時它們在P中也屬于同一個類別；

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

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

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

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

(11)

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

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

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

2.1 種群個體的編碼

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

2.2 種群的初始化

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

2.3 聚類規(guī)則

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

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

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

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

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

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

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

(12)

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

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

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

(13)

(14)

2.5 MT-CACPSO具體流程

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

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

輸出：L個指標下對應的聚類結果。

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

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

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

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

fork=1，2，…，Ldo

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

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

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

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

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

3 算法實驗測試

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

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

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

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

3.2 參數(shù)設置

本實驗比較了3種聚類算法。其中ACPSO是單任務算法，實驗中分別對其采用了不同的聚類內(nèi)部指標作為優(yōu)化目標進行測試。ACPSO的種群規(guī)模為40，本文提出的MT-CACPSO同時優(yōu)化多個內(nèi)部指標任務，每個任務的種群規(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。

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

3.3 MT-CACPSO與單任務算法的結果比較

ACPSO是先后選取了不同的3個優(yōu)化目標(CH、DUNN、SIL)單獨運行而得到的結果，MT-CACPSO是一次運行后得到的3個不同優(yōu)化任務對應的結果。

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

表2 ACPSO與MT-CACPSO運行結果的平均內(nèi)部指標

續(xù)上表

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

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

表3 ACPSO與MT-CACPSO運行結果的平均外部指標ARI

3.4 MT-CACPSO與多因子進化聚類算法的結果比較

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

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

表4 多因子進化聚類算法與MT-CACPSO運行結果的平均內(nèi)部指標

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

表5 MT-CACPSO與多因子進化聚類算法結果的平均外部ARI值

3.5 算法收斂曲線圖

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

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

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

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

4 結語

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