孫 林,杜雯娟,李 碩,徐久成

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

多標記學(xué)習是目前機器學(xué)習和數(shù)據(jù)挖掘等領(lǐng)域中的熱門研究方向之一[1]。目前,維度災(zāi)難問題已成為多標記學(xué)習的重要挑戰(zhàn)之一[2]。特征選擇無需進行映射變換即可從原始特征空間中選擇出重要特征信息,且保留原始數(shù)據(jù)的分類能力,有效地降低了數(shù)據(jù)的特征維度[3-5]。互信息在信息論中用于衡量兩個隨機變量之間的相關(guān)程度,通常用于統(tǒng)計語言模型中計算特征與特征之間的關(guān)系[6-7]。互信息可以認為是一個隨機變量由于另一個已知隨機變量而減少的不確定性[8-9]。由于互信息無需對特征與標記之間關(guān)系的性質(zhì)作出假設(shè),因此非常適合于多標記學(xué)習任務(wù)。Sun等[10]提出了一種基于鄰域互信息的多標記特征選擇算法。但是,該算法的輸出結(jié)果是隨機的,這會導(dǎo)致權(quán)重值的波動,同時杰卡德相關(guān)系數(shù)受稀疏標記矩陣的影響,容易導(dǎo)致計算結(jié)果的不平衡。Huang等[11]利用最大相關(guān)最小冗余設(shè)計了一種基于鄰域粗糙集模型的多標記特征選擇算法。然而,該算法只考慮了單個標記中的樣本鄰域半徑,忽略了標記之間的相關(guān)性。Wang等[12]結(jié)合Fisher分數(shù)和鄰域粗糙集提出了一種新的多標記特征選擇算法。然而,該算法忽略了特征之間的相關(guān)性且未考慮多標記高階相關(guān)性,導(dǎo)致計算復(fù)雜度偏高。Lim等[6]利用互信息提出了基于進化算法的多標記特征選擇方法。但是,該方法在計算時間上開銷較大。Huang等[2]利用流形正則化和依賴最大化提出了一種多標記特征選擇算法。但是,該算法沒有考慮標記相關(guān)性,計算復(fù)雜度較高。Wang等[13]提出了一種基于互信息和譜粒度的多標記在線流特征選擇算法。然而當信息粒數(shù)變大時,其計算復(fù)雜度可能會大大增加?；谏鲜鲅芯康膯l(fā),綜合考慮特征與標記集之間的互信息,結(jié)合標記權(quán)重來定義標記相關(guān)性公式,對多標記數(shù)據(jù)集進行預(yù)處理,初步篩選出與標記集合相關(guān)度較高的特征子集。

Relief算法是一種過濾式特征選擇方法[14],該算法賦予每個特征不同的權(quán)重,權(quán)重小于某個閾值的特征將被剔除。Kira等[15]提出的Relief算法只能用于二分類問題。為了研究適用于多標記分類問題的ReliefF算法,蔡亞萍等[16]提出了一種結(jié)合局部相關(guān)性的多標記ReliefF特征選擇算法。劉海洋等[17]利用ReliefF算法度量標記間的依賴關(guān)系,選擇有較強依賴關(guān)系的標記加入原始特征空間。但是,上述算法均未考慮特征與標記的相關(guān)性。馬晶瑩等[18]通過研究最近的同類樣本和異類樣本的搜索方法,提出基于多標記ReliefF的特征選擇算法。然而,該算法確定隨機樣本的最近鄰樣本數(shù)較少,容易導(dǎo)致特征權(quán)重值波動較大。Kong等[19]基于ReliefF和F-statistic研究了特征選擇算法,并將其應(yīng)用在多標記圖像標注任務(wù)中。但上述方法沒有考慮不同標記對于樣本數(shù)據(jù)具有不同的可分性。林夢雷等[20]計算樣本在特征上的歐式距離并對標記進行加權(quán),提出了基于加權(quán)標記的多標記特征選擇算法。但是,當樣本間的距離非常大時會使異類樣本或者同類樣本無效。為了解決這個問題,引入異類樣本和同類樣本數(shù)量,結(jié)合特征與標記集合相關(guān)度構(gòu)建一種新的特征權(quán)重更新公式,消除樣本距離過大時帶來的負面影響,進而設(shè)計了帶有標記權(quán)重的多標記ReliefF算法。其主要貢獻如下:

