基于局部和全局一致性的多標簽分類算法

姚小慧，孫國強

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200096)

基于局部和全局一致性的多標簽分類算法

姚小慧，孫國強

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200096)

針對局部和全局一致性的分類算法LGC未考慮標簽之間的相關(guān)性，提出了一種基于局部和全局一致性的多標簽分類(MLGC)算法。該方法新增加了一個標簽與標簽之間的約束，在分類時考慮了標簽之間的相關(guān)性，再取出1/10的數(shù)據(jù)集使用該算法，求出每個標簽的自適應(yīng)閾值，利用閾值對整個數(shù)據(jù)集進行預(yù)測。實驗結(jié)果表明，所提出算法在Emotion和Yeast數(shù)據(jù)集上均優(yōu)于原來算法，將此算法應(yīng)用于區(qū)域醫(yī)療大數(shù)據(jù)的項目中，也取得了良好的分類結(jié)果。

多標簽分類；局部和全局一致性；標簽相關(guān)性

眾多學(xué)者對于分類問題提出了許多算法[1]，但有許多問題無法采用單分類方法解決，例如文本領(lǐng)域[2-3]，圖片注解領(lǐng)域[4-6]和生物信息領(lǐng)域[7]。所以，多標簽分類問題應(yīng)運而生，引起了人們廣泛的關(guān)注。解決多標簽分類最簡單的方法就是BR(Binary Relevance)方法[8]，但它沒有考慮標簽之間的相關(guān)性。LP(Label Powerset)[9]方法是將問題轉(zhuǎn)化為多分類問題，雖然考慮了標簽之間的相關(guān)性，但是訓(xùn)練開銷會比較大。MLkNN算法[10]用最大化后驗概率來預(yù)測該樣本的標簽集，也沒有考慮標簽之間的相關(guān)性。因此本文在文獻[11～13]的研究基礎(chǔ)上，提出了一種基于局部和全局一致性的多標簽分類算法MLGC(A Multi-label Classification Based on The Local And Global Consistency)，不僅考慮了標簽之間的相關(guān)性，而且還提出了適應(yīng)于該算法的閾值，經(jīng)過Matlab仿真實驗，證明了該算法優(yōu)于LGC(Learning With Local And Global Consistency)算法。

1 LGC正則化框架

已知數(shù)據(jù)集X=X1,X2,…,Xn,標簽集Y=Y1,Y2,…,Yc,其中n為數(shù)據(jù)集總數(shù)，c為標簽集總數(shù)，分類函數(shù)定義如下

(1)

其中，W是n×n的數(shù)據(jù)相關(guān)性矩陣;D是一個對角矩陣；(i,i)值等于W第i行的和；F是n×c的目標標簽矩陣；Y是n×c的初始化標簽矩陣，μ>0,是正則化參數(shù)。式(1)的第一項是平滑性約束，第二項是擬合約束。采用參數(shù)μ對這兩個約束進行權(quán)衡。

對矩陣F求導(dǎo)，可得

F=β(I-αS)-1Y

(2)

2 MLGC算法

多標簽學(xué)習(xí)算法只考慮了數(shù)據(jù)之間的相關(guān)性，而忽視了標簽之間的相關(guān)性，當標簽之間的關(guān)系密切時，那么文獻[14]所提出的LGC正則化框架就會受到限制。本文提出的MLGC算法通過引入標簽與標簽之間的約束，避免了LGC正則化框架的限制，從而解決了多標簽的分類問題。

2.1 算法原理

LGC正則化框架只考慮了兩大約束，這對多標簽分類來說，是遠遠不夠的。受文獻[13]的啟發(fā)，在考慮多標簽分類時，還應(yīng)該考慮標簽與標簽之間的相關(guān)性，因此本文在LGC的基礎(chǔ)上，添加了第三項約束條件，使該算法更加適用多標簽分類算法。

已知數(shù)據(jù)集X-{X1,X2,,,Xn}∈Rn*m，數(shù)據(jù)集X所對應(yīng)的標簽集共有c個標簽，記為L={L1,L2,,,Lc}∈Rc*n,X中前l(fā)個數(shù)據(jù)已經(jīng)分好類，其中l(wèi)<

F(t+1)=αSF(t)+βF(t)P+γY

(3)

