基于主動(dòng)學(xué)習(xí)的圖半監(jiān)督分類算法

高 成，陳秀新，于重重，劉 宇

（北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京100048）

0 引 言

近些年，半監(jiān)督學(xué)習(xí)方法得到了廣泛地研究與應(yīng)用。例如基于半監(jiān)督流形學(xué)習(xí)的人臉識別研究［1］、基于圖的半監(jiān)督學(xué)習(xí)模型研究與分類器設(shè)計(jì)［2］等。從早期的生成模型、有限混合模型無監(jiān)督學(xué)習(xí)算法［3］，到基于圖的半監(jiān)督協(xié)同訓(xùn)練算法［4］，再到把圖論方法引入半監(jiān)督學(xué)習(xí)，如高斯隨機(jī)場［5］、基于圖方法的半監(jiān)督學(xué)習(xí)［6］等。基于圖的半監(jiān)督學(xué)習(xí)算法主要是根據(jù)已標(biāo)記樣本節(jié)點(diǎn)的標(biāo)記信息與節(jié)點(diǎn)之間的關(guān)系推測未標(biāo)記樣本節(jié)點(diǎn)的類別標(biāo)記，借助樣本之間的關(guān)系確立樣本關(guān)系完全圖結(jié)構(gòu)。在圖模型中，既有已標(biāo)記樣本節(jié)點(diǎn)，也有未標(biāo)記節(jié)點(diǎn)，節(jié)點(diǎn)之間的邊權(quán)代表樣本節(jié)點(diǎn)之間的相關(guān)性，已標(biāo)記節(jié)點(diǎn)的類別標(biāo)記信息根據(jù)相關(guān)性的大小傳播給周圍的未標(biāo)記節(jié)點(diǎn)，已標(biāo)記節(jié)點(diǎn)近似于一個(gè)傳播源，節(jié)點(diǎn)間的相關(guān)性越大，標(biāo)記的傳播越容易。該算法是非參數(shù)直推式的，與其它學(xué)習(xí)算法相比，這類方法更為直接，并且直觀解析性強(qiáng)，具有優(yōu)良的分類性能。

典型的算法如Zhu提出的圖傳播算法高斯隨機(jī)域算法（Gaussian random fields algorithm，GRF）［7］、Zha等提出的ML－GRF （multi－label Gaussian random field）算法［8］等，基于圖的半監(jiān)督算法利用數(shù)據(jù)本身的流形結(jié)構(gòu)建立圖模型，延續(xù)了半監(jiān)督學(xué)習(xí)帶來的分類性能上的優(yōu)勢，并且提高了樣本的利用率。但是，基于圖的半監(jiān)督學(xué)習(xí)也有自身的局限性，其對于圖的依賴性較強(qiáng)。

此外，標(biāo)準(zhǔn)的基于圖的半監(jiān)督算法忽略了標(biāo)記樣本噪聲對建立圖模型的影響，以及在處理不平衡數(shù)據(jù)分類時(shí)的低性能問題，這些問題一直是限制其發(fā)展的重要因素。基于上述問題，并主要以解決橋梁結(jié)構(gòu)健康數(shù)據(jù)分類問題為目的，本文在GRF算法基本思想的基礎(chǔ)上，分別針對標(biāo)記樣本集噪聲和不平衡性數(shù)據(jù)分類問題進(jìn)行改進(jìn)，提出了一個(gè)改進(jìn)的圖半監(jiān)督算法，即帶噪聲度量的主動(dòng)學(xué)習(xí)高斯隨機(jī)域算法，旨在為數(shù)據(jù)分類問題提供一種更有效的算法。

1 理論基礎(chǔ)

1.1 樣本噪聲問題

在實(shí)際分類中，樣本數(shù)據(jù)集通常帶有一定的噪聲。在數(shù)據(jù)分類的過程中，這些噪聲數(shù)據(jù)會(huì)誤導(dǎo)分類器，將錯(cuò)誤傳播給整個(gè)數(shù)據(jù)集，極大地影響了分類的準(zhǔn)確率。針對噪聲的處理方法有很多，例如小波消噪算法［9］、聚類數(shù)據(jù)清洗等［10］。Hein等提出一種對流形采樣樣本去噪的方法［11］，雖然預(yù)處理后建立的圖分類準(zhǔn)確性更高了，但當(dāng)使用高斯函數(shù)做邊的權(quán)重時(shí)，對高斯函數(shù)的帶寬選擇很敏感。

