柴瑞敏 閆 婷 (遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院 遼寧 葫蘆島 125105)

0 引 言

傳統(tǒng)的監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)研究范疇之一，其中現(xiàn)實(shí)世界的每個(gè)對象由單個(gè)實(shí)例表示并與單個(gè)標(biāo)簽相關(guān)，稱作單標(biāo)簽學(xué)習(xí)。傳統(tǒng)監(jiān)督學(xué)習(xí)所采用的一個(gè)基本假設(shè)是，每個(gè)例子只屬于一個(gè)概念，即具有獨(dú)特的語義意義，然而真實(shí)世界的對象可能是復(fù)雜的，同時(shí)具有多個(gè)語義意義[1]。例如，《盜夢空間》這部電影被同時(shí)賦予動(dòng)作、冒險(xiǎn)和懸疑三個(gè)標(biāo)簽。類似地，在醫(yī)學(xué)診斷中，患者可能同時(shí)患有糖尿病和前列腺癌，這些不同于單標(biāo)簽分類，將一個(gè)實(shí)例同時(shí)涉及到多個(gè)標(biāo)簽的問題稱為多標(biāo)簽學(xué)習(xí)。近年來，研究者注意到現(xiàn)代智能信息處理越來越多地需要多標(biāo)簽分類方法，如音樂情感分類[2]、文本分類和基因功能組[3]。在音樂情感分類中，歌曲可以屬于多種類型，例如，流行搖滾和質(zhì)樸民謠。在文本分類中，一篇文章可能包含多個(gè)領(lǐng)域，如數(shù)學(xué)和圖像分析。

在多標(biāo)簽分類中，每個(gè)對象也是由單個(gè)實(shí)例表示，但它與一組標(biāo)簽而不是單個(gè)標(biāo)簽相關(guān)，多標(biāo)簽學(xué)習(xí)的任務(wù)就是給定一個(gè)未知實(shí)例可以正確預(yù)測它所屬的標(biāo)簽集。從多標(biāo)簽訓(xùn)練集T={(xi,Yi)|1≤i≤m}中學(xué)習(xí)一個(gè)多標(biāo)簽分類器函數(shù)h:X→2L。每個(gè)多標(biāo)簽實(shí)例(xi,Yi)，xi∈X是t維特征向量，Yi∈L是與xi相關(guān)的標(biāo)簽集合，其中，F(xiàn)={f1,f2,…,ft}是t維的特征空間，L={l1,l2,…,lq}表示具有q個(gè)可能類標(biāo)簽的標(biāo)簽空間，對任意給定的一個(gè)未知實(shí)例xi∈X，多標(biāo)簽分類器h(·)能夠預(yù)測h(x)?L的正確標(biāo)簽集合。

在學(xué)習(xí)多標(biāo)簽數(shù)據(jù)時(shí)，隨著類標(biāo)簽數(shù)量的增加，標(biāo)簽集的數(shù)量呈指數(shù)增長[1]，使得標(biāo)簽數(shù)據(jù)復(fù)雜多變，增加了標(biāo)簽預(yù)測的難度。特征與標(biāo)簽的相關(guān)性更為復(fù)雜，不同的特征對同一標(biāo)簽的分類有不同的重要度，所以應(yīng)該根據(jù)對標(biāo)簽分類的重要度對不同特征給予相應(yīng)的權(quán)重。

1 相關(guān)工作

目前處理多標(biāo)簽分類的方法可歸為兩類：問題轉(zhuǎn)換法和算法適應(yīng)法。研究者為了將復(fù)雜的問題簡單化，利用基于問題轉(zhuǎn)化方法將多標(biāo)簽分類轉(zhuǎn)化為多個(gè)單標(biāo)簽分類，如BR(Binary Relevance)二元關(guān)系法[1]，該算法的基本思想是將多標(biāo)簽分類問題分解為|q|個(gè)二類分類問題，為每一個(gè)標(biāo)簽訓(xùn)練一個(gè)二分類器，該算法雖然簡單、高效，但其忽略了標(biāo)簽間的相關(guān)性；ECC(Ensembles of Classifier Chains)集成分類器鏈[4]，該算法是對BR算法的一種改進(jìn)，將已訓(xùn)練的樣本屬性繼續(xù)代入到下一個(gè)分類器中訓(xùn)練，解決了BR算法造成的信息缺失問題，但是隨機(jī)產(chǎn)生的分類器鏈組合排序問題會(huì)對結(jié)果造成不利影響。

