一種基于半監(jiān)督學(xué)習(xí)的非平衡分類算法

武永成

(荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門448000)

在利用監(jiān)督學(xué)習(xí)(supervised learning)進(jìn)行分類時(shí)，往往需要大量的有標(biāo)注(label)(即分類類型)的樣例(labeled instances)，才能得到準(zhǔn)確率高的分類模型(classifier)． 現(xiàn)實(shí)世界中，通常存在大量的未標(biāo)注樣例(unlabeled instances)，而有標(biāo)注樣例則往往較少．例如在計(jì)算機(jī)輔助醫(yī)學(xué)圖像分析中，可以從醫(yī)院獲得大量的醫(yī)學(xué)圖像作為訓(xùn)練例，但如果要求醫(yī)學(xué)專家把這些圖像中的病灶都標(biāo)注出來，則要付出大量的時(shí)間和精力，這往往是不現(xiàn)實(shí)的．為了綜合利用有限的有標(biāo)注樣例和大量的未標(biāo)注樣例，各種半監(jiān)督學(xué)習(xí)方法(semisupervised learning)被提出，并取得較好的效果［1－2］．但現(xiàn)存的這些半監(jiān)督學(xué)習(xí)方法都假定樣例數(shù)據(jù)(包括有標(biāo)注數(shù)據(jù)和未標(biāo)注數(shù)據(jù))都是均衡的，即標(biāo)注的分布是均衡的．現(xiàn)實(shí)世界中，很多情況下，樣例數(shù)據(jù)是不均衡的．例如:在1 000 個(gè)體檢數(shù)據(jù)集中，最終分類類型為健康的可能占90%，分類類型為不健康的可能為10%，標(biāo)注的分布就不是均衡的了．本研究中，為便于敘述，將一個(gè)數(shù)據(jù)集中大多數(shù)的樣例都屬于的分類類型稱為MA，而剩余的樣例的分類類型稱為MI．對(duì)于非平衡數(shù)據(jù)的分類(imbalanced classification)，半監(jiān)督學(xué)習(xí)最大的問題是:最終得到的分類模型可能只對(duì)MA 數(shù)據(jù)敏感，而忽略MI 數(shù)據(jù)．在對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類預(yù)測(cè)時(shí)，容易將樣例分類為MA 而忽略MI．

針對(duì)非平衡數(shù)據(jù)的分類，在監(jiān)督學(xué)習(xí)中，主要采用的是重取樣(re－sampling)［3］和代價(jià)敏感(cost－sensitive learning)［4］的方法．

本研究的貢獻(xiàn)在于:①對(duì)監(jiān)督學(xué)習(xí)中的重取樣技術(shù)進(jìn)行擴(kuò)展，使其應(yīng)用到半監(jiān)督學(xué)習(xí)中;②通過隨機(jī)動(dòng)態(tài)生成樣例特征子空間(random feature subspace)，提供半監(jiān)督學(xué)習(xí)的協(xié)同訓(xùn)練［5］(co－training)所需的不同的視圖(view)．在4 個(gè)相關(guān)數(shù)據(jù)集上的試驗(yàn)驗(yàn)證了本方法的有效性．

1 相關(guān)工作

1．1 基于半監(jiān)督學(xué)習(xí)的分類

機(jī)器學(xué)習(xí)的分類問題中，給定一個(gè)樣例集合D={＜x1，y1＞，…＜xn，yn＞}∈X×Y，其中＜xi，yi＞是一個(gè)樣例．xi是一個(gè)向量［xi1，…xim］，yi是該樣例的標(biāo)注(或分類類型)．X、Y分別是xi，yi的取值范圍． ＜x1，?＞是未標(biāo)注樣例，＜x1，y1＞是有標(biāo)注樣例．

協(xié)同訓(xùn)練是當(dāng)前最流行的一種半監(jiān)督學(xué)習(xí)風(fēng)范［5］．它假設(shè)數(shù)據(jù)集有兩個(gè)充分冗余(sufficient and redundant)的視圖(view)．在這兩個(gè)視圖上利用有標(biāo)記示例分別訓(xùn)練出一個(gè)分類器，然后，在協(xié)同訓(xùn)練過程中，每個(gè)分類器從未標(biāo)注示例中挑選出若干分類置信度較高的示例進(jìn)行標(biāo)注，并把標(biāo)注后的示例加入另一個(gè)分類器的有標(biāo)注訓(xùn)練集中．協(xié)同訓(xùn)練的目的是，通過相互提供未知的信息，使得兩個(gè)分類器的準(zhǔn)確性都得以提高．

協(xié)同訓(xùn)練的關(guān)鍵是找到同一數(shù)據(jù)集的不同的視圖． 本文通過隨機(jī)動(dòng)態(tài)生成樣例特征子空間的方法［6］，在同一數(shù)據(jù)集上，產(chǎn)生多個(gè)視圖．

