賈樂瑤,馬盈倉,邢志偉,蒙瑩瑩

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

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

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

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

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

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

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

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

1 相關工作

1.1 自步學習

g(νi,λ))，

其中,λ是自步參數(shù),g(ν,λ)是自步函數(shù),用來控制自步學習的進程。

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

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

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

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

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

(1)

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

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

1) ‖x‖σ是二階可導的;

3) 當xi≥σ時,‖x‖σ→(1+σ)‖x‖1;

4) 當σ→0時,‖x‖σ→‖x‖1;

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

2 模型的建立

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

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

s.t.Fl=Yl

(2)

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

s.t.Fl=Yl

(3)

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

s.t.Fl=Yl

(4)

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

s.t.Fl=Yl

(5)

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

3 模型的求解

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

3.1 一般自適應損耗最小化問題算法

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

(6)

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

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

(7)

(8)

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

(9)

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

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

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

重復 1) 計算pi=(1+σ)

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

直到收斂

輸出x。

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

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

s.t.

Fl=Yl

(10)

s.t.Fl=Yl

(11)

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

s.t.Fl=Yl

(12)

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

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

s.t.Fl=Yl

(13)

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

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

對L(F)求關于F的偏導數(shù),可以得到下面的式子，

通過矩陣的乘法準則,將上式展開可以得到

解得

(14)

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

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

(15)

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

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

4 實驗

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

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

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

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

算法2基于自步學習的自適應半監(jiān)督聚類算法(ASSCSPL)

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

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

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

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

4) 更新λ1，λ2；

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

輸出F∈Rn×c。

4.2 比較方法

在接下來的實驗中,ASSCSPL算法將分別與GFHF、SODA、SFS、RGL、SEE、RLSR算法進行比較。下面將簡單地對這6種算法進行介紹。

1) GFHF[23],將標記的和未標記的樣本數(shù)據(jù)表示為一個加權圖的頂點,用邊權編碼實例之間的相似性;

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

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

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

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

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

4.3 實驗設置

4.4 實驗結(jié)果

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

表2 l=3時所有算法的ACC結(jié)果(均值±標準差)

表3 l=5時所有算法的ACC結(jié)果(均值±標準差)

表4 l=10時所有算法的ACC結(jié)果(均值±標準差)

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

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

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

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

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

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

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

5 結(jié)語

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