LP(Label Powerset)標(biāo)簽密集法[1]，該算法將訓(xùn)練集中樣本所屬的標(biāo)簽集進(jìn)行二進(jìn)制編碼，組成新的單標(biāo)簽數(shù)據(jù)，從而將多標(biāo)簽分類轉(zhuǎn)化成新的多類分類，該算法雖然考慮到了標(biāo)簽間的相關(guān)性，但是由于分類器的偏置性使得新的標(biāo)簽組合難以預(yù)測且算法復(fù)雜度較高；EPS(Ensembles of Pruned Sets)修剪組合算法[5]，該算法根據(jù)LP模型中未分類的預(yù)測樣本用概率分布模型計(jì)算標(biāo)簽組合頻次，頻次較低的將被刪除，這樣使得算法復(fù)雜度降低而且也保證了標(biāo)簽之間的相關(guān)性。

算法適應(yīng)法的思想是改進(jìn)已經(jīng)成熟的單標(biāo)簽學(xué)習(xí)算法，使之去適應(yīng)多標(biāo)簽數(shù)據(jù)，如神經(jīng)網(wǎng)絡(luò)[6]，該算法考慮了相關(guān)標(biāo)簽排序應(yīng)比不相關(guān)標(biāo)簽排序靠前，因此提出了一種排序的誤差度量函數(shù)。Clare等[7]改進(jìn)了C4.5用于單標(biāo)簽分類的經(jīng)典決策樹算法，允許葉節(jié)點(diǎn)為一個(gè)標(biāo)簽的集合，擴(kuò)展了信息熵的計(jì)算公式。Elisseeff等[8]對支持向量機(jī)算法改進(jìn)后提出一種RankSVM算法，其將SVM標(biāo)簽預(yù)測模型應(yīng)用到每個(gè)標(biāo)簽上，而后利用排序損失來衡量每個(gè)樣本的相關(guān)標(biāo)簽和不相關(guān)標(biāo)簽。

Zhang等[9]提出了ML-kNN，一種多標(biāo)簽懶惰學(xué)習(xí)算法，先計(jì)算測試樣本與訓(xùn)練樣本間的歐氏距離，從中選取最近的k個(gè)近鄰樣本作為預(yù)測標(biāo)簽，通過最大后驗(yàn)概率判斷每一個(gè)標(biāo)簽的取值，該算法優(yōu)點(diǎn)是簡單、高效，缺點(diǎn)沒有考慮多個(gè)標(biāo)簽之間的相關(guān)性。李峰等[10]提出基于互信息的?；卣骷訖?quán)多標(biāo)簽學(xué)習(xí)k近鄰算法(GFWML-kNN)，該算法把標(biāo)簽空間粒化，將特征與標(biāo)簽間的相關(guān)性融合進(jìn)特征的權(quán)重系數(shù)中，考慮了特征和標(biāo)簽之間的關(guān)系，但其采用硬劃分對標(biāo)簽空間?；?，不能有效表達(dá)標(biāo)簽在形態(tài)和類屬方面的中介性，導(dǎo)致所得的結(jié)果偏差較大，而且對于最佳粒化數(shù)目沒有合理分析。本文提出了基于模糊C均值(FCM)改進(jìn)的?；卣骷訖?quán)多標(biāo)簽分類，F(xiàn)CM算法先計(jì)算每個(gè)樣本對所有類的隸屬度，得到樣本屬于各個(gè)類的不確定性程度，這種具有樣本分類結(jié)果可靠性的計(jì)算方法，使得聚類結(jié)果更加準(zhǔn)確靈活。對標(biāo)簽空間進(jìn)行?；闷骄畔㈧卮_定最佳?；瘮?shù)目，平均信息熵能有效衡量某標(biāo)簽的歸屬程度，其值越小，結(jié)果越確定，而后利用信息增益方法對特征進(jìn)行加權(quán)，這樣既考慮了標(biāo)簽與特征的相關(guān)性，又有效地減少了標(biāo)簽的組合，降低算法復(fù)雜度。

