基于三元組排序局部性的SOCFS改進(jìn)算法

吳昌明,趙興濤,柳可鑫

(中國人民公安大學(xué) 信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院,北京 102623)

0 概述

在大數(shù)據(jù)時代背景下,數(shù)據(jù)維度急劇增長,大量的高維特征廣泛存在于模式識別、機器學(xué)習(xí)、生物信息等領(lǐng)域,如何在高維數(shù)據(jù)下準(zhǔn)確地獲取對學(xué)習(xí)任務(wù)有利的信息已成為當(dāng)前研究的熱點。在實際應(yīng)用中,多數(shù)特征是與當(dāng)前學(xué)習(xí)任務(wù)無關(guān)的冗余特征或者噪聲特征,這些冗余和噪聲特征會給學(xué)習(xí)任務(wù)帶來很多不利影響,比如過擬合、低效率。因此,降維成為處理高維數(shù)據(jù)的重要技術(shù)[1]。特征選擇[2-3]是當(dāng)前廣泛使用的降維方法[4-5],其在高維數(shù)據(jù)中選出與當(dāng)前學(xué)習(xí)任務(wù)相關(guān)的特征,去除與當(dāng)前學(xué)習(xí)任務(wù)無關(guān)的冗余和噪聲特征,從而降低數(shù)據(jù)空間維度,便于后續(xù)數(shù)據(jù)處理與任務(wù)分析。

在實際應(yīng)用中,通常需要解決缺少數(shù)據(jù)標(biāo)簽信息的非監(jiān)督[6-7]特征選擇問題[8-9]。由于數(shù)據(jù)樣本的標(biāo)簽信息未知,因此需要進(jìn)行聚類,挖掘無標(biāo)簽數(shù)據(jù)的潛在規(guī)律和性質(zhì)并劃分簇結(jié)構(gòu),從而找到對應(yīng)的類別?；诓煌奶卣鬟x擇判據(jù)以及不同的聯(lián)合框架,研究者們提出了大量面向聚類應(yīng)用的特征選擇算法,比如拉普拉斯的特征得分法(LS)[10]、非負(fù)譜分解的判決性特征選擇法(NDFS)[11]、同時正交基聚類特征選擇法(Simultaneous Orthogonal Basis Clustering Feature Selection,SOCFS)[12]等。然而,現(xiàn)有的非監(jiān)督特征選擇方法雖然在實際應(yīng)用中具有良好表現(xiàn),但是在聚類性能上還有較大的提升空間。因此,本文面向聚類應(yīng)用研究非監(jiān)督特征選擇問題,選取與當(dāng)前學(xué)習(xí)任務(wù)相關(guān)且具有局部結(jié)構(gòu)保持性與判別性的特征,并去除冗余和噪聲特征,以提升聚類性能。

1 相關(guān)工作

近年來,非監(jiān)督特征選擇成為人工智能的研究趨勢。早期面向聚類應(yīng)用的特征選擇算法基于某種特定的判據(jù),單獨評估每一個特征的重要性,從而選擇在此判據(jù)下的最優(yōu)特征。此類方法的代表有最大方差法[13]、LS法[14],其中LS法選擇對應(yīng)最大拉普拉斯得分的特征,而相應(yīng)的拉普拉斯得分可以用來反映局部流形結(jié)構(gòu)的保持能力。然而,單獨評估每一個特征重要性的方法不能用于處理多類簇結(jié)構(gòu)。也就是說,對于多類簇問題,很可能不同特征對不同類簇具有不同的判別能力,而單獨評估每一個特征的方法忽略了特征之間的組合對類簇的判別作用。因此,文獻(xiàn)[15]提出一種面向多類簇應(yīng)用的非監(jiān)督特征選擇算法(MCFS),其運用譜回歸的兩步法并聯(lián)合l1范數(shù)最小化進(jìn)行特征選擇。