本文提出的噪聲度量方法能夠很好地解決上述問題，不僅去除噪聲數(shù)據(jù)，而且保留蘊(yùn)含大量信息的樣本數(shù)據(jù)，增強(qiáng)算法的魯棒性。主要考慮將已有圖半監(jiān)督分類算法進(jìn)行改進(jìn)，加入噪聲處理環(huán)節(jié)，通過信息熵來度量樣本集中的潛在噪聲數(shù)據(jù)，對噪聲數(shù)據(jù)進(jìn)行處理，提高算法分類精度。具體來說，將給定數(shù)據(jù)集進(jìn)行聚類，分成數(shù)量較大的聚類簇和數(shù)量較小的聚類簇，分別計(jì)算每個(gè)樣本節(jié)點(diǎn)到各個(gè)聚類簇中心的距離，求得每個(gè)樣本的噪聲度量值NF，將樣本集中每個(gè)樣本的噪聲度量按降序排列，去除掉噪聲排名較高的樣本，避免噪聲數(shù)據(jù)通過分類器傳播到整個(gè)數(shù)據(jù)集。

1.2 主動(dòng)學(xué)習(xí)解決的核心問題

圖的半監(jiān)督算法從樣本的全局結(jié)構(gòu)出發(fā)，考慮的是樣本的標(biāo)記傳播性，卻沒有考慮到個(gè)別樣本的特殊信息。在類別數(shù)量少時(shí)，由于構(gòu)圖方法的不同，往往樣本數(shù)量上存在很大的差異，因此，會(huì)產(chǎn)生樣本不平衡問題，主動(dòng)學(xué)習(xí)就是解決該問題的有效方法。

在主動(dòng)學(xué)習(xí)中，學(xué)習(xí)器自動(dòng)地選擇信息量大的樣本進(jìn)行標(biāo)記，而不是使用已有的給定標(biāo)記樣本。算法對主動(dòng)學(xué)習(xí)篩選后的數(shù)據(jù)樣本進(jìn)行分類，并加入到訓(xùn)練樣本集中，形成新的標(biāo)記樣本集，并采用迭代法來更新分類模型。理論分析表明，在類似的分類準(zhǔn)確率下，有效樣本選擇和隨機(jī)樣本選擇相比，可以大大減少所需樣本數(shù)。

主動(dòng)學(xué)習(xí)與半監(jiān)督學(xué)習(xí)看似相對獨(dú)立，但在解決實(shí)際的問題時(shí)往往可以結(jié)合使用。例如在模式識別研究中，手寫體字符識別被很多文獻(xiàn)用以檢驗(yàn)結(jié)合主動(dòng)學(xué)習(xí)的基于圖的半監(jiān)督算法的性能［12］，半監(jiān)督學(xué)習(xí)只需少量有價(jià)值樣本就能實(shí)現(xiàn)對大量未標(biāo)記樣本的分類，主動(dòng)學(xué)習(xí)可以輔助生成信息含量大的訓(xùn)練樣本集，不僅能夠提高算法的分類效果，還能最大限度降低人工標(biāo)記的成本。指紋識別研究就用到了這一思想，將兩種算法相結(jié)合運(yùn)用到指紋圖像提取的應(yīng)用中，在實(shí)際的識別過程中收到了很好的反響［13］。

2 基于主動(dòng)學(xué)習(xí)算法的圖半監(jiān)督分類算法

2.1 帶噪聲系數(shù)的高斯隨機(jī)域算法

實(shí)際分類過程中，訓(xùn)練樣本集常帶有一些噪聲標(biāo)記，這些噪聲數(shù)據(jù)會(huì)誤導(dǎo)分類器的訓(xùn)練，將噪聲傳播給整個(gè)數(shù)據(jù)集。因此，在分類過程中噪聲的檢測與剔除十分必要。

