無監督動態超圖學習拉普拉斯矩陣特征選擇

吳換霞

(信陽農林學院 信息工程學院，河南 信陽 464000)

0 引 言

隨著對學習模型精度要求的不斷提高，實際應用中普遍采用高維特征來表示數據，高維數據通常含有噪聲和冗余，這既增加了存儲和計算成本，又降低了學習模型的精度[1,2]。因此如何有效實現高維數據的特征選擇成為了提升學習模型精度和效率的關鍵。

特征選擇是從原始特征中選擇活動特征的一種可解釋模型，已成為處理高維數據問題的常用解決方案[3]。為了考慮特征選擇的現實需求，現在的研究主要集中于半監督以及無監督特征選擇。Zhu等提出了一個PCGRBM模型，將成對約束融合到重構的可見層中，用于聚類任務[4]。為了減輕注釋的負擔，Gao等應用自學習方法構建了一個系統，該系統可以從大量未標記數據和少量標記示例中學習草圖識別。該系統通過擴展一個小的標記集來進行自學習，并從未標記的草圖中提取新的示例[5]。喬美英等開發了一個具有有監督微調和無監督分層自學習的深度稀疏自動編碼器網絡，用于實現機械故障識別[6]。雖然上述方法成功構建了半監督特征學習模型，但是，對于無先驗知識條件下的特征學習還存在一定的局限性。

為此提出了一系列無監督特征學習方法，Zhu等提出了一種基于遞歸自編碼網絡(RAE)的無監督特征學習方法，利用原始數據中的光譜和空間信息來產生高層次的特征[7]。李靜將自步學習和多視圖學習引入到基于圖拉普拉斯的半監督特征選擇算法中，提出了一個多視圖自適應半監督特征選擇算法[8]。Song等通過在譜特征選擇框架中嵌入拉普拉斯正則化子，提出了一種無監督譜特征選擇(USFS)方法，通過在稀疏特征選擇的框架中嵌入拉普拉斯正則化子來保持訓練樣本的局部相似性，使其同時具有可解釋性和可分辨性[9]。但是上述方法的拉普拉斯矩陣通常是從包含冗余特征的原始數據中學習得到的，因此很難輸出魯棒拉普拉斯矩陣，并且上述方法只關注于用一般的圖來學習拉普拉斯矩陣，無法捕捉樣本之間的復雜關系，從而難以輸出可靠的特征選擇模型。

為解決上述問題，提出了一種基于動態超圖學習拉普拉斯矩陣的無監督特征選擇方法。本文通過對訓練樣本的協方差矩陣施加正交約束，并利用超圖動態學習拉普拉斯矩陣分別保持低維訓練樣本的全局和局部結構，從而獲取樣本之間的復雜關系，從而輸出可靠的信息特征。實驗結果驗證提出的方法能夠有效提升無監督特征選擇的性能。

1 圖學習理論

1.1 固定通用圖學習

圖被廣泛用于保持樣本的幾何結構以提高降維性能，給定兩個不同的數據點xi和xj， 如果xi是xj的K近鄰(KNN)之一，則生成連接兩者的邊。此邊的權重的計算公式如下

(1)

式中：σ代表權衡參數。LPP是一種經典的通用圖方法，其使用相似矩陣來保持樣本的局部結構，生成固定通用圖的計算公式為

(2)

1.2 動態通用圖學習

由于原始數據通常含有噪聲和異常值，所以原始數據構造的拉普拉斯矩陣的可靠性較差。針對這一問題，可以在稀疏特征選擇過程中嵌入一般的圖學習，使得相似矩陣可以由低維空間而不是原始特征空間來構造。動態廣義圖學習的表達式為

(3)

2 本文方法

2.1 超圖學習

在先前的USFS研究方法中，由一般圖構造的相似度矩陣并不能反映樣本間的復雜關系。此外，從原始數據中學習到的相似度矩陣包含了大量不相關的冗余信息特征，從而無法輸出可靠的特征選擇模型。為了解決這些問題，本文設計了超圖學習來解決第一個問題，并使用動態廣義圖矩陣學習來解決第二個問題，通過學習動態超圖來捕捉樣本在低維特征中固有的復雜結構空間。

