基于低秩評分的非監督特征選擇算法

謝乃俊，楊國亮，羅 璐，梁禮明

（江西理工大學 電氣工程與自動化學院，江西 贛州341000）

0 引 言

根據評判數據特征重要性時是否利用了類別標簽信息，特征選擇算法可以分為有監督、無監督和半監督3類方法。有監督特征選擇算法主要是依據數據的特征與類別標簽信息之間的相關程度來選擇特征，經典的算法有fisher評分（fisher score，FS）［1］?，F實中，數據的類別標簽信息很少，人為地去獲取數據的類別標簽非常耗時、代價昂貴，因此人們提出了半監督和無監督特征選擇算法。方差評分 （variance data，VD）和拉普拉斯評分 （Laplacian score，LS）屬于非監督方法。在方差評分算法中，代表信息量多的特征點被選擇；拉普拉斯評分算法在考慮信息量的同時引入了局部信息描述能力約束項來對特征進行評分。半監督方法則利用部分類別標簽作為數據的一種先驗信息，文獻［2］中提出了 一 種 半 監 督 的 約 束 評 分 （constrain score，CS），同時利用無標簽的數據和帶有標簽的數據來進行數據的特征選擇，提高算法的性能。隨后，文獻 ［3］中將稀疏表示系數引入特征的評分標準中，提出了無監督的稀疏評分特征選擇方法。然而，稀疏表示理論方法為了使數據的表示稀疏滿足稀疏性，需要一個完備的詞典，怎樣構建有效的數據字典存在很大的挑戰。低秩表示理論是在稀疏的基礎上發展而來的最新的數據表示方法，它通過最小化核范數來誘導數據在字典下的低秩結構，能夠有效揭示數據的全局結構信息。目前，低秩表示在子空間恢復［4］、運動目標檢測［5］、特征提?。?］等任務中得到成功的運用。本文運用具有干凈字典約束的低秩表示模型學習數據的全局連接權值矩陣，揭示數據的全局結構和鑒別信息，利用該權值矩陣代替拉普拉斯評分機制中的局部連接矩陣，構建了一種低秩評分機制，用于非監督的特征選擇。該算法對那些揭示數據全局結構信息和鑒別信息能力較強、表達信息量較多的特征賦予更大的重要性。

1 低秩連接權值矩陣

數據的連接權值矩陣一定程度上能夠揭示數據間的某種關系，利用不同方法構建的連接權值矩陣所表示的數據結構信息不同。低秩表示模型能夠學習出數據在字典下的最低秩表示，這種表示能夠揭示數據的全局結構信息，同時又有一定的數據鑒別表達能力［7］。本節在低秩表示模型中引入干凈字典約束和低秩系數對稱性約束構建低秩連接權值矩陣，揭示數據間的結構信息。

1.1 干凈字典約束的低秩表示

假設數據集合X ＝［x1，x2，…，xn］∈Rd×n，采樣于l個獨立的子空間（ln），d代表數據的維數，n表示數據點的個數?，F實數據往往受噪聲的干擾，假設采樣數據集X由原始干凈數據D 和噪聲干擾數據E 疊加而成，因此，數據X 可以表示成X ＝D＋E。由ln可知，“干凈”數據集中某些數據點來自相同的子空間，彼此間具有類似的屬性，所以干凈數據矩陣D 具有低秩性特點，而噪聲干擾數據往往滿足稀疏性。通過低秩性和稀疏性約束，可以構建如下的優化目標函數來恢復出 “干凈”數據成分和噪聲成分

式中：λ＞0是噪聲懲罰參數，平衡噪聲對干凈數據的影響。上述優化問題是典型的非凸優化問題，在魯棒主成分分析［8］中，常常將式 （1）轉換為具有封閉解的松弛凸優化問題

假設數據集D 中的任意一列di能夠由數據本身D 中的每一列線性 組合表示成di＝Dzi，D ＝［d1，d2，…，dn］∈Rd×n中每一列di代表一個數據點向量，Zi＝Rn×l是字典中所有列對數據di線性表示的系數。由于所有數據都是在相同的字典下進行線性表示，數據集D 具有低秩性，所以在表達式D＝DZ 中，系數矩陣Z 同樣具有低秩這一特性?？紤]一對數據點（di，dj）兩者互相表示時具有對等性，我們引入對稱約束條件Z ＝ZT，因此，可以通過求解如下優化問題得到數據的低秩表示系數

