基于圖拉普拉斯的多標簽類屬特征選擇

吳 君, 黃 睿

(上海大學通信與信息工程學院, 上海 200444)

在傳統的單標簽學習框架中, 每個樣本只對應一種標簽. 然而, 在現實生活中, 大部分對象都表現為多語義性[1-2], 即一個樣本同時對應多種標簽. 因此, 多標簽學習模型更具實際應用價值, 已經在圖像標注[3]、文本分類[4]、音樂情感分類[5]等領域獲得應用.

與單標簽學習一樣, 多標簽學習也會受到“維度災難”的影響, 尤其在多標簽分類問題中,大量冗余特征不僅會增加計算復雜度, 也會降低分類器的性能. 通過特征選擇, 去除無關冗余特征, 基于特征子集進行分類是解決該問題的有效方法. 目前, 已有很多標簽特征選擇算法[6-12], 但多數算法忽略了標簽與特征之間存在的內在聯系, 只是基于相同的特征子集對所有標簽進行分類. 事實上, 對于不同的標簽, 存在一些最能體現該標簽內在屬性的特征, 這些特征對相應標簽具有更強的判別能力, 被稱為類屬特征(label-specific features). 基于類屬特征的多標簽分類表現出了更好的性能, 如何構建類屬特征已成為相關領域的研究熱點之一[13-17].

Zhang 等[13]最早提出了基于類屬特征的多標簽學習(multi-label learning with labelspecific features, LIFT)算法, 該算法將數據的原始特征轉換為數據與正負樣本聚類中心的距離, 以此來構建類屬特征. 文獻[15-16]在LIFT 基礎上引入標簽相關性, 分別提出基于標簽相關性的類屬屬性多標簽分類算法(label-correlation based multi-label classification algorithm with label-specific features, CLLIFT)[15]和利用聚類集成的類屬特征多標簽學習(multi-label learning with label-specific features via clustering ensemble, LIFTACE)算法[16]. 上述算法采用特征變換的方式獲得類屬特征, 改變了特征屬性的固有含義. Huang等[14]則提出了一種類屬特征學習(learning label-specific features, LLSF)算法, 該算法通過優化具有稀疏正則項的線性分類器確定類屬特征. 但LLSF 得到的類屬特征子集規模較大, 特征間冗余較多. 文獻[17]基于線性判別分析思想改進LLSF 的目標函數, 提出了聯合特征選擇和分類的多標簽學習(joint feature selection and classification for multi-label learning, JFSC)算法[17].

LLSF 和JFSC 算法都假定數據與類別標簽間存在線性關系, 直接對標簽進行稀疏回歸學習來確定系數矩陣. 但事實上, 大部分數據都不滿足線性可分性, 因此該假設是不合理的. 本工作結合流形學習和稀疏回歸, 認為具有較高判別性的特征應盡可能保持數據的低維結構特性[18], 由此提出一種基于圖拉普拉斯的多標簽類屬特征選擇(multi-label label-specific feature selection based on graph Laplacian, LSGL)算法. 首先利用圖拉普拉斯獲取數據的低維流形結構, 再對流形結構的稀疏回歸計算系數矩陣, 確定類屬特征.

1 LSGL 算法

1.1 構建低維嵌入

設由N個樣本構成的數據集為X= [x1,x2,··· ,xN]∈RD×N, 標簽集合為L={l1,l2,··· ,lC}, 數據集對應的邏輯型類別標簽集為Y= [y1,y2,··· ,yN]T∈{0,1}N×C,C為類別標簽個數.xn ∈RD對應的標簽為yn= [yn1,yn2,··· ,ynC]∈{0,1}C, 1 表示樣本與標簽相關, 0 表示樣本與標簽無關.

對于同一標簽, 如果兩個樣本都是正樣本或負樣本, 那么它們之間的權重為1, 反之為0. 由此,可以得到對于標簽lc的鄰接矩陣Sc, 進而可以求得度矩陣Dc和拉普拉斯矩陣Lc[19],

式中: 矩陣Dc為對角陣, 對角元素為Sc每列元素之和. 數據的低維流形可以通過求解以下廣義特征值問題得到,

取前K個最小特征值對應的特征向量構成原始數據對于標簽lc的低維嵌入[20],

式中:K是低維嵌入的維數. 在文獻[21]提出的非監督譜聚類算法中, 低維流形的維數設置為數據的聚類簇數. 在LSGL 算法中, 對于每個標簽, 數據只可能具有該標簽或不具有該標簽,這是一個二分類問題, 可以認為數據由兩個類簇組成, 由此將K設置為2.

1.2 稀疏特征選擇

對于標簽lc, 從數據空間到流形空間的投影矩陣Wc=[w1,w2]可通過優化以下目標函數獲得,