2 基礎(chǔ)知識

2.1 模糊C劃分

本文將模糊C均值(FCM)[11-12]聚類算法應(yīng)用到標(biāo)簽空間的?；?，使用隸屬度U表示一個(gè)標(biāo)簽屬于某一標(biāo)簽粒的程度。標(biāo)簽空間L={l1,l2,…,lq}的模糊C劃分目標(biāo)函數(shù)為：

(1)

J(U,c1,…,cc,λ1,…,λq)=

(2)

式中:λj=(j=1,…,q)是q個(gè)約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮?dǎo)，得到隸屬度和粒中心的更新公式分別為：

(3)

(4)

2.2 信息增益

定義1信息增益[13]是一種量化隨機(jī)變量X和Y的關(guān)聯(lián)程度的度量。其值計(jì)算如下：

(5)

式中：p(x)表示x的概率密度;p(x,y)是x和y的聯(lián)合概率密度。

信息增益可由熵和聯(lián)合熵表示：

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

(6)

信息增益能有效描述兩個(gè)變量之間的關(guān)聯(lián)程度，信息增益越大，關(guān)聯(lián)性越高。

2.3 改進(jìn)的標(biāo)簽空間粒化及特征加權(quán)

本文采用聚類分析中的FCM聚類算法來對標(biāo)簽空間?；痆14]。在問題求解中使用的粒子用Mc表示，標(biāo)簽?；倪^程就是將一系列相似標(biāo)簽劃分為一粒，使得相似度大的被劃分到同一粒中，不同粒中相似度最小，其中每一個(gè)粒是基于相似性或者泛函性聚集得到的一個(gè)標(biāo)簽的集合。

在面對具體的復(fù)雜問題時(shí)，粒化的程度直接影響計(jì)算復(fù)雜度和效率。既要避免粒度過粗而造成達(dá)不到原預(yù)計(jì)的粒化效果，也要避免粒度過細(xì)造成信息的冗余而導(dǎo)致求解效率低下。因此，本文在?；^程中對于標(biāo)簽粒個(gè)數(shù)c用平均信息熵來確定。

定義2平均信息熵用來衡量標(biāo)簽空間中的某一標(biāo)簽歸屬于某一標(biāo)簽粒的程度，該值越小表明歸屬結(jié)果越確定，平均信息熵值可表示為：

(1-uij)×logr(1-uij)]}

(7)

首先要確定?；瘮?shù)目的范圍，即標(biāo)簽粒的個(gè)數(shù)，給出最大值和最小值，即k∈[kmin,kmax]，在計(jì)算H(k)的過程中使k從kmin增加到kmax，記錄下每次變換k所得的平均信息熵值，從中選取使得H(k)最小的粒化數(shù)目k作為最終的最佳?；瘮?shù)c。表1為對emotions[15]數(shù)據(jù)集的標(biāo)簽空間?；瘮?shù)目平均熵值表。

表1 emotions的標(biāo)簽空間粒化數(shù)目平均熵值表

如表1所示，當(dāng)?；瘮?shù)目為2時(shí)，平均信息熵取得最小值，因此，在對emotions數(shù)據(jù)集標(biāo)簽空間粒化時(shí)，?；瘮?shù)目取值為2。

