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

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

0 引 言

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

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

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

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

1 基于錨點(diǎn)策略的FAFS算法

1.1 FAFS目標(biāo)函數(shù)

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

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

(1)

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

=WTXDXTW-WTXSXTW

=WTX(D-S)XTW=WTXLXTW

(2)

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

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

(3)

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

1.2 基于錨點(diǎn)策略的相似圖學(xué)習(xí)

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

圖1 數(shù)據(jù)點(diǎn)與錨點(diǎn)連接示意

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

(5)用拉格朗日乘子法對(duì)式(5)進(jìn)行求導(dǎo)得到拉格朗日函數(shù)為

(6)

式(6)優(yōu)化求解的詳細(xì)過(guò)程可以參見(jiàn)文獻(xiàn)[15],最后求解結(jié)果為

(7)

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

(8)

式中Λ為對(duì)角矩陣,其對(duì)角元素為E矩陣的列和。此外,相似度矩陣S為一個(gè)稀疏對(duì)稱(chēng)、PSD且雙隨機(jī)矩陣,這些性質(zhì)對(duì)于圖的學(xué)習(xí)和提高算法的性能非常有用。

2 目標(biāo)函數(shù)求解

2.1 模型優(yōu)化

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

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

(9)

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

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

(10)

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

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

(11)

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

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

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

Step1：隨機(jī)初始化一個(gè)投影矩陣W滿(mǎn)足WTW=I;

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

Step3：根據(jù)P的對(duì)角線(xiàn)元素選取最大的k個(gè),其對(duì)應(yīng)位置的k行序號(hào)為W非零行的位置,W其余行元素置0;

Step4：計(jì)算M=HW,取對(duì)應(yīng)位置的k行元素組成∈k×m,用的任意一個(gè)標(biāo)準(zhǔn)正交基,來(lái)更新W對(duì)應(yīng)位置的行,W其余的行為0;

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

輸出:投影矩陣W。

2.2 收斂性證明

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

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

定理1：對(duì)于算法中的Wt+1,有

(12)

證明

(13)

其中，第一個(gè)不等式來(lái)自Wt+1的定義；第二個(gè)不等式根據(jù)引理2；最后一個(gè)等式根據(jù)引理1,這是因?yàn)橛?/p>

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

(14)

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

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

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

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

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

表1 數(shù)據(jù)集描述

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用ACC和NMI指標(biāo)對(duì)算法性能進(jìn)行評(píng)估。定義yi為樣本數(shù)據(jù)點(diǎn)xi自帶的類(lèi)別標(biāo)簽,fi為算法對(duì)樣本數(shù)據(jù)點(diǎn)xi預(yù)測(cè)標(biāo)簽,ACC計(jì)算公式如式(15)；定義矩陣P為算法聚類(lèi)結(jié)果,矩陣Q為數(shù)據(jù)實(shí)際標(biāo)簽矩陣,NMI計(jì)算公式如式(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 對(duì)比算法

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

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

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

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

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

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

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

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

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

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

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

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