一種標記粒化集成的多標記學習算法

李 峰，苗奪謙，張志飛，羅 晟

(同濟大學 計算機科學與技術系，上海 201804)

(同濟大學 嵌入式系統與服務計算教育部重點實驗室，上海 201804)

1 引 言

現實世界存在的大量事物同時擁有多個標記，例如，一首樂曲可能同時包含悲傷、靜謐等多種情感[1]；一個蛋白質可能同時擁有轉錄、新陳代謝等多種功能[2]；一幅圖片可能表達了大海、沙灘等多個語義信息[3]；一部電影可能同時屬于動作、喜劇等多個題材類型.這些擁有多個標記的事物稱為多標記樣本，這些多標記樣本構成了多標記數據.然而傳統機器分類學習中通常每個樣本僅被賦予一個類別標記，稱作單標記學習，不能直接用于多標記數據.不同于傳統機器學習算法，給定一個標記空間L，多標記學習算法旨在學習標記已知的多標記數據，預測出未標記樣本相關的標記子集Y，其中Y?L，并且|Y|≥1[4-6].

多標記數據中標記之間往往存在一定的相關性，如一部電影如果標記為“動作”類型，那么它同時屬于“冒險”類型的可能性比它同時屬于“愛情”類型的可能性大得多，因此在多標記學習中不能忽略標記之間的相關性.多標記數據中的樣本可能同時擁有多個標記，導致了多標記數據的復雜多變，并且標記之間具有相關性，這些都極大地增加了多標記學習算法預測的難度.多標記分類問題儼然成為一個比較有挑戰的問題，吸引了越來越多學者的關注與研究，成為機器學習中一個研究熱點.針對多標記分類問題，一系列多標記學習算法被提出，這些算法主要可以分為兩類，問題轉化型方法(Problem Transformation Methods)和算法適應型方法(Algorithm Adaption Methods)[4].

第一種類型的方法獨立于算法，將多標記分類問題轉換成一個或者多個單標記分類問題，再利用已有的單標記學習算法處理.而第二類方法則是對某一具體算法進行改進以使其能直接處理多標記分類問題，如支持向量機(SVM)[7，8]、決策樹[9，10]、神經網絡[11]、粗糙集[12]、k-近鄰算法[13，14]等.本文主要研究第一類方法.

本文基于粒計算的思想，提出了一種標記粒化集成的多標記學習算法(Label-Granulated Ensemble Method for Multi-label Learning，GEM).粒計算(Granular Computing，GrC)[18，19]是目前解決復雜問題的有效方法之一，其模擬人類處理復雜問題的方式，將復雜問題轉化為若干簡單問題，依據某一特性從信息或者數據中抽象出信息粒.該方法為標記空間中的每一個標記找到相關性程度最大的前k個標記，這k個標記構成了一個關系粒，這樣使標記間的相關性最大可能地被考慮.對每一個關系粒構建一個分類器，最后集成各分類器的結果，最終輸出預測的結果.GEM算法不僅考慮到了標記之間的相關性，而且根據標記之間的相關性構建關系粒，避免了LP算法復雜度過高、泛化性不夠的問題和RAkEL方法隨機選擇造成的不穩定性，以及標記可能被遺漏的，算法性能不夠好的問題.

在三個多標記數據集上通過實驗研究了關系粒的基數，既標記個數對算法性能的影響.并跟BR方法、LP方法和RAkEL方法進行了比對.實驗表明本文所提算法能取得較好的性能.

本文在第一部分介紹了本文工作提出的背景；相關的基礎知識放在了第二部分；第三部分詳細介紹了本文所提算法；在第四部分通過實驗驗證了本文所提算法的有效性；最后對本文工作進行了總結.

2 基礎知識

這里先簡要介紹與本文所提算法相關的基礎知識，多標記學習和互信息的基本概念.

2.1 多標記學習