在?；^程中，F(xiàn)CM算法會(huì)根據(jù)隸屬度的大小分配標(biāo)簽所屬的某一標(biāo)簽粒，但這個(gè)過程中會(huì)出現(xiàn)標(biāo)簽不平衡現(xiàn)象，因此可以采用平衡模糊C均值聚類算法[16]將標(biāo)簽均勻地分配到每個(gè)標(biāo)簽粒中，減少標(biāo)簽組合數(shù)量，標(biāo)簽粒化過程的步驟如下：

算法1標(biāo)簽?；^程.

輸入：標(biāo)簽空間L={l1,l2,…,lq}，標(biāo)簽粒個(gè)數(shù)c，訓(xùn)練集T={(xi,Yi)|1≤i≤m}，模糊指數(shù)m=2，迭代次數(shù)iter;

輸出：c個(gè)標(biāo)簽粒;

1) 初始化每個(gè)標(biāo)簽粒Mi和粒中心ci;

2) Whileiter>0

3) Forlj∈L

4) 計(jì)算lj到各個(gè)粒中心的歐氏距離dij，將循環(huán)變量flag設(shè)為真；

5) 根據(jù)式(3)計(jì)算標(biāo)簽的隸屬度值；

6) Whileflag

7) 將lj到各個(gè)標(biāo)簽粒的隸屬度進(jìn)行排序，then將lj插入到隸屬度最大的中心粒Mi，對標(biāo)簽粒Mi中的標(biāo)簽根據(jù)隸屬度值的大小進(jìn)行排序;

8) If |Mi|>「|L|/c? then

9) 將Mi中排在最后的一個(gè)標(biāo)簽lk從該標(biāo)簽粒中去除，then把lk插入到其隸屬度排名第二的標(biāo)簽粒中，以此類推；

10) Else將循環(huán)變量flag設(shè)為假；

11) End If

12) End While

13) End FOR

14) 根據(jù)式(4)更新各粒中心，迭代次數(shù)iter減1;

15) End While

16) 得到標(biāo)簽粒M1,M2,…,Mc.

由算法1得到了C個(gè)標(biāo)簽粒，同一特征對不同標(biāo)簽粒的重要性不同，信息增益能有效描述特征與標(biāo)簽粒之間的關(guān)聯(lián)程度，信息增益越大，關(guān)聯(lián)性越高，該特征越重要，相應(yīng)的權(quán)重系數(shù)越大，所以標(biāo)簽的分類信息和特征的權(quán)重系數(shù)是等價(jià)的。

(8)

式中：IG(fi;Mc)根據(jù)定義1可得：

(9)

進(jìn)而得到加權(quán)的歐氏距離，即：

(10)

隨后采用經(jīng)典的kNN算法對未知標(biāo)簽進(jìn)行預(yù)測，該算法是通過計(jì)算不同樣本之間的距離進(jìn)行分類，如果一個(gè)樣本的k個(gè)最近鄰樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。樣本間距離計(jì)算常用的就是歐氏距離，本文中加權(quán)的歐氏距離包含了特征攜帶分類信息的多少以及特征與標(biāo)簽之間的相關(guān)程度，將特征重要度的差異體現(xiàn)在樣本的距離計(jì)算中，提高了算法的分類效率及分類結(jié)果的準(zhǔn)確性。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集

本文采用了來自Mulan[17]平臺上的四個(gè)公共數(shù)據(jù)集yeast、medical、genbase、emotions作為實(shí)驗(yàn)數(shù)據(jù)，相關(guān)信息如表2所示。

表2 數(shù)據(jù)集相關(guān)信息

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