式 （4）的最優解Z＊是數據在干凈字典約束下的最低秩表示，Z＊＝［，，…，］。數據在字典下的低秩表示是一種全局聯合的表示方式，具有揭示數據全局結構信息的表達能力，能夠自動的學習出數據間的相關性，使得具有相近屬性的數據在相互表示的時候提供較大的權值。

1.2 低秩模型求解

增廣拉格朗日乘子（augmented Lagrange multipiler，ALM）法分為精確增廣拉格朗日 （EALM，exact ALM）方法和非精確增廣拉格朗日 （IALM，inexact ALM）方法也稱為交替方向法 （ADM）。Lin在文獻 ［11］中證明了非精確增廣拉格朗日方法能夠有效的解決式 （2），下面我們詳細的介紹運用ADM 方法求解干凈字典約束的低秩表示模型式 （4）。首先參考文獻 ［12］，介紹一種優化問題求解定理。

定理1 假設存在如下優化問題

其中M ＝UΣVT代表數據矩陣M 的奇異值分解，式 （5）的最優解為

式中：Σ1——數據矩陣M 的奇異值大于的奇異值，U1、V1——相應的奇異向量。

通過引入拉格朗日乘子Y 消除式 （4）中的等式約束X ＝D＋E，保留等式約束D ＝DZ 和Z ＝ZT，式 （4）轉換成

利用迭代方法求解最優的（D，Z，E，Y），由于無法一次性得出所有參數的最優解，采用交替求解策略，固定其他參數，分別對每個參數獨立的進行更新。

（1）更新D，Z

為了更新（D，Z），固定參數E，Y，更新方法如下

根據定理1可知，上述問題的最優解為

（2）更新E

固定參數D，Z，Y，對參數E 進行更新

［13］可知：參數Ek＋1的最優化解為Ek＋1＝其中，當時，算子Ωε（X）的第i列為否則，Ωε（X）的第i列為零向量。完整的迭代求解過程列在算法1中。

1.3 數據的低秩權值矩陣

數據的圖結構能夠揭示數據集中隱含的本質結構信息，不同的構圖方法揭示的數據信息結構也不同。傳統的K 鄰域和ε鄰域圖構建反映了數據集在歐式空間中局部結構關系，揭示的是數據的局部結構信息。數據的局部信息結構被證明能夠很好的揭示數據的流形結構，但是局部鄰域圖的構建過程面臨鄰域參數k 的選擇問題。在構圖方法中參數k對圖的好壞起到決定性作用，現有方法往往通過經驗設置k值，沒有一種好的有效的機制來對進行適應性計算。基于稀疏表示的l1圖從數據全局角度考慮來揭示數據點間的關系，通過學習出數據在字典下的稀疏表示來揭示數據的全局結構信息。但是由于稀疏性約束條件，往往只有很少的一部分全局信息被揭示，而且，當數據存在噪聲干擾時，l1圖揭示數據信息的能力會受到影響。

低秩圖是在上述干凈字典約束的低秩表示模型的基礎上構建了揭示數據全局信息的一種結構圖。由于干凈字典約束低秩表示模型學習的是數據在干凈字典下的全局聯合線性表示，能夠揭示數據間的全局結構信息，同時干凈字典約束還能消除噪聲數據的干擾。因為數據被字典聯合的全局表示，低秩模型學習得到的全局連接權值相似度矩陣中存在密集的數值很小的連接值，這些值對全局信息的揭示不起作用，所以，將每個數據的低秩表示系數歸一化

（zi＝zi/zi2）并設置一個閾值，使得閾值以下的系數為零。數據的低秩權值矩陣W 定義為

2 低秩評分

有一數據集X ＝［x1，x2，…，xn］∈Rd×n，d表示數據特征的個數，n為數據樣本的個數。令fri是第i個樣本數據xi的第r個特征為反映某個特征所包含信息量大小的能力，定義如下的數據特征方差模型

