一種基于交叉驗(yàn)證思想的半監(jiān)督分類方法

趙建華

(1.西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 陜西西安 710072;2.商洛學(xué)院計(jì)算機(jī)科學(xué)系 陜西商洛 726000)

機(jī)器學(xué)習(xí)作為人工智能一個(gè)重要研究方向，一直受到計(jì)算機(jī)科學(xué)家的關(guān)注。當(dāng)前，機(jī)器學(xué)習(xí)面臨的現(xiàn)實(shí)情況是:未標(biāo)記樣本數(shù)目眾多，易于獲得;標(biāo)記樣本數(shù)據(jù)稀少，難于獲得。這種現(xiàn)象使傳統(tǒng)的機(jī)器學(xué)習(xí)算法無法得以有效應(yīng)用，原因在于監(jiān)督學(xué)習(xí)需要大量標(biāo)記樣本對分類器進(jìn)行迭代訓(xùn)練。在這種情況下，半監(jiān)督學(xué)習(xí)(Semi－Supervised Learning)和主動(dòng)學(xué)習(xí)(Active Learning)應(yīng)運(yùn)而生并迅速發(fā)展，成為解決上述問題的重要技術(shù)［1］。

半監(jiān)督分類［2－3］利用大量無標(biāo)記數(shù)據(jù)擴(kuò)大分類算法的訓(xùn)練集，主要研究從有監(jiān)督學(xué)習(xí)的角度出發(fā)，當(dāng)已標(biāo)記訓(xùn)練樣本不足時(shí)，如何自動(dòng)利用大量未標(biāo)記樣本信息輔助分類器的訓(xùn)練。根據(jù)每個(gè)樣本標(biāo)記數(shù)目的不同，半監(jiān)督分類可以分為單標(biāo)記分類和多標(biāo)記分類。對于單標(biāo)記分類問題，也就是傳統(tǒng)的半監(jiān)督分類，目前常見的分類方法很多，包括基于EM算法的生成式模型參數(shù)估計(jì)法［4］、協(xié)同訓(xùn)練方法［5－7］、基于支持向量機(jī)的半監(jiān)督分類方法［8－9］、基于流形的半監(jiān)督分類方法［10］等;對于半監(jiān)督多標(biāo)記分類問題，目前出現(xiàn)的方法包括直推式多標(biāo)記分類［11］和基于正則化的半監(jiān)督多標(biāo)記分類［12］等。

泛化誤差(Generalization)是統(tǒng)計(jì)機(jī)器學(xué)習(xí)模型的重要評價(jià)指標(biāo)，在統(tǒng)計(jì)中，泛化誤差通常使用交叉驗(yàn)證方法來估計(jì)，所以，交叉驗(yàn)證方法廣泛地應(yīng)用到模型選擇領(lǐng)域，實(shí)現(xiàn)對模型泛化誤差的估計(jì)和選擇［13－14］。有一些研究者或?qū)徊骝?yàn)證進(jìn)行改進(jìn)，或?qū)⑵鋺?yīng)用到分類領(lǐng)域，取得了較好的效果。文獻(xiàn)［15］提出一種極限學(xué)習(xí)機(jī)的快速留一交叉驗(yàn)證方法，文獻(xiàn)［16］提出了一種改進(jìn)的交叉驗(yàn)證容噪分類算法，文獻(xiàn)［17］將交叉驗(yàn)證容噪分類算法應(yīng)用到數(shù)據(jù)流分類領(lǐng)域，都取得了較好的效果。

通過對國內(nèi)外大量文獻(xiàn)的查閱，就作者掌握的文獻(xiàn)來看，目前還沒有研究者將交叉驗(yàn)證思想應(yīng)用到半監(jiān)督分類領(lǐng)域，實(shí)現(xiàn)對未標(biāo)記樣本的標(biāo)記。

