基于流形學(xué)習(xí)的約束Laplacian分值多標(biāo)簽特征選擇

蔣偉東，黃 睿

上海大學(xué) 通信與信息工程學(xué)院，上海 200444

1 引言

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

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

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

2 本文算法

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

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

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

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

在多標(biāo)簽數(shù)據(jù)分類中，邏輯型的類別標(biāo)簽無法反映出實(shí)例所具有的不同標(biāo)簽的重要度。利用流形學(xué)習(xí)思想，將邏輯型標(biāo)簽轉(zhuǎn)化為數(shù)值型，通過標(biāo)簽的實(shí)值體現(xiàn)不同類別標(biāo)簽的相對重要性[12]。根據(jù)平滑假設(shè)（即相鄰的點(diǎn)很可能屬于同一類別）[14]，特征空間的拓?fù)浣Y(jié)構(gòu)可以傳遞到類別標(biāo)簽的數(shù)值空間。通過極小化下式得到特征流形結(jié)構(gòu)：

若 xj不是xi的近鄰，則將置為0。通過求解最小二乘問題獲得ψ。定義與邏輯型標(biāo)簽對應(yīng)的實(shí)值標(biāo)簽為zi∈RC。在獲得數(shù)據(jù)特征空間的流形結(jié)構(gòu)后，類別標(biāo)簽的流形結(jié)構(gòu)表示為：

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

在此基礎(chǔ)上，定義標(biāo)簽空間的鄰接矩陣如下：

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

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

下面對M-CLS的流程進(jìn)行了總結(jié)：

輸入：數(shù)據(jù)集X，多標(biāo)簽集Y，近鄰數(shù)k

輸出：每個(gè)特征的M-CLS分值

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

2.根據(jù)式（7）計(jì)算數(shù)值型標(biāo)簽空間的鄰接矩陣SL，并以此計(jì)算DL和LL。

ford=1∶D

3.根據(jù)式（4）、（8）、（9）計(jì)算每個(gè)特征的M-CLS分值。

end

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

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

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

表1 實(shí)驗(yàn)所用數(shù)據(jù)集

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

表2 不同方法在Recreation數(shù)據(jù)集上的性能比較

表3 不同方法在Yeast數(shù)據(jù)集上的性能比較

圖1 Recreation數(shù)據(jù)集分類結(jié)果對比

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

表4 不同方法在Recreation數(shù)據(jù)集上所選特征比較

表5 不同方法在Yeast數(shù)據(jù)集上所選特征比較

4 結(jié)論

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