本文采用多標(biāo)簽分類常用的5大評價(jià)指標(biāo)[9]對實(shí)驗(yàn)結(jié)果進(jìn)行分析，5大評價(jià)指標(biāo)分別為HammingLoss、One-Error、Coverage、RankingLoss、AveragePrecision。為了驗(yàn)證所提算法的有效性，本實(shí)驗(yàn)將其與經(jīng)典算法RankSVM[5]、GFWML-kNN[10]、ML-kNN[9]進(jìn)行了對比，其中近鄰數(shù)k取值為10、平滑因子取值為1；本實(shí)驗(yàn)算法在所給數(shù)據(jù)集yeast、medical、genbase、emotions的標(biāo)簽粒數(shù)目由平均信息熵分別取值為3、8、7、2。如表3-表7所列是各多標(biāo)簽算法在數(shù)據(jù)集中各項(xiàng)指標(biāo)的實(shí)驗(yàn)結(jié)果。其中，表中的粗體字表示各項(xiàng)指標(biāo)的最優(yōu)值，(↑)表示取值越大，分類效果越佳；(↓)表示取值越小，分類效果越佳。

表3 多標(biāo)簽學(xué)習(xí)算法的HammingLoss(↓)比較

表4 多標(biāo)簽學(xué)習(xí)算法的OneError(↓)比較

從表3可以看出本文算法在3個(gè)多標(biāo)簽數(shù)據(jù)集上都優(yōu)于RankSVM和GFWML-kNN；而在數(shù)據(jù)集emotions中，ML-kNN算法優(yōu)于其他三個(gè)算法取得最優(yōu)。表4中的數(shù)據(jù)顯示本文算法在多個(gè)多標(biāo)簽數(shù)據(jù)集上效果明顯優(yōu)于其他算法，在yeast數(shù)據(jù)集上，RankSVM算法算法略優(yōu)于本文算法。

表5 多標(biāo)簽學(xué)習(xí)算法的Coverage(↓)比較

表6 多標(biāo)簽學(xué)習(xí)算法的RankingLoss(↓)比較

表7 多標(biāo)簽學(xué)習(xí)算法的AveragePrecision(↑)比較

從表5-表7中可以看出，表5中除RankSVM算法外的其他三個(gè)算法都在對應(yīng)數(shù)據(jù)集中取到過最優(yōu)值，本文算法分別在數(shù)據(jù)集medical和emotions上效果明顯優(yōu)于其他算法。表6中除了在數(shù)據(jù)集yeast中本文算法略低于ML-kNN算法，在其他數(shù)據(jù)集上本文算法在該項(xiàng)指標(biāo)中都優(yōu)于另外三個(gè)算法。表7中本文算法和GFWML-kNN算法的效果相當(dāng)，在不同數(shù)據(jù)集上都取到過兩次最優(yōu)，其中在yeast數(shù)據(jù)集上本文算法略高于ML-kNN算法，取得最佳效果。

圖1-圖3中分別是未?；奶卣骷訖?quán)的ML-kNN[9]算法(①)、本文算法(②)和GFWML-kNN[10]算法(③)隨著近鄰數(shù)k的選擇對標(biāo)簽相關(guān)性造成的損失，以emotions數(shù)據(jù)集為例，圖中顯示了多標(biāo)簽的5項(xiàng)評價(jià)指標(biāo)隨著k值增加的變化曲線。

(a) (b)圖1 漢明損失和1-錯(cuò)誤率隨著近鄰數(shù)k的變化曲線

(a) (b)圖2 覆蓋率和排序損失隨著近鄰數(shù)k的變化曲線

圖3 平均準(zhǔn)確率隨著近鄰數(shù)k的變化曲線

從以上三個(gè)圖中可以看到三個(gè)算法隨著近鄰數(shù)k的增加各項(xiàng)損失變化整體趨勢很接近，k從2增加到20過程中性能先快速提升，當(dāng)k=10時(shí)達(dá)到最優(yōu)，隨后逐漸略微下降。在漢明損失中未?；奶卣骷訖?quán)的ML-kNN算法損失略小于本文算法和GFWML-kNN算法，但在1-錯(cuò)誤率、覆蓋率、排序損失上，本文算法的性能優(yōu)于未?；奶卣骷訖?quán)的ML-kNN算法和GFWML-kNN算法，取得最佳；在平均準(zhǔn)確率上GFWML-kNN算法略高于本文算法，取得最優(yōu)值。

