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

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

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

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

1 大間隔

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

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

當P=1時，Δ函數表示曼哈頓距離；當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]。另外，樣本之間標記的關聯性說明了多標記數據集特征并非所有樣本都具有同等重要性。因此，本節利用聚類技術對多標記數據集進行采樣，以組成新的多標記決策系統。具體來說，給定多標記數據集D={(xi,li)|1≤i≤n}，特征向量(xi1,xi2,…,xid)T構成了d維樣本xi，其中，樣本xi∈L的所具有的標記的集合用lk表示。對于標記lk∈L，具有類別標記的樣本和不具有類別標記的樣本構成的集合[16]可表示為

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

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

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

2.2 樣本差異性

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

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

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

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

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

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

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

定義7?x∈U,w為特征的權重向量，則特征子集的評價函數：

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

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

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

輸入：多標記數據集D

輸出：特征子集lable_featurespace

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

②for eachf∈F；

③根據（6）式計算每個特征的權重；

④end；

⑤按特征權重大小把排序好的特征值放在lable_featurespace。

3 實驗設計

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

3.1 實驗數據

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

表1 數據集的基本信息

3.2 評價指標

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

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

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

3.3 實驗結果與分析

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

根據表2的實驗結果可發現：

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

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

續表2

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

為了更直觀地看出特征子集的個數與分類性能之間的關系，圖2～5分別表示在AP、HL、RL和CV這4種評價指標下，各算法的分類性能的變化趨勢?？梢园l現，本文所提的MFSD算法優于其他的算法。

圖2 特征數目與AP的關系圖

圖3 特征數目與HL的關系圖

圖4 特征數目與RL的關系圖

圖5 特征數目與CV的關系圖

4 總結

本文提出了一種類似RELIEF基于樣本差異性的多標記特征選擇算法，在每個標記下反復計算特征空間中所有樣本的間隔，充分考慮了樣本的差異性對特征權重學習的影響。從樣本的分類間隔及樣本分類間隔數量出發定義了樣本的差異性，基于此，設計了一種前向啟發式的基于樣本差異性的多標記特征選擇算法。本文所提出的算法與對比算法用了相同的數據集以及評級指標，實驗顯示MFSD算法分類性能會更優。