基于自步學(xué)習(xí)的自適應(yīng)半監(jiān)督聚類算法

賈樂瑤,馬盈倉(cāng),邢志偉,蒙瑩瑩

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

現(xiàn)在正處于一個(gè)大數(shù)據(jù)時(shí)代,數(shù)據(jù)多且繁雜。在數(shù)據(jù)集中存在少量的標(biāo)簽數(shù)據(jù)以及大量的無標(biāo)簽數(shù)據(jù),人工標(biāo)記這些無標(biāo)簽數(shù)據(jù)需要消耗大量的人力及時(shí)間。因此,半監(jiān)督學(xué)習(xí)被提出用來標(biāo)記無標(biāo)簽數(shù)據(jù)。近些年來,半監(jiān)督聚類算法得到越來越多的關(guān)注,并應(yīng)用到了許多領(lǐng)域[1-3]。

一般情況下, 半監(jiān)督聚類算法分為以下3類[4]: ①基于約束的半監(jiān)督聚類算法(簡(jiǎn)稱CBSSC)[5-7],該類算法在傳統(tǒng)聚類的基礎(chǔ)上加入了必連和不連的成對(duì)約束限制,從而達(dá)到增強(qiáng)聚類效果的目的。在聚類過程中,具有必連約束條件的樣本會(huì)被分配到同一個(gè)類中,具有不連約束條件的樣本會(huì)被分配到不同的類中。②基于距離的半監(jiān)督聚類算法(簡(jiǎn)稱DBSSC)[8-10],該類算法在數(shù)據(jù)的預(yù)處理階段,通過學(xué)習(xí)一個(gè)自適應(yīng)度量或構(gòu)造某種距離度量來刻畫樣本間的相似性。這個(gè)新的度量函數(shù)能使數(shù)據(jù)集的類內(nèi)樣本距離盡可能小,類間樣本距離盡可能大。③基于約束和距離相結(jié)合的半監(jiān)督聚類算法(簡(jiǎn)稱CDBSSC)[11-12]，該類算法結(jié)合了前2類算法的優(yōu)點(diǎn),因而可以獲得更好的聚類效果。

自步學(xué)習(xí)(self-paced learning,SPL)[13]的靈感來源于教師對(duì)學(xué)生的教學(xué),即先教授簡(jiǎn)單的概念,后教授復(fù)雜的概念,以一種自定節(jié)奏的方式,從簡(jiǎn)單的樣本到復(fù)雜的樣本,逐步地學(xué)習(xí)模型。自步學(xué)習(xí)自從被提出以后,就受到了廣泛的關(guān)注和研究。Wang等提出了一種自步和自一致協(xié)同訓(xùn)練的深度學(xué)習(xí)方法[14],運(yùn)用自步學(xué)習(xí)策略來進(jìn)行協(xié)同訓(xùn)練,使得訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)能夠最先關(guān)注較容易分割的區(qū)域,然后逐漸考慮較難分割的區(qū)域;Shi等提出了一種新的多視圖自適應(yīng)半監(jiān)督特征選擇(MASFS)算法[15],該算法在半監(jiān)督特征選擇中引入自步學(xué)習(xí)(SPL),使得拉普拉斯權(quán)值圖能夠根據(jù)當(dāng)前預(yù)測(cè)信息自適應(yīng)變化;Chen等提出了一種自適應(yīng)圖學(xué)習(xí)半監(jiān)督自節(jié)奏分類(AGLSSC)方法[16],該方法將自步學(xué)習(xí)(SPL)和自適應(yīng)圖學(xué)習(xí)(AGL)集成到一個(gè)聯(lián)合框架中,并增加一個(gè)衡量樣本重要性的參數(shù)來自動(dòng)選擇需要導(dǎo)入的樣本。目前自步學(xué)習(xí)已經(jīng)成功應(yīng)用到多個(gè)領(lǐng)域且都獲得了良好的效果[17-18]。

