基于稀疏學習的魯棒自表達屬性選擇算法

何 威 劉星毅 程德波 胡榮耀

1(廣西師范大學廣西多源信息挖掘與安全重點實驗室 廣西 桂林 541004)2(廣西欽州學院 廣西 欽州 535000)

?

基于稀疏學習的魯棒自表達屬性選擇算法

何 威1劉星毅2*程德波1胡榮耀1

1(廣西師范大學廣西多源信息挖掘與安全重點實驗室 廣西 桂林 541004)2(廣西欽州學院 廣西 欽州 535000)

受屬性選擇處理高維數據表現的高效性和低秩自表達方法在子空間聚類上成功運用的啟發，提出一種基于稀疏學習的自表達屬性選擇算法。算法首先將每個屬性用其他屬性線性表示得到自表達系數矩陣；然后結合稀疏學習的理論(即整合L2,1-范數為稀疏正則化項懲罰目標函數)實現屬性選擇。在以分類準確率和方差作為評價指標下，相比其他算法，實驗結果表明該算法可更高效地選擇出重要屬性，且顯示出非常好的魯棒性。

高維數據 屬性選擇 屬性自表達 稀疏學習

0 引 言

在機器學習和數據挖掘的分類任務中，往往需要處理大量的高維數據，其中無關或冗余的屬性會對分類性能產生嚴重影響。屬性選擇方法能選擇出小部分重要屬性作為新的屬性集，并能維持甚至提高分類性能[1]，因而在機器學習領域得到了廣泛的應用。常見的屬性選擇方法有：有監督方法、無監督和半監督方法[13]。有監督的屬性選擇方法通過已知的類標簽，對訓練結果測試，從而進行屬性的重要性評估，常見的方法有t檢驗法和稀疏正則化線性回歸等[14]。無監督的屬性選擇，沒有指導最小特征子集選擇的類標簽信息。無監督屬性選擇方法，主要使用一些評價指標，如方差[5]、拉普拉斯算子分值[7]或秩比率[15]等，來評估每一個單獨的特征或特征子集，然后選擇最重要的前k個特征或最佳特征子集。這些指標可評價聚類性能、冗余、信息損失、樣本相似性或流形結構等。但是，在使用這些方法對所有屬性進行搜索時，計算復雜度過高，不能適用于高維大數據。半監督方法是有監督與無監督方法的結合，主要利用少量有標簽樣本和大量的無標簽樣本進行訓練和分類，如：自訓練算法、多視圖算法[13]。本文研究無監督屬性選擇方法。

在屬性選擇方法中，L2,1-范數的組稀疏正則化已被成功應用，且在各種實際應用中表現出了良好的性能[6]。在自然界中，自相似性是普遍存在的，即一個對象的一部分與其本身的其他部分相似。研究發現，擁有自相似性質的對象，每個屬性可以近似表示為其自身屬性的線性組合，稱之為自表達?；趯ο蟮淖韵嗨菩缘男再|，自表達性質適用于大多數的高維數據，并已廣泛應用于機器學習和計算機視覺領域[11]。而在無監督的屬性選擇中，由于沒有類標簽指導，很難獲得最小屬性子空間[4]。本文提出特征的自表達屬性方法，即每個屬性通過用其他屬性來表征，更好地利用了數據的內部特征，從而解決了無監督屬性選擇方法中，無類標簽的特點?；谝陨峡紤]，本文利用特征的自我表達能力，特征矩陣代表本身尋找有代表性的特征成分，并結合稀疏學習以達到良好的效果。

1 相關理論背景及簡介

稀疏學習[2]最早應用于圖形、圖像視覺等領域。由于具有強大的內在理論及應用價值，所以稀疏學習得到了迅速的發展，并在模式識別與機器學習等領域得到廣泛的應用。

設W∈Rn×1是模型的參數向量，n是樣本數，其中，w1,w2,…,wn表示n個樣本參數，且W=[w1，w2，…，wn]。本質上，數據的特點是由少量關鍵特征決定的。屬性選擇的目標是找出一個有代表性的特征子集，所有屬性都能通過它來重建。鑒于稀疏學習可實現特征的自動選擇，為此本文算法采用稀疏學習的方法，來自動選擇重要的特征子集。在稀疏學習的基本理論中，首先通過對模型的參數向量w∈Rn進行一種稀疏假設，再用訓練樣本對參數w進行擬合，主要實現的目標函數為：

