不平衡標(biāo)記差異性多標(biāo)記特征選擇算法

王一賓，吳 陳，程玉勝，江健生

1)安慶師范大學(xué)計(jì)算機(jī)與信息院，安徽安慶 246133；2)安徽省高校智能感知與計(jì)算重點(diǎn)實(shí)驗(yàn)室，安徽安慶 246133

現(xiàn)實(shí)世界廣泛存在著多標(biāo)記學(xué)習(xí)對象，多標(biāo)記學(xué)習(xí)已日漸成為機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和深度學(xué)習(xí)[1-2]等領(lǐng)域的研究熱點(diǎn)之一．這些標(biāo)記之間并非相互獨(dú)立的，而是有著一定的關(guān)聯(lián)，如一篇新聞報(bào)道可能同時(shí)屬于“經(jīng)濟(jì)”、“體育”和“國家”；人的面部表情可能同時(shí)被“開心”、“激動”和“興奮”等標(biāo)記．因此，如何利用標(biāo)記的相關(guān)性構(gòu)造出泛化性較強(qiáng)的分類器是多標(biāo)記學(xué)習(xí)的關(guān)鍵之一[3]．劉軍煜等[4]通過挖掘標(biāo)記之間的關(guān)聯(lián)性，提出一種關(guān)聯(lián)規(guī)則挖掘的多標(biāo)記分類算法．何志芬等[5]提出基于多標(biāo)記分類和標(biāo)記相關(guān)性的聯(lián)合學(xué)習(xí)．蔡亞萍等[6]利用標(biāo)記的局部相關(guān)性進(jìn)行多標(biāo)記學(xué)習(xí)和分類．吳磊等[7]通過構(gòu)建標(biāo)記的類屬屬性提出基于類屬屬性的多標(biāo)記學(xué)習(xí)算法．王一賓等[8]通過關(guān)聯(lián)規(guī)則分析標(biāo)記空間并提出一種基于回歸核極限學(xué)習(xí)機(jī)的多標(biāo)記分類算法．例如，在某個(gè)實(shí)例中，是否有該標(biāo)記與實(shí)例的特征屬性密切相關(guān)，如“感冒”和“肺炎”都有“發(fā)燒”和“咳嗽”癥狀，但若還有“流鼻涕”癥狀，則“感冒”的可能性要大于“肺炎”，此現(xiàn)象被稱為標(biāo)記的不平衡性．標(biāo)記的不平衡性廣泛存在于現(xiàn)實(shí)世界中，也正是由于標(biāo)記的不平衡性造成了不同標(biāo)記對樣本實(shí)例的描述程度存在一定的差異性，有些標(biāo)記出現(xiàn)的頻率較多，能描述大部分的樣本；而有些標(biāo)記僅僅存在于少量樣本中，但往往這一小部分的標(biāo)記卻包含了很多信息．可見，實(shí)例的特征會直接影響到標(biāo)記的結(jié)果，因此，研究特征與標(biāo)記的相關(guān)性十分重要．

傳統(tǒng)處理不平衡性標(biāo)記的方法大多是先通過抽樣或重采樣將不平衡數(shù)據(jù)處理為平衡數(shù)據(jù)再進(jìn)行研究，但是這種方式常會改變原數(shù)據(jù)集屬性，丟失部分信息，降低分類器的分類精度．若能將不同標(biāo)記包含的信息加入到分類過程中，則不僅能保留特征空間的原始屬性，還能提高分類器的精度．在多標(biāo)記學(xué)習(xí)中，為更準(zhǔn)確的描述樣本實(shí)例，往往需要大量特征，且特征越多描述越準(zhǔn)確．但隨著特征數(shù)據(jù)的增加，弱相關(guān)特征和冗余特征也增多，嚴(yán)重影響到分類器的分類精度，甚至造成誤分類．因此，需先對特征數(shù)據(jù)進(jìn)行降維．特征選擇是一種廣泛使用且有效的降維方法，經(jīng)過解析樣本特征與標(biāo)記之間的相關(guān)性，選擇出相關(guān)性高且冗余性小的特征作為特征子集進(jìn)行分類訓(xùn)練與預(yù)測[9]．張振海等[10]提出一類基于信息熵的多標(biāo)記特征選擇算法．劉景華等[11]基于互信息提出基于局部子空間的特征選擇算法．LIN等[12-13]通過擴(kuò)展互信息提出一種基于鄰域互信息的多標(biāo)記特征選擇算法，進(jìn)而又提出一種基于模糊互信息的特征選擇算法．