1) 為了解決沒有充分考慮特征與標記之間的相關(guān)性而造成分類精度偏低的問題,使用特征與標記集合的互信息和改進的標記權(quán)重,定義標記相關(guān)性公式,衡量特征與標記之間的相關(guān)程度,初步篩選出與標記集相關(guān)度較高的特征子集。

2) 為了解決傳統(tǒng)ReliefF算法會因樣本間距離過大,導(dǎo)致異類樣本和同類樣本失去原有度量特征重要性的作用,引入異類樣本數(shù)和同類樣本數(shù)消除樣本間距過大的影響,由此分別計算樣本與最近鄰樣本間的距離;結(jié)合標記權(quán)重構(gòu)建新的特征權(quán)值更新公式,進而選擇初篩特征集合中的重要特征。

3) 為了解決傳統(tǒng)ReliefF算法分類精度偏低的問題,構(gòu)建基于標記相關(guān)性和改進ReliefF算法的多標記特征選擇算法,提高多標記數(shù)據(jù)的分類性能。

1 基礎(chǔ)理論

1.1 熵與互信息

假設(shè)MLDS=〈U，C，D，T〉是一個多標記決策系統(tǒng),其中U={x1，x2，…，xn}表示由n個樣本構(gòu)成的樣本集;C表示特征屬性集,D表示各個樣本對應(yīng)的標記空間,L表示標記總個數(shù);T={(xi，yi)|i=1,2,…，n}表示在標記上的映射關(guān)系。每個樣本由f維表示,記為xi∈Rf,對應(yīng)的標記集由向量yi∈{0, 1}l表示,其中l(wèi)∈D。如果xi有l(wèi)類別標記,則yi(l)=1,否則yi(l)=0;且∑yi≥ 1。

在MLDS=〈U，C，D，T〉中,對任意的xi∈X?U(i=1, 2, …,n),p(xi)為樣本xi的先驗概率,則集合X的信息熵[10-11]表示為

(1)

在MLDS=〈U，C，D，T〉中,任意兩個樣本子集X、Y?U,xi∈X和yj∈Y(i,j=1, 2, …,n),p(xi,yj)為兩個樣本xi和yj的先驗概率,則X和Y的聯(lián)合信息熵[10]表示為

(2)

在MLDS=〈U，C，D，T〉中,X、Y?U,xi∈X和yj∈Y(i，j=1, 2, …,n),p(yj|xi)為條件先驗概率,則Y在給定X下的條件熵[10]表示為

(3)

X和Y的互信息量表示已知Y的條件下,X不確定性的改變量,從統(tǒng)計學(xué)角度反映了X和Y的關(guān)聯(lián)程度,所以X和Y的互信息[13]表示為

(4)

易證明0 ≤I(X;Y)≤1。I(X;Y)=0表示X和Y相互獨立,I(X;Y)=1表示X和Y之間相關(guān)性較強。

1.2 大間隔

在MLDS=〈U，C，D，T〉中,對于任意的X?U,xi∈X(i=1, 2, …,n),則樣本xi的分類間隔[20]表示為

margin(xi)=Δ(xi,NM(xi))-

Δ(xi,NH(xi))

(5)

其中：NM(xi)是在樣本空間U中與xi距離最近的異類樣本,稱為xi的最近鄰異類樣本;NH(xi)是在樣本空間U中與xi距離最近的同類樣本,稱為xi的最近鄰?fù)悩颖?Δ(xi, NM(xi))和Δ(xi, NH(xi))分別代表xi到NM(xi)和NH(xi)的距離。

在MLDS=〈U，C，D，T〉中,特征空間F?C,fj∈F(j=1, 2,…,z),對于任意的X?U,xi∈X(i=1, 2, …,n)，則第i個特征的權(quán)重可被計算[20]為

wi=wi+|xi-NM(xi)|-|xi-NH(xi)|

(6)

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

2 多標記特征選擇方法

2.1 特征和標記集之間的相關(guān)度

為解決部分方法忽略特征和標記之間的相關(guān)度而造成分類精度偏低且時間代價較大的問題,引入標記權(quán)重的概念,并將其與傳統(tǒng)互信息相結(jié)合,更精確地反映特征與標記集的相關(guān)度,從而提高算法的分類精度。

定義1在MLDS=〈U，C，D，T〉中,任意標記子集L?D,標記lk∈L,其中k=1, 2, …,m,則標記lk的權(quán)重定義如下

