基于ReliefF和最大相關最小冗余的多標記特征選擇

孫林,徐楓,李碩,王振

(河南師范大學 計算機與信息工程學院,河南 新鄉 453007)

目前,多標記學習是數據挖掘、人工智能等領域的一個重要的研究方向[1].作為數據挖掘的預處理技術,多標記特征選擇策略可分為過濾式、封裝式和嵌入式[2].過濾式在效率上有一定的優勢,而如何構建合適的評價指標來評價候選特征是過濾式的關鍵,并且不依賴特定分類器,由此選擇出來的特征子集對于不同的分類器適用性更強[3].王晨曦等[4]通過融合標記權重與對象平均間隔構建了鄰域信息熵,進而設計了信息粒化多標記特征選擇模型.但是該方法未涉及標記之間以及特征與標記集之間的相關性.魏葆雅等[5]使用標記對對象的可分性賦予標記權重,并聯合特征權重對特征進行排序,基于標記重要性提出了多標記特征選擇模型.但是該模型未涉及特征與標記間的相關性.綜合考慮上述缺陷,利用互信息計算標記權重,由此設計特征和標記集間的相關度,初選與標記集相關度高的特征,提高特征與標記集之間的相關性.ReliefF是一種基于過濾式與特征加權的特征選擇算法.陳平華等[6]結合ReliefF和多標記貢獻值改進特征權值,基于互信息與ReliefF設計了多標記特征選擇算法.但是這種方法未計算標記之間的相關性.REYES等[7]提出了擴展的多標記ReliefF的特征選擇模型.但是,該模型未涉及特征間的相關性和冗余性.劉海洋等[8]利用ReliefF算法度量標記間的依賴關系,提出了基于ReliefF剪枝的多標記分類算法,但是,該算法未考慮特征與標記的相關性.針對以上算法存在的問題,本文改進ReliefF方法,引入標記權重構建特征權值更新公式,提高特征與標記間的相關性.

最大相關最小冗余算法是一種有效的過濾式特征選擇模型,其評價函數考慮了特征與類別、特征與特征之間的相關性,因此基于mRMR的多標記特征選擇得到了越來越多的關注.LI等[9]為了選擇更相關和緊湊的特征子集以及探索標記相關性,基于互信息和mRMR構造了多標記特征選擇模型.但是該算法計算復雜度較高.LIN等[10]考慮了標記之間的相關性、特征依賴性與冗余性,基于mRMR設計了多標記特征選擇模型.但是,它未涉及特征和標記之間的相關性而造成分類精度低且時間代價大.HUANG等[11]將鄰域逼近精度與mRMR結合,基于鄰域粗糙集構建了多標記特征選擇方法.但是該方法的計算復雜度較大.SUN等[12]提出了一種基于模糊鄰域粗糙集和mRMR的缺失標記特征選擇算法.然而,該算法沒有考慮標記間相關性,造成去除冗余特征精度不高,不能完全剔除所有的冗余特征,降低多標記分類的預測結果.基于上述分析,使用互信息和標記權重改進最大相關算法,提出了新的mRMR評價準則,以此來衡量標記間的相關性以及特征之間的冗余度,有助于對多標記數據集去除冗余特征,獲得最佳分類性能.

針對傳統ReliefF算法僅能處理單標記數據并且未充分考慮特征和標記集之間的相關性,以及傳統mRMR算法沒有考慮標記間相關性而造成分類精度偏低等問題,對傳統ReliefF算法和mRMR算法進行改進,提出了基于ReliefF和mRMR的多標記特征選擇算法.首先,根據標記和標記集之間的互信息定義相關度,計算該相關度所占的比例來構建新的標記權重,構造特征和標記集之間的相關度,初選與標記集相關度較高的特征;然后,計算對象在特征上的距離,構建新的特征權值更新公式,并結合標記權重改進多標記ReliefF特征選擇模型;最后,結合互信息和標記權重定義最大相關性,使用標記權重值與特征權值之和構建新的mRMR評價準則,有效提高模型的分類性能.

1 基礎理論

1.1 互信息

給定A={a1,a2,…,an}為一個隨機變量,p(ai)為變量ai的先驗概率,則A的信息熵[13]表示為:

(1)

給定A={a1,a2,…,an}和B={b1,b2,…,bm}為隨機變量,p(ai,bj)為A和B的聯合概率,i=1,2,…,n,j=1,2,…,m,則A和B的聯合信息熵[13]表示為:

(2)

給定A={a1,a2,…,an}和B={b1,b2,…,bm}為隨機變量,p(bj|ai)為條件先驗概率,i=1,2,…,n,j=1,2,…,m,則B在給定A下的條件熵[13]表示為:

(3)

隨機變量A和B的互信息[13]表示為:

(4)

