一種基于Tri-training的半監督多標記學習文檔分類算法

高嘉偉,梁吉業,劉楊磊,李 茹

(1. 山西大學 計算機與信息技術學院，山西 太原 030006；2. 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006)

?

一種基于Tri-training的半監督多標記學習文檔分類算法

高嘉偉1,2,梁吉業1,2,劉楊磊1,2,李 茹1,2

(1. 山西大學 計算機與信息技術學院，山西 太原 030006；2. 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006)

多標記學習主要用于解決因單個樣本對應多個概念標記而帶來的歧義性問題，而半監督多標記學習是近年來多標記學習任務中的一個新的研究方向，它試圖綜合利用少量的已標記樣本和大量的未標記樣本來提高學習性能。為了進一步挖掘未標記樣本的信息和價值并將其應用于文檔多標記分類問題，該文提出了一種基于Tri-training的半監督多標記學習算法(MKSMLT)，該算法首先利用k近鄰算法擴充已標記樣本集，結合Tri-training算法訓練分類器，將多標記學習問題轉化為標記排序問題。實驗表明，該算法能夠有效提高文檔分類性能。

半監督學習；多標記學習；文檔分類

1 引言

多標記學習(multi-label learning)[1]是近年來機器學習領域中的研究熱點問題之一。在多標記學習問題中，一個訓練樣本可能同時對應多個不同的類別標記，以表達其豐富的語義信息，那么學習的任務是為待分類樣本預測其可能對應的類別標記集合。多標記學習問題廣泛存在于真實世界中，比如在文檔分類任務中，如圖1所示的一篇關于“2016年巴西奧運會”的網頁文檔中，同時擁有“體育”、“志愿者”以及“南美洲”等多個類別標記。

如果每個樣本只對應一個類別標記，那么多標記學習問題可以退化為傳統的兩類或多類學習問題。然而，多標記學習的普適性使得其相對于傳統的學習問題更加地復雜并難以解決。當前，多標記學習面臨的最大挑戰在于標記輸出空間過大，即與一個待學習樣本相關聯的候選類別標記集合的數量將會隨著標記空間的增大而成指數規模增加。如何充分利用標記之間的相關性是構造具有強泛化能力多標記學習算法的關鍵。按照考察標記之間相關性的不同方式， 已有的多標記學習問題求解策略大致分為三類，即“一階”策略、“二階”策略和“高階”策略[2]。

圖1 多標記學習網頁文檔分類示例圖

傳統的多標記學習通常是在監督意義下考慮的，即要求訓練集的所有樣本必須是已標記樣本。然而，在現實生活中，雖然獲取大量的訓練樣本并不十分困難，但是為這些數據提供準確完備的類別標記卻需要耗費大量的時間和人力資源。例如，在上述網頁文檔分類任務中，現實世界中存在著海量的未標記文檔，且每一篇文檔可能擁有大量的候選類別標記。如果要完整標注訓練集中的每一個樣本就意味著需要查看每一篇文檔的所有候選類別并逐一標注。當數據規模較大或者候選類別數目較多時，要獲得完整類別標記的訓練樣本集是非常困難的。此時，如果只使用少量已標記樣本訓練，則得到的模型很難具有較強的泛化能力。而半監督學習能夠較好地解決上述問題，它綜合利用少量的已標記樣本和大量的未標記樣本以提高泛化性能[3-4]。因而，融合半監督學習機制的半監督多標記學習方法成為近年來新的研究熱點。

2 背景知識

2.1 多標記學習之k近鄰算法

2007年，張敏靈等人[5]把傳統的k近鄰學習算法擴展到多標記學習領域，提出了ML-kNN算法。它對于給定的分類測試樣本，首先確定其在訓練集中的k個近鄰，然后根據挑選出的這些近鄰樣本的類別標記集合所蘊含的統計信息，利用最大化后驗概率準則確定測試樣本的標記集合。在若干多標記學習問題上的應用表明，ML-kNN算法的性能，尤其是算法執行效率方面，優于其他一些常用的多標記學習算法。

2.2 多標記學習之文檔分類