一般的圖方法使用訓練樣本之間的成對關系來保持訓練樣本的局部結構，并且已經驗證不足以捕獲訓練樣本中的復雜關系。為了解決這個問題，本文構造了作者-論文關系，如圖1所示，其中圖1中的左半部分使用了一個易于測量兩個樣本之間關系的通用圖來描述作者-論文關系，例如，a1與a2(即a1和a2是論文的作者)、a2與a3以及a2與a4。 然而，表示兩者之間的真正關系仍舊較為困難，即第一篇論文有3位作者(即a1、a2和a3)，第二篇論文有兩位作者(即a2和a4)。相比之下，圖1的右圖通過構造超鏈接便能輕易指明這兩種類型的關系，因此本文的重點是利用超圖來保存訓練數據的局部結構，因為超圖可以比一般圖獲得更復雜的數據關系。

圖1 普通圖和超圖之間區別

通過將超圖表示為G=(V,E,w)， 其中V=[v1,…,vn] 和E=[e1,…,en] 分別是頂點和超邊的集合，W=[w1,…,wn] 是超邊的權重，超圖的構造包括3個連續分量：

(1)表示二元頂點-邊關系的關聯矩陣H，其中每個參數的定義為

(4)

(2)度量超邊重要性的權重向量w；

(3)超圖拉普拉斯L，即超圖的規范化拉普拉斯矩陣。

與一般的圖不同，超圖的關聯矩陣H描述了頂點和超邊之間的關系。為此，首先，給定訓練數據X∈Rc×n， 其中c和n分別表示特征數和樣本數，本文將每個樣本視為一個頂點，并嘗試按照文獻[10]中的方法為每個頂點生成一個超邊，即通過以下公式生成超邊ei

ei={vj|θ(xi,xj)≤0.1σi},i,j=1,…,n

(5)

式中：θ(xi,xj) 表示xi和xj之間的相似性，而σi是xi和每個其它樣本之間的平均距離。上述閾值方法常用于超邊的構造，并且適用于不同樣本具有不同數量的最近鄰的情況。

其次，本文利用得到的關聯矩陣H和訓練數據來學習每一條超邊的重要性，即w。然后，進一步通過δ(ei)=∑vj∈Eh(vj,ei)和d(vj)=∑vj∈ei,ei∈Ew(ei)h(vj,ei) 得到超邊ei的度和δ(ei) 頂點vj的度d(vj)。 超圖拉普拉斯矩陣的表達式為

(6)

式中：I∈Rn×n是單位矩陣，De，Dv和W分別是δ=[δ(ei)]，d=[d(vj)] 和w的對角矩陣。最后，由式(6)構造一個超圖，從而保持不少于兩個樣本之間的關系。

2.2 局部和全局結構保持的超圖學習

進一步提出了保持訓練數據的局部超圖結構，并通過動態學習超圖來解決兩步USFS方法的問題。為此，本研究構造了以下目標函數

(7)

(8)

式中：正交約束STXLXTS=I潛在地進行子空間學習，從而保持訓練數據的全局結構。

2.3 目標函數

由于構造超圖的3個部分是有一定次序的，因此，W或L的性能取決于H。然而，H是從原始訓練數據中學習的，通常包含噪聲和冗余信息。通常，性能較差的H不能得到性能較好的L，因此不能通過式(8)有效地降低特征維數。本文在統一的框架下，將超圖H的學習與S的學習結合起來。本文希望通過修復另一個來迭代更新其內容，以便動態更新得以輸出最優H和S。為此，本文為DHLFS方法設計了最終目標函數，如下所示

(9)

式(9)可直接改寫為

(10)

首先，在式(10)中的方法將子空間學習和特征選擇集成在一個統一的框架中，其中子空間學習和特征選擇可以相互提供互補信息，以便從不同方面去除噪聲和冗余。下一步將對各個變量進行優化。

2.4 優 化

2.4.1 通過修正其它變量更新

固定其它變量后，關于S的目標函數變為

(11)

由于l2,1范數正則化器是凸的和非光滑的，便采用迭代加權最小二乘法(IRLS)的框架來優化S，通過將式(11)轉換為

(12)

式中：P是對角矩陣，矩陣中的元素的計算公式