然后對互信息量進行歸一化處理[13],歸一化處理公式表示為:

(5)

易證明NMI(A;B)∈[0,1].NMI(A;B)=0表示A和B相互獨立,NMI(A;B)=1表示可通過A和B之一確定另一個.

1.2 ReliefF算法

在ReliefF算法中,兩個對象R1和R2在特征f上的距離[14]為:

(6)

其中,R1(f)表示對象R1在特征f上的值;R2(f)表示對象R2在特征f上的值;max(f)表示在特征f上的最大值,min(f)表示最小值.更新每個特征的權重的公式為:

(7)

其中,Hj和Mj分別代表對象R的第j個近鄰同類對象和異類對象,diff(f,R,Hj)和diff(f,R,Mj)分別表示對象R與Hj和Mj分別在f上的距離,m為算法的迭代次數,k為近鄰對象數,LRi是對象Ri的標記,P(LRi)是對象Ri所屬標記的概率,P(l)表示標記l的概率.

2 多標記特征選擇方法

2.1 標記權重

假設一個多標記決策系統表示為MDS=〈U,C,D,T〉[15],其中U={x1,x2,…,xn}是對象集;C是條件特征集和D是對象對應的標記空間;T={(xi,ti)|i=1,2,…,n}是在標記上的映射關系.若對象xi有第l個類別標記,記為ti(l)=1,否則記為ti(l)=0;且∑ti≥1,其中每個對象xi由f維表示,即xi∈Rf,對應的標記集由ti∈{0,1}l表示,這里l∈D.

為了解決未考慮特征和標記集之間的相關度而造成分類精度偏低的問題,利用互信息和標記權重,計算特征和標記集之間的相關度,使其有效篩選出與標記集相關度較高的特征子集.

定義1在MDS=〈U,C,D,T〉中,L?D,lk∈L,k=1,2,…,m,基于互信息計算標記和標記集之間相關度公式為:

(8)

定義2在MDS=〈U,C,D,T〉中,L?D,lk∈L,k=1,2,…,m,計算每個標記和標記集相關度,并計算其相關度的和,用兩者的比例來定義標記權重為:

(9)

定義3在MDS=〈U,C,D,T〉中,F?C,fj∈F,j=1,2,…,z,L?D,lk∈L,k=1,2,…,m,根據互信息和標記權重計算特征f和標記集L之間的相關度為:

(10)

2.2 改進的ReliefF

為了解決傳統ReliefF不適用于多標記特征選擇的問題,根據標記權重設計新的ReliefF模型,由此構建特征權值更新公式,提高ReliefF算法的分類性能.

定義4在MDS=〈U,C,D,T〉中,X?U,xi,yi∈X,i=1,2,…,n,F?C,fj∈F,j=1,2,…,z,任意兩個對象xi和yi在特征fj上的距離被定義為:

(11)

其中,xi(fj)是xi在fj上的特征值;yi(fj)是yi在fj上的特征值;max(fj)和min(fj)分別是fj在對象空間上的最大值和最小值.

定義5在MDS=〈U,C,D,T〉中,X?U,xi∈X,i=1,2,…,n,F?C,f∈F,L?D,lk∈L,k=1,2,…,m,結合標記權重和距離定義特征權重更新公式為:

(12)

其中,NMl(xi)是在l中xi的最近鄰異類對象,NHl(xi)是在l中xi的最近鄰同類對象.diff(xi,NMl(xi))和diff(xi,NHl(xi))分別是在f下xi在l中與其最近異類對象的距離和最近同類對象的距離.

2.3 改進的mRMR

為解決mRMR未涉及標記之間的相關性,導致刪除冗余特征后的分類精度出現不理想的問題,運用互信息和標記權重更新最大相關性公式,并結合特征權值之和,提出新的mRMR評價準則,并將其應用于多標記特征選擇.

定義6在MDS=〈U,C,D,T〉中,L?D,l∈L,F?C,fj∈F,j= 1,2,…,z,結合互信息和標記權重定義最大相關性的計算公式為:

(13)

定義7在MDS=〈U,C,D,T〉中,F?C,fi,fj∈F,i,j=1,2,…,z,基于互信息定義最小冗余性的計算公式為:

(14)

定義8在MDS=〈U,C,D,T〉中,特征集合F?C,L?D,l∈L,結合特征權重定義新的mRMR計算公式為:

(15)

其中,∑w(F)為特征集合F中每個特征的特征權重之和.

2.4 多標記特征選擇算法

由此,設計基于ReliefF和mRMR的多標記特征選擇算法(Multilabel feature selection algorithm using ReliefF and mRMR,MFSRM).首先計算新的標記權重和每個特征和標記集之間的相關度,初次篩選特征子集;然后計算特征權重選擇出中間特征子集;最后計算MR值得到最終特征排序.其偽代碼為:

