魯棒的半監督多標簽特征選擇方法

嚴菲，王曉棟

（廈門理工學院 計算機與信息工程學院，福建 廈門 361024）

在機器學習中，特征選擇從原始數據集中提取最具代表性子集，降低數據維度以提高后續分類、聚類處理精度，是當前研究的熱點。按已標記數據樣本數量劃分，特征選擇方法可分為監督、無監督和半監督學習。監督特征選擇[1-2]在已知數據集和類別標簽上訓練學習模型。在已獲取大量已知標簽時，該類方法能取得較好的識別效果。但在實際應用中獲取大量已知標簽較困難，且當已知標簽數量不足時該類方法性能迅速下降。無監督特征選擇方法[3-4]通過對無標簽數據的訓練以發現其隱藏的結構性知識，但由于缺乏可區分性的標簽信息導致學習性下降。近年來，半監督特征選擇將少量已知標簽數據與未標記數據結合建立學習模型，受到學者的廣泛研究。Doquire等[5]提出以數據方差為評價準則篩選出重要特征，但其忽略了特征間的相關性，易陷入局部最優。為解決此問題，研究者提出基于譜圖理論的半監督方法，依據某準則建立Laplacian矩陣提取數據底層流形結構進行特征選擇，如Liu等[6]提出以跡比準則為評價機制，Ma等[7]引入流形正則化的稀疏特征選擇方法等。

在現實應用中，存在某個數據樣本同時隸屬于一個或多個不同的類別，如網頁分類、自然場景分類等。以圖像標注為例，一幅自然圖像可包含多種場景，如樹、陸地、沙漠，即一個圖像樣本可屬于多種類別。最簡單的解決方法將多標簽簇問題分解為多個獨立單標簽分類問題，但其忽略了多標簽間的相關性。為此，Ji等[8]利用多標簽的共享子空間建立學習框架，文獻[9]使用互信息和交互信息的理論方法尋找最優子集，這些方法均屬于監督類方法。但現實應用中大量訓練樣本中已標記數據極少。如何利用未標記數據及其之間的關系信息提高泛化性能，給多標簽特征選擇方法帶來了巨大的挑戰。針對此問題，研究者提出半監督多標簽特征學習。Alalga等[10]提出利用Laplacian得分判斷多標簽類間關系，但其利用l2-范數建立Laplacian矩陣易受離群點的影響，從而導致學習穩定性差。Chang等[11]提出基于全局線性約束的多標簽半監督方法，無需構建Laplacian圖和特征分解操作，計算量少，速度快，但其忽略了真實數據嵌入在高維空間的底層流形結構。受啟于上述研究工作，本文提出基于l1圖的半監督多標簽特征選擇方法SMFSL (semi-supervised multi-label feature selection method based on L1-norm graph)，利用全局線性回歸函數方法和l2,1組稀疏約束建立多標簽特征選擇模型，引用l1圖模型以提高特征選擇準確度。

1 范數圖模型

在機器學習中，基于圖的學習方法通過構建近鄰圖，利用樣本間反映流形分布而建立問題模型，得到廣泛的研究應用。其中，基于譜圖理論的譜聚類學習方法[12]，在多種應用場景下取得較好的效果。

譜聚類根據數據樣本間的相似關系建立Laplacian矩陣，利用特征值和特征向量獲取樣本間的內在聯系。給定 n 組數據集 X={x1，x2，···，xn}∈Rd×n，其中 xi∈Rd為第 i組數據，d 為維度。定義G=(V，A)為無向權重圖，其中V為向量集，相似矩陣 A=[A1A2··· An]∈Rn×n，Aji=Aij≥0?；诟咚购撕瘮郸蚁嗨凭仃嘇定義為

式中：σ為寬度參數，控制函數的徑向作用范圍。

基于式(1)構造加權圖，譜聚類算法將聚類問題轉化為圖劃分問題，但其最優解為NP問題。傳統解決方法以借助松弛方法得到連續的類別標簽，進而轉換為率切(ratio cut)問題：

