基于矩陣分解和自適應(yīng)圖的無監(jiān)督特征選擇

曹浪財, 林曉昌, 蘇思行

(1.廈門大學(xué)航空航天學(xué)院, 福建 廈門 361005;2.廈門大數(shù)據(jù)智能分析與決策重點實驗室, 福建 廈門 361005)

0 引 言

特征選擇可以通過某種標(biāo)準(zhǔn)從原始的特征集中選擇出最優(yōu)的特征子集解決維數(shù)災(zāi)難[1]。根據(jù)特征選擇過程中涉及的不同子步驟,這些嵌入式方法可以進一步分為以下4種類型。

第1種嵌入式方法首先檢測數(shù)據(jù)的結(jié)構(gòu),然后直接選擇能用于最好地保留封閉結(jié)構(gòu)的那些特征。典型的方法有跡比準(zhǔn)則[2]和無監(jiān)督判別性特征選擇(unsupervised discriminant feature selection,UDFS)算法[3]。

第2種嵌入式特征選擇方法首先通過構(gòu)造各式各樣的拉普拉斯圖捕獲樣本的相似性信息,通過譜分析檢測數(shù)據(jù)的簇結(jié)構(gòu)。然后,通過稀疏譜回歸[4]得到稀疏的特征選擇矩陣。最后,選擇特征選擇矩陣中得分最高的p個特征,也就是和簇結(jié)構(gòu)最契合的p個特征。這些通過圖嵌入或者通過其他聚類方式挖掘數(shù)據(jù)的簇結(jié)構(gòu)都可以看作對真實數(shù)據(jù)標(biāo)簽的近似過程。典型的方法包括多簇特征選擇[5],最小冗余譜特征選擇[6],全局和局部結(jié)構(gòu)保留特征選擇[7]。

第3種嵌入方法的簇結(jié)構(gòu)是由拉普拉斯圖以及自適應(yīng)判別正則共同決定的,是動態(tài)改變的。通過特征選擇結(jié)果的反饋,這類方法可以得到更好的聚類分析。典型算法包括聯(lián)合嵌入學(xué)習(xí)和譜回歸[8],魯棒無監(jiān)督特征選擇方法[9],非負(fù)判別特征選擇[10],魯棒的譜學(xué)習(xí)特征選擇[11]。

第4種嵌入式方法為了提高結(jié)構(gòu)學(xué)習(xí)的質(zhì)量,將特征選擇的結(jié)果輸入到結(jié)構(gòu)學(xué)習(xí)中,并使用矯正后的數(shù)據(jù)結(jié)構(gòu)引導(dǎo)選擇特征過程。典型算法包括基于局部學(xué)習(xí)聚類的特征選擇方法[12],自適應(yīng)結(jié)構(gòu)學(xué)習(xí)的無監(jiān)督特征選擇(unsupervised feature selection with adaptive structure learning,FSASL)[13],結(jié)構(gòu)最優(yōu)圖特征選擇(structured optimal graph feature selection, SOGFS)[14]。

綜合以上特征選擇方法可知,一個好的特征選擇方法需要提取到可靠的數(shù)據(jù)幾何結(jié)構(gòu)以及可靠的簇結(jié)構(gòu)來引導(dǎo)特征選擇過程,但是現(xiàn)有的算法或側(cè)重于理想數(shù)據(jù)幾何結(jié)構(gòu)的提取(FSASL,SOGFS),或側(cè)重于通過魯棒聚類進而引導(dǎo)更好的特征選擇，比如基于矩陣分解的魯棒無監(jiān)督特征選擇[15],很少同時兼顧這兩方面。

基于以上分析,本文擬建立一個特征選取方法統(tǒng)一的框架,將自適應(yīng)的局部結(jié)構(gòu)學(xué)習(xí)、判別性信息的提取以及特征選擇融合到該框架。在此基礎(chǔ)上提出了一種基于魯棒矩陣分解和自適應(yīng)圖的無監(jiān)督特征選擇(unsupervised feature selection based on robust matrix factorization and adaptive graph, MFAGFS)方法。該方法通過魯棒矩陣分解獲取判別性信息,并通過自適應(yīng)圖嵌入[16],學(xué)習(xí)數(shù)據(jù)集中的局部結(jié)構(gòu)信息,并對學(xué)習(xí)到的相似性矩陣添加先驗約束,而無需預(yù)先構(gòu)建樣本間的相似性矩陣, 降低了噪聲和冗余特征的影響,從而提高了模型的魯棒性,使得學(xué)習(xí)到的局部結(jié)構(gòu)信息更加精確。最后通過對特征選擇矩陣施加行稀疏的范數(shù)實現(xiàn)特征選擇功能。