算法1 MFSRM

輸入MDS=〈U,C,D,T〉.

輸出 最優特征子集R.

步驟1 For每個標記l∈D和每個特征f∈C;

步驟2 根據式(9)和式(10)分別計算標記權重WOL(lk)和特征和標記集之間的相關度Corr(f,D);

步驟3 End For;

步驟4 根據特征和標記集之間的Corr(f,D)值初次篩選出特征子集R0(特征個數關系:|R0|=2|R1|=4|R|).

步驟5 Forxi∈U;

步驟6 計算xi的NMl(xi)和NMl(xi);

步驟7 End For;

步驟8 For 每個特征f∈C;

步驟9 根據式(12)計算特征權重wf;

步驟10 End For;

步驟11 根據特征權重選擇出中間特征子集R1(特征個數關系:|R1|=2|R|).

步驟12 For 特征子集R1;

步驟13 根據式(15)計算MR(R1);

步驟14 End For ;

步驟15 對MR值進行排序并選擇前c個特征作為最終特征子集R.

3 實驗分析

3.1 實驗準備

為了測試MFSRM算法的分類性能,選取了Mulan數據庫(http://mulan.sourceforge.net)中的8個數據集進行實驗,表1描述了8個數據集的詳細信息.依據文獻[16]的平均分類精度(Average Precision,AP)、覆蓋率(Coverage,CV)、漢明損失(Hamming Loss,HL)、1錯誤率(One Error,OE)、排序損失(Ranking Loss,RL)指標作為分類性能和排序性能的5個評價指標.為了充分驗證本文算法的有效性,采用上述的5個基于對象的評價指標和選擇特征比例來評價算法的性能,其中AP值越大表示算法性能越好(最優值為1),其余4個指標值和特征選擇比例越小則算法性能越好.采用多標記K最近鄰(Multilabel k-nearest neighbor,ML-KNN)分類器,設置近鄰個數為10,平滑參數為1.實驗環境為Windows 10、CPU Intel(R)Core(TM)i5-8500 3.00 GHz和內存8.00 GB,采用MATLAB 2019a工具箱進行編碼.

表1 8個多標記數據集的信息

3.2 ML-KNN分類器上的實驗分析

為了充分展示MFSRM算法在不同數據集上的有效性,選擇5種對比算法:MLNB(Feature selection for multi-label naive Bayes classification)[17]、PMU(Pairwise Multivariate Mutual Information)[18]、MLRF(Relief for multi-label feature selection)[19]、MFSR(Multi-label feature selection algorithm based on improved ReliefF)[20]和WFSNR(Weak label feature selection method based on neighborhood rough sets and Relief)[21],進一步呈現MFSRM算法在ML-KNN分類器上的5個指標(AP、HL、CV、OE和RL)的實驗結果.各個數據集進行實驗時所選的特征個數見文獻[22].表2描述了MFSRM算法與5種多標記特征選擇算法在5個指標下的實驗結果.

表2 8個數據集上6種算法在5個指標下的比較結果

由表2可知,在AP指標下,MFSRM算法在除Education外的7個數據集上,MFSRM算法的實驗結果均優于其他5種算法;尤其在Recreation數據集上,MFSRM算法比次優的MLNB算法高0.066;在Education數據集上,MFSRM算法為次優,比最優的MFSR算法低0.116 2,但MFSRM算法比其他4種算法高0.013 2～0.072 3.在HL指標下,MFSRM算法在8個數據集上的表現均為最優.在CV指標下,在Business數據集上,MFSRM算法比最優的PMU算法和次優的MFSR算法分別高0.057 4和0.008 2;在Health數據集上,MFSRM算法比最優的PMU算法高0.072;但在其他6個數據集上,MFSRM算法均優于其他5種多標記特征選擇算法.在OE指標下,在這8個數據集上,MFSRM算法均為最優.在RL指標下,MFSRM算法在除Business和Health以外的6個數據集上的實驗結果均為最優;在Business數據集上,MFSRM算法比最優的PMU算法高0.001 6;在Health數據集上,MFSRM算法為次優,比最優的PMU算法高0.001 9,但總體上仍優于其他4種算法;在Recreation數據集上,MFSRM算法明顯優于其他5種算法,比其他算法低0.014 9～0.034 6.從整體來看,MFSRM算法在大部分數據集上的表現均為最優,在極個別數據集上的指標表現為次優,如在CV和RL指標下,Business和Health這2個數據集上MFSRM算法的表現較差,原因是Business和Health這2個數據集是稀疏矩陣數據集,證明了MFSRM算法在這類稀疏矩陣數據集上的分類性能不佳.通過觀察發現:這6種算法在Art和Recreation這2個數據集上的AP值均過低(低于或略高于50%).究其原因可能是:在Art和Recreation這2個數據集上,收集數據和劃分數據時可能對平均分類精度有所限制,從而導致在現存大多數流行算法的實驗結果中呈現的平均分類精度均不高.綜上所述,MFSRM算法的性能得到了有效地提升.

在本節實驗的第2部分是將MFSLM算法與第1部分的4種多標記特征選擇算法:MLRF算法、PMU算法、MFSR算法和WFSNR算法作對比分析,給出表1中Art、Business、Computer、Entertainment、Reference這5個數據集各特征選擇算法在不同特征比例下的分類情況.圖1展示了5種算法在不同特征比例下AP指標的變化趨勢對比圖.由于篇幅限制,其余4個指標的變化趨勢圖可以單獨提供.

由圖1可知,在AP指標下,在Art和Entertainment這2個數據集上,MFSRM算法在選擇特征比例較小時,算法性能較好,在選擇特征比例大于0.7時,MFSRM算法的性能差于MFSR算法.在Business數據集上,在選擇特征比例為0.25～0.35時,MFSRM算法差于PMU算法;在選擇特征比例為0.40～0.45和0.65～0.70時,MFSRM算法為最優;在選擇特征比例大于0.5時,MFSRM算法性能較差.在Computer數據集上,在選擇特征比例小于0.5時,MFSRM算法優于其他算法.在Reference數據集,MFSRM算法在選擇特征比例較小時優于其他算法,但選擇特征比例大于0.6時,MFSRM算法差于MFSR算法.

整體來看,在選擇特征比例較小時,MFSRM算法優于其他4種算法,其原因可能是:在選擇特征比例較大時,冗余特征較多,分類性能下降.但綜上所述,MFSRM算法的改進是有效的,提升了算法的性能.

3.3 統計分析

本節使用Friedman測試[23]和Nemenyi測試[24]驗證多標記特征選擇算法對于不同數據集分類結果的統計重要性.Friedman測試公式為:

(16)

(17)

其中,T是數據集的數量,s代表對比算法數量,Ri是每個算法在所有數據集上的平均排序.臨界距離表示為:

(18)

其中,qα是測試臨界值,α是Nemenyi測試中的一個重要指標.

參考文獻[23]的統計計算方法,檢測本文MFSRM算法與其他5種對比算法在AP、HL、CV、OE和RL這5個指標上是否存在顯著差異.表2中的實驗結果對應的統計結果如表3所示,CD圖如圖2所示.圖2展示了表2中5個指標上的6種算法的對比結果.接下來,使用了Friedman檢驗判斷這6種算法在分類性能上是否相同.由文獻[25]中表2.6的F檢驗的常用臨界值可知,在α=0.1,s=6且T=8時,F檢驗臨界值是2.019,而由表3可知,這5個評價指標的FF值均大于臨界值2.019.因此拒絕“所有算法性能相同”這個假設,需要進行后續檢驗.于是,本文采用Nemenyi測試執行后續檢驗.而對于Nemenyi測試,當q0.1=2.589,s=6且T=8時,CD值為2.421 8.文獻[25]指出:若兩個算法存在性能顯著不同,則它們的平均序值之差會超出臨界值CD,否則它們之間有一條直線連接,表示它們沒有顯著差別.從圖2中可以得到如下結論:本文MFSRM算法在5個評價指標上分類性能均排名第1.詳細來講:在AP指標上,MFSRM算法與WFSNR和MLRF這2種算法的性能顯著不同,與其他3種算法的分類性能沒有顯著差別;在HL、CV和RL這3種指標上,MFSRM算法與PMU和MLNB這2種算法之間不存在顯著性差異,MFSRM算法與MFSR、WFSNR和MLRF這3種算法之間存在顯著性差異;在OE指標上,MFSRM算法與PMU和MFSR這2種算法之間不存在顯著性差異,MFSRM算法顯著優于與MLNB、WFSNR和MLRF這3種算法.總之,與其他5種對比算法相比,MFSRM算法表現出了良好的分類性能.

表3 5個評價指標下6種算法的統計結果

4 結 論

針對一些多標記特征選擇算法未充分考慮特征和標記集之間的相關性導致算法分類性能偏低的問題,本文考慮標記之間的相關性以及特征與標記集之間的相關性,提出了基于ReliefF和mRMR的多標記特征選擇算法.首先,基于互信息計算標記和標記集間的相關度來改進標記權重,并結合標記權重計算特征和標記集之間的相關度,提高了特征和標記集之間的相關性.然后,改進ReliefF模型,結合標記權重和基于對象在特征上的距離更新特征權值公式,提高算法分類精度.最后,結合互信息和標記權重定義最大相關性,使用特征權值之和構建了新的mRMR評價準則,得到最優特征子集.在8個多標記數據集上進行實驗,結果表明所提算法性能有所提高.