4 結(jié) 語

針對多標(biāo)簽組合呈指數(shù)增長以及特征和標(biāo)簽之間的關(guān)系影響分類結(jié)果的問題，本文提出了將標(biāo)簽空間利用FCM算法基于平均信息熵進(jìn)行?；纬傻臉?biāo)簽粒大大減少了標(biāo)簽的組合。而后用信息增益計(jì)算特征和標(biāo)簽粒的相關(guān)程度，對特征進(jìn)行加權(quán)，使得不同特征攜帶的分類信息被賦予不同的重要度。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明該方法在多標(biāo)簽分類問題中取得較好的效果。下一步研究工作將在繼續(xù)優(yōu)化該算法使之能處理含有大量標(biāo)簽的數(shù)據(jù)集上進(jìn)行開展。

[1] Zhang M L, Zhou Z H. A Review on Multi-Label Learning Algorithms[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(8):1819- 1837.

[2] Sanden C,Zhang J Z. Enhancing multi-label music genre techniques[C]// Proceedings of the 34th International ACM SIGIR Conference on Research and Development in information Retrieval(SIGIR’11). New York, USA, 2011: 705- 714.

[3] Wu J S, Huang S J, Zhou Z H. Genome-Wide Protein Function Prediction through Multi-instance Multi-label Learning[J]. IEEE/ACM Transactions on Computational Biology & Bioinformatics, 2014, 11(5):891- 902.

[4] Read J, Pfahringer B, Holmes G, et al. Classifier chains for multi-label classification[J]. Machine Learning, 2011, 85(3):333- 359.

[5] Read J, Pfahringer B, Holmes G. Multi-label Classification Using Ensembles of Pruned Sets[C]// Eighth IEEE International Conference on Data Mining. IEEE, 2009:995- 1000.

[6] Chen G, Ye D, Xing Z, et al. Ensemble application of convolutional and recurrent neural networks for multi-label text categorization[C]// International Joint Conference on Neural Networks. IEEE, 2017:2377- 2383.

[7] Clare A,King R. Knowledge discovery in multi-label phenotype data[C]//Proceedings of 5th European Conference on Principles of Data Mining and Knowledge Discovery (PKDD). Freiburg,Germany, 2001: 42- 53.

[8] Elisseeff A, Weston J. A kernel method for multi-labelled classification[C]// International Conference on Neural Information Processing Systems: Natural and Synthetic. MIT Press, 2001:681- 687.

[9] Zhang M L,Zhou Z H. ML-kNN: A lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007(40): 2038- 2048.

[10] 李峰,苗奪謙,張志飛,等.基于互信息的粒化特征加權(quán)多標(biāo)簽學(xué)習(xí)k近鄰算法[J].計(jì)算機(jī)研究與發(fā)展,2017,54(5): 1024- 1035.

[11] 文傳軍,汪慶淼,詹永照.均衡模糊C均值聚類算法[J].計(jì)算機(jī)科學(xué),2014,41(8): 250- 253.

[12] 廖松有,張繼福,劉愛琴.利用模糊熵約束的模糊C均值聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(2): 379- 383.

[13] Cover T M,Thomas J A. Elements of information theory [M]. John Wiley & Sons, 2012.

[14] 徐計(jì),王國胤,于洪.基于粒計(jì)算的大數(shù)據(jù)處理[J].計(jì)算機(jī)學(xué)報(bào),2015,38(8): 1497- 1517.

[15] Trohidis K,Tsoumakas G,Kalliris G,et al. Multi-label classification of music into emotions[J]. Eurasip Journal on Audio Speech & Music Processing, 2008, 2011(1): 325- 330.

[16] Shannon C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948, 27(4):379- 423.

[17] Tsoumakas G, Spyromitros-Xioufis E, Vilcek J, et al. MULAN: A Java library for multi-label learning[J]. Journal of Machine Learning Research, 2012, 12(7):2411- 2414.