基于錨點策略的快速無監(jiān)督特征選擇算法*

朱建勇, 徐 彬, 楊 輝, 聶飛平

(1.華東交通大學 電氣與自動化工程學院,江西 南昌 330013； 2.江西省先進控制與優(yōu)化重點實驗室,江西 南昌 330013； 3.西北工業(yè)大學 計算機科學學院 光學影像分析與學習中心, 陜西 西安 710072)

0 引 言

網絡信息技術的發(fā)展迅速擴大了信息數(shù)據樣本的數(shù)量和維度,數(shù)據模型也逐漸呈現(xiàn)出高度復雜的特征[1]。從高維數(shù)據中提取有用的關鍵信息現(xiàn)在成為數(shù)據挖掘、計算機視覺、機器學習等領域的研究熱點。在特定的應用中,如人臉識別[2]、文本檢索[3]、圖像分類[4]等,高維數(shù)據給信息存儲帶來了巨大的壓力。特征選擇是應對數(shù)據“維數(shù)災難”的典型方法,特征選擇在樣本的原始特征空間中篩選具有代表性的特征子集,沒有改變特征屬性。依據是否利用數(shù)據標簽,特征選擇可分為有監(jiān)督特征選擇[5]、半監(jiān)督特征選擇[6]和無監(jiān)督特征選擇[7]。有監(jiān)督和半監(jiān)督特征選擇可以根據數(shù)據的標簽信息對模型進行訓練,選擇代表性的特征子集相對簡單有效,無監(jiān)督特征選擇則是從整個特征集合中選擇特征,而無需使用標簽信息。一般來說,在大多數(shù)實際情況下獲得的都是未標記的數(shù)據,此時標記大量高維度數(shù)據是不劃算和不現(xiàn)實的[8]。在這類場景中,無監(jiān)督特征選擇方法是一個可靠的選擇。

根據特征評價和選擇中特征結合方式歸類,特征選擇方法主要分為3類：過濾式方法、包裹式方法和嵌入式方法。嵌入式方法用于處理大規(guī)模數(shù)據時效率高、效果理想,受到研究者的青睞。由于局部結構能更好地反映數(shù)據的實際情況,大多數(shù)嵌入式特征選擇方法都是探索局部流形結構。真實數(shù)據的稀疏性使得研究者將稀疏結構學習引入到特征學習算法的框架中。Liu W等人[9]利用稀疏學習決策樹方法實現(xiàn)了對高維數(shù)據的預測,提高了算法的魯棒性和穩(wěn)定性。傳統(tǒng)的基于圖的特征選擇方法通常需要經過兩個步驟：探索數(shù)據結構構造相似度矩陣,利用稀疏正則化方法選擇具有代表性的特征。

傳統(tǒng)的譜方法[10]往往使用K近鄰法來構造幾乎滿秩的相似矩陣,這使得圖的構造和譜分析非常耗時,且時間復雜度至少為O(n2d)。為了降低算法的計算復雜度,加快相似矩陣的構造,受構造可伸縮大圖[11]的啟發(fā),采用錨點嵌入策略構造稀疏相似矩陣。該方法的計算復雜度為O(nd),大大加快了相似矩陣的構造速度。稀疏正則化選擇特征的正則項研究者通常傾向于使用L2,1范數(shù),Yang Y等人[12]將結構學習與特征選擇相結合,利用判別分析特征的重要性來選擇特征。Han K等人[13]也提出使用L2,1范數(shù)對編碼器的權重進行稀疏正則化。值得注意的是,這些算法在優(yōu)化L2,1范數(shù)時不可避免會引入正則化參數(shù),帶來復雜的調參問題。

為此,本文提出了一種基于錨點策略的快速無監(jiān)督特征選擇(fast anchor-based unsupervised feature selection,FAFS)算法。該算法利用正交局部保持投影探索數(shù)據內部局部幾何流形結構,對投影矩陣施加L2,0范數(shù)約束動態(tài)選擇最優(yōu)特征組合,采用嵌入錨點策略快速構建數(shù)據矩陣相似圖,并設計了一個有效的迭代算法在避免引入正則化參數(shù)的情況下優(yōu)化目標函數(shù)問題。通過在4個公開數(shù)據集上比較其他4種無監(jiān)督特征選擇方法,實驗結果表明:FAFS算法選擇了更優(yōu)的特征,算法效率也得到了提升。