1 MFAGFS建模

傳統(tǒng)的無監(jiān)督特征選擇模型在學(xué)習(xí)數(shù)據(jù)的局部結(jié)構(gòu)的時候,通常在樣本的原始特征空間中通過建立鄰邊和計算權(quán)重得到樣本間的相似矩陣。然而原始樣本空間中往往存在著許多的冗余甚至噪聲,這種信息提取過程是不可靠的。因此，本文選擇從純凈的投影空間中構(gòu)造更加可靠的相似性矩陣,并對相似矩陣添加先驗約束使得其具有c個連接分量(c為簇的個數(shù))得到理想的局部結(jié)構(gòu)信息。在此基礎(chǔ)上通過矩陣分解進一步添加判別性信息防止過擬合。

為方便本節(jié)首先以矩陣A∈Rm×n介紹本文中所涉及到的各種范數(shù)和矩陣分解。

1.1 魯棒矩陣分解

X∈Rm×n，其中m是特征的維數(shù),n是樣本的數(shù)目。每一個樣本點可以表示為xi∈Rm×1。將矩陣X進行分解:

式中：V∈Rm×c是潛在的特征矩陣(聚類中心)；U∈Rn×c是類指示矩陣(c為聚類個數(shù))[17-18]。存在著正交和非負(fù)約束的矩陣U可以看作是一個放縮的聚類索引矩陣。正交約束和非負(fù)約束的同時存在提高矩陣的質(zhì)量,并且非負(fù)約束更符合實際情況。由于用F范數(shù)作為損失函數(shù)容易受到噪聲點和異常點的影響。本文用l2,1范數(shù)來代替常見的F范數(shù)來避免大的損失從而使得所提的模型更加魯棒。表示如下:

(1)

通過優(yōu)化式(1)可得到聚類索引矩陣,然后用聚類索引指示矩陣去指導(dǎo)特征選擇。但是這還遠(yuǎn)遠(yuǎn)不夠的,需要增添更多的信息去提升所選擇特征子集的質(zhì)量。由于在無監(jiān)督特征選擇任務(wù)中數(shù)據(jù)的局部幾何結(jié)構(gòu)是十分重要的[19-20]。本文后續(xù)通過自適應(yīng)圖學(xué)習(xí),進行基于數(shù)據(jù)內(nèi)部幾何結(jié)構(gòu)的樣本相似度提取,使得聚類索引矩陣更加接近數(shù)據(jù)的真實類別,獲得理想的聚類效果,最終提升特征選擇的性能。

1.2 自適應(yīng)圖構(gòu)建

1.2.1 基于局部結(jié)構(gòu)的自適應(yīng)圖

(2)

式中：1n是長度為1的全1列向量；α是正則化參數(shù),正則化參數(shù)是為了避免無效解?？紤]兩個極端的例子:①α=0,對于向量si∈Rn×1有且只有一個元素的值為1,其他的都為0;②α=∞,這會讓向量si中的每一個元素都為1/n;顯而易見,正則項α可以用來調(diào)節(jié)鄰居節(jié)點的個數(shù)。最佳的α值應(yīng)該使大部分向量si只包含k個非零元素,其中k是與xi連接的鄰居數(shù)。最優(yōu)α值自動求解將在第2.3節(jié)詳細(xì)給出。在得到相似性矩陣后可以對其進一步添加先驗約束提高其可靠性。下一節(jié)將提出一種基于理想局部結(jié)構(gòu)的自適應(yīng)圖優(yōu)化,來進一步提升自適應(yīng)圖的正確性。

1.2.2 基于理想局部結(jié)構(gòu)自適應(yīng)圖

對于相似性矩陣來說最理想的狀態(tài)是只包含c個連通分量,即c個簇。然而通過局部結(jié)構(gòu)學(xué)習(xí)到的相似性矩陣幾乎不可能處于這種狀態(tài)。注意到:

