基于局部鄰域嵌入的無監(jiān)督特征選擇

脫倩娟，　趙　紅

(閩南師范大學(xué) 福建省粒計(jì)算重點(diǎn)實(shí)驗(yàn)室　福建 漳州 363000)

?

基于局部鄰域嵌入的無監(jiān)督特征選擇

脫倩娟，趙紅

(閩南師范大學(xué) 福建省粒計(jì)算重點(diǎn)實(shí)驗(yàn)室福建 漳州 363000)

機(jī)器學(xué)習(xí)中，特征選擇可以有效降低數(shù)據(jù)維度.考慮到流形學(xué)習(xí)能夠保持原始數(shù)據(jù)的幾何結(jié)構(gòu)，l2,1范數(shù)能夠防止過擬合，提升模型的泛化能力，將二者結(jié)合起來可以提高特征選擇的效果和效率.結(jié)合局部鄰域嵌入(LNE)算法和l2,1范數(shù)，提出一種新的無監(jiān)督特征選擇方法.其主要思想是：首先利用數(shù)據(jù)樣本和鄰域間的距離以及重構(gòu)系數(shù)構(gòu)造相似矩陣；其次構(gòu)建低維空間并結(jié)合l2,1范數(shù)進(jìn)行稀疏回歸；最后計(jì)算每個特征的重要性并選出最優(yōu)特征子集.實(shí)驗(yàn)通過與幾種典型的特征選擇算法做對比，驗(yàn)證了所提算法的有效性.

機(jī)器學(xué)習(xí)； 局部鄰域嵌入； 流形學(xué)習(xí)； 無監(jiān)督特征選擇

0　引言

在當(dāng)今社會中，隨著科技信息的發(fā)展，計(jì)算機(jī)視覺、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、信息檢索等研究領(lǐng)域出現(xiàn)的數(shù)據(jù)大都呈現(xiàn)出高維狀態(tài).高維數(shù)據(jù)中通常含有冗余維度，直接對高維數(shù)據(jù)進(jìn)行研究不但會消耗大量時(shí)間，而且還會對研究任務(wù)造成不良影響.因此，對數(shù)據(jù)進(jìn)行降維顯得尤為重要，將高維數(shù)據(jù)轉(zhuǎn)化成低維數(shù)據(jù)并且盡量保留原有數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)是降維的目標(biāo)和方向.

特征選擇是一種非常有效的降維方法，根據(jù)原始數(shù)據(jù)有無標(biāo)簽信息，可以分為有監(jiān)督的特征選擇[1-2]和無監(jiān)督的特征選擇[3-4].有監(jiān)督的特征選擇利用標(biāo)簽信息可以準(zhǔn)確快速地選出對分類有利的特征，但對數(shù)據(jù)進(jìn)行標(biāo)記需要投入大量的人力、物力，這就意味著大多數(shù)數(shù)據(jù)可能沒有標(biāo)簽，在實(shí)際應(yīng)用中處理無標(biāo)簽數(shù)據(jù)經(jīng)常使用無監(jiān)督的特征選擇算法.傳統(tǒng)的無監(jiān)督特征選擇算法[5]對特征進(jìn)行單獨(dú)評價(jià)沒有考慮到數(shù)據(jù)的整體分布情況，有可能選不出全局最優(yōu)特征子集.為了避免該問題，一些無監(jiān)督特征選擇算法[6-7]從全局考慮每個特征的重要性，選出的特征子集能夠較好地保持原始數(shù)據(jù)的幾何結(jié)構(gòu).如文獻(xiàn)[3]提出的多類簇特征選擇方法(MCFS)，它通過解決稀疏特征問題得到低維嵌入空間，進(jìn)而解決特征選擇問題；文獻(xiàn)[6]利用局部線性嵌入算法獲得局部鄰域之間的重構(gòu)關(guān)系，結(jié)合l1范數(shù)選出最優(yōu)特征子集；文獻(xiàn)[7]提出一種無監(jiān)督判別特征選擇方法(UDFS)，它對每個樣本定義一個局部判別得分，利用l2,1范數(shù)[8]得到最優(yōu)特征子集.

