唐 莉，王晨曦，胡敏杰，林耀進,2，鄭文彬

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

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

1 大間隔

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

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

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

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

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

RELIEF算法主要運用大間隔方法度量特征對樣本是否可分，即

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

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

2 基于樣本差異性的多標記特征選擇算法

2.1 采樣

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

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

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

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

2.2 樣本差異性

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

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

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

定義4對于整個標記空間L，樣本x在特征f下的分類間隔定義為

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

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

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

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

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

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

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

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

輸出：特征子集lable_featurespace

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

②for eachf∈F；

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

④end；

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

3 實驗設(shè)計

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

3.1 實驗數(shù)據(jù)

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

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

3.2 評價指標

實驗采用平均查準率（Average Precision，AP）、排序損失（Ranking Loss，RL）、漢明損失（Hamming Loss，HL）、覆蓋率（Coverage，CV）4個評價指標[17-18]驗證算法的有效性。令測試集：

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

實驗所用評價指標中，AP的值越高說明分類性能越優(yōu)，最優(yōu)為1；而RL、HL和CV等3種指標值越小說明分類性能越優(yōu)，最優(yōu)值為0。

3.3 實驗結(jié)果與分析

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

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

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

表2 各對比算法不同指標下的分類性能

續(xù)表2

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

為了更直觀地看出特征子集的個數(shù)與分類性能之間的關(guān)系，圖2～5分別表示在AP、HL、RL和CV這4種評價指標下，各算法的分類性能的變化趨勢?？梢园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基于樣本差異性的多標記特征選擇算法，在每個標記下反復(fù)計算特征空間中所有樣本的間隔，充分考慮了樣本的差異性對特征權(quán)重學習的影響。從樣本的分類間隔及樣本分類間隔數(shù)量出發(fā)定義了樣本的差異性，基于此，設(shè)計了一種前向啟發(fā)式的基于樣本差異性的多標記特征選擇算法。本文所提出的算法與對比算法用了相同的數(shù)據(jù)集以及評級指標，實驗顯示MFSD算法分類性能會更優(yōu)。