(13)

在式(12)中，P和S都是未知的。此外，P依賴于S，根據IRLS框架，本文設計了一個迭代算法，通過兩個連續步驟求解方程(12)，直到算法收斂：①通過固定S，通過方程(13)得到P；②通過固定P，方程(12)變為關于S的特征分解問題，即

(14)

式(14)中的最優解S是 (XXT+εI)-I(XLXT+βP) 的特征向量，因為XXT+εI是可逆的，ε是非常小的正值。

2.4.2 通過修正其它變量來更新H

根據等式(5)，超邊是從原始訓練數據生成的，因此可能導致不準確的超圖。為此，設計了從低維訓練數據中學習超邊緣的方法，盡可能地去除了噪聲和冗余。因此，使用以下公式來構造超邊集

(15)

式(15)表明本文方法：①低維特征空間的關聯矩陣H；②不同樣本(或邊)的不同鄰域數。得到關聯矩陣H后，利用該矩陣可以很容易地求出De

(16)

2.4.3 通過固定其它變量來更新W

通過固定其它變量，可以得到關于W的目標函數為

(17)

考慮到單位矩陣I與W無關；W是對角矩陣；tr(ABC)=tr(BCA)， 式(17)可改為

(18)

(19)

通過使用拉格朗日乘數法可將式(19)改為

(20)

其中，η≥0和γ≥0是拉格朗日乘子。基于KKT條件[11]，由此可以得到wi,i=1,…,n的閉式解，如下所示

(21)

(22)

式(9)并非所有變量(即W、S和H)的共同凸點，但對每個變量都是凸的，同時固定了其它變量。因此，本文采用替代優化策略來優化式(9)，即迭代優化每個變量，同時固定其它變量，直到算法收斂。具體優化算法步驟見算法1。

算法1：優化算法

輸入：X∈Rc×n，L∈Rn×n,α和β；

輸出：S,W,H,Dv以及De；

(1)隨機初始化S；

(2)隨機初始化W；

(3)While 不收斂 do

(4) while 不收斂 do

(5) 用式(14)計算P

(6) 用式(15)計算S

(7) end while

(8)用式(17)計算H；

(9)用方程式(17)計算De

(10)用方程(20)計算W；

(11)用方程(22)計算Dv；

(12)end while

2.5 復雜度分析

本文提出的DHLFS的時間復雜度包括3個部分，即S、W和H的更新。S的更新是一個特征值分解問題，其時間復雜度為min{O(t1c3),O(t1nc2)}， 其中t1、c和n分別是IRLS的迭代次數、特征和樣本。W的優化具有閉式解，其時間復雜度為O(nc2)， 而H的構造實際上需要構造一個n×n的相似矩陣，其時間復雜度約為O(nc2)。 因此，DHLFS的時間復雜度為min{O(t1t2c3),O(t1t2nc2)}， 其中t2是更新S、W和H的迭代所需復雜度。

2.6 α的計算

式(10)有兩個權衡參數，即α和β。在本文中，可以根據等式(21)中超圖的構造來確定α的值。尤其是，首先對f=[f1,…,fn] 進行升序排序，得到q=[q1,…,qn]。 每個頂點有不同的鄰域，首先，將鄰域數的最大值設為k，得到：fk≥0，fk+1=0， 公式如下

(23)

通過考慮W，即WT1=1， 可以得到

(24)

結合式(23)和式(24)，可以得到

(25)

這表明

(26)

2.7 收斂性分析

本節驗證了算法1的收斂性，以驗證本文算法的優勢，從而解決本文提出的目標函數在式(11)是合理的。

定理1 算法1分別可以令式(11)和式(12)的目標函數值單調減小，直到收斂。

證明。首先，將第t次迭代的優化結果分別表示為S(t)、W(t)和L(t)。 通過定理1和文獻[12]，可以得到

tr(S(t+1)TXLXTS(t+1))+βtr(S(t+1)TPS(t+1))≤ (S(t)XLXTS(t))+βtr(S(t)TPS(t))

(27)

本文可以通過式(14)得到以下導數

(28)

根據文獻[13]中的結論，可以得到

(29)

將式(29)代入式(28)，可以得到

(30)

