局部和稀疏保持無監(jiān)督特征選擇法

簡(jiǎn)彩仁，陳曉云

（福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州350116）

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

1 相關(guān)工作

局部和稀疏保持無監(jiān)督特征選擇法利用局部保持投影和稀疏保持投影來刻畫數(shù)據(jù)的本質(zhì)結(jié)構(gòu).

1.1 局部保持投影

給定數(shù)據(jù)集X∈Rm×n，局部保持投影（LPP）［8］的目標(biāo)函數(shù)定義為

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

最小化目標(biāo)函數(shù)可以使降維后的樣本保持原空間的距離.常見的相似矩陣定義是熱核函數(shù).經(jīng)過簡(jiǎn)單的代數(shù)運(yùn)算，LPP求解如下優(yōu)化問題，即

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

1.2 稀疏保持投影

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

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

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

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

2.1 目標(biāo)函數(shù)

將式（2）的局部保持項(xiàng)和式（4）的稀疏保持項(xiàng)相結(jié)合，得到目標(biāo)函數(shù)為

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

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

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

2.2 模型求解

式（6）可以寫為

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

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

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

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

對(duì)V求導(dǎo)得

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

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

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

3 實(shí)驗(yàn)分析

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

對(duì)給定樣本，令ri和si分別為聚類算法得到的類標(biāo)簽和樣本自帶的類標(biāo)簽，則聚類準(zhǔn)確率［10］為

式（14）中：n為樣本總數(shù)；δ（x，y）為函，當(dāng)x＝y(tǒng)時(shí)，其值為1，否則，為0；map（ri）為正交函數(shù)，將每一個(gè)類標(biāo)簽ri映射成與樣本自帶的類標(biāo)簽等價(jià)的類標(biāo)簽.

3.1 數(shù)據(jù)集

選用6個(gè)公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，如表1 所示.表1 中：DLBCL，LUNGCANCER，LEUKEMIA，TOX 為基因表達(dá)數(shù)據(jù)集；ORL，PIE為圖像數(shù)據(jù)集.

3.2 實(shí)驗(yàn)結(jié)果與分析

應(yīng)用每種方法選取特征子集，選取的特征個(gè)數(shù)依次設(shè)為｛5，10，15，…，95，100｝，采用K－means對(duì)選取的特征子集進(jìn)行聚類分析，運(yùn)行20次.各種方法的平均聚類準(zhǔn)確率，如表2所示.聚類準(zhǔn)確率與特征數(shù)量（n）的關(guān)系，如圖1所示.

表1 數(shù)據(jù)集描述Tab.1 Summary of data sets

表2 平均聚類準(zhǔn)確率Tab.2 Average clustering accuracy %

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

3.3 參數(shù)討論

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

圖1 聚類準(zhǔn)確率與選擇的特征數(shù)量關(guān)系Fig.1 Relation between clustering accuracy and the number of selected features

圖2 不同α的聚類準(zhǔn)確率Fig.2 Clustering accuracy of differentα

4 結(jié)束語(yǔ)

提出局部和稀疏保持無監(jiān)督特征選擇法，利用局部保持投影和稀疏保持投影來刻畫數(shù)據(jù)的本質(zhì)結(jié)構(gòu)，利用L2，1范數(shù)的組稀疏性來篩選特征.實(shí)驗(yàn)結(jié)果表明：LSP是一種有效的無監(jiān)督特征選擇方法.LSP方法的平衡參數(shù)α對(duì)實(shí)驗(yàn)結(jié)果有較大的影響，如何自適應(yīng)地選取該參數(shù)將在今后的研究中給出.

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

［2］張莉，孫鋼，郭軍.基于K－均值聚類的無監(jiān)督的特征選擇方法［J］.計(jì)算機(jī)應(yīng)用研究，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－h(huán)ui，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－h(huán)ui，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.