吳 君, 黃 睿

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

在傳統(tǒng)的單標(biāo)簽學(xué)習(xí)框架中, 每個樣本只對應(yīng)一種標(biāo)簽. 然而, 在現(xiàn)實(shí)生活中, 大部分對象都表現(xiàn)為多語義性[1-2], 即一個樣本同時對應(yīng)多種標(biāo)簽. 因此, 多標(biāo)簽學(xué)習(xí)模型更具實(shí)際應(yīng)用價值, 已經(jīng)在圖像標(biāo)注[3]、文本分類[4]、音樂情感分類[5]等領(lǐng)域獲得應(yīng)用.

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

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

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

1 LSGL 算法

1.1 構(gòu)建低維嵌入

設(shè)由N個樣本構(gòu)成的數(shù)據(jù)集為X= [x1,x2,··· ,xN]∈RD×N, 標(biāo)簽集合為L={l1,l2,··· ,lC}, 數(shù)據(jù)集對應(yīng)的邏輯型類別標(biāo)簽集為Y= [y1,y2,··· ,yN]T∈{0,1}N×C,C為類別標(biāo)簽個數(shù).xn ∈RD對應(yīng)的標(biāo)簽為yn= [yn1,yn2,··· ,ynC]∈{0,1}C, 1 表示樣本與標(biāo)簽相關(guān), 0 表示樣本與標(biāo)簽無關(guān).

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

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

取前K個最小特征值對應(yīng)的特征向量構(gòu)成原始數(shù)據(jù)對于標(biāo)簽lc的低維嵌入[20],

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

1.2 稀疏特征選擇

對于標(biāo)簽lc, 從數(shù)據(jù)空間到流形空間的投影矩陣Wc=[w1,w2]可通過優(yōu)化以下目標(biāo)函數(shù)獲得,

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

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

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

對每個標(biāo)簽計算投影矩陣, 可獲得相應(yīng)的類屬特征, 再利用類屬特征對每個標(biāo)簽構(gòu)建二分類器進(jìn)行訓(xùn)練和預(yù)測. LSGL 算法的完整流程如表1 所示.

表1 LSGL 算法Table 1 LSGL algorithm

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

2.1 數(shù)據(jù)集

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

表2 數(shù)據(jù)集信息Table 2 Data information

2.2 實(shí)驗(yàn)設(shè)置

本工作選取7 個多標(biāo)簽學(xué)習(xí)算法作為對比算法, 并利用5 種評價指標(biāo)衡量不同算法的性能.

2.2.1 對比算法

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

(1) BR: 基于特征全集, 將多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)換為多個二分類問題進(jìn)行分類, 實(shí)驗(yàn)結(jié)果可作為比較基準(zhǔn).

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

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

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

2.2.2 評價指標(biāo)

本工作采用5 種廣泛使用的多標(biāo)簽學(xué)習(xí)評價指標(biāo)來衡量算法性能.

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

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

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

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

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

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

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

2.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

表4 genbase 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Table 4 Results on genbase data set

表5 medical 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Table 5 Results on medical data set

表6 arts 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Table 6 Results on arts data set

表7 education 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Table 7 Results on education data set

表8 recreation 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Table 8 Results on recreation data set

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

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

表9 選擇特征的個數(shù)Table 9 Number of selected features

圖1 在不同數(shù)據(jù)集上的特征選擇結(jié)果Fig.1 Results of feature selection on different data sets

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

3 結(jié)束語

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

LSGL 算法在進(jìn)行類屬特征時沒有考慮標(biāo)簽之間的相關(guān)性, 因此后續(xù)研究將關(guān)注如何在構(gòu)建類屬特征的同時引入標(biāo)簽相關(guān)性, 從而進(jìn)一步提升分類性能.