而式(11)對3個變量的優化過程，即S、W和L單調減小。通過固定W(t)和L(t)來更新S(t+1)。 根據IRLS收斂于S的優化結果，即

(31)

通過固定S(t+1)和L(t)來更新W(t+1)。 通過式(22)，變量W有閉式解，即

(32)

通過給定S(t+1)和W(t+1)來更新L(t+1)。 根據式(8)，L的優化與變量有關，即W、H、De和Dv。H，De和Dv的變量有閉式解，W的收斂性在式(32)中得到了驗證，因此L的收斂結果較好，即

(33)

通過將式(31)、式(32)和式(33)積分，可以得到

(34)

式(34)表示式(11)的目標函數值在每次迭代中減小，因此算法1收斂。

3 實驗分析

3.1 數據集與實驗設置

在本節中，使用前面的5種方法對本文方法進行了評估，這些方法涉及公共UCI數據集上的聚類任務，表1列出了這些數據集的詳細信息，以及Berkeley分割數據集(BSD500)上的分割任務。

表1 所用數據集的詳細介紹

所有的數據集都是在一臺個人計算機(PC)上進行處理的，配置為3.7 GHz的i7中央處理器(CPU)和64 GB的隨機存取存儲器(RAM)。算法運行平臺為Matlab2016a，所有算法的程序均通過Matlab腳本編寫運行。

相應的對比方法如下：

基線方法：對原始數據進行k均值聚類。

拉普拉斯分數(LS)[6]：通過學習一個通用圖來保存訓練數據的局部結構，使用拉普拉斯分數來評估每個特征的重要性。

最小化光譜特征選擇(MRFS)的特征冗余[8]：是一種兩步USFS方法，它使用最小平方損失函數和l2,1范數正則化項輸出稀疏結果。

結構化最優圖特征選擇(SOGFS)[9]：將圖學習嵌入稀疏特征選擇的框架中。

耦合字典學習特征選擇(CDLFS)[14]：使用合成字典重構樣本，使用分析字典對樣本進行分析編碼，旨在為特征分配概率進行特征選擇。

聯合超圖學習和稀疏回歸(JHLSR)[15]：學習動態超圖從而保持樣本的局部結構。

在本文的實驗中，采用10倍交叉驗證的方法將數據集隨機分成10部分，其中一部分用于測試，其余部分用于訓練。在訓練過程中，本文進一步采用5倍交叉驗證法進行模型選擇，將參數取值范圍設為 {10-3,10-2,…,103}， 所有方法都能達到最佳效果。在每個實驗中，首先使用所有的特征選擇方法來選擇一個特征子集，其中特征數在所有特征的 {20%，30%，…，80%} 范圍內變化，然后在縮減的數據集上進行k均值聚類。本文對所有方法重復k均值聚類20次，并取平均結果。最后，本文利用聚類準確度來評估所有方法的性能。其它方法的參數選擇均參考相應的文獻進行復現。

3.2 聚類分析

3.2.1 聚類結果

在本節中，通過在圖2中列出具有不同數量的選定特征的所有方法的聚類精度，在12個公共UCI數據集上用比較方法評估了DHLF。

圖2 所有方法的聚類精度

本文的方法在大多數數據集上取得了最好的聚類性能，其次是JHLSR、SOGFS、CDLFS、MRFS、LS和Baseline。例如，本文的方法與最差的方法(即Baseline)和最佳比較方法(即JHLSR)相比，平均分別提高了5.38%和2.01%，原因可能是本文的方法：①在統一的框架下進行子空間學習和特征選擇；②從低維訓練數據中學習超圖，從而得到最優的超圖捕獲訓練數據的高階局部結構。

從圖2中，還觀察到原始數據中存在冗余和不相關的特征，在進行聚類之前需要進行降維任務。首先，所有的特征選擇方法都優于基線方法。例如，在所有數據集上，LS平均比基線方法提高了3.03%。第二，所有特征選擇方法的聚類精度首先隨著特征維數的增加而提高。到達峰值后，聚類精度開始下降甚至不穩定。例如，在保持60%特征的情況下，聚類精度先提高到55.7%，然后在保持80%特征的情況下，聚類精度又下降到52.0%，這一趨勢表明，少量特征不能很好地解釋學習模型，而過多的特征可能會增加冗余特征，降低聚類性能。另外，進一步驗證了提出方法相對與其它方法能夠更加有效捕捉不同樣本之間的復雜關系，從而有效實現了聚類精度的提升。

