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

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

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

0 引言

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

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

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

1 相關(guān)理論

1.1 稀疏屬性選擇

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

(1)

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

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

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

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

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

(2)

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

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

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

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

2.1 算法描述

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

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

X=XW+E

(3)

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

(4)

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

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

(5)

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

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

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

(6)

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

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

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

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

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

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

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

本文算法流程如下：

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

輸入 訓(xùn)練樣本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；重復(fù)以上步驟。

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

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

2.2 算法優(yōu)化

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

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

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

(7)

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

(8)

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

-GTG+GTGW+αDW=0

(9)

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

(10)

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

W=(GTG+αD)-1GTG

(11)

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

當(dāng)固定W后，原目標(biāo)函數(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的收斂性證明。

假設(shè)算法的第t+1次迭代結(jié)果為：

(15)

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

(16)

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

(17)

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

(18)

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

(19)

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

(20)

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

3.2 參數(shù)設(shè)置

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

(21)

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

(22)

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

(23)

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

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

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

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

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

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

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

4.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

5 結(jié)語

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