低秩評分是在方差模型的基礎上保持了數據樣本點間的全局結構信息提出的一種特征評分算法，選擇出那些包含信息量多，全局結構信息表達能力強的特征。低秩評分模型如下

式中：Wij——數據樣本點間的相似度關系，通過上述低秩表示模型學習得出的，具有全局數據表示能力，權值的Wij表示數據樣本點（i，j）間的相似關系，具有大權值的樣本點來自同類的概率大，且具有較好的鑒別表示能力。Vs（r）表示特征的方差估計，特征方差估計的本質是將特征投影到最大方差的方向上，在該方向選擇出滿足條件的特征。大的方差說明數據特征在不同環境下屬性的表現區分性大，包含的信息量豐富，區分不同屬性事物的能力強。相反，小方差的特征對不同屬性事物區分發揮不了多大的作用。從式 （14）中我們能夠觀察出，如果某一特征的Vs（r）和Wij越大，（fri－frj）越小，那么該特征最后的低秩評分結果較小，特征表達信息的能力強。

經過下面簡單的推導可以得出

由此，低秩評分模型式 （14）轉換為

式中：L——拉普拉斯矩陣L ＝D－W ，D 為一對角矩陣，Dii＝Wij。數據特征的低秩評分算法過程見算法2。

3 實驗分析

為了驗證提出的低秩評分算法的有效性，我們在Iris鳶尾花數據集、PIE和ORL人臉數據集上分別進行實驗并同傳統的特征選擇算法進行比較。實驗先通過特征選擇算法在原始特征上選出一個子集，然后在新的特征子集上進行聚類或分類實驗。在PIE數據集上進行數據的聚類實驗，在ORL庫上進行分類實驗。低秩評分算法屬于非監督的特征選擇算法，因此選擇同已存在的方差評分，拉普拉斯評分和稀疏評分3 種非監督的特征選擇算法進行比較分析，其中拉普拉斯算法中的鄰域參數設置為k＝5。

3.1 Iris鳶尾花數據集

鳶尾花數據集包含3種類別共150 個數據樣本點，每種類別的數據樣本個數為50，每個數據樣本點含有4個數據特征。

我們分別選擇數據的單個特征利用簡單的最近鄰分類器對數據進行分類，數據中第1，2，3，4個特征對應的分類識別率分別為：r1＝0.38，r2＝0.20，r3＝0.84，r4＝0.86。表明不同特征在分類中發揮的作用按降序排列依次為：F4，F3，F1，F2，Fi表示第i個特征。

表1中列出了數據4個特征在不同評分算法下的最后評分結果。在方差評分中，得分越高說明該特征的作用越大，其他幾種算法則是得分越小的重要性越大。從表1中列出了4種算法學習出的特征重要性排位結果：方差評分算法為F3，F1，F4，F2，低秩評分算法和其他兩種算法都是F4，F3，F1，F2。對比上面分別用每個特征進行分類實驗可知，在特征選擇效果上而言，方差評分效果不佳，而低秩評分算法和其他兩種算法對特征重要性評價更接近真實情況。另外，在利用不同算法對數據特征打分后，按其重要性選擇不同的特征組合來進行實驗，選取數據中的不同特征組成兩個特征子集合，分別為特征子集（F1，F2），（F4，F3），將特征集中的兩個特征分別視為x 和y 軸，得到數據特征鑒別能力的可視化圖，結果如圖1所示。結果同樣證明，特征F4，F3的對數據的鑒別表達能力要強于特征F1，F2。

表1 幾種評分算法對不同特征的評分結果

圖1 Iris數據2維可視化

3.2 PIE人臉數據集

PIE人臉數據集中收集了68個人的41368張人臉數據，包含每個人在不同光照，表情和姿態條件下的數據，來自卡內基梅隆人臉表情數據庫。在本文的實驗中，保持人臉的表情和姿態條件不變，選取每個人的21張不同光照下的人臉數據組成實驗數據集。每張人臉數據都被裁剪為32×32像素大小的尺度。在PIE 數據集上，先利用不同算法對特征進行選擇，然后通過K 均值聚類算法對新的特征數據集聚類。最后選擇歸一化互信息度量標準 （normalized mutual information metric，NIM）來評價幾種不同特征選擇算法在聚類中的表現。NIM 的基本思想是通過比較數據點的真實標簽信息和聚類得到的標簽信息來評價實驗的表現。在PIE人臉數據上低秩打分中懲罰參數設置為λ＝0.5。

