基于自步學習的無監(jiān)督屬性選擇算法

龔永紅，鄭 威，吳 林，譚馬龍，余 浩

(1.桂林航天工業(yè)學院 圖書館，廣西 桂林 541004； 2.廣西師范大學 廣西多源信息挖掘與安全重點實驗室，廣西 桂林 541004)(*通信作者電子郵箱zwgxnu@163.com)

0 引言

伴隨信息采集技術的不斷發(fā)展，具有大樣本、高維度特點的大數(shù)據(jù)已經(jīng)普遍應用于模式識別和機器學習等領域中[1-2]。高維大數(shù)據(jù)不僅提升了數(shù)據(jù)處理的成本，而且數(shù)據(jù)中存在的冗余屬性還會影響數(shù)據(jù)處理的效果，此外還可能造成維度災難等問題[3]。在高維大數(shù)據(jù)的研究中，大數(shù)據(jù)知識挖掘或者數(shù)據(jù)認知模式建立之前，合理地移除數(shù)據(jù)中的冗余屬性和噪聲樣本，能夠有效提高知識獲取的準確性，因此數(shù)據(jù)降維成為了一個重要的研究領域[4-5]。屬性選擇方法[6]是一種重要的數(shù)據(jù)降維方法，按照學習方式的不同可分為三類：有監(jiān)督學習[7]、無監(jiān)督學習[1,8-10]和半監(jiān)督學習[11-12]。在現(xiàn)實應用中，獲取數(shù)據(jù)的類標簽是十分困難的，通常需要消耗大量的人力物力，因此無監(jiān)督學習更具有實際應用價值。

高維大數(shù)據(jù)除了包含冗余的屬性外，往往也包含了噪聲樣本。由于數(shù)據(jù)降維方法只考慮樣本之間的共同性(即所有樣本都包含有用信息)，卻忽略了樣本的差異性(即不同樣本擁有不同的重要性)[13]，因此，不能有效避免數(shù)據(jù)中噪聲樣本對模型的影響而導致獲得的屬性選擇模型并不理想。根據(jù)文獻[2,14]的研究表明，屬性選擇方法對冗余屬性具有良好效果，而自步學習方法對噪聲樣本的處理具有顯著效果。因此，本文通過結合無監(jiān)督屬性選擇和自步學習兩種學習理念，提出了一種新的屬性選擇模型——基于自步學習的無監(jiān)督屬性選擇(Unsupervised Feature Selection base on Self-Paced Learning, UFS-SPL)算法，能夠同時在樣本層次和屬性層次進行有效篩選，挖掘數(shù)據(jù)內(nèi)在的認知模式，提高屬性選擇模型的學習能力。

本文首先使用屬性自表達方法獲得自表達系數(shù)矩陣實現(xiàn)無監(jiān)督學習；然后利用L2,1-范數(shù)懲罰自表達系數(shù)矩陣去除冗余屬性，實現(xiàn)屬性選擇的目的。此外，在屬性選擇框架中添加自步學習正則化項，通過考慮樣本的共同性和差異性，使得目標函數(shù)首先自動選取重要的樣本子集進行模型學習，然后通過迭代學習方式從剩余樣本中逐步選擇次要樣本訓練模型從而提升模型泛化性能，直至所有樣本均參與模型訓練或者模型性能降低。通過考慮樣本的差異性并依據(jù)樣本重要性逐步對模型進行訓練，本文提出算法能夠降低噪聲樣本對訓練過程的干擾，因此可以保證最終獲得的屬性選擇模型同時具有健壯性和泛化性。此外，本文提出了一種簡單有效的優(yōu)化方法，能夠使目標函數(shù)快速收斂。由于本文采用自步學習方法對數(shù)據(jù)進行抽樣訓練，所以比傳統(tǒng)的屬性選擇方法具備更好屬性選擇效果。實驗結果表明，相較于常規(guī)屬性選擇算法，通過本算法獲得的新屬性集在聚類分析上具有更良好的表現(xiàn)。

1 相關理論

1.1 稀疏屬性選擇