多標記學習起源于文檔分類研究中遇到的歧義性問題[6]。2000年，Schapire等人[7]在MachineLearning上發表文章，提出了一種基于集成學習的BoosTexter方法。該方法是對AdaBoost算法的擴展，它在訓練過程中不僅要改變訓練樣本的權重，同時還要改變類別標記的權重。在此之后，多標記文檔分類問題引起了學界的廣泛關注。

2001年，Amanda Clare等人[8]通過改變熵的形式，改造了C4.5決策樹分類算法，并使其適應多標記數據的處理。2012年，張敏靈[9]提出了一種新型多標記懶惰學習算法。它首先以測試樣本為起點，按照不同的類別，對應找出這些測試樣本在訓練集中近鄰樣本，然后構造一個標記計數向量，并提交給已訓練得到的分類器進行預測。2013年，程圣軍等人[10]提出了一種改進的ML-kNN多標記文檔分類算法，其中文檔相似度利用KL散度的距離來度量，并根據k個近鄰樣本所屬類別的統計信息，通過一種模糊最大化后驗概率法則來預測未標記文檔的標記集合。

目前關于文檔分類的多標記學習主要集中在監督意義下。在現實生活中，為訓練集標注正確完備的類別標記需要耗費大量的人力和時間。因此，如果只有少量已標記樣本可以利用時，傳統的多標記學習算法已不再完全適用。

2.3 半監督多標記學習

近來年，一些學者開始關注半監督多標記學習(semi-supervised multi-label learning)或直推式多標記學習(transductive multi-label learning)，并取得了一些研究成果。兩者的相同點是學習目的相同，都是希望從大量的未標記樣本獲取有價值的信息來輔助少量已標記樣本的學習。但是二者的基本思想與測試環境卻完全不同。直推式學習要求測試樣本必須是訓練集中的未標記樣本，測試環境是相對封閉的；而半監督學習并無此要求，測試樣本與訓練樣本完全無關，測試環境是開放的。

根據如果樣本具有較大相似性，那么它們對應的標記集合也可能具有較大相似性的假設，Liu等人[11]于2006年提出了CNMF方法。它通過求解一個帶約束的非負矩陣分解問題，在滿足上述兩種相似性的差值最小的情形下，希望獲得的預測樣本的標記最優。2008年，Chen等人[12]提出了SMSE方法，它利用樣本相似性與標記相似性構圖，通過標記傳播思想對未標記樣本的標記進行預測。2008年，姜遠等人[13]提出了直推式多標記學習算法TML，采用隨機游走的思想，并將其應用于文檔分類問題。針對如果訓練樣本對應的標記集合中只有小部分擁有標記，或者根本沒有任何標記，即多標記學習中的弱標記問題，Sun等人[14]和孔祥南等人[15]于2010年分別提出了WELL方法和TML-WL方法，他們都采用標記傳播的思想對缺失標記進行學習。2013年，孔祥南等人[16]同樣采用標記傳播的思想提出了TRAM算法。它首先將多標記學習任務看作對標記集合進行估計的優化問題，在得出封閉解的基礎上，給未標記樣本分配其對應的標記。以上方法都是直推式方法，這類方法不能對非測試樣本進行預測，具有一定的局限性。2012年，李宇峰等人[17]針對歸納式半監督多標記學習，引入正則項使得相似的樣本擁有相似的標記和約束分類器的復雜度，提出了一種正則化方法MASS算法。

但是上述方法都沒有考慮到目前半監督學習重要的方法之一的協同訓練機制[18]在多標記學習領域的擴展和應用。2013年，劉楊磊等人[19]以協同訓練思想為核心，以兩兩標記之間的關系為出發點，利用Tri-training算法[20]訓練分類器，并將多標記學習問題轉化為標記排序問題進行求解，提出了半監督多標記學習SMLT算法。從文獻[19]中實驗部分可以看出，已標記樣本集的規模對于最終的分類結果有較大影響。因而當已標記樣本集在已經給定的情形下，如何充分利用現有的數據來擴充已標記樣本集從而提高多標記學習的分類性能成為本文的研究動機。

3 本文算法

本文提出了一種基于Tri-training的半監督多標記學習算法(MKSMLT)，該算法首先利用k近鄰算法擴充已標記樣本集，并結合Tri-training算法訓練得到分類器，將多標記學習問題轉化為標記排序問題。