其中，α+β+γ=1，F(xiàn)(0)=Y,矩陣S和矩陣P由數(shù)據(jù)關(guān)系矩陣(4)和標簽關(guān)系矩陣(5)得出

(4)

(5)

對式(4)和式(5)進行歸一化,得到S矩陣和P矩陣

S=D-1/2WD-1/2,P=D’-1/2W’D’-1/2

(6)

其中，矩陣D為對角矩陣，它的(i,i)是矩陣W的第i行的和，矩陣D’為對角矩陣，它的(i,i)是矩陣W’第i行的和。

至此，式(3)中的變量已逐一闡明，對其求極限，可得

(ɑS-I)F*+βF*P+γY=0

(7)

2.2 正則化框架

(8)式(8)中第一項是數(shù)據(jù)節(jié)點之間的光滑性約束，是指相鄰數(shù)據(jù)節(jié)點間應(yīng)該有相同的標簽；第二項是標簽光滑性約束，是指相鄰標簽節(jié)點間應(yīng)該有相同的數(shù)據(jù)節(jié)點；第三項是擬合性約束，是指預(yù)測的標簽值與初始值不應(yīng)發(fā)生過大的變化。為了最小化Q(F)，對F進行求導(dǎo)

(9)

化簡式(9)可得

(10)

令，

(11)

由式(10)和式(11)得

(αS-I)F*+βF8P+γY=0

(12)

由此，式(12)得出了與式(7)一致的結(jié)論。

2.3 自適應(yīng)閾值

在文獻[14]的基礎(chǔ)上，本文根據(jù)該算法提出了適應(yīng)于本算法的自適應(yīng)閾值。實驗中，本文選取1/10的訓(xùn)練集，根據(jù)MLGC算法，快速得出最后的分類矩陣F′。對于每一個標簽，選取F′矩陣中屬于該標簽的值取其平均值，得到該標簽的接受閾值Tal，選取F′矩陣中不屬于該標簽的值取其平均值，得到該標簽的拒絕閾值Tdl，最終的閾值T1即為接受閾值和拒絕閾值的平均值

(13)

3 驗證

3.1 實驗數(shù)據(jù)

實驗采用兩個不同領(lǐng)域的真實的數(shù)據(jù)集：Emotion數(shù)據(jù)集是有關(guān)音樂領(lǐng)域的數(shù)據(jù)集，在該數(shù)據(jù)集中，標簽空間為6；Yeast數(shù)據(jù)集是生物領(lǐng)域的數(shù)據(jù)集，它是對基因片段的功能進行分類，其標簽空間為14，表1描述了兩個數(shù)據(jù)集的詳細信息。

表1 數(shù)據(jù)集

3.2 評價指標

實驗采用精確匹配率(Exact Match Ratio, EMR)[15],微平均F1值(Micro-F1)和宏平均F1值(Macro-F1)這3個性能指標，具體定義為

(14)

F1 score定義如下

(15)

其中，P1是第l個標簽的精確率；R1是第l個標簽的召回率，所以c個標簽的宏F1 score就是它們每個類別F1 score的算術(shù)平均值

(16)

微F1 score是每個實體F1 score的算術(shù)平均值[15]，具體定義為

(17)

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

為驗證本文算法的有效性，與已有的LGC算法進行比較，在LGC算法中，本文取 。對于本文算法，采用十折交叉驗證法來選擇參數(shù)，即把訓(xùn)練集分成10份，取其中9份作為訓(xùn)練集，剩下的一份作為測試集，實驗結(jié)果如表2和表3所示。

表2 十折交叉法在Emotion數(shù)據(jù)集上的性能

表3 十折交叉法在yeast數(shù)據(jù)集上的性能

實驗結(jié)果表明，α=0.89，β=0.1時，算法得到最優(yōu)解。這表明，在取值過程中，α與β并不是越大越好，他們二者相互制約，當α較大時，說明預(yù)測的節(jié)點更有可能與其相似的數(shù)據(jù)節(jié)點具有相同標簽，當β較大時，說明預(yù)測的節(jié)點更有可能具有與其標簽相似的標簽。

表4 K折交叉法在Emotion數(shù)據(jù)集上的性能(α=0.89,β=0.1)

表5 K折交叉法在Yeast數(shù)據(jù)集上的性能(α=0.89,β=0.1)