(7)

其中：n是樣本數(shù)；n(lk)表示含有標記lk的正類樣本數(shù)；W(lk)反映正類樣本在標記集合中所占的比例。

定義2在MLDS=〈U，C，D，T〉中,F?C,fj∈F(j=1, 2, …,z),L?D,lk∈L(k=1, 2, …,m), 每個特征和標記集之間的相關(guān)度計算公式為

(8)

其中：I(f;lk)表示特征與標記之間的互信息；W(lk)為定義1中的標記權(quán)重。結(jié)合標記集合中正類樣本的分布情況,為標記賦予不同的權(quán)重,動態(tài)地調(diào)節(jié)特征f與標記集L的相關(guān)程度。由此可知,特征與標記集合的相關(guān)度可用特征與標記集合間各個標記的互信息與標記權(quán)重的乘積的總和來衡量。

2.2 改進的多標記ReliefF

為了解決原有的ReliefF方法會因樣本間距離過大,導(dǎo)致異類樣本和同類樣本失去原有度量特征重要性的作用,引入異類樣本和同類樣本數(shù)量來消除該影響,并結(jié)合定義1的標記權(quán)重公式,改進多標記ReliefF模型,進而構(gòu)建新的特征權(quán)值更新公式,有效提高了算法的分類性能。

定義3在MLDS=〈U，C，D，T〉中,X?U,xi∈X(i=1, 2, …,n),F?C,fj∈F(j=1, 2, …,z), 對任意的特征f∈F,任意兩個樣本xi和xj在特征f上的距離公式表示為

(9)

其中：xi(f)表示xi在f上的值;xj(f)表示xj在f上的值;max(f)和min(f)分別表示特征f在樣本空間中取得的最大值和最小值。

定義4在MLDS=〈U,C,D,T〉中,X?U,xi∈X(i=1, 2, …,n),F?C,fj∈F(j=1, 2, …,z),L?D,lk∈L(k=1, 2, …,m), 則樣本xi分類間隔定義為

(10)

其中：NMl(xi)表示標記l中xi的最近鄰異類樣本;NHl(xi)表示標記l中xi的最近鄰?fù)悩颖?df(xi, NMl(xi))表示在特征f下樣本xi在標記l中與其最近鄰異類樣本的距離,df(xi, NHl(xi))表示在特征f下樣本xi在標記l中與其最近鄰?fù)悩颖镜木嚯x;|NNM|和|NNH|分別表示異類樣本數(shù)量和同類樣本數(shù)量。

定義5在MLDS=〈U,C,D,T〉中,X?U,xi∈X(i=1, 2, …,n),F?C,fj∈F(j=1, 2, …,z),L?D,lk∈L(k=1, 2, …,m), 結(jié)合標記權(quán)重和樣本分類間隔定義特征權(quán)值更新公式為

(11)

其中：W(lk)為標記權(quán)重；CM(xi)表示xi的分類間隔。

2.3 算法描述

首先,計算標記所占的比例權(quán)重,得到標記權(quán)重;其次,計算每個特征和標記集之間的相關(guān)度,根據(jù)相關(guān)度的值初次篩選出特征子集;然后,根據(jù)式(11)得出特征權(quán)重值;最后,根據(jù)特征重要性權(quán)值選出最終特征排序。由此,設(shè)計基于互信息的標記相關(guān)性并結(jié)合基于標記權(quán)重的ReliefF的多標記特征選擇(mutual information-based label correlation and label weighting-based ReliefF, MI-LW)算法,其偽代碼如下:

算法1MI-LW算法

輸入 MLDS=〈U,C,D,T〉

輸出 最優(yōu)選特征子集S

/*初步篩選模塊*/

Step1 For eachl∈D

Step2 For eachf∈C

Step3 由式(4)計算標記和特征之間的互信息

Step4 End For

Step5 End For

Step6 For eachlk∈D

Step7 根據(jù)式(7)計算含有標記lk的正類樣本個數(shù)并得出標記權(quán)重W(lk)

Step8 End For

Step9 For eachf∈C

Step10 For eachl∈D

Step11 根據(jù)式(8)計算CFL(f,D)

Step12 End For

Step13 End For

Step14 根據(jù)CFL值初次篩選出特征子集S-temp

/*Multi-Label-ReliefF模塊*/

Step15 For eachxi∈U