給定一個b維的樣本空間F=Rb和q個標記的標記空間L.T={(X1，Y1)，(X2，Y2)，…，(Xn，Yn)}表示一個多標記數據集，其中每個樣本Xi∈F表示為一b維特征向量，Yi={yi1，yi2，…，yiq}表示樣本Xi對應的標記向量，當Xi含有標記lj時，yij=1，否則yij=0(1≤i≤n，1≤j≤q).

2.2 互信息

定義1. 熵[20，21]能有效地度量隨機變量不確定性，隨機變量A的熵定義為：

(1)

其中，p(a)表示a的概率密度.

定義2. 給定變量A時變量C的條件熵為：

(2)

其中p(a，c)是聯合概率密度，p(c|a)是條件概率密度.

定義3. 互信息能度量兩個變量間相互依賴的程度，變量A和C的互信息定義為：

(3)

從式(3)可以看出MI(A；C)=MI(C；A).

MI(A；C)=H(A)-H(A|C).

(4)

3 粒化集成多標記學習算法

針對LP算法復雜度過高，RAkEL方法穩定性不佳的問題，以及粒計算能較好的把復雜問題轉化為若干簡單問題，本文提出了一種標記粒化集成的多標記學習算法.該算法首先根據標記之間的相關性，為每個標記li∈L劃分出一個與之相關度最大的k個標記構成的標記子集，記為關系粒[li]k.將標記之間的相關性考慮進標記子集的劃分中，相較于RAkEL方法更加直接而且穩定.對每一個關系粒[li]k構建一個分類模型，對于?lj∈[li]k有hi：X→lj，lj，預測出在該分類模型下樣本X是否含有標記lj，模型可改寫為輸出預測值hi(X，lj)，如果X含有lj則hi(X，lj)=1，否則hi(X，lj)=0.最終對各分類模型的相應預測的值集成后輸出預測的標記向量Y′.算法流程如圖1所示.

圖1 粒化集成算法流程Fig.1 Flowchart of the proposed method

3.1 關系粒

定義4. 給定一個標記li∈L和相關度度量函數S，那么li的關系粒[li]k定義為：

[li]k={lj|Rank(S(li，lj))≤k，lj∈L}

(5)

其中，k為關系粒基數，確定了關系粒中標記的個數，滿足1≤k≤q，Rank(σ)為排序函數，其對σ值從大到小排序.對于?li，lj∈L，滿足以下性質：

1)0≤S(li，lj)≤1；

2)S(li，lj)=S(lj，li)；

3)Rank(S(li，li))=1.

從定義4可以看出當關系粒基數k=q時，關系粒與標記空間等同，所有的標記組合被考慮，則是LP方法.然而當k=1時，關系粒中只剩自身一個標記，不考慮標記之間的相關性，則是BR方法.更進一步，當k=q或k=1時，輕易可以看出關系粒[li]k為等價類.

相關度度量函數S影響著關系粒中標記的選擇.在機器學習中，常用各類距離函數度量不同樣本間的相關性，如歐氏距離、曼哈頓距離、馬氏距離等.在多標記學習中，也常用各類相關性度量函數來判斷樣本間的相關性，但相較于傳統機器學習，多標記學習還度量標記間的相關性.常見的標記間相關性度量函數有基于互信息的相關性度量，基于皮爾遜相關系數的相關性度量.基于距離函數的相關性度量往往只能度量正相關性，不能很好地判斷負相關性.而互信息是常用的度量兩個變量相關性的有效方式之一，不僅能度量正相關性，還能評估非線性相關性和負相關性，所以這里我們選用常用的互信息定義兩個標記間的相關性，作為相關度度量函數.給定?li，lj∈L，根據公式(3)他們間的相關性計算如下：

S(li，lj)=MI(li；lj)

(6)

由定理1，相關性度量函數可表示為：

S(li，lj)=H(li)-H(li|lj)

(7)

從式(7)可以看出，對于給定的一個標記li，H(li)為常數，對排序函數Rank(σ)而言，去除或者添加一個常數項，對排序結果無影響.因此求解關系粒[li]k對相關性度量函數S(li，lj)的排序可轉換為只由條件熵表示即：

