吳喆君，黃 睿

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

0 引 言

“維數(shù)災(zāi)難”是多標(biāo)簽學(xué)習(xí)面臨的挑戰(zhàn)之一[1-7]。通過特征選擇對(duì)高維數(shù)據(jù)進(jìn)行維數(shù)約簡是克服該問題的有效手段[8-10]?；谙∈杌貧w的多標(biāo)簽特征選擇算法利用優(yōu)化得到的回歸矩陣進(jìn)行特征選擇[11-14]。Ma等提出利用稀疏性來構(gòu)建子空間(sub-feature uncovering with sparsity，SFUS)的多標(biāo)簽特征選擇算法[12]，通過聯(lián)合稀疏特征選擇與多標(biāo)簽學(xué)習(xí)來獲得特征的共享子空間。文獻(xiàn)[13]提出非負(fù)稀疏表示的多標(biāo)簽特征選擇方法(multi-label feature selection based non-negative sparse representation，MNMFS)，融合了非負(fù)約束問題和l2,1范數(shù)最小優(yōu)化問題。Zhang等提出一種基于流形正則化的多標(biāo)簽特征選擇方法(manifold regularized discriminative feature selection for multi-label lear-ning，MDFS)[14]，將數(shù)據(jù)空間和標(biāo)簽空間的流形正則化引入稀疏回歸模型。

當(dāng)前，多數(shù)基于稀疏回歸的多標(biāo)簽特征選擇算法認(rèn)為數(shù)據(jù)的特征空間和標(biāo)簽空間之間存在線性關(guān)系，在回歸模型中直接將數(shù)據(jù)從特征空間映射到標(biāo)簽空間。然而大部分情況下兩者之間的線性關(guān)系并不成立。文獻(xiàn)[15]通過依賴最大化對(duì)多標(biāo)簽數(shù)據(jù)進(jìn)行特征提取。受此啟發(fā)，本文提出一種基于依賴最大化和稀疏回歸的多標(biāo)簽特征選擇算法(multi-label feature selection with dependence maximization and sparse regression，DMSR)。該方法通過最大化投影子空間與標(biāo)簽空間之間的依賴性來構(gòu)建數(shù)據(jù)的低維空間，利用希爾伯特-施密特獨(dú)立性準(zhǔn)則[15]來衡量兩者之間的依賴性，然后把該低維空間引入稀疏回歸模型中，將數(shù)據(jù)從特征空間映射到低維空間。相比于呈現(xiàn)稀疏性、二值性的標(biāo)簽空間，該低維空間包含了更豐富的信息。結(jié)合l2,1正則化得到目標(biāo)函數(shù)，利用交替優(yōu)化的方式進(jìn)行求解，得到用于特征選擇的回歸系數(shù)矩陣。

1 本文算法

1.1 目標(biāo)函數(shù)

假設(shè)有多標(biāo)簽數(shù)據(jù)集X=[x1,x2,…,xN]T∈RN×d，N是數(shù)據(jù)個(gè)數(shù)，d是特征個(gè)數(shù)，其中每個(gè)數(shù)據(jù)樣本為xi=[xi1,xi2,…,xid]， 標(biāo)簽集合為L={l1,l2,…,lC}，C是總共的類別標(biāo)簽個(gè)數(shù)，數(shù)據(jù)集對(duì)應(yīng)的標(biāo)簽為Y=[y1,y2,…,yN]T∈{0,1}N×C，xi的標(biāo)簽為yi=[yi1,yi2,…,yiC]， 如果xi含有標(biāo)簽lj，則yij=1， 否則yij=0。 令I(lǐng)表示單位矩陣，e表示全為1的向量。

所提算法DMSR源自稀疏回歸模型，使用最小平方損失作為損失函數(shù)的稀疏回歸模型的目標(biāo)函數(shù)一般有如下形式

(1)

式(1)的目標(biāo)函數(shù)直接將數(shù)據(jù)從原始特征空間映射到標(biāo)簽空間，但是特征空間和標(biāo)簽空間之間往往不存在線性關(guān)系，因此我們希望構(gòu)建一個(gè)數(shù)據(jù)的m維子空間V=[v1,v2,…,vN]T∈RN×m， 把數(shù)據(jù)從原始特征空間映射到該低維子空間。受文獻(xiàn)[15]的啟發(fā)，DMSR最大化低維空間V和標(biāo)簽空間Y之間的依賴性，使用希爾伯特-施密特獨(dú)立性準(zhǔn)則(Hilbert-Schmidt independence criterion，HSIC)計(jì)算兩者之間的依賴性，其定義如下

HSIC(V,Y)=(N-1)-2Tr(HK1HK2)

(2)

(3)

同時(shí)，對(duì)低維空間V的每個(gè)維度之間進(jìn)行正交約束，用V代替式(1)中的標(biāo)簽空間Y， 再結(jié)合式(3)，則目標(biāo)函數(shù)轉(zhuǎn)變?yōu)?/p>

(4)