上述文獻(xiàn)[3]和[6]中所提的方法都使用了流形學(xué)習(xí)[9-11]的思想.使用流形學(xué)習(xí)進(jìn)行特征選擇不但能夠找到高維空間中的低維流形達(dá)到降維的目的，而且可以提高數(shù)據(jù)處理的效率.常見的流形學(xué)習(xí)方法可以分為非線性流形學(xué)習(xí)和線性流形學(xué)習(xí).非線性流形學(xué)習(xí)算法包括等距映射(ISOMAP)[9]、局部線性嵌入(LLE)[10-12]、拉普拉斯特征映射(LE)[13]等.線性流形學(xué)習(xí)算法包括主成分分析(PCA)[14]、線性區(qū)別分析(LDA)[15].有的線性流形學(xué)習(xí)算法則是對非線性流形學(xué)習(xí)算法的線性拓展，如局部保持投影(LPP)[16]是拉普拉斯特征映射(LE)的線性逼近，鄰域保持嵌入(NPE)[17]是局部線性嵌入(LLE)的線性逼近.

在流形學(xué)習(xí)中，構(gòu)造數(shù)據(jù)之間的相似關(guān)系起著至關(guān)重要的作用，它的構(gòu)建結(jié)果可能直接影響到最終的嵌入結(jié)果.文獻(xiàn)[18]提到兩種常見的構(gòu)造相似矩陣的方式：一種是利用成對數(shù)據(jù)之間的距離，如LE選用熱核函數(shù)確定數(shù)據(jù)點(diǎn)之間的權(quán)重大小，對噪聲和離群點(diǎn)比較敏感；另一種是利用數(shù)據(jù)的重構(gòu)系數(shù)，如LLE計(jì)算局部線性重構(gòu)系數(shù)來保持原始數(shù)據(jù)的流形結(jié)構(gòu)，對數(shù)據(jù)樣本大小和鄰域個數(shù)比較敏感.單獨(dú)使用其中一種方式構(gòu)造相似矩陣時(shí)，數(shù)據(jù)樣本關(guān)系有可能被固定地表示成一種形式.比如熱核函數(shù)中的參數(shù)一旦確定，樣本間的相似關(guān)系就會被確定唯一，這不符合現(xiàn)實(shí)世界的數(shù)據(jù)分布規(guī)律.文獻(xiàn)[18]將兩種方法結(jié)合起來，不但彌補(bǔ)了各自的缺陷而且更具有一般性，得到的低維嵌入空間使得數(shù)據(jù)類簇更明顯.在得到的低維空間中加入l2,1范數(shù)不但可以防止過擬合，提升模型的泛化能力，而且可以達(dá)到去噪的效果.

本文在文獻(xiàn)[18]的思想基礎(chǔ)上結(jié)合l2,1范數(shù)提出了基于局部鄰域嵌入的無監(jiān)督特征選擇方法(UFLNE).首先，計(jì)算數(shù)據(jù)和其鄰域間的歐氏距離以及重構(gòu)系數(shù)，并結(jié)合二者構(gòu)造相似矩陣，避免了單獨(dú)使用可能帶來的影響；其次，利用得到的相似矩陣構(gòu)建低維嵌入空間，很好地保持了原始數(shù)據(jù)集的流形結(jié)構(gòu)；再次，使用l2,1范數(shù)進(jìn)行稀疏回歸，準(zhǔn)確計(jì)算每個特征的重要性；最后，根據(jù)特征的重要性進(jìn)行降序排列，選出指定個數(shù)的特征.

1　算法的基本原理

算法主要分為兩部分：第一部分利用局部鄰域嵌入算法(LNE)構(gòu)建低維嵌入空間；第二部分利用l2,1范數(shù)進(jìn)行稀疏回歸得到每個嵌入低維空間的特征重要性.

1.1LNE構(gòu)建低維嵌入空間

局部鄰域嵌入算法假設(shè)每個數(shù)據(jù)點(diǎn)都存在一個很小的鄰域，它們近似于低維任意子空間的同一流形.假設(shè)數(shù)據(jù)矩陣為X=[x1, x2, … , xn]∈Rm×n，它的低維嵌入空間為Y=[y1, y2, …, yn]∈Rc×n(c≤m).

局部鄰域嵌入算法(LNE)的步驟如下.

1) 尋找k近鄰點(diǎn).

對于每一個數(shù)據(jù)點(diǎn)xi，計(jì)算xi和其他數(shù)據(jù)點(diǎn)之間的歐氏距離.然后選出xi的k個近鄰點(diǎn)，記為：

其中:將對應(yīng)的距離記為如下形式：

2) 利用重構(gòu)系數(shù)結(jié)合成對距離構(gòu)造相似矩陣.具體形式為：