(3)

(4)

因此可以將優(yōu)化問題式(4)改寫為

(5)

1.3 MFAGFS算法流程

根據(jù)流形學(xué)習(xí)理論[25],始終存在可以表達高維數(shù)據(jù)結(jié)構(gòu)的低維流形。WTX表示為此線性組合,其中W∈Rm×d是投影矩陣,m和d分別是原始特征維度和投影特征尺寸。將投影后的數(shù)據(jù)用在相似性矩陣的學(xué)習(xí)中,可以有效降低無關(guān)特征和冗余特征的負(fù)面影響。整理式(1)和式(5)可以得到MFAGFS模型的公式:

2γtr(UTLU)+η‖W‖2,1

(6)

圖1 模型算法流程圖

圖1中,投影矩陣W用來特征選擇,相似性矩陣S用來獲取局部結(jié)構(gòu)。將自適應(yīng)的局部結(jié)構(gòu)學(xué)習(xí)、判別性信息的提取以及特征選擇融合到一體。

2 MFAGFS算法優(yōu)化

2.1 模型優(yōu)化求解

式(6)需要對S,U,V,W4個未知變量進行求解。為了降低模型求解的復(fù)雜度引入輔助變量E=X-VUT和Z=U。Z的作用是通過約束Z=U將獲得的非負(fù)性傳遞給U,并在此過程中保持U的正交性不變。引入輔助變量后,同時使用增廣拉格朗日法進行處理,式(6)可以改寫為

‖E‖2,1+2γtr(ZTLU)+η‖W‖2,1+

<λ1,X-VUT-E>+<λ2,Z-U>+

(7)

式中：λ1,λ2是拉格朗日乘子;μ是懲罰參數(shù),用來控制兩個等式約束的懲罰。由于上面的目標(biāo)函數(shù)包含多個變量,因此采用交替方向乘子法(alternating direction method of multipliers, ADMM)[26]來求解,通過交替迭代的方式將原問題簡化為幾個方便求解的子問題,即當(dāng)更新某一變量的時候,其他變量固定,并由此依次對每個變量進行更新,具體流程如下所示。

算法1 基于魯棒矩陣分解和自適應(yīng)圖的無監(jiān)督特征選擇的優(yōu)化算法輸入:數(shù)據(jù)集X∈Rm×n,特征選擇個數(shù)h,聚類個數(shù)c,投影維度d。正則化參數(shù)η,β,足夠大的γ,以及參數(shù)α。初始化:k均值聚類初始化U,V=XU,E=X-VUT,W=Id×m。迭代:1更新相似性陣S;2計算拉普拉斯矩陣L=D-ST+S2;3通過算法2更新特征選擇矩陣W;4更新聚類索引矩陣U;5更新聚類中心V;6更新輔助變量E;7更新輔助變量Z;8更新拉格朗日乘子λ1,λ2,μ,直至收斂。輸出:計算所有的‖wi‖2(i=1,2,…,n)并按降序排序,選擇排名靠前p的特征作為最后結(jié)果。

算法1中相似性矩陣S、特征選擇矩陣W、聚類索引矩陣U、聚類中心V、輔助變量E、輔助變量Z、拉格朗日乘子λ1,λ2,μ等子問題求解公式優(yōu)化如下:

(1)相似性矩陣S

移除式(7)中與相似性矩陣S無關(guān)的項,得

2γtr(ZTLU)

(8)

(9)

(2)特征選擇矩陣W

W通過求解以下問題更新:

s.t.WTW=I

(10)

(11)

顯然當(dāng)ε等于0時與原問題等價。式(11)寫成拉格朗日乘子法形式:

tr(ΛWTW-1)

(12)

式中:Λ為拉格朗日乘子。

對W求導(dǎo)并令其等于0可以得到:

(13)

式中：Q∈Rd×d是一個對角矩陣,其中第i個元素定義如下:

(14)

矩陣Q是未知的,并且依賴于投影矩陣W。因此,本文采用一個迭代算法來求解式(11)。當(dāng)固定W的時候,Q可以通過式(14)獲得。而當(dāng)固定Q的時候,特征選擇矩陣W可以通過求解下式得到:

