基于自步學習的自適應半監督聚類算法

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

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

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

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

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

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

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

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

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

1 相關工作

1.1 自步學習

g(νi,λ))，

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

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

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

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

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

1.2 自適應損失函數

(1)

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

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

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

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

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

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

2 模型的建立

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

傳統譜聚類是無監督的,在已知部分標簽的情況下,可以將無監督聚類擴展到半監督聚類。本文通過約束原始已知數據點的標簽類別Yl與聚類后對應的標簽類別Fl保持一致,其中l為已知標簽的個數,利用標簽矩陣Y調整F,使得F的結構更加規則,從而得到如下半監督標簽傳播算法，

s.t.Fl=Yl

(2)

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

s.t.Fl=Yl

(3)

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

s.t.Fl=Yl

(4)

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

s.t.Fl=Yl

(5)

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

3 模型的求解

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

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

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

(6)

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

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

(7)

(8)

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

(9)

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

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

輸入 數據向量x。

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

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

直到收斂

輸出x。

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

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

s.t.

Fl=Yl

(10)

s.t.Fl=Yl

(11)

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

s.t.Fl=Yl

(12)

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

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

s.t.Fl=Yl

(13)

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

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

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

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

解得

(14)

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

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

(15)

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

綜上所述,ASSCSPL目標函數的優化求解過程如算法2所示。

4 實驗

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

4.1 數據集

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

表1 數據集

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

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

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

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

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

4) 更新λ1，λ2；

直到收斂或達到最大迭代次數

輸出F∈Rn×c。

4.2 比較方法

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

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

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

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

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

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

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

4.3 實驗設置

4.4 實驗結果

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

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

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

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

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

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

A YALE數據集; B colon數據集

4.5 參數的靈敏度測試

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

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

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

5 結語

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