一種基于Tri-training的半監(jiān)督多標(biāo)記學(xué)習(xí)文檔分類(lèi)算法

高嘉偉,梁吉業(yè),劉楊磊,李 茹

(1. 山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；2. 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006)

?

一種基于Tri-training的半監(jiān)督多標(biāo)記學(xué)習(xí)文檔分類(lèi)算法

高嘉偉1,2,梁吉業(yè)1,2,劉楊磊1,2,李 茹1,2

(1. 山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；2. 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006)

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

半監(jiān)督學(xué)習(xí)；多標(biāo)記學(xué)習(xí)；文檔分類(lèi)

1 引言

多標(biāo)記學(xué)習(xí)(multi-label learning)[1]是近年來(lái)機(jī)器學(xué)習(xí)領(lǐng)域中的研究熱點(diǎn)問(wèn)題之一。在多標(biāo)記學(xué)習(xí)問(wèn)題中，一個(gè)訓(xùn)練樣本可能同時(shí)對(duì)應(yīng)多個(gè)不同的類(lèi)別標(biāo)記，以表達(dá)其豐富的語(yǔ)義信息，那么學(xué)習(xí)的任務(wù)是為待分類(lèi)樣本預(yù)測(cè)其可能對(duì)應(yīng)的類(lèi)別標(biāo)記集合。多標(biāo)記學(xué)習(xí)問(wèn)題廣泛存在于真實(shí)世界中，比如在文檔分類(lèi)任務(wù)中，如圖1所示的一篇關(guān)于“2016年巴西奧運(yùn)會(huì)”的網(wǎng)頁(yè)文檔中，同時(shí)擁有“體育”、“志愿者”以及“南美洲”等多個(gè)類(lèi)別標(biāo)記。

如果每個(gè)樣本只對(duì)應(yīng)一個(gè)類(lèi)別標(biāo)記，那么多標(biāo)記學(xué)習(xí)問(wèn)題可以退化為傳統(tǒng)的兩類(lèi)或多類(lèi)學(xué)習(xí)問(wèn)題。然而，多標(biāo)記學(xué)習(xí)的普適性使得其相對(duì)于傳統(tǒng)的學(xué)習(xí)問(wèn)題更加地復(fù)雜并難以解決。當(dāng)前，多標(biāo)記學(xué)習(xí)面臨的最大挑戰(zhàn)在于標(biāo)記輸出空間過(guò)大，即與一個(gè)待學(xué)習(xí)樣本相關(guān)聯(lián)的候選類(lèi)別標(biāo)記集合的數(shù)量將會(huì)隨著標(biāo)記空間的增大而成指數(shù)規(guī)模增加。如何充分利用標(biāo)記之間的相關(guān)性是構(gòu)造具有強(qiáng)泛化能力多標(biāo)記學(xué)習(xí)算法的關(guān)鍵。按照考察標(biāo)記之間相關(guān)性的不同方式， 已有的多標(biāo)記學(xué)習(xí)問(wèn)題求解策略大致分為三類(lèi)，即“一階”策略、“二階”策略和“高階”策略[2]。

圖1 多標(biāo)記學(xué)習(xí)網(wǎng)頁(yè)文檔分類(lèi)示例圖

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

2 背景知識(shí)

2.1 多標(biāo)記學(xué)習(xí)之k近鄰算法

2007年，張敏靈等人[5]把傳統(tǒng)的k近鄰學(xué)習(xí)算法擴(kuò)展到多標(biāo)記學(xué)習(xí)領(lǐng)域，提出了ML-kNN算法。它對(duì)于給定的分類(lèi)測(cè)試樣本，首先確定其在訓(xùn)練集中的k個(gè)近鄰，然后根據(jù)挑選出的這些近鄰樣本的類(lèi)別標(biāo)記集合所蘊(yùn)含的統(tǒng)計(jì)信息，利用最大化后驗(yàn)概率準(zhǔn)則確定測(cè)試樣本的標(biāo)記集合。在若干多標(biāo)記學(xué)習(xí)問(wèn)題上的應(yīng)用表明，ML-kNN算法的性能，尤其是算法執(zhí)行效率方面，優(yōu)于其他一些常用的多標(biāo)記學(xué)習(xí)算法。