目前,大多數(shù)半監(jiān)督聚類方法在構(gòu)建鄰域圖時(shí)忽略了樣本間的差異性,即在模型的訓(xùn)練過程中同等對(duì)待所有的樣本?；谇懊娴挠懻?本文將自步學(xué)習(xí)的思想運(yùn)用到半監(jiān)督聚類中,在聚類的過程中,對(duì)樣本有順序地進(jìn)行聚類。同時(shí),為了提升本文算法的魯棒性,我們采用了一種自適應(yīng)損失函數(shù),最終提出了基于自步學(xué)習(xí)的自適應(yīng)半監(jiān)督聚類算法(ASSCSPL)，主要特點(diǎn)表現(xiàn)為:

1)該方法在每次算法更新時(shí),利用自步學(xué)習(xí)為不同樣本賦予不同的權(quán)重,使模型更注重可靠樣本而不是全部樣本。在這種情況下,將噪聲對(duì)模型的影響減小。因此,該分類器對(duì)噪聲具有魯棒性;

2)通過標(biāo)簽傳播,將標(biāo)簽信息從有標(biāo)簽數(shù)據(jù)傳播到無標(biāo)簽數(shù)據(jù),從而更有效地對(duì)無標(biāo)簽數(shù)據(jù)進(jìn)行標(biāo)記,提高了模型的學(xué)習(xí)性能;

3)使用自適應(yīng)損失函數(shù),增強(qiáng)了模型對(duì)具有較小的或者較大損失的數(shù)據(jù)的魯棒性。

1 相關(guān)工作

1.1 自步學(xué)習(xí)

g(νi,λ))，

其中,λ是自步參數(shù),g(ν,λ)是自步函數(shù),用來控制自步學(xué)習(xí)的進(jìn)程。

一般自步函數(shù)需要滿足以下條件[20]:

1)g(ν,λ)關(guān)于ν∈[0,1]是凸的;

2)ν*(λ,l)關(guān)于l是單調(diào)遞減的,且當(dāng)l→0時(shí),ν*(λ,l)→1,當(dāng)l→∞時(shí)，ν*(λ,l)→0;

文獻(xiàn)[20]中證明了該函數(shù)滿足上述自步函數(shù)的條件,這里就不加贅述。

1.2 自適應(yīng)損失函數(shù)

(1)

其中，σ為自適應(yīng)參數(shù),xi為向量x的第i個(gè)元素。不同σ值(σ=0.1、5、10)下的自適應(yīng)損失函數(shù)如圖1所示?？梢钥闯?σ范數(shù)損失函數(shù)介于L1范數(shù)和L2范數(shù)之間,能兼具二者的優(yōu)勢(shì)。此外,式(1)中的損失函數(shù)具有以下性質(zhì)：

A σ=0.1; B σ=5; C σ=10

1) ‖x‖σ是二階可導(dǎo)的;

3) 當(dāng)xi≥σ時(shí),‖x‖σ→(1+σ)‖x‖1;

4) 當(dāng)σ→0時(shí),‖x‖σ→‖x‖1;

此外,文獻(xiàn)[21]中還將自適應(yīng)損失函數(shù)從向量擴(kuò)展到矩陣并給出了詳細(xì)的描述。

2 模型的建立

給定數(shù)據(jù)集X=[x1,x2,…,xn]∈Rn×d,其中n為樣本的個(gè)數(shù),d為維數(shù)。那么,傳統(tǒng)的譜聚類問題描述如下，

傳統(tǒng)譜聚類是無監(jiān)督的,在已知部分標(biāo)簽的情況下,可以將無監(jiān)督聚類擴(kuò)展到半監(jiān)督聚類。本文通過約束原始已知數(shù)據(jù)點(diǎn)的標(biāo)簽類別Yl與聚類后對(duì)應(yīng)的標(biāo)簽類別Fl保持一致,其中l(wèi)為已知標(biāo)簽的個(gè)數(shù),利用標(biāo)簽矩陣Y調(diào)整F,使得F的結(jié)構(gòu)更加規(guī)則,從而得到如下半監(jiān)督標(biāo)簽傳播算法，

s.t.Fl=Yl

(2)

矩陣跡的形式可以寫成向量的形式,因此式(2)可以寫為

s.t.Fl=Yl

(3)