(1)

(2)

其中：Si=diag(S)，θ∈[0,1]是平衡參數(shù).使用Lagrangian乘數(shù)法后，對Ci求偏導(dǎo)，并令其為0，得到：

(3)

3) 求低維嵌入空間.

為使W在低維空間中保持不變，低維嵌入空間Y可由下列目標(biāo)函數(shù)得到：

(4)

其中:Q=(1-W)T(1-W).將式(4)轉(zhuǎn)化為下列廣義特征值問題：

QY=λY,

(5)

得到Q的特征值與特征向量，由于最小特征值經(jīng)常趨于零，所以低維嵌入空間Y=[y1, y2, …, yn]∈Rc×n由第2小特征值到第c+1小特征值所對應(yīng)的特征向量構(gòu)成.

1.2基于l2,1范數(shù)的特征選擇

在低維嵌入空間基礎(chǔ)上，通過最小化式(6)的目標(biāo)函數(shù)：

(6)

那么每個嵌入原始空間的特征重要性由式(7)得到：

(7)

根據(jù)式(7)將所有的特征進(jìn)行降序排列，選出最重要的(FeatureScore越大越重要)d個特征.

具體的算法表述如下.

算法：基于局部鄰域嵌入的無監(jiān)督特征選擇(UFLNE).

輸入：數(shù)據(jù)集X=[x1,x2, … ,xn]∈Rm×n(n是樣本個數(shù)，m是特征個數(shù))，低維嵌入空間的維數(shù)c，選擇的特征數(shù)目d，近鄰個數(shù)k，平衡參數(shù)θ.

輸出：指定個數(shù)的特征.

步驟1：找出每個數(shù)據(jù)樣本的k近鄰，并利用式(1)和式(3)構(gòu)造相似矩陣；

步驟2：求解式(5)，得到Q的特征值特征向量，用Q的第2小特征值到第c+1小特征值所對應(yīng)的特征向量構(gòu)成低維嵌入空間Y=[y1,y2, … ,yn]∈Rc×n；

步驟3：求出式(6)中的稀疏矩陣F∈Rm×c；

步驟4：根據(jù)式(7)計(jì)算每個特征的重要性得分；

步驟5：選出d個FeatureScore最大的特征.

根據(jù)上述的算法步驟，每步時(shí)間復(fù)雜度分別為：步驟1中尋找k近鄰需要O(n2k)，求成對距離需要O(n2m)；步驟2中求解Q的特征值特征向量需要O(n2m)；步驟3中求解稀疏矩陣需要O(m2n)；步驟4中計(jì)算每個特征的重要性得分需要O(cm)；步驟5中根據(jù)FeatureScore選擇特征需要O(mlogm).所以算法的整體時(shí)間復(fù)雜度為O(n2k+n2m+m2n+cm+mlogm).

2　仿真實(shí)驗(yàn)

實(shí)驗(yàn)選用K-means算法進(jìn)行聚類，進(jìn)行10次實(shí)驗(yàn)記錄平均值.將得到的結(jié)果和多類簇特征選擇(MCFS)、無監(jiān)督判別特征選擇(UDFS)、基于拉普拉斯打分的特征選擇(LaplacianScore)[15]、基于最大方差的特征選擇(MaxVaiance)4種典型的特征選擇算法以及選擇所有特征(AllFeature)時(shí)的結(jié)果進(jìn)行比較.利用人工標(biāo)記的數(shù)據(jù)標(biāo)簽與聚類后的數(shù)據(jù)標(biāo)簽之間的歸一化互信息(取值范圍在0和1之間)和聚類精度去衡量不同算法在選擇不同特征時(shí)的效果，值的大小可以體現(xiàn)算法的好壞.

2.1實(shí)驗(yàn)數(shù)據(jù)集

本文使用以下4個現(xiàn)實(shí)世界中的數(shù)據(jù)集[19]：圖像數(shù)據(jù)集COIL20，字母識別數(shù)據(jù)集ISOLET，生物數(shù)據(jù)集Lymphoma，Lung_discrete.具體情況如表1.

表1　實(shí)驗(yàn)數(shù)據(jù)集的具體情況Tab.1　The whole situation of experimental data sets

2.2實(shí)驗(yàn)的參數(shù)設(shè)置

