局部和稀疏保持無監督特征選擇法

簡彩仁，陳曉云

（福州大學 數學與計算機科學學院，福建 福州350116）

數據維數災難普遍存在于模式識別的許多應用中.高維數據集不僅限制傳統模式識別方法的應用，還會顯著地增加內存和時間開銷.特征選擇是解決這些問題的有效手段之一［1］.特征選擇旨在選擇一些相關的特征代表原始的高維數據，而剔除一些不相關的特征.基于聚類的特征選擇法［2］，利用聚類算法將數據聚類，用得到的類別信息指導特征選擇.然而，由此獲得的判別信息是不可靠的.近年來，隨著流形學習的興起，學者提出了新的無監督特征選擇方法，如拉普拉斯得分［3］、多簇特征選擇方法［4］等.利用L2，1范數的組稀疏性，學者提出了許多嵌入型的特征選擇方法，如稀疏限制的無監督最大化邊緣的特征選擇法［5］、局部和相似保持嵌入特征選擇法［6］.這些方法應用在高維小樣本數據時，需要求解大規模的特征值問題，不利于問題的求解.而聯合特征選擇和子空間學習法［7］、聯合局部保持投影和L2，1范數構造的特征選擇，可以克服大規模特征值的問題.本文提出一種基于局部保持投影和稀疏保持投影的無監督特征選擇方法，并利用L2，1范數的組稀疏性質，通過正則化L2，1范數來選擇特征.

1 相關工作

局部和稀疏保持無監督特征選擇法利用局部保持投影和稀疏保持投影來刻畫數據的本質結構.

1.1 局部保持投影

給定數據集X∈Rm×n，局部保持投影（LPP）［8］的目標函數定義為

式（1）中：yi＝VTxi；W＝Wi，j為相似矩陣.

最小化目標函數可以使降維后的樣本保持原空間的距離.常見的相似矩陣定義是熱核函數.經過簡單的代數運算，LPP求解如下優化問題，即

式（2）中：V為投影矩陣；D為對角矩陣，為圖拉普拉斯矩陣，L＝D－W.

1.2 稀疏保持投影

稀疏保持投影（SPP）［9］用樣本稀疏重構每一個樣本xi∈X，得到求解稀疏表示系數的模型為

式（3）中：‖·‖1為1－范數；si＝［si，1，…，si，n］，si，j反映了xi和xj之間的關系.因此，將S＝（si，j）n×n視為仿射權矩陣是合理的.SPP旨在尋找保持稀疏關系的投影，SPP的目標函數為

式（4）中：V為投影矩陣.為避免平凡解，通常引入正交約束VTXXTV，V可以通過求解廣義特征值問題X（I－S－ST＋STS）XTv＝λXXTv得到.

2 局部和稀疏保持投影特征選擇

2.1 目標函數

將式（2）的局部保持項和式（4）的稀疏保持項相結合，得到目標函數為

引入L2，1范數來選擇有利于保持局部性和稀疏性的相關特征，且為避免平凡解，引入正交約束VTXXTV，得到局部和稀疏保持投影特征選擇模型，即

式（6）中：α為平衡參數，用于平衡局部性和稀疏性；λ為正則參數；‖V‖2.1定義為

當獲得投影矩陣V后，可以利用vi的2范數，即‖vi‖2來選擇特征，其值越大表示該特征越重要.

2.2 模型求解

式（6）可以寫為

式（7）中：A＝αL＋（1－α）（I－S－ST＋STS）.式（7）可以利用廣義特征值問題求解.但是，當X是高維小樣本數據時，式（7）需要求解大規模的特征值問題，且會造成矩陣不可逆的問題.

類似于文獻［7］，采用分步求解的方法避免上述困難.令Y＝XTV，有

式（8）的解為Y＊＝［y1，…，yd］，其為A的最小d個特征值對應的特征向量.求解如下的問題得到式（7）的解，即

該問題可用拉格朗日乘子法迭代求解［7］.拉格朗日函數為

對V求導得

式（11）中：Di，i＝1／（2‖vi‖2），vi≠0，當Di，i＝0時，用一個較小的正數替代，確保D可逆［8］.不難求得

將式（12）代入式（11），可得

由式（12），（13）交替迭代直至收斂，可得投影矩陣V.通過上述討論可以得到局部和稀疏保持投影無監督特征選擇法（LSP）.Input：數據矩陣X；Output：特征子集.1）計算拉普拉斯矩陣L和稀疏表示矩陣S；2）通過式（8）計算最小d個廣義特征值對應的特征向量Y＊；3）求解式（9）得到投影矩陣V；4）將‖vi‖2降序排列，選取前p個特征構成特征子集.

3 實驗分析

相似矩陣通過W＝（|S|＋|ST|）／2計算.其中：S為稀疏矩陣，可以避免近鄰數量的選擇；平衡參數α＝0.8.選用數據方差（DV）、拉普拉斯得分（LS）［3］、多簇特征選擇方法（MCFS）［4］、聯合特征選擇和子空間學習法（JFSSL）［7］作為對比方法.LS，MCFS和JFSSL的近鄰數量取5，MCFS，JFSSL和LSP的降維維數d取類別個數.通過對選取的特征子集進行聚類分析，對比聚類準確率（ACC）來驗證特征選擇的有效性.實驗環境為Windows 7系統，內存為2G，用Matlab 2010b編程實現.

