基于模糊C均值改進的粒化特征加權多標簽分類算法

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

0 引 言

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

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

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

1 相關工作

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

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

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

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

2 基礎知識

2.1 模糊C劃分

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

(1)

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

(2)

式中:λj=(j=1,…,q)是q個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮В玫诫`屬度和粒中心的更新公式分別為：

(3)

(4)

2.2 信息增益

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

(5)

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

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

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

(6)

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

2.3 改進的標簽空間粒化及特征加權

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

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

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

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

(7)

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

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

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

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

算法1標簽粒化過程.

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

輸出：c個標簽粒;

1) 初始化每個標簽粒Mi和粒中心ci;

2) Whileiter>0

3) Forlj∈L

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

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

6) Whileflag

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

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

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

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

11) End If

12) End While

13) End FOR

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

15) End While

16) 得到標簽粒M1,M2,…,Mc.

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

(8)

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

(9)

進而得到加權的歐氏距離，即：

(10)

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

3 實 驗

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

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

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

3.2 實驗結果分析

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

表3 多標簽學習算法的HammingLoss(↓)比較

表4 多標簽學習算法的OneError(↓)比較

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

表5 多標簽學習算法的Coverage(↓)比較

表6 多標簽學習算法的RankingLoss(↓)比較

表7 多標簽學習算法的AveragePrecision(↑)比較

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

圖1-圖3中分別是未粒化的特征加權的ML-kNN[9]算法(①)、本文算法(②)和GFWML-kNN[10]算法(③)隨著近鄰數(shù)k的選擇對標簽相關性造成的損失，以emotions數(shù)據(jù)集為例，圖中顯示了多標簽的5項評價指標隨著k值增加的變化曲線。

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

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

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

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

4 結 語

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

[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] 李峰,苗奪謙,張志飛,等.基于互信息的粒化特征加權多標簽學習k近鄰算法[J].計算機研究與發(fā)展,2017,54(5): 1024- 1035.

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

[12] 廖松有,張繼福,劉愛琴.利用模糊熵約束的模糊C均值聚類算法[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] 徐計,王國胤,于洪.基于粒計算的大數(shù)據(jù)處理[J].計算機學報,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.