本文算法及對比算法的聚類數(shù)目q設(shè)置為各數(shù)據(jù)標(biāo)簽包含的類別數(shù)，即分別為20，9，26，7.MCFS和提出的算法UFLNE需要設(shè)置鄰域k，這里統(tǒng)一指定k=5.利用網(wǎng)絡(luò)搜索策略來調(diào)節(jié)UFLNE中的稀疏參數(shù)α和UDFS中的稀疏參數(shù)γ，設(shè)置參數(shù)均為{10-3, 10-2, 10-1, 1, 101, 102, 103}，記錄每種算法在不同參數(shù)時(shí)的最好結(jié)果.UFLNE中還需要設(shè)置一個控制平衡的參數(shù)θ，令θ=0.25.最后將所有特征選擇算法中的特征選擇數(shù)目均設(shè)置為：{10, 20,…,100, 120, 140, … , 200}.

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

表2和表3分別列出不同特征選擇算法在選擇120特征時(shí)的聚類精度和歸一化互信息.從表2和表3中的數(shù)據(jù)對比信息可以看出本文所提算法在兩種評價(jià)指標(biāo)下的結(jié)果大部分優(yōu)于對比算法.

此外，為了比較不同的特征選擇數(shù)目對算法性能的影響，用圖1和圖2顯示各個算法在選擇不同特征數(shù)時(shí)的實(shí)驗(yàn)結(jié)果.圖1和圖2中的橫坐標(biāo)均表示選擇的特征個數(shù)，縱坐標(biāo)分別表示聚類精度和歸一化互信息.從圖中可以看出隨著選擇的特征數(shù)目的增加,聚類精度和歸一化互信息的值也會發(fā)生相應(yīng)的變化.在數(shù)據(jù)集COIL20和Lung_discrete上當(dāng)特征個數(shù)小于50時(shí)所提算法的效果尤為突出，這說明本文算法在某些數(shù)據(jù)集上只要選擇很少的特征就能達(dá)到不錯的效果.在數(shù)據(jù)集Lymphoma和ISOLET上當(dāng)選擇的特征數(shù)目增加到一定程度時(shí)所提算法的聚類精度和歸一化互信息的值會逐漸優(yōu)于對比算法.從總體性能上，可以發(fā)現(xiàn)利用本文算法進(jìn)行特征選擇會比一般的特征選擇算法效果好.

表2　不同特征選擇算法的聚類精度Tab.2　Clustering accuracy of different feature selection algorithms

注：每種算法的最好結(jié)果用粗體標(biāo)注，第二好結(jié)果用下劃線標(biāo)注.

表3　不同特征選擇算法歸一化互信息Tab.3　Normalized mutual information of different feature selection algorithms

注：每種算法的最好結(jié)果用粗體標(biāo)注，第二好結(jié)果用下劃線標(biāo)注.

圖1　不同特征數(shù)時(shí)各個算法的聚類精度Fig.1　Clustering accuracy of different feature selection algorithms in different number of the selected features

圖2　不同特征數(shù)時(shí)各個算法的歸一化互信息Fig.2　Normalized mutual information of different feature selection algorithms in different number of the selected features

本文算法是一種基于流行學(xué)習(xí)的特征選擇算法，結(jié)合局部鄰域嵌入和l2,1范數(shù)，準(zhǔn)確地評價(jià)了每個數(shù)據(jù)樣本的重要性，得到的全局最優(yōu)解能夠避免了一些貪心算法可能帶來的缺陷.但是，本文算法將利用LNE構(gòu)建低維空間和利用l2,1范數(shù)進(jìn)行稀疏回歸分為兩個獨(dú)立的部分，不能將構(gòu)建低維空間的誤差和特征選擇的誤差綜合考慮.探索它們之間的相互聯(lián)系，將其統(tǒng)一在同一框架中將是進(jìn)一步學(xué)習(xí)研究的方向.

[1]DUDA R O, HART P E, STORK D G. Pattern classification[M]. New York: John Willey & Sons, 2004.

[2]COVER T M, THOMAS J A. Elements of information theory[M]. 2nd edition. New York: John Willey & Sons, 2003.

[3]CAI D, ZHANG C, HE X. Unsupervised feature selection for multi-cluster data[C]// Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. Washington, 2010: 333-342.

[4]HE X, CAI D, NIYOGI P.Laplacian score for feature selection[C]// Advances in neural information processing systems. Columbia, 2005: 507-514.

[5]PENG H, LONG F, DING C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy[J]. Pattern analysis and machine intelligence, IEEE transactions on, 2005, 27(8): 1226-1238.