(1)

其中，f(x)是損失函數，φ(w)是正則化項，λ調節w的稀疏性，且λ越大，w越稀疏，反之亦然。

將稀疏學習應用于屬性選擇算法當中，能夠將原始數據之間的系數權重作為重要的鑒別信息引入模型，通過稀疏約束來使得輸入數據進行稀疏表示。這樣可以去除冗余和不相關屬性，同時保證重要屬性能夠被選擇[9]。鑒于稀疏學習的正則化因子通常選用能夠轉化為凸優化問題來求解，故更能保證本文提出的模型求得唯一的全局最優解[3]。在稀疏學習中，L0-范數是最有效的稀疏正則因子，但因其求解為NP難，故很多文獻均采用近似正則項L1-范數來替代L0-范數；而L2,1-范數能導致行稀疏，已經被證明比L1-范數更適合于屬性選擇[18]。L2,1-范數正則化因子能用于稀疏表示來獲得組稀疏，因此本文采用L2,1-范數作為稀疏正則化因子來對屬性自表達進行行稀疏處理，以達到剔除冗余和不相關屬性的目的，且能夠有效地減少離群點對結果的影響。

2 算法描述和優化方法

基于低秩自表達方法在子空間聚類上的成功運用，本文利用特征的自表達能力，提出了一種簡單而且十分有效的無監督屬性選擇方法。通過屬性自表達來構造自表達稀疏矩陣，然后采用稀疏學習的原理將冗余屬性和不相關屬性進行稀疏化處理，從而本文算法能夠尋找出重要的特征成分。

假設給定訓練集X∈Rn×m，其中，n和m分別表示樣本數和屬性數。xi代表第i個樣本，即X=[x1,x2,…,xn]，然后利用fj代表第j個屬性，即X=[f1,f2,…，fm]。早期的屬性選擇是利用一些度量來估計每個屬性，比如協方差、拉普拉斯算子[7]等，然后通過得到的權值對所有屬性進行排序，取前面的一部分屬性作為新的屬性集。在目前的一些方法[3,4,6]中，通常是先計算樣本間的相似性或流行結構，然后建立一個響應矩陣Y=[y1,y2,…,ym]，使得屬性選擇問題轉化為一個多輸出的回歸問題：

(2)

其中，W是屬性權值矩陣，l(Y-XW)是損失函數，R(W)是關于W的正則化項，λ是正參數，用來調節對損失項的懲罰。

盡管式(2)是一種廣泛應用的屬性選擇的方法，但在如何選取一個適當的響應矩陣時往往比較困難。因此，本文提出一種SR_FS(Self-Representation for Feature Selection)的屬性選擇算法。本文的算法使用X作為響應矩陣，其中Y=X，即利用屬性自表達的方法，使得每個屬性都能被全體屬性很好地表現出來。即X中的每個屬性fi，均能通過用全體屬性(包括自身)的線性組合來表示：

(3)

其中ei為誤差項，ωji為自表達系數。對于每個屬性，可以將式(3)重寫為：

X=XW+E

(4)

經以上屬性自表達，可以得到自表達關系矩陣W。此時的W不能夠很好地選擇出重要的屬性，而且為使得剩余量E盡可能接近于0，故本文算法添加一個有效的稀疏學習正則化來輔助屬性選擇。因此本文算法的模型可以重寫為以下最小化問題：

(5)

最終由式(5)就可以得到目標函數為：

(6)

其中，X∈Rn×d(n和d分別表示樣本數和屬性變量數)為訓練樣本，W∈Rd×d是關于X的系數矩陣，λ是調和參數。本文算法的偽代碼如下：

算法1SR_FS算法

輸入：訓練樣本，正則化參數λ。

輸出：分類準確率。

1. 通過訓練樣本得出類指示矩陣X=[xi,k]；

3. 根據得到的W對原始屬性集X進行屬性選擇，并將得到的屬性集作為樣本的新屬性集；