為了得到可靠的實驗結果，在數據集的68個類別子集上選取不同的類別數進行實驗 （類別數分別選取K ＝5，10，30，68）。在給定一個特定的類別數K 后，下面的過程被重復執行20次，求解20次的平均表現性能。在68類數據中隨機的選擇K 類數據，運用不同的特征評分方法對每個特征進行打分，學習出其重要性排序；選擇前d 個特征組成新的特征數據進行10次K 均值聚類實驗，選出最好的聚類效果。圖2顯示選取不同數量特征時，幾種特征重要性評分算法在聚類中的表現，K 表示參與實驗的類別數，橫坐標軸表示選擇特征的維數，縱坐標表示分類的NIM 數值，NIM 數值越大分類效果越好。通過比較結果表明，在所有的情況下本文提出的低秩評分算法在聚類實驗中取得最好的表現。在類別數K 選擇為5類和10類的情況下，特征數量選擇為300個以內時，低秩評分算法和稀疏評分算法的表現相當的穩定，而拉普拉斯評分在100個特征數以內，聚類表現出現一個上升階段，這說明，利用數據全局結構信息的評分機制比利用數據局部結構信息的評分機制更能揭示特征點的重要性。隨著類別數的增多，不同特征維數下的方差評分聚類表現反而越來越穩定，不會出現類似5類中前200個特征數內的那種大的波動，表明利用數據方差信息的評分機制需要更多數據來揭示數據特征的重要性。

圖2 幾種算法在不同特征數下的聚類表現

特征選擇的主要目的是為了減少數據的維數，使得某些算法在低維數據上能夠快速有效的執行，同時又不影響數據本質屬性的表達能力。為了驗證特征選擇算法的性能，表2列出了4種算法在選取不同特征個數下的聚類表現結果，表中數值表示算法在聚類表現中的NIM 值。對比幾種算法的表現可以看出：①所有算法在選擇特征數量適當時，聚類效果更好，說明特征選擇算法能夠有效的提高數據聚類算法的聚類能力；②低秩評分特征選擇算法在選擇不同特征時的聚類表現都強于其他幾種算法，尤其在特征選擇數量少的時候，優勢更加的明顯，證明了低秩特征選擇算法在數據聚類中相比于其他算法更具有優勢。為了更加直觀的揭示各種算法在聚類中表現不同的原因，在人臉圖像中分別標注了特征重要性排序后的前50、100、150、200個特征的幾何位置分布如圖3所示。從圖中能夠直觀的看出，特征通過方差評分算法對其重要性排序后，排序靠前的200個特征點主要分布在人臉圖像的四周和中間鼻子位置；拉普拉斯評分算法和稀疏評分算法的結果顯示重要性前200個特征主要是在人臉的眼睛，鼻子，嘴巴區域分散的分布；低秩評分算法則主要集中在眼睛，嘴巴和鼻子區域，從直觀的認知中可知，人臉特征主要是由五官來決定的，圖3所示的結果能夠直觀的說明低秩評分取得較好表現的原因。

表2 不同算法聚類的NIM 評價結果

3.3 ORL人臉數據集

ORL人臉庫是由英國劍橋Olivetti實驗室提供，數據集包含40個人共400張圖片，收集了每個人在不同時期，不同表情和不同姿態下的10張人臉圖片。每張人臉數據都經過位置校正預處理并被裁剪為32×32像素大小的尺度。實驗中，首先，我們分別在每類中選擇不同數量（l＝2，4，6，8）數據樣本參與學習，通過不同打分機制得到特征點的重要性排序，該數據庫上低秩評分機制中的參數設置為λ＝1.6。然后選擇原始數據的前d個特征子集組成新的數據表示原始數據，利用最近鄰分類器對數據分類。

幾種算法在不同特征數下的分數表現如圖4所示。

圖3 不同算法評價的重要特征幾何分布

圖4 幾種算法在不同特征數下的分類表現