式中：Q=[q1q2··· qn]T∈Rn×c為聚類指標矩陣，c 為類別標簽數，qk∈Rc為Q矩陣第k列；L為譜圖Laplacian矩陣，其定義為L=D-A，D為對角矩陣，其每個i對角元素。為獲取最終的類別標簽，必須進一步借助聚類算法將連續值矩陣Q進行離散化，如采用K-means算法等。Nie等[13]提出基于l1范數圖模型來獲取更清晰的流形結構，上述式(2)轉換為

2 基于l1圖的半監督多標簽特征選擇方法

2.1 問題定義

給定數據集 X=[x1x2··· xlxl+1··· xn]∈Rd×n，xi∈Rd為第i組數據，d為維度，l為已標記樣本數。設 Y=[y y ··· y]T∈Rl×c為已標記數據集

l12l的標簽矩陣， yi∈{0,1}c為數據xi的類別標簽。若xi被標識為j類，則Yij=1，否則Yij=0。為獲取未標簽數據的類別標簽信息，定義預測標簽矩陣，其中 Fl初始化為 Yl，Fu∈R(n-l)×c則為未標簽數據的標簽矩陣，且初始化Fu=Ο，Ο為所有元素為0的矩陣。定義W=[w1w2··· wd]T∈Rd×c為特征選擇分類器，半監督多標簽特征選擇學習模型定義為

在式 (4)中， Ω(·)為正則化項 (可以選擇不同的正則化模型，如l1范數、l2,1范數等)，參數γ為正則化參數，loss(·)為損失函數。從模型的簡單性、高效性角度進行考慮，本文選擇最小二乘法作為損失函數，式(4)可表示為

式中：b∈Rc為偏置量；1∈Rn為元素值全是1的列向量。

從式(5)可以看出，利用線性回歸函數逐漸逼近可找出全局最優，但卻忽略了其局部數據之間相關性。為提高特征選擇準確度，文獻[7]提出建立相似矩陣以獲取局部流形結構，建立的學習模型如下：

半監督學習應用中，已標簽的數據集往往只占據小部分，無標簽數據集非常龐大，而離群點一般存在無標簽數據集中。Nie等[13]研究證明，采用l1范數有效減少噪音的影響，從而獲取更清晰的譜聚類結構，因此本文提出將l1范數引入半監督學習模型中。同時為減少外界噪聲點的干擾，本文提出采用l2,1范數[3]來約束最小二乘損失函數。給定任意矩陣M∈Rd×c，其定義為結合式(3)，式(6)轉換為

為有效地去除原數據集的冗余特征，本文對特征選擇矩陣W引入正則化模型l2,1范數，最后提出的目標函數定義如下：

2.2 學習模型求解

為獲取最終選擇特征子集，將對多標簽特征選擇的目標函數進行模型求解。由于目標函數式(7)引入的l2,1范數具有非光滑特征，無法直接進行求解，因此本文提出一種迭代優化方法來解決。

首先，將目標函數(7)進行轉換。定義對角矩陣S，其元素。其中，為防止Sii除數為0，δ的值為接近于0的正常量。式(7)轉換后形式如下：

保持W，S，F不變，將式(8)對b求導，令求導結果為0，得到：

將式(10)對W求導，并令求導結果為0，得到

式中DW為對角矩陣，可表示為

由于矩陣DW與W相關，無法直接求解上式。為解決此問題，將W隨機初始化以獲取矩陣DW，轉換式 (11)，推導出：

為求解F，將式(10)進行變換，得到：

轉換式(14)，得到：

將W的求導結果式(13)代入式(15)，得到：

定義M為：

將式(16)按分塊矩陣形式轉換為：

將上式對Fu求導，并令求導結果為0，得到：

基于以上推導過程求解學習模型，本文方法具體描述如下：

算法1SMFSL

輸入數據集類別標簽，相似矩陣A，參數；

輸出特征選擇矩陣W，預測標簽矩陣F。

1) t=0，隨機初始化 Wt?Rd×c，bt?Rc，Ft?Rn×c

