唐 莉，王晨曦，胡敏杰，林耀進(jìn),2，鄭文彬

（1.閩南師范大學(xué)計(jì)算機(jī)學(xué)院，福建漳州363000；2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建漳州363000）

多標(biāo)記學(xué)習(xí)是模式識(shí)別和機(jī)器學(xué)習(xí)等研究領(lǐng)域的熱點(diǎn)問(wèn)題。多標(biāo)記學(xué)習(xí)框架中每個(gè)對(duì)象不再局限于單一類別標(biāo)記，而是可能同時(shí)用多個(gè)類別標(biāo)記來(lái)表征該對(duì)象的語(yǔ)義信息[1-3]。通常，多標(biāo)記數(shù)據(jù)集的高維性會(huì)嚴(yán)重干擾分類學(xué)習(xí)的過(guò)程[4]。特征選擇作為一種常見(jiàn)的降維技術(shù)，根據(jù)一定的評(píng)價(jià)準(zhǔn)則選擇一組能表征原始特征空間的過(guò)程。常見(jiàn)的評(píng)價(jià)準(zhǔn)則有信息度量[5-7]、一致性度量[8]、依賴性度量[9]和大間隔[10-13]等。目前，在單標(biāo)記決策系統(tǒng)中，利用樣本的分類間隔可以有效地度量特征的重要性。然而，在多標(biāo)記決策系統(tǒng)中，樣本在不同標(biāo)記下分組的不確定性導(dǎo)致僅用樣本分類間隔很難有效地度量特征的重要性，因?yàn)槟繕?biāo)樣本在不同類標(biāo)記下相應(yīng)的正負(fù)類近鄰樣本并不固定。因此，本文設(shè)計(jì)了一種基于樣本差異性的多標(biāo)記特征選擇算法。

1 大間隔

給定單標(biāo)記決策系統(tǒng)NDT=＜U,F,C＞，其中U={x1,x2,…,xn}是樣本集，F(xiàn)={f1,f2,…,fn}是一組用來(lái)表述樣本的屬性集合，C代表類別標(biāo)記。

定義1[14]U是一個(gè)非空的樣本集合空間，若?x1,x2,…,xn∈U有且僅有一個(gè)確定實(shí)函數(shù)Δ與之對(duì)應(yīng)，且Δ滿足：(1)Δ(xi,xj)≥ 0當(dāng)且僅當(dāng)xi=xj,Δ(xi,xj)=0；(2)Δ(xi,xj)= Δ(xj,xi)；(3)Δ(xi,xj)≤ Δ(xj,xi)，則稱＜U,Δ＞是度量空間。其中，Δ是用來(lái)度量樣本空間U上距離的函數(shù)。在m維空間中，任意兩點(diǎn)xi=(xi1,xi2,…,xin)和xj=(xj1,xj2,…,xjn)間的距離定義為閔科夫斯基距離：

當(dāng)P=1時(shí)，Δ函數(shù)表示曼哈頓距離；當(dāng)P=2時(shí)，Δ為歐式距離；當(dāng)P→∞，Δp(xi,xj)=|xli,xlj|。

定義2[15]樣本空間用U來(lái)表示，x表示樣本，則x的分類間隔為

其中，NH(x)和NM(x)分別表示在樣本空間U中距離x最近的具有相同類別標(biāo)記的樣本和不同類別標(biāo)記樣本。Δ[x ,NM(x)]和Δ[x ,NH(x)]分別表示樣本點(diǎn)x到NM(x)和NH(x)的距離，見(jiàn)圖1。

RELIEF算法主要運(yùn)用大間隔方法度量特征對(duì)樣本是否可分，即

其中，‖xi- NM(xi)‖-‖xi-NH(xi)‖表示樣本在第i個(gè)特征分量上間隔的2倍。

圖1 樣本x的分類間隔margin(x)

2 基于樣本差異性的多標(biāo)記特征選擇算法

2.1 采樣

在多標(biāo)記學(xué)習(xí)中，Zhang等指出樣本是否具有某個(gè)標(biāo)記受其類屬屬性決定[16]。另外，樣本之間標(biāo)記的關(guān)聯(lián)性說(shuō)明了多標(biāo)記數(shù)據(jù)集特征并非所有樣本都具有同等重要性。因此，本節(jié)利用聚類技術(shù)對(duì)多標(biāo)記數(shù)據(jù)集進(jìn)行采樣，以組成新的多標(biāo)記決策系統(tǒng)。具體來(lái)說(shuō)，給定多標(biāo)記數(shù)據(jù)集D={(xi,li)|1≤i≤n}，特征向量(xi1,xi2,…,xid)T構(gòu)成了d維樣本xi，其中，樣本xi∈L的所具有的標(biāo)記的集合用lk表示。對(duì)于標(biāo)記lk∈L，具有類別標(biāo)記的樣本和不具有類別標(biāo)記的樣本構(gòu)成的集合[16]可表示為

