擴展ReliefF的兩種多標簽特征選擇算法

馬晶瑩 宣恒農(nóng)

(南京財經(jīng)大學(xué)信息工程學(xué)院 江蘇 南京 210000)

?

擴展ReliefF的兩種多標簽特征選擇算法

馬晶瑩 宣恒農(nóng)

(南京財經(jīng)大學(xué)信息工程學(xué)院 江蘇 南京 210000)

針對ReliefF算法局限于單標簽數(shù)據(jù)問題，提出兩種多標簽特征選擇算法Mult-ReliefF和M-A算法。Mult-ReliefF算法重新定義了類內(nèi)最近鄰和類外最近鄰的查找方法，并加入標簽的貢獻值更新特征權(quán)重公式。M-A算法在Mult-ReliefF算法的基礎(chǔ)下，利用鄰域能去除冗余的特性，更多地去除冗余特征達到更好的降維效果。采用ML-KNN分類算法進行實驗。在多個數(shù)據(jù)集上測試表明，Mult-ReliefF算法能提高分類效果，M-A算法能獲得最小的特征子集。

多標簽分類 特征選擇 數(shù)據(jù)降維 ReliefF 鄰域粗糙集

0 引 言

在傳統(tǒng)的分類任務(wù)中，每個樣本僅有一個類別標簽。然而在許多現(xiàn)實問題中，一個對象能夠同時被多個標簽標記，這稱為多標簽分類[1]。比如說一幅圖片可以同時標記為“藍天”和“大海”；一部電影同時分類為“動作片”和“喜劇片”；一位病人被診斷患有多種疾病等。多標簽分類技術(shù)近年來備受關(guān)注，并且被不斷應(yīng)用到多個領(lǐng)域中如多媒體內(nèi)容的自動標注[2]、生物信息[3]、Web挖掘[4]、信息檢索[5]和個性化推薦[6]等。在多標簽分類中，樣本是由高維數(shù)據(jù)描述的，描述樣本的特征數(shù)量一般較多，其中存在大量冗余和不相關(guān)的特征，這會使得后繼分類工作難度增加。特征選擇是指從原始特征集中，選出能使某種評價標準最優(yōu)的特征子集。在分類任務(wù)前，對特征集約簡，能夠有效減少描述樣本的特征個數(shù)，縮短運行時間，提高分類精度。

文獻[7]在粗糙集理論基礎(chǔ)上，利用鄰域粗糙集的下近似和依賴度，設(shè)計適合多標簽數(shù)據(jù)的特征選擇算法，并驗證算法的有效性。但是該算法沒有考慮標簽之間的相關(guān)性并且不適用高維稀疏數(shù)據(jù)。文獻[8]將遺傳算法和主成分分析法結(jié)合，同時應(yīng)用貝葉斯分類器的方法完成特征提取。但是由于使用的主成分分析法只能用于特征值連續(xù)的數(shù)據(jù)，所以導(dǎo)致該方法有一定的局限性。文獻[9]通過子空間降維和映射降維兩種映射策略來定義一個低維特征空間，這種映射仍然采用核矩陣。文獻[10]使用特征和標簽之間的信息增益刪除不相關(guān)的特征，達到降維的目的，但忽略了特征之間的相關(guān)性。

ReliefF[11-12]是一個經(jīng)典的特征選擇算法，利用特征與類別之間的相關(guān)性大小來評判特征好壞，好的特征能使同類樣本靠近，異類樣本遠離。但是它沒有考慮到標簽共現(xiàn)的情況，所以只適用于單標簽數(shù)據(jù)。本文算法擴展ReliefF算法，重新定義最近鄰樣本，加入標簽對特征的貢獻值，實現(xiàn)了多標簽分類任務(wù)的特征選擇，并通過實驗驗證該算法的有效性。ReliefF算法通過特征權(quán)值的排序選擇前k個，不能去除冗余的特征，因此擴展的算法也有這一不足。結(jié)合文獻[7]考慮到粗糙集能通過刪除冗余條件屬性來實現(xiàn)屬性約簡，進行二層特征約簡，實驗表明能更好地降低特征維度。

1 多標簽的特征選擇算法

1.1 單標簽ReliefF特征選擇算法

Kira和Rendell在1992年提出的Relief算法只適用于兩類數(shù)據(jù)的特征選擇，而實際應(yīng)用中多類問題存在更多。隨后兩年，Kononenko在Kira工作的基礎(chǔ)上提出了ReliefF算法解決了多類問題。ReliefF算法的基本思想：在訓(xùn)練集中選取m個隨機樣本，對每個樣本找到它的k個類內(nèi)最近鄰(Hit)和類外最近鄰(Miss)，求出樣本各特征與類別的相關(guān)性，求平均得到各特征的權(quán)重。將特征的權(quán)重排序，根據(jù)設(shè)定的閾值來選擇有效特征。