研究發(fā)現(xiàn)，在多標(biāo)記學(xué)習(xí)中，由于標(biāo)記對樣本的描述存在差異性，即在每個(gè)標(biāo)記下正類與負(fù)類出現(xiàn)的頻率不一樣，這種標(biāo)記頻率分布可為多標(biāo)記學(xué)習(xí)的研究提供一定的輔助信息，從而提高分類的精度[14]．本研究提出一種不平衡標(biāo)記差異性多標(biāo)記特征選擇(multi-label feature selection algorithm with imbalance label otherness, MSIO)算法，首先計(jì)算標(biāo)記空間中，記錄每個(gè)標(biāo)記下正標(biāo)記(正類)樣本和負(fù)標(biāo)記(負(fù)類)樣本出現(xiàn)的頻率分布，并作為相應(yīng)標(biāo)記的權(quán)值保存在權(quán)值矩陣中；其次，考慮到標(biāo)記空間中的標(biāo)記包含一些輔助信息結(jié)合信息熵設(shè)計(jì)相應(yīng)的度量方法以度量特征與標(biāo)記之間的相關(guān)性；最后，根據(jù)所構(gòu)造出的模型提出不平衡標(biāo)記差異性多標(biāo)記特征選擇算法．在11個(gè)常用公開數(shù)據(jù)集上與5個(gè)常用的多標(biāo)記特征選擇算法[15]對比，證明MSIO算法可提高分類器的分類精度．

1 相關(guān)知識

1.1 多標(biāo)記學(xué)習(xí)框架

多標(biāo)記學(xué)習(xí)是一種針對實(shí)際生活中普遍存在的多義性現(xiàn)象的學(xué)習(xí)框架，在此框架下，樣本由多個(gè)特征和多個(gè)標(biāo)記構(gòu)成，學(xué)習(xí)目的是將未知的實(shí)例對應(yīng)上更多正確的標(biāo)記[16]．

假設(shè)T是由n個(gè)特征組成的特征集合T={t1,t2, …,tn}，L是由m個(gè)標(biāo)記組成的標(biāo)記集合L={l1,l2, …,lm}， 在標(biāo)記集合中，有該標(biāo)記為1，否則為0，則含有z個(gè)樣本的多標(biāo)記數(shù)據(jù)集表示為

DataSet={(Ti,Li)|1≤i≤z,Ti∈T，Li∈L}

(1)

1.2 信息熵與互信息

定義1[11]若X={x1,x2, …,xm}為隨機(jī)變量，xi的概率為p(xi)， 則X的不確定性期望為

(2)

H(X)亦被稱為隨機(jī)變量X的熵，其值越小表示X的期望和不確定性程度越?。?/p>

定義2[11]設(shè)隨機(jī)變量X={x1,x2, …,xm}和Y={y1,y2, …,yn}， 則X和Y的聯(lián)合熵為

(3)

定義3[11]設(shè)隨機(jī)變量X={x1,x2, …,xm}，Y={y1,y2, …,yn}， 則Y在X條件下的條件熵為

(4)

H(Y|X)可用來度量Y在給定X時(shí)的不確定性程度．

定義4[11]若X和Y為已給定的隨機(jī)變量，則定義X與Y之間的互信息為

(5)

I(X;Y)用于衡量隨機(jī)變量X和Y的相關(guān)性，I(X;Y)越大，表明X與Y之間的相關(guān)性越大．同時(shí)，互信息還滿足以下關(guān)系

I(X;Y)=H(X)+H(Y)-H(X,Y)=

H(X)-H(X|Y)=

H(Y)-H(Y|X)

(6)

2 不平衡標(biāo)記差異性多標(biāo)記特征選擇

2.1 特征與標(biāo)記集合的互信息

在多標(biāo)記學(xué)習(xí)中，一個(gè)樣本由多個(gè)特征和標(biāo)記描述，則特征與標(biāo)記集合之間的互信息可定義為：

定義5[11]對于給定描述樣本的特征f和標(biāo)記集合L={l1,l2, …,lm}， ?li∈L，i=1, 2,…,m， 若特征f與標(biāo)記li之間的互信息為I(f;li)， 則特征f與標(biāo)記集合L之間的互信息為