為了能夠針對后續分類過程中產生的標記排序結果進行有效客觀的分析，并得到最終的預測標記結果,因而在算法的預處理階段，給所有訓練樣本xi添加虛擬標記yi0，并把測試樣本通過分類算法在虛擬類標記上的得票數作為閾值對標記排序結果進行有效劃分。因此，引入虛擬類標記后，涉及到標記的下標都應從0開始。

3.1 算法思想

傳統多標記學習無法充分利用大量的未標記樣本，僅憑借少量已標記樣本訓練得到的分類器泛化能力不強。因此，利用協同訓練Tri-training算法訓練分類器，能夠綜合利用少量的已標記樣本和大量的未標記樣本以提高泛化性能。為了進一步挖掘未標記樣本的信息和價值，在訓練分類器之前首先利用ML-kNN算法對未標記樣本集進行預測，然后將預測標記中置信度較高的樣本添加至已標記樣本集中，以實現對已標記樣本集的擴充。

首先，利用ML-kNN算法，將未標記樣本集U中滿足條件的樣本擴充至已標記樣本集L中。此時，為了將置信度較高的樣本添加至已標記樣本集L中得到擴充后的已標記樣本集Lnew，需要設置一個閾值th篩選置信度較高的樣本。由于不同的數據差別較大，該閾值由經驗確定。

最后，在測試過程中，針對某個測試樣本，用學習得到的3個分類器，對其在每一標記進行預測，并統計每個標記所得的票數Rsj，并最終得到該測試樣本在所有標記上的一個標記排序結果。在此利用虛擬標記y″s0的得票數Rs0作為劃分所取類標記的依據。如果Rsj>Rs0,(j=1,2,…,n)，則樣本x″s在第j個標記的取值為1，即y″sj=1；否則y″sj=0。這樣就可以得出對測試樣本的分類結果Y″。

3.2 算法流程

算法流程圖如圖2所示。

圖2 算法流程圖

輸入：原始已標記樣本集L，未標記樣本集U，測試集T

輸出：測試集T的分類結果Y″

