多標(biāo)簽數(shù)據(jù)問(wèn)題常用的分類器或者分類策略

1、多標(biāo)簽(multi-label )據(jù)問(wèn)題常用的分類器或者分類策略多標(biāo)記分類和傳統(tǒng)的分類問(wèn)題相比較，主要難點(diǎn)在于以下兩個(gè)方面：類標(biāo)數(shù)量不確定，有些樣本可能只有一個(gè)類標(biāo)，有些樣本的類標(biāo)可能高達(dá)幾 十甚至上百個(gè)。類標(biāo)之間相互依賴，例如包含藍(lán)天類標(biāo)的樣本很大概率上包含白云，如何解 決類標(biāo)之間的依賴性問(wèn)題也是一大難點(diǎn)。對(duì)于多標(biāo)記學(xué)習(xí)領(lǐng)域的研究，國(guó)外起步較早，起源于2000年Schapire R E等人提出的基于 boost方法的文本多分類，著名的 學(xué)者有G Tsoumakas、Eyke HUllermeier、Jesse Read , Saso Dzeroski等等。在國(guó)內(nèi)，南京大學(xué)的周志華和張 敏靈和

2、哈工大的葉允明等等學(xué)者在這一領(lǐng)域較都有很好研究成果。目前有很多關(guān)于多標(biāo)簽的學(xué)習(xí)算法，依據(jù)解決問(wèn)題的角度，這些算法可以分為 兩大類：一是基于問(wèn)題轉(zhuǎn)化(Problem Transformation )的方法，二是基于算法適 應(yīng)的方法和算法適應(yīng)方法(Algorithm Adaptation )?；趩?wèn)題轉(zhuǎn)化的多標(biāo)記分類 是轉(zhuǎn)化問(wèn)題數(shù)據(jù)，使之適用現(xiàn)有算法；基于算法適應(yīng)的方法是指針對(duì)某一特定的算 法進(jìn)行擴(kuò)展，從而能夠直接處理多標(biāo)記數(shù)據(jù)，改進(jìn)算法，適應(yīng)數(shù)據(jù)?；谶@兩種思 想，目前已經(jīng)有多種相對(duì)成熟的算法被提出，如下圖所示：?jiǎn)栴}轉(zhuǎn)化方法(Problem Transformation ):該類方法的基本思想是

3、通過(guò)對(duì)多 標(biāo)記訓(xùn)練樣本進(jìn)行處理，將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)換為其它已知的學(xué)習(xí)問(wèn)題進(jìn)行求解。 代表性學(xué)習(xí)算法 LPi，Binary Relevance ，Calibrated Label Ranking 3， Random k-labelsets囹?？傮w來(lái)說(shuō)，這類方法有考慮類標(biāo)之間的聯(lián)系，但是對(duì)于類 標(biāo)較多、數(shù)據(jù)量較大的數(shù)據(jù)集，這類方法的計(jì)算復(fù)雜度是一個(gè)很明顯的缺陷。算法適應(yīng)方法與問(wèn)題轉(zhuǎn)化方法不同，問(wèn)題轉(zhuǎn)化方法是將多標(biāo)記問(wèn)題轉(zhuǎn)化成一個(gè) 或者多個(gè)單類標(biāo)問(wèn)題，算法適應(yīng)方法是在多標(biāo)記的基礎(chǔ)上研究算法。近年來(lái)，用于 多標(biāo)記的算法適應(yīng)的算法越來(lái)越多，代表性學(xué)習(xí)算法ML-kNN 5，Rank-SVM 句，LEAD7

4、，CML。對(duì)于分類策略，基于考察標(biāo)記之間相關(guān)性的不同方式，已有的多標(biāo)記學(xué)習(xí)算法的策略思路大致可以分為以下三類8:一階(first-order)”策略：該類策略通過(guò)逐一考察單個(gè)標(biāo)記而忽略標(biāo)記 之間的相關(guān)性，如將多標(biāo)記學(xué)習(xí)問(wèn)題分解為個(gè)獨(dú)立的二類分類問(wèn)題，從而構(gòu)造多標(biāo) 記學(xué)習(xí)系統(tǒng)。該類方法效率較高且實(shí)現(xiàn)簡(jiǎn)單，但由于其完全忽略標(biāo)記之間可能存在 的相關(guān)性，其系統(tǒng)的泛化性能往往較低。二階(second-order)”策略：該類策略通過(guò)考察兩兩標(biāo)記之間的相關(guān)性， 如相關(guān)標(biāo)記與無(wú)關(guān)標(biāo)記之間的排序關(guān)系，兩兩標(biāo)記之間的交互關(guān)系等等，從而構(gòu)造 多標(biāo)記學(xué)習(xí)系統(tǒng)。該類方法由于在一定程度上考察了標(biāo)記之間的相關(guān)性，因此其系

5、 統(tǒng)泛化性能較優(yōu)。高階(high-order)”策略：該類策略通過(guò)考察高階的標(biāo)記相關(guān)性，如處 理任一標(biāo)記對(duì)其它所有標(biāo)記的影響，處理一組隨機(jī)標(biāo)記集合的相關(guān)性等等，從而構(gòu) 造多標(biāo)記學(xué)習(xí)系統(tǒng)。該類方法雖然可以較好地反映真實(shí)世界問(wèn)題的標(biāo)記相關(guān)性，但 其模型復(fù)雜度往往過(guò)高，難以處理大規(guī)模學(xué)習(xí)問(wèn)題。Madjarov G, Kocev D, Gjorgjevikj D, et al. An extensive experimental comparisonof methods for multi-label learningJ. Pattern Recognition, 2012, 45(9): 3084-

6、3104.Boutell M R, Luo J, Shen X, Brown C M. Learning multi-label scene classification.Pattern Recognition, 2004, 37(9): 1757-1771.Furnkranz J, Hullermeier E, LozaMenci a E, Brinker K. Multilabel classification viacalibrated label ranking. Machine Learning, 2008, 73(2): 133-153.Tsoumakas G, Vlahavas

7、I. Random k-labelsets: An ensemble method for multilabelclassification. In: Kok J N, Koronacki J, de Mantaras R L, Matwin S, Mladenic D, Skowron A, eds. Lecture Notes in Artificial Intelligence 4701, Berlin: Spr inger,2007, 406-417.Zhang M-L, Zhou Z-H. ML-kNN: A lazy learning approach to multi-label

8、 learning.Pattern Recognition, 2007, 40(7): 2038-2048.Elisseeff A, Weston J. A kernel method for multi-labelled classification. In: DietterichT G, Becker S, Ghahramani Z, eds. Advances in Neural Information Processing Systems 14 (NIPS01), Cambridge, MA: MIT Press, 2002, 681-687.Zhang M-L, Zhang K. Multi-label learning by exploiting label dependency. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discov ery and Data Mining (KDD10), Washington, D. C., 2010, 999-1007.Zhang M L, Zhang K. Multi-labe