受聯(lián)合求解的啟發(fā),現(xiàn)有的非監(jiān)督特征選擇算法大多采用一個特定的聯(lián)合框架來選擇最合適的特征子集。NDFS是在一個聯(lián)合框架中,同時進(jìn)行非負(fù)譜分析和l2,1范數(shù)正則化回歸,從而實現(xiàn)在整個特征集合中批量選擇最具判別性的特征子集。無監(jiān)督的規(guī)范化判別特征選擇算法(UDFS)[16]綜合了分析和最小化范數(shù)以確定特征。然而,UDFS和NDFS算法忽略了噪聲和異常值的影響,魯棒性較差。因此,文獻(xiàn)[17]提出一種魯棒非監(jiān)督特征選擇算法(RUFS),其通過局部學(xué)習(xí)正則化非負(fù)矩陣分解來學(xué)習(xí)偽標(biāo)簽,同時聯(lián)合l2,1范數(shù)正則化回歸進(jìn)行特征選擇,從而有效處理異常值和噪聲。SOCFS[12]利用雙正交半非負(fù)矩陣分解進(jìn)行正交基聚類,捕捉潛在的類簇中心,從而進(jìn)一步指導(dǎo)特征選擇過程。

上述特征選擇方法已經(jīng)在實際應(yīng)用中取得了較好的應(yīng)用效果,但在聚類性能方面依然有較大的提升空間。由于已有特征選擇方法忽略了排序局部性對特征選擇過程的影響,即特征選擇后并不能保持?jǐn)?shù)據(jù)點原始的近鄰排列順序,而排序局部性卻對基于距離的聚類任務(wù)影響較大,因此本文利用數(shù)據(jù)的三元組局部結(jié)構(gòu),構(gòu)建數(shù)據(jù)之間的排序關(guān)系并對該關(guān)系在特征選擇過程中進(jìn)行局部保持,提出基于三元組排序局部性的SOCFS改進(jìn)算法,從而選擇排序局部性保持較好的特征,應(yīng)用于后續(xù)的非監(jiān)督學(xué)習(xí)任務(wù)。

2 SOCFS改進(jìn)算法

2.1 SOCFS算法

SOCFS是一種非監(jiān)督特征選擇算法。為對無標(biāo)簽數(shù)據(jù)進(jìn)行有效的特征選擇,該算法設(shè)計了一個含有新型目標(biāo)矩陣的正則化回歸公式。目標(biāo)矩陣通過正交基聚類來捕獲映射后的數(shù)據(jù)點潛在的類簇中心,繼而指導(dǎo)映射矩陣選擇判別性的特征。SOCFS未使用數(shù)據(jù)點的局部結(jié)構(gòu)信息作為目標(biāo)函數(shù)的附加項,而是在提出的目標(biāo)函數(shù)中通過使用具有統(tǒng)一項的目標(biāo)矩陣指導(dǎo)正交基聚類,直接計算潛在的類簇信息,并且可采用一個簡單的優(yōu)化算法實現(xiàn)目標(biāo)函數(shù)最小化。在多個數(shù)據(jù)集上的實驗結(jié)果表明:與現(xiàn)有特征選擇算法相比,SOCFS獲得了更加有效的聚類結(jié)果。

(1)

λ>0

(2)

約束的意義為:1)B的正交約束使B的每一列都是獨立的;2)E的正交和非負(fù)約束使E的每一行都只有一個非零元素。由此可以看出,B作為基矩陣,有正交性,E作為編碼矩陣,ET中每一列的非零元素選擇B中的一列。該約束確保了SOCFS算法基于距離的正交基聚類。

T=BET使用正交基B和編碼矩陣E對映射后的數(shù)據(jù)點WTX進(jìn)行聚類,所以T能估計WTX的潛在類簇中心。然后,X經(jīng)過W的映射后,可以成功逼近由T估計出的潛在類簇中心。由于B的正交約束使得WTX映射后的類簇更加分散(類簇中心相互獨立),因此使得W能選擇更有判別性的特征。對于E,已有方法通過近似正交約束的方式解決問題式(2)。然而,因為該方法是基于非負(fù)矩陣分解,在多數(shù)情況下其處理的是非負(fù)約束而不是正交約束,且也不能完全保證E是一個正交矩陣,所以E不能作為編碼矩陣。因此,SOCFS算法的目標(biāo)函數(shù)為:

s.t.BTB=I,ETE=I,F=E,F≥0

(3)