眾所周知, 傳統(tǒng)的L2范數(shù)損失函數(shù)對(duì)異常值很敏感, 為了提高模型的魯棒性, 本文在模型中引入對(duì)異常值不敏感的自適應(yīng)損失函數(shù)‖X‖σ=

s.t.Fl=Yl

(4)

但上述模型并沒有考慮到樣本重要性的問題,為此,我們將自步學(xué)習(xí)的思想引入半監(jiān)督聚類中,最終,在式(4)的基礎(chǔ)上提出了一種基于自步學(xué)習(xí)的自適應(yīng)半監(jiān)督聚類模型，

s.t.Fl=Yl

(5)

式(5)為最終的模型,它不僅考慮了不同樣本的重要程度,而且降低了噪聲數(shù)據(jù)在標(biāo)簽預(yù)測(cè)過程中所產(chǎn)生的影響。

3 模型的求解

參考文獻(xiàn)[21]給出了式(1)的優(yōu)化過程,本文在式(1)優(yōu)化的基礎(chǔ)上給出了式(5)的優(yōu)化求解算法。

3.1 一般自適應(yīng)損耗最小化問題算法

由于(1)式難以優(yōu)化,文獻(xiàn)[21]提出了一種有效的算法來求解最優(yōu)解。首先,提出一種更一般的自適應(yīng)損失函數(shù)形式為

(6)

其中,gi(x)是一個(gè)向量輸出函數(shù)?？梢钥闯鍪?1)是式(6)的特殊情況。受文獻(xiàn)[21]和[22]的啟發(fā),本文采用迭代重加權(quán)算法求解最小化問題(6)，通過求式(6)對(duì)x的導(dǎo)數(shù),并令其導(dǎo)數(shù)等于0,可以得到

f′(x)+2(1+σ)

(7)

(8)

由于變量pi依賴于x,因此式(8)很難直接求解,但如果pi是固定的,則求解式(6)等價(jià)于求解以下問題，

(9)

其中,pi為過渡權(quán)重。因此,求廣義問題(6)的最優(yōu)解在算法1中提出。在算法1中,pi是根據(jù)當(dāng)前的x計(jì)算的,而解x是通過求解式(9)來更新的。算法1的收斂性參見文獻(xiàn)[21]。

算法1(6)式的優(yōu)化過程

輸入 數(shù)據(jù)向量x。

重復(fù) 1) 計(jì)算pi=(1+σ)

2) 通過解式(9)更新x。

直到收斂

輸出x。

3.2 求解問題(5)的優(yōu)化算法

根據(jù)算法1,問題(5)中提出的ASSCSPL目標(biāo)函數(shù)可以改寫為

s.t.

Fl=Yl

(10)

s.t.Fl=Yl

(11)

式(11)可寫為矩陣跡的形式,因此,求解式(10)就等價(jià)于求解下式，

s.t.Fl=Yl

(12)

因此,對(duì)式(5)的求解就轉(zhuǎn)化為對(duì)式(12)的求解,下面,本文將用交替迭代法對(duì)式(12)進(jìn)行求解。

固定ν,更新F:則式(12)關(guān)于F的子問題為

s.t.Fl=Yl

(13)

可以得到式(13)的拉格朗日函數(shù)為

αTr((F-Y)′V(F-Y))。

對(duì)L(F)求關(guān)于F的偏導(dǎo)數(shù),可以得到下面的式子，

通過矩陣的乘法準(zhǔn)則,將上式展開可以得到

解得

(14)

固定F,更新ν:則(12)式關(guān)于ν的子問題為

上式可以寫成向量的形式為

(15)

參數(shù)λ1和λ2的更新:λ2是自步學(xué)習(xí)的參數(shù),當(dāng)λ2較小時(shí),只考慮損失值小的樣本,隨著λ2的值的增加,才會(huì)考慮到損失較大的樣本,簡(jiǎn)單來說,λ2控制著每次迭代中加入學(xué)習(xí)的樣本的個(gè)數(shù)。而λ1則控制重要程度為1的樣本的個(gè)數(shù)。因此,自步參數(shù)λ1與λ2在迭代過程中都是逐步增大的,這樣就控制了模型的學(xué)習(xí)進(jìn)程。在本文中,我們將通過分別給λ1和λ2乘以μ和ρ來增大λ1和λ2的值,其中μ、ρ均為大于1的數(shù)。即λ1=μλ1,λ2=ρλ2,μ,ρ>1。