4. 最后，對新屬性集構成的樣本采用SVM算法進行分類。

本文提出的算法具有如下優點：首先，由于算法采用了無監督屬性選擇模型的屬性自表達方法，所以不需要標簽矩陣Y來作為響應矩陣；其次，有效地將自表達學習和稀疏學習理論結合，該模型既能消除輸入數據中的冗余和不相關的屬性，又可實現特征的自動選擇；最后，本文的目標函數提出了一種區別于交替方向乘子法的求解方法，該優化算法能保證目標值在每次迭代過程中減小，并趨近于全局最優解，最終求得全局最優解。

3 優化分析求解

由于式(6)的前半部分是凸的，且正則化項是非光滑的，本文設計了一種高效方法來求解式(6)。具體為，首先將式(6)對wi(1≤i≤m)求微分，且令其等于0，可以得到如下等式：

XTx(i)-XXTwi+λDiwi=0

(7)

wi=(λDi+XXT)-1XTx(i)

(8)

注意Di是未知的且取決于W。由以上分析，并根據文獻[12]和文獻[8],本文提出算法2，用一種迭代方法來優化式(6)。

算法2優化求解式(6)的偽代碼

輸入:X;

輸出: w(t)∈Rn×n;

1.初始化 W∈Rn×n,t=1;

2. while 未收斂 do

5.t=t+1;

6. 結束

證明：根據算法2可得到

(9)

由此得到：

Tr(XTW(t+1)-X)T(XTW(t+1)-X)+

4 實驗結果與分析

4.1 實驗數據集和對比算法

本文用六個公開數據集測試提出的屬性選擇算法性能。為了測試本文算法的有效性和進行屬性選擇的效果，使用有標簽的數據集來測試算法，并與其他對比算法進行比較測試。其中數據集madelon、DBWorld、train和musk來源于UCI數據集[15],TOX-171、warpAP10P來源于文獻[16]，數據集詳情如表1所示。

表1 數據集信息統計

本文實驗是在Win7系統下的Matlab 2014a軟件上進行編程實驗。然后實驗選擇四種公認的有代表性的算法參與比較，包括:① NFS算法(Non Feature Selection)：對原始數據不做任何處理，直接使用LIBSVM工具箱[17]進行SVM分類，并作為實驗的基準線；② PCA主成分分析方法(Principal Component Analysis)；③ LPP方法(Locality Preserving Projection)；④ RFS方法[9]：通過權值大小來表示屬性重要性的強弱，損失函數和正則化項兩者均采用L2,1-范數來約束。其中，NFS方法直接對原始數據集進行SVM分類[10]，未對原始數據進行任何處理，相比SR_FS等屬性約簡算法，不僅數據處理量大，而且結果容易受到冗余數據和噪音數據的影響；PCA考慮數據的主成分把數據從高維空間投影到低維空間，信息損失較為嚴重；LPP只考慮了數據的局部信息，沒有考慮數據內部的整體情況，投影時信息損失也較為嚴重；RFS方法為產生稀疏系數矩陣，由此可以賦大權重給重要的屬性，賦小權重給不重要的屬性。在比較的算法中，PCA和LPP算法均屬于子空間學習方法，RFS算法屬于屬性選擇方法。

分析各算法的時間復雜度和空間復雜度。時間復雜度：本文SR_FS算法是稀疏學習與屬性自表達的最小二乘的有效組合,其時間復雜度與PCA、LPP及RFS算法一致，同為O(n3)(其中n是樣本量)；空間復雜度：本文算法與所有的對比算法均需存儲矩陣乘法的中間結果，空間復雜度為線性。

4.2 實驗結果和分析

本文首先用不同的算法對數據進行屬性選擇處理，然后用統一的方法對數據進行分類，并采用分類準確率作為評價指標，分類準確率越高表示算法效果越好，以此來檢測是否提出的SR_FS算法能夠具有很好的效果。實驗通過10折交叉驗證方法把原始數據劃分為訓練集和測試集，運用訓練集通過算法來訓練模型，用測試集測試模型的效果。實驗采用SVM分類工具箱分類，得到分類準確率。所有的算法均保證在同一實驗環境下進行，最后提取10次運行的實驗結果的均值加減方差來評估各算法的分類效果和魯棒性，具體各數據集實驗結果見表2所示。為了比較不同數據量綱的各算法的魯棒性，本文采用變異系數(變異系數=(標準差/平均值)× 100%)作為評價指標，統計結果見表3所示。為更直觀地比較各算法的效果，每一數據集各算法每次的實驗結果對比如圖1-圖6所示。