2) repeat

9) 更新

10) 更新

11) t=t+1

2.3 收斂性分析

本小節將對上一小節提出的SMFSL算法收斂性進行證明。

引理1對于任意非零的向量p,q∈Rc，有以下不等式成立：

根據以上引理，本文提出以下定理：

定理1算法SMFSL在每次迭代過程中最小化目標函數。

證明為方便起見，首先定義g(W,F,bT,S)=αtr((XTW+1bT-F)TS(XTW+1bT-F)) 。目標函數可寫為：

假設在第t次迭代后獲得了W，F,bT和S。在下一次迭代中，固定W為Wt、b為bt、S為St來求解Ft+1，參考文獻[14]中的方法可得出：

結合引理1的式(18)，有以下公式：

結合式(20)和(21)，得到

接下來，固定 F 為 Ft+1、b為 bt、S為 St來求解Wt+1，根據算法1可得出：

同樣，參考文獻[14]中的方法，可得出：

接下來，固定F為Ft+1、W為Wt+1求解bt+1、St+1，同樣，參考文獻[14]中的方法，可得出：

最后，結合式 (22)、(23)和 (24)，可得出：

從式(25)中可證明出算法1是收斂的。

3 實驗分析

3.1 對比方法及實驗數據

為驗證本文方法的有效性，對相關方法進行描述。

All-feature：其數據未采用特征選擇，本次實驗以該分類結果作為基準線。

TRCFS(trace ratio criterion for feature selection)[6]：采用譜圖的半監督學習方法，其通過引入具有抗噪聲的率切準則提高特征選擇的效率。

CSFS(convex semi-supervised multi-label feature selection)[12]：該將線性回歸模型引入特征選擇模型中，是一種快速的半監督特征選擇方法。

FSNM(feature selection via joint l2,1-norms minimization)[1]：監督學習方法，其在損失函數和正則化方面采用l2,1范數模型進行特征選擇。

本次實驗將所提出方法應用到各種場景，包括自然場景分類、網頁分類和基因功能分類。同時本文將各方法應用到多種開源數據庫，包括MIML[15]、YEAST[16]、Education[17]和 Entertainment[17]，數據集的相關屬性描述如表1所示。

本文對于每一種方法所有涉及到的參數(如果有的話)的范圍設定為{10-4、10-2、100、102、104}。對于每種數據集，隨機選擇n個樣本作為訓練集，其中分別選擇10%、20%和40%的數據為已標記數據集，其余為未標記數據。實驗獨立重復5次，最后取其平均值。本次實驗選擇MLKNN作為多標簽分類器，其中MLKNN的優化參數參照文獻[18]。

表 1 實驗數據集Table 1 Experimental datasets

3.2 性能對比分析

本次實驗選擇Hamming loss(HL，漢明損失)、One-Error(OE，單錯誤)作為評價指標[19]用來評價方法的分類性能。其中，Hamming loss和One Error值越低代表性能越好。圖1、2列出了以Allfeature方法的分類結果為基準線，TRCFS、CSFS、FSNM以及本文提出的SMFSL方法在各種數據集的性能對比分析。其中圖1分別為HL評價標準的性能提升百分比，以及圖2分別為OE評價標準的性能提升百分比。從圖中可以看出：

1) 大部分特征選擇方法要優于未采用特征選擇的All-feature，由此可證明特征選擇有助于提高多標記學習性能。但在YEAST、Education和Entertainment數據集中，TRCFS學習性能整體略低于All-feature，但該方法經過特征選擇后維度會有所降低，從而能有效地節省后續分類時間。

圖 1 各種方法在各數據集上的漢明損失Fig. 1 Hamming loss comparison of various methods on various datasets

圖 2 各種方法在各數據集上的單錯誤Fig. 2 One-Error comparison of various methods on various datasets

2) CSFS在部分數據集上表現略差于FSNM，這是由于CSFS方法采用l2范式損失函數，對噪聲較敏感。當無標簽數據集比例較大時，噪聲較多，CSFS的分類性能受噪聲影響較大。而當已標記數據集比例增加時，其與FSNM差距越小。