圖4中給出了不同打分算法給數據特征評分后，按特征重要性選擇不同的特征數進行最近鄰分類的結果，L 表示每類參與學習的樣本數。從實驗結果中能夠看出低秩評分算法在不同的數據參與訓練情況下都取得了比其他算法要好的效果。不同算法隨著參與訓練的樣本增多時取得的分類效果也有所提升，但是相對于在PIE 人臉數據庫上取得的效果來說，低秩評分效果的優勢較其他幾種算法而言沒有那么的明顯，主要原因是ORL數據庫中，人臉圖像在姿態上存在較大的差異導致數據的低秩這一特性受到一定程度的破壞，影響了低秩評分的效果。圖5中標記了二維人臉特征的重要性信息，從左向右依次是取訓練樣本數為2，4，6，8的評分結果，圖中越亮的位置表示該特征越重要。從圖5中能夠直觀的看出，經過低秩評分機制獲得的重要性特征集中分布在人臉的嘴巴，鼻子和眼睛部位，說明低秩評分機制能夠更好的揭示特征重要性的真實情況。

圖5 特征重要性分布

4 結束語

本文提出一種基于低秩評分的非監督特征選擇算法。算法綜合考慮了數據特征信息量大小的表達能力，揭示數據全局結構信息和鑒別信息的能力以及相同情況下特征屬性相近性的能力，因此，通過低秩評分特征選擇算法選擇出的重要性特征能夠很好的揭示數據的本質特征信息。同已經存在的方差評分，拉普拉斯評分和稀疏評分特征選擇相比較，低秩評分在數據聚類和分類任務中獲得了更好的表現。尤其在數據類別較多和選擇特征數量較少的情況下，優勢更加明顯，體現了低秩評分特征選擇比傳統的特征選擇算法能夠更好地提升傳統模式識別中聚類和分類算法的性能。

參考文獻：

［1］Gu Q，Li Z，Han J.Generalized fisher score for feature selection ［C］//Proceedings of the International Conference on Uncertainty in Articial Intelligence，2011.

［2］Zhang D，Chen S，Zhou Z H.Constraint score：A new filter method for feature selection with pairwise constraints［J］.Pattern Recognition，2008，41 （5）：1440－1451.

［3］SU Yaru.Research on dimensionality reduction of high－dimensinal data［D］.Hefei：University of Science and Technology of China，2012 （in Chinese）.［蘇雅茹.高維數據的維數約簡算法研究 ［D］.合肥：中國科學技術大學，2012.］

［4］Liu G，Lin Z，Yan S，et al.Robust recovery of subspace structures by low－rank representation ［J］.Pattern Analysis and Machine Intelligence，2012，35 （1）：172－184.

［5］Shen X，Wu Y.A unified approach to salient object detection via low rank matrix recovery ［C］//IEEE Conference on Computer Vision and Pattern Recognition.IEEE，2012：853－860.

［6］Zhang N，Yang J.Low－rank representation based discriminative projection for robust feature extraction ［J］.Neurocomputing，2013，111：13－20.

［7］Zhuang L，Gao H，Huang J，et al.Semisupervised classification via low rank graph ［C］//Sixth International Conference on Image and Graphics.IEEE，2011：511－516.

［8］Candès E J，Li X，Ma Y，et al.Robust principal component analysis？［J］.Journal of the ACM，2011，58 （3）：1－11.

［9］Recht B，Fazel M，Parrilo P A.Guaranteed minimumrank solutions of linear matrix equations via nuclear norm minimization［J］.SIAM Review，2010，52 （3）：471－501.

［10］Xu H，Caramanis C，Sanghavi S.Robust PCA via outlier pursuit［J］.Systems Advances in Neural Information Processing Systems，2010，23：2496－2504.

［11］Lin Z，Chen M，Ma Y.The augmented Lagrange multiplier method for exact recovery of corrupted low－rank matrices［R］.UIUC Technical Report UILU－ENG－09－2215，2009.

［12］Vidal R，Favaro P.Low rank subspace clustering（LRSC）［J］.Pattern Recognition Letters，2014，43：47－61.

［13］Liu G，Lin Z，Yu Y.Robust subspace segmentation by lowrank representation ［C］//Proceedings of the 27th International Conference on Machine Learning，2010：663－670.