Step16 計算xi的NMl(xi)和NHl(xi)

Step17 End For

Step18 對標記權(quán)重W(lk)歸一化

Step19 For eachf∈C

Step20 For eachxi∈U

Step21 根據(jù)式(11)逐個計算特征f的權(quán)重Wf

Step22 End For

Step23 End For

Step24 根據(jù)Wf值對特征進行排序,輸出前k個特征組成最終的特征子集S

在MI-LW算法中,假設(shè)多標記數(shù)據(jù)集包括n個樣本、m個標記和z個特征。Step1至Step5計算標記和特征之間互信息的復(fù)雜度為O(mz),Step6到Step8計算標記權(quán)重的復(fù)雜度為O(m),Step9至Step13計算特征和標記集之間的相關(guān)度,復(fù)雜度為O(mz),Step15到Step17計算xi的最近鄰異類樣本NMl(xi)和最近鄰?fù)悩颖綨Hl(xi),復(fù)雜度為O(n),Step18對標記權(quán)重歸一化,復(fù)雜度為O(1),Step19至Step23計算特征權(quán)重的復(fù)雜度為O(mz),其中Step14和Step24為特征排序和輸出特征子集,時間復(fù)雜度均為O(zlogz)。由此,計算MI-LW算法總的時間復(fù)雜度為O(mz+m+n+zlogz)。

3 實驗結(jié)果及分析

3.1 實驗準備

實驗環(huán)境為Matlab R2019a,實驗使用計算機系統(tǒng)為Windows 7的64位操作系統(tǒng)、處理器為Intel(R)Core(TM)i7-4790 CPU @ 3.60GHz、內(nèi)存為8GB。采用多標記k最近鄰方法[20](Multi-labelk-nearest neighbors,ML-KNN)作為分類器來評估所提算法的性能,設(shè)置本實驗中的近鄰個數(shù)為10,平滑系數(shù)調(diào)節(jié)為1。為驗證MI-LW算法的有效性,在Mulan數(shù)據(jù)庫中選取7個數(shù)據(jù)集進行實驗(http:∥mulan.sourceforge.net/datasets.html),詳細信息描述如表1所示。為了評估所提算法的分類性能,采用文獻[10]中的5個指標:平均分類精度(Average Precision, AP)、覆蓋率(Coverage, CV)、1-錯誤率(One Error, OE)、排序損失(Ranking Loss, RL)、漢明損失(Hamming Loss, HL),并結(jié)合所選特征個數(shù)(the Number of Selected Features,NF)進行比較。在下面實驗結(jié)果中,“↑”表示值越大分類性能越好,“↓”表示值越小分類性能越好;表格中的粗體均表示最優(yōu)結(jié)果。

表1 7個多標記數(shù)據(jù)集描述

3.2 ML-KNN下的實驗結(jié)果

在第一部分實驗中采用消融實驗來證明MI-LW算法的有效性,選擇5個指標:AP、CV、HL、RL和OE進行評估。ReliefF表示原始ReliefF,Cor表示原始相關(guān)度,I-ReliefF表示改進的RelieF,I-Cor表示改進的相關(guān)度,MI-LW表示改進ReliefF和改進相關(guān)度相結(jié)合。在表1中選擇7個數(shù)據(jù)集作為實驗數(shù)據(jù)集。表2給出了4種多標記特征選擇方法在7個多標記數(shù)據(jù)集上的分類結(jié)果。

從表2中可以看出,在AP指標上,MI-LW算法在Emotions、Education、Social、Yeast、Flags和Arts這6個數(shù)據(jù)集上均取得最優(yōu);在Health數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF高了0.063 3。在CV指標上,MI-LW算法在Emotions、Health、Yeast和Flags這4個數(shù)據(jù)集上均取得最優(yōu);在Education數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.328 3;在Social數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.192;在Arts數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.263 7。在HL指標下,MI-LW算法在Education、Health、Social和Arts這4個數(shù)據(jù)集上均取得最優(yōu);在Emotions數(shù)據(jù)集上,MI-LW算法比ReliefF低了0.033 8;在Yeast數(shù)據(jù)集上, MI-LW算法比ReliefF低了0.004 6;在Flags數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.028 6。在RL指標上,MI-LW算法在Emotions、Social、Yeast和Flags這4個數(shù)據(jù)集上均取得最優(yōu);在Education數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.01;在Health數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.008 5;在Arts數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.012。在OE指標上,MI-LW算法在Emotions、Education、Social和Arts這4個數(shù)據(jù)集上均取得最優(yōu);在Health數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.100 3;在Yeast數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF低了0.090 4;在Flags數(shù)據(jù)集上,MI-LW算法僅比最優(yōu)ReliefF高了0.015 4,與其他2種算法持平。綜上分析,MI-LW算法優(yōu)于ReliefF、ReliefF+I-Cor和I-ReliefF+Cor,該實驗充分驗證了MI-LW算法的有效性。

