趙文亮，郭華平，范 明

(鄭州大學信息工程學院，鄭州 450052)

基于特征變換的Tri-Training算法

趙文亮，郭華平，范 明

(鄭州大學信息工程學院，鄭州 450052)

提出一種基于特征變換的Tri-Training算法。通過特征變換將已標記實例集映射到新空間，得到有差異的訓練集，從而構(gòu)建準確又存在差異的基分類器，避免自助采樣不能充分利用全部已標記實例集的問題。為充分利用數(shù)據(jù)類分布信息，設(shè)計基于Must-link和Cannot-link約束集合的特征變換方法(TMC)，并將其用于基于特征變換的Tri-Training算法中。在UCI數(shù)據(jù)集上的實驗結(jié)果表明，在不同未標記率下，與經(jīng)典的Co-Training、Tri-Trainng算法相比，基于特征變換的Tri-Training算法可在多數(shù)數(shù)據(jù)集上得到更高的準確率。此外，與Tri-LDA和Tri-CP算法相比，基于TMC的Tri-Training算法具有更好的泛化性能。

特征變換；已標記實例集；差異；自助抽樣；泛化能力

1 概述

在數(shù)據(jù)挖掘應(yīng)用領(lǐng)域(如Web頁面分類)，可輕易收集大量未標記的實例，但標記這些實例卻需要耗費大量的人力物力。因此，在有標記實例較少時，如何利用大量的未標記實例來改善學習性能已成為一個研究熱點。其中，半監(jiān)督學習是一種主流學習技術(shù)。目前已經(jīng)提出了很多半監(jiān)督算法，如Co-Training[1]、CoTrade[2]、SSCCM[3]等。文獻[4]提出的Tri-Training是較受關(guān)注的該類型的算法之一。與Co-Training不同，Tri-Training試圖在單個視圖上學習3個有差異的分類器，進而有效地緩解Co-Training方法對視圖正交的要求：在2個獨立的視圖上獨立學習2個強分類器。同時，基于文獻[5]的噪音理論，文獻[4]又給出了確保Tri-Training有效的條件。

Tri-Training算法成功的關(guān)鍵因素是構(gòu)建差異且準確的基分類器[6]。該算法通過對已標記實例進行重復采樣獲得差異的實例集進而獲得有差異的基分類器，而自助采樣并不能充分利用全部的已標記實例集，加之已標記實例本來就特別稀少，在特殊情況下可能導致采樣的結(jié)果為單類實例集，進而導致訓練失敗。

基于以上問題，本文提出一種基于特征變換的Tri-Training算法。與傳統(tǒng)的Tri-Training算法不同，該算法使用特征變換把訓練實例集映射到新空間，得到有差異的訓練集，從而避免了自助抽樣帶來的問題。此外，本文還設(shè)計基于Must-link和Cannot-link約束集合的特征變換方法(Transformation Based on Must-link Constrains and Cannotlink Constrains, TMC)，并將其用于基于特征變換的Tri-Training算法中。

2 相關(guān)研究

與自助采樣方法不同，特征變換方法通過處理實例集特征來構(gòu)建訓練集。這樣做的另一個原因是：基于特征變換的方法更容易構(gòu)建準確而又差異的基分類器[7]。例如，圖1給出了使用bagging[8]和COPEN[7]在實例集ionosphere上分別構(gòu)建包含50個基分類器的差異-錯誤圖，其中橫軸表示2個分類器的平均錯誤率，縱軸表示kappa度量的差異性[9]，三角形重心指示出中心點。bagging使用自助抽樣獲得有差異訓練實例集，COPEN使用約束投影(Constrain Projection)方法構(gòu)建有差異實例集。圖1顯示，基于特征變換構(gòu)建的基分類器和基于自助采樣的方法具有相近的差異性，但比基于自助采樣的方法具有更高的準確率。為此，本文提出一種TMC特征變換方法。

圖1 在ionosphere實例集上的差異-錯誤圖

文獻[10]總結(jié)存在3種常用的建立準確而又有差異的基分類器方法：(1)使用不同的基分類器；(2)使用不同的特征子集；(3)使用不同的子數(shù)據(jù)集。本文主要關(guān)注于后兩種方法，即通過操縱實例集(抽樣或特征變換)構(gòu)建準確且有差異的分類器。