1 基于錨點策略的FAFS算法

1.1 FAFS目標函數(shù)

本文利用局部保持投影(LPP)[14]的數(shù)據空間結構保持思想,引入L2,0范數(shù)約束,通過結構化稀疏投影矩陣選擇特征。為增強算法的線性映射能力,同時對投影矩陣施加單位正交約束,這對算法處理后的數(shù)據重構提供了便利。

若給定一個原始樣本數(shù)據矩陣,X=[x1,x2,…,xn]∈d×n,W∈d×m為投影矩陣,Y=[y1,y2,…,yn]∈m×n為數(shù)據投影后的矩陣,且有Y=WTX。定義Tr(·)為矩陣的跡,‖·‖2,0為矩陣的L2,0范數(shù),LPP算法解決如下問題

(1)

式中Sij為原始樣本數(shù)據點xi和xj之間的相似度,是原始數(shù)據點之間距離的度量。該目標函數(shù)盡量保持數(shù)據點投影前后的距離關系,如果樣本數(shù)據點xi和xj接近,那么投影后的yi和yj也接近,此時Sij很大,反之則Sij值很小。上述目標函數(shù)可以進一步推導

=WTXDXTW-WTXSXTW

=WTX(D-S)XTW=WTXLXTW

(2)

對投影矩陣施加單位正交約束,同時約束投影矩陣W的L2,0范數(shù)等于k,‖W‖2,0=k,這表示W矩陣只有k個非零行,對應的序號即為所選擇的k個特征的索引。將目標函數(shù)用矩陣跡的形式表示為

min Tr(WTXLXTW)，s.t.WTW=I,‖W‖2,0=k

(3)

目標函數(shù)中k值為預先設置的要選擇的特征數(shù)目,投影矩陣W為需要優(yōu)化求解的未知量。優(yōu)化目標函數(shù)前提是求出L矩陣,L矩陣可以通過構造數(shù)據矩陣相似圖來求得,所以接下來要先求解數(shù)據矩陣的相似度矩陣。

1.2 基于錨點策略的相似圖學習

傳統(tǒng)的構造數(shù)據矩陣相似圖多采用譜分析法?；谧V分析的K近鄰方法構造的相似度矩陣通常幾乎是滿秩的,這無疑會給算法帶來巨大的時間和計算開銷。另外,基于譜分析方法,采用高斯核函數(shù)來度量數(shù)據點之間的相似度也會引入帶寬參數(shù)。而采用嵌入錨點的方法學習到的是樣本數(shù)據的高度稀疏、對稱且半正定的相似度矩陣。在基于錨點策略的圖相似矩陣的構造中,首先要考慮的是如何生成錨點?；阱^點策略的方法通過從原始n個數(shù)據樣本中找到p(p?n)個錨點構建數(shù)據矩陣的相似圖,然后計算數(shù)據點與其近鄰的c個錨點之間的距離。數(shù)據點與錨點連接示意如圖1所示。

圖1 數(shù)據點與錨點連接示意

數(shù)據點與錨點是稀疏連接,最終得到的相似度矩陣也是高度稀疏的。本文使用K-means聚類方法生成標志性的錨點,定義G∈d×p為選定的錨點矩陣,Gi為第i個原始數(shù)據采樣點的c個最近鄰錨集。第i個樣本數(shù)據點與其c個近鄰錨之間的相似度計算滿足如下模型問題

(5)用拉格朗日乘子法對式(5)進行求導得到拉格朗日函數(shù)為

(6)

式(6)優(yōu)化求解的詳細過程可以參見文獻[15],最后求解結果為

(7)

錨點相似度矩陣的表達式只包含一個預先設置的整數(shù)近鄰c參數(shù),并且公式只涉及簡單的運算,相似度值對應距離屬性。原始樣本數(shù)據的相似度矩陣可以在錨點相似度矩陣的結果基礎上,按照Liu W等人[12]提出的方法設計,如下所示