其中,F是一個輔助變量,并帶有一個附加約束F=E,這一步轉(zhuǎn)換的目的是從E中分離出非負(fù)約束并將該約束施加到新變量F上。當(dāng)E保持正交性時,F可以通過約束F=E保證E的非負(fù)性。改寫問題式(3),得到最終SOCFS算法的目標(biāo)函數(shù)為:

s.t.BTB=I,ETE=I,F≥0

(4)

其中γ>0是一個控制F和E相等程度的參數(shù)。

2.2 排序局部性

如圖1所示,假設(shè)在原始空間(見圖1(a))中,數(shù)據(jù)點x0有4個近鄰x1、x2、x3、x4,其中相同顏色表示同一類別,即(x0,x1,x2)屬于類別1,x3屬于類別2,x4屬于類別3,線段長短表示距離遠(yuǎn)近,距離排序為1→2→3→4。當(dāng)采用W矩陣映射進(jìn)行特征選擇時,可以看到圖1(b)中未經(jīng)過排序局部性保持的特征在投影之后,排序局部性發(fā)生了變化,距離排序變?yōu)?→4→1→2,這說明原始空間中數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)發(fā)生了變化,在基于距離的聚類中,后續(xù)過程將會把中間部分的y0、y4、y2聚為一類,從而導(dǎo)致聚類結(jié)果的不準(zhǔn)確。本文將經(jīng)過特征選擇矩陣投影到新的空間后,使數(shù)據(jù)的排序得到保持,也就是保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu),從而得到正確的聚類結(jié)果,即y0、y1、y2聚為一類,y4為一類,y3為一類,如圖1(c)所示。綜上所述,在基于聚類的任務(wù)中,近鄰之間的相對遠(yuǎn)近關(guān)系也稱為排序局部性[18-19],對于特征選擇過程極其重要。

圖1 排序局部性原理

2.3 三元組排序局部性

對數(shù)據(jù)點xi,經(jīng)過特征選擇矩陣W的映射后得到所選擇的新特征組,記作yi=WTxi,因此有Y=WTX。

基于三元組引導(dǎo)的排序局部性表示若存在一個數(shù)據(jù)點xi及其近鄰組成一個三元組向量(xi,xp,xq),經(jīng)過特征選擇矩陣W的映射后,得到一個新特征組構(gòu)成的三元組(yi,yp,yq)。如果當(dāng)dist(xi,xp)≤dist(xi,xq)成立時,則有dist(yi,yp)≤dist(yi,yq)。因此,筆者認(rèn)為排序局部性,也就是近鄰的遠(yuǎn)近關(guān)系在基于聚類的任務(wù)中得到了保持。

(5)

(6)

基于以上數(shù)學(xué)推導(dǎo),最終得到保持排序局部性的損失函數(shù)為:

(7)

綜上,本文得到基于三元組引導(dǎo)排序局部性的損失函數(shù)。

2.4 TOL-SOCFS算法

在原有SOCFS算法的基礎(chǔ)上,本文加入三元組引導(dǎo)保持排序局部性的附加項Tr(WTXLXTW),得到最終改進(jìn)算法的目標(biāo)函數(shù)為:

s.t.BTB=I,ETE=I,F≥0

(8)

其中,α是一個標(biāo)量常數(shù),控制保持排序局部性的損失函數(shù)項的相對重要性。

采用交替迭代的方式對式(8)進(jìn)行優(yōu)化,并得到基于三元組引導(dǎo)排序局部性的SOCFS改進(jìn)算法(TOL-SOCFS)。

1)W更新:固定B、E、F求使目標(biāo)函數(shù)值最小的W,與W相關(guān)的子問題如下:

(9)

令J(W,B,E,F)對W的導(dǎo)數(shù)等于0,有:

α(XLXT+XLTXT)W=0?

W=(XXT+λD+0.5αX(L+LT)XT)-1XEBT?

W=(XXT+λD+αXLXT)-1XEBT

(10)

2)B更新:固定W、F求使目標(biāo)函數(shù)值最小的B,與B相關(guān)的子問題如下:

(11)

(12)

解析解為:

(13)

(14)

其中,UB和VB分別為矩陣ETXTW奇異值分解后的左右特征向量。