稀疏學習[15]因其強大的內(nèi)在理論以及應用價值被引入機器學習等領域并獲得廣泛應用，而屬性選擇的目標是在所有屬性中尋找一個最能描述樣本的屬性子集。所以將稀疏學習理論應用到屬性選擇方法中，通過稀疏表示方法約束獲得的屬性權重，最終通過稀疏解進行屬性選擇。稀疏學習的引入可以實現(xiàn)屬性的自動選擇，因此能在去除冗余和不相關信息的同時保留重要特征?；谙∈璞硎镜膶傩赃x擇方法可以表示為：

(1)

其中：L(x,w)是損失函數(shù)；φ(w)是稀疏正則化項；α是稀疏控制參數(shù),α值越大w就越稀疏,反之亦然。

選擇有效的稀疏正則化因子能夠提升稀疏屬性選擇的性能。在稀疏學習中，最有效的稀疏正則化因子是L0-范數(shù)，但由于其難以優(yōu)化求解(NP難問題)，故許多文獻采用L0-范數(shù)的最優(yōu)凸近似L1-范數(shù)代替。L2,1-范數(shù)正則化因子能夠促進行稀疏，可以在移除冗余及不相關屬性的同時有效地降低離群點的影響，所以本文采用L2,1-范數(shù)代替L1-范數(shù)作為正則化項，而且求解L2,1-范數(shù)正則化項是凸優(yōu)化問題，故能夠保證本文模型獲得全局最優(yōu)解[2]。

1.2 自步學習

受到學習方式的啟發(fā)，文獻[13]提出了課程學習理論并建立了一種由簡到難的學習框架，其核心思想是通過模擬人的學習過程，首先從簡單的知識學起，然后逐漸增加學習難度，最后學習更困難、更專業(yè)的知識。而自步學習則是使用數(shù)學形式表達課程學習理論的方法。

給定數(shù)據(jù)集X∈Rn×d及對應響應矩陣Y∈Rn×c；L(yi,f(xi,w))表示損失函數(shù)，φ(w)為變量w的正則化項；v=[v1,v2,…,vn]表示自步權重向量，其中vi∈[0,1]為二分變量用于表示第i個樣本是否被選擇；φ(v)為自步學習正則化項?；谧圆綄W習的目標函數(shù)可寫為：

(2)

s.t.v∈[0,1]n

其中:α為稀疏正則化控制參數(shù)；λ為樣本選擇控制參數(shù)。

自步學習根據(jù)預測誤差(損失值)來定義樣本的重要性，通常將不存在預測誤差或者小于一定閾值的樣本定義為重要樣本(即“簡單”樣本)，而將預測誤差較大的噪聲或異常值定義為次要樣本(即“困難”樣本)。將自步學習方法融入到屬性選擇中，能夠更有效地避免噪聲樣本參與屬性選擇模型的訓練，最終獲得具有魯棒性與泛化性的訓練模型。

2 算法描述與優(yōu)化

2.1 算法描述

假設給定數(shù)據(jù)集X∈Rn×d，其中n和d分別為樣本和屬性的數(shù)量。不同于有監(jiān)督學習，無監(jiān)督學習由于缺少類標簽引導學習，導致無法直接通過擬合響應矩陣Y與樣本矩陣X獲取屬性權重矩陣。雖然可以將屬性選擇問題轉化為多輸出問題，即通過計算樣本間的相似性或流形結構的方法建立響應矩陣，但是想要選取一個合適的響應矩陣仍然比較困難。

實際上，每個屬性都可以通過其他屬性的線性組合去近似表示，因此，本文利用X代替Y作為響應矩陣建立屬性自表達關系：

X=XW+E

(3)

選擇適當?shù)南∈枵齽t化因子可以有效地去除冗余屬性和離群點的影響。由于L2,1-范數(shù)可以引導行稀疏，可以迫使系數(shù)矩陣W中對應不重要特征的系數(shù)趨近于零或直接等于零，從而去除無關屬性，實現(xiàn)屬性選擇的目的。故本文采用L2,1-范數(shù)作為稀疏正則化項，得到的無監(jiān)督屬性選擇的目標函數(shù)為：

(4)

雖然式(4)可以有效移除冗余屬性從而達到屬性選擇的效果，但是采用全體樣本進行訓練不僅會造成計算資源的浪費,而且其中包含的噪聲樣本也會影響模型的訓練。