3) 本文提出的SMFSL方法優于其他方法，由此可證明采用l2,1范式約束全局回歸函數能有效減少外界噪聲影響，同時結合l1圖建立相似矩陣能有效獲取底層局部流形結構，提高分類性能。

3.3 模型魯棒性分析

為驗證本文所提出模型的魯棒性，本次實驗針對不同類型相似矩陣進行對比分析。實驗采用如圖3(a)所示的雙月(two-moon)數據集。該數據集可分為上半月形和下半月形2個類別數據，具有明顯的流形結構。基于l2范數的相似矩陣如圖3(b)所示，其中任意2個數據間的連線代表其具有相似性。從圖中可以看出，該相似矩陣存在過多冗余連接，無法提取清晰的流形結構信息，很難直接應用于后續對數據的分類任務。本文模型輸出的相似矩陣如圖3(c)所示，可明顯看出，在l1范數稀疏性約束下，該相似矩陣可有效剔除數據間的無關連接，提取更加清晰的流形結構信息，進而有助于提高分類模型的準確性和對外界噪聲的抗干擾性。

3.4 特征數對分類性能的影響

本次實驗挑選了MIML、YEAST和Education數據集在已標記樣本集為20%時，選擇不同特征數的Average Precision(AP，平均查準率)性能[19]對比效果，具體如圖4所示。據文獻[19]得知，AP值越高，表示方法性能越好。從圖中可以看出，MIML、YEAST、Education數據集在選擇特征數分別為40、80和400時AP值最高。這意味著選擇最大特征數并不一定能產生最高的AP值。在給定不同的特征數量時，本文所提方法普遍高于其他方法，尤其是在MIML和Education數據集優勢更加明顯。另外，從圖中看出不同方法的結果曲線出現交叉，這是由于不同方法所選擇出的最優特征子集不同，其對應的分類準確度也會有所不同。

3.5 參數敏感性分析

本次實驗將對學習模型中涉及的參數進行具體分析。為節省篇幅，本次實驗挑選YEAST、Education和Entertainment在已標記數據為40%、評價標準為One Error的性能分析。首先，固定α值為1，即參數調節范圍的中位數，調整γ和特征數進行分析，結果如圖5所示。同樣，固定參數γ的值為1，對α和特征數的變化進行分析，具體如圖6所示。從圖5、圖 6可以看出，參數α、γ的選擇依賴于所選數據集，如Entertainment數據集在固定α、特征數為600時，選擇γ=10-4時One Error性能最佳，而當γ=1該性能表現最差。因此在實驗測試時需對不同的數據集設置不同的參數。

圖 3 l1范數對相似矩陣的影響分析Fig. 3 Influence analysis of l1-norm on similarity matrix

圖 4 平均查準率與選擇的特征數量關系Fig. 4 Relation between average precision and the number of selected features

圖 5 本文方法的參數敏感性分析 (a=1)Fig. 5 Parameter sensitivity analysis of the proposed method (a=1)

圖 6 本文方法的參數敏感性分析 (γ=1)Fig. 6 Parameter sensitivity analysis of the proposed method (γ=1)

4 結束語

本文提出一種魯棒的半監督多標簽特征選擇方法SMFSL。不同于傳統基于譜圖的特征選擇方法，本文方法利用l2,1范數約束全局線性回歸函數，減少外界噪聲干擾，還借助l1圖獲取更清晰的數據底層流形結構，有效提取局部特征，以提高學習效率。為提高特征選擇準確度，本文引入l2,1范數約束特征選擇過程，有效利用特征間相關信息，進而過濾冗余特征。文中所提出的模型涉及l2,1范數具有非光滑特征，無法直接對其求閉合解，因此提出一套快速有效迭代方法求解學習模型。最后通過多個開源數據集實驗證明了本文方法的有效性。結合自適應學習及采用魯棒性更好的損失函數以進一步提高特征選擇的準確度，為本文的下一步研究目標。