多任務(wù)孿生支持向量聚類算法

朱文文， 黃成泉， 阮 麗

(1 貴州民族大學(xué) 數(shù)據(jù)科學(xué)與信息工程學(xué)院, 貴陽 550025； 2 貴州民族大學(xué) 工程技術(shù)人才實(shí)踐訓(xùn)練中心, 貴陽 550025)

0 引 言

傳統(tǒng)機(jī)器學(xué)習(xí)方法，如分類和聚類，是假設(shè)要處理的數(shù)據(jù)必須來自于同一分布，當(dāng)要處理的數(shù)據(jù)是來自于不同分布時(shí)，傳統(tǒng)機(jī)器學(xué)習(xí)方法需要分別對每個(gè)分布下的數(shù)據(jù)、即每個(gè)任務(wù)進(jìn)行學(xué)習(xí)，這樣就導(dǎo)致較多的時(shí)間花費(fèi)，且忽略了任務(wù)間的相關(guān)性，特別是當(dāng)某一任務(wù)的數(shù)據(jù)有限時(shí)，采用傳統(tǒng)機(jī)器學(xué)習(xí)技術(shù)并不能夠獲得很好的效果，多任務(wù)學(xué)習(xí)正是為了應(yīng)對這種情況而被提出的。

聚類在計(jì)算機(jī)視覺、文本挖掘、生物信息學(xué)和信號處理等多個(gè)領(lǐng)域都有應(yīng)用。聚類是機(jī)器學(xué)習(xí)中最基本的方法之一，其目的是將數(shù)據(jù)點(diǎn)劃分為簇，使得同一個(gè)簇中的數(shù)據(jù)具有較大的相似性，不同簇之間的數(shù)據(jù)具有較大的差異性?？紤]到傳統(tǒng)的基于點(diǎn)的聚類方法、如K-均值是根據(jù)數(shù)據(jù)集的分布將數(shù)據(jù)劃分到所屬集群中，當(dāng)數(shù)據(jù)沒有分布在多個(gè)集群點(diǎn)時(shí)，傳統(tǒng)的基于點(diǎn)的聚類方法聚類性能很差。因此，本文在孿生支持向量聚類[1]模型基礎(chǔ)上基于平面進(jìn)行聚類。為了保持任務(wù)間的差異性、又充分利用任務(wù)間的相關(guān)性，從而整體上提高每個(gè)任務(wù)的聚類性能，本次研究把單任務(wù)孿生支持向量聚類擴(kuò)展到多任務(wù)學(xué)習(xí)框架下，提出了多任務(wù)孿生支持向量聚類算法，多任務(wù)孿生支持向量聚類假設(shè)任務(wù)間共享一個(gè)公共的表示，同時(shí)學(xué)習(xí)多個(gè)相關(guān)任務(wù)，從而整體上提高所有任務(wù)的聚類性能。

1 孿生支持向量聚類

在孿生支持向量機(jī)的研究基礎(chǔ)上，Wang等人[1]提出了孿生支持向量聚類(twin support vector clustering , TWSVC)，在TWSVC中，為了尋找k個(gè)聚類中心平面ωTixi+bi=0,i=1,…,k，通過求解以下聚類模型：

(1)

其中，c>0為懲罰參數(shù)；ξi>0為松弛向量；ωi為超平面的法向量；bi為超平面的偏移量。

分析可知，式(1)為一個(gè)二次規(guī)劃問題。其模型的幾何意義為：第Xi個(gè)樣本點(diǎn)在TWSVC中需要盡可能靠近第i個(gè)聚類中心平面，而遠(yuǎn)離其他類的中心平面。

通過核技巧將TWSVC擴(kuò)展到非線性情況下，非線性TWSVC在一個(gè)合適的內(nèi)核生成空間中尋找k個(gè)聚類中平面，即：

K(x,X)ui+γi=0,i=1,2,…,k，

(2)

其中，K(·,·)是一個(gè)適當(dāng)?shù)暮撕瘮?shù)。

非線性孿生支持向量聚類模型為：

(3)

其中，ηi(i=1,2,…,k)為松弛向量。

2 多任務(wù)孿生支持向量聚類

基于前述工作，將孿生支持向量聚類擴(kuò)展到多任務(wù)學(xué)習(xí)框架下，研究認(rèn)為所有的任務(wù)都有一個(gè)公共的表示[ωi;bi]，[ωit;bit]表示任務(wù)t與共享的公共表示之間的偏差。多任務(wù)孿生支持向量聚類模型為：

(i=1,2,…k).

(4)

類似于TWSVC求解方法，上述優(yōu)化問題可以通過凹凸過程(CCCP)[2]求解，該過程將式(4)中的第i個(gè)問題分解為一系列具有初始ω0i和b0i的凸二次子問題，此時(shí)有：

ξj+1it≥0.

(5)

其中，子問題的指數(shù)j=0,1,2,…,T(·)定義為一階泰勒展開式。

注意到：

由此可以得到：

(6)

同理可得：

因此模型(4)的約束為：

(7)

從而，模型(4)等價(jià)為：

ξj+1it≥0,

(8)

受支持向量機(jī)[4-5]、孿生支持向量機(jī)[6-7]的啟發(fā)，求解[ωj+1i;bj+1i]與[ωj+1it;bj+1it]，通過求解(8)的對偶問題：

s.t. 0≤α≤ce,

(9)

其中，

H=[Xie]，Ht=[Xite]，

并且α∈R是拉格朗日乘子向量。

問題(9)是一個(gè)凸QPP問題，通過逐次超松弛[8]方法可以有效地解決，該方法是求解線性方程組的迭代方法，并成功地推廣到求解上述問題[9]，通過以下式子可得式(9)的解，從而得到式(8)的解：

[ωj+1i+ωj+1it;bj+1i+bj+1it]=(HTH)-1GTα+

(10)

綜上，對于i=1,2,…,k，式(4)可以通過以下步驟來求解：

(1)初始化[ω0i+ω0it;b0i+b0it]。

(2)對于j=0,1,2,…,通過式(10)求[ωj+1i+ωj+1it;bj+1i+bj+1it]。

(3)如果‖[ωj+1i+ωj+1it;bj+1i+bj+1it]-[ωji+ωjit;bji+bjit]‖≤ε，停止迭代，并設(shè)置ωi=ωj+1i+ωj+1it,bi=bj+1i+bj+1it。

通過內(nèi)核技巧將上面的線性多任務(wù)孿生支持向量機(jī)擴(kuò)展到多任務(wù)非線性孿生支持向量機(jī)，即：

e-ηit,ηit≥0(i=1,2,…k).

(11)

其中，ηit為松弛向量，模型(11)的優(yōu)化過程類似于上述線性情況的優(yōu)化過程，此處不再贅述。

3 結(jié)束語

本文在孿生支持向量聚類模型上進(jìn)行改進(jìn)，將孿生支持向量聚類模型擴(kuò)展到多任務(wù)學(xué)習(xí)框架下，提出了多任務(wù)孿生支持向量聚類算法，通過求解一系列二次規(guī)劃問題確定聚類中心平面。同時(shí)學(xué)習(xí)多個(gè)相關(guān)任務(wù)的經(jīng)驗(yàn)和理論表明，相對于獨(dú)立學(xué)習(xí)每個(gè)任務(wù)，該算法利用任務(wù)間的相關(guān)性來提升所有任務(wù)的聚類性能。