表2 MI-LW在7個數(shù)據(jù)集上的消融實驗結(jié)果

在第二部分實驗中,選擇4個指標(AP、RL、OE和CV)進行算法評估,對比算法包括基于最大相關(guān)性的多標記維數(shù)約簡算法(multi-label dimensionality reduction algorithm via dependence maximization, MDDM)[21],其中,MDDM按照參數(shù)的不同可以分為MDDMspc和MDDMproj、基于多變量互信息的多標記特征選擇算法(feature selection algorithm for multilabel classification using multivariate mutual information, PMU)[22]、多標記樸素貝葉斯分類的特征選擇算法(feature selection algorithm for multi-label na?ve Bayes classification, MLNB)[23]、基于標記相關(guān)性的多標記特征選擇算法(multi-label feature selection algorithm with label correlation, MUCO)[13]、基于鄰域粗糙集和Relief的弱標記特征選擇算法(weak label feature selection algorithm based on neighborhood rough sets and relief, WFSNR)[1]和基于AP聚類和互信息的弱標記特征選擇算法(weak label feature selection algorithm based on AP clustering and mutual information,WFSAM)[24]。從表1中選擇4個數(shù)據(jù)集作為實驗數(shù)據(jù)集。表3給出了8種算法在4個多標記數(shù)據(jù)集上4個指標的分類結(jié)果。

從表3中可以看出,在AP指標上,MI-LW算法在Health、Yeast和Flags這3個數(shù)據(jù)集上均為最優(yōu);在Emotions數(shù)據(jù)集上,MI-LW算法為次優(yōu),僅比最優(yōu)算法MUCO低了0.000 5,但比其他對比算法高了0.001 6～0.066 9。在RL指標上,MI-LW算法在Health、Yeast和Flags這3個數(shù)據(jù)集上均為最優(yōu);在Emotions數(shù)據(jù)集上,MI-LW算法的RL值僅比最優(yōu)MDDMspc算法高了0.019 2,但比PMU、MLNB、WFSNR和WFSAM這4種算法分別低0.070 2、0.010 1、0.019 8和0.039 4,與MDDMproj算法基本持平。在OE指標上,MI-LW算法在Health和Flags這2個數(shù)據(jù)集上均為最優(yōu);在Emotions數(shù)據(jù)集上,MI-LW算法的OE值僅比最優(yōu)算法MUCO高了0.009 9,但比MDDMproj算法低了0.024 8,比PMU算法低了0.064 4,比MLNB算法低了0.049 8,比WFSNR算法低了0.054 5,比WFSAM算法低了0.059 4,與MDDMspc算法基本持平;在Yeast數(shù)據(jù)集上,MI-LW算法的OE值僅比最優(yōu)算法PMU高了0.010 1,但比MDDMspc算法低了0.016 1,比MDDMproj算法低了0.009 5,比MLNB算法低了0.012 8,比MUCO算法低了0.009 5,與WFSAM算法持平。在CV指標上,MI-LW算法在Health、Yeast和Flags這3個數(shù)據(jù)集上均為最優(yōu);在Emotions數(shù)據(jù)集上,MI-LW算法的CV值僅比最優(yōu)算法MDDMspc高了0.109 0,但比PMU、MLNB、WFSNR和WFSAM這 4種算法分別低了0.351 4、0.019 8、0.089 1和0.232 6,與MDDMproj算法基本持平。對于Emotions數(shù)據(jù)集,MI-LW算法在4個指標上均未取得最優(yōu),Emotions數(shù)據(jù)集的標記集為稀疏矩陣,且標記分布也較為集中,導(dǎo)致MI-LW算法在Emotions數(shù)據(jù)集上性能不佳。

表3 4個數(shù)據(jù)集上8種算法的4個指標對比結(jié)果