1．2 非平衡分類

非平衡分類問題，作為一個(gè)具有挑戰(zhàn)性的機(jī)器學(xué)習(xí)問題，近些年在多個(gè)領(lǐng)域被廣泛研究．如:機(jī)器學(xué)習(xí)領(lǐng)域、數(shù)據(jù)挖掘領(lǐng)域和算法領(lǐng)域．其中使用的最重要的技術(shù)是:重取樣技術(shù)和代價(jià)敏感學(xué)習(xí)技術(shù)．重取樣技術(shù)又分為增重取樣(over－sampling)［3］和減重取樣(under－sampling)［7］兩種方法．增重取樣技術(shù)通過復(fù)制MI 樣本來使得它和MA 的樣本數(shù)達(dá)到平衡．減重取樣技術(shù)則通過刪除一定的MA 樣本使它與MI 的樣本數(shù)達(dá)到平衡．本文采用減重取樣技術(shù)來處理非平衡分類問題．

2 基于半監(jiān)督學(xué)習(xí)的非平衡分類算法

采用半監(jiān)督學(xué)習(xí)中最流行的協(xié)同訓(xùn)練方法．對(duì)于協(xié)同訓(xùn)練所需的同一數(shù)據(jù)集上的不同視圖，本文采用隨機(jī)動(dòng)態(tài)特征子空間的產(chǎn)生辦法．

2．1 動(dòng)態(tài)子空間的產(chǎn)生

動(dòng)態(tài)子空間產(chǎn)生(Random Subspace Generation，RSG)是一種集成(ensemble)技術(shù)［6］． 如本文1．1 所述，對(duì)于樣例集合D 中的每個(gè)樣例＜xi，yi＞，xi是一個(gè)m維向量［xi1，xi2，…，xim］，即樣例由m個(gè)特征來描述．從m個(gè)特征中，RSG 隨機(jī)的選取r(m＞r)個(gè)特征，組成一個(gè)r維的特征子空間．通過這種方式，就產(chǎn)生了一個(gè)r維的訓(xùn)練樣例集合Ds={＜x1s，y1＞，＜x2s，y2＞，…＜xns，yn＞}∈X×Y，其中＜xis，yi＞的xis是r維的向量．

文中，r=m/2．在得到的兩個(gè)m/2 維數(shù)據(jù)集上，分別訓(xùn)練，生成兩個(gè)子空間分類器，為協(xié)同訓(xùn)練做準(zhǔn)備．

2．2 基于半監(jiān)督學(xué)習(xí)的非平衡分類算法

如1．2 節(jié)所述，本文采用減重取樣技術(shù)來處理非平衡分類問題．通過減重取樣技術(shù)得到平衡的訓(xùn)練數(shù)據(jù)集后，采用動(dòng)態(tài)子空間產(chǎn)生方法，生成兩個(gè)m/2 維數(shù)據(jù)集．在這兩個(gè)數(shù)據(jù)集上，訓(xùn)練生成協(xié)同訓(xùn)練所需的兩個(gè)子空間分類器．這里存在一個(gè)問題:由于采用減重取樣技術(shù)，使得大量MA樣本被舍棄，而這些MA樣本中可能蘊(yùn)含很多重要的信息．為充分利用這些信息，循環(huán)地利用減重取樣技術(shù)，生成多個(gè)平衡的樣本集合．在每個(gè)平衡的樣本集合上，再采用采用動(dòng)態(tài)子空間產(chǎn)生方法，生成兩個(gè)m/2 維數(shù)據(jù)集，訓(xùn)練生成兩個(gè)子空間分類器．本文提出的基于半監(jiān)督學(xué)習(xí)的非平衡分類算法，完整描述如算法1 所示．

算法1 基于半監(jiān)督學(xué)習(xí)的非平衡分類算法(Algorithm 1 An imbalanced classification algorithm based on semi－supervised learning)

5 for j=1 to K do 6 在全部特征空間上，隨機(jī)產(chǎn)生兩個(gè)特征子空間;7 在第j 個(gè)平衡的樣例集合上，在隨機(jī)產(chǎn)生的兩個(gè)特征子空間上，訓(xùn)練生成兩個(gè)分類器Ci1 和Ci2;8 利用Ci1 和Ci2，對(duì)未標(biāo)注樣例集合U 進(jìn)行分類，并選取分類置信度最高的一個(gè)MA 類型樣本和一個(gè)MI 類型的樣本，將它們加入B 中;9 end for 10 將集合B 中樣例分別加入K 個(gè)平衡的樣例集合中;11 A=A ∪B ;12 end for

3 試驗(yàn)結(jié)果與分析

試驗(yàn)中用到4 個(gè)數(shù)據(jù)集［8］．?dāng)?shù)據(jù)集的相關(guān)信息如表1 所示． 從表可以看出，每個(gè)數(shù)據(jù)集都是非平衡的，MA類型的樣例和MI類型的樣例的個(gè)數(shù)的比(K=(int)n+/ n－)最小為3，最大為8．