首先，分析表2數據可以看出，其中，SR_FS算法在不同數據集上取得的準確率均為最高，且與NFS算法比較平均提高了12.78%，效果最為明顯，與RFS算法比較平均提高了3.35%。其中，在train數據集上，SR_FS對比其他算法準確率平均提升3.94%，為最低；而在musk數據集上效果最為顯著，SR_FS與其他對比算法相比平均提高14.08%，且與NFS相比提高了19.1%。這是因為SR_FS算法不僅可以使屬性自表達，而且同時利用屬性自表達的表示方式，考慮到了全體不同屬性之間的相互關系；而PCA算法僅做了高維到低維的投影，RFS算法未考慮數據之間的關系，LPP算法只考慮了數據局部的關系。而SR_FS算法又結合了稀疏學習，彌補了單一方法的不足，因此能有效地選擇主要的類判別屬性和去除噪音屬性，顯著提高分類性能。根據圖1-圖6可以直觀地看出，SR_FS算法在各數據集上10次運行的結果的折線大部分能在其他算法的上方，表明SR_FS算法表現出了更好的效果。

分析表2的方差統計結果可看出，SR_FS算法在各個數據集的10次運行結果取得的方差與各對比算法相比，均能取得最小的方差。分析表3的變異系數統計結果可看出，SR_FS算法在各數據集上得到的變異系數均為最小。通過各算法10次運行結果得到的方差(表2)和變異系數(表3)的比較可知，在多個不同數據集上，經本文SR_FS算法屬性選擇后的數據，均能達到更加準確和穩定的分類效果。因此，本文SR_FS算法比對比算法有更好的魯棒性。

圖1 數據集madelon上各算法準確率對比

圖2 數據集mask上各算法準確率對比

圖3 數據集train上各算法準確率對比

圖4 數據集warpAR10P上各算法準確率對比

圖5 數據集TOX-171上各算法準確率對比

圖6 數據集DBworld上各算法準確率對比

表2 準確率的均值統計結果(百分比%)

表3 各數據集十次結果的變異系數統計結果(百分比%)

5 結 語

本文提出一種新的屬性選擇算法SR_FS算法，即通過使用數據本身的性質來構建自表達系數矩陣，并整合L2,1-范數作為稀疏正則化項，來達到選擇重要屬性的目的。該算法有效地利用屬性的特性來構造自表達系數矩陣并和稀疏屬性選擇有機融合在一起，達到了進行自動屬性選擇的目的。其既擴展了屬性自表達的理論應用范疇，也彌補了稀疏學習在屬性選擇處理方面的不足。經實驗表明，本文算法能夠在分類準確率和穩定性上取得顯著提高。在后續的工作中，將嘗試在半監督屬性選擇方面拓展驗證本文提出的算法，并嘗試使用更先進的技術改進。

[1] Zhu X F,Suk H I,Shen D G.Matrix-Similarity Based Loss Function and Feature Selection for Alzheimer’s Disease Diagnosis[C]//Computer Vision and Pattern Recognition (CVPR),2014 IEEE Conference on.IEEE,2014:3089-3096.

[2] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[3] Zhao Z,Wang L,Liu H.Efficient spectral feature selection with minimum redundancy [C]//Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence,Atlanta,2010:673-678.

[4] Li Z C,Yang Y,Liu J,et al.Unsupervised feature selection using nonnegative spectral analysis [C]//Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence,Toronto,2012:1026-1032.

[5] Zhu X F,Huang Z,Yang Y,et al.Self-taught dimensionality reduction on the high-dimension-al small-sized data[J].Pattern Recognition,2013,46(1): 215-229.