第三部分實驗選擇在不同特征個數(shù)下進行算法的分類性能比較。表1中選擇4個實驗數(shù)據(jù)集:Yeast、Arts、Education和Social。采用的評價指標為AP、CV、HL和RL。對比算法包括基于最大相關(guān)性的多標記維數(shù)約簡(multi-label dimensionality reduction via dependence maximization, MDDM)[21],其中,MDDM算法按照參數(shù)的不同可以分為MDDMspc算法和MDDMproj算法,本節(jié)選擇的對比算法為MDDMproj算法、多標記特征選擇算法(multi-label feature selection ReliefF algorithm,RF-ML)[25]、基于標記權(quán)重的多標記特征選擇算法(multi-label feature selection algorithm based on label weighting, LWMF)[20]、基于AP聚類和互信息的弱標記特征選擇算法(weak label feature selection method based on AP clustering and mutual information,WFSAM)[24]和基于鄰域粗糙集和Relief的弱標記特征選擇算法(Weak label feature selection method based on neighborhood rough sets and relief, WFSNR)[1]。圖1展示了4個數(shù)據(jù)集上6種算法的4個指標對比結(jié)果,其中橫坐標和縱坐標分別表示所選特征個數(shù)(NF)和評價指標。

圖1 6種算法在4個多標記數(shù)據(jù)集上的4個指標對比結(jié)果

對圖1A分析可知,在Yeast數(shù)據(jù)集上,AP指標下,當NF=20時,MI-LW算法略低于LWMF算法和WFSNR算法,與WFSAM算法基本持平,但仍優(yōu)于MDDMproj和RF-ML這2種算法。當NF=10、30、40時,MI-LW算法的AP值均優(yōu)于其他算法。CV指標下,當NF=50時,MI-LW算法的CV值最優(yōu)。在其他NF值上,MI-LW算法優(yōu)于絕大多數(shù)對比算法。當NF> 50時,MI-LW算法的CV值雖略有上升但仍優(yōu)于MDDMproj、RF-ML和WFSAM這3種算法。在HL指標下,當NF=60時,MI-LW算法的HL值最優(yōu)。在其他NF值上,MI-LW算法優(yōu)于絕大多數(shù)對比算法。當NF> 60時,MI-LW算法的HL值雖略有上升但優(yōu)于MDDMproj、RF-ML、LWMF和WFSAM這4種算法。RL指標下,MI-LW算法在所有NF值上均優(yōu)于MDDMproj、RF-ML、LWMF和WFSAM這4種算法,并且在絕大多數(shù)NF值上,MI-LW算法的RL值優(yōu)于WFSNR算法。對圖1B分析可知,在Education數(shù)據(jù)集上,AP指標下,當NF=200時,MI-LW算法的AP值取得最優(yōu),高于其他5種對比算法。當NF< 300時,MI-LW算法的AP值與WFSAM算法基本持平,但遠遠高于MDDMproj、RF-ML、LWMF和WFSNR這4種算法。CV指標下,當NF=200時,MI-LW算法的CV值取得最優(yōu),與WFSAM算法基本持平,但遠遠低于MDDMproj、RF-ML、LWMF和WFSNR這4種算法。隨著NF取值的增大,MI-LW算法的CV值雖略有上升,但仍優(yōu)于MDDMproj、RF-ML和WFSAM這3種算法。HL指標下,當NF=50時,MI-LW算法的HL值取得最優(yōu),遠低于其他對比算法。當NF< 300時,MI-LW算法的HL值均優(yōu)于其他對比算法。RL指標下,當NF=200時,MI-LW算法的RL值取得最優(yōu),低于其他對比算法。當NF< 300時,MI-LW算法的RL值與WFSAM算法相差無幾,但優(yōu)于MDDMproj、RF-ML、LWMF和WFSNR這4種算法。綜合來看,當NF值較小時,MI-LW算法的分類效果優(yōu)于其他5種對比算法。雖然隨著NF值的增大MI-LW算法的分類性能有所下降,但因為特征選擇所選的特征要盡量的少,故MI-LW算法的分類性能仍優(yōu)于其他算法。對圖1C分析可知,在Arts數(shù)據(jù)集上,AP指標下,當NF=100時,MI-LW算法的AP值取得最優(yōu),遠高于其他5種對比算法。當NF取其他值時,MI-LW算法的AP值雖略有下降,但在絕大多數(shù)NF值上仍優(yōu)于其他5種對比算法。CV指標下,當NF=150時,MI-LW算法的CV值取得最優(yōu)。當NF取其他值時,MI-LW算法的CV值遠遠優(yōu)于MDDMproj、RF-ML、LWMF和WFSNR這4種算法。HL指標下,當NF=50時,MI-LW算法的HL值遠遠優(yōu)于其他5種對比算法。當NF> 50時,MI-LW算法的HL值雖有所上升,但仍優(yōu)于MDDMproj、RF-ML、LWMF和WFSNR這4種算法,并且在絕大多數(shù)NF值上,MI-LW算法的HL值優(yōu)于WFSAM算法。RL指標下,當NF=100時,MI-LW算法的RL值取得最優(yōu)。當150

