基于自步學習的無監督屬性選擇算法

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

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

0 引言

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

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

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

1 相關理論

1.1 稀疏屬性選擇

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

(1)

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

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

1.2 自步學習

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

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

(2)

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

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

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

2 算法描述與優化

2.1 算法描述

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

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

X=XW+E

(3)

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

(4)

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

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

(5)

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

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

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

(6)

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

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

本文提出的UFS-SPL算法具有以下優點：

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

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

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

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

本文算法流程如下：

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

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

輸出 系數矩陣W∈Rd×d。

①如果k≤k_end，則退出。

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

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

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

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

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

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

2.2 算法優化

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

1)固定v，優化W。

當固定v后，目標函數(6)變為：

(7)

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

(8)

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

-GTG+GTGW+αDW=0

(9)

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

(10)

通過簡單數學變換得到最終解為：

W=(GTG+αD)-1GTG

(11)

2)固定W，優化v。

當固定W后，原目標函數可寫為：

(12)

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

(13)

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

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

(14)

3 優化算法收斂性證明及參數決定

3.1 收斂性證明

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

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

(15)

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

(16)

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

(17)

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

(18)

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

(19)

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

(20)

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

3.2 參數設置

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

(21)

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

(22)

根據式(22)可以得到:

(23)

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

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

4 實驗結果與分析

4.1 實驗設置

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

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

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

表1 數據集信息統計Tab. 1 Dataset information statistics

4.2 實驗結果與分析

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

通過分析表2可以看出，在全部數據集中,本文提出的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%，因此，可以驗證本文方法比使用傳統訓練方式的屬性選擇方法擁有更好的性能。特別地，在數據集USPS(樣本最多)和DBworld(維度最高)上，本文方法均獲得良好的表現，準確率不但比NFS分別高出26.88%和11.54%，而且與CDLFS算法相比分別提高15.02%和8.18%，這是因為UFS-SPL算法充分考慮了樣本的共同性和差異性，在降低噪聲樣本干擾的同時去除冗余信息，因此，在處理多樣本與高維度的數據上能取得更好的效果。表2還展示了各算法在互信息與純度的對比結果，本文算法的效果仍然均超過其他對比算法，進一步說明本文算法的魯棒性。

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

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

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

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

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

5 結語

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