Rank(S(li，lj))∝Rank(-H(li|lj))

定義4中關系粒[li]k的求解可改寫為：

[li]k={lj|Rank(-H(li|lj))≤k，lj∈L}

(8)

既對已知標記lj，標記li存在的不確定性大小的負值進行排序，不確定性越小說明相關度越大.關系粒的劃分過程偽代碼如算法1所示.

算法1.標記粒化算法

輸入：標記空間L，關系粒基數k，訓練集T={(X1，Y1)，(X2，Y2)，…，(Xn，Yn)}

輸出：關系粒[li]k，1≤i≤q

第1步：

Fori=1：q

//初始化關系粒

①[li]k←φ；

②Forj=1：q

根據公式(2)計算條件熵H(li|lj)，(li，lj∈L)；

End For

③Car←k；

④WhileCar>0

a)查找條件熵最小的標記arg min1≤a≤qH(li|la)；

b)[li]k←la；

c)H(li|la)←∞；

d)Car←Car-1；

End While

End For

第2步：得到關系粒[li]k，1≤i≤q.

3.2 分類器

算法2.粒化集成多標記學習算法

輸入：未標記樣本X，關系粒基數k，訓練集T={(X1，Y1)，(X2，Y2)，…，(Xn，Yn)}，標記空間L

輸出：未標記樣本X對應的標記向量Y′

第1步：

調用算法1；

第2步：

Forj=1：q

訓練分類模型hi；

Negj←0；

Posj←0；

End For

第3步：

Fori=1：q

Forlj∈[li]k

Negj←Negj+1-hi(X，lj)；

Posj←Posj+hi(X，lj)；

End For

End For

第4步：

Forj=1：q

IfPosj≥Negj

yj←1；

Else if

yj←0；

End If

End For

第5步：輸出預測的標記向量Y′

4 實驗分析

4.1 數據集及實驗設置

本文從Mulan Library[22]選取了3個涵蓋文本、圖像、生物的來自真實世界的多標記數據集進行了實驗，以驗證本文所提算法的有效性.數據集的詳細信息如表1所示.表中，樣本數是指該數據集包含的樣本數量，特征數是指特征空間的維度，標記數則是該數據集標記空間的標記個數，標記基數是平均每個樣本所含有的標記數量.

Scene數據集[15]包含2407張圖片，每張圖片由6個可能的語義標記標注.其特征空間由294維視覺特征構成.

Medical數據集[23]是關于病例診斷的數據里.該數據集包含了978個病歷文本記錄樣本，每個樣本由1449維的診斷歷史記錄和觀察到的癥狀組成，標記空間則是45種ICD-9-CM疾病編碼.

Yeast數據集[7]用于描述酵母菌的基因功能分類，由2417個yeast基因樣本和14種可能的基因功能構成.每個基因樣本對應于一個103維的特征向量.

為了驗證算法的性能，實驗中將所提算法與BR方法、LP方法和RAkEL方法進行了比對.根據文獻[16]建議的參數配置，RAkEL方法的子集大小為2，子集數量為2p，閾值設為0.5.支持向量機算法(SVM)是機器學習中的經典算法，能有效地處理多類分類問題，因此本文選取了RBF核的支持向量機算法構建最終的分類模型，損失參數取1，gamma值為0.07.實驗采用了十折交叉驗證方法(Ten-foldcross-validation).

表1 多標簽數據集Table 1 Multi-label datasets used in the experiments

4.2 評價指標

漢明損失度量算法預測出的標記信息與實際的標記信息的平均差異值.

當π條件滿足時，<π> 值為1，否則為0.該指標值越小說明算法性能越好.

綜合評價指標F1值是準確率和召回率的調和平均值，解決了準確率和召回率可能存在矛盾的問題，是機器學習中常用的一個評價指標.當我們知道真正數tp，真負數tn，假正數fp，假負數fn，那么F1的計算如下：