[6]譚臺哲, 葉青, 尚鵬. 基于局部重構(gòu)的無監(jiān)督特征選擇方法[J]. 計(jì)算機(jī)應(yīng)用研究,2014, 31(9): 2828-2831.

[7]YANG Y,SHEN H T, MA Z, et al.l2,1norm regularized discriminative feature selection for unsupervised learning[C]// IJCAI Proceedings: international joint conference on artificial intelligence. Bacelona, 2011.

[8]LI Z, YANG Y, LIU J, et al. Unsupervised feature selection using nonnegative spectral analysis[C]// National conference on artificial intelligence. Toronto, 2012: 1026-1032.

[9]TENENBAUM J B, DE SILVA V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319-2323.

[10]ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J].Science, 2000, 290(5500): 2323-2326.

[11]SAUL L K, ROWEIS S T. Think globally, fit locally: unsupervised learning of low dimensional manifolds[J]. The journal of machine learning research, 2003, 4(6): 119-155.

[12]馬麗, 董唯光, 梁金平, 等. 基于隨機(jī)投影的正交判別流形學(xué)習(xí)算法[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2016, 48(1): 102-109.

[13]BELKIN M, NIYOGI P. Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Advances in neural information processing systems. Denver, 2001, 585-591.

[14]SCH?LKOPF B, SMOLA A, MüLLER K R. Kernel principal component analysis[C]// International conference on artificial neural networks. Berlin, 1997: 583-588.

[15]BELHUMEUR P N, HESPANHA J P, KRIEGMAN D J. Eigenfaces vs. fisherfaces: Recognition using class specific linear projection[J]. Pattern analysis and machine intelligence, IEEE transactions on, 1997, 19(7): 711-720.

[16]HE X F, NIYOGI P. Locality preserving projections[J]. Neural information processing systems, 2005, 45(1): 186-197.

[17]HE X, CAI D, YAN S, et al. Neighborhood preserving embedding[C]// Tenth IEEE international conference on computer vision (ICCV'05). Beijing, 2005: 1208-1213.

[18]ZHEN L, PENG X, PENG D. Local neighborhood embedding for unsupervised nonlinear dimension reduction[J]. Journal of software, 2013, 8(2): 410-417.

[19]LI J D, CHENG K W, LIU H. Feature selection datasets[EB/OL].[2016-09-14].http://featureselection.asu.edu/datasets.php.

(責(zé)任編輯：王浩毅)

Unsupervised Feature Selection Based on Local Neighborhood Embedding

TUO Qianjuan,ZHAO Hong

(LaboratoryofGranularComputing,MinnanNormalUniversity,Zhangzhou363000,China)

In machine learning, feature selection can effectively reduce the data dimension. Manifold learning andl2,1norm can improve the effectiveness and efficiency of feature selection. Manifold learning can maintain the geometric structure of the original data.l2,1norm can prevent the over fitting, and it can enhance the generalization ability of the model. A new unsupervised feature selection method based on local neighborhood embedding (LNE) algorithm andl2,1norm were proposed. The main ideas were as following. Firstly, it constructed similar matrix by the distances and reconstruction coefficients between each data and its neighborhood. Secondly, it built a low dimensional space and usedl2,1norm sparse regression. Finally, it calculated the importance of each feature and chose the optimal feature subset. Experimental results showed the effectiveness of the proposed algorithm by comparing it with several typical feature selection algorithms.

machine learning; local neighborhood embedding; manifold learning; unsupervised feature selection

2016-06-04

國家自然科學(xué)基金資助項(xiàng)目(61379049,61472406);福建省自然科學(xué)基金資助項(xiàng)目(2015J01269);漳州市自然科學(xué)基金資助項(xiàng)目(ZZ2016J35).

脫倩娟(1991—)，女，甘肅慶陽人，碩士研究生,主要從事機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘研究，E-mail:qianjuan_Tuo@163.com；通訊作者:趙紅(1979—)，女，黑龍江哈爾濱人，副教授，主要從事粒計(jì)算、代價(jià)敏感學(xué)習(xí)、分層分類學(xué)習(xí)研究,E-mail:HongZhaocn@163.com.

TP181

A

1671-6841(2016)03-0057-06

10.13705/j.issn.1671-6841.2016087

引用本文:脫倩娟，趙紅．基于局部鄰域嵌入的無監(jiān)督特征選擇[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016，48(3)：57-62．