為了更清晰地了解6種算法在上述5個指標下的最優(yōu)值的對比結(jié)果,表4列出了6種算法(MDDMproj、RF-ML、LWMF、WFSAM、WFSNR和MI-LW)在4個數(shù)據(jù)集(Yeast、Education、Arts和Social)上的關(guān)于5個指標(NF、AP、CV、HL和RL)上的分類結(jié)果。從表4中可以明顯看出,在AP指標下,MI-LW算法的AP值在Education、Arts和Social這3個數(shù)據(jù)集上取得最優(yōu)。在Yeast數(shù)據(jù)集上,MI-LW算法的AP值僅比最優(yōu)WFSNR算法的AP值低了0.005 1,但它的NF值比WFSNR算法低了30。在CV指標下,MI-LW算法的CV值在Education數(shù)據(jù)集和Arts數(shù)據(jù)集上取得最優(yōu)。在Yeast數(shù)據(jù)集上,MI-LW算法的CV值比WFSNR算法的CV值高了0.053 4,但它的NF值比WFSNR算法低了30;在Social數(shù)據(jù)集上,MI-LW算法的CV值比WFSAM算法和LWMF算法的CV值高了0.060 3和0.046 7,但它的NF值比WFSAM算法和LWMF算法低了100和500。在HL指標下,MI-LW算法的HL值在Education數(shù)據(jù)集、Arts數(shù)據(jù)集和Social數(shù)據(jù)集上取得最優(yōu)。在Yeast數(shù)據(jù)集上,MI-LW算法的HL值比WFSNR算法的HL值高了0.005 1,但它的NF值比WFSNR算法低了30。在RL指標下,MI-LW算法的RL值在Education數(shù)據(jù)集、Arts數(shù)據(jù)集和Social數(shù)據(jù)集上取得最優(yōu),在Yeast數(shù)據(jù)集上,MI-LW算法的RL值比WFSNR算法的RL值高了0.004 2,但它的NF值比WFSNR算法低了30。因此,綜合5個指標來看,MI-LW算法的分類性能優(yōu)于其他5種對比算法。

表4 4個數(shù)據(jù)集上6種算法的5個指標的對比結(jié)果

3.3 統(tǒng)計分析

接下來,本節(jié)使用Friedman統(tǒng)計檢驗[26]和Bonferroni-Dunn統(tǒng)計檢驗[24]來討論所有算法對于各個評價指標的統(tǒng)計結(jié)果,計算公式為

(11)

(12)

根據(jù)表2的實驗結(jié)果,MI-LW算法和其他3種對比算法:ReliefF、ReliefF+I-Cor和I-ReliefF+Cor在5種指標上的平均排名對應(yīng)的χF2和FF值如表5所示,對應(yīng)的CD圖如圖2所示。

表5 4種算法在5個評價指標上的統(tǒng)計結(jié)果

由表5分析可知,在顯著性水平α取值為0.1時,則qα=2.128,CD=1.468 5,其中T=7,s=4。從圖2中可以明顯看出MI-LW算法在AP、CV、RL和OE這4個指標下都優(yōu)于其他3種對比算法。在AP和CV這2個指標下,MI-LW算法明顯優(yōu)于ReliefF算法和I-ReliefF+Cor算法,且MI-LW算法與ReliefF算法具有顯著差異;在HL指標下,MI-LW算法明顯優(yōu)于ReliefF和I-ReliefF+Cor這2種算法,且MI-LW算法與ReliefF算法具有顯著差異;在RL指標下,MI-LW算法明顯優(yōu)于ReliefF算法和ReliefF+I-Cor算法,且MI-LW算法與ReliefF算法具有顯著差異;在OE指標下,MI-LW算法明顯優(yōu)于ReliefF算法和I-ReliefF+Cor算法,且MI-LW算法與其他3種算法具有顯著差異。

