基于流形學習的約束Laplacian分值多標簽特征選擇

蔣偉東，黃 睿

上海大學 通信與信息工程學院，上海 200444

1 引言

多標簽分類針對具有多個類別標簽的實例進行類別劃分，是數據挖掘領域的研究熱點之一，已在文本分類、信息檢索、生物信息提取等方面獲得廣泛應用[1-3]。與單標簽分類一樣，多標簽分類也會因標記樣本有限而受到維數災難問題的影響，導致分類器性能降低。通過多標簽特征選擇技術降低數據維數，可有效提高分類器性能。

相對于傳統單標簽特征選擇，多標簽數據的特征選擇更加復雜。張振海等提出基于信息熵的多標簽特征選擇算法，通過計算每個特征與標簽間的信息增益關系以及設置信息增益閾值，剔除不相關特征，得到最佳特征子集[4]。文獻[5]則是在原始的信息增益多標簽算法基礎上引入標簽間的相關性以實現特征重要度排序。文獻[6]提出一種融合特征排序的多標記特征選擇算法，首先在標簽下自適應粒化樣本，構造特征與標簽間鄰域關系并進行排序，最后通過聚類融合形成新的特征排序。對已有單標簽特征選擇算法進行改造應用于多標簽數據也是一種可行的方法。如：文獻[7]通過對多標簽數據相關性與特征權值的分析，提出基于ReliefF的多標簽特征選擇（Multi-Label ReliefF，ML-ReliefF）；Spolaor等提出基于Label Powerset處理方式的信息增益算法（Information Gain-Label Powerset，IG-LP），通過考慮不同的標簽組合，將多標簽直接轉換為單標簽，之后采用信息增益算法衡量每個特征與標簽間的相關度[8]。Chang等提出一種凸半監督多標簽特征選擇算法（Convex Semisupervised multi-label Feature Selection，CSFS），通過最小化最小二乘損失函數進行稀疏特征選擇，可用于大規模數據集[9]。Ma等提出基于多標簽學習的稀疏特征選擇算法（Sub-Feature Uncovering with Sparsity，SFUS），一方面通過稀疏空間選擇出最具有辨別力的特征，同時也考慮不同標簽間的相關性[10]。Alalga等將不同樣本的類別標簽相似性定義為軟約束，并用以修正鄰接矩陣，提出一種半監督的軟約束Laplacian Score（Soft-Constrained Laplacian Score，S-CLS）[11]。

在多標簽數據分類中，樣本的類別標簽通常為邏輯型，即若樣本屬于該類別則置為“1”，否則置為“0”。這樣的表示方法沒有考慮到不同類別標簽對于同一樣本的重要性往往是不同的。Hou等利用流形學習思想對類別標簽的重要性進行量化，將邏輯型類別標簽映射為數值型類別標簽[12]。受此啟發，本文提出一種基于流形學習的約束Laplacian分值多標簽特征選擇方法（Manifold-based Constraint Laplacian Score，M-CLS）。方法首先從數據空間對特征進行評分，利用邏輯型類別標簽間的相似性修正Laplacian分值；接著在標簽空間通過流形學習將邏輯型類別標簽映射為數值型類別標簽，并計算相應的Laplacian分值；兩種分值之積為最終的特征分值。實驗結果表明，所提M-CLS方法能提取出更有效的特征子集，獲得更好的多標簽分類性能。

2 本文算法

對于單標簽數據，樣本間的關系可以直接劃分為同類和異類。但對于多標簽數據，由于每個樣本都具有多個類別標簽，需要衡量不同樣本間類別標簽的相似性。定義樣本xi與xj的邏輯型類別標簽的相似性為：

其中，δ(?)為狄拉克函數，有：

在此基礎上定義特征空間鄰接矩陣如下：

其中，t為可調參數。對于第n個特征 fn(1≤n≤N)，特征空間的約束Laplacian分值定義為[13]：

在多標簽數據分類中，邏輯型的類別標簽無法反映出實例所具有的不同標簽的重要度。利用流形學習思想，將邏輯型標簽轉化為數值型，通過標簽的實值體現不同類別標簽的相對重要性[12]。根據平滑假設（即相鄰的點很可能屬于同一類別）[14]，特征空間的拓撲結構可以傳遞到類別標簽的數值空間。通過極小化下式得到特征流形結構：