式中:‖·‖2和‖·‖1分別表示向量的1 范數和2 范數;pck表示pc的第k列;wk為d維向量, 表示每個特征在相應維度上的權重, 而由于K= 2, 故低維嵌入實際上是一個二維空間,即k ∈{1,2}, 利用wk將原始數據映射到這個二維空間. 式(5)是一個典型的套索即最小絕對值收斂和選擇算子(least absolute shrinkage and selection operator, LASSO)回歸問題,l1正則化項保證了特征權重wk的稀疏性. 使用最小角回歸(least angle regression, LARS)算法[22]獲得wk.

投影矩陣Wc ∈Rd×2的每行表示對應特征在低維流形上的權重. 對于第d個特征, 定義重要度評分為

式中:Wcdk為Wc的第d行、第k列元素. 特征評分值越大, 表明該特征越重要.

對每個標簽計算投影矩陣, 可獲得相應的類屬特征, 再利用類屬特征對每個標簽構建二分類器進行訓練和預測. LSGL 算法的完整流程如表1 所示.

表1 LSGL 算法Table 1 LSGL algorithm

2 實 驗

2.1 數據集

為了評估所提出算法的性能, 在5 個多標簽數據集上進行特征選擇和分類實驗, 數據集均來自Mulan 數據庫(http://mulan.sourceforge.net/datasets-mllc.html), 詳細信息如表2 所示.

表2 數據集信息Table 2 Data information

2.2 實驗設置

本工作選取7 個多標簽學習算法作為對比算法, 并利用5 種評價指標衡量不同算法的性能.

2.2.1 對比算法

7 種多標簽學習算法分別為二元關聯法(binary relevance, BR)[23]、LIFT[13]、LLSF[14]、類屬特征學習-二元支持向量機(learning label-specific features-binary support vector machine, LLSF-BSVM)[14]、LASSO[11]、魯棒特征選擇(robust feature selection, RFS)[12]和利用稀疏性的子特征發現(sub-feature uncovering with sparsity, SFUS)[8], 可劃分為如下3 類.

(1) BR: 基于特征全集, 將多標簽學習問題轉換為多個二分類問題進行分類, 實驗結果可作為比較基準.

(2) LIFT、LLSF、LLSF-BSVM 是基于類屬特征的多標簽學習算法, 其中LIFT 通過特征映射來構建類屬特征; LLSF 和LLSF-BSVM 利用特征選擇得到類屬特征, 但前者直接基于權重矩陣使用線性回歸模型進行類別預測, 后者則利用權重矩陣選擇類屬特征后, 再利用分類器進行訓練和預測.

(3) LASSO、RFS、SFUS: 傳統的多標簽特征選擇算法, 即對所有類別采用相同特征子集進行分類. LASSO 是基于l1正則化的特征選擇方法; RFS 是通過最小化損失函數和正則化項的l2,1范數進行特征選擇; SFUS 則融合了稀疏特征選擇和計算共享特征子空間兩種思想.

本工作所提算法LSGL 不需要設置參數, 7 種對比算法涉及的參數均使用相應文獻中的建議參數. 此外, 除LLSF 算法外, 其余算法均使用二元支持向量機庫(library for binary support vector machines, LIBSVM)[24]作為基分類器, 采用線性核, 參數C=1.

2.2.2 評價指標

本工作采用5 種廣泛使用的多標簽學習評價指標來衡量算法性能.

假設測試數據集T={(xi,Yi)|1 ≤i≤t},C個二分類模型(f1,f2,··· ,fC). 算法對數據xi預測的標簽集合為Y′i, 則各評價指標的定義如下.

漢明損失(Hamming loss, HL): 考察樣本的標簽被誤分類的情況.

式中: Δ 表示兩個集合之間的對稱差.

1-錯誤率(one-error, OE): 考察樣本的預測標簽中排名最靠前的標簽不是相關標簽的情況.

對于任意π, 當π成立時, ?π?取值為1; 當π不成立時, ?π?取值為0. 覆蓋率(coverage, CV):考察在樣本的預測標簽排序中, 找到樣本的所有相關標簽所需步驟數.

式中:R(xi,lc)={lj|rank(xi,lj)≤rank(xi,lc),lj ∈Yi}.

以上5 種評價指標的取值范圍均為0～1. 平均精度指標取值越大, 則分類性能越好; 而其余4 個評價指標則相反.

2.3 實驗結果及分析

所有實驗均采用5 折交叉驗證, 取平均值作為每次實驗的結果. 需要指出的是, LLSFBSVM 算法無法指定類屬特征個數, 并且不同標簽的類屬特征個數也不同. 為方便比較, 本工作統計了LLSF-BSVM 算法在不同數據集上對不同類別標簽選取的平均類屬特征數, 將其作為LASSO、RFS、SFUS 這3 種傳統特征選擇算法的特征子集規模. 對于LSGL 算法,選擇的類屬特征個數與LLSF-BSVM 算法選擇的平均類屬特征個數保持一致. 表3 給出了LLSF-BSVM 算法在不同數據集上的平均類屬特征個數.

表3 LLSF-BSVM 算法得到的平均類屬特征個數Table 3 Average number of lable-specific features by LLSF-BSVM algorithm

表4～8 給出了包括本工作所提出算法在內的8 種算法分別在5 個數據集上的性能指標,其中↓(↑)表示該指標值越小(大), 分類性能越好, 指標值后括號中的數字表示每個算法在相應性能指標上的排名. 此外, “Rank”列表示算法在各評價指標上的平均排名, 值越小則性能越好.

表4 genbase 數據集的實驗結果Table 4 Results on genbase data set

表5 medical 數據集的實驗結果Table 5 Results on medical data set

表6 arts 數據集的實驗結果Table 6 Results on arts data set

表7 education 數據集的實驗結果Table 7 Results on education data set

表8 recreation 數據集的實驗結果Table 8 Results on recreation data set

從表4～8 的實驗結果可以看出, 本工作所提算法LSGL 取得了較好的分類性能. 觀察“Rank”列可以發現, LSGL 算法在所有數據集上取得了最高平均排名. 具體而言, 對于5 個數據集和5 種評價指標, 總共25 種情況下, LSGL 算法在其中的21 種情況排名第一, 4 種情況排名第二, 這充分說明了LSGL 算法在分類性能上的優越性. 根據不同數據集上的平均排名, 8 種算法的性能排序為LSGL＞LLSF-BSVM＞SFUS＞LIFT＞BR＞LLSF＞LASSO＞RFS.LIFT、LLSF-BSVM 和LSGL 使用了類屬特征, 因此整體排名要高于沒有使用類屬特征的算法BR、LASSO、RFS 和SFUS, 這說明在多標簽分類中引入類屬特征的必要性. 值得一提的是, 雖然LLSF 算法使用了類屬特征, 但分類性能較差, 原因可能是其他算法均使用SVM 作為基分類器, 而LLSF 算法直接使用線性回歸模型進行預測, 影響了分類精度. 在LIFT、LLSF-BSVM 和LSGL 這3 種算法中, LIFT 算法的排名遠低于另外兩種算法, 原因可能在于LIFT 算法通過特征映射來構建類屬特征, 從而損失了原始特征空間的一些有用信息.LLSF-BSVM 和LSGL 算法均是通過特征選擇來獲得類屬特征, 但后者性能更優, 說明基于圖拉普拉斯的特征評價準則能選擇出更具有判別力的特征.

圖1(a)～(e)以AP 指標為例, 給出了LSGL、LASSO、RFS 和SFUS 這4 種多標簽特征選擇算法的性能在不同特征子集規模下的變化情況, 其中BR 算法直接使用原始特征進行分類, 可作為比較基準. 表9 給出了各數據集的特征子集規模.

表9 選擇特征的個數Table 9 Number of selected features

圖1 在不同數據集上的特征選擇結果Fig.1 Results of feature selection on different data sets

從圖1(a)～(e)的實驗結果可以發現, 在不同的特征子集規模下, LSGL 算法都優于對比算法, 表現出了更優異的性能. 在genbase 數據集上, 當選擇10 個特征時, LSGL 算法的性能要明顯優于其他算法, 并且超過了BR 基準算法. 隨著選擇特征數增多, 其他算法的性能逐漸接近甚至超過了LSGL 算法, 但整體差距很小. 在medical 數據集上, LSGL 算法的性能始終優于其他算法, 尤其是選擇的特征數較少時差距較為明顯, 且始終高于Baseline, 表明類屬特征選擇能夠在選擇較少特征的同時取得更優異的性能. 在arts、education 和recreation 這3 個數據集上, 算法性能隨特征數變化的趨勢比較類似, 因此一并進行分析. 可以看到, LSGL 算法的性能曲線始終位于最上方, 且與其他算法保持著一定的距離, 而隨著特征數的增多, LSGL算法的性能也超越了Baseline.

3 結束語

與單標簽學習一樣, 多標簽學習同樣面臨著“維數災難”的問題, 使用特征選擇可以有效消除冗余信息. 另一方面, 對于每個標簽, 都具有最能反映其標簽特性的特征, 即類屬特征. 本工作提出的LSGL 算法, 通過對每個標簽構建樣本鄰接矩陣, 用拉普拉斯特征映射方法得到數據的低維嵌入, 再優化帶有稀疏正則項的目標函數, 求得從數據空間到嵌入空間的投影矩陣, 通過矩陣系數分析對特征重要度進行評分, 由此得到每個標簽的類屬特征. 在5 個公共多標簽數據集上的特征選擇和分類實驗表明, 相比7 種對比算法, LSGL 算法的性能優勢明顯.

LSGL 算法在進行類屬特征時沒有考慮標簽之間的相關性, 因此后續研究將關注如何在構建類屬特征的同時引入標簽相關性, 從而進一步提升分類性能.