為了有效表征數(shù)據(jù)和分析樣本的內(nèi)在性質(zhì)，采用k-means對(duì)正負(fù)類樣本進(jìn)行聚類，將集合Pk的個(gè)聚類中心記為{,,…,}，集合Nk的個(gè)聚類中心記為{,,…,}。文獻(xiàn)[16]提出，對(duì)于可能存在正負(fù)類的樣本個(gè)數(shù)不均衡情況，將Pk和Nk的聚類個(gè)數(shù)置為等同，即mk==，即樣本集合在Pk和Nk上的聚類個(gè)數(shù)可設(shè)定為

其中，|·|表示返回集合的勢(shì)，r=[0,1]是限定聚類樣本的個(gè)數(shù)。

通過(guò)（3）式與（4）式，多標(biāo)記數(shù)據(jù)集D可轉(zhuǎn)換為由具有代表性的樣本組成的多標(biāo)記決策系統(tǒng)＜U,F,L＞，其中U={x1,x2,…,xn}表示樣本集，F(xiàn)={f1,f2,…,fm}是用于描述樣本的一組特征，L={l1,l2,…,lt}是一組標(biāo)記集合。

2.2 樣本差異性

根據(jù)（2）式可以度量單標(biāo)記決策系統(tǒng)中每個(gè)特征與標(biāo)記之間的相關(guān)性，權(quán)重越大說(shuō)明特征越能區(qū)分樣本的類別。在多標(biāo)記數(shù)據(jù)集中，樣本在標(biāo)記空間中的關(guān)系并不確定，即在某個(gè)標(biāo)記下為同類，但在另一個(gè)標(biāo)記下卻為異類。因此，在多標(biāo)記決策系統(tǒng)中僅從樣本間隔來(lái)度量特征的重要性具有一定局限性。

定義3給定多標(biāo)記決策系統(tǒng)＜U,F,L＞，對(duì)于?l∈L，則樣本x在特征f下的分類間隔為

根據(jù)RELIEF算法的思想，特征的權(quán)重可通過(guò)樣本的分類間隔進(jìn)行度量。通常特征對(duì)樣本的可分性越強(qiáng)，分類間隔會(huì)越大；否則，越小。當(dāng)mlf(x)＞0時(shí)，表示對(duì)于標(biāo)記l，樣本x到最近異類樣本的距離大于到最近同類樣本的距離，此時(shí)特征對(duì)樣本x是可分的；反之則表示特征對(duì)樣本x不可分。為了便于計(jì)算，將mlf(x)＜0設(shè)置為ml(x)=0。

定義4對(duì)于整個(gè)標(biāo)記空間L，樣本x在特征f下的分類間隔定義為

定義4反映了樣本在多標(biāo)記決策系統(tǒng)中某個(gè)特征空間下的分類間隔度量特征對(duì)樣本的區(qū)分能力。

定義5給定多標(biāo)記決策系統(tǒng)＜U,F,L＞，特征f∈F在樣本空間的分類間隔為(x)，則特征f在樣本空間中間隔大于零的樣本構(gòu)成的集合為={xi|(xi)＞0,xi∈U}，那么，分類間隔大于零的樣本數(shù)目為||。

定義6給定多標(biāo)記決策系統(tǒng)＜U,F,L＞，對(duì)于?x∈U，在特征f下，若(x)＞0且||＞0，則說(shuō)明樣本x是有差異性的樣本。

定義7?x∈U,w為特征的權(quán)重向量，則特征子集的評(píng)價(jià)函數(shù)：

定義8樣本x在特征f下的分類間隔度量特征的權(quán)重計(jì)算公式為

其中，df(xi,NMl(xi))代表在特征f和類標(biāo)簽l下，距離樣本xi最近且具有不同類標(biāo)簽的樣本，df(xi,NHl(xi))代表具有相同類標(biāo)簽的樣本的距離。本文將距離df(x,y)定義為

基于樣本差異性，由（6）式設(shè)計(jì)一種類似RELIEF的多標(biāo)記特征選擇算法（MFSD），具體描述如下：

輸入：多標(biāo)記數(shù)據(jù)集D

輸出：特征子集lable_featurespace

①根據(jù)（3）式與（4）式，獲得由具有代表性樣本組成的多標(biāo)記決策系統(tǒng)＜U,F,L＞；

②for eachf∈F；

③根據(jù)（6）式計(jì)算每個(gè)特征的權(quán)重；

④end；

⑤按特征權(quán)重大小把排序好的特征值放在lable_featurespace。

3 實(shí)驗(yàn)設(shè)計(jì)