2.2 多標(biāo)記學(xué)習(xí)之文檔分類(lèi)

多標(biāo)記學(xué)習(xí)起源于文檔分類(lèi)研究中遇到的歧義性問(wèn)題[6]。2000年，Schapire等人[7]在MachineLearning上發(fā)表文章，提出了一種基于集成學(xué)習(xí)的BoosTexter方法。該方法是對(duì)AdaBoost算法的擴(kuò)展，它在訓(xùn)練過(guò)程中不僅要改變訓(xùn)練樣本的權(quán)重，同時(shí)還要改變類(lèi)別標(biāo)記的權(quán)重。在此之后，多標(biāo)記文檔分類(lèi)問(wèn)題引起了學(xué)界的廣泛關(guān)注。

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

目前關(guān)于文檔分類(lèi)的多標(biāo)記學(xué)習(xí)主要集中在監(jiān)督意義下。在現(xiàn)實(shí)生活中，為訓(xùn)練集標(biāo)注正確完備的類(lèi)別標(biāo)記需要耗費(fèi)大量的人力和時(shí)間。因此，如果只有少量已標(biāo)記樣本可以利用時(shí)，傳統(tǒng)的多標(biāo)記學(xué)習(xí)算法已不再完全適用。

2.3 半監(jiān)督多標(biāo)記學(xué)習(xí)

近來(lái)年，一些學(xué)者開(kāi)始關(guān)注半監(jiān)督多標(biāo)記學(xué)習(xí)(semi-supervised multi-label learning)或直推式多標(biāo)記學(xué)習(xí)(transductive multi-label learning)，并取得了一些研究成果。兩者的相同點(diǎn)是學(xué)習(xí)目的相同，都是希望從大量的未標(biāo)記樣本獲取有價(jià)值的信息來(lái)輔助少量已標(biāo)記樣本的學(xué)習(xí)。但是二者的基本思想與測(cè)試環(huán)境卻完全不同。直推式學(xué)習(xí)要求測(cè)試樣本必須是訓(xùn)練集中的未標(biāo)記樣本，測(cè)試環(huán)境是相對(duì)封閉的；而半監(jiān)督學(xué)習(xí)并無(wú)此要求，測(cè)試樣本與訓(xùn)練樣本完全無(wú)關(guān)，測(cè)試環(huán)境是開(kāi)放的。

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

但是上述方法都沒(méi)有考慮到目前半監(jiān)督學(xué)習(xí)重要的方法之一的協(xié)同訓(xùn)練機(jī)制[18]在多標(biāo)記學(xué)習(xí)領(lǐng)域的擴(kuò)展和應(yīng)用。2013年，劉楊磊等人[19]以協(xié)同訓(xùn)練思想為核心，以?xún)蓛蓸?biāo)記之間的關(guān)系為出發(fā)點(diǎn)，利用Tri-training算法[20]訓(xùn)練分類(lèi)器，并將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)化為標(biāo)記排序問(wèn)題進(jìn)行求解，提出了半監(jiān)督多標(biāo)記學(xué)習(xí)SMLT算法。從文獻(xiàn)[19]中實(shí)驗(yàn)部分可以看出，已標(biāo)記樣本集的規(guī)模對(duì)于最終的分類(lèi)結(jié)果有較大影響。因而當(dāng)已標(biāo)記樣本集在已經(jīng)給定的情形下，如何充分利用現(xiàn)有的數(shù)據(jù)來(lái)擴(kuò)充已標(biāo)記樣本集從而提高多標(biāo)記學(xué)習(xí)的分類(lèi)性能成為本文的研究動(dòng)機(jī)。

3 本文算法

本文提出了一種基于Tri-training的半監(jiān)督多標(biāo)記學(xué)習(xí)算法(MKSMLT)，該算法首先利用k近鄰算法擴(kuò)充已標(biāo)記樣本集，并結(jié)合Tri-training算法訓(xùn)練得到分類(lèi)器，將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)化為標(biāo)記排序問(wèn)題。