考慮樣本噪聲過程中，樣本噪聲度量由類樣本大小和節(jié)點(diǎn)近鄰大類別的數(shù)據(jù)距離中心決定，一個(gè)樣本所屬類別數(shù)量越大，該樣本是噪聲的可能性就越小。為減少噪聲樣本在傳播過程中對分類性能的影響，標(biāo)記傳播算法目標(biāo)為最小化能量函數(shù)E（F），不同方法在于選擇了不同目標(biāo)函數(shù)。高斯隨機(jī)域算法 （GRF）作為最廣泛使用的圖傳播算法，具有分類精度高、可觀性等優(yōu)點(diǎn)。GRF 算法的目標(biāo)函數(shù)為

為抑制噪聲數(shù)據(jù)對分類結(jié)果的影響，本文考慮將噪聲處理算法與高斯隨機(jī)域算法結(jié)合，提出一種基于圖的半監(jiān)督分類算法，即帶噪聲系數(shù)的高斯隨機(jī)域?qū)W習(xí)算法（Gaussian random fields based on noise filter），簡稱GRFNF算法。其偽代碼見表1。

表1 GRFNF算法偽代碼

2.2 基于主動(dòng)學(xué)習(xí)與噪聲系數(shù)的高斯隨機(jī)域算法

為解決樣本不平衡問題，利用主動(dòng)學(xué)習(xí)的選擇器篩選出有代表性的樣本，通過領(lǐng)域?qū)＜胰斯みM(jìn)行標(biāo)記，使標(biāo)記樣本集的類別數(shù)量相同，有效解決不平衡問題。將被篩選的樣本及標(biāo)記添加到標(biāo)記樣本集，分類器可以同時(shí)使用標(biāo)記和未標(biāo)記的數(shù)據(jù)，結(jié)合算法的流程如圖1所示。

對于一個(gè)非平衡樣本集，其數(shù)據(jù)分布如圖2 所示，中間的豎線代表臨界面，樣本離平面越遠(yuǎn)，其類別越確定，對分類問題的貢獻(xiàn)越小。若樣本距離該臨界面越近，該樣本的分類越不好分配，這樣的樣本比距離平面遠(yuǎn)的樣本包含更重要的信息，須人工標(biāo)記，此類有價(jià)值樣本能夠大大提升學(xué)習(xí)器的性能。因此，主動(dòng)學(xué)習(xí)的任務(wù)是搜索類別模糊的樣本交由專家進(jìn)行標(biāo)記，即選擇特定類的近鄰樣本集。

圖1 本文算法流程

圖2 不平衡數(shù)據(jù)集的數(shù)據(jù)分布

通過樣本類劃分獲得新的訓(xùn)練樣本集，緩解樣本分布不平衡的問題，同時(shí)添加具有代表性的樣本。本文結(jié)合主動(dòng)學(xué)習(xí)以平衡樣本集為目的，將主動(dòng)學(xué)習(xí)嵌入到基于圖的半監(jiān)督分類算法中，提出帶噪聲系數(shù)的主動(dòng)學(xué)習(xí)高斯隨機(jī)域 （combining active learning and Gaussian random fields with noise filtering，ALGRFNF）算法，偽代碼見表2。

3 算法驗(yàn)證

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評價(jià)指標(biāo)

為了驗(yàn)證結(jié)合了主動(dòng)學(xué)習(xí)的圖半監(jiān)督分類算法的有效性，在標(biāo)準(zhǔn)UCI數(shù)據(jù)集上進(jìn)行驗(yàn)證實(shí)驗(yàn)，對算法的有效性進(jìn)行分析。將帶噪聲系數(shù)的主動(dòng)學(xué)習(xí)高斯隨機(jī)域算法與標(biāo)準(zhǔn)GRF算法算法進(jìn)行比較。

表2 ALGRFNF算法偽代碼

實(shí)驗(yàn)中采用4個(gè)來自UCI的不平衡數(shù)據(jù)集，wine、wdbc、glass和Geman是數(shù)據(jù)挖掘研究中常用的不平衡數(shù)據(jù)集。各數(shù)據(jù)集的特征信息見表3。

表3 數(shù)據(jù)集的屬性特征

進(jìn)行實(shí)驗(yàn)時(shí)，將每個(gè)數(shù)據(jù)集中數(shù)據(jù)的順序隨機(jī)打亂，取其中的30%作為標(biāo)記樣本數(shù)據(jù)集L，剩余的70%作為未標(biāo)記樣本集。