為了證明本文算法的有效性，實(shí)驗(yàn)取MDDMspc[17]、MDDMproj[17]、RF_ML[11]、MLNB[18]和 FWLW[19]作為對(duì)比算法。用ML-KNN[20]的分類算法來(lái)對(duì)已經(jīng)進(jìn)行特征選擇后形成的新的數(shù)據(jù)集進(jìn)行評(píng)價(jià)，其中ML-KNN設(shè)定為默認(rèn)參數(shù)值，平滑參數(shù)s=1，近鄰k=10。

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)從Mula(http：//mulan.sourceforge.net/datasets.Html)中選取了4個(gè)多標(biāo)記數(shù)據(jù)集，表1刻畫了數(shù)據(jù)相關(guān)信息。

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

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用平均查準(zhǔn)率（Average Precision，AP）、排序損失（Ranking Loss，RL）、漢明損失（Hamming Loss，HL）、覆蓋率（Coverage，CV）4個(gè)評(píng)價(jià)指標(biāo)[17-18]驗(yàn)證算法的有效性。令測(cè)試集：

Z={(xi,Yi)}?Rd×{+1,-1}L，根據(jù)預(yù)測(cè)函數(shù)fl(x)可定義排序函數(shù)為rankf(x,l)∈{1,2,…,L}。

實(shí)驗(yàn)所用評(píng)價(jià)指標(biāo)中，AP的值越高說(shuō)明分類性能越優(yōu)，最優(yōu)為1；而RL、HL和CV等3種指標(biāo)值越小說(shuō)明分類性能越優(yōu)，最優(yōu)值為0。

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

下面從兩個(gè)方面來(lái)驗(yàn)證MFSD算法的有效性：第一，與已經(jīng)提出的算法在特征子集的個(gè)數(shù)以及分類性能兩方面作比較；第二，觀察特征子集的數(shù)目與分類性能之間的關(guān)系。本文采用的對(duì)比算法為MDDMspc、MDDMproj、RF_ML和FWLW，且對(duì)比算法均得到一組特征排序，本文將選擇排序前k個(gè)特征作為最終的特征，并將k設(shè)置為與MLNB最終選擇特征相同的數(shù)目。表2給出了各算法在不同評(píng)價(jià)指標(biāo)下的實(shí)驗(yàn)結(jié)果。表中Original列的數(shù)值表示未做選擇的特征的分類性能；數(shù)值后的符號(hào)“↑”表示分類性能與數(shù)值的大小成正比；符號(hào)“↓”表示二者成反比；數(shù)值后的符號(hào)“√”在相應(yīng)指標(biāo)下該算法誘發(fā)的分類性能優(yōu)于初始特征；斜體表示各算法與相應(yīng)的指標(biāo)下的分類性能平均值，加粗表示所有值中的最優(yōu)。

根據(jù)表2的實(shí)驗(yàn)結(jié)果可發(fā)現(xiàn)：

（1）表2分別統(tǒng)計(jì)了MDDMspc、MDDMproj、RF_ML、MLNB、MFSD和FWLW算法在4個(gè)數(shù)據(jù)集、4個(gè)評(píng)價(jià)指標(biāo)上的16個(gè)結(jié)果。與各算法進(jìn)行對(duì)比，結(jié)果顯示本文提出的算法具有更好的性能。

表2 各對(duì)比算法不同指標(biāo)下的分類性能

續(xù)表2

（2）從平均分類精度上來(lái)看，MFSD在4種評(píng)價(jià)準(zhǔn)則中獲得的平均分類性能極其明顯地優(yōu)于其他5種對(duì)比算法和原始分類性能，這更加充分地說(shuō)明了本文算法的有效性。

為了更直觀地看出特征子集的個(gè)數(shù)與分類性能之間的關(guān)系，圖2～5分別表示在AP、HL、RL和CV這4種評(píng)價(jià)指標(biāo)下，各算法的分類性能的變化趨勢(shì)?？梢园l(fā)現(xiàn)，本文所提的MFSD算法優(yōu)于其他的算法。

圖2 特征數(shù)目與AP的關(guān)系圖

圖3 特征數(shù)目與HL的關(guān)系圖

圖4 特征數(shù)目與RL的關(guān)系圖

圖5 特征數(shù)目與CV的關(guān)系圖

4 總結(jié)

本文提出了一種類似RELIEF基于樣本差異性的多標(biāo)記特征選擇算法，在每個(gè)標(biāo)記下反復(fù)計(jì)算特征空間中所有樣本的間隔，充分考慮了樣本的差異性對(duì)特征權(quán)重學(xué)習(xí)的影響。從樣本的分類間隔及樣本分類間隔數(shù)量出發(fā)定義了樣本的差異性，基于此，設(shè)計(jì)了一種前向啟發(fā)式的基于樣本差異性的多標(biāo)記特征選擇算法。本文所提出的算法與對(duì)比算法用了相同的數(shù)據(jù)集以及評(píng)級(jí)指標(biāo)，實(shí)驗(yàn)顯示MFSD算法分類性能會(huì)更優(yōu)。