3)E、F更新:固定B和W求使目標(biāo)函數(shù)值最小的E和F,E和F通過固定一個并更新另一個的方式交替迭代。與E相關(guān)的子問題如下:

s.t.ETE=I

(15)

子問題可重寫為:

XTWWTX)+γTr(ETE-2ETF+FTF)=

(16)

(17)

其中,UE和VE分別為矩陣BTWTX+γFT奇異值分解所得的左右特征向量。

與F相關(guān)的子問題可以寫為:

(18)

子問題式(18)的解可以改寫為:

(19)

算法1為E和F的更新算法,整體優(yōu)化算法見算法2。由更新規(guī)則式(10)、式(14)、式(17)和式(19)可知,目標(biāo)函數(shù)單調(diào)下降。

算法1E和F更新算法

輸入矩陣Ft、Wt、Bt,參數(shù)γ

輸出Et+1=E′s、Ft+1=F′s

初始化s=0、F′s=Ft

1.Repeat Step 2～Step 4;

4.s=s+1;

算法2TOL-SOCFS算法

初始化t=0、Dt=I、Bt和Et

1.Construct k-neighbor graph,obtaining Laplacian matrix L;

2.Repeat Step 3～Step 7;

3.Update Et+1and Ft+1by algorithm 1;

7.‖ΔJ(Wt,Bt,Et,Ft)‖≤ε;

2.5 TOL-SOCFS算法復(fù)雜度分析

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

實驗在6個公開數(shù)據(jù)集上進(jìn)行K均值聚類[19-21]:目標(biāo)圖像數(shù)據(jù)集(COIL20),字母讀音識別數(shù)據(jù)集(Isolet1),手寫數(shù)字?jǐn)?shù)據(jù)集(USPS),人臉圖像數(shù)據(jù)集(YaleB、UMIST、ORL)。在每個數(shù)據(jù)集上,本文提出的TOL-SOCFS算法都與下列5種非監(jiān)督特征選擇算法以及原SOCFS算法進(jìn)行比較,并且未經(jīng)過特征選擇處理的所有特征被作為對比評估標(biāo)準(zhǔn)[22-23]。

1)無監(jiān)督的規(guī)范化判別特征選擇算法(UDFS):基于局部判決得分進(jìn)行特征選擇,其中局部判決得分基于l2,1正則化矩陣反映局部結(jié)構(gòu)信息。

2)面向多類簇應(yīng)用的非監(jiān)督特征選擇算法(MCFS):基于l1正則化矩陣的譜回歸兩步法選擇特征。

3)非負(fù)譜分解的判決性特征選擇算法(NDFS):基于非負(fù)的譜分析和l2,1正則化回歸的聯(lián)合框架選擇特征。

4)魯棒非監(jiān)督特征選擇算法(RUFS):基于l2,1范數(shù)且?guī)в芯植繉W(xué)習(xí)的非負(fù)矩陣分解和l2,1正則化回歸的聯(lián)合框架選擇特征。

5)拉普拉斯的特征得分法(LS):先根據(jù)算法計算拉普拉斯得分,再選擇得分最高的特征,其中計算得到的拉普拉斯得分可以反映特征的局部保持能力。

本文使用聚類精確度(ACC)和歸一化互信息(NMI)評估不同算法選擇的特征集的聚類結(jié)果[24]。對于LS、MCFS、UDFS,NDFS和RUFS,設(shè)置近鄰參數(shù)k的值為5。因為SOCFS和TOL-SOCFS將數(shù)據(jù)點的局部結(jié)構(gòu)信息嵌入到三元組的損失函數(shù)構(gòu)建中,所以不需要額外設(shè)置任何的近鄰參數(shù),其中將映射空間的維數(shù)m設(shè)為潛在類簇的數(shù)量c。

針對TOL-SOCFS算法,本文同樣采用網(wǎng)格搜索策略在{10-6,10-4,…,104,106}范圍內(nèi)調(diào)整所有參數(shù),不同的是相比其他非監(jiān)督特征選擇算法,TOL-SOCFS算法需要調(diào)整更多的參數(shù)。對于前5個數(shù)據(jù)集,設(shè)置選擇的特征數(shù)目為{50,100,…,300}。對于USPS數(shù)據(jù)集,考慮其特征維數(shù)的限制,設(shè)置選擇的特征數(shù)目為{50,80,…,200}。本文對所有實驗都重復(fù)了20次,每次實驗均隨機初始化并列出ACC和NMI的平均值和標(biāo)準(zhǔn)差,同時隨機初始化NDFS、RUFS、SOCFS等算法的變量。