(15)

特征選擇矩陣W的求解詳細(xì)描述如算法2所示。

算法2 更新特征選擇矩陣W輸入:數(shù)據(jù)矩陣X∈Rn×d,拉普拉斯矩陣L∈Rn×n,參數(shù)η,參數(shù)β,投影維度d。初始化:Q∈Rn×n,Q=I。迭代:1根據(jù)現(xiàn)有的Q值,通過XTLX+βQ/η最小的d個特征值所對應(yīng)的特征向量,更新特征選擇矩陣W;2根據(jù)現(xiàn)有的W值,更新Q,直至收斂。輸出:特征選擇矩陣W∈Rm×d。

(3)聚類索引矩U

U通過求解以下問題更新:

經(jīng)過進一步的整理可以得到:

(16)

式中：

(17)

式(16)可以進一步化簡為

(18)

最后得到聚類標(biāo)簽U的迭代更新公式:

(19)

式中：NU,QU分別對應(yīng)于矩陣H奇異值分解的左奇異矩陣和右奇異矩陣。

(4)聚類中心V

聚類中心V子問題如下所示:

(20)

考慮到U是正交的,也就是UTU=I,進一步整理可得

最后得到聚類中心V的更新式:

(21)

(5)輔助變量E

子問題E如下所示:

(22)

(23)

(6)輔助變量Z

移除式(7)與輔助變量Z無關(guān)的項,得

(24)

(25)

(7)拉格朗日乘子以及w

參考文獻[27]更新方式如下:

λ1=λ1+μ(X-VUT-E)

(26)

λ2=λ2+μ(Z-U)

(27)

μ=min(μmax,pμ)

(28)

式中：μmax是常數(shù);p是迭代步長。

2.2 算法2的收斂性分析

特征選擇矩陣迭代過程中的收斂性直接影響到算法的可行性,本節(jié)給與證明。首先給出以下引理。

引理 1對于任意的正實數(shù)u,v,下面的不等式[28]恒成立:

定理 1算法1中的目標(biāo)函數(shù)將單調(diào)遞減直到收斂。

(29)

基于引理1,可知:

(30)

通過整理式(29)和式(30),可得到:

(31)

證畢

2.3 正則化參數(shù)α值的求解

式(9)滿足KKT(Karush-Kuhn-Tuckre)[29]條件的最優(yōu)解為

(32)

式中:(·)+表示相似向量si是稀疏并且非負(fù),意味著向量si中有且只有k個數(shù)據(jù)大于0,其他都是等于0。如果將sij從大到小排列,則si,k>0,si,k+1≤0,也就是:

(33)

(34)

(35)

整理式(33)～式(35),得到:

(36)

(37)

最后對所有的αi加和平均得到:

(38)

3 實驗與分析

本節(jié)將通過對比實驗驗證提出的無監(jiān)督特征選擇算法的有效性。

3.1 實驗準(zhǔn)備

3.1.1 數(shù)據(jù)集介紹

在MFAGFS模型對比實驗中,使用了6個常見的公開數(shù)據(jù)集。這6個公開數(shù)據(jù)集的樣本數(shù),特征維度、類別數(shù)以及實驗中選擇的特征個數(shù)在表1中詳細(xì)給出。這6個數(shù)據(jù)集的類別數(shù)最少的有8類,最多的高達100類。樣本數(shù)目也具有多樣性,最少的有165個,最多的有2 000個。

表1 數(shù)據(jù)集的簡要信息和特征選擇維度

3.1.2 實驗設(shè)置

為了對MFAGFS模型的性能有個客觀的認(rèn)識。實驗中將采用所有特征作為基準(zhǔn),并與其他5個相關(guān)的無監(jiān)督特征選擇算法進行比較。實驗中涉及到的對照模型為Baseline、LapScore[30]、UDFS、NDFS、FSASL、SOGFS。