雖然簡單隨機抽樣方法可以緩解資源消耗的問題，但其既無法避免噪聲數(shù)據(jù)的影響，也不能兼顧樣本間的共同性和差異性，這不僅不能優(yōu)化模型的訓練，還有可能因為樣本信息的缺失而導致模型訓練的失敗。因此，本文融合自步學習方法與無監(jiān)督屬性選擇兩種學習模型，首先通過訓練獲取重要樣本，然后再通過重要樣本訓練獲得重要屬性，由于沒有噪聲樣本的影響而提升屬性選擇的準確性，其目標函數(shù)為：

(5)

s.t.v∈[0,1]n

其中:k為自步學習參數(shù)，用于決定自步學習過程中參與訓練的樣本。當k值較大時，自步學習傾向于選擇擬合誤差較小的樣本進行訓練；當k值逐漸減小就會有越來越多的樣本被選擇。因此，自步學習是一種由簡到難的學習模式，也是一種能夠有效避免噪聲數(shù)據(jù)的抽樣方式。

式(5)通過分配給每個樣本一個二分權重(vi為0或1，其中i=1,2,…,n)實現(xiàn)了“硬性”的樣本選擇，但是由于數(shù)據(jù)中的噪聲樣本并非均勻分布在所有樣本中，所以硬權重并不能精準判斷是否選取樣本。而軟權重分配給每個樣本一個0～1的實數(shù)值(包括0和1)，這樣能夠更加真實地反映訓練中樣本的潛在重要性，因此比硬權重具有更好的抽樣效果[16]。使用軟權重自步學習正則化因子替換原有正則化項，得到最終目標函數(shù)為：

(6)

s.t. 0≤vi≤1;i=1,2,…,n

其中：β為區(qū)間控制參數(shù)；k為自步學習參數(shù)。軟權重自步學習正則化項能夠通過更精確選取樣本，進一步避免噪聲樣本的影響，從而獲得更優(yōu)秀的屬性選擇效果。

本文提出的UFS-SPL算法具有以下優(yōu)點：

1)本文算法使用屬性自表達方法建立模型不僅解決了無監(jiān)督學習中響應矩陣難以確認的問題，而且該方式對離群點并不敏感，因此具有良好的魯棒性和泛化性；而且在自表達模型中引入L2,1-范數(shù)實現(xiàn)行稀疏能夠有效地移除冗余屬性，使模型能夠自動選取重要屬性。

2)加入了一種新的樣本訓練模式。自步通過模擬人或動物的學習機制，實現(xiàn)了一種由簡到難的學習方式；在傳統(tǒng)的無監(jiān)督屬性選擇中添加自步學習正則化因子，可以避免噪聲樣本對模型訓練的影響，提升屬性選擇模型的魯棒性。

3)使用了軟權重自步學習正則化因子進行樣本抽樣。不同于硬權重正則化因子使用二分權重(選擇樣本的權重為1，否則為0)，軟權重在硬權重的基礎上添加了“模糊區(qū)間”(權重值為0～1)[17]，這不僅可以細化樣本的抽樣，而且還可以進一步降低噪聲樣本在訓練中的影響，從而提高屬性選擇模型的效果。

4)UFS-SPL在迭代過程中對樣本進行逐步抽樣，并且通過對某一迭代過程所選擇的樣本進行優(yōu)化獲取當前最優(yōu)解，直到所有樣本參與訓練并獲得最終的全局最優(yōu)解。

本文算法流程如下：

1)獲取自表達系數(shù)矩陣W∈Rd×d。

輸入 訓練樣本X∈Rn×d，控制參數(shù)α、β、k、k_end，步長參數(shù)μ>1。

輸出 系數(shù)矩陣W∈Rd×d。

①如果k≤k_end，則退出。

②通過式(14)獲取v(t);

③根據(jù)式(11)獲取W(t);

④通過式(10)更新D(t+1)；

⑤更新參數(shù)k=k/μ，t=t+1；重復以上步驟。

2)計算每個屬性權重θi(θi=‖wi‖2),其中wi是系數(shù)矩陣W的第i行。

3)對屬性權重θ按降序排序并選取前c個權重對應的X的特征向量組成新的屬性集。

2.2 算法優(yōu)化

本文UFS-SPL算法包含兩個變量，因此采用兩步交替優(yōu)化法分別優(yōu)化：

1)固定v，優(yōu)化W。

當固定v后，目標函數(shù)(6)變?yōu)椋?/p>

(7)

為方便優(yōu)化，將式(7)改寫為：

(8)