微平均F1與宏平均F1是以兩種不同的平均方式求的全局的F1指標.微平均F1和宏平均F1能綜合多個類別的分類情況，評測系統整體性能.給定標記li的tpi、tni、fpi和fni四個值，那么MicroF1和MacroF1計算如下：

微平均F1與宏平均F1值越高說明算法性能越好.

4.3 實驗結果及分析

4.3.1 關系粒基數選擇

該部分研究了關系粒基數k的取值變化對算法性能的影響.從表1可以看出數據集Scene、Medical和Yeast標記空間的維數q分別為6、45和14標記數，當關系粒基數k取1時為BR方法，取q時為LP方法，因此在實驗中我們令2≤k≤q-1.由于Medical的標記空間維數過大，當基數k取值過大時，喪失了粒化的意義，因此實驗中我們對其基數取值為2≤k≤20.各評價指標結果在各數據集上隨著基數k增加的變化曲線如圖2-圖4所示.圖中顯示的評價指標值為十折交叉驗證的均值，為了讓各評價指標結果能在圖中清晰的表示，更清楚地觀察變化規律，對同一數據集地單一評價指標結果進行了放大和移動，但這些修改不影響評價指標的變化規律.

從圖2可以看出，在Medical數據集上，隨著k的增加漢明損失先逐漸變小，微平均F1逐漸變大，當k取13時兩個指標達到最優，而宏平均F1的變化較復雜，但綜合考量三個評價指標，當k取13時算法在Medical數據集上最優.而從圖3和圖4可以清楚地看出在Scene數據集和Yeast數據集上的最優在k取5時獲得.

圖2 Medical數據集上評價指標隨著k增加變化曲線Fig.2 Evaluation criteria of varying the number of k on Medical

圖3 Scene數據集上評價指標隨著k增加變化曲線Fig.3 Evaluation criteria of varying the number of k on Scene

圖4 Yeast數據集上評價指標隨著k增加變化曲線Fig.4 Evaluation criteria of varying the number of k on Yeast

4.3.2 對比實驗分析

各對比算法BR方法、LP方法RAkEL方法和本文所提算法在各數據集上的實驗結果如表2所示.表中↑(↓)符號表示該項指標值越大算法性能越好.

從表2可以看出在Medical數據集上，各個對比算法取得的Hamming Loss值比較相近，GEM在MicroF1指標上優于其它三個算法，而LP方法在MacroF1上取得最優，但跟本文所提算法GEM相差不大.本文所提算法在數據集Scene上各項指標均優于其它對比算法，但在Hamming Loss上跟其它算法差異較小.BR算法性能明顯劣于其它.Yeast數據集中，從MicroF1和MacroF1兩項指標來看GEM最優，從Hamming Loss角度，除了LP外，其它三種方法所取得的結果差異較小.從三個數據集整體上看，本文所提算法性能整體上優于其它三種算法.

表2 對比實驗結果(均值±標準差)Table 2 Compared experimental results (mean±std.deviation)

5 結 論

針對BR方法忽略標記間的相關性，LP算法復雜度過高、標記組合對應的正例可能過少的問題，RAkEL方法中隨機選擇子集造成算法性能不穩定的問題，本文提出了一種粒化集成的多標記學習算法.該算法根據標記間的相關性，為每一個標記找到一個關系粒，考慮關系粒中標記組合，構建一個單標記分類器，最終集成各分類器的結果.能避免前面提到的問題，產生穩定較好的結果.實驗結果表明相較于其它對比算法，本文所提算法能取得較好的預測效果.

：

[1] Tsoumakas G，Katakis I，Vlahavas I.Multi-label classification of music into emotions[C].Proceedings of the 9th International Conference on Music Information Retrieval，Philadephia，ISMIR 2008：325-330.

[2] Yu Ying，Pedrycz W，Miao Duo-qian.Neighborhood rough sets based multi-label classification for automatic image annotation[J].International Journal of Approximate Reasoning，2013，54(9)：1373-1387.