對實例集進行抽樣的方法有很多種，其中，bagging和boosting方法是最典型的2個代表。bagging使用有放回隨機抽樣的方法從訓練實例集D中自助抽樣得到多個有差異的實例集D1,D2,…,DM，并在每個訓練實例集Dj上獨立訓練一個分類器hj。與bagging不同，boosting方法是一個迭代過程，每次迭代都自適應(yīng)地改變訓練實例的分布，進而使用加權(quán)抽樣方法為每個分類器hj構(gòu)建有差異的訓練實例集Dj。

特征變換方法已經(jīng)被廣泛地應(yīng)用于獲得有差異的訓練集，進而獲得不同的分類器。例如，文獻[9]將主成分分析應(yīng)用于為分類器構(gòu)建有差異的訓練實例集，進而提出一種稱作旋轉(zhuǎn)森林的組合學習方法。文獻[7]給出了一種基于成對約束的約束投影，利用must-link和cannot-link約束集合將實例集投影到新的特征空間，形成新的實例集描述，進而構(gòu)建準確且有差異的分類器。文獻[11]提出一種非陑性boosting映射方法，使用神經(jīng)網(wǎng)絡(luò)學習新特征，并將訓練集映射到不同特征空間。

還有一些方法同時使用抽樣和特征分析為每個分類器構(gòu)建有差異的訓練實例集，如隨機森林將bagging和隨機子空間結(jié)合，使用決策樹構(gòu)建有差異分類器。文獻[12]同時使用隨機抽樣、特征子空間和參數(shù)控制學習不同的最近鄰分類器。

不同于以上研究，本文將特征變換方法應(yīng)用于Tri-Training算法中，以提高Tri-Training的泛化能力。

3 本文算法

基于特征變換的Tri-Training算法描述如下：

算法基于特征變換的Tri-Training算法

其中，DL：{xi| i =1, 2, …, N}(yi∈Y是與xi相關(guān)聯(lián)的類標號)代表原始的已標記訓練實例集合；Y表示類標號集合；Du代表原始的未標記訓練實例集合。

本文算法首先使用特征變換方法初始化3個基分類器(行1～行4)：在DL上學習不同的變換矩陣Wk(行2)、應(yīng)用Wk到DL得到不同訓練集DLk，進而學習相應(yīng)的分類器hk。然后Tri-Training迭代地更新這3個分類器直到更新不再發(fā)生(行6～行24)。對于每次迭代，Tri-Training首先為每個分類器hk標記新的實例(行11)，并根據(jù)如下條件確定是否更新hk(行12～行17)[4]：

在上述算法中，et(hk)表示第t次迭代其他2個分類器(除hk外)同時錯誤預測DL中實例的比例，|Dkt|是表示第t次迭代為分類器hk標記的實例數(shù)，即其他2個分類器(除hk)在Du上預測相同的實例數(shù)。為了防止|Dkt|過大，使用欠抽樣方法減少Dkt中的實例(行15～行17)。最后，Tri-Training迭代更新每個分類器(行19～行23)。注意：算法中變量flagk(行4、行9和行22)目的是標記分類器hk是否已經(jīng)被更新過，若未更新過則需將Du轉(zhuǎn)換到新空間以便hk能夠進行預測，否則直接使用hk預測Du中的實例。

如本文第2節(jié)所述，特征變換方法已經(jīng)得到了廣泛的研究，本文將這些變換引入到Tri-Training中。另外，本文構(gòu)建一種新的基于Must-link和Cannot-link約束集合的特征變換(TMC)。該方法描述如下：給定已標記實例集DL，令Must-link約束集合Φm={(xi,xj)|xi∈DL,xj∈DL,yi=yj}和Cannotlink約束集合Φc={(xi,xj)|xi∈DL,xj∈DL,yi≠yj}，筆者的目標是尋找一個變換矩陣W，使得在變換后的低維空間中(實例表示為zi=WTxi)，類內(nèi)實例距離盡量小而類間實例距離盡量大。搜索變換矩陣W，使得最大化目標函數(shù)J(W)且WWT=WTW=I，其中，I為單位矩陣。

