曹浪財, 林曉昌, 蘇思行

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

0 引 言

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

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

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

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

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

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

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

1 MFAGFS建模

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

為方便本節(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]。存在著正交和非負約束的矩陣U可以看作是一個放縮的聚類索引矩陣。正交約束和非負約束的同時存在提高矩陣的質量,并且非負約束更符合實際情況。由于用F范數(shù)作為損失函數(shù)容易受到噪聲點和異常點的影響。本文用l2,1范數(shù)來代替常見的F范數(shù)來避免大的損失從而使得所提的模型更加魯棒。表示如下:

(1)

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

1.2 自適應圖構建

1.2.1 基于局部結構的自適應圖

(2)

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

1.2.2 基于理想局部結構自適應圖

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

(3)

(4)

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

(5)

1.3 MFAGFS算法流程

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

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

(6)

圖1 模型算法流程圖

圖1中,投影矩陣W用來特征選擇,相似性矩陣S用來獲取局部結構。將自適應的局部結構學習、判別性信息的提取以及特征選擇融合到一體。

2 MFAGFS算法優(yōu)化

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

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

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

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

(7)

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

算法1 基于魯棒矩陣分解和自適應圖的無監(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的特征作為最后結果。

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

(1)相似性矩陣S

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

2γtr(ZTLU)

(8)

(9)

(2)特征選擇矩陣W

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

s.t.WTW=I

(10)

(11)

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

tr(ΛWTW-1)

(12)

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

對W求導并令其等于0可以得到:

(13)

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

(14)

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

(15)

特征選擇矩陣W的求解詳細描述如算法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個特征值所對應的特征向量,更新特征選擇矩陣W;2根據(jù)現(xiàn)有的W值,更新Q,直至收斂。輸出:特征選擇矩陣W∈Rm×d。

(3)聚類索引矩U

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

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

(16)

式中：

(17)

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

(18)

最后得到聚類標簽U的迭代更新公式:

(19)

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

(4)聚類中心V

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

(20)

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

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

(21)

(5)輔助變量E

子問題E如下所示:

(22)

(23)

(6)輔助變量Z

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

(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中的目標函數(shù)將單調遞減直到收斂。

(29)

基于引理1,可知:

(30)

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

(31)

證畢

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

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

(32)

式中:(·)+表示相似向量si是稀疏并且非負,意味著向量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 實驗準備

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

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

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

3.1.2 實驗設置

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

為了保證對比實驗的公平性和有效性,實驗中需要提前設置近鄰參數(shù)時,統(tǒng)一設置為k=5,高斯熱核函數(shù)中的參數(shù)σ大小設為1。此外,對于特征選擇矩陣(投影矩陣)的維數(shù)空間和潛在簇的個數(shù)都設為c(c是數(shù)據(jù)集的真實類別數(shù))。MFAGFS模型還需要調節(jié)η,β和γ這3個參數(shù)。其中γ用來實現(xiàn)對秩的約束,在具體實驗操作中根據(jù)秩的大小自動調節(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均值聚類的效果與初始化緊密相關,所以在實驗中重復實驗20次并記錄其平均值。

3.1.3 實驗評價指標

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

3.2 實驗結果分析

3.2.1 特征有效性分析

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

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

從表2以及表3中可以得到如下結論。

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

表3 各算法最優(yōu)標準互信息比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.1 聚類ACC分析

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

3.3.2 聚類NMI分析

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

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

4 結 論

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

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

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

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

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