采用K折交叉驗證法(K=2～10),在Emotion和Yeast數(shù)據(jù)集上采用最佳參數(shù)值，即α=0.89，β=0.1進行試驗，試驗結(jié)果如表5和表6所示，在這兩個數(shù)據(jù)集上，隨著K值的增大，即訓(xùn)練集變大，精確匹配率、微平均和宏平均這3個指標均有上升的趨勢。當K值一定時，MLGC算法在這3個性能指標上的值均大于LGC算法在這3個指標上的值，這表明MLGC算法整體上均優(yōu)于LGC算法。

4 結(jié)束語

標簽之間的相關(guān)性是多標簽分類中不可忽視的一項重要因素。本文提出了考慮標簽相關(guān)性的MLGC算法，提供了其迭代算法和框架。實驗結(jié)果表明，MLGC算法均優(yōu)于LGC算法，可以提高多標簽的分類效果。

[1] Tsoumakas G,Katakis I.Multi label classification:an overview[J].IEEE Intelligent Systems,2010,25(4):19-25.

[2] Lewis D,Yang Y, Rose T,et al.RCV1:A new benchmark collection for text categorization research [J].The Journal of Machine Learning Research,2004,5(2):361-397.

[3] Moffat A,Zobel J.Self-indexing inverted files for fast text retrieval[J].Acm Transactions on Information Systems,2015,14(4):349-379.

[4] Boutell M R,Luo J,Shen X,et al.Learning multi-label scene classification[J].Pattern Recognition,2004,37(9):1757-1771.

[5] Peng Y,Ngo C W.Clip-based similarity measure for query-dependent clip retrieval and video summarization[J]. IEEE Transactions on Circuits & Systems for Video Technology,2006,16(5):612-627.

[6] Greenspan H, Goldberger J, Mayer A. Probabilistic space-time video modeling via piecewise GMM[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2010, 26(3):384-96.

[7] Jiang J Q,Mcquay L J.Predicting protein function by multi-label correlated semi-supervised learning[J].IEEE/ACM Transactions on Computational Biology & Bioinformatics,2012,9(4):1059-69.

[8] Boutell M R,Luo J,Shen X,et al.Learning multi-label scene classification[J].Pattern Recognition,2004,37(9):1757-1771.

[9] Tsoumakas G,Katakis I,Vlahavas I.Random k-labelsets for multilabel classification[J].IEEE Transactions on Knowledge & Data Engineering,2011,23(7):1079-1089.

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

[11] Zhang M L.An improved multi-label lazy learning approach[J].Journal of Computer Research and Development,2012,49(11):2271-2282.

[12] Zhou D,Bousquet O,Lal T N,et al. Learning with local and global consistency[J].Advances in Neural Information Processing Systems,2004,16(4):321-328.

[13] Xu J J,Jagadeesh V.Multi-label learning with fused multimodal birelational gaph[J].IEEE Transactions on Multimedia,2014,16(2):403-412.

[14] 鄭偉,王朝坤,劉璋,等.一種基于隨機游走模型的多標簽分類算法[J].計算機學(xué)報,2010,33(8):1418-1426.

[15] 史仍浩,陳秀真,李生紅.基于流形學(xué)習(xí)的社會化媒體網(wǎng)絡(luò)數(shù)據(jù)分類[J].計算機應(yīng)用研究,2013,30(3):692-694.

The Multi-label Classification Based on the Local and Global Consistency

YAO Xiaohui,SUN Guoqiang

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 2000235,China)

The multi-label classification didn’t take the relationship of the labels into consideration,so this paper improved LGC and proposed a multi-label classification based on the local and global consistency(MLGC). The method added a new constraint between labels, which consider the correlation between tags. Besides, this paper put forward a suitable threshold. Experimental results based on the emotion and yeast data sets shows this method is superior to LGC.Then the algorithm is applied to the project of medical,which also achieved great result.

multi-label classification;local and global consistency;label relation

2016- 06- 20

國家高技術(shù)研究發(fā)展計劃(863計劃)基金資助項目(2015AA020105)

姚小慧(1992-)，女，碩士研究生。研究方向：機器學(xué)習(xí)。孫國強(1962-)，男，副教授。研究方向：嵌入式應(yīng)用系統(tǒng)開發(fā)。

10.16180/j.cnki.issn1007-7820.2017.03.002

TP301.6

A

1007-7820(2017)03-004-04