(7)

由I(f;li)≥0可知， IML(f;L)≥0． 當(dāng)f和L相互獨(dú)立時(shí)，等號成立，此時(shí)特征與標(biāo)記之間不提供任何信息，即該特征與標(biāo)記空間互信息為最小值． 互信息值越大， 特征與標(biāo)記之間的關(guān)系越密切．

同理，式(8)和式(9)成立．

IML(f;L)=IML(L;f)

(8)

(9)

根據(jù)式(9)可得，若

(10)

則表明標(biāo)記集合L可完全由特征f確定，兩者的不確定度之和取得最大值．

2.2 不平衡標(biāo)記差異性多標(biāo)記特征選擇模型

在多標(biāo)記數(shù)據(jù)集中，常因標(biāo)記的不平衡性導(dǎo)致不同標(biāo)記對樣本描述程度有所不同，而目前多數(shù)算法并未考慮這種情況．為此，本研究根據(jù)標(biāo)記空間中的每個(gè)標(biāo)記下的正負(fù)樣本個(gè)數(shù)對標(biāo)記賦予權(quán)值，建立標(biāo)記權(quán)值模型，具體定義為：

對于傳統(tǒng)的單標(biāo)記運(yùn)用互信息進(jìn)行特征選擇過程中，假使用兩個(gè)特征f1和f2對樣本進(jìn)行刻畫，則對于特征與特征之間的冗余性用I(f1;f2)進(jìn)行有效表示；倘若樣本的特征用給定的f表示，樣本的類別標(biāo)記用l表示，則對于特征與標(biāo)記類別之間的相關(guān)程度用I(f;l)進(jìn)行有效表示．而在現(xiàn)有的多標(biāo)記學(xué)習(xí)中，各個(gè)樣本可用1個(gè)特征向量來表示，也可能隸屬于多個(gè)類別標(biāo)記，同時(shí)，充分考慮到標(biāo)記權(quán)值模型下的各樣本所含有的有用信息，因此需對加權(quán)特征和標(biāo)記集合之間的相關(guān)性進(jìn)行更深層次的探究.定義7給出了加權(quán)特征與標(biāo)記集合之間的互信息定義.

定義7對于給定樣本空間U={x1,x2,…,xz}， 標(biāo)記空間L={l1,l2, …,lm}， ?li∈L，i=1,2,…,m, 由定義6和式(7)可知，加權(quán)特征f與標(biāo)記之間的互信息為

(11)

2.3 MSIO算法描述

考慮到標(biāo)記對樣本的描述存在一定的差異性，為使描述的樣本實(shí)例更準(zhǔn)確，同時(shí)也為了更充分地挖掘存在于少量樣本中但包含眾多有用信息的一些標(biāo)記，首先計(jì)算標(biāo)記空間中同一標(biāo)記下正負(fù)標(biāo)記的權(quán)值；其次，利用加權(quán)信息熵度量特征與標(biāo)記空間之間的相關(guān)性，并由此得出兩組不同的特征重要度排序；最后，將兩組重要度不同的特征進(jìn)行融合排序，得出最終特征序列．MSIO算法偽代碼如圖1．

輸入:多標(biāo)記訓(xùn)練集D輸出:排序后的特征序列rank1) IML=?;2)for each fi∈F3) rank=?4) for each lj∈L5) 根據(jù)定義5計(jì)算和IML(fi; L+j)和IML(fi; L-j)6) end7) 根據(jù)式(11)計(jì)算每個(gè)特征fi在同一標(biāo)記的不同情況下的互信息8)end9)根據(jù)7)得到的互信息降序排序,得到正標(biāo)記的特征序列rank+和負(fù)標(biāo)記的特征序列rank-10)對rank+和rank-融合排序,得到最終序列rank,并輸出

圖1 MSIO算法偽代碼

Fig.1 Pseudocode of MSIO algorithm

分析圖1的算法可見，MSIO算法先通過統(tǒng)計(jì)標(biāo)記空間中類標(biāo)記下的正負(fù)標(biāo)記密度，然后計(jì)算標(biāo)記空間與特征空間的相關(guān)性，并按照標(biāo)記密度對特征進(jìn)行賦權(quán)得分輸出兩組序列，再按照一定關(guān)系對兩組序列加權(quán)得出最終序列．此方法簡單易行且運(yùn)行快速，既考慮了多種因素，又能有效提高分類器的分類精度．MSIO算法流程圖如圖2．

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