本文將交叉驗(yàn)證思想引入到半監(jiān)督分類領(lǐng)域，提出一種基于交叉驗(yàn)證思想的半監(jiān)督分類算法(Cross Validation Semi－Supervised Support Vector Machine，CV－S3VM)，提高半監(jiān)督單標(biāo)記分類器的性能。對所選未標(biāo)記樣本進(jìn)行偽標(biāo)記后，形成新的標(biāo)記集;將新的標(biāo)記樣本集分為多組，使用SVM作為分類器進(jìn)行交叉驗(yàn)證，計(jì)算分類準(zhǔn)確率，求出每種偽標(biāo)記所對應(yīng)的分類誤差率，最后選取能使分類器誤差最小的偽標(biāo)記作為未標(biāo)記樣本的最終標(biāo)記，挖掘未標(biāo)記樣本信息，擴(kuò)充未標(biāo)記樣本數(shù)量。最后對算法的性能進(jìn)行分析，并在UCI數(shù)據(jù)集進(jìn)行半監(jiān)督分類實(shí)驗(yàn)，驗(yàn)證算法的有效性。

1 基于交叉驗(yàn)證思想的半監(jiān)督分類方法(CV－S3VM)

1.1 算法思想

該算法的主要思想是通過對未標(biāo)記樣本進(jìn)行偽標(biāo)記，將偽標(biāo)記后的樣本加入到標(biāo)記樣本集中，參與訓(xùn)練和測試，選取能使分類器誤差較小的標(biāo)記作為最終的標(biāo)記，實(shí)現(xiàn)對未標(biāo)記樣本進(jìn)行標(biāo)記。依次挖掘未標(biāo)記樣本的隱含信息，擴(kuò)充標(biāo)記樣本的數(shù)目。用最終的標(biāo)記樣本訓(xùn)練分類器，減少分類器誤差，直接提高學(xué)習(xí)算法的泛化能力。首先選取一個(gè)未標(biāo)記樣本集U，把U中每一個(gè)未標(biāo)記樣本都作為候選樣本，按照不同的分類類別分別進(jìn)行不同的偽標(biāo)記;其次，將標(biāo)記后的候選樣本放入已標(biāo)記樣例中形成新的訓(xùn)練集，將訓(xùn)練集進(jìn)行分組、交叉驗(yàn)證;接著，分別計(jì)算在各種偽標(biāo)記下分類器訓(xùn)練后誤差值，選取誤差值小的對應(yīng)標(biāo)記作為最終的樣本標(biāo)記值;反復(fù)迭代，不斷擴(kuò)充標(biāo)記集的樣本數(shù)目，作為最終的訓(xùn)練集。

1.2 算法實(shí)現(xiàn)

該算法借鑒交叉驗(yàn)證思想中分組、交叉、驗(yàn)證、求平均值等思想和方法挖掘未標(biāo)記樣本的隱含信息，實(shí)現(xiàn)對未標(biāo)記樣本的標(biāo)記。具體實(shí)現(xiàn)算法描述如表1所示。

表1 交叉驗(yàn)證半監(jiān)督分類算法描述Table 1 The description of sem i－supervised classification algorithm based on cross validation

第1步，合理選取有標(biāo)記樣本集L、未標(biāo)記樣本集U作為初始的分類器訓(xùn)練集。

第2步，從未標(biāo)記樣本集U中選取未標(biāo)記樣本w，分別給w進(jìn)行偽標(biāo)記Mi，其中Mi=1，2，…，m－1，m(假設(shè)是進(jìn)行m分類，m≥2)。

第3步，對任意一個(gè)標(biāo)記為Mi的樣本w，將其依次填加到有標(biāo)記樣本集L中。

第4步，對于新的有標(biāo)記樣本集L，按照交叉驗(yàn)證的思想將其均勻分為k組。將每個(gè)子集數(shù)據(jù)分別做一次驗(yàn)證集，同時(shí)其余的k－1組子集數(shù)據(jù)作為訓(xùn)練集，得到k個(gè)模型。用這k個(gè)模型中的訓(xùn)練集訓(xùn)練分類器，使用驗(yàn)證集進(jìn)行驗(yàn)證，得到最終的分類準(zhǔn)確率，計(jì)算k個(gè)模型分類準(zhǔn)確率的平均數(shù)，得出相應(yīng)的誤差率。

第5步，選取使得誤差率最小的標(biāo)記Mx，用其實(shí)現(xiàn)對樣本w的最終標(biāo)記，并將標(biāo)記后的w添加到L中，實(shí)現(xiàn)對L的擴(kuò)充。