對(duì)于每個(gè)數(shù)據(jù)集，先隨機(jī)選取100 個(gè)MI樣例數(shù)據(jù)，然后選取K* 100 個(gè)MA樣例數(shù)據(jù)，形成有標(biāo)注樣例集合L．在隨機(jī)選取400個(gè)MA數(shù)據(jù)和400 個(gè)MI數(shù)據(jù)作為測(cè)試數(shù)據(jù);最后剩余的樣例數(shù)據(jù)，去掉它們的分類類型，讓它們組成未標(biāo)注樣例集合U．

由于數(shù)據(jù)的非平衡性，最終對(duì)算法的評(píng)價(jià)不能采用常用的分類預(yù)測(cè)正確率評(píng)價(jià)方法．為此，本文采用了一種流行的G－mean 方法［9］．該方法中其中TPrate=TP/(TP+FN)，TNrate=TN(TN+FP)．TP指樣例本身標(biāo)注為MA且被分類預(yù)測(cè)也是MA，F(xiàn)N指樣例本身標(biāo)注為MA但被分類預(yù)測(cè)為MI，TN指本身標(biāo)注為MI且被分類預(yù)測(cè)也是MI，F(xiàn)P指樣例本身標(biāo)注為MI但被分類預(yù)測(cè)為MA．

表1 試驗(yàn)中用到的數(shù)據(jù)集(Table 1 Experimental data sets)

為驗(yàn)證本算法的有效性，與另一基礎(chǔ)算法做了比較．該基礎(chǔ)算法的特征子空間是靜態(tài)的，其余部分與本算法相同．試驗(yàn)結(jié)果如圖1 所示．圖中Ours 代表本文提出的算法．Static 代表基礎(chǔ)算法．從圖看看出，在4 個(gè)數(shù)據(jù)集上，本研究中的算法都優(yōu)于Static 基礎(chǔ)算法．

圖1 比較Ours 和Static 在不同數(shù)據(jù)集上的分類正確率Fig．1 Classification accuracy on different data sets

4 結(jié)語(yǔ)

本文對(duì)基于半監(jiān)督學(xué)習(xí)的非平衡分類問題進(jìn)行了研究．首先采用減重取樣技術(shù)對(duì)原始非平衡數(shù)據(jù)進(jìn)行處理，得到多個(gè)平衡的數(shù)據(jù)集．然后在每個(gè)平衡的數(shù)據(jù)集上，采用動(dòng)態(tài)子空間產(chǎn)生方法，生成同一數(shù)據(jù)集的兩個(gè)不同視圖，從而利于半監(jiān)督學(xué)習(xí)進(jìn)行學(xué)習(xí)訓(xùn)練．試驗(yàn)表明該方法優(yōu)于靜態(tài)的子空間的產(chǎn)生辦法．在協(xié)同訓(xùn)練的過程中，循環(huán)的次數(shù)是根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)事先確定的．如何設(shè)定一個(gè)循環(huán)終止的條件，讓算法自動(dòng)確定循環(huán)的次數(shù)，是需要繼續(xù)研究的問題．

［1］ Cohen I，Cozman F G，Sebe N，et al．Semi－supervised learning of classifiers:theory，algorithm，and their application to human－computer interaction［C］//IEEE Trans．Pattern Anal．Mach． Intell，2004，26(12):553－567．

［2］ Zhu X．Semi－Supervised Learning Literature Survey［R］．Computer Sciences Technical Report，University of Wisconsin，Madison，2006．

［3］ Chawla N，Bowyer K，Hall L．SMOTE:Synthetic Minority Over－Sampling Technique［J］．Journal of Artificial Intelligence Research，2002(16):321－357．

［4］ Zhou Z，Liu X．Training Cost－Sensitive Neural Networks with Methods Addressing the Class Imbalance Problem［C］//IEEE Transaction on Knowledge and Data Engineering，2006(18):63－77．

［5］ 周志華．半監(jiān)督學(xué)習(xí)中的協(xié)同訓(xùn)練算法［C］//周志華，王玨．機(jī)器學(xué)習(xí)及其應(yīng)用．北京:清華大學(xué)出版社，2007:259－275．

［6］ Ho T．The Random Subspace Method for Constructing Decision Forests［C］//IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20(8):832－844．

［7］ Barandela R，Sánchez J，García V，et al．Strategies for Learning in Class Imbalance Problems［J］．Pattern Recognition，2003(36):849－851．

［8］ Multi－domain sentiment dataset v2．0［Z］．(2009－03－23)［2013－10－10］http://www．seas．upenn．edu/～mdredze/datasets/sentiment/．

［9］ Kubat M，Matwin S．Addressing the Curse of Imbalanced Training Sets:One－Sided Selection［C］．In Proceedings of ICML－97，1997:179－186．