為了保證對比實驗的公平性和有效性,實驗中需要提前設(shè)置近鄰參數(shù)時,統(tǒng)一設(shè)置為k=5,高斯熱核函數(shù)中的參數(shù)σ大小設(shè)為1。此外,對于特征選擇矩陣(投影矩陣)的維數(shù)空間和潛在簇的個數(shù)都設(shè)為c(c是數(shù)據(jù)集的真實類別數(shù))。MFAGFS模型還需要調(diào)節(jié)η,β和γ這3個參數(shù)。其中γ用來實現(xiàn)對秩的約束,在具體實驗操作中根據(jù)秩的大小自動調(diào)節(jié)γ的值。對于剩下的參數(shù)η和參數(shù)β采用網(wǎng)格搜索的方式來確定。搜索的范圍為{10-3,10-2,10-1,100,101,102,103}。為了公平起見,其他對比模型的正則參數(shù)統(tǒng)一進行范圍大小為{10-3,10-2,10-1,100,101,102,103}的網(wǎng)格搜索。

由于k均值聚類的效果與初始化緊密相關(guān),所以在實驗中重復(fù)實驗20次并記錄其平均值。

3.1.3 實驗評價指標(biāo)

為了準(zhǔn)確地觀察算法的效果,需要采用相應(yīng)的評價指標(biāo)得到客觀的量化結(jié)果。本文采用準(zhǔn)確率(accuracy, ACC)以及歸一化互信息(normalized mutual information,NMI)這兩個評價準(zhǔn)則來評估特征子集的聚類性能[7]。

3.2 實驗結(jié)果分析

3.2.1 特征有效性分析

本節(jié)通過對比實驗來驗證MFAGFS模型所選擇的特征的有效性?？偣膊捎昧?個數(shù)據(jù)集進行聚類分析。實驗結(jié)果中的測試指標(biāo)用粗體表示最好的結(jié)果,下劃線表示次好的結(jié)果。AVERAGE表示各個特征選擇方法在6個數(shù)據(jù)集上的平均表現(xiàn)。

表2和表3描述的是各個模型在各個數(shù)據(jù)集上的最優(yōu)表現(xiàn)情況。

從表2以及表3中可以得到如下結(jié)論。

表2 各算法最優(yōu)識別率比較

表3 各算法最優(yōu)標(biāo)準(zhǔn)互信息比較

(1)大部分的無監(jiān)督特征選擇算法都比基線有著更加優(yōu)異的表現(xiàn)。說明原始數(shù)據(jù)中有著大量冗余以及噪聲特征。通過特征選擇可以提高學(xué)習(xí)器的性能。說明了進行特征選擇的重要性。

(2)LapScore的特征選擇結(jié)果差強人意,這是由于它的特征選擇策略是逐個選取特征的方式。這種特征選擇方式忽略了特征之間的關(guān)系選出來的特征與其他模型相比特征冗余度高。

(3)在6個數(shù)據(jù)集的平均準(zhǔn)確率上,MFAGFS比次優(yōu)的NDFS模型高出了4.01%。另外值得注意的是,MFAGFS算法在所有數(shù)據(jù)集上的表現(xiàn)比基準(zhǔn)方法提高了1.01%到15.60%。說明MFAGFS能夠選擇出更加具有區(qū)分性的特征子集。

3.2.2 特征個數(shù)和聚類結(jié)果之間的關(guān)系分析

從實驗結(jié)果中,可以進一步分析特征個數(shù)和聚類結(jié)果之間的關(guān)系。從圖2和圖3中可以得出如下結(jié)論。

圖2 ACC隨選擇特征數(shù)量變化曲線

圖3 NMI隨著選擇特征數(shù)量變化曲線

(1)基線在PalmData25上的最好結(jié)果稍微好于其他數(shù)據(jù)集,這是由于PalmData25數(shù)據(jù)集的特征維度低,特征冗余度比較低。進行特征選擇的難度比較高。

(2)ACC和NMI并不是簡單的隨著特征維度的增高而增高,而是處于一種進入一定的特征維數(shù)后就開始穩(wěn)定,甚至波動。這說明了數(shù)據(jù)中真正的有效特征是少數(shù)的,大部分特征是冗余、無效的,過多的特征不僅帶來計算負(fù)擔(dān)還可能帶來負(fù)面效果。這也說明了特征選擇的必要性。

(3)SOGFS、FSASL以及MFAGFS這3個有自適應(yīng)學(xué)習(xí)數(shù)據(jù)的局部流形結(jié)構(gòu)的模型的表現(xiàn)比其他模型的表現(xiàn)要更加出色。說明了局部幾何信息在無監(jiān)督特征選擇中的重要性。

