嚴(yán)菲，王曉棟

（廈門理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，福建 廈門 361024）

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

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

1 范數(shù)圖模型

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

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

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

基于式(1)構(gòu)造加權(quán)圖，譜聚類算法將聚類問題轉(zhuǎn)化為圖劃分問題，但其最優(yōu)解為NP問題。傳統(tǒng)解決方法以借助松弛方法得到連續(xù)的類別標(biāo)簽，進(jìn)而轉(zhuǎn)換為率切(ratio cut)問題：

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

2 基于l1圖的半監(jiān)督多標(biāo)簽特征選擇方法

2.1 問題定義

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

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

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

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

從式(5)可以看出，利用線性回歸函數(shù)逐漸逼近可找出全局最優(yōu)，但卻忽略了其局部數(shù)據(jù)之間相關(guān)性。為提高特征選擇準(zhǔn)確度，文獻(xiàn)[7]提出建立相似矩陣以獲取局部流形結(jié)構(gòu)，建立的學(xué)習(xí)模型如下：

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

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

2.2 學(xué)習(xí)模型求解

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

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

保持W，S，F(xiàn)不變，將式(8)對b求導(dǎo)，令求導(dǎo)結(jié)果為0，得到：

將式(10)對W求導(dǎo)，并令求導(dǎo)結(jié)果為0，得到

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

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

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

轉(zhuǎn)換式(14)，得到：

將W的求導(dǎo)結(jié)果式(13)代入式(15)，得到：

定義M為：

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

將上式對Fu求導(dǎo)，并令求導(dǎo)結(jié)果為0，得到：

基于以上推導(dǎo)過程求解學(xué)習(xí)模型，本文方法具體描述如下：

算法1SMFSL

輸入數(shù)據(jù)集類別標(biāo)簽，相似矩陣A，參數(shù)；

輸出特征選擇矩陣W，預(yù)測標(biāo)簽矩陣F。

1) t=0，隨機(jī)初始化 Wt?Rd×c，bt?Rc，F(xiàn)t?Rn×c

2) repeat

9) 更新

10) 更新

11) t=t+1

2.3 收斂性分析

本小節(jié)將對上一小節(jié)提出的SMFSL算法收斂性進(jìn)行證明。

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

根據(jù)以上引理，本文提出以下定理：

定理1算法SMFSL在每次迭代過程中最小化目標(biāo)函數(shù)。

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

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

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

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

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

同樣，參考文獻(xiàn)[14]中的方法，可得出：

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

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

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

3 實(shí)驗(yàn)分析

3.1 對比方法及實(shí)驗(yàn)數(shù)據(jù)

為驗(yàn)證本文方法的有效性，對相關(guān)方法進(jìn)行描述。

All-feature：其數(shù)據(jù)未采用特征選擇，本次實(shí)驗(yàn)以該分類結(jié)果作為基準(zhǔn)線。

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

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

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

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

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

表 1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental datasets

3.2 性能對比分析

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

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

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

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

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

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

3.3 模型魯棒性分析

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

3.4 特征數(shù)對分類性能的影響

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

3.5 參數(shù)敏感性分析

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

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

圖 4 平均查準(zhǔn)率與選擇的特征數(shù)量關(guān)系Fig. 4 Relation between average precision and the number of selected features

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

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

4 結(jié)束語

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