采用Mulan數(shù)據(jù)庫[16]中11個(gè)常用的公開實(shí)驗(yàn)數(shù)據(jù)集 (表1)，來驗(yàn)證算法MSIO的有效性．

3.2 評價(jià)指標(biāo)

利用平均準(zhǔn)確率(average precision, AP)、排位損失(ranking loss, RL)、1-錯(cuò)誤(one-error, OE)和海明損失(Hamming loss, HL) 4個(gè)評價(jià)指標(biāo)[18]對多標(biāo)記實(shí)驗(yàn)實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證和評價(jià)度量．

AP為評估預(yù)測標(biāo)記排在前列且正確存在于相關(guān)樣本標(biāo)記的平均概率，如式(12)．該值越大表示分類效果越好，最優(yōu)值為1．

(12)

其中，Yi為隸屬于樣本xi的相關(guān)標(biāo)記集合．

RL用于評估無關(guān)標(biāo)記在相關(guān)標(biāo)記的樣本前列的多少，如式(13)．該值越小表示分類效果越好，最優(yōu)值為0．

(13)

HL用于衡量樣本在單一標(biāo)記上的非正確匹配情況，如式(14)．該值越小，分類效果越好，最優(yōu)值為0．

(14)

其中，Yi為隸屬于xi的相關(guān)標(biāo)記集合；h(·)為分類器，即可得xi的預(yù)測標(biāo)記向量．

OE用于衡量最高排序中樣本的標(biāo)記不存在于相關(guān)標(biāo)記集合中的情況，如式(15)．該值越小，表示分類效果越好，最優(yōu)值為0．

(15)

在4個(gè)評價(jià)指標(biāo)中，除去AP值越大越優(yōu)，其余的越小越優(yōu)．

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

本研究實(shí)驗(yàn)代碼均在Matlab2016a中運(yùn)行，硬件環(huán)境Inter?CoreTMi7-7700HQ CPU @ 2.80 GHz，8 Gbyte內(nèi)存；操作系統(tǒng)為Windows 10．以多標(biāo)記k近鄰(multi-labelk-nearest neighbor, ML-kNN)[19]作為基礎(chǔ)分類器，對基于最大相關(guān)性的多標(biāo)記維數(shù)約簡(multi-label dimensionality reduction via dependence maximization, MDDM)算法[20-21]、基于多變量互信息的多標(biāo)記特征選擇算法PMU(pairwise multivariate mutual information)[22]、 多標(biāo)記樸素貝葉斯分類的特征選擇(feature selection for multi-label naive Bayes classification, MLNB)算法[23]、 基于標(biāo)記相關(guān)性的多標(biāo)記特征選擇(multi-label feature selection with label correlation, MUCO)算法[13]和MSIO算法的AP、RL、OE和HL值進(jìn)行排序．其中，MDDM算法按照參數(shù)所選擇的不同分為MDDMspc與MDDMproj算法．由于MDDM、PMU、MUCO和MSIO算法得到的是一組特征序列，于是設(shè)置特征子集的個(gè)數(shù)與MLNB算法一致，并設(shè)ML-kNN中的平滑系數(shù)s=1， 近鄰個(gè)數(shù)k=10． 表2至表5列舉了6種算法在數(shù)據(jù)集中的AP、RL、OE和HL值．

表2 六種算法在11個(gè)數(shù)據(jù)集中的平均準(zhǔn)確率排序1)Table 2 Average precision ranking of 6 algorithms in 11 datasets

1)平均準(zhǔn)確率指標(biāo)越大越好，灰底數(shù)值表示在該指標(biāo)上取得的最優(yōu)結(jié)果； 2)括號內(nèi)數(shù)字表示在11個(gè)數(shù)據(jù)集中算法獲得最優(yōu)值的個(gè)數(shù) 表3 六種算法在11個(gè)數(shù)據(jù)集中的排位損失排序1)Table 3 Ranking loss of 6 algorithms in 11 datasets

1)排位損失指標(biāo)越小越好，灰底數(shù)值表示在該指標(biāo)上取得的最優(yōu)結(jié)果；2)括號內(nèi)的數(shù)字表示在11個(gè)數(shù)據(jù)集中算法獲得最優(yōu)值的個(gè)數(shù)