(4)MFAGFS的曲線基本處于其他算法的上方(除了PalmData25),這說明了局部幾何結(jié)構(gòu)和判別信息的充分利用有助于選擇出好的特征子集。

3.3 參數(shù)敏感度分析

MFAGFS在實驗中需要提前設(shè)置一些參數(shù),本節(jié)主要關(guān)注兩個主要正則參數(shù)η和β對實驗結(jié)果的影響,即用來保證數(shù)據(jù)局部相似性的β,以及用來控制特征選擇矩陣稀疏約束的η。通過重復(fù)使用k均值聚類20次并取其平均值,并取得到最好結(jié)果的維度作三維圖,如圖4和圖5所示。

圖4 ACC隨η和β的變化情況

圖5 NMI隨η和β的變化情況

3.3.1 聚類ACC分析

圖2和圖4是MFAGFS在6個數(shù)據(jù)集上,不同的β和η值所對應(yīng)的聚類ACC結(jié)果。算法在PalmData25和COIL20上的結(jié)果比較穩(wěn)定。這可能與PalmData25以及COIL20數(shù)據(jù)集樣本數(shù)目多進行特征選擇的難度比較低有關(guān)。

3.3.2 聚類NMI分析

圖3和圖5為MFAGFS在6個公開數(shù)據(jù)集上對應(yīng)不同的參數(shù)的聚類NMI的結(jié)果。從數(shù)據(jù)集ECOLI和ISOLET的聚類NMI上來看可以得到對數(shù)據(jù)進行參數(shù)選擇是必要的,不同的參數(shù)組合對結(jié)果的影響可能是巨大的。

另外從圖2～圖5上可以得出如下結(jié)論:同一參數(shù)組合下的ACC和NMI的表現(xiàn)可能有巨大差異。這是由于ACC和NMI是兩個完全不同的評價指標(biāo),不同的評價指標(biāo)造就不同的評價結(jié)果。

4 結(jié) 論

特征選擇是一種成熟的數(shù)據(jù)預(yù)處理方法,可以有效地去除冗余特征以及噪聲,進而達到降低數(shù)據(jù)維度且同時保留數(shù)據(jù)的重要信息的目的。無監(jiān)督的特征選擇算法相比于有監(jiān)督的特征選擇更加富有挑戰(zhàn)性。

本文提出了一種MFAGFS方法,通過矩陣分解得到的聚類信息以及通過自適應(yīng)圖得到的局部結(jié)構(gòu)信息指導(dǎo)特征選擇過程,為了防止過擬合進一步通過行稀疏的l2,1范數(shù)來去除數(shù)據(jù)中冗余特征提升特征選擇的效果。在6個真實世界的數(shù)據(jù)集上進行了對比試驗以及穩(wěn)定性試驗,試驗結(jié)果表明,提出的MFAGFS模型與相比其他無監(jiān)督特征選擇模型相比,ACC和NMI都有一定程度的提升,模型具有更高的精度,且具有較高的魯棒性,對參數(shù)不敏感。

MFAGFS與NDFS一樣,都有通過聚類來獲得到判別性信息。但是NDFS進行譜聚類的時候是在原始空間,而數(shù)據(jù)在原始空間中有大量的噪聲和冗余特征,這會影響到所學(xué)習(xí)到的特征準(zhǔn)確性。而MFAGFS通過魯棒的矩陣分解獲得聚類標(biāo)簽可以有效地降低噪聲和異常點對特征選擇的影響。

MFAGFS和FSASL都考慮了噪聲點和異常點的影響,模型都比較魯棒。但是不同的是MFAGFS有對相似性矩陣進行更加細(xì)致的先驗約束,因此得到的結(jié)構(gòu)信息更加精確。

采用矩陣分解的模型來進行數(shù)據(jù)點的聚類,這是一個線性的模型。然而數(shù)據(jù)往往是嵌入在一個低維流形上的,數(shù)據(jù)之間存在復(fù)雜的非線性關(guān)系,這是線性的矩陣分解模型所處理不了的。如何應(yīng)用更先進的技術(shù)到特征選擇的過程中來,如張量分析、分解機,是本文后續(xù)重點研究的課題。