多標簽分類問題的解法綜述前言分類問題分類問題是模式識別的核心研究內(nèi)容，其目的是通過對己知標簽數(shù)據(jù)集的學習設計一個分類器，然后用該分類器來預測新樣本的標簽。按照樣本所屬標簽個數(shù)，分類問題可以分為單標簽分類問題和多標簽分類問題。在多標簽分類問題中，標簽與標簽之間存在著一定的依賴或關聯(lián)關系，而且問題中的樣本可以同時屬于多個標簽，因此多標簽分類問題是最為復雜的分類問題之一。分類問題的應用目前，現(xiàn)實世界中存在著大量的多標簽分類問題，多標簽分類算法有非常廣泛的應用前景，比如a)文本分類[1][2][3]a)文本分類[1][2][3]隨著大量文字信息開始以計算機可讀形式存在，其數(shù)量也急劇增加，用機器學習工具快速、自動地將文本分類已成為當今一個重要的研究課題。文本分類是指給定分類體系，將文本分到某個或者某幾個類別中。比如：對于一篇新聞報道，從不同角度分析，可以將其劃分到不同的話題中，也就是說一篇新聞報道可以看作是經(jīng)濟類、政治類和體育類等。b)場景分類[4][5]b)場景分類[4][5]場景圖像普遍存在，人們很容易識別場景圖像屬于哪個主題。大多數(shù)的場景圖像都屬于一個主題，但也有部分場景圖像不只屬于一個主題，可以同時擁有多個主題，比如海灘、山峰、樹林和湖泊等。c)蛋白質(zhì)功能分析[6][7]蛋白質(zhì)功能分析是生物信息學領域研究的一項重要任務，近年來，使用機器學習工具來預測蛋白質(zhì)功能的問題引起了更多人的關注。眾所周知，蛋白質(zhì)允許同時擁有多個功能，它屬于多標簽分類問題，且從生物學角度看，功能類之間是相互關聯(lián)的，因此使用機器學習工具預測未知蛋白質(zhì)的功能是很有應用價值的。我們可以通過計算機的多標簽分類算法預先估計基因所擁有的功能，然后再進行生物實驗，這樣可以大大降低其成本，從而快捷有效的解決問題。除此之外，在諸如電影分類、音樂分類等領域，多標簽問題出現(xiàn)的頻率也非常高，引起了人們的研究興趣，因此對多標簽分類方法需求在持續(xù)增長。主題：多標簽分類問題的解法綜述單標簽兩類問題和單標簽多類問題可以看作多標簽分類問題的特例[8]，其中的每個樣本只屬于一個標簽，所以多標簽分類算法也可以解決單標簽分類問題。目前，根據(jù)已形成多種解決多標簽分類問題的方法，根據(jù)總體設計思路不同，將其分為兩種：一種是基于單個優(yōu)化問題的多標簽分類算法，一種是基于數(shù)據(jù)分解的多標簽分類算法。2.1基于單個優(yōu)化問題的多標簽分類算法基于單個優(yōu)化問題的多標簽分類算法的基本思想[8]是：只建立一個最優(yōu)化問題直接處理數(shù)據(jù)集中的所有樣本。多標簽數(shù)據(jù)集中的樣本擁有多個標簽，怎樣建立和求解這樣的最優(yōu)化問題是要解決的重要問題。算法的實現(xiàn)雖有一定的難度，但其優(yōu)點是它沒有改變數(shù)據(jù)集的結構，沒有破壞類別之間的關聯(lián)關系，反映了多標簽分類的特殊性質(zhì)。因此，建立一個具體的最優(yōu)化問題直接解決多標簽分類問題會有更好的性能。根據(jù)建立最優(yōu)化問題的不同方法，基于單個優(yōu)化問題的多標簽算法也可以分成多種不同的形式。2.1.1基于Adaboost算法的多標簽分類算法Adaboost算法［10］的研究及應用大多集中于分類問題，現(xiàn)在也有些應用于回歸問題。該算法是用全部的訓練樣本進行學習。其基本思想是針對同一個訓練集訓練不同的分類器，然后將這些弱分類器組合，最終構成一個更強的分類器。BoosTexter算法⑹，它就是基于AdaBoost算法的處理多標簽文本分類的方法，其中形成兩種算法，即AdaBoost.MH算法和AdaBoost.MR算法。AdaBoost.MH算法的基本原理是首先為由m個樣本和k個標簽所組成的訓練數(shù)據(jù)集分別建立m*k個權值(初始權值相同)，在每次循環(huán)中，對于容易分類的樣本減小其權值，而對于難于分類的樣本增加其權值， 經(jīng)過多次循環(huán)后，最終用這些權值預測未知數(shù)據(jù)集中新樣本的所屬標簽。AdaBoost.MR算法是為每個樣本的相關標簽排序，所排順序取決于樣本屬于該標簽的概率大小。2.1.2決策樹方法擴展為多標簽分類算法DeComite等于2003年提出了一種對可變決策樹學習算法 ［11］(AltematingDecisionTrees，簡稱ADTrees)擴展的處理多標簽問題的方法即ADTBoostMH算法［12］，是一種基于單個優(yōu)化問題的多標簽分類算法。 該算法通過擴展Schapire和Singer提出的AdaBoost.MH引，產(chǎn)生一系列類似于交替決策樹學習算法的規(guī)則，是AdaBoost.MH和ADTrees相結合的多標簽分類算法，該算法具有處理異種輸入數(shù)據(jù)的能力。C4.5算法可以通過修改來處理基因功能分類，也屬于基于單個優(yōu)化問題的多標簽分類算法［13］oC4.5算法引入一個信息熵來定義樹節(jié)點：entropy(S)=-工? p(Ci))+(g(q)logq(q)))M其中k表示標簽總數(shù)，p(ci)表示樣本屬于標簽Ci的概率，q(cj為樣本不屬于標簽G的概率，p(c)+q(c)=1。該算法的另一種修改是用樹的葉子節(jié)點表示標簽集合，即其輸出可以是多個標簽，然而由于可能的標簽組合很多，并要與每個葉子節(jié)點對應，將導致葉子節(jié)點很多。2.1.3多標簽支持向量機算法支持向量機的基本思想：最大化間隔的同時最小化錯分樣本。 Rank—SVM算法冋15］是Elisseeff和Weston于2002年提出的采用支持向量機思想實現(xiàn)的多標簽分類算法，最大化分類問隔和最小化排序損失。而最大化間隔標簽算法 何(MML)也是支持向量機形式的多標簽分類算法，其基本思想和 Rank-SVM算法相似，只是對經(jīng)驗風險估計有所不同。MML算法的損失函數(shù)用一般的樣本錯分程度表示，而Rank-SVM算法則是使排序損失最小，即minXEJEIx||x|l5吟幣st-＜wi_叫心A+玄f21—爲屮做“左＞＞升，當樣本數(shù)或標簽數(shù)比較大時，會導致產(chǎn)生的二次規(guī)劃問題的變量增多，從而難以計算。多標簽k近鄰算法[17][18](ML-KNN)該算法是以k近鄰算法為基礎的基于單個優(yōu)化問題的多標簽分類算法。該算法在訓練階段要計算樣本的先驗概率及條件概率，然后在測試階段用貝葉斯規(guī)則計算后驗概率，最終確定樣本的所屬標簽。然而求得的條件概率是一個統(tǒng)計值，對那些無法保證獨立同分布的特殊樣本不一定準確，這也是該算法的不足之處。反向傳播多標簽學習算法[19](BP-MLL)該算法是一種用BP神經(jīng)網(wǎng)絡處理多標簽分類問題的方法?；緲嫾芊譃槿龑樱狠斎雽?單元個數(shù)=樣本維數(shù)西；中間層(單元個數(shù)取決于訓練樣本數(shù)歷)；輸出層(單元個數(shù)依賴于標簽總數(shù)助，前兩層之間有d*m個權值，后兩層之間有m*k個權值。調(diào)整權值的方法是通過使目標函數(shù)的平方和最小來得到，最終達到學習的目的。多標簽最大化熵算法[20](MLME)MLME也是基于單個優(yōu)化問題的多標簽分類算法，其模型同時考慮了樣本和標簽之間的關系及標簽與標簽之間的關系，并使用了一個正則化參數(shù)來調(diào)整經(jīng)驗風險和實際分布，從而避免產(chǎn)生過學習的現(xiàn)象?；跀?shù)據(jù)分解的多標簽分類算法基于數(shù)據(jù)分解的多標簽分類算法[21]實質(zhì)上是將多標簽分類問題分解為多個單標簽分類子問題，然后使用現(xiàn)有的單標簽分類方法處理這些子問題，再將所有子問題的解集成，最終得到總的多標簽分類問題的解。對數(shù)據(jù)分解可以根據(jù)標簽信息分解，也可以根據(jù)樣本信息分解。根據(jù)分解方法的不同，有“一對一''方法、“一對多"方法、樣本剔除方法、標簽冪集方法等。2.2.1“一對一''分解策略“一對一''分解策略[22]是指對于含有后個標簽的數(shù)據(jù)集，對任意兩個標簽構造一個兩類分類器，只對含有這兩個標簽的樣本進行分類，這樣的兩兩配對一共存在k(k一1)/2種情況，從而產(chǎn)生k(k—1)/2個不同的分類器，即將含有k個標簽的多標簽分類問題分解成k(k一1)／2個單標簽兩類問題。根據(jù)多標簽分類問題的特性，分解后的子問題中的樣本所屬標簽種類有三種可能：①只屬于第一個標簽的樣本；②只屬于第二個標簽的樣本；③同時屬于這兩個標簽的樣本。根據(jù)解決子問題的不同，形成了多種多標簽分類算法。直接將子問題看成兩類分類問題，忽略③，然后用兩類分類器進行分類。比如Model-i算法[19]，很顯然，其速度較快但其正確率不高。用兩個兩類分類器處理子問題，比如Model-x算法[19]和多標簽成對比較算法[20]，其思想是第一個分類器將樣本分成只包含第一個標簽的樣本和包含第二個標簽的樣本兩類，第二個分類器則將樣本分成只包含第二個標簽的樣本和包含第一個標簽的樣本兩類，這樣每個樣本可以確定它的相關標簽；兩者不同之處是前者將雙標簽樣本看作正類，而后者則將雙標簽樣本看作負類。這種方法正確率比較高，但它的訓練速度會比較慢。平行支持向量機算法[21](PSVM)和基于兩類和三類支持向量機的快速多標簽分類算法 [22]是直接

創(chuàng)造一種三類分類器處理子問題，但前者的變量個數(shù)是樣本總數(shù)的兩倍，而后者的變量總數(shù)是樣本總數(shù)加上混合類樣本數(shù)，因此后者要比前者規(guī)模小，速度上更快一些，測試階段的集成工作采用常見的“投票法"，最終給定一個投票值，對于某樣本大于該值的標簽集合就是該樣本的預測標簽。“一對多"分解策略“一對多"分解策略[21][22]中，標簽總數(shù)為k的數(shù)據(jù)集分解方法是建立k個分類器，第i個分類器將含有第i個標簽的樣本與其余樣本分開，即第f個分類器將含第i個標簽的樣本看作一類，不含標簽i的樣本看作另一類，每個分類器也是使用現(xiàn)有的兩類分類算法來解決。處理單標簽兩類問題的方法比較多，如尼近鄰算法、C4.5算法、貝葉斯分類算法，支持向量機算法等[2]。根據(jù)使用的兩類分類算法的不同，實現(xiàn)了多種不同的多標簽算法，比如 OVRkNN算法（使用k近鄰算法）、0VRC4.5（使用C4.5算法）、OVRNB算法（使用貝葉斯算法）和OV—SVMJ法（使用支持向量機算法）。樣本剔除方法樣本剔除方法[23]實現(xiàn)比較簡單，其基本思想是將原數(shù)據(jù)集中含有兩個或兩個以上標簽的樣本剔除掉，只保留含有一個標簽的樣本。轉(zhuǎn)化后的問題比起原問題簡單，但剔除的樣本體現(xiàn)了原問題的主要特征，因此，剔除后的新問題不能正確反映原問題的本質(zhì)標簽冪集法標簽冪集法[23]的具體做法：引入新的標簽將多標簽分類問題中含有多個標簽的樣本轉(zhuǎn)化為單標簽樣本。若原問題中不同標簽組合很多，則新的標簽就越多，從而導致總標簽數(shù)增加?？偨Y本次我主要總結了對于多標簽分類問題的流行算法。首先在第一種思路中，算法的實現(xiàn)雖有一定的難度，但它沒有改變數(shù)據(jù)集的結構，沒有破壞類別之間的關聯(lián)關系，反映了多標簽分類的特殊性質(zhì)。而第二種思路更為直觀、簡便。 SVM在單標簽分類問題中有著很好的表現(xiàn)，分類精度及收斂速度都優(yōu)于其他方法。從而我覺得可以順著第二種思路，用變形后的 SVM來訓練分類器。其中，因為數(shù)據(jù)集存在著內(nèi)在的聯(lián)系，由文獻[9]知,SVM在局部上的表現(xiàn)，很多情況下要優(yōu)于全局，所以我希望能夠?qū)⒕植縎V啲算法改進后用到多標簽分類問題的求解上，這也是我下一步工作的重點。參考文獻M．L．Zhang，Z．H．Zhou．ML-kNN：Alazylearningapproachtomulti—labellearning．PatternRecognition，V01.40，PP.2038-2048，2007．Y．Freund，R．E．Schapire．Adecision—theoreticgeneralizationofon—linelearningandanapplicationtoboosting．JournalofComputerandSystemSciences，V01．55，No.1，pp.119-139，1997.'99)'99)Proc.WorkingNotesAm.Assoc.ArtificialIntelligenceWorkshopTextLeaming（AAAl，Orlando，F(xiàn)L，1999M．R．Boutell，J.Luo，X．Shen，andC．M．Brown．Learningmulti-labelsceneclassification．PatternRecognition，V01.37，No.9，PP.1757-1771，2003.X．Li，L．Wang，andE．Sung．Multi—LabelSVMactivelearningforimageclassification．In：ProceedingsOf2004internationalconferenceonImageProcessing（ICIP ，v01'．04，）Singapore，PP．2207—2210，2004．P．Pavlidis，J.Weston，J.CaiandW:N.Grundy.Combiningmicroarrayexpressiondataandphylogeneticprofilestolearnfunctionalcategoriesusingsupportvectormachines．In:ProceedingsofthefifthAnnualinternationalConferenceonComputationalMolecularBiology,Canada：Montreal，PP．242-248，2001．S．Diplaris，GTsoumakas，P．MitkasandI．Vlahavas．Proteinclassificationwithmultiplealgorithms．In：Proceedingsofthe10mPanhellenicConferenceonInformatics（PCI2005），Greece：Volos，LNCS3746，PP．448—456，2005．[6]A．Elisseeff,J．Weston．Akernelmethodformulti．1abelledclassification．In：ProceedingsofAdvancesinNeuralInformationProcessingSystems，Canada：Vancouver,V01．14，PP．681-687，2002L.Bottou,V.Vapnik.Locallearningalgorithms.NeuralComputation4（1992）888 -900.YFreund，R．E．Schapire．Adecision—theoreticgeneralizationofon-linelearningandanapplicationtoboosting．In：Vitanyi，P．M．B．（ed．）EuroCOLT1995．LNCS，V01．904，PP．23．37，Springer，Heidelberg,1995.YFreund，L．Mason．Thealternatingdecisiontreelearningalgorithm．In：ProceedingsoftheSixteenthInternationalConferenceonMachineLearning，ICML，PP．12-133，1999[12]F．D．Comite，R．GilleronandM．Tommasi．Learningmulti—labelalternatingdecisiontreesfromtextsanddata．In：P．Perner,A．Rosenfeld，（Eds．）MLDM2003.LNCS，V01．2734，PP．35—49，Springer,Heidelberg，2003．A．Clare,R.D.King．Knowledgediscoveryinmulti—labelphenotypedata.In:Proceedingsofthe5mEuropeanConferenceonPrinciplesofDataMiningandKnowledgeDiscovery,Germany：Freiburg，V01．2168，PP．42-53，2001．A．Elisseeff,J．Weston．Akernelmethodformulti．1abelledclassification．In：ProceedingsofAdvancesinNeuralInformationProcessingSystems，Canada：Vancouver,V01．14，PP．681-687，2002．A．Elisseeff,J．Weston．Kernelmethodsformulti．1abelledclassificationandcategoricalregressionproblems．Technicalreport，BIOwulfTechnologies，2001．H．Kazawa,T．Izumitant，H．Taira,andE．Maeda．Maximalmarginlabelingformulti-topictextcategorization．In：ProceedingsofAdvancesinNeuralInformationProcessingSystems，Canada：Vancouver,V01.16,PP.647-656,2004.49A．Elisseeff,J．Weston．Kernelmethodsformulti．1abelledclassificationandcategoricalregressionproblems．Technicalreport，BIOwulfTechnologies，2001．H．Kazawa,T．Izumitant，H．Taira,andE．Maeda．Maximalmarginlabelingformulti-topictextcategorization．In：ProceedingsofAdvancesinNeuralInformationProcessingSystems，Canada：Vancouver,V01．16，PP．647-656，2004.49M．L．Zhang，Z．H．Zhou．Multi—labelneuralnetworkswithapplicationtofunctiongenomicsandtextcategorization．IEEETransactiononKnowledgeandDataEngineering，V01．18，No．10，PP．1338—1351，2006．S．H．Zhu，X．Ji，w．Xu，andYH．Gong．Multi—labelledclassificationusingmaximumentropymethod．In：Proceedingsofthe28thAnnualInternationalAC