式(8)可以看作關于W的函數(shù)，因此，對式(8)進行求導，并且使導數(shù)為0得到：

-GTG+GTGW+αDW=0

(9)

其中D為對角矩陣，它的每一個元素：

(10)

通過簡單數(shù)學變換得到最終解為：

W=(GTG+αD)-1GTG

(11)

2)固定W，優(yōu)化v。

當固定W后，原目標函數(shù)可寫為：

(12)

s.t. 0≤vi≤1;i=1,2,…,n

(13)

s.t. 0≤vi≤1;i=1,2,…,n

通過式(13)可以得到v的解為：

(14)

3 優(yōu)化算法收斂性證明及參數(shù)決定

3.1 收斂性證明

由于式(8)是非平滑的，使得對W的優(yōu)化求解變得困難，但本文使用了一種簡單有效的算法來求解該問題，下面將給出算法第t次迭代中優(yōu)化矩陣W的收斂性證明。

假設算法的第t+1次迭代結果為：

(15)

在求得第t+1次的解W后,可以得到：

(16)

將式(8)得到的對角矩陣代入到不等式(16)，得到：

(17)

對于W(t)和W(t+1)的每一行，可以得到下列不等式：

(18)

在累加后并乘以控制參數(shù)α可以得到：

(19)

最后，結合不等式(17)、(19)可得到：

(20)

由式(15)～(20)可知，目標函數(shù)的值在優(yōu)化過程中保持單調(diào)遞減，所以本文提出的優(yōu)化算法可以在當前所選擇的樣本下使目標函數(shù)穩(wěn)定收斂從而獲得全局解。

3.2 參數(shù)設置

由式(14)可知，參數(shù)k和β的值決定了學習過程中樣本的選取，因此，選擇合適的參數(shù)可以提升自步學習的效果。假設第一次被選入樣本的最大損失值為LS，根據(jù)式(14)可以得到：

(21)

為簡化計算，令k=1/β，可以得到：

(22)

根據(jù)式(22)可以得到:

(23)

由式(22)與(23)可知，本文方法可以根據(jù)初始選取的樣本的數(shù)量獲取合適的參數(shù)，因此，可以降低本文算法對參數(shù)的依賴。在固定參數(shù)k和β之后，其他參數(shù)仍需要調(diào)整，本文將在實驗部分給出具體的參數(shù)設定。

表2 不同算法在不同數(shù)據(jù)集上準確率、互信息、純度統(tǒng)計 %Tab. 2 Accuracy, mutual information, purity statistics of different algorithms on different data sets %

4 實驗結果與分析

4.1 實驗設置

本文使用6個真實數(shù)據(jù)集測試提出屬性選擇算法的性能，其中數(shù)據(jù)集Umist、Isolet來源于UCI(UCI machine learning repository)[20]，USPS來自手寫數(shù)字數(shù)據(jù)庫[21]，Jaffe來自人臉圖像數(shù)據(jù)庫[22]，Coil、DBword來自屬性選擇數(shù)據(jù)庫[23]，數(shù)據(jù)集的詳細信息見表1。

本文實驗使用Matlab 2014a軟件在Windows 10系統(tǒng)下進行測試。為驗證本文算法的有效性，本文實驗選擇4種對比算法進行比較：1)NFS(Non Feature Selection)方法，對不經(jīng)屬性選擇的數(shù)據(jù)直接進行k-means聚類。2)凸半監(jiān)督多標簽屬性選擇(Convex Semi-supervised multi-label Feature Selection, CSFS)方法[18]，通過真實標簽構造的預測標簽去擬合數(shù)據(jù)獲得屬性權重，并且使用L2,1-范數(shù)對權重矩陣進行稀疏處理。3)正則化自表達(Regularized Self-Representation, RSR)方法[10]，通過自表達方法使用樣本矩陣代替響應矩陣，然后嵌入到稀疏回歸模型進行屬性選擇。4)無監(jiān)督屬性選擇的耦合字典學習方法(Coupled Dictionary Learning method for unsupervised Feature Selection, CDLFS)[19]，依據(jù)矩陣分解的思想構造分解字典矩陣與合成字典矩陣進行無監(jiān)督屬性選擇。

在參數(shù)設置方面，本文算法中的稀疏控制參數(shù)α=10-3,10-2,…,103，自步學習步長參數(shù)μ>1。對于其他對比算法，本文均按照其原實驗參數(shù)進行設置。

