基于標(biāo)記相關(guān)性和ReliefF的多標(biāo)記特征選擇

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

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

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

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

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

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

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

1 基礎(chǔ)理論

1.1 熵與互信息

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

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

(1)

在MLDS=〈U，C，D，T〉中,任意兩個(gè)樣本子集X、Y?U,xi∈X和yj∈Y(i,j=1, 2, …,n),p(xi,yj)為兩個(gè)樣本xi和yj的先驗(yàn)概率,則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àn)概率,則Y在給定X下的條件熵[10]表示為

(3)

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

(4)

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

1.2 大間隔

在MLDS=〈U，C，D，T〉中,對(duì)于任意的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),對(duì)于任意的X?U,xi∈X(i=1, 2, …,n)，則第i個(gè)特征的權(quán)重可被計(jì)算[20]為

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

(6)

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

2 多標(biāo)記特征選擇方法

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

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

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

(7)

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

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

(8)

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

2.2 改進(jìn)的多標(biāo)記ReliefF

為了解決原有的ReliefF方法會(huì)因樣本間距離過(guò)大,導(dǎo)致異類樣本和同類樣本失去原有度量特征重要性的作用,引入異類樣本和同類樣本數(shù)量來(lái)消除該影響,并結(jié)合定義1的標(biāo)記權(quán)重公式,改進(jìn)多標(biāo)記ReliefF模型,進(jìn)而構(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), 對(duì)任意的特征f∈F,任意兩個(gè)樣本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)表示標(biāo)記l中xi的最近鄰異類樣本;NHl(xi)表示標(biāo)記l中xi的最近鄰?fù)悩颖?df(xi, NMl(xi))表示在特征f下樣本xi在標(biāo)記l中與其最近鄰異類樣本的距離,df(xi, NHl(xi))表示在特征f下樣本xi在標(biāo)記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é)合標(biāo)記權(quán)重和樣本分類間隔定義特征權(quán)值更新公式為

(11)

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

2.3 算法描述

首先,計(jì)算標(biāo)記所占的比例權(quán)重,得到標(biāo)記權(quán)重;其次,計(jì)算每個(gè)特征和標(biāo)記集之間的相關(guān)度,根據(jù)相關(guān)度的值初次篩選出特征子集;然后,根據(jù)式(11)得出特征權(quán)重值;最后,根據(jù)特征重要性權(quán)值選出最終特征排序。由此,設(shè)計(jì)基于互信息的標(biāo)記相關(guān)性并結(jié)合基于標(biāo)記權(quán)重的ReliefF的多標(biāo)記特征選擇(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)計(jì)算標(biāo)記和特征之間的互信息

Step4 End For

Step5 End For

Step6 For eachlk∈D

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

Step8 End For

Step9 For eachf∈C

Step10 For eachl∈D

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

Step12 End For

Step13 End For

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

/*Multi-Label-ReliefF模塊*/

Step15 For eachxi∈U

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

Step17 End For

Step18 對(duì)標(biāo)記權(quán)重W(lk)歸一化

Step19 For eachf∈C

Step20 For eachxi∈U

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

Step22 End For

Step23 End For

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)準(zhǔn)備

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

表1 7個(gè)多標(biāo)記數(shù)據(jù)集描述

3.2 ML-KNN下的實(shí)驗(yàn)結(jié)果

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

從表2中可以看出,在AP指標(biāo)上,MI-LW算法在Emotions、Education、Social、Yeast、Flags和Arts這6個(gè)數(shù)據(jù)集上均取得最優(yōu);在Health數(shù)據(jù)集上,MI-LW算法為次優(yōu),與ReliefF+I-Cor持平,比ReliefF高了0.063 3。在CV指標(biāo)上,MI-LW算法在Emotions、Health、Yeast和Flags這4個(gè)數(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指標(biāo)下,MI-LW算法在Education、Health、Social和Arts這4個(gè)數(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指標(biāo)上,MI-LW算法在Emotions、Social、Yeast和Flags這4個(gè)數(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指標(biāo)上,MI-LW算法在Emotions、Education、Social和Arts這4個(gè)數(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,該實(shí)驗(yàn)充分驗(yàn)證了MI-LW算法的有效性。

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

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

從表3中可以看出,在AP指標(biāo)上,MI-LW算法在Health、Yeast和Flags這3個(gè)數(shù)據(jù)集上均為最優(yōu);在Emotions數(shù)據(jù)集上,MI-LW算法為次優(yōu),僅比最優(yōu)算法MUCO低了0.000 5,但比其他對(duì)比算法高了0.001 6～0.066 9。在RL指標(biāo)上,MI-LW算法在Health、Yeast和Flags這3個(gè)數(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指標(biāo)上,MI-LW算法在Health和Flags這2個(gè)數(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指標(biāo)上,MI-LW算法在Health、Yeast和Flags這3個(gè)數(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算法基本持平。對(duì)于Emotions數(shù)據(jù)集,MI-LW算法在4個(gè)指標(biāo)上均未取得最優(yōu),Emotions數(shù)據(jù)集的標(biāo)記集為稀疏矩陣,且標(biāo)記分布也較為集中,導(dǎo)致MI-LW算法在Emotions數(shù)據(jù)集上性能不佳。

表3 4個(gè)數(shù)據(jù)集上8種算法的4個(gè)指標(biāo)對(duì)比結(jié)果

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

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

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

為了更清晰地了解6種算法在上述5個(gè)指標(biāo)下的最優(yōu)值的對(duì)比結(jié)果,表4列出了6種算法(MDDMproj、RF-ML、LWMF、WFSAM、WFSNR和MI-LW)在4個(gè)數(shù)據(jù)集(Yeast、Education、Arts和Social)上的關(guān)于5個(gè)指標(biāo)(NF、AP、CV、HL和RL)上的分類結(jié)果。從表4中可以明顯看出,在AP指標(biāo)下,MI-LW算法的AP值在Education、Arts和Social這3個(gè)數(shù)據(jù)集上取得最優(yōu)。在Yeast數(shù)據(jù)集上,MI-LW算法的AP值僅比最優(yōu)WFSNR算法的AP值低了0.005 1,但它的NF值比WFSNR算法低了30。在CV指標(biāo)下,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指標(biāo)下,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指標(biāo)下,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個(gè)指標(biāo)來(lái)看,MI-LW算法的分類性能優(yōu)于其他5種對(duì)比算法。

表4 4個(gè)數(shù)據(jù)集上6種算法的5個(gè)指標(biāo)的對(duì)比結(jié)果

3.3 統(tǒng)計(jì)分析

接下來(lái),本節(jié)使用Friedman統(tǒng)計(jì)檢驗(yàn)[26]和Bonferroni-Dunn統(tǒng)計(jì)檢驗(yàn)[24]來(lái)討論所有算法對(duì)于各個(gè)評(píng)價(jià)指標(biāo)的統(tǒng)計(jì)結(jié)果,計(jì)算公式為

(11)

(12)

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

表5 4種算法在5個(gè)評(píng)價(jià)指標(biāo)上的統(tǒng)計(jì)結(jié)果

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

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

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

表6 8種算法在4個(gè)評(píng)價(jià)指標(biāo)上的統(tǒng)計(jì)結(jié)果

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

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

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

表7 6種算法在4個(gè)評(píng)價(jià)指標(biāo)上的統(tǒng)計(jì)結(jié)果

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

4 結(jié)語(yǔ)

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