經(jīng)過簡單的代數(shù)運算，式(2)可用以下更簡潔的方式來描述：

其中，trace(·)表示矩陣的跡；C和M分別表示Φc和Φm的散度矩陣(見式(4))，定義如下：

這里C和M分別相應(yīng)于陑性判別分析(Linear Discriminant Analysis, LDA)[10]類間散度矩陣和類內(nèi)散度矩陣。與LDA不同，本文采用成對實例約束構(gòu)建散度矩陣。與約束投影不同，本文的目標函數(shù)無額外參數(shù)，這使得本文的變換方法更簡單、簡便。另外，最大化式(2)相當于最小化分母而最大化分子，進而使用式(2)求得的變換矩陣W能夠使得在變換后的低維空間中，類內(nèi)的實例距離盡量小而類間實例距離盡量大。

式(5)是一個典型的特征值問題，可以通過計算矩陣CM–1前d個最大的特征值對應(yīng)的特征向量高效的解決。假定W=[W1, W2,…, Wd]作為式(5)的解決方案，矩陣中每一個特征向量對應(yīng)的特征值為λ1≥λ2≥…≥λd，定義對角矩陣∧=diag(λ1, λ2, …, λd)，那么：

注意：存在式(6)中的一個問題是M的行列式為0。事實上，由于C和M都是半正定的，M的行列式為0的情況很難出現(xiàn)，因此不那么嚴格地說，CM–1也是半正定的。為了支持算法1構(gòu)建不同的變換矩陣，使用隨機采樣構(gòu)建Φm和Φc使得|Φm|=|Φc|=|DL|，其中，|Q|表示集合Q的大小，DL表示已標記實例集(參見本文第3節(jié)算法)。

4 實驗與結(jié)果分析

4.1 實驗設(shè)置