算法的評價(jià)指標(biāo)如下

其中，R 為算法分類錯(cuò)誤率，Ncorrect為分類正確的樣本數(shù)目，N 為總樣本數(shù)，Rimprove為算法性能提高比率。

3.2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的有效性，分別將改進(jìn)算法與標(biāo)準(zhǔn)基于圖的高斯隨機(jī)域算法作用在4個(gè)數(shù)據(jù)集上，每個(gè)數(shù)據(jù)集重復(fù)20遍。根據(jù)實(shí)驗(yàn)設(shè)置進(jìn)行數(shù)據(jù)分類實(shí)驗(yàn)，通過主動(dòng)學(xué)習(xí)算法處理不平衡數(shù)據(jù)集，以數(shù)據(jù)集glass為例，圖3 （a）為原始的非平衡樣本集的類型分布，圖3 （b）為主動(dòng)學(xué)習(xí)處理后的樣本集的類型分布。從圖中可以看出，經(jīng)過主動(dòng)學(xué)習(xí)處理的樣本集類別分布較之原數(shù)據(jù)集更加平衡，算法能夠有效地解決樣本集不平衡的問題。

圖3 非平衡樣本集的處理

實(shí)驗(yàn)中樣本的劃分是隨機(jī)抽取的，故實(shí)驗(yàn)存在隨機(jī)性，一次實(shí)驗(yàn)沒法從整體上體現(xiàn)分類算法的效果，為了避免實(shí)驗(yàn)的偶然性，對每個(gè)數(shù)據(jù)集重復(fù)進(jìn)行20次實(shí)驗(yàn)。反復(fù)的實(shí)驗(yàn)結(jié)果具有統(tǒng)計(jì)特性，比較不同算法準(zhǔn)確率的相對值，分析出數(shù)值變化的趨勢，才能客觀的反應(yīng)算法的性能，實(shí)驗(yàn)結(jié)果如圖4所示。20次實(shí)驗(yàn)隨機(jī)抽取標(biāo)記樣本，從圖中可以看出，改進(jìn)的主動(dòng)學(xué)習(xí)帶噪聲圖半監(jiān)督算法的準(zhǔn)確率普遍高于標(biāo)準(zhǔn)的圖半監(jiān)督算法。

圖5顯示了主動(dòng)學(xué)習(xí)帶噪聲高斯隨機(jī)域算法與噪聲圖半監(jiān)督算法及標(biāo)準(zhǔn)的高斯隨機(jī)域算法相比性能的提高比。

為了客觀地比較算法的性能，本文的數(shù)據(jù)集選擇標(biāo)準(zhǔn)UCI常用的不平衡數(shù)據(jù)集，將所提出的改進(jìn)算法與標(biāo)準(zhǔn)的高斯隨機(jī)域算法相比較。從實(shí)驗(yàn)結(jié)果可以看出，主動(dòng)學(xué)習(xí)算法在改善樣本標(biāo)記不平衡問題上有良好的效果。在樣本集不平衡的情況下，改進(jìn)算法相對于標(biāo)準(zhǔn)高斯隨機(jī)域算法，具有更高的分類準(zhǔn)確率，且具有明顯的性能提高比率。

圖4 不同數(shù)據(jù)集上算法的準(zhǔn)確率

圖5 算法的性能提高比

4 結(jié)束語

本文主要對主動(dòng)學(xué)習(xí)的主要方法及樣本類劃分算法進(jìn)行了闡述，提出了一種帶噪聲系數(shù)的主動(dòng)學(xué)習(xí)高斯隨機(jī)域算法。將噪聲處理算法與高斯隨機(jī)域算法相結(jié)合，利用基于樣本劃分的主動(dòng)學(xué)習(xí)方法，對正類的近鄰樣本集中的樣本與特定類的樣本形成的新的樣本集做總體散度排序，并篩選出能使新的樣本集中總體散度最小的樣本，來代替正類的近鄰樣本集中所有的樣本形成平衡類。通過實(shí)驗(yàn)可以看出，本文提出的ALGRFNF 算法的分類性能明顯優(yōu)于GRFNF和標(biāo)準(zhǔn)的GRF 算法，這說明類不平衡問題的確影響了分類效果。主動(dòng)學(xué)習(xí)的樣本散度劃分算法能夠有效地改善樣本類別不平衡的問題。