第6步，通過該方法反復(fù)迭代，不斷挖掘未標(biāo)記樣本的隱含信息，擴(kuò)充標(biāo)記樣本集L，直到未標(biāo)記樣本集U為空為止。

第7步，使用擴(kuò)展后的標(biāo)記樣本集作為最終的訓(xùn)練集，訓(xùn)練形成最終的半監(jiān)督分類器。

特別地，對于二分類問題，即k=2時(shí)，為了能較好地提高標(biāo)記正確率和分類準(zhǔn)確率，采用下面的方式進(jìn)行處理。當(dāng)滿足公式(1)時(shí)，將未標(biāo)記樣本標(biāo)記為第1類，滿足公式(2)時(shí)，將未標(biāo)記樣本標(biāo)記為第2類。

其中，e1和e2分別表示將未標(biāo)記樣本歸類為第1類和第2類時(shí)對應(yīng)的誤差，η為可調(diào)參數(shù)，可以通過η調(diào)節(jié)分類準(zhǔn)確率。

1.3 算法分析

該算法將交叉驗(yàn)證思想引入半監(jiān)督分類領(lǐng)域，通過迭代計(jì)算誤差，實(shí)現(xiàn)了對未標(biāo)記樣本數(shù)據(jù)的標(biāo)記。算法可以在某種意義下得到最優(yōu)的解，可以有效避免選擇野點(diǎn)，有效避免過學(xué)習(xí)和欠學(xué)習(xí)狀態(tài)的發(fā)生。

算法通過選擇能夠最大程度縮減分類器誤差的樣本進(jìn)行標(biāo)記，是一種統(tǒng)計(jì)學(xué)分析方法，具有很強(qiáng)的統(tǒng)計(jì)學(xué)基礎(chǔ)，可以建立基于主動(dòng)學(xué)習(xí)的統(tǒng)計(jì)學(xué)學(xué)習(xí)模型，即基于模型方差最小化的縮減策略［1，18］。期望誤差如式(3)所示，其中D為訓(xùn)練集，x為輸入特征，y(x)代表x對應(yīng)的實(shí)際類別，y^(x;D)為預(yù)測類別。ET(·)和ED(·)都表示在D上的期望誤差，但ED(·)表示通過主動(dòng)學(xué)習(xí)，選取誤差小的樣本進(jìn)行標(biāo)記后，將新標(biāo)記樣本擴(kuò)充到有標(biāo)記樣本集后的訓(xùn)練集D。式(3)可以通過式(4)計(jì)算求出，式(4)中的第三項(xiàng)可以通過式(5)計(jì)算得出，式(5)可以通過式(6)計(jì)算。通過交叉驗(yàn)證半監(jiān)督學(xué)習(xí)的目的就是選取期望誤差最小的樣本進(jìn)行標(biāo)記。

其中，ET(·)表示在D上的期望誤差。

其中，ED(·)表示D更新后在D上的期望誤差。

其中，＜·＞表示增加新的標(biāo)記樣本后，在D上的期望誤差值。

同時(shí)，算法操作簡單，可行性強(qiáng)，較容易實(shí)現(xiàn)對未標(biāo)記樣本的標(biāo)記，同時(shí)能較容易實(shí)現(xiàn)2分類問題和多分類問題。當(dāng)m的值為2時(shí)，算法可以解決2分類問題，當(dāng)m＞2時(shí)，算法很容易地轉(zhuǎn)化為解決多分類問題。該算法時(shí)間復(fù)雜度為O(n1*n2)，其中n1表示選取的未標(biāo)記樣本集中樣本數(shù)目，n2表示選取的標(biāo)記樣本中樣本的數(shù)目，一般情況下n1?n2。

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

實(shí)驗(yàn)平臺選用 Intel Core2 Duo CPU 2.0 GHz、內(nèi)存2.0 GB的 PC;安裝 Windows XP操作系統(tǒng)和MATLAB 7.8.0(R2009.0a)編程環(huán)境;SVM 分類器選用臺灣大學(xué)林智仁等人開發(fā)的模式識別與回歸機(jī)軟件包 libsvm －mat－2.89－3。