記訓(xùn)練樣本集U={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈Rn是樣本的屬性空間，p為樣本屬性個數(shù)；yi∈RL為樣本類別空間，L為所給單標簽數(shù)據(jù)集的類別個數(shù)。

在樣本空間中:

每個樣本的類別標簽滿足:

(1)

每一個樣本只能被一個標簽標記，所以ReliefF算法只適用于單標簽數(shù)據(jù)。

算法1 ReliefF算法

輸入：訓(xùn)練數(shù)據(jù)集U，迭代次數(shù)m，最近鄰樣本個數(shù)k

輸出：特征權(quán)重向量W

(1) 初始化W(1:p)=0.0;

(2) fori=1∶m

(3) 從U中隨機選擇一個樣本記Ri;

(4) 找到與樣本Ri同類的k個最近鄰Hj;

(5) for eachC≠Class(Ri)

(6) 找Ri不同類的k個最近鄰Mj(C);

(7) fora=1∶p

(9) end

(10) end

(11) end

Hj表示與樣本Ri同類的第j個樣本，Class(Ri)表示樣本Ri所包含的類別標簽，d(a,x1,x2)表示樣本x1和x2關(guān)于特征a的距離，P(C)表示類別C的概率，Mj(C)表示類別C的第j個樣本。最終得到所有特征的權(quán)值，權(quán)值越大表示該特征對樣本的區(qū)分能力越強，設(shè)定閾值選擇符合條件的特征從而達到降維的目的。

在這里Class(Ri)只包含一個標簽，從算法1的(4)、(6)中可以看出尋找的最近鄰是以某個樣本屬于某一類為前提的，沒有考慮樣本同時擁有多個標簽的情況。所以ReliefF算法只針對單標簽數(shù)據(jù)，而當Class(Ri)是一個標簽集合時不再適用，對于多標簽數(shù)據(jù)的特征選擇問題需要進一步研究。

1.2Mult-ReliefF特征選擇算法

現(xiàn)實中大多數(shù)據(jù)并不能清晰地劃分為多個不相交的類別，每一個數(shù)據(jù)樣本均可能同時屬于多個類別。若在多標簽中能很好地找到隨機樣本的最近鄰那么ReliefF算法也能用于多標簽數(shù)據(jù)。基于此本文提出了Mult-ReliefF算法解決查找最近鄰問題，并且考慮每個標簽對屬性的貢獻值，更新權(quán)值公式。

一個樣本R可以被一個或一個以上標簽標記，將樣本R的標簽看作一個集合LR，全部樣本空間看作全集L，那么樣本標簽的補集CLLR就被定義為樣本R的不同標簽集。記L(x)表示為樣本x的標簽集合，那么定義同類樣本滿足,非同類樣本，相關(guān)模糊樣本。

又在多標簽數(shù)據(jù)中，每個樣本的標簽滿足：

{x|L(x)∩LR≠?∧L(x)∪LR=LR},非同類樣本

{x|L(x)∩LR≠?},相關(guān)模糊樣本

{x|L(x)∩LR≠?∧L(x)∪LR?LR}。

又在多標簽數(shù)據(jù)中，每個樣本的標簽滿足：

(2)

所以不考慮L(x)為空集的可能。

對隨機選擇的樣本R，若查找不到k個近鄰，則重新選擇隨機樣本。根據(jù)新的類內(nèi)最近鄰樣本和類外最近鄰樣本的定義，可以很好地解決ReliefF算法不能處理樣本類別共現(xiàn)問題。在迭代更新權(quán)值時，將標簽的貢獻值加入到公式中，改進特征權(quán)值的更新公式更好地調(diào)節(jié)權(quán)重分配。

算法2 Mult-ReliefF特征選擇算法

輸入：樣本的特征矩陣X，樣本的標簽矩陣Y，迭代次數(shù)m，近鄰樣本個數(shù)K

輸出：特征的權(quán)值向量W

(1) 初始化W(1∶p)=0.0;

(2) fori=1∶m

(3) 從U中隨機選擇一個樣本記Rj;

(4) 找到與樣本Ri標簽集合LR;

(5) for each Class(Ri)?LR

(6) 找Ri同類的k個最近鄰Hj(Class(Ri));

(7) for eachC?CLLR

(8) 找Ri不同類的k個最近鄰Mj(C);

(9) fora=1∶p

(11) end

(12) end

(13) end

(14) end

Class(Ri)是LR的一個非空子集，有(2|LR|-1)種情況。與算法1不同的是這里C和Class(Ri)表示一個非空集合，它們含有的元素個數(shù)可以是一個，也可以是多個，其他符號說明同算法1。如果樣本Ri和同類樣本關(guān)于特征a的距離不相同，則特征a就把兩個同類的樣本區(qū)分開了，故要減去d(a,Ri,Hj)。相反，如果樣本Ri和不同類樣本關(guān)于特征a的距離不相同，則特征a就把兩個不同類的樣本區(qū)分開了，正是我們想要的，故要加上d(a,Ri,Mj)，特征權(quán)重公式中求的是均值化差異。原來的權(quán)重公式中沒有考慮標簽對權(quán)重的貢獻值，加入標簽貢獻值參數(shù)μi，考慮樣本Ri的標簽占標簽空間的比重，對多標簽數(shù)據(jù)給予重視，實驗證明算法的有效性。

2 二層特征約簡

特征選擇的目的就是在保證分類效果的前提下，獲得一個較少元素的最優(yōu)特征子集。我們通過Mult-ReliefF算法獲得一個特征的權(quán)重向量，特征的權(quán)值越大表示該特征區(qū)分樣本的能力越強。從后面實驗部分可以看出在算法2中，按照比例選擇靠前的特征，分類的效果會隨著選取特征比例的變化而變化，并且在多個數(shù)據(jù)集上的實驗表明選取前80%能較好地提高分類精度。此時獲得的特征個數(shù)只是相比原來有所減少，但對于特征基數(shù)大的，選取的特征子集的個數(shù)仍然較大。比如說一個樣本有1 000個特征，按照比例選取前80%依然留有800個特征，這時特征維度還是較大的。特征排序只能遠離區(qū)分樣本能力弱的特征，無法去除冗余的特征，這里冗余特征是指該特征所包含的分類信息已經(jīng)包含于其他特征中了。根據(jù)這一不足，又提出一種二層約簡M-A算法。

粗糙集理論[13]可以通過刪除冗余屬性來實現(xiàn)約簡，為了更好地去除冗余特征，利用鄰域區(qū)分樣本的能力[7]，對算法2選取的特征子集，進一步約簡去冗余。

在一個多標簽鄰域決策系統(tǒng)中，樣本集合U={x1,x2,…,xn}，描述樣本的屬性集A={a1,a2,…,aN}，標簽集L={l1,l2,…,lm}。Xj?U表示具有類別標簽lj的樣本集合，B?A表示約簡后的屬性集合，B生成U上的鄰域關(guān)系為NB。

定義1x∈U的δ鄰域為:

(3)

〈U,Δ〉是非度量空間。

定義2 集合L關(guān)于鄰域關(guān)系NB的下近似為:

(4)

定義3 多標簽分類的依賴度定義為:

(5)

定義4 條件屬性a∈A-B在屬性集B的基礎(chǔ)上相對于決策屬性L的重要度為:

sigγ(a,B,L)=γB∪{a}(L)-γB(L)

(6)

多標簽鄰域特征選擇算法(ARMLNRS)，基于屬性的重要性來約簡屬性。該算法的主要思想是使用向前貪心算法依次選擇具有最大重要度的特征，當sigγ(a,B,L)=0時說明特征a是多余的。

算法3 M-A

輸入： 樣本的特征矩陣X，樣本的標簽矩陣L和鄰域參數(shù)δ

輸出： 約簡特征集feature_reduct

(1) 根據(jù)算法1得到特征權(quán)重向量W

(2) 選取排名前80%的特征，構(gòu)造新的特征矩陣A

(3) 初始化feature_reduct=?

(4) fori=1∶p

(5) 不在約簡屬性集的屬性ai

(6) 根據(jù)式(6)計算sigγ(ai,feature_reduct,L)

(7) ifsig>0

(8) 將ai加入到集合feature_reduct

(9) end if

(10) end for

(11) return feature_reduct

二層約簡算法M-A在算法2的基礎(chǔ)下，再根據(jù)屬性重要度能有效去除冗余的特征，進行二層特征篩選，實驗表明能有效減少特征個數(shù)，并且分類效果相比原來的ARMLNRS有所提高。

3 實驗分析

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

本文從Mulanlibrary下載3個多標簽分類任務(wù)，如表1所示。其中，Emotions是一個關(guān)于音樂情感分類的數(shù)據(jù)集，它有593首歌，6種音樂情感，每首歌用72個特征來描述； Yeast是一個關(guān)于酵母菌基因功能分類的數(shù)據(jù)集，它包含2 417個樣本，103個特征，14個標簽；Scene是一個語義場景的靜態(tài)索引數(shù)據(jù)集，它有2 407個實例，294個特征，6個標簽。

表1 數(shù)據(jù)集描述

3.2 實驗設(shè)置

所有實驗評估使用多標簽分類模型中的算法ML-KNN[14](設(shè)定平滑參數(shù)smooth=1，鄰居個數(shù)num=10)，實驗全部運行在3.30 GHz處理器、8.00 GB的內(nèi)存空間中。

3.3 評價指標

本文根據(jù)下列5個指標[15]來評價分類效果：

(1) Hamming Loss(HL)：評估預(yù)測結(jié)果與實際結(jié)果的平均差值；

(2) Ranking Loss(RL)：估計有多少與樣本不相關(guān)的標簽的排序高于相關(guān)標簽的排序；

(3) One-Error(OE)：反應(yīng)序列最前端的標記不屬于標記集合的情況；

(4) Coverage(CV)：樣本標簽排序的序列中，覆蓋屬于樣本的所有標簽所需搜索時間；

(5) Average Precision(AP)：在樣本預(yù)測排序中，排在該樣本標簽前的標簽仍屬于樣本標簽集的情況。

指標(1)-指標(4)越小越好，指標(5)越大越好。

3.4 實驗結(jié)果

實驗中，首先通過特征選擇算法獲得特征子集，然后對新的特征子集采用ML-KNN分類器進行多標簽分類。根據(jù)文獻[7]的最佳測試結(jié)果，比較在不同比例下Mult-ReliefF特征選擇方法和ARMLNRS算法的平均分類精度。

由圖1可以看出，對于數(shù)據(jù)樣本集Yeast和Scene而言，利用Mult-ReliefF算法在80%選擇后的特征子集分類效果達到最好，并且選擇50%及以上的特征數(shù)目，分類效果明顯高于ARMLNRS算法。而對于數(shù)據(jù)樣本Emotions而言，只有在80%左右的效果比ARMLNRS算法略優(yōu)。由表1可知，Yeast和Scene的標簽數(shù)和描述樣本的屬性數(shù)比Emotions的要大，可見Mult-ReliefF特征選擇算法更適合標簽數(shù)和屬性數(shù)較大的樣本集。說明特征選擇的效果和描述樣本屬性的個數(shù)和標記樣本的標簽數(shù)有關(guān)，進行數(shù)據(jù)分類時應(yīng)針對數(shù)據(jù)集的特點選擇合適的特征選擇算法。

圖1 三個數(shù)據(jù)集下分類精度比較

實驗表明在選擇樣本80%左右的特征，才能獲得最好的分類結(jié)果，若是樣本屬性個數(shù)基數(shù)大，特征排序后選擇前80%后的特征數(shù)目依然不低，這樣的情況下選擇的是與樣本關(guān)系緊密的屬性，不能去除冗余。考慮到ARMLNRS算法能去除冗余特征，結(jié)合該算法做二層特征約簡能在保證分類效果的前提下，盡可能獲得較少的特征子集，更好地達到特征約簡的目的。

實驗結(jié)果如表2-表4所示。在每個數(shù)據(jù)集上比較三種特征選擇方式的效果，其中，F(xiàn)N表示約簡后的特征個數(shù)。

表2 Emotions下分類效果與特征子集個數(shù)對比

表3 Yeast下分類效果與特征子集個數(shù)對比

表4 Scene下分類效果與特征子集個數(shù)對比

從實驗結(jié)果可以看出，在Emotions數(shù)據(jù)集上，M-A較Mult-ReliefF和ARMLNRS算法均有提高，而且選擇的特征數(shù)目最少。在Yeast和Scene數(shù)據(jù)集下依然得到了最小的特征子集，但是分類效果不如Mult-ReliefF，卻比ARMLNRS算法略優(yōu)。結(jié)合兩次實驗，可以看出二層約簡M-A算法更側(cè)重表現(xiàn)ARMLNRS算法的優(yōu)勢，能夠獲得較小的特征子集，分類效果也優(yōu)于ARMLNRS算法。這是由于先進行了降噪處理，然后再進行鄰域下的去冗余操作，更好地發(fā)揮了ARMLNRS算法的優(yōu)點，有效降低特征數(shù)目。然而，M-A算法造成了過度約簡，所以效果不如Mult-ReliefF算法。Mult-ReliefF算法能有效提高分類精度，并且在數(shù)據(jù)量大的樣本中表現(xiàn)的更為明顯。總的來說，Mult-ReliefF算法在五個評價指標中都表現(xiàn)出優(yōu)勢，M-A算法能獲得較小的特征子集，因此要根據(jù)需求選擇合適的特征選擇方法，這樣更有利于提高分類的效果。

4 結(jié) 語

本文擴展了ReliefF算法，提出一種適合多標簽數(shù)據(jù)的特征選擇算法——Mult-ReliefF算法。該算法解決如何查找多標簽樣本最近鄰的問題，改進了權(quán)值的更新公式，實現(xiàn)了數(shù)據(jù)降維的功能，實驗表明該算法是有效且可行的。又由于Mult-ReliefF算法不能去除特征間的冗余性，設(shè)計了二層約簡M-A算法，進一步去除冗余。實驗表明M-A算法能在分類效果相差不大的情況下，獲得更小的特征子集。但是M-A算法會造成過度約簡，影響分類效果，接下來將研究如何避免二層約簡造成的過度去噪。

[1] Zhang M L, Zhou Z H. A Review On Multi-Label Learning Algorithms[J]. IEEE Transactionson Knowledge &Data Engineering, 2014, 26(8):1819-1837.

[2] Qi G J, Hua X S, Rui Y, et al. Correlative multi-label video annotation[C]// ACM International Conference on Multimedia. ACM, 2007:17-26.

[3] Barutcuoglu Z, Schapire R E, Troyanskaya O G. Hierarchical multi-label prediction of gene function[J]. Bioinformatics, 2006, 22(7):830-836.

[4] Yang B, Sun J T, Wang T, et al. Effective multi-label active learning for text classification[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28-July. 2009:917-926.

[5] Gopal S, Yang Y. Multilabel classification with meta-level features.[J]. Machine Learning, 2010, 88(1-2):315-322.

[6] Ozonat K, Young D. Towards a universal marketplace over the web: statistical multi-label classification of service provider forms with simulated annealing[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2009:1295-1304.

[7] 段潔, 胡清華, 張靈均,等. 基于鄰域粗糙集的多標記分類特征選擇算法[J]. 計算機研究與發(fā)展, 2015, 52(1):56-65.

[8] Zhang M L, Pena J M, Robles V. Feature selection for multi-label native Bayes classification[J]. Information Science,2009,179(19):3218-3229.

[9] Zhang Y, Zhou Z H. Multi-Label Dimensionality Reduction via Dependence Maximization[C]// AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, Usa, July. DBLP, 2008:1503-1505.

[10] 張振海,李士寧,李志剛,等.一類基于信息熵的多標簽特征選擇算法[J]. 計算機研究與發(fā)展, 2013, 50(6):1177-1184.

[11] Cai Y P, Yang M, Gao Y, et al. ReliefF-based Multi-label Feature Selection[J]. International Journal of Database Theory & Application,2015(8):307-318.

[12] Spolaor N, Cherman E A, Monard M C, et al. ReliefF for Multi-label Feature Selection[C]// Brazilian Conference on Intelligent Systems. 2013:6-11.

[13] 于洪, 王國胤, 姚一豫. 決策粗糙集理論研究現(xiàn)狀與展望[J]. 計算機學(xué)報, 2015(8):1628-1639.

[14] Zhang M L, Zhou Z H. ML-KNN: A lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7):2038-2048.

[15] Schapire R E, Singer Y. BoosTexter: A Boosting-based Systemfor Text Categorization[J]. Machine Learning, 2000,39(2-3):135-168.

TWO FEATURE SELECTION ALGORITHMS FOR MULTI-LABEL CLASSIFICATION BY EXTENDING RELIEFF

Ma Jingying Xuan Hengnong

(SchoolofInformationEngineering,NanjingUniversityofFinanceandEconomics,Nanjing210000,Jiangsu,China)

The ReliefF feature selection algorithm is limited to single-label data. Concerning this problem, two multi-label feature selection algorithms termed Mult-ReliefF and M-A are proposed. The Mult-ReliefF algorithm redefined the relationship of the nearest neighbors and updating formula of feature weights and added the label contribution to update the feature weight formula. Based on the Mult-ReliefF algorithm, combining with neighborhood rough set to achieve better effect of the feature dimension reduction, secondary reduction algorithm M-A is proposed by also adopting the ML-KNN sorting algorithm. Experimental results on data sets show that Mult-ReliefF algorithm can improve classification effect and M-A can obtain smaller feature subset.

Multi-label classification Feature selection Attribute reduction ReliefF Neighborhood rough sets

2016-09-18。馬晶瑩，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，多標簽分類。宣恒農(nóng)，教授。

TP181

A

10.3969/j.issn.1000-386x.2017.07.055