對給定樣本，令ri和si分別為聚類算法得到的類標簽和樣本自帶的類標簽，則聚類準確率［10］為

式（14）中：n為樣本總數；δ（x，y）為函，當x＝y時，其值為1，否則，為0；map（ri）為正交函數，將每一個類標簽ri映射成與樣本自帶的類標簽等價的類標簽.

3.1 數據集

選用6個公開數據集進行實驗，如表1 所示.表1 中：DLBCL，LUNGCANCER，LEUKEMIA，TOX 為基因表達數據集；ORL，PIE為圖像數據集.

3.2 實驗結果與分析

應用每種方法選取特征子集，選取的特征個數依次設為｛5，10，15，…，95，100｝，采用K－means對選取的特征子集進行聚類分析，運行20次.各種方法的平均聚類準確率，如表2所示.聚類準確率與特征數量（n）的關系，如圖1所示.

表1 數據集描述Tab.1 Summary of data sets

表2 平均聚類準確率Tab.2 Average clustering accuracy %

由表2，圖1可知：局部和稀疏保持投影無監督特征選擇法具有良好的特征選擇能力，除TOX 數據集外，其聚類準確率的平均值最高.與MCFS和JFSSL相比，LSP的聚類效果更為理想，這說明稀疏保持性質也可以刻畫數據的本質結構.與DV 和LS相比，因為DV 和LS只考慮獨立的計算每個特征的得分，而忽略了特征之間的相互作用，所以考慮特征之間的關系可以提高聚類準確率.此外，用LSP進行特征選擇與保留全部特征（ALL）可以明顯地提高聚類的準確率.因此，利用局部和稀疏保持投影構造的無監督特征選擇法是有效的.

3.3 參數討論

平衡參數α在｛0，0.1，0.2，…，0.9，1.0｝變化時，平均聚類準確率的情況，如圖2所示.由圖2可知：總體上，平衡參數α對LSP的影響是明顯的；當α為0.6～0.9時，LSP 的聚類準確率在較高的水平上保持相對穩定.在這一范圍內稀疏保持項的比重較大，說明稀疏保持項可以提高特征選擇的能力.

圖1 聚類準確率與選擇的特征數量關系Fig.1 Relation between clustering accuracy and the number of selected features

圖2 不同α的聚類準確率Fig.2 Clustering accuracy of differentα

4 結束語

提出局部和稀疏保持無監督特征選擇法，利用局部保持投影和稀疏保持投影來刻畫數據的本質結構，利用L2，1范數的組稀疏性來篩選特征.實驗結果表明：LSP是一種有效的無監督特征選擇方法.LSP方法的平衡參數α對實驗結果有較大的影響，如何自適應地選取該參數將在今后的研究中給出.

［1］徐峻嶺，周毓明，陳林，等.基于互信息的無監督特征選擇［J］.計算機研究與發展，2012，49（2）：372－382.

［2］張莉，孫鋼，郭軍.基于K－均值聚類的無監督的特征選擇方法［J］.計算機應用研究，2005，22（3）：23－24.

［3］HE Xiao－fei，CAI Deng，NIYOGI P.Laplacian score for feature selection［C］∥Advances in Neural Information Processing Systems.Vancouver：［s.n.］，2005：507－514.

［4］CAI Deng，ZHANG Chi－yuan，HE Xiao－fei.Unsupervised feature selection for multi－cluster data［C］∥Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington DC：ACM，2010：333－342.

［5］YANG Shi－zhun，HOU Chen－ping，NIE Fei－ping，et al.Unsupervised maximum margin feature selection viaL2，1－norm minimization［J］.Neural Computing and Applications，2012，21（7）：1791－1799.

［6］FANG Xiao－zhao，XU Yong，LI Xue－long，et al.Locality and similarity preserving embedding for feature selection［J］.Neurocomputing，2014，128：304－315.

［7］GU Quan－quan，LI Zhen－hui，HAN Jia－wei.Joint feature selection and subspace learning［C］∥The 22nd International Joint Conference on Artificial Intelligence.Barcelona：［s.n.］，2011：1294－1299.

［8］HE Xiao－hui，NIYOGI P.Locality preserving projections［C］∥Proceedings of the 17th Annual Conference on Neural Information Processing Systems.Columbia：［s.n.］，2003：153－160.

［9］QIAO Li－shan，CHEN Song－can，TAN Xiao－yang.Sparsity preserving projections with applications to face recognition［J］.Pattern Recognition，2010，43（1）：331－341.

［10］CAI Deng，HE Xiao－fei，WU Xiao－yun，et al.Non－negative matrix factorization on manifold［C］∥Proceedings of International Conference on Data Mining.Pisa：IEEE Press，2008：63－72.