[3] Pavlidis P，Weston J，Cai J，et al.Grundy.Combining microarray expression data and phylogenetic profiles to learn functional categories using support vector machines[C] .Proceedings of the 5th Annual International Conference on Computational Biology，Montreal，QC：ACM，2001：242-248.

[4] Tsoumakas G，Katakis I，Vlahavas I.Mining multi-label data/Data mining and knowledge discovery handbook[M].Berlin：Springer，2010：667-685.

[5] Tsoumakas G，Katakis I.Multi label classification：An overview[J].International Journal of Data Warehousing and Mining，2007，3(3)：1-13.

[6] Zhang Min-ling，Zhou Zhi-hua.A Review on multi-label learning algorithms[J].IEEE Transactions on Knowledge and Data Engineering，2014，26(8)：1819-1837.

[7] Elisseeff A，Weston J.A kernel method for multi-labelled classification[C].Proceedings of Advances in Neural Information Processing Systems，Vancouver，BC：NIPS，2001：681-687.

[8] Chen W J，Shao Y H，Li C N，et al.MLTSVM：a novel twin support vector machine to multi-label learning[J].Pattern Recognition，2015，52：61-74.

[9] Clare A，King R.Knowledge discovery in multi-label phenotype data[G].LNCS 2168：Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery：PKDD 2001.Berlin：Springer，2001：42-53.

[10] Wu Q，Tan M，Song H，et al.ML-forest：a multi-label tree ensemble method for multi-label classification[J].IEEE Transactions on Knowledge and Data Engineering，2016，28(10)：2665-2680.

[11] Zhang Min-ling，Zhou Zhi-hua.Multi-label neural networks with applications to functional genomics and text categorization[J].IEEE Transactions on Knowledge and Data Engineering，2006，18(10)：1338-1351.

[12] Yu Ying，Pedrycz W，Miao Duo-qian.Multi-label classification by exploiting label correlations[J].Expert Systems with Applications，2014，41(6)：2989-3004.

[13] Zhang Min-ling，Zhou Zhi-hua.ML-kNN：a lazy learning approach to multi-label learning[J].Pattern Recognition，2007，40(7)：2038-2048.

[14] Zhang Min-ling.An improved multi-label lazy learning approach[J].Journal of Computer Research and Development，2012，49(11)：2271-2282.

[15] Boutell M，Luo J，Shen X，et al.Learning multi-label scene classification[J].Pattern Recognition，2004，37(9)：1757-1771.

[16] Tsoumakas G，Katakis I，Vlahavas I.Randomk-labelsets for multilabel classification[J].IEEE Transactions on Knowledge and Data Engineering，2011，23(7)：1079-1089.

[17] Tsoumakas G，Vlahavas I.Random k-labelsets：An ensemble method for multilabel classification[M].Machine Learning：ECML′07，Springer，Berlin，2007，406-417.

[18] Yao Yi-yu.Interpreting concept learning in cognitive informatics and granular computing[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2009，39(4)：855-866.

[19] Yao Yi-yu，Zhao Li-quan.A measurement theory view on the granularity of partitions[J].Information Sciences，2012，213(23)：1-13.

[20] Shannon C.A mathematical theory of communication[J].Bell System Technical Journal，1948，27(3)：379-423.

[21] Shannon C.A mathematical theory of communication[J].Bell System Technical Journal，1948，27(4)：623-656.

[22] Tsoumakas G，Spyromitros-Xiousfis E，Vilcek I.Mulan：a java library for multi-label learning[J].Journal of Machine Learning Research，2011，12(7)：2411-2414.

[23] Pestian J，Brew C，Matykiewicz P，et al.A shared task involving multi-label classification of clinical free text[C].Proceedings of the Workshop on BioNLP 2007：Biological，Translational，and Clinical Language Processing，Prague：BioNLP，2007：97-104.

附中文參考文獻：

[14] 張敏靈.一種新型多標記懶惰學習算法[J].計算機研究與發展，2012，49(11)：2271-2282.