圖2 ML-KNN分類器下4種算法的Bonferroni-Dunn測試結(jié)果

根據(jù)表3的實驗結(jié)果,MI-LW算法和其他7種對比算法:MDDMspc算法、MDDMproj算法、PMU算法、MLNB算法、MUCO算法、WFSNR算法及WFSAM算法在4種指標上的平均排名對應(yīng)的χF2和FF值如表6所示,對應(yīng)的CD圖如圖3所示。

表6 8種算法在4個評價指標上的統(tǒng)計結(jié)果

由表6分析可知,在顯著性水平α取值為0.1時,則qα=2.450,CD=4.243 5,其中T=4,s=8。從圖3中可以明顯看出MI-LW算法在4個指標下都優(yōu)于其他7種對比算法。在AP指標和CV指標下,MI-LW算法的性能明顯優(yōu)于MDDMproj算法、WFSNR算法、PMU算法和WFSAM算法;在RL指標和OE指標下,MI-LW算法的性能明顯優(yōu)于WFSNR算法、MLNB算法、MDDMproj算法和WFSAM算法;在AP、RL、OE和CV這4個指標下,MI-LW算法與其余7種對比算法具有顯著差異。

圖3 ML-KNN分類器下8種算法的Bonferroni-Dunn測試結(jié)果

根據(jù)表4的實驗結(jié)果,MI-LW算法和其他5種對比算法:MDDMproj算法、RF-ML算法、LWMF算法、WFSAM算法及WFSNR算法在4種指標上的平均排名對應(yīng)的χF2和FF值如表7所示,對應(yīng)的CD圖如圖4所示。由表7分析可知,在顯著性水平α取值為0.1時,則qα=2.326,CD=3.077 0,其中T=4,s=6。從圖4可以看出,MI-LW算法在4個指標上優(yōu)于其他5種對比算法。在AP、CV、HL和RL這4個指標下,MI-LW的性能明顯優(yōu)于RF-ML、MDDMproj與WFSNR這3種算法;在AP指標下,MI-LW算法與其他5種算法具有顯著差異;在CV、HL和RL這3個指標下,MI-LW算法與MDDMproj和RF-ML這2種算法具有顯著差異。

表7 6種算法在4個評價指標上的統(tǒng)計結(jié)果

圖4 ML-KNN分類器下6種算法的Bonferroni-Dunn測試結(jié)果

4 結(jié)語

目前,一些多標記特征選擇算法未充分考慮特征和標記之間的相關(guān)性，并且傳統(tǒng)ReliefF算法中樣本之間分類間隔較大導(dǎo)致出現(xiàn)分類無意義,以及算法分類精度偏低的問題,為了解決上述缺陷,設(shè)計了一種基于標記相關(guān)性和改進ReliefF的多標記特征選擇方法。首先,為了有效反映特征與標記集的相關(guān)性并提高算法的分類精度,使用正類樣本在標記集合中的所占比例給出標記權(quán)重定義,通過結(jié)合互信息和標記權(quán)重提出了特征與標記集合之間的相關(guān)度。然后,為了解決傳統(tǒng)ReliefF算法中因樣本間距離過大導(dǎo)致異類樣本和同類樣本失效的不足,引入傳統(tǒng)ReliefF算法中的距離分別計算樣本與最近鄰異類樣本、最近鄰?fù)悩颖镜木嚯x,基于異類樣本和同類樣本數(shù)量提出了新的樣本分類間隔,結(jié)合標記權(quán)重與分類間隔給出了一種新的特征權(quán)值更新公式。最后,結(jié)合標記相關(guān)性和改進的ReliefF算法,構(gòu)建了一種新的多標記特征選擇算法。在7個多標記數(shù)據(jù)集上使用6個評價指標與相關(guān)多標記特征選擇算法進行對比分析,仿真實驗結(jié)果表明了所提算法是有效的。但是,當數(shù)據(jù)集的標記集為稀疏矩陣時,所提算法無法很好地處理此類數(shù)據(jù)集。因此,在以后的研究工作中,針對缺失標記數(shù)據(jù)集,結(jié)合粗糙集、聚類等理論,研究弱監(jiān)督特征選擇方法。