［1］BAI Wanrong.Methods of feature extraction based on manifold learning in face recognition ［D］.Gansu：Lanzhou University of Technology，2012 （in Chinese）. ［白萬榮.人臉識別中基于流形學(xué)習(xí)的特征提取方法研究 ［D］.甘肅：蘭州理工大學(xué)，2012.］

［2］HAO Jianbai.Research on graph－based semi－supervised learning model and classifier design ［D］.Hefei：University of Science and Technology of China，2009 （in Chinese）. ［郝建柏.基于圖的半監(jiān)督學(xué)習(xí)模型研究與分類器設(shè)計(jì) ［D］.合肥：中國科學(xué)技術(shù)大學(xué)，2009.］

［3］Abas AR.An algorithm for unsupervised learning and optimization of finite mixture models［J］.Egyptian Informatics Journal，2011，12 （1）：19－27.

［4］GUO Tao，LI Guiyang，LAN Xia.Semi－supervised collaborative training algorithm based on graph ［J］.Computer Engineering，2012，38 （13）：163－165. ［郭濤，李貴洋，蘭霞.基于圖的半監(jiān)督協(xié)同訓(xùn)練算法 ［J］.計(jì)算機(jī)工程，2012，38（13）：163－165.］

［5］LU Jialei.Comparison and improvement of two method based on semi－supervised learning［D］.Qingdao：China Ocean University，2010 （in Chinese）.［盧加磊.半監(jiān)督學(xué)習(xí)中協(xié)同訓(xùn)練與多視圖方法的比較及改進(jìn)［D］.青島：中國海洋大學(xué)，2010.］

［6］Hady MFA，Schwenker F.Combining committee－based semisupervised learning and active learning ［J］.Journal of Computer Science and Technology，2010，25 （4）：681－698.

［7］JIN Yuan.Multi－label classification with active learning and semi－supervised Bayesian networks ［D］.Xiangtan：Xiangtan University，2012 （in Chinese）.［金圓.結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督貝葉斯網(wǎng)絡(luò)多類標(biāo)分類 ［D］.湘潭：湘潭大學(xué)，2012.］

［8］Zha ZJ，Mei T，Wang J，et al.Graph－based semi－supervised learning with multiple labels［J］.Journal of Visual Communication and Image Representation，2009，20 （2）：97－103.

［9］ZHAN Yongzhao，CHEN Yabi.Co－training semi－supervised active learning algorithm with noise filter［J］.Journal of Pattern Recognition and Artificial Intelligence，2009，22 （5）：750－755 （in Chinese）.［詹永照，陳亞必.具有噪聲過濾功能的協(xié)同訓(xùn)練半監(jiān)督主動(dòng)學(xué)習(xí)算法 ［J］.模式識別與人工智能，2009，22 （5）：750－755.］

［10］ZHANG Huaitao.A multi－graph semi－supervised learning based on geodesic distance［D］.Xi’an：Xi’an University of Electronic Science and Technology，2013 （in Chinese）.［張懷濤.基于測地距離的多圖組合半監(jiān)督學(xué)習(xí) ［D］.西安：西安電子科技大學(xué)，2013.］

［11］ZHAN Huirong.Research on graph－based semi－supervised learning algorithms［D］.Wuhan：Huazhong University of Science and Technology，2009 （in Chinese）.［占惠融.基于圖的半監(jiān)督學(xué)習(xí)算法研究［D］.武漢：華中科技大學(xué)，2009.］

［12］WANG Yao.Research on optimization of semi－supervised classification algorithm combining with active learning ［D］.Dalian：Dalian Dalian University of Technology，2013 （in Chinese）.［王瑤.結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督分類算法優(yōu)化研究［D］.大連：大連理工大學(xué)，2013.］

［13］LIANG Yanfeng.Research of query－by－committee method of active learning ［D］.Qingdao：China Ocean University，2010 （in Chinese）.［梁延峰.基于專家委員會(huì)的主動(dòng)學(xué)習(xí)算法研究 ［D］.青島：中國海洋大學(xué)，2010.］