(8)

式中Λ為對角矩陣,其對角元素為E矩陣的列和。此外,相似度矩陣S為一個稀疏對稱、PSD且雙隨機矩陣,這些性質對于圖的學習和提高算法的性能非常有用。

2 目標函數(shù)求解

2.1 模型優(yōu)化

在優(yōu)化目標函數(shù)問題時,由于目標函數(shù)中含有L2,0范數(shù)NP難問題求解比較困難,許多研究者往往做近似處理,轉化為求解L2,1范數(shù)問題

min Tr (WTXLXTW)+λ‖W‖2,1，s.t.WTW=I

(9)

式(9)問題需要迭代優(yōu)化,但值得注意的是目標函數(shù)中涉及的正則化參數(shù)很難調整。對于不同類型的數(shù)據,正則化參數(shù)的取值可能不固定,這會削弱模型的泛化能力。為避免參數(shù)調整問題,本文巧妙設計了一個迭代算法直接求解L2,0范數(shù)模型問題,并且不會引入正則化參數(shù)。首先對目標函數(shù)式(3)作一個等價變換

max Tr[WT(λI-XLXT)W]，s.t.WTW=I,‖W‖2,0=k

(10)

式中λ的值為矩陣XLXT的最大特征值,變換目的是保證矩陣λI-XLXT半正定,這也是迭代算法需滿足的前提條件。令H=λI-XLXT,目標函數(shù)簡化為

max Tr[WTHW]，s.t.WTW=I,‖W‖2,0=k

(11)

針對目標函數(shù)式(11),巧妙地設計了一個由原始矩陣近似的低秩代理協(xié)方差矩陣P,迭代更新并求解了一般的L2,0范數(shù)目標函數(shù)問題。利用低秩代理協(xié)方差矩陣P參與行選擇矩陣的映射,并選取行選擇矩陣的特定k行進行迭代更新,得到目標函數(shù)的最優(yōu)投影矩陣W。迭代求解投影矩陣W的流程如算法1所示。

算法1迭代優(yōu)化投影矩陣W

輸入：樣本數(shù)據矩陣X,選擇的特征數(shù)k;

Step1：隨機初始化一個投影矩陣W滿足WTW=I;

Step2：計算矩陣P=HW(WTHW)-1WTH;

Step3：根據P的對角線元素選取最大的k個,其對應位置的k行序號為W非零行的位置,W其余行元素置0;

Step4：計算M=HW,取對應位置的k行元素組成∈k×m,用的任意一個標準正交基,來更新W對應位置的行,W其余的行為0;

Step5：迭代Step2-Step4直到收斂;

輸出:投影矩陣W。

2.2 收斂性證明

針對模型優(yōu)化迭代算法全局收斂性問題,下面給出兩個引理進行證明。

引理1[16]：若A∈n×m,B∈n×m,并且n≤m,設λi(A)為n階矩陣A的特征值(i=1,…,n),則有?1≤i≤n︰λi(BA)=λi(AB),且有?n+1≤i≤m︰λi(BA)=0。

定理1：對于算法中的Wt+1,有

(12)

證明

(13)

其中，第一個不等式來自Wt+1的定義；第二個不等式根據引理2；最后一個等式根據引理1,這是因為有

k+1≤i≤d︰λi(X)=0

(14)

證畢。算法中的迭代優(yōu)化算法在每次迭代中單調增加問題(10)的目標函數(shù)值,直至收斂。

3 實驗與分析

選取了4個公開的標準數(shù)據集實驗,并用分類正確率(accuracy,ACC)和標準化互信息(normalized mutual information,NMI)2個指標與其他4種無監(jiān)督特征選擇算法進行了比較,評價和分析算法性能。記錄算法運行時間,繪制目標函數(shù)值變化曲線,通過實驗證明了算法的收斂性。

3.1 數(shù)據集

實驗共選取了4個標準數(shù)據集：圖像數(shù)據集COIL20,包含從20個物體的不同角度拍攝的1 440張照片；ORL面部數(shù)據集,它是40個人的10種不同表情拍攝的400張圖像；顯著性檢測圖像數(shù)據集MSRA25,它是MSRA圖像數(shù)據集的子集；Palm25圖像數(shù)據集,包含2 000幅手掌細節(jié)圖像。表1具體描述了這4個數(shù)據集。