其中，α和β為平衡參數(shù)。關(guān)于正則項(xiàng)R(W)， 這里采用l2,1正則化來保證稀疏性和減少離群點(diǎn)的影響[7,12]，即令R(W) 等于W的l2,1范數(shù)，從而得到最終的目標(biāo)函數(shù)

(5)

1.2 優(yōu)化求解

(6)

式(6)對(duì)W求導(dǎo)，并且令導(dǎo)數(shù)為零，可以得到

2XT(XW-V)+2βQW=0

(7)

解得

W=(XTX+βQ)-1XTV

(8)

把式(8)代入式(6)中的優(yōu)化項(xiàng)，可以得到

(9)

其中，A=XTX+βQ， 從而得到如下只含有一個(gè)優(yōu)化變量V的目標(biāo)函數(shù)

(10)

該優(yōu)化問題可以通過對(duì)矩陣I-αHYYTH-XA-1XT進(jìn)行特征分解來進(jìn)行求解，取前m個(gè)最小特征值對(duì)應(yīng)的特征向量構(gòu)成V。

算法1：DMSR算法

輸入：數(shù)據(jù)集X∈RN×d， 標(biāo)簽Y∈{0,1}N×C， 平衡參數(shù)α，β， 低維空間的維數(shù)m。

輸出：特征排序。

(1) 初始化Q為單位矩陣Id×d；

(2) 迭代

(3) 求解式(10)得到V；

(4) 根據(jù)式(8)更新W；

(5) 根據(jù)W每一行的值更新Q；

(6) 直至收斂；

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

本文將所提算法DMSR與其它4種多標(biāo)簽特征選擇算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明所提算法能夠取得較好的性能。

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

為驗(yàn)證所提算法性能，在Emotions、Birds、Enron、Image、Scene和Yeast等6個(gè)多標(biāo)簽數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。這些數(shù)據(jù)集都可以從互聯(lián)網(wǎng)上獲得，涵蓋了音頻、音樂、圖片、生物、文本等多種類型。表1列出了數(shù)據(jù)集的詳細(xì)信息，包括樣本數(shù)、特征數(shù)、標(biāo)簽數(shù)、所屬領(lǐng)域以及URL鏈接。

表1 數(shù)據(jù)集信息

本文使用5種常用的評(píng)價(jià)指標(biāo)來評(píng)估所提算法的性能，分別是漢明損失、排序損失、覆蓋率、1-錯(cuò)誤率和平均精度[7,14]。假設(shè)T={(xi,yi)|1≤i≤p} 表示含有p個(gè)數(shù)據(jù)樣本的測試數(shù)據(jù)集以及其對(duì)應(yīng)的標(biāo)簽，某種算法對(duì)樣本xi的預(yù)測標(biāo)簽為y′i，fk(xi)(1≤k≤C,1≤i≤p) 表示分類器輸出的樣本xi在第k個(gè)標(biāo)簽上的分值，各評(píng)價(jià)指標(biāo)的含義和定義如下：

漢明損失(Hamming loss，HL)：考察數(shù)據(jù)樣本被錯(cuò)誤分類的情況，即分類器沒有預(yù)測相關(guān)的標(biāo)簽或者預(yù)測了不相關(guān)的標(biāo)簽

(11)

其中，Δ表示兩個(gè)集合之間的對(duì)稱差。

1-錯(cuò)誤率(one-error，OE)：考察分類器輸出分值最高的標(biāo)簽不屬于數(shù)據(jù)實(shí)際標(biāo)簽的次數(shù)

(12)

覆蓋率(coverage，CV)：考察在分類器給出的標(biāo)簽排序中，覆蓋樣本所有實(shí)際標(biāo)簽所需的平均標(biāo)簽個(gè)數(shù)

(13)

排序損失(ranking loss，RL)：考察出現(xiàn)排名顛倒的標(biāo)簽對(duì)的情況，即不相關(guān)標(biāo)簽的排名高于相關(guān)標(biāo)簽的排名

(14)

平均精度(average precision，AP)：考察排名高于某個(gè)特定相關(guān)標(biāo)簽的相關(guān)標(biāo)簽的平均個(gè)數(shù)

(15)

這5種評(píng)價(jià)指標(biāo)的取值范圍均為0到1，漢明損失、1-錯(cuò)誤率、覆蓋率和排序損失取值越小，算法性能越好，平均精度則相反。

實(shí)驗(yàn)采用如下4種多標(biāo)簽特征選擇算法作為對(duì)比算法：

MDMR[8]：利用最大化依賴和最小化冗余(max-dependency and min-redundancy)實(shí)現(xiàn)多標(biāo)簽特征選擇。

GMBA[9]：基于圖邊界的多標(biāo)簽特征選擇算法(graph-margin based multi-label feature selection)，利用大邊界理論來衡量特征的重要程度。

SFUS[12]：通過聯(lián)合稀疏特征選擇與多標(biāo)簽學(xué)習(xí)來獲得特征的共享子空間，并且將子空間引入稀疏回歸模型，完成特征選擇。

MDFS[14]：基于流形正則化的多標(biāo)簽特征選擇算法，在優(yōu)化模型中加入了數(shù)據(jù)空間和標(biāo)簽空間的流形正則化項(xiàng)。