3.2.2 參數靈敏度

本文在式(11)中提出的目標函數有兩個權衡參數，即α和β。固定了α的值，并使用β來調整權重矩陣S的稀疏性。具體來說，β的值越大，S的稀疏性就越高。圖3展示了在所有數據集上相對于β的聚類精度的變化。

圖3 所有數據集關于β的聚類精度變化

從圖3可以看出，本文的方法在β的某些值上獲得了最佳的聚類性能，這導致了S上的稀疏性，即選擇特征的子集。這再次驗證了本文的結論，即有必要對高維數據進行降維。例如，在數據集Mnis上，β值的最佳取值范圍是 [10-3,10-1]， 對應于在所有特征中保留大約30%的特征。

3.2.3 收斂性分析

前文從理論上驗證了優化算法的收斂性，圖4展示出了等式(11)的目標值相對于算法1的迭代次數的增加的變化。

圖4 不同數據集的迭代次數變化

3.3 圖像分割分析

3.3.1 數據集和相關參數設置

本文使用了所有的方法在BSD500上進行圖像分割，即先進行特征選擇，然后進行k均值聚類。

BSD500包括500幅真實標簽的自然風景圖片。在本文實驗中，首先，隨機選取了圖5所示的10幅圖像進行分割，分別是飛機、鵝、房子、汽車、鹿、海星、馬、花、狗和鳥。其次，使用簡單的線性迭代聚類方法來獲得所有選定圖像的超像素。首先將每幅圖像分割成300個超像素，每個超像素由9個特征表示。

圖5 圖像分割對比結果

本文采用所有的特征選擇方法，選取較少的9個特征進行圖像分割，然后采用k均值聚類進行分割，其中k值為每幅圖像的準確聚類數。此外，還分析了利用超像素的所有特征進行k均值聚類的方法。

3.3.2 圖像分割評價指標

本文采用了3個評價指標，即概率蘭特指數(PRI)、信息方差(VOI)和全局一致性誤差(GCE)來評價分割性能。

PRI通過以下公式計算預測分割標簽和地面真值標簽之間的成對相似性

(35)

VOI根據信息差異測量預測分割和地面真實之間的距離

VOI(S,G)=H(S)+H(G)_2I(S,G)

(36)

其中，H和I分別表示熵的平方和預測S和地面真值G之間的互信息立方。

GCE假設其中一個細分必須是另一個細分的細化，并強制所有局部細化遵守相同的標準

(37)

一般來說，PRI值越高，對應的方法越好。此外，VOI和GCE越低，方法越差。

3.3.3 性能分析

本文在圖5中展示了每個圖像的分割結果，并在表2中報告了相應的分割性能。根據實驗結果，本文的方法有效地區分了背景和目標。本文的方法是唯一一種能夠從汽車圖像的背景中完全分割出目標物體的方法。在圖像分割中，與其它方法相比，本文提出的方法分割出的目標物體最為完整。原因可能是本文的方法利用動態超圖學習從不同的角度(即子空間學習和特征選擇)保持數據的局部結構。

表2 所有方法的分割結果

表2(續)

根據表2，發現本文方法性能最好。也就是說，就所有3個評估指標而言，與最佳比較方法(即JHLSR)和最差方法(即基線)相比，本文方法平均改進了0.12和0.56。

4 結束語

為了捕捉樣本之間的復雜關系，并且提升噪聲魯棒性，提出了一種基于動態超圖學習拉普拉斯矩陣的無監督特征選擇方法。通過多個公共數據集在聚類任務和圖像分割任務上的實驗結果可以得出如下結論：①提出的方法能夠利用動態超圖學習從不同的角度保持數據的局部結構，從而有效提升了特征選擇的效果；②少量特征不能很好地解釋學習模型，而過多的特征可能會增加冗余特征，降低性能。而提出的方法能夠有效去除冗余特征，提取有效特征；③提出的方法具有較強的特征提取魯棒性。