若 xj不是xi的近鄰，則將置為0。通過求解最小二乘問題獲得ψ。定義與邏輯型標簽對應的實值標簽為zi∈RC。在獲得數據特征空間的流形結構后，類別標簽的流形結構表示為：

在給定ψ的前提下極小化上式，獲得實值標簽z。實值標簽一方面反映了同一實例具有的不同類別標簽的重要度差異，另一方面也體現了同一類別標簽對不同實例的重要度差異。

在此基礎上，定義標簽空間的鄰接矩陣如下：

其中，dmax和dmin分別為實值標簽間的最大和最小歐式距離。對于第n個特征 fn(1≤n≤N)，實值標簽空間的Laplacian分值定義為：

結合式（4）和（8），對于第 n個特征 fn(1≤n≤N)，基于流形的約束Laplacian分值定義如下：

下面對M-CLS的流程進行了總結：

輸入：數據集X，多標簽集Y，近鄰數k

輸出：每個特征的M-CLS分值

1.根據式（1）、（2）、（3）計算特征空間的約束鄰接矩陣SF，并以此計算DF和LF。

2.根據式（7）計算數值型標簽空間的鄰接矩陣SL，并以此計算DL和LL。

ford=1∶D

3.根據式（4）、（8）、（9）計算每個特征的M-CLS分值。

end

4.對特征按M-CLS值排序。

3 實驗

為驗證所提算法M-CLS的性能，在多標簽數據集Recreation和Yeast上進行了特征選擇與分類實驗，并與4種多標簽特征選擇算法IG-LP、CSFS、SFUS和ML-ReliefF的實驗結果進行比較。分類器為ML-KNN[15]，近鄰數k設為10。采用漢明損失（Hamming Loss），排序損失（Ranking Loss），1-錯誤率（One Error），覆蓋長度（Coverage）和預測精度（Precision）這5個性能評價指標進行性能評價[16]，其中，前4個指標與預測精度相反，值越小表示分類效果越好。表1給出了所用數據集的具體描述。

表1 實驗所用數據集

表2、3分別列出了不同特征選擇方法在數據集Recreation和Yeast上的分類結果。此外，還給出了采用全部特征時的分類性能指標，作為比較基準。可以看到，所提算法的5個指標與其他特征選擇方法相比不但具有明顯優勢；而且也優于采用特征全集時的性能指標。圖1進一步給出了不同方法對于Recreation數據選擇不同特征數時的性能指標，橫坐標為所選特征數，縱坐標為參數值，可以看到，特征選擇方法的性能并沒有隨著特征數的增多而逐漸提升，而是存在明顯起伏，這在M-CLS上表現的尤為突出。M-CLS在選擇較少特征數時體現出更好的性能，說明此方法在特征子集規模相同情況下能選擇出更有效的特征構成子集。

表2 不同方法在Recreation數據集上的性能比較

表3 不同方法在Yeast數據集上的性能比較

圖1 Recreation數據集分類結果對比

表4、5列出了兩個數據集采用不同方法進行特征評分時，所選出的最重要特征。可以看到，不同特征選擇方法選擇出的最重要特征均不同。本文所提算法MCLS在Recreation、Yeast數據集上選擇出的最重要特征編號分別為Att493、Att34。

表4 不同方法在Recreation數據集上所選特征比較

表5 不同方法在Yeast數據集上所選特征比較

4 結論

提出一種基于流形學習的約束Laplacian分值多標簽特征選擇方法M-CLS。本文方法首先在特征空間利用邏輯型類別標簽的相似性對鄰接矩陣進行改進，定義了約束Laplacian分值；接著基于流形學習將邏輯型類別標簽映射為數值型類別標簽，在實值標簽空間定義新的鄰接矩陣，由此定義Laplacian分值；最后將兩種分值相乘獲得最終的特征評分。實驗結果表明，本文算法M-CLS能選擇出更有效的特征構成子集，性能優于多種多標簽特征選擇方法。