趙文亮,郭華平,范 明
(鄭州大學(xué)信息工程學(xué)院,鄭州 450052)
基于特征變換的Tri-Training算法
趙文亮,郭華平,范 明
(鄭州大學(xué)信息工程學(xué)院,鄭州 450052)
提出一種基于特征變換的Tri-Training算法。通過(guò)特征變換將已標(biāo)記實(shí)例集映射到新空間,得到有差異的訓(xùn)練集,從而構(gòu)建準(zhǔn)確又存在差異的基分類器,避免自助采樣不能充分利用全部已標(biāo)記實(shí)例集的問(wèn)題。為充分利用數(shù)據(jù)類分布信息,設(shè)計(jì)基于Must-link和Cannot-link約束集合的特征變換方法(TMC),并將其用于基于特征變換的Tri-Training算法中。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,在不同未標(biāo)記率下,與經(jīng)典的Co-Training、Tri-Trainng算法相比,基于特征變換的Tri-Training算法可在多數(shù)數(shù)據(jù)集上得到更高的準(zhǔn)確率。此外,與Tri-LDA和Tri-CP算法相比,基于TMC的Tri-Training算法具有更好的泛化性能。
特征變換;已標(biāo)記實(shí)例集;差異;自助抽樣;泛化能力
在數(shù)據(jù)挖掘應(yīng)用領(lǐng)域(如Web頁(yè)面分類),可輕易收集大量未標(biāo)記的實(shí)例,但標(biāo)記這些實(shí)例卻需要耗費(fèi)大量的人力物力。因此,在有標(biāo)記實(shí)例較少時(shí),如何利用大量的未標(biāo)記實(shí)例來(lái)改善學(xué)習(xí)性能已成為一個(gè)研究熱點(diǎn)。其中,半監(jiān)督學(xué)習(xí)是一種主流學(xué)習(xí)技術(shù)。目前已經(jīng)提出了很多半監(jiān)督算法,如Co-Training[1]、CoTrade[2]、SSCCM[3]等。文獻(xiàn)[4]提出的Tri-Training是較受關(guān)注的該類型的算法之一。與Co-Training不同,Tri-Training試圖在單個(gè)視圖上學(xué)習(xí)3個(gè)有差異的分類器,進(jìn)而有效地緩解Co-Training方法對(duì)視圖正交的要求:在2個(gè)獨(dú)立的視圖上獨(dú)立學(xué)習(xí)2個(gè)強(qiáng)分類器。同時(shí),基于文獻(xiàn)[5]的噪音理論,文獻(xiàn)[4]又給出了確保Tri-Training有效的條件。
Tri-Training算法成功的關(guān)鍵因素是構(gòu)建差異且準(zhǔn)確的基分類器[6]。該算法通過(guò)對(duì)已標(biāo)記實(shí)例進(jìn)行重復(fù)采樣獲得差異的實(shí)例集進(jìn)而獲得有差異的基分類器,而自助采樣并不能充分利用全部的已標(biāo)記實(shí)例集,加之已標(biāo)記實(shí)例本來(lái)就特別稀少,在特殊情況下可能導(dǎo)致采樣的結(jié)果為單類實(shí)例集,進(jìn)而導(dǎo)致訓(xùn)練失敗。
基于以上問(wèn)題,本文提出一種基于特征變換的Tri-Training算法。與傳統(tǒng)的Tri-Training算法不同,該算法使用特征變換把訓(xùn)練實(shí)例集映射到新空間,得到有差異的訓(xùn)練集,從而避免了自助抽樣帶來(lái)的問(wèn)題。此外,本文還設(shè)計(jì)基于Must-link和Cannot-link約束集合的特征變換方法(Transformation Based on Must-link Constrains and Cannotlink Constrains, TMC),并將其用于基于特征變換的Tri-Training算法中。
與自助采樣方法不同,特征變換方法通過(guò)處理實(shí)例集特征來(lái)構(gòu)建訓(xùn)練集。這樣做的另一個(gè)原因是:基于特征變換的方法更容易構(gòu)建準(zhǔn)確而又差異的基分類器[7]。例如,圖1給出了使用bagging[8]和COPEN[7]在實(shí)例集ionosphere上分別構(gòu)建包含50個(gè)基分類器的差異-錯(cuò)誤圖,其中橫軸表示2個(gè)分類器的平均錯(cuò)誤率,縱軸表示kappa度量的差異性[9],三角形重心指示出中心點(diǎn)。bagging使用自助抽樣獲得有差異訓(xùn)練實(shí)例集,COPEN使用約束投影(Constrain Projection)方法構(gòu)建有差異實(shí)例集。圖1顯示,基于特征變換構(gòu)建的基分類器和基于自助采樣的方法具有相近的差異性,但比基于自助采樣的方法具有更高的準(zhǔn)確率。為此,本文提出一種TMC特征變換方法。
圖1 在ionosphere實(shí)例集上的差異-錯(cuò)誤圖
文獻(xiàn)[10]總結(jié)存在3種常用的建立準(zhǔn)確而又有差異的基分類器方法:(1)使用不同的基分類器;(2)使用不同的特征子集;(3)使用不同的子數(shù)據(jù)集。本文主要關(guān)注于后兩種方法,即通過(guò)操縱實(shí)例集(抽樣或特征變換)構(gòu)建準(zhǔn)確且有差異的分類器。
對(duì)實(shí)例集進(jìn)行抽樣的方法有很多種,其中,bagging和boosting方法是最典型的2個(gè)代表。bagging使用有放回隨機(jī)抽樣的方法從訓(xùn)練實(shí)例集D中自助抽樣得到多個(gè)有差異的實(shí)例集D1,D2,…,DM,并在每個(gè)訓(xùn)練實(shí)例集Dj上獨(dú)立訓(xùn)練一個(gè)分類器hj。與bagging不同,boosting方法是一個(gè)迭代過(guò)程,每次迭代都自適應(yīng)地改變訓(xùn)練實(shí)例的分布,進(jìn)而使用加權(quán)抽樣方法為每個(gè)分類器hj構(gòu)建有差異的訓(xùn)練實(shí)例集Dj。
特征變換方法已經(jīng)被廣泛地應(yīng)用于獲得有差異的訓(xùn)練集,進(jìn)而獲得不同的分類器。例如,文獻(xiàn)[9]將主成分分析應(yīng)用于為分類器構(gòu)建有差異的訓(xùn)練實(shí)例集,進(jìn)而提出一種稱作旋轉(zhuǎn)森林的組合學(xué)習(xí)方法。文獻(xiàn)[7]給出了一種基于成對(duì)約束的約束投影,利用must-link和cannot-link約束集合將實(shí)例集投影到新的特征空間,形成新的實(shí)例集描述,進(jìn)而構(gòu)建準(zhǔn)確且有差異的分類器。文獻(xiàn)[11]提出一種非陑性boosting映射方法,使用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)新特征,并將訓(xùn)練集映射到不同特征空間。
還有一些方法同時(shí)使用抽樣和特征分析為每個(gè)分類器構(gòu)建有差異的訓(xùn)練實(shí)例集,如隨機(jī)森林將bagging和隨機(jī)子空間結(jié)合,使用決策樹(shù)構(gòu)建有差異分類器。文獻(xiàn)[12]同時(shí)使用隨機(jī)抽樣、特征子空間和參數(shù)控制學(xué)習(xí)不同的最近鄰分類器。
不同于以上研究,本文將特征變換方法應(yīng)用于Tri-Training算法中,以提高Tri-Training的泛化能力。
基于特征變換的Tri-Training算法描述如下:
算法基于特征變換的Tri-Training算法
其中,DL:{xi| i =1, 2, …, N}(yi∈Y是與xi相關(guān)聯(lián)的類標(biāo)號(hào))代表原始的已標(biāo)記訓(xùn)練實(shí)例集合;Y表示類標(biāo)號(hào)集合;Du代表原始的未標(biāo)記訓(xùn)練實(shí)例集合。
本文算法首先使用特征變換方法初始化3個(gè)基分類器(行1~行4):在DL上學(xué)習(xí)不同的變換矩陣Wk(行2)、應(yīng)用Wk到DL得到不同訓(xùn)練集DLk,進(jìn)而學(xué)習(xí)相應(yīng)的分類器hk。然后Tri-Training迭代地更新這3個(gè)分類器直到更新不再發(fā)生(行6~行24)。對(duì)于每次迭代,Tri-Training首先為每個(gè)分類器hk標(biāo)記新的實(shí)例(行11),并根據(jù)如下條件確定是否更新hk(行12~行17)[4]:
在上述算法中,et(hk)表示第t次迭代其他2個(gè)分類器(除hk外)同時(shí)錯(cuò)誤預(yù)測(cè)DL中實(shí)例的比例,|Dkt|是表示第t次迭代為分類器hk標(biāo)記的實(shí)例數(shù),即其他2個(gè)分類器(除hk)在Du上預(yù)測(cè)相同的實(shí)例數(shù)。為了防止|Dkt|過(guò)大,使用欠抽樣方法減少Dkt中的實(shí)例(行15~行17)。最后,Tri-Training迭代更新每個(gè)分類器(行19~行23)。注意:算法中變量flagk(行4、行9和行22)目的是標(biāo)記分類器hk是否已經(jīng)被更新過(guò),若未更新過(guò)則需將Du轉(zhuǎn)換到新空間以便hk能夠進(jìn)行預(yù)測(cè),否則直接使用hk預(yù)測(cè)Du中的實(shí)例。
如本文第2節(jié)所述,特征變換方法已經(jīng)得到了廣泛的研究,本文將這些變換引入到Tri-Training中。另外,本文構(gòu)建一種新的基于Must-link和Cannot-link約束集合的特征變換(TMC)。該方法描述如下:給定已標(biāo)記實(shí)例集DL,令Must-link約束集合Φm={(xi,xj)|xi∈DL,xj∈DL,yi=yj}和Cannotlink約束集合Φc={(xi,xj)|xi∈DL,xj∈DL,yi≠yj},筆者的目標(biāo)是尋找一個(gè)變換矩陣W,使得在變換后的低維空間中(實(shí)例表示為zi=WTxi),類內(nèi)實(shí)例距離盡量小而類間實(shí)例距離盡量大。搜索變換矩陣W,使得最大化目標(biāo)函數(shù)J(W)且WWT=WTW=I,其中,I為單位矩陣。
經(jīng)過(guò)簡(jiǎn)單的代數(shù)運(yùn)算,式(2)可用以下更簡(jiǎn)潔的方式來(lái)描述:
其中,trace(·)表示矩陣的跡;C和M分別表示Φc和Φm的散度矩陣(見(jiàn)式(4)),定義如下:
這里C和M分別相應(yīng)于陑性判別分析(Linear Discriminant Analysis, LDA)[10]類間散度矩陣和類內(nèi)散度矩陣。與LDA不同,本文采用成對(duì)實(shí)例約束構(gòu)建散度矩陣。與約束投影不同,本文的目標(biāo)函數(shù)無(wú)額外參數(shù),這使得本文的變換方法更簡(jiǎn)單、簡(jiǎn)便。另外,最大化式(2)相當(dāng)于最小化分母而最大化分子,進(jìn)而使用式(2)求得的變換矩陣W能夠使得在變換后的低維空間中,類內(nèi)的實(shí)例距離盡量小而類間實(shí)例距離盡量大。
式(5)是一個(gè)典型的特征值問(wèn)題,可以通過(guò)計(jì)算矩陣CM–1前d個(gè)最大的特征值對(duì)應(yīng)的特征向量高效的解決。假定W=[W1, W2,…, Wd]作為式(5)的解決方案,矩陣中每一個(gè)特征向量對(duì)應(yīng)的特征值為λ1≥λ2≥…≥λd,定義對(duì)角矩陣∧=diag(λ1, λ2, …, λd),那么:
注意:存在式(6)中的一個(gè)問(wèn)題是M的行列式為0。事實(shí)上,由于C和M都是半正定的,M的行列式為0的情況很難出現(xiàn),因此不那么嚴(yán)格地說(shuō),CM–1也是半正定的。為了支持算法1構(gòu)建不同的變換矩陣,使用隨機(jī)采樣構(gòu)建Φm和Φc使得|Φm|=|Φc|=|DL|,其中,|Q|表示集合Q的大小,DL表示已標(biāo)記實(shí)例集(參見(jiàn)本文第3節(jié)算法)。
4.1 實(shí)驗(yàn)設(shè)置
12個(gè)實(shí)例集從UCI(http://archive.ics.uci.edu/ml/)庫(kù)中隨機(jī)選取。由于篇幅限制,本文省去了它們的信息描述。在每個(gè)數(shù)據(jù)集上,使用10折交叉驗(yàn)證分析算法的性能。為了評(píng)估基于特征變換的Tri-Training有效性,將它與Co-Training[1]和基于自助采樣的Tri-Training[4]相比較,其中,將如下特征變換引入到Tri-Training中:TM,LDA和CP (Constraint Projections)。對(duì)應(yīng)的算法分別記作Tri-TMC、Tri-LDA和Tri-CP。所有基分類器都使用C4.5[13]構(gòu)建。對(duì)于Tri-TMC和Tri-CP,使用隨機(jī)抽樣構(gòu)建Φm和Φc,使得它們的大小與已標(biāo)記實(shí)例數(shù)相同。Tri-LDA使用隨機(jī)抽樣獲得的已標(biāo)記實(shí)例集構(gòu)建類間和類內(nèi)散度矩陣。
本文設(shè)計(jì)4個(gè)實(shí)驗(yàn)評(píng)估本文算法的有效性,其中,前3個(gè)實(shí)驗(yàn)測(cè)試給定未標(biāo)號(hào)實(shí)例比例時(shí)算法的性能(未標(biāo)記比率分別設(shè)置為訓(xùn)練實(shí)例的80%、60%和40%),最后一個(gè)實(shí)驗(yàn)測(cè)試了不同的未標(biāo)記實(shí)例比率對(duì)算法性能的影響。所有的實(shí)驗(yàn)均使用開(kāi)源數(shù)據(jù)挖掘工具洛陽(yáng)鏟(LySpoon)[14]完成。
4.2 實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)1測(cè)試了未標(biāo)記率為80%時(shí)本文算法的性能。相關(guān)結(jié)果如表1所示,其中粗體表示相應(yīng)的算法在相應(yīng)的數(shù)據(jù)集上準(zhǔn)確率最高,最后一行給出了平均準(zhǔn)確率??梢钥闯?,由于使用特征變換的方法更易構(gòu)建準(zhǔn)確且差異的基分類器,基于變換的Tri-Training算法比基于抽樣方法構(gòu)建的Tri-Training算法表現(xiàn)出更好的泛化性能。Tri-TMC和Tri-LDA在絕大多數(shù)數(shù)據(jù)集上取得了最高的準(zhǔn)確率,其他依次是Co-Training、Tri-CP和Tri-Training。同時(shí)Tri-TMC以77.95%的平均準(zhǔn)確率最高,隨后依次是Tri-LDA、Tri-CP、Tri-Training和Co-Training。
表1 UCI數(shù)據(jù)集80%%%%未標(biāo)記率下對(duì)應(yīng)的準(zhǔn)確率及序
在多個(gè)數(shù)據(jù)集上比較2個(gè)或更多算法的一個(gè)合適的方法是根據(jù)他們?cè)跀?shù)據(jù)集上的序及平均序[15]:獲得最高準(zhǔn)確率的算法的序是1.0,獲得次高準(zhǔn)確率的算法的序是2.0,依次類推。當(dāng)多個(gè)算法準(zhǔn)確率一樣時(shí),它們獲得一個(gè)平均序。表1的右半部分給出了算法在每個(gè)數(shù)據(jù)集合上的序。
表1中算法的序驗(yàn)證了本文結(jié)論:基于特征變換的Tri-Training算法比基于抽樣方法構(gòu)建Tri-Training的方法表現(xiàn)出更好的泛化性能??梢钥闯?,Tri-LDA以2.33的平均序排名第一,緊隨其后的依次是Tri-TMC、Tri-Training、Tri-CP 和Co-Training。
仔細(xì)觀察表1關(guān)于準(zhǔn)確率和序的結(jié)果可以發(fā)現(xiàn),較之于其他特征變換,TMC同樣對(duì)Tri-Training是有效的。因此,在未標(biāo)記率為80%時(shí),本文總結(jié)如下:(1)基于變換的Tri-Training算法較之于基于自助采樣的Tri-Training算法具有更好的泛化能力;(2)較之于其他特征變化方法,TMC方法同樣對(duì)Tri-Training算法有效;(3)在UCI數(shù)據(jù)集上,與Co-Training算法相比較,Tri-Training更優(yōu)越。
實(shí)驗(yàn)2和實(shí)驗(yàn)3分別展示了當(dāng)未標(biāo)記類標(biāo)號(hào)比例為60%和40%時(shí),算法準(zhǔn)確率和序的比較結(jié)果,相關(guān)結(jié)果如表2和表3所示,其中設(shè)置同表1。
表2和表中的結(jié)果進(jìn)一步驗(yàn)證了本文結(jié)論:使用特征變換方法更容易構(gòu)建準(zhǔn)確且差異的基分類器,進(jìn)而有效提升Tri-Training算法性能。具體地,當(dāng)未標(biāo)號(hào)實(shí)例比例為60%時(shí),Tri-TMC在7個(gè)數(shù)據(jù)集上取得最高的準(zhǔn)確率,其他依次是Tri-CP、Tri-Training、Tri-LDA和Co-Training。在平均準(zhǔn)確率上,Tri-TMC以79.82%排名第一,緊隨其后的依次是Tri-CP、Tri-LDA、Tri-Training和Co-Training。在序比較上,它們的排名依次是Tri-TMC、Tri-LDA、Tri-CP、Tri-Training和Co-Training。當(dāng)未標(biāo)號(hào)實(shí)例比例為40%時(shí),平均準(zhǔn)確率依次是Tri-CP、Tri-TMC、Tri- Training、Tri-LDA和Co-Training。平均序排名依次是Tri-TMC、Tri-CP、Tri-LDA、Tri-Training和Co-Training。
表2 UCI數(shù)據(jù)集60%%%%未標(biāo)記率下對(duì)應(yīng)的準(zhǔn)確率及序
表3 UCI數(shù)據(jù)集40%%%%未標(biāo)記率下對(duì)應(yīng)的準(zhǔn)確率及序
實(shí)驗(yàn)4測(cè)試了不同算法在不同的未標(biāo)記率下的準(zhǔn)確率,選取letter和sonar作為代表測(cè)試未標(biāo)記率對(duì)算法性能的影響,結(jié)果如圖2所示。可以看出,隨著未標(biāo)記實(shí)例的比例升高,較之于基于抽樣的Tri-Training算法,基于變換的Tri-Training算法性能優(yōu)勢(shì)越來(lái)越明顯。另外,3種特征變換方法對(duì)Tri-Training的效果是相當(dāng)?shù)摹?/p>
圖2 算法準(zhǔn)確率的變化趨勢(shì)
根據(jù)以上結(jié)果,總結(jié)得到以下結(jié)論:(1)基于特征變換的Tri-Training算法具有更好的泛化能力;(2)與基于LDA 和CP一樣,基于TMC對(duì)Tri-Training同樣可取得較好的效果;(3)隨著未標(biāo)記率的升高,基于特征變換的Tri-Training算法性能優(yōu)勢(shì)越來(lái)越明顯。
本文將特征變換方法應(yīng)用到Tri-Training中。較之于傳統(tǒng)Tri-Training算法,利用該方法構(gòu)建的基分類器在保持相當(dāng)?shù)牟町愋酝瑫r(shí)具有更高的分類器準(zhǔn)確率,進(jìn)而可有效地提高Tri-Training的泛化能力。此外,本文提出了基于Mustlink和Cannot-link約束集合的特征變換方法(TMC)。實(shí)驗(yàn)結(jié)果表明,較之于隨機(jī)抽樣,特征變換能更有效用于Tri-Training算法中;較之于其他變換,本文提出的TMC方法同樣是有效的。TMC方法可以很容易地?cái)U(kuò)展到其他Co-Training類型算法,因此,下一步的研究工作是將特征變換應(yīng)用到其他協(xié)同學(xué)習(xí)方法中,同時(shí)對(duì)TMC方法進(jìn)行深入的理論分析,將其用于其他領(lǐng)域。
[1] Blum A, Mitchell T. Combining Labeled and Unlabeled Data with Co-training[C]//Proc. of the 11th Annual Conference on Computational Learning Theory. Madison, USA: [s. n.], 1998: 92-100.
[2] Zhang Minling, Zhou Zhihua. CoTrade: Confident Co-training with Data Editing[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2011, 41(6): 1612-1626.
[3] Wang Yunyun, Chen Songcan, Zhou Zhihua. New Semisupervised Classification Method Based on Modified Cluster Assumption[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(5): 689-702.
[4] Zhou Zhih ua, Li Ming. Tri-training: Explo iting Unlabeled Data Using Three Classifier s[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11): 1529-1541.
[5] Angluin D, Laird P. Learning from Noisy Examples[J]. Machine Learning, 1988, 2(4): 343-370.
[6] W ang Wei, Zh ou Zhihua. Analyzing Co-tr aining S tyle Algorithms[C]//Proc. of the 18th Europea n Conference on Machine Learning. Warsaw, Poland: [s. n.], 2007: 454-465.
[7] Zhang Da oqiang, Chen Songcan, Zhou Zhih ua, et al. Constraint Proj ections for Ensemble Learning[C]//Proc. of the 23rd AAAI Conference on A rtificial Intelligence. C hicago, USA: AAAI Press, 2008: 758-763.
[8] Breiman L. Bag ging Predictors[J]. Machine Learning, 1996, 24(2): 123-140.
[9] Rodriguez J J, Kuncheva L I, Alonso C J. Rotation Forest: A New Classifier Ensemble Metho d[J]. IEEE Transactions on Pattern A nalysis and M achine I ntelligence, 2006, 28(10): 1619-1630.
[10] Kuncheva L. Combining P attern Classifiers: Methods and Algorithms[M]. [S. l.]: John Wiley and Sons, 2004.
[11] García-Pedrajas N, G arcía-Osorio C, Fyfe C. N onlinear Boosting Projections for Ensemble Construction[J]. Journal of Machine Learning Research, 2007, 8: 1-33.
[12] Zhou Zhihu a, Yu Yang. Ensembling Local L earners Through Multimodal Perturbation[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2005, 35(4): 725-735.
[13] Quinlan J R. C4.5: Progra ms for Machine Learning[M]. New York, USA: Morgan-Kaufmann, 1993.
[14] 郭華平. LySpoon[EB/OL]. (2012-10-10). http://nlp.zzu.edu.cn/ LySpoon.asp.
[15] Demsar J. Statistical Comparisons of Classifiers over Multiple Data Sets[J]. Journal of M achine Le arning Research, 2006, 7(1): 1-30.
編輯 金胡考
Tri-Training Algorithm Based on Feature Transformation
ZHAO Wen-liang, GUO Hua-ping, FAN Ming
(School of Information Engineering, Zhengzhou University, Zhengzhou 450052, China)
This paper proposes a new Tri-Training algorithm based on feature transformation. It employs feature transformation to transform labeled instances into new space to obtain new training sets, and constructs accurate and diverse classifiers. In this way, it avoids the weakness of bootstrap sampling which only adopts training data samples to train base classifiers. In order to make full use of the data distribution information, this paper introduces a new transformation method called Transformation Based on Must-link Constrains and Cannot-link Constrains(TMC), and uses it to this new Tri-Training algorithm. Experimental results on UCI data sets show that, in different unlabeled rate, compared with the classic Co-Training and Tri-Training algorithm, the proposed algorithm based on feature transformation gets the highest accuracy in most data sets. In addition, compared with the Tri-LDA and Tri-CP algorithm, the Tri-Training algorithm based on TMC has better generalization ability.
feature transformation; labeled instances set; difference; bootstrap sampling; generalization ability
10.3969/j.issn.1000----3428.2014.05.038
趙文亮(1989-),男,碩士研究生,主研方向:數(shù)據(jù)挖掘,機(jī)器學(xué)習(xí);郭華平,博士研究生;范 明,教授。
2013-04-22
2013-08-07E-mail:wlzhao.gm@gmail.com
1000-3428(2014)05-0183-05
A
TP18