趙建華

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

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

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

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

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

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

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

1.1 算法思想

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

1.2 算法實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

1.3 算法分析

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

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

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

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

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

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

2 實驗

實驗平臺選用 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ā)的模式識別與回歸機軟件包 libsvm －mat－2.89－3。

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

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

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

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

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

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

表3 實驗結(jié)果(λ=5%)Table 3 The experimental result(λ=5%)

表4 實驗結(jié)果(λ=10%)Table 4 The experimental result(λ=10%)

表5 實驗結(jié)果(λ=20%)Table 5 The experimental result(λ=20%)

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

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

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

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

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

3 結(jié)語

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

［1］吳偉寧，劉揚，郭茂祖，等.基于采樣策略的主動學(xué)習(xí)算法研究進展［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］.模式識別與人工智能，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］.計算機應(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)督多標記學(xué)習(xí)方法［J］.計算機研究與發(fā)展，2012，49(6):1272－1278.

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

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

［15］劉學(xué)藝，李平，郜傳厚.極限學(xué)習(xí)機的快速留一交叉驗證算法［J］.上海交通大學(xué)學(xué)報，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］張健沛，楊顯飛，楊 靜.交叉驗證容噪分類算法有效性分析及其在數(shù)據(jù)流上的應(yīng)用［J］.電子學(xué)報，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.