實(shí)驗(yàn)采用 UCI數(shù)據(jù)庫(http://archive.ics.uci.edu/ml/)中常用的5個(gè)數(shù)據(jù)集，數(shù)據(jù)集如表2所示。

對于表2所選取的樣本，將訓(xùn)練集和測試集的樣本數(shù)目比例設(shè)為1:1。將訓(xùn)練集分為標(biāo)記樣本和未標(biāo)記樣本兩種，按照標(biāo)記樣本占訓(xùn)練集樣本數(shù)目的比例(如式(7)所示)構(gòu)造三類半監(jiān)督分類實(shí)驗(yàn)數(shù)據(jù)集。第一類，標(biāo)記樣本占訓(xùn)練集樣本的5%;第二類，標(biāo)記樣本占訓(xùn)練集樣本的10%;第三類，標(biāo)記樣本占訓(xùn)練集樣本的20%。

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental data sets

對于構(gòu)造的三類半監(jiān)督分類實(shí)驗(yàn)數(shù)據(jù)集，分別使用普通的SVM方法(即訓(xùn)練集僅僅使用初始的有標(biāo)記樣本集)和CV－S3VM方法(通過交叉驗(yàn)證方法對未標(biāo)記樣本標(biāo)記，擴(kuò)充標(biāo)記樣本集)進(jìn)行分類實(shí)驗(yàn)。按照公式(8)和(9)統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果，其中P1表示CV－S3VM方法對訓(xùn)練集中未標(biāo)記樣本進(jìn)行標(biāo)記擴(kuò)充后，對未標(biāo)記樣本進(jìn)行標(biāo)記的正確率，P2表示SVM和CV－S3VM對測試集樣本進(jìn)行分類測試的分類正確率。

表3、表4和表5分別表示λ=5%，λ=10%和λ=20%時(shí)的實(shí)驗(yàn)結(jié)果。圖1－圖5分別表示SVM和CV－S3VM使用5種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)的分類正確率P2和標(biāo)記正確率P1的實(shí)驗(yàn)結(jié)果對比圖。

通過圖表可以看出，CV－S3VM使用了交叉驗(yàn)證方法對未標(biāo)記樣本進(jìn)行了標(biāo)記和擴(kuò)充，具有較高的標(biāo)記率，因此其對測試集樣本的分類率明顯比SVM要高，尤其在Sonar數(shù)據(jù)集(圖3)中最為明顯。同時(shí)，我們也可以看到，在標(biāo)記樣本集數(shù)目較少時(shí)，即λ=5%，相對SVM，CV－S3VM的分類率的優(yōu)越性得到了充分體現(xiàn)。但隨著標(biāo)記樣本集數(shù)目不斷增加，到達(dá)一定程度時(shí)，CV－S3VM和SVM的分類率差距越來越小。這是由于此時(shí)標(biāo)記樣本數(shù)目已經(jīng)非常充足，半監(jiān)督學(xué)習(xí)已經(jīng)演化成有監(jiān)督學(xué)習(xí)。

表3 實(shí)驗(yàn)結(jié)果(λ=5%)Table 3 The experimental result(λ=5%)

表4 實(shí)驗(yàn)結(jié)果(λ=10%)Table 4 The experimental result(λ=10%)

表5 實(shí)驗(yàn)結(jié)果(λ=20%)Table 5 The experimental result(λ=20%)

圖1 ionosphere樣本實(shí)驗(yàn)結(jié)果對比圖Fig.1 The result comparison chart of sample ionosphere

圖2 pima樣本實(shí)驗(yàn)結(jié)果對比圖Fig.2 The result comparison chart of sample pima

圖3 Sonar樣本實(shí)驗(yàn)結(jié)果對比圖Fig.3 The result comparison chart of sample Sonar

圖4 WDBC樣本實(shí)驗(yàn)結(jié)果對比圖Fig.4 The result comparison chart of sample WDBC

圖5 australian樣本實(shí)驗(yàn)結(jié)果對比圖Fig.5 The result comparison chart of sample australian

3 結(jié)語