表1 數(shù)據集描述

3.2 評價指標

實驗采用ACC和NMI指標對算法性能進行評估。定義yi為樣本數(shù)據點xi自帶的類別標簽,fi為算法對樣本數(shù)據點xi預測標簽,ACC計算公式如式(15)；定義矩陣P為算法聚類結果,矩陣Q為數(shù)據實際標簽矩陣,NMI計算公式如式(16)

(15)

(16)

式中n為樣本數(shù)目,δ(x,y)為比較函數(shù),若x=y,則δ(x,y)=1,否則δ(x,y)=0；H(P)和H(Q)分別為P和Q的熵,I(P,Q)為P和Q之間的互信息。

3.3 對比算法

為了驗證FAFS算法的性能,本文將其與LS[18]、MCFS[19]、UDFS[12]、SRCFS[20]4種無監(jiān)督特征選擇方法進行了比較,將使用所有特征Kmeans分類的結果作為基線(Baseline)。在實驗中,所有算法的近鄰數(shù)據點數(shù)目都設置為5。對于LS算法,需要調整高斯核函數(shù)的帶寬參數(shù)；對于MCFS,UDFS算法,需要調整正則化參數(shù)。為保證比較實驗的公平性,本次實驗采用網格搜索法,從{10-3,10-2,10-1,1,101,102,103}中取值對參數(shù)進行調整。實驗中FAFS算法錨點數(shù)量p根據實驗經驗選取數(shù)據集樣本數(shù)量約25 %的整數(shù)。為減小K-means初始化對實驗結果的影響,取10次實驗的平均值作為算法的最終結果。

3.4 實驗結果與分析

實驗中所有算法選擇不同特征數(shù)目的ACC和NMI值變化曲線分別繪制如圖2和圖3所示。

圖2 數(shù)據集選擇不同數(shù)量特征的聚類精度

圖3 數(shù)據集選擇不同數(shù)量特征的NMI

從圖2和圖3中4個數(shù)據集ACC和NMI變化曲線可以看出,本文提出的FAFS算法總體性能優(yōu)于所對比的算法,在COIL20,ORL和MSRA25數(shù)據集上的性能提升尤為顯著。在ORL數(shù)據集上,與其他比較算法和基線相比,分類準確率提高了10 %左右,表明該算法對ORL中這類數(shù)據的所選特征更具代表性。圖3中NMI結果也表明FAFS算法所選特征與數(shù)據的原始標簽之間的相關性總體上也優(yōu)于比較算法,這證明該算法提高了所選特征的質量。

另外,統(tǒng)計實驗中選取最大數(shù)量特征時各算法的運行時間如表2。最后,繪制COIL20和MSRA25兩個數(shù)據集的目標函數(shù)值變化曲線如圖4。

表2 各算法在數(shù)據集上運行時間

在算法運行時間方面,表2標出運行時間最短的前兩位。從表中可以看出,FAFS算法速度大體上僅次于LS方法,表明基于錨點策略的構圖方法對于算法運行效率提升顯著。LS方法雖然時間最短,但它只對數(shù)據特征的拉普拉斯特征分數(shù)進行簡單的排序,算法實際性能在所有對比算法中最差。從圖4中目標函數(shù)值的變化曲線可以看出,FAFS算法在前10次迭代內目標函數(shù)值上升非?？?隨后減緩并趨于平穩(wěn)并逐漸接近收斂,驗證了算法的收斂性。

圖4 數(shù)據集在算法1的變化曲線

4 結束語

本文針對稀疏正則化模型提出了FAFS算法。在原始數(shù)據點中嵌入錨點快速構建相似圖,通過對投影矩陣施加L2,0范數(shù)約束來選擇特征,將局部結構學習和特征選擇融為一體。算法不需要復雜的調參步驟就能有效選擇特征,在后續(xù)的公開數(shù)據集對比實驗中表明算法性能優(yōu)于其他幾種對比算法,尤其在算法運行速度上得到了顯著改善。