綜上所述,ASSCSPL目標(biāo)函數(shù)的優(yōu)化求解過程如算法2所示。

4 實(shí)驗(yàn)

我們?cè)?個(gè)公共數(shù)據(jù)集上對(duì)所提出的ASSCSPL算法進(jìn)行性能評(píng)估,并將其與幾種最先進(jìn)的半監(jiān)督聚類方法進(jìn)行比較。

4.1 數(shù)據(jù)集

本文選取以下6個(gè)數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn):COIL20、Umist、YALE、yeast-uni、colon、tr11,其中COIL20為文本數(shù)據(jù)集,Umist和YALE為人臉圖像數(shù)據(jù)集,yeast-uni為多標(biāo)簽數(shù)據(jù)集,colon為基因表達(dá)數(shù)據(jù)集,tr11為文本數(shù)據(jù)集，這些數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集

算法2基于自步學(xué)習(xí)的自適應(yīng)半監(jiān)督聚類算法(ASSCSPL)

輸入 相似矩陣S∈R(n×n)，有標(biāo)簽樣本的個(gè)數(shù)m，參數(shù)α，σ，λ1，λ2，μ>1，ρ>1

滿足FTDF=I的F∈R(n×c)；

2) 通過式(14)更新F；

3) 通過式(15)更新v；

4) 更新λ1，λ2；

直到收斂或達(dá)到最大迭代次數(shù)

輸出F∈Rn×c。

4.2 比較方法

在接下來的實(shí)驗(yàn)中,ASSCSPL算法將分別與GFHF、SODA、SFS、RGL、SEE、RLSR算法進(jìn)行比較。下面將簡(jiǎn)單地對(duì)這6種算法進(jìn)行介紹。

1) GFHF[23],將標(biāo)記的和未標(biāo)記的樣本數(shù)據(jù)表示為一個(gè)加權(quán)圖的頂點(diǎn),用邊權(quán)編碼實(shí)例之間的相似性;

2) SODA[24],通過標(biāo)簽傳播為無標(biāo)簽數(shù)據(jù)賦予標(biāo)簽,并且定義了基于標(biāo)簽傳播學(xué)習(xí)的軟標(biāo)簽的散射矩陣來進(jìn)行判別分析;

3) SFS[25],一種廣義不相關(guān)約束下的半監(jiān)督特征選擇方法,將嶺回歸擴(kuò)展到廣義不相關(guān)約束下的半監(jiān)督特征選擇;

4) RGL[26],一種新的魯棒圖學(xué)習(xí)方案,從真實(shí)數(shù)據(jù)中學(xué)習(xí)可靠的圖;

5) SEE[21],一種自適應(yīng)半監(jiān)督彈性嵌入損失最小化算法,該算法在預(yù)測(cè)標(biāo)簽矩陣上使用彈性嵌入約束,并運(yùn)用了一種新的自適應(yīng)損失函數(shù),使模型學(xué)習(xí)到更好的圖;

6) RLSR[27],用一組度量因子重新調(diào)整最小二乘回歸中的回歸系數(shù),對(duì)特征進(jìn)行排序,使模型學(xué)習(xí)到投影矩陣的全局解和稀疏解。

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

4.4 實(shí)驗(yàn)結(jié)果

本文以均值±標(biāo)準(zhǔn)差的形式展示最終的結(jié)果,所有方法在6個(gè)數(shù)據(jù)集上的ACC結(jié)果如表2～表4所示。

表2 l=3時(shí)所有算法的ACC結(jié)果(均值±標(biāo)準(zhǔn)差)

表3 l=5時(shí)所有算法的ACC結(jié)果(均值±標(biāo)準(zhǔn)差)

表4 l=10時(shí)所有算法的ACC結(jié)果(均值±標(biāo)準(zhǔn)差)

從表格中可以看出,我們提出的方法在大多數(shù)基準(zhǔn)數(shù)據(jù)集上優(yōu)于其他方法,這證實(shí)了我們提出的模型的有效性。