表4 六種算法在11個(gè)數(shù)據(jù)集中的1-錯(cuò)誤上排序1)Table 4 One-error ranking of 6 algorithms in 11 datasets

1)1-錯(cuò)誤指標(biāo)越小越好，灰底數(shù)值表示在該指標(biāo)上取得的最優(yōu)結(jié)果；2)括號內(nèi)數(shù)字表示在11個(gè)數(shù)據(jù)集中算法獲得最優(yōu)值的個(gè)數(shù)

(續(xù)表5)

1)海明損失指標(biāo)越小越好，灰底數(shù)值表示在該指標(biāo)上取得的最優(yōu)結(jié)果；2)括號內(nèi)數(shù)字表示在11個(gè)數(shù)據(jù)集中算法獲得最優(yōu)值的個(gè)數(shù)

由表2至表5可見：

1)MSIO算法在4種評價(jià)指標(biāo)中的最優(yōu)數(shù)目和平均值均位列第1，且在Art、Computer、Rec和Ref數(shù)據(jù)集中的所有評價(jià)指標(biāo)均優(yōu)于其他算法．

2)在AP指標(biāo)上，僅MUCO算法在部分?jǐn)?shù)據(jù)集上占優(yōu)，但最優(yōu)的Cal500數(shù)據(jù)集也僅提高了2.15%；在RL指標(biāo)上，6種算法各有千秋，其中，在Emotions數(shù)據(jù)集中MDDMspc算法占優(yōu)最大，為11.12%；在OE和HL指標(biāo)上，最優(yōu)的分別高7.46%和3.58%．

圖3為6種算法在不同評價(jià)指標(biāo)上的箱型圖．由圖3可見，6種算法在4種評價(jià)指標(biāo)上展現(xiàn)的分類性能對比中，MSIO算法在箱形圖中的中位數(shù)表現(xiàn)明顯占優(yōu)．可見，MSIO算法穩(wěn)定性更好的，且分類精度更高，性能優(yōu)于其他特征選擇算法．

圖3 六種算法在不同評價(jià)指標(biāo)上的箱型圖Fig.3 Box-plot of six algorithms on different evaluation indexes

3.4 算法性能統(tǒng)計(jì)分析

運(yùn)用統(tǒng)計(jì)學(xué)知識，對在11個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果進(jìn)行顯著性水平為5%的Nemenyi統(tǒng)計(jì)假設(shè)檢驗(yàn)，若在所有數(shù)據(jù)集上兩個(gè)對比算法平均排序的差低于臨界差(critical difference, CD)，則認(rèn)為它們無顯著性差異，否則，認(rèn)為這兩個(gè)對比算法有顯著性差異．本研究設(shè)顯著性水平α=0.05，qα=2.850(第k個(gè)對應(yīng)數(shù))， 算法個(gè)數(shù)k=6， 數(shù)據(jù)集個(gè)數(shù)N=11，則

(16)

圖4給出了各個(gè)算法在不同評價(jià)指標(biāo)下的對比．坐標(biāo)軸上的刻度描述了各種算法在不同指標(biāo)中的平均排序，軸上數(shù)字越小，表明算法性能越優(yōu)．不同線型相接的算法表示在性能之間無顯著性差異．由圖4可見，MSIO算法排名除在RL指標(biāo)上比MUCO稍微遜色，在其余指標(biāo)中均明顯較優(yōu)．

圖4 各算法Nemenyi檢驗(yàn)的性能對比Fig.4 Performance comparison of Nemenyi test of each algorithm

結(jié) 語

通過對不同標(biāo)記在樣本空間的描述程度存在一定的差異性的思考，結(jié)合信息熵的相關(guān)知識，提出一種不平衡標(biāo)記差異性特征選擇算法MSIO，通過不同標(biāo)記下的正負(fù)標(biāo)記權(quán)值修正傳統(tǒng)的信息熵，由于加入了標(biāo)記空間的信息，使選出的特征具有更加豐富的信息．在多組數(shù)據(jù)集上的多個(gè)評價(jià)指標(biāo)中，MSIO算法性能都優(yōu)于目前多數(shù)的特征選擇算法．但是，MSIO算法在進(jìn)行特征選擇時(shí)僅考慮了特征與標(biāo)記的相關(guān)性，而未對特征空間本身進(jìn)行冗余性約簡，這也是下一步的研究方向．