表1 數(shù)據(jù)集信息統(tǒng)計Tab. 1 Dataset information statistics

4.2 實驗結果與分析

在本文實驗中，除NFS外，利用所有屬性選擇算法對數(shù)據(jù)集屬性的重要性進行學習，并且依據(jù)重要程度排序，選擇前[20%，40%，60%，80%]的屬性作為新的屬性集，然后分別進行k-means聚類，選取最優(yōu)結果作為最終結果。本文采用準確率、互信息、純度3種評價指標評估所有算法的效果。表2分別展示了所有算法在6個真實數(shù)據(jù)集上的準確率、互信息和純度。

通過分析表2可以看出，在全部數(shù)據(jù)集中,本文提出的UFS-SPL方法在三項評價指標上相較于CSFS、RSR、CDLFS方法平均提高了12.06%、10.54%和10.5%。具體地，在聚類準確率上UFS-SPL方法分別比NFS、CSFS、RSR、CDLFS四種算法提升了20.38%、12.20%、11.29%、12.68%，因此，可以驗證本文方法比使用傳統(tǒng)訓練方式的屬性選擇方法擁有更好的性能。特別地，在數(shù)據(jù)集USPS(樣本最多)和DBworld(維度最高)上，本文方法均獲得良好的表現(xiàn)，準確率不但比NFS分別高出26.88%和11.54%，而且與CDLFS算法相比分別提高15.02%和8.18%，這是因為UFS-SPL算法充分考慮了樣本的共同性和差異性，在降低噪聲樣本干擾的同時去除冗余信息，因此，在處理多樣本與高維度的數(shù)據(jù)上能取得更好的效果。表2還展示了各算法在互信息與純度的對比結果，本文算法的效果仍然均超過其他對比算法，進一步說明本文算法的魯棒性。

圖1 不同參數(shù)下準確率的直方圖Fig. 1 Histograms of accuracy under different parameters

圖2 不同樣本數(shù)下的聚類準確率Fig. 2 Clustering accuracy under different samples

圖1為不同參數(shù)下準確率的直方圖，可清楚地看到本文UFS-SPL算法通過設置不同的參數(shù)可以獲得不同的效果。從圖1可以看出：當設置參數(shù)α=10-3并且設置參數(shù)μ=1.4時，本文方法在數(shù)據(jù)集USPS上獲得最佳表現(xiàn)。這說明了UFS-SPL算法對于參數(shù)是敏感的，因此通過調(diào)節(jié)參數(shù)可以獲得更好的效果。

圖2為不同樣本數(shù)下的聚類準確率，從中可以看出：1)非抽樣方法由于采用所有樣本進行訓練，相對隨機抽樣方法來說模型的泛化性更強；但由于缺少對樣本重要性的判別，所以難以獲得更有效的模型。2)隨機抽樣方法由于沒有考慮樣本間的共同性和差異性，造成結果同樣存在隨機性。3)自步學習方法能克服隨機抽樣方法不穩(wěn)定且不易獲得好結果的缺點，該方法可以首先選擇重要樣本進行模型訓練，獲得健壯的初始屬性選擇模型，然后通過不斷添加次要樣本進一步提升模型的泛化性能，從而獲得最好的屬性選擇效果。

因為不同的數(shù)據(jù)集具有不同的數(shù)據(jù)分布，往往所含有的干擾因素也是不同的。實驗結果表明，本文UFS-SPL算法在不同數(shù)據(jù)集上均獲得了更好的效果,因此，UFS-SPL算法能夠輸出更具有判別力的屬性子集，模型具有更強的魯棒性。

5 結語

本文通過結合屬性自表達、稀疏學習和自步學習提出了一種新的無監(jiān)督屬性選擇方法——UFS-SPL算法。本文算法通過在稀疏屬性選擇框架中引入自步學習對數(shù)據(jù)進行迭代抽樣，選擇重要樣本參與模型訓練，有效避免了噪聲樣本帶來的干擾，從而更加準確地捕捉重要屬性，提升屬性選擇的準確性。經(jīng)實驗驗證，本文算法可以獲得魯棒的屬性選擇模型。在今后工作中，將嘗試在本文算法中添加圖正則化以進一步提升屬性選擇算法準確性，并嘗試拓展算法到半監(jiān)督學習中。