為了進(jìn)一步驗(yàn)證所提算法的有效性以及標(biāo)記樣本數(shù)量對(duì)該算法聚類性能的影響,在YALE和colon這2個(gè)數(shù)據(jù)集上,將每個(gè)類中的標(biāo)記樣本數(shù)量分別設(shè)置為1到5個(gè)和1到10個(gè),計(jì)算本文算法和對(duì)比算法的ACC值。在該實(shí)驗(yàn)中,其余參數(shù)分別設(shè)置為:α=1.5,λ1=0.01,λ2=0.02,μ=1.2,ρ=1.5。這些算法在不同標(biāo)記樣本數(shù)量下的ACC值如圖2所示。從圖2中可以看到,本文提出的算法(黑色三角線)總體上優(yōu)于其他對(duì)比算法,且聚類精度也會(huì)隨著已知標(biāo)簽數(shù)量的增加而增加。這證實(shí)了本文提出的模型的有效性。顯然,我們提出的半監(jiān)督聚類方法降低了噪聲數(shù)據(jù)的影響,提高了半監(jiān)督分類性能。

A YALE數(shù)據(jù)集; B colon數(shù)據(jù)集

4.5 參數(shù)的靈敏度測(cè)試

對(duì)于提出的ASSCSPL算法,本節(jié)將研究參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響,本文所提出的聚類模型包括λ1、λ2、μ、ρ、α和σ6個(gè)調(diào)優(yōu)參數(shù),實(shí)驗(yàn)結(jié)果通過聚類精度(ACC)來評(píng)判。本文通過網(wǎng)格搜索方法,在[10-3，10-2，10-1,1,10,100,1 000]內(nèi)設(shè)置參數(shù)α和σ的值,在[10-7,10-6,10-5,10-4，10-3,10-2,10-1]內(nèi)設(shè)置參數(shù)λ1的值,λ2的值在[2×10-7，2×10-6，2×10-5，2×10-4，2×10-3，2×10-2，2×10-1]內(nèi)設(shè)置,在[1.1∶0.1∶1.5]內(nèi)設(shè)置參數(shù)μ和ρ的值。對(duì)YALE和colon數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),記錄不同參數(shù)下ACC的結(jié)果,以顯示參數(shù)λ1、λ2、μ、ρ、α和σ對(duì)算法聚類性能的影響程度。值得一提的是,每個(gè)參數(shù)的ACC值都是在固定其余參數(shù)的情況下得到的。在YALE和colon數(shù)據(jù)集上的ACC結(jié)果分別見圖3和圖4,從這2幅圖中可以觀察到,當(dāng)各參數(shù)設(shè)置為不同值時(shí),ACC的值不會(huì)產(chǎn)生較大變化,由此可見,在YALE和colon這2個(gè)數(shù)據(jù)集上,所有參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響不是很大。

圖3 YALE數(shù)據(jù)集在不同參數(shù)值下的聚類精度(ACC)圖像

圖4 colon數(shù)據(jù)集在不同參數(shù)值下的聚類精度(ACC)圖像

5 結(jié)語

本文提出了一種新的自適應(yīng)半監(jiān)督聚類方法，ASSCSPL可以為不同重要性的樣本分配不同的權(quán)重,使算法能得到更好的聚類結(jié)果。另一方面,通過在模型中運(yùn)用了σ范數(shù),結(jié)合了L1范數(shù)和L2范數(shù)的優(yōu)點(diǎn),增加了模型的魯棒性能。最后,在公共數(shù)據(jù)集上的實(shí)驗(yàn)表明了該方法的有效性。盡管ASSCSPL相比于其他的方法有一定的優(yōu)勢(shì),能夠給出較好的聚類結(jié)果,但仍有改進(jìn)的空間。例如ASSCSPL所包含的參數(shù)較多,而對(duì)不同的數(shù)據(jù)集,我們需要通過調(diào)整參數(shù)來得到最優(yōu)的結(jié)果,這就要花費(fèi)大量的時(shí)間。希望在未來的研究中,能夠提出一個(gè)參數(shù)較少的模型。