為了能夠針對(duì)后續(xù)分類(lèi)過(guò)程中產(chǎn)生的標(biāo)記排序結(jié)果進(jìn)行有效客觀的分析，并得到最終的預(yù)測(cè)標(biāo)記結(jié)果,因而在算法的預(yù)處理階段，給所有訓(xùn)練樣本xi添加虛擬標(biāo)記yi0，并把測(cè)試樣本通過(guò)分類(lèi)算法在虛擬類(lèi)標(biāo)記上的得票數(shù)作為閾值對(duì)標(biāo)記排序結(jié)果進(jìn)行有效劃分。因此，引入虛擬類(lèi)標(biāo)記后，涉及到標(biāo)記的下標(biāo)都應(yīng)從0開(kāi)始。

3.1 算法思想

傳統(tǒng)多標(biāo)記學(xué)習(xí)無(wú)法充分利用大量的未標(biāo)記樣本，僅憑借少量已標(biāo)記樣本訓(xùn)練得到的分類(lèi)器泛化能力不強(qiáng)。因此，利用協(xié)同訓(xùn)練Tri-training算法訓(xùn)練分類(lèi)器，能夠綜合利用少量的已標(biāo)記樣本和大量的未標(biāo)記樣本以提高泛化性能。為了進(jìn)一步挖掘未標(biāo)記樣本的信息和價(jià)值，在訓(xùn)練分類(lèi)器之前首先利用ML-kNN算法對(duì)未標(biāo)記樣本集進(jìn)行預(yù)測(cè)，然后將預(yù)測(cè)標(biāo)記中置信度較高的樣本添加至已標(biāo)記樣本集中，以實(shí)現(xiàn)對(duì)已標(biāo)記樣本集的擴(kuò)充。

首先，利用ML-kNN算法，將未標(biāo)記樣本集U中滿足條件的樣本擴(kuò)充至已標(biāo)記樣本集L中。此時(shí)，為了將置信度較高的樣本添加至已標(biāo)記樣本集L中得到擴(kuò)充后的已標(biāo)記樣本集Lnew，需要設(shè)置一個(gè)閾值th篩選置信度較高的樣本。由于不同的數(shù)據(jù)差別較大，該閾值由經(jīng)驗(yàn)確定。

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

3.2 算法流程

算法流程圖如圖2所示。

圖2 算法流程圖

輸入：原始已標(biāo)記樣本集L，未標(biāo)記樣本集U，測(cè)試集T

輸出：測(cè)試集T的分類(lèi)結(jié)果Y″

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

步驟2 利用ML-kNN算法以及由經(jīng)驗(yàn)值確定的閾值th對(duì)已標(biāo)記樣本集L進(jìn)行擴(kuò)充，得到新的已標(biāo)記樣本集L*。其中ML-kNN算法的參數(shù)設(shè)置為文獻(xiàn)[6]中公布的最好參數(shù)，即最近鄰數(shù)k=10，平滑指數(shù)smooth=1。

步驟5 利用得到的3個(gè)分類(lèi)器對(duì)測(cè)試集T中的未標(biāo)記樣本x″s,(s=1,2,…,w)進(jìn)行預(yù)測(cè)，得出分類(lèi)結(jié)果rspq并分別統(tǒng)計(jì)對(duì)應(yīng)標(biāo)記獲得的投票數(shù)。如果rspq=1，則樣本x″s屬于第p類(lèi)標(biāo)記，對(duì)應(yīng)的Rsp自增1；如果rspq=0，則樣本x″s屬于第q類(lèi)標(biāo)記，對(duì)應(yīng)的Rsq自增1。

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

4 實(shí)驗(yàn)

本文實(shí)驗(yàn)分為兩個(gè)部分，一是在各個(gè)領(lǐng)域中常用的多標(biāo)記數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比，二是在網(wǎng)頁(yè)文檔分類(lèi)領(lǐng)域中的“yahoo.com”數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比。

4.1 在常用多標(biāo)記數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)

本文分別在emotions、scene、yeast、enron4個(gè)常用的多標(biāo)記數(shù)據(jù)集[21]上，與多標(biāo)記學(xué)習(xí)的多種算法實(shí)驗(yàn)對(duì)比，其中包括ML-kNN[5]、TRAM[16]以及SMLT[19]。實(shí)驗(yàn)數(shù)據(jù)集的相關(guān)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集相關(guān)信息