2.2 實(shí)驗(yàn)結(jié)果與分析

圖1(a)～圖1(f)分別給出了在6個(gè)數(shù)據(jù)集上，不同算法的平均精度指標(biāo)隨選擇特征個(gè)數(shù)改變的變化情況，其中，橫坐標(biāo)軸表示選擇的特征個(gè)數(shù)，縱坐標(biāo)軸表示平均精度。除了上述提到的4種對(duì)比算法，我們還采用了全特征進(jìn)行實(shí)驗(yàn)，將其結(jié)果作為比較基準(zhǔn)，記為Baseline。從圖中可以看出，隨著選擇特征個(gè)數(shù)的增加，各個(gè)算法的性能先逐步提升，然后趨于平緩，一些算法的性能還出現(xiàn)了下降，而DMSR算法的性能超過了Baseline，這表明DMSR能夠選擇優(yōu)秀的特征，提升分類器的性能。與其它對(duì)比算法相比，DMSR在大多數(shù)情況下表現(xiàn)出更優(yōu)異的性能。在Emotions、Yeast和Image數(shù)據(jù)集上，選擇特征的個(gè)數(shù)變化時(shí)，DMSR的性能始終能夠高于其它算法，在Birds、Scene和Enron數(shù)據(jù)集上，雖然DMSR沒有在所有情況中均領(lǐng)先其它算法，但是其性能一直排名前3。

圖1 不同數(shù)據(jù)集上算法的性能

此外，為了對(duì)算法性能做進(jìn)一步的定量分析，我們?cè)诿總€(gè)數(shù)據(jù)集上利用各個(gè)算法選擇最重要的30個(gè)特征進(jìn)行實(shí)驗(yàn)。表2～表6列出了在5種評(píng)價(jià)指標(biāo)上的實(shí)驗(yàn)結(jié)果，各表中的最后一行“AvgRank”表示每個(gè)算法在不同數(shù)據(jù)集上的平均排名，不同算法中最優(yōu)的結(jié)果加粗表示，↓表示評(píng)價(jià)指標(biāo)越小，性能越好，↑表示評(píng)價(jià)指標(biāo)越大，性能越好。從表中可以看出，由于實(shí)驗(yàn)采用了5種評(píng)價(jià)指標(biāo)和6種數(shù)據(jù)集，因此總共有30種比較情況，DMSR算法在其中的24種情況排名第一，6次排名第二，盡管在個(gè)別情況下DMSR的性能不如MDFS和SFUS，但整體上看DMSR仍然優(yōu)于其它對(duì)比算法。綜合分析各個(gè)算法在5種評(píng)價(jià)指標(biāo)上的平均排名，我們可以得到各個(gè)算法的性能排序：DMSR>MDFS>SFUS>MDMR>GMBA。DMSR、MDFS和SFUS都是基于稀疏回歸的多標(biāo)簽特征選擇算法，而MDMR和GMBA是過濾式多標(biāo)簽特征選擇算法，這驗(yàn)證了利用稀疏回歸模型進(jìn)行特征選擇的有效性。在大多數(shù)情況下DMSR的性能要優(yōu)于MDFS和SFUS，這說明基于HSIC構(gòu)建數(shù)據(jù)的低維空間并將其引入回歸模型，能夠選擇出更具有判別力的特征，從而有效提升多標(biāo)簽分類器的性能。

表2 不同算法的漢明損失(↓)

表3 不同算法的排序損失(↓)

表4 不同算法的覆蓋率(↓)

表5 不同算法的1-錯(cuò)誤率(↓)

表5(續(xù))

表6 不同算法的平均精度(↑)

3 結(jié)束語

多標(biāo)簽學(xué)習(xí)面臨“維數(shù)災(zāi)難”的問題，利用稀疏回歸模型的多標(biāo)簽特征選擇方法能夠有效去除冗余特征，提升算法性能，但是回歸模型中數(shù)據(jù)的特征空間和標(biāo)簽空間之間通常不存在線性關(guān)系。本文提出一種基于依賴最大化和稀疏回歸的多標(biāo)簽特征選擇算法DMSR，首先構(gòu)建數(shù)據(jù)的低維空間，最大化低維空間和標(biāo)簽空間之間的依賴性，該依賴性使用希爾伯特-施密特獨(dú)立性準(zhǔn)則來衡量，然后將低維空間加入含有l(wèi)2,1正則項(xiàng)的回歸模型，最后設(shè)計(jì)了一種交替優(yōu)化的方法進(jìn)行求解，利用得到的回歸系數(shù)矩陣選擇特征。在6個(gè)公共多標(biāo)簽數(shù)據(jù)集上的特征選擇與分類實(shí)驗(yàn)結(jié)果表明所提算法DMSR的性能優(yōu)于其它對(duì)比算法。

DMSR算法沒有考慮標(biāo)簽相關(guān)性，后續(xù)的研究工作將關(guān)注如何將標(biāo)簽相關(guān)性引入回歸模型，從而進(jìn)一步提高算法性能。