[6] Yang Y,Shen H T,Ma Z G,et al.L2,1-norm regularized discriminative feature selection for unsupervised learning [C]//Proceedings of the Twenty-Second international joint conference on Artificial Intelligence,2011，2:1589-1594.

[7] Wan J W,Yang M,Chen Y J.Discriminative cost sensitive Laplacian score for face recognition[J].Neurocomputing,2015,152:333-344.

[8] Zhu X F,Huang Z,Yang Y,et al.Self-taught dimensionality reduction on the high-dimensional small-sized data[J].Pattern Recognition,2013,46(1):215-229.

[9] Nie F P,Huang H,Cai X,et al.Efficient and Robust Feature Selection via Joint L2,1-Norms Minimization[C]//Advances in Neural Information Processing Systems,2010:1813-1821.

[10] Yao L,Zhang X J,Li D H,et al.An interior point method for L1/2-SVM and application to feature selection in classification[J].Journal of Applied Mathematics,2014(1):1-16.

[11] Zhu P F,Zuo W M,Zhang L,et al.Unsupervised feature selection by regularized self-representation[J].Pattern Recognition,2015,48(2):438-446.

[12] Zhu X F,Huang Z,Shen H T,et al.Linear cross-modal hashing for efficient multimedia search[C]//MM 2013-Proceedings of the 2013 ACM International Conference on Multimedia， 2013:143-152.

[13] Zhao Z,Wang L,Liu H,et al.On Similarity Preserving Feature Selection[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(3):619-632.

[14] Mitra P,Murthy C A,Pal S K.Unsupervised feature selection using feature similarity[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(3):301-312.

[15] Nie F P,Xiang S M,Jia Y Q,et al.Trace ratio criterion for feature selection[C]//AAAI’08,2008,2:671-676.

[16] Feature selection datasets[EB/OL].[2015-04-10].http://featureselection.asu.edu/datasets.php.

[17] LIBSVM—A Library for Support Vector Machines.[EB/OL].[2015-04-10]. http://www.csie.ntu.edu.tw/～cjlin/libsvm.

[18] Yang Y,Shen H T,Ma Z G,et al.l2,1-norm regularized discriminative feature selection for unsupervised learning[C]//Proceedings of the Twenty-Second international joint conference on Artificial Intelligence.AAAI Press,2011,2:1589-1594.

[19] Zhu X F,Zhang L,Huang Z.A sparse embedding and least variance encoding approach to hashing[J].IEEE Transactions on image processing,2014,23(9):3737-3750.

FEATURE SELECTION ALGORITHM WITH ROBUST SELF-REPRESENTATION BASED ON SPARSE LEARNING

He Wei1Liu Xingyi2*Cheng Debo1Hu Rongyao1

1(GuangxiKeyLabofMulti-sourceInformationMiningandSecurity,GuangxiNormalUniversity,Guilin541004,Guangxi，China)2(QinzhouUniversity,Qinzhou535000,Guangxi，China)

Inspired by the high efficiency of feature selection in dealing with high-dimensional data and the success application of low-rank self-representation in subspace clustering,we proposed a sparse learning-based self-represented feature selection algorithm.The algorithm first represents every feature in other feature linearity to obtain the self-representation coefficient matrix; then in combination with sparse learning theory (i.e.to integrate the L2,1-norm as a sparse regularisation punishment object function) it implements feature selection.With the evaluation indexes of classification accuracy and variance,and compared with the algorithms to be contrasted,experimental results indicated that the proposed algorithm could be more efficient in selecting important features and showed excellent robustness as well.

High-dimensional data Feature selection Featrue self-representation Sparse learning

2015-07-27。國家自然科學基金項目(61170131，61263035，61363009)；國家高技術研究發展計劃項目(2012AA011005)；國家重點基礎研究發展計劃項目(2013CB329404)；廣西自然科學基金項目(2012GXNSFGA060004)；廣西高校科學技術研究重點項目(2013 ZD041)；廣西研究生教育創新計劃項目(YCSZ2015095，YCSZ2015096)。何威，碩士，主研領域：數據挖掘，機器學習。劉星毅，碩士。程德波，碩士。胡榮耀，碩士。

TP181

A

10.3969/j.issn.1000-386x.2016.11.045