[發(fā)明專利]一種適用于多標(biāo)簽分類的ML?kNN改進(jìn)方法和系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201710278015.8
• 申請日: 2017-04-25
• 公開（公告）號(hào): CN107133293A
• 公開（公告）日: 2017-09-05
• 發(fā)明（設(shè)計(jì)）人: 劉鵬鶴;孫曉平;孫毓忠
• 申請（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06K9/62
• 代理公司: 北京律誠同業(yè)知識(shí)產(chǎn)權(quán)代理有限公司11006
• 代理人: 祁建國,梁揮

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)器學(xué)習(xí)領(lǐng)域，特別涉及一種適用于多標(biāo)簽分類的ML-kNN改進(jìn)方法和系統(tǒng)。

背景技術(shù)

在傳統(tǒng)的單標(biāo)簽分類中，是從一系列只具有一個(gè)標(biāo)簽l的樣本中進(jìn)行學(xué)習(xí)，其中l(wèi)來自標(biāo)簽集合L，|L|>1。如果|L|＝2，學(xué)習(xí)問題便稱為二分類問題；如果|L|>2，學(xué)習(xí)問題便是一個(gè)多分類問題。然而，在多標(biāo)簽分類中，一個(gè)樣本往往具有若干個(gè)標(biāo)簽Y，其中在現(xiàn)實(shí)中，有許多標(biāo)簽分類問題，如文本分類，一篇文本可能既是體育類又是政治類；又如醫(yī)學(xué)上的疾病診斷，一個(gè)患者往往具有多種并發(fā)癥，如患者可能同時(shí)具有呼吸道感染，支氣管炎和肺炎三種疾病。論文(Tsoumakas G,Katakis I.Multi-Label Classification:An Overview[J].International Journal ofData Warehousing&Mining,2010,3(3):1-13)將解決多標(biāo)簽分類的方法歸為2類，一類是問題轉(zhuǎn)換方法，另一類則是算法適應(yīng)方法。前者之所以稱為問題轉(zhuǎn)換方法，是其將多標(biāo)簽分類問題轉(zhuǎn)換成一個(gè)或多個(gè)單標(biāo)簽分類問題；后者稱為算法適應(yīng)方法則是其嘗試將學(xué)習(xí)算法進(jìn)行擴(kuò)展以適應(yīng)多標(biāo)簽數(shù)據(jù)集。最常見的一種問題轉(zhuǎn)換方法(Boutell M R,Luo J,Shen X,et al.Learning multi-label scene classification☆[J].Pattern Recognition,2004,37(9):1757-1771.)是將原始數(shù)據(jù)集劃分為|L|個(gè)子數(shù)據(jù)D_l，每一個(gè)子數(shù)據(jù)集中的樣本如果其具有l(wèi)標(biāo)簽則將其標(biāo)記為l，否則標(biāo)記為隨后利用|L|個(gè)子數(shù)據(jù)集訓(xùn)練|L|個(gè)二分類器，當(dāng)對樣本進(jìn)行分類時(shí)，則分別用這|L|個(gè)二分類器進(jìn)行預(yù)測。最后取這|L|個(gè)二分類器預(yù)測結(jié)果的并集作為最種的樣本預(yù)測標(biāo)簽集合。在算法適應(yīng)方法上，論文(ClareA,KingRD.KnowledgeDiscoveryinMulti-label Phenotype Data[J].Lecture Notes in Computer Science,2001,2168(2168):42-53.)將C4.5算法適用到多標(biāo)簽數(shù)據(jù)上，并對熵計(jì)算公式進(jìn)行修改從而允許決策樹上的葉子結(jié)點(diǎn)具有多個(gè)標(biāo)簽。論文(Schapire R E,Singer Y.BoosTexter:A Boosting-based System for Text Categorization[J].Machine Learning,2000,39(2):135-168.)對AdaBoost算法(Freund,Yoav,Schapire,Robert E.A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting[J].Journal of Computer&System Sciences,1997,55(1):119-139.)進(jìn)行擴(kuò)展提出了Adaboost.MH和Adaboost.MR以適應(yīng)于多標(biāo)簽分類。在Adaboost.MH中，預(yù)測一個(gè)樣本時(shí)，考慮標(biāo)簽l，如果弱分類器輸出為正，則將該標(biāo)簽加入樣本的預(yù)測標(biāo)簽集合中，反之則不加；在MR中，弱分類器的輸出則用來對標(biāo)簽集合L進(jìn)行排序以確定最終的輸出。論文(Godbole S,Sarawagi S.Discriminative Methods for Multi-labeled Classification[M]//Advances in Knowledge Discovery and Data Mining.Springer Berlin Heidelberg,2004:22-30.)對支持向量機(jī)(SupportVector Machine)做了一些改進(jìn)以支持多標(biāo)簽數(shù)據(jù)，其首先將距離分類超平面的距離小于一定閾值的負(fù)訓(xùn)練樣本去掉，隨后又將經(jīng)驗(yàn)證集測試出的與正樣本相近的負(fù)訓(xùn)練樣本去掉。論文(Thabtah F A,Cowling P,Peng Y.MMAC:A New Multi-Class,Multi-Label Associative Classification Approach[C]//IEEE International Conference on Data Mining.IEEE,2004:217-224.)針對多標(biāo)簽問題提出了MMAC算法，該算法利用關(guān)聯(lián)規(guī)則挖掘的方法處理分類規(guī)則的構(gòu)建，其首先利用關(guān)聯(lián)規(guī)則挖掘算法學(xué)習(xí)出一個(gè)初始的分類規(guī)則集合，然后刪掉與這些規(guī)則相對應(yīng)的樣本，繼續(xù)從剩余樣本中學(xué)習(xí)分類規(guī)則，如此反復(fù)，直到?jīng)]有新的規(guī)則出現(xiàn)。在這些規(guī)則中，存在同樣的前綴條件但不同標(biāo)簽的情況，從而將這些規(guī)則合并為一個(gè)多標(biāo)簽規(guī)則。ML-kNN(Zhang M L,Zhou Z H.A k-nearest neighbor based algorithm for multi-label classification[C]//IEEE International Conference on Granular Computing.IEEE,2005:718-721Vol.2.)是kNN懶惰學(xué)習(xí)算法的進(jìn)化以適應(yīng)在多標(biāo)簽數(shù)據(jù)集。ML-kNN對每一個(gè)標(biāo)簽l獨(dú)立地使用kNN算法(多標(biāo)簽k近鄰算法)：對一個(gè)測試樣本，其找出在訓(xùn)練集中與該樣本距離最相近的k個(gè)鄰居并將其中帶有標(biāo)簽l的樣本為正樣本，其余的則為負(fù)樣本，從而根據(jù)這些已經(jīng)獲取的近鄰標(biāo)簽集的統(tǒng)計(jì)信息，用最大后驗(yàn)概率原則(MAP)去決定測試樣本的標(biāo)簽集合，最大后驗(yàn)概率是基于kNN對每個(gè)標(biāo)簽的前驗(yàn)和后驗(yàn)概率。然而ML-kNN仍然有一些不足，首先由于樣本的多標(biāo)簽特性，其并沒有區(qū)分同一條樣本的不同的標(biāo)簽所對應(yīng)的特征向量，即對同一條樣本，如果其具有若干個(gè)不同的標(biāo)簽，ML-kNN方法認(rèn)為這些標(biāo)簽具有相同的特征向量，這就導(dǎo)致標(biāo)簽之間的區(qū)分度下降，增大分類的誤差；其次，在樣本的距離計(jì)算上，ML-kNN采用經(jīng)典的余弦相似度作為樣本距離的衡量指標(biāo)，這種計(jì)算方式并未考慮標(biāo)簽之間的相關(guān)性，如在醫(yī)療診斷數(shù)據(jù)集中“支氣管肺炎”和“支氣管炎”這兩個(gè)疾病標(biāo)簽是具有較強(qiáng)的相關(guān)性的，而這種相關(guān)性會(huì)對距離的計(jì)算帶來一定影響，這點(diǎn)ML-kNN方法并沒有考慮。