步驟1 初始化用于存放投票數的Rsj和用于臨時存放訓練樣本的集合Vpq，使Rsj=0,(s=1,2,…,w;j=0,1,…,n)，Vpq=φ,(0≤p

步驟2 利用ML-kNN算法以及由經驗值確定的閾值th對已標記樣本集L進行擴充，得到新的已標記樣本集L*。其中ML-kNN算法的參數設置為文獻[6]中公布的最好參數，即最近鄰數k=10，平滑指數smooth=1。

步驟5 利用得到的3個分類器對測試集T中的未標記樣本x″s,(s=1,2,…,w)進行預測，得出分類結果rspq并分別統計對應標記獲得的投票數。如果rspq=1，則樣本x″s屬于第p類標記，對應的Rsp自增1；如果rspq=0，則樣本x″s屬于第q類標記，對應的Rsq自增1。

步驟7 對于測試集T中的未標記樣本x″s，如果其在第j個標記上獲得的投票數Rsj大于虛擬標記獲得的投票數Rs0，即Rsj>Rs0,(j=1,2,…,n)，則未標記樣本x″s在第j個標記的取值為1，即y″sj=1；否則y″sj=0。最終可以輸出測試集的預測標記集合Y″={Y″s,s=1,2,…,w}。

4 實驗

本文實驗分為兩個部分，一是在各個領域中常用的多標記數據集上的實驗對比，二是在網頁文檔分類領域中的“yahoo.com”數據集上的實驗對比。

4.1 在常用多標記數據集上的對比實驗

本文分別在emotions、scene、yeast、enron4個常用的多標記數據集[21]上，與多標記學習的多種算法實驗對比，其中包括ML-kNN[5]、TRAM[16]以及SMLT[19]。實驗數據集的相關信息如表1所示。

表1 實驗數據集相關信息

實驗選用常用的4種多標記學習評價指標(Hamming Loss，One-Error，Coverage，Ranking Loss)對算法性能進行評估。這4種評價指標的值越小，表明多標記學習算法的分類性能越好[22]。

實驗抽取各數據集的90%作為訓練樣本集(其中10%的訓練樣本是已標記樣本集L，90%的訓練樣本是未標記樣本集U)，其余10%的數據為測試樣本集T，重復10次統計其平均結果。由于TRAM算法屬于直推式方法，不能直接對未見樣本進行預測，因而實驗中將測試樣本T也并入TRAM訓練時的未標記樣本集U中。TRAM的參數k取值為10。

表2到表5列出了相關實驗結果，加粗部分為每個指標上的最佳性能。

表2 數據集yeast上各算法實驗結果

續表

表3 數據集emotions上各算法實驗結果

表4 數據集scene上各算法實驗結果

表5 數據集enron上各算法實驗結果

通過分析表2至表5，在以上4個數據集中，本文提出的MKSMLT算法大部分都取得了較好的分類結果，4個評估指標大多優于其他同類算法。

4.2 在文檔分類領域中數據集上的對比實驗

本文選用了2個“yahoo.com”數據集進行了實驗，數據集來自于真實的網頁文檔。這兩個數據集分別對應于yahoo的Business&Economy和Science兩個一級類別，每個網頁再根據yahoo的二級類別賦予標記。由于每個網頁可能同時隸屬于多個二級類別，因此，該數據集是較為典型的網頁文本分類的多標記數據集。每個數據集都包括2 000個訓練樣本和3 000個測試樣本。

實驗同樣采用上文所述的Hamming Loss，One-Error，Coverage，Ranking Loss 這4種常用的多標記學習評價指標對算法性能進行評估。

實驗將抽取每個數據集2 000個訓練樣本中的10%為已標記樣本集L，其余的90%為未標記樣本集U，同時從3 000個測試樣本中隨機抽取300個樣本作為測試集T。實驗中TRAM算法設置同上。

表6和表7給出了實驗結果，加粗部分為每個指標上的最佳性能。

表6 數據集Business&Economy上各算法實驗結果

表7 數據集Science上各算法實驗結果

通過分析表6和表7，在兩個數據集上，本文提出的MKSMLT算法大部分都取得了較好的分類結果，四個評估指標大多優于其他同類算法。

5 總結與展望

本文針對廣泛存在于現實生活中的半監督多標記學習問題，綜合利用少量的已標記樣本和大量的未標記樣本，充分挖掘未標記樣本的信息和價值，首先利用ML-kNN算法擴充已標記樣本集，以多標記的“二階”策略為出發點，結合Tri-training算法訓練得到多標記學習分類器，將多標記學習問題轉化為標記排序問題求解，并將其應用于文檔文類領域。實驗結果表明了本文提出算法的有效性。但是，當多標記學習問題中的標記的數量和樣本的規模較大時，如何進一步降低算法的計算復雜度以及閾值參數th的選定仍將是需要深入討論的問題。

[1]TsoumakasG,KatakisI.Multi-labelclassification:Anoverview[J].InternationalJournalofDataWarehousingandMining, 2007,3(3): 1-13.

[2]ZhangMinling,ZhangK.Multi-labellearningbyexploitinglabeldependency[C]//Proceedingsofthe16thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,Washington,D.C., 2010, 999-1007.

[3]ZhuXiaojin.Semi-supervisedLearningLiteratureSurvey[R].MadisonUniversityofWisconsin,2008.

[4] 常瑜, 梁吉業, 高嘉偉,等. 一種基于Seeds集和成對約束的半監督聚類算法[J]. 南京大學學報(自然科學版), 2012,48(4): 405-411.

[5]ZhangMinling,ZhouZhihua.ML-kNN:Alazylearningapproachtomulti-labellearning[J].PatternRecognition, 2007, 40(7): 2038-2048.

[6] 廣凱, 潘金貴. 一種基于向量夾角的k近鄰多標記文本分類算法[J]. 計算機科學, 2008,35(4): 205-207.

[7]RobertE.Schapire,YoramSinger.BoosTexter:aboosting-basedsystemfortextcategorization[J].MachineLearning, 2000, 39(2-3):135-168.

[8]AmandaClare,RossD.King.Knowledgediscoveryinmulti-labelphenotypedata[J].LectureNotesinComputerScience, 2001, 2168:42-53.

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

[10] 程圣軍, 黃慶成, 劉家鋒,等. 一種改進的ML-kNN多標記文檔分類方法 [J]. 哈爾濱工業大學學報，2013,45(11): 45-49.

[11]LiuYi,JinRong,YangLiu.Semi-supervisedmulti-labellearningbyconstrainednon-negativematrixfactorization[C]//Proceedingsofthe21stNationalConferenceonArtificialIntelligence.MenloPark:AAAI,2006: 421-426.

[12]ChenGang,SongYangqiu,WangFei,etal.Semi-supervisedmulti-labellearningbySolvingaSylvesterequation[C]//ProceedingsofSIAMInternationalConferenceonDataMining.LosAlamitos,CA:IEEEComputerSociety, 2008: 410-419.

[13] 姜遠,佘俏俏,黎銘,等. 一種直推式多標記文檔分類方法[J]. 計算機研究與發展,2008,45(11): 1817-1823.

[14]SunYuyin,ZhangYin,ZhouZhihua.Multi-labellearningwithweaklabel[C]//Proceedingsofthe24thAAAIConferenceonArtificialIntelligence.MenloPark:AAAI, 2010: 593-598.

[15] 孔祥南, 黎銘, 姜遠,等. 一種針對弱標記的直推式多標記分類方法[J]. 計算機研究與發展. 2010,47(8):1392-1399.

[16]XiangnanKong,MichaelK.Ng,ZhouZhihua.TransductiveMulti-labelLearningviaLabelSetPropagation[J].IEEETransactionsonKnowledgeandDataEngineering, 2013,25(3): 704-719.

[17] 李宇峰, 黃圣君, 周志華. 一種基于正則化的半監督多標記學習方法[J]. 計算機研究與發展. 2012,49(6): 1272-1278.

[18] 周志華,王玨. 半監督學習中的協同訓練算法[M]. 機器學習及其應用.北京:清華大學出版社, 2007: 259-275.

[19] 劉楊磊, 梁吉業, 高嘉偉,等. 基于Tri-training的半監督多標記學習算法[J]. 智能系統學報.2013, 8(5):439-445.

[20]ZhouZhihua,LiMing.Tri-training:Exploitingunlabeleddatausingthreeclassifiers[J].IEEETransactionsonKnowledgeandDataEngineering, 2005, 17(11): 1529-1541.

[21]http://mulan.sourceforge.net/datasets.html[OL].

[22]ZhouZhihua,ZhangMinling,HuangShengjun,etal.Multi-instancemulti-labellearning[J].ArtificialIntelligence, 2012, 176:2291-2320.

A Tri-training Based Semi-supervised Multi-label Learning for Text Categorization

GAO Jiawei1,2， LIANG Jiye1,2，LIU Yanglei1,2，LI Ru1,2

(1. School of Computer and Information Technology, Shanxi University, Taiyuan, Shanxi 030006, China；2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Taiyuan, Shanxi 030006,China)

Multi-label learning is proposed to deal with the ambiguity problem in which a single sample is associated with multiple concept labels simultaneously, while the semi-supervised multi-label learning is a new research direction in recent years. To further exploit the information of unlabeled samples, a semi-supervised multi-label learning algorithm based on Tri-training(MKSMLT) is proposed. It adopts ML-kNN algorithm to get more labeled samples, then employs the Tri-training algorithm to use three classifiers to rank the unlabeled samples. Experimental results illustrate that the proposed algorithm can effectively improve the classification performance.

semi-supervised learning； multi-label learning； text categorization

高嘉偉(1980—)，講師，博士研究生，主要研究領域為機器學習。E?mail：gjw@sxu．edu．cn梁吉業(1962—)，博士，教授，博士生導師，主要研究領域為機器學習、計算智能、數據挖掘等。E?mail：ljy@sxu．edu．cn劉楊磊(1990—)，碩士研究生，主要研究領域為機器學習。E?mail：lyl＿super@126．com

1003-0077(2015)01-0104-07

2013-03-23 定稿日期： 2014-12-15

國家重點基礎研究發展規劃(973)前期研究專項(2011CCB311805)；國家自然科學基金(61432011，61100058，61202018)；山西省科技攻關項目(20110321027-01)；山西省科技基礎條件平臺建設項目(2012091002-0101)

TP391

A