多任務孿生支持向量聚類算法

朱文文， 黃成泉， 阮 麗

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

0 引 言

傳統機器學習方法，如分類和聚類，是假設要處理的數據必須來自于同一分布，當要處理的數據是來自于不同分布時，傳統機器學習方法需要分別對每個分布下的數據、即每個任務進行學習，這樣就導致較多的時間花費，且忽略了任務間的相關性，特別是當某一任務的數據有限時，采用傳統機器學習技術并不能夠獲得很好的效果，多任務學習正是為了應對這種情況而被提出的。

聚類在計算機視覺、文本挖掘、生物信息學和信號處理等多個領域都有應用。聚類是機器學習中最基本的方法之一，其目的是將數據點劃分為簇，使得同一個簇中的數據具有較大的相似性，不同簇之間的數據具有較大的差異性。考慮到傳統的基于點的聚類方法、如K-均值是根據數據集的分布將數據劃分到所屬集群中，當數據沒有分布在多個集群點時，傳統的基于點的聚類方法聚類性能很差。因此，本文在孿生支持向量聚類[1]模型基礎上基于平面進行聚類。為了保持任務間的差異性、又充分利用任務間的相關性，從而整體上提高每個任務的聚類性能，本次研究把單任務孿生支持向量聚類擴展到多任務學習框架下，提出了多任務孿生支持向量聚類算法，多任務孿生支持向量聚類假設任務間共享一個公共的表示，同時學習多個相關任務，從而整體上提高所有任務的聚類性能。

1 孿生支持向量聚類

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

(1)

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

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

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

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

(2)

其中，K(·,·)是一個適當的核函數。

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

(3)

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

2 多任務孿生支持向量聚類

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

(i=1,2,…k).

(4)

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

ξj+1it≥0.

(5)

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

注意到：

由此可以得到：

(6)

同理可得：

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

(7)

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

ξj+1it≥0,

(8)

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

s.t. 0≤α≤ce,

(9)

其中，

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

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

問題(9)是一個凸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]‖≤ε，停止迭代，并設置ωi=ωj+1i+ωj+1it,bi=bj+1i+bj+1it。

通過內核技巧將上面的線性多任務孿生支持向量機擴展到多任務非線性孿生支持向量機，即：

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

(11)

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

3 結束語

本文在孿生支持向量聚類模型上進行改進，將孿生支持向量聚類模型擴展到多任務學習框架下，提出了多任務孿生支持向量聚類算法，通過求解一系列二次規劃問題確定聚類中心平面。同時學習多個相關任務的經驗和理論表明，相對于獨立學習每個任務，該算法利用任務間的相關性來提升所有任務的聚類性能。