本文將交叉驗(yàn)證思想引入到半監(jiān)督分類領(lǐng)域，提出一種基于交叉驗(yàn)證思想的半監(jiān)督分類算法(CV－S3VM)。實(shí)驗(yàn)結(jié)果表明，CV－S3VM操作簡單、能較容易實(shí)現(xiàn)對未標(biāo)記樣本的標(biāo)記，性能良好。尤其在標(biāo)記樣本較少的情況下具有明顯的優(yōu)越性?？梢詫⒃摲椒☉?yīng)用到病例分類、網(wǎng)絡(luò)數(shù)據(jù)流分類、入侵檢測等標(biāo)記樣本稀缺領(lǐng)域。

［1］吳偉寧，劉揚(yáng)，郭茂祖，等.基于采樣策略的主動(dòng)學(xué)習(xí)算法研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2012，49(6):1162－1173.

［2］ZHU X J.Semi－ supervised Learning Literature Survey［R］.Madison:University ofWisconsin，2008.

［3］李昆侖，曹錚，曹麗蘋，等.半監(jiān)督聚類的若干新進(jìn)展［J］.模式識別與人工智能，2009，22(5):735 －742.

［4］CH APELLE O，ZIEN A.Semi－supervised Classification by Low Density Separation［C］.Proceedings of the 10th InternationalWorkshop on Artificial Intelligence and Statistics，Barbados，2005.57 －64.

［5］ZHOU ZH ，LIM.Tri－training:exploiting unlabeled data using three classifiers［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(11):1529－1542.

［6］Zhang M L，ZHOU Z H.CoTrade:Confident co－training with data editing［J］.IEEE Transactions on Systems，Man，and Cybernetics － Part B:Cybernetics，2011，41(6):1612－1626.

［7］趙建華，李偉華.一種協(xié)同半監(jiān)督分類算法Co－S3OM［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(11):3249 －3252.

［8］WANG Yun－yun，CHEN Song－cai，ZHOU Zhi－ hua.New semi－supervised classification method based on modified cluster assumption［J］.IEEE Transactions on Neural Networks and Learning Systems，2012，23(5):689－702.

［9］LIY F，KWOK J T，ZHOU Z H.Cost－Sensitive Semi－supervised Support Vector Machine［A］.In:Proceedings of the 24th AAAI Conference on Artificial Intelligences(AAAI＇10)［C］.Atlanta，GE，2010，500 －505.

［10］MENG Jun，WU Li－xia，WANG Xiu－kun.Granulation－based symbolic representation of time series and semi－supervised classification［J］.Computers and Mathematics with Applications，2011，62(9):3581 －3590.

［11］KONG Xiang－nan，NG M K，ZHOU Zhi－h(huán)ua.Transductive multi－label learning via label set propagation［J］.IEEE Transactions on Knowledge and Data Engineering(TKDE)，2011.25(3):704 －719.

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

［13］趙存秀，王瑞波，李濟(jì)洪.交叉驗(yàn)證中類別切分不均衡對分類性能的影響分析［J］.太原師范學(xué)院學(xué)報(bào):自然科學(xué)版，2013，12(1):53－57.

［14］杜偉杰，王瑞波，李濟(jì)洪.基于均衡7×2交叉驗(yàn)證的模型選擇方法［J］.太原師范學(xué)院學(xué)報(bào):自然科學(xué)版，2013，12(1):27 －31.

［15］劉學(xué)藝，李平，郜傳厚.極限學(xué)習(xí)機(jī)的快速留一交叉驗(yàn)證算法［J］.上海交通大學(xué)學(xué)報(bào)，2011，45(8):1141－1145.

［16］JOHN G H.Robust Decision Trees:Removing Outliers from Databases［A］.Proceedings of the First International Conference on Knowledge Discovery and Data Mining［C］.Menlo Park，CA:AAAIPress，1995.174 －179.

［17］張健沛，楊顯飛，楊 靜.交叉驗(yàn)證容噪分類算法有效性分析及其在數(shù)據(jù)流上的應(yīng)用［J］.電子學(xué)報(bào)，2011，39(2):378－381.

［18］COHN D，GHAHRAMANI Z，JORDAN MI.Active learning with statistical models［J］.Journal of Artificial Intelligence Research，1996，(4):129 －145.