實(shí)驗(yàn)選用常用的4種多標(biāo)記學(xué)習(xí)評(píng)價(jià)指標(biāo)(Hamming Loss，One-Error，Coverage，Ranking Loss)對(duì)算法性能進(jìn)行評(píng)估。這4種評(píng)價(jià)指標(biāo)的值越小，表明多標(biāo)記學(xué)習(xí)算法的分類(lèi)性能越好[22]。

實(shí)驗(yàn)抽取各數(shù)據(jù)集的90%作為訓(xùn)練樣本集(其中10%的訓(xùn)練樣本是已標(biāo)記樣本集L，90%的訓(xùn)練樣本是未標(biāo)記樣本集U)，其余10%的數(shù)據(jù)為測(cè)試樣本集T，重復(fù)10次統(tǒng)計(jì)其平均結(jié)果。由于TRAM算法屬于直推式方法，不能直接對(duì)未見(jiàn)樣本進(jìn)行預(yù)測(cè)，因而實(shí)驗(yàn)中將測(cè)試樣本T也并入TRAM訓(xùn)練時(shí)的未標(biāo)記樣本集U中。TRAM的參數(shù)k取值為10。

表2到表5列出了相關(guān)實(shí)驗(yàn)結(jié)果，加粗部分為每個(gè)指標(biāo)上的最佳性能。

表2 數(shù)據(jù)集yeast上各算法實(shí)驗(yàn)結(jié)果

續(xù)表

表3 數(shù)據(jù)集emotions上各算法實(shí)驗(yàn)結(jié)果

表4 數(shù)據(jù)集scene上各算法實(shí)驗(yàn)結(jié)果

表5 數(shù)據(jù)集enron上各算法實(shí)驗(yàn)結(jié)果

通過(guò)分析表2至表5，在以上4個(gè)數(shù)據(jù)集中，本文提出的MKSMLT算法大部分都取得了較好的分類(lèi)結(jié)果，4個(gè)評(píng)估指標(biāo)大多優(yōu)于其他同類(lèi)算法。

4.2 在文檔分類(lèi)領(lǐng)域中數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)

本文選用了2個(gè)“yahoo.com”數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)集來(lái)自于真實(shí)的網(wǎng)頁(yè)文檔。這兩個(gè)數(shù)據(jù)集分別對(duì)應(yīng)于yahoo的Business&Economy和Science兩個(gè)一級(jí)類(lèi)別，每個(gè)網(wǎng)頁(yè)再根據(jù)yahoo的二級(jí)類(lèi)別賦予標(biāo)記。由于每個(gè)網(wǎng)頁(yè)可能同時(shí)隸屬于多個(gè)二級(jí)類(lèi)別，因此，該數(shù)據(jù)集是較為典型的網(wǎng)頁(yè)文本分類(lèi)的多標(biāo)記數(shù)據(jù)集。每個(gè)數(shù)據(jù)集都包括2 000個(gè)訓(xùn)練樣本和3 000個(gè)測(cè)試樣本。

實(shí)驗(yàn)同樣采用上文所述的Hamming Loss，One-Error，Coverage，Ranking Loss 這4種常用的多標(biāo)記學(xué)習(xí)評(píng)價(jià)指標(biāo)對(duì)算法性能進(jìn)行評(píng)估。

實(shí)驗(yàn)將抽取每個(gè)數(shù)據(jù)集2 000個(gè)訓(xùn)練樣本中的10%為已標(biāo)記樣本集L，其余的90%為未標(biāo)記樣本集U，同時(shí)從3 000個(gè)測(cè)試樣本中隨機(jī)抽取300個(gè)樣本作為測(cè)試集T。實(shí)驗(yàn)中TRAM算法設(shè)置同上。

表6和表7給出了實(shí)驗(yàn)結(jié)果，加粗部分為每個(gè)指標(biāo)上的最佳性能。

表6 數(shù)據(jù)集Business&Economy上各算法實(shí)驗(yàn)結(jié)果

表7 數(shù)據(jù)集Science上各算法實(shí)驗(yàn)結(jié)果