12個實例集從UCI(http://archive.ics.uci.edu/ml/)庫中隨機選取。由于篇幅限制，本文省去了它們的信息描述。在每個數(shù)據(jù)集上，使用10折交叉驗證分析算法的性能。為了評估基于特征變換的Tri-Training有效性，將它與Co-Training[1]和基于自助采樣的Tri-Training[4]相比較，其中，將如下特征變換引入到Tri-Training中：TM，LDA和CP (Constraint Projections)。對應(yīng)的算法分別記作Tri-TMC、Tri-LDA和Tri-CP。所有基分類器都使用C4.5[13]構(gòu)建。對于Tri-TMC和Tri-CP，使用隨機抽樣構(gòu)建Φm和Φc，使得它們的大小與已標記實例數(shù)相同。Tri-LDA使用隨機抽樣獲得的已標記實例集構(gòu)建類間和類內(nèi)散度矩陣。

本文設(shè)計4個實驗評估本文算法的有效性，其中，前3個實驗測試給定未標號實例比例時算法的性能(未標記比率分別設(shè)置為訓練實例的80%、60%和40%)，最后一個實驗測試了不同的未標記實例比率對算法性能的影響。所有的實驗均使用開源數(shù)據(jù)挖掘工具洛陽鏟(LySpoon)[14]完成。

4.2 實驗結(jié)果

實驗1測試了未標記率為80%時本文算法的性能。相關(guān)結(jié)果如表1所示，其中粗體表示相應(yīng)的算法在相應(yīng)的數(shù)據(jù)集上準確率最高，最后一行給出了平均準確率。可以看出，由于使用特征變換的方法更易構(gòu)建準確且差異的基分類器，基于變換的Tri-Training算法比基于抽樣方法構(gòu)建的Tri-Training算法表現(xiàn)出更好的泛化性能。Tri-TMC和Tri-LDA在絕大多數(shù)數(shù)據(jù)集上取得了最高的準確率，其他依次是Co-Training、Tri-CP和Tri-Training。同時Tri-TMC以77.95%的平均準確率最高，隨后依次是Tri-LDA、Tri-CP、Tri-Training和Co-Training。

表1 UCI數(shù)據(jù)集80%%%%未標記率下對應(yīng)的準確率及序

在多個數(shù)據(jù)集上比較2個或更多算法的一個合適的方法是根據(jù)他們在數(shù)據(jù)集上的序及平均序[15]：獲得最高準確率的算法的序是1.0，獲得次高準確率的算法的序是2.0，依次類推。當多個算法準確率一樣時，它們獲得一個平均序。表1的右半部分給出了算法在每個數(shù)據(jù)集合上的序。

表1中算法的序驗證了本文結(jié)論：基于特征變換的Tri-Training算法比基于抽樣方法構(gòu)建Tri-Training的方法表現(xiàn)出更好的泛化性能?？梢钥闯?，Tri-LDA以2.33的平均序排名第一，緊隨其后的依次是Tri-TMC、Tri-Training、Tri-CP 和Co-Training。

仔細觀察表1關(guān)于準確率和序的結(jié)果可以發(fā)現(xiàn)，較之于其他特征變換，TMC同樣對Tri-Training是有效的。因此，在未標記率為80%時，本文總結(jié)如下：(1)基于變換的Tri-Training算法較之于基于自助采樣的Tri-Training算法具有更好的泛化能力；(2)較之于其他特征變化方法，TMC方法同樣對Tri-Training算法有效；(3)在UCI數(shù)據(jù)集上，與Co-Training算法相比較，Tri-Training更優(yōu)越。

實驗2和實驗3分別展示了當未標記類標號比例為60%和40%時，算法準確率和序的比較結(jié)果，相關(guān)結(jié)果如表2和表3所示，其中設(shè)置同表1。

表2和表中的結(jié)果進一步驗證了本文結(jié)論：使用特征變換方法更容易構(gòu)建準確且差異的基分類器，進而有效提升Tri-Training算法性能。具體地，當未標號實例比例為60%時，Tri-TMC在7個數(shù)據(jù)集上取得最高的準確率，其他依次是Tri-CP、Tri-Training、Tri-LDA和Co-Training。在平均準確率上，Tri-TMC以79.82%排名第一，緊隨其后的依次是Tri-CP、Tri-LDA、Tri-Training和Co-Training。在序比較上，它們的排名依次是Tri-TMC、Tri-LDA、Tri-CP、Tri-Training和Co-Training。當未標號實例比例為40%時，平均準確率依次是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%%%%未標記率下對應(yīng)的準確率及序

表3 UCI數(shù)據(jù)集40%%%%未標記率下對應(yīng)的準確率及序

實驗4測試了不同算法在不同的未標記率下的準確率，選取letter和sonar作為代表測試未標記率對算法性能的影響，結(jié)果如圖2所示?？梢钥闯?，隨著未標記實例的比例升高，較之于基于抽樣的Tri-Training算法，基于變換的Tri-Training算法性能優(yōu)勢越來越明顯。另外，3種特征變換方法對Tri-Training的效果是相當?shù)摹?/p>

圖2 算法準確率的變化趨勢

根據(jù)以上結(jié)果，總結(jié)得到以下結(jié)論：(1)基于特征變換的Tri-Training算法具有更好的泛化能力；(2)與基于LDA 和CP一樣，基于TMC對Tri-Training同樣可取得較好的效果；(3)隨著未標記率的升高，基于特征變換的Tri-Training算法性能優(yōu)勢越來越明顯。

5 結(jié)束語

本文將特征變換方法應(yīng)用到Tri-Training中。較之于傳統(tǒng)Tri-Training算法，利用該方法構(gòu)建的基分類器在保持相當?shù)牟町愋酝瑫r具有更高的分類器準確率，進而可有效地提高Tri-Training的泛化能力。此外，本文提出了基于Mustlink和Cannot-link約束集合的特征變換方法(TMC)。實驗結(jié)果表明，較之于隨機抽樣，特征變換能更有效用于Tri-Training算法中；較之于其他變換，本文提出的TMC方法同樣是有效的。TMC方法可以很容易地擴展到其他Co-Training類型算法，因此，下一步的研究工作是將特征變換應(yīng)用到其他協(xié)同學習方法中，同時對TMC方法進行深入的理論分析，將其用于其他領(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ù)挖掘，機器學習；郭華平，博士研究生；范 明，教授。

2013-04-22

2013-08-07E-mail：wlzhao.gm@gmail.com

1000-3428(2014)05-0183-05

A

TP18