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

馬晶瑩 宣恒農

(南京財經大學信息工程學院 江蘇 南京 210000)

?

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

馬晶瑩 宣恒農

(南京財經大學信息工程學院 江蘇 南京 210000)

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

多標簽分類 特征選擇 數據降維 ReliefF 鄰域粗糙集

0 引 言

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

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

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

1 多標簽的特征選擇算法

1.1 單標簽ReliefF特征選擇算法

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

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

在樣本空間中:

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

(1)

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

算法1 ReliefF算法

輸入：訓練數據集U，迭代次數m，最近鄰樣本個數k

輸出：特征權重向量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關于特征a的距離，P(C)表示類別C的概率，Mj(C)表示類別C的第j個樣本。最終得到所有特征的權值，權值越大表示該特征對樣本的區分能力越強，設定閾值選擇符合條件的特征從而達到降維的目的。

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

1.2Mult-ReliefF特征選擇算法

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

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

又在多標簽數據中，每個樣本的標簽滿足：

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

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

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

又在多標簽數據中，每個樣本的標簽滿足：

(2)

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

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

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

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

輸出：特征的權值向量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)表示一個非空集合，它們含有的元素個數可以是一個，也可以是多個，其他符號說明同算法1。如果樣本Ri和同類樣本關于特征a的距離不相同，則特征a就把兩個同類的樣本區分開了，故要減去d(a,Ri,Hj)。相反，如果樣本Ri和不同類樣本關于特征a的距離不相同，則特征a就把兩個不同類的樣本區分開了，正是我們想要的，故要加上d(a,Ri,Mj)，特征權重公式中求的是均值化差異。原來的權重公式中沒有考慮標簽對權重的貢獻值，加入標簽貢獻值參數μi，考慮樣本Ri的標簽占標簽空間的比重，對多標簽數據給予重視，實驗證明算法的有效性。

2 二層特征約簡

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

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

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

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

(3)

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

定義2 集合L關于鄰域關系NB的下近似為:

(4)

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

(5)

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

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

(6)

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

算法3 M-A

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

輸出： 約簡特征集feature_reduct

(1) 根據算法1得到特征權重向量W

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

(3) 初始化feature_reduct=?

(4) fori=1∶p

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

(6) 根據式(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的基礎下，再根據屬性重要度能有效去除冗余的特征，進行二層特征篩選，實驗表明能有效減少特征個數，并且分類效果相比原來的ARMLNRS有所提高。

3 實驗分析

3.1 數據集

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

表1 數據集描述

3.2 實驗設置

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

3.3 評價指標

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

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

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

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

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

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

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

3.4 實驗結果

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

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

圖1 三個數據集下分類精度比較

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

實驗結果如表2-表4所示。在每個數據集上比較三種特征選擇方式的效果，其中，FN表示約簡后的特征個數。

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

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

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

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

4 結 語

本文擴展了ReliefF算法，提出一種適合多標簽數據的特征選擇算法——Mult-ReliefF算法。該算法解決如何查找多標簽樣本最近鄰的問題，改進了權值的更新公式，實現了數據降維的功能，實驗表明該算法是有效且可行的。又由于Mult-ReliefF算法不能去除特征間的冗余性，設計了二層約簡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]. 計算機研究與發展, 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]. 計算機研究與發展, 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] 于洪, 王國胤, 姚一豫. 決策粗糙集理論研究現狀與展望[J]. 計算機學報, 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。馬晶瑩，碩士生，主研領域：數據挖掘，多標簽分類。宣恒農，教授。

TP181

A

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