3.2 結(jié)果分析

TOL-SOCFS算法與其他非監(jiān)督特征選擇算法的ACC和NMI的平均值和標(biāo)準(zhǔn)差對比結(jié)果見表1和表2,其中最優(yōu)結(jié)果加粗表示,括號內(nèi)的值為當(dāng)前結(jié)果下對應(yīng)最合適選取特征的數(shù)目。由表1和表2可以看出,TOL-SOCFS算法在6個數(shù)據(jù)庫上都產(chǎn)生了比其他非監(jiān)督特征選擇算法更好的實驗結(jié)果,并且在所選特征數(shù)目較少時,TOL-SOCFS算法也有較好的聚類性能。

表1 TOL-SOCFS算法與其他非監(jiān)督特征選擇算法的ACC對比結(jié)果

表2 TOL-SOCFS算法與其他非監(jiān)督特征選擇算法的NMI對比結(jié)果

如表1所示，在COIL20數(shù)據(jù)集上，本文提出的TOL-SOCFS算法具有接近3%的聚類性能提升，表明了TOL-SOCFS算法的ACC聚類精確度較高?？梢钥闯?，在COIL20數(shù)據(jù)集上，TOL-SOCFS算法可以選擇更少的特征(即200維)，但得到比SOCFS算法300維特征更好的結(jié)果，驗證了TOL-SOCFS算法特征選擇的有效性。此外，在USPS數(shù)據(jù)集上，TOL-SOCFS算法在110維特征數(shù)的情況下，可以得到比200維特征的SOCFS算法更好的聚類結(jié)果，驗證了TOL-SOCFS算法的有效性。同樣地，在互信息NMI的度量指標(biāo)上，如表2所示，TOL-SOCFS算法取得了所有算法中最好的互信息結(jié)果，并且在COIL20數(shù)據(jù)集上，僅通過200維特征即可獲得比其他算法300維特征更好的聚類性能，進(jìn)一步驗證了TOL-SOCFS算法的有效性。以上結(jié)果主要得益于三元組引導(dǎo)的排序局部性對原始數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)的保持，即原始數(shù)據(jù)中近鄰的相對遠(yuǎn)近關(guān)系與數(shù)據(jù)原始幾何結(jié)構(gòu)得到保持，有利于選擇具有局部結(jié)構(gòu)保持性及判別區(qū)分度高的特征。因此，實驗證實TOL-SOCFS算法的聚類性能優(yōu)于現(xiàn)有非監(jiān)督特征選擇算法。

3.3 算法收斂性分析

TOL-SOCFS算法的收斂性曲線見圖2。在6個數(shù)據(jù)集上的實驗結(jié)果表明,TOL-SOCFS算法可以在60次迭代內(nèi)實現(xiàn)收斂,表明其具備快速收斂能力。

圖2 TOL-SOCFS算法的收斂性曲線

4 結(jié)束語

本文提出一種基于三元組排序局部性的SOCFS改進(jìn)算法(TOL-SOCFS),利用數(shù)據(jù)的三元組局部結(jié)構(gòu),構(gòu)建數(shù)據(jù)之間的排序關(guān)系并對該關(guān)系在特征選擇過程中進(jìn)行局部性保持,從而選擇排序局部性保持較好的特征,用于后續(xù)的非監(jiān)督聚類任務(wù)。在6個公開數(shù)據(jù)集上的聚類實驗結(jié)果表明,TOL-SOCFS算法具有比其他非監(jiān)督特征選擇算法更好的聚類性能,驗證了其有效性。鑒于TOL-SOCFS算法利用三元組排序局部性在樣本維度上保持映射前后的一致性能力,下一步將更多關(guān)注三元組排序局部性在特征維度上的映射保持關(guān)系,通過保持映射前后特征的相似性,進(jìn)一步提升非監(jiān)督特征選擇算法的整體性能。