通過(guò)分析表6和表7，在兩個(gè)數(shù)據(jù)集上，本文提出的MKSMLT算法大部分都取得了較好的分類(lèi)結(jié)果，四個(gè)評(píng)估指標(biāo)大多優(yōu)于其他同類(lèi)算法。

5 總結(jié)與展望

本文針對(duì)廣泛存在于現(xiàn)實(shí)生活中的半監(jiān)督多標(biāo)記學(xué)習(xí)問(wèn)題，綜合利用少量的已標(biāo)記樣本和大量的未標(biāo)記樣本，充分挖掘未標(biāo)記樣本的信息和價(jià)值，首先利用ML-kNN算法擴(kuò)充已標(biāo)記樣本集，以多標(biāo)記的“二階”策略為出發(fā)點(diǎn)，結(jié)合Tri-training算法訓(xùn)練得到多標(biāo)記學(xué)習(xí)分類(lèi)器，將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)化為標(biāo)記排序問(wèn)題求解，并將其應(yīng)用于文檔文類(lèi)領(lǐng)域。實(shí)驗(yàn)結(jié)果表明了本文提出算法的有效性。但是，當(dāng)多標(biāo)記學(xué)習(xí)問(wèn)題中的標(biāo)記的數(shù)量和樣本的規(guī)模較大時(shí)，如何進(jìn)一步降低算法的計(jì)算復(fù)雜度以及閾值參數(shù)th的選定仍將是需要深入討論的問(wèn)題。

[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] 常瑜, 梁吉業(yè), 高嘉偉,等. 一種基于Seeds集和成對(duì)約束的半監(jiān)督聚類(lèi)算法[J]. 南京大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012,48(4): 405-411.

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

[6] 廣凱, 潘金貴. 一種基于向量夾角的k近鄰多標(biāo)記文本分類(lèi)算法[J]. 計(jì)算機(jī)科學(xué), 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] 張敏靈. 一種新型多標(biāo)記懶惰學(xué)習(xí)算法[J]. 計(jì)算機(jī)研究與發(fā)展. 2012,49(11):2271-2282.

[10] 程圣軍, 黃慶成, 劉家鋒,等. 一種改進(jìn)的ML-kNN多標(biāo)記文檔分類(lèi)方法 [J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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] 姜遠(yuǎn),佘俏俏,黎銘,等. 一種直推式多標(biāo)記文檔分類(lèi)方法[J]. 計(jì)算機(jī)研究與發(fā)展,2008,45(11): 1817-1823.

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

[15] 孔祥南, 黎銘, 姜遠(yuǎn),等. 一種針對(duì)弱標(biāo)記的直推式多標(biāo)記分類(lèi)方法[J]. 計(jì)算機(jī)研究與發(fā)展. 2010,47(8):1392-1399.

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

[17] 李宇峰, 黃圣君, 周志華. 一種基于正則化的半監(jiān)督多標(biāo)記學(xué)習(xí)方法[J]. 計(jì)算機(jī)研究與發(fā)展. 2012,49(6): 1272-1278.

[18] 周志華,王玨. 半監(jiān)督學(xué)習(xí)中的協(xié)同訓(xùn)練算法[M]. 機(jī)器學(xué)習(xí)及其應(yīng)用.北京:清華大學(xué)出版社, 2007: 259-275.

[19] 劉楊磊, 梁吉業(yè), 高嘉偉,等. 基于Tri-training的半監(jiān)督多標(biāo)記學(xué)習(xí)算法[J]. 智能系統(tǒng)學(xué)報(bào).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—)，講師，博士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)。E?mail：gjw@sxu．edu．cn梁吉業(yè)(1962—)，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)、計(jì)算智能、數(shù)據(jù)挖掘等。E?mail：ljy@sxu．edu．cn劉楊磊(1990—)，碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)。E?mail：lyl＿super@126．com

1003-0077(2015)01-0104-07

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

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973)前期研究專(zhuān)項(xiàng)(2011CCB311805)；國(guó)家自然科學(xué)基金(61432011，61100058，61202018)；山西省科技攻關(guān)項(xiàng)目(20110321027-01)；山西省科技基礎(chǔ)條件平臺(tái)建設(shè)項(xiàng)目(2012091002-0101)

TP391

A