□劉楊磊

(山西大學計算機與信息技術學院，山西太原030006)

1 引言

半監(jiān)督學習(Semi－supervised Learning)是模式識別和機器學習的重要研究領域。近幾年隨著機器學習理論在數(shù)據(jù)分析和數(shù)據(jù)挖掘等實際問題中的廣泛應用，半監(jiān)督學習在眾多理論和實際應用研究中也獲得了長足的發(fā)展［1］。半監(jiān)督學習主要關注如何綜合使用有標記樣本和未標記樣本來獲得具有良好性能和泛化能力的學習機器。

目前，常用的半監(jiān)督學習算法利用有標記樣本訓練分類器標注未標記樣本，來增加標記樣本的數(shù)量，這樣如果未標記樣本被錯誤標注將會影響后續(xù)分類器的迭代訓練，進而降低最終分類器的預測精度。MPWPS(The Most Possibly Wrong－predicted Sampling)作為一種主動學習算法，在訓練過程中選取最大可能預測錯誤的樣本進行標注來擴大有標記樣本集，保證了訓練集較小的情況下能夠獲得較高的分類正確率，從而降低構建高性能分類器的代價［2］。因此，本文借鑒MPWPS主動學習的思想，實現(xiàn)半監(jiān)督分類，來提高算法的性能。

2 背景知識

2.1 半監(jiān)督學習算法

按照學習目的的不同，大致將半監(jiān)督學習算法分為半監(jiān)督聚類［3］、半監(jiān)督分類和半監(jiān)督回歸，其中半監(jiān)督聚類和半監(jiān)督分類是目前研究的熱點［4］。半監(jiān)督分類是從有監(jiān)督學習的角度出發(fā)，當已標簽訓練樣例不足時，如何利用大量未標簽樣例信息輔助分類器的訓練［1］。

在A.Blum和T.Mitchell提出最早的協(xié)同訓練算法后，很多研究者對其進行了研究并取得了很多進展，使得協(xié)同訓練成為半監(jiān)督學習中最重要的風范之一［5］。而 Tri－ training算法［6］是 Zhou 等人提出的一種新的協(xié)同訓練算法，它使用3個分類器進行訓練。Tri－training對屬性集和3個分類器所用監(jiān)督學習算法都沒有約束，而且不使用交叉驗證，因此適用范圍更廣、效率更高。

Tri－training算法執(zhí)行過程如下:

該算法首先對有標記樣本集進行可重復取樣(Bootstrap Sampling)以獲得三個有標記訓練集，然后從每個訓練集產(chǎn)生一個分類器。在協(xié)同訓練過程中，各分類器所獲得的新標記樣本都由其余兩個分類器協(xié)作提供，具體來說，如果兩個分類器對同一個未標記樣本的預測相同，則該樣本就被認為具有較高的標記置信度，并在標記后被加入第三個分類器的有標記訓練集。在對未見樣本進行預測時，Tritraining算法不再像以往算法那樣挑選一個分類器來使用，而是使用集成學習中經(jīng)常用到的投票法來將三個分類器組成一個集成來實現(xiàn)對未見樣本的預測［3］。

2.2 主動學習算法

主動學習算法(Active Learning)最早由Lewis等人提出，用來解決對樣本進行標記代價昂貴或者非常困難的應用問題。主動學習研究是機器學習的重要研究領域之一，與半監(jiān)督學習有著密切的聯(lián)系。與被動接收訓練數(shù)據(jù)的學習算法不同，主動學習算法自主選擇對學習過程中最有用的樣本來請求用戶標記，以加快學習過程并提高分類性能［7］。

MPWPS算法是由龍軍等人提出的主動學習算法。該算法中，如果某個可能的標簽在當前分類器判斷下具有非常大的概率是該樣本的標簽，但通過某種更準確的評估機制判斷這個標簽不是該樣本的標簽，則這樣的樣本優(yōu)先被采樣。MPWPS算法通過采樣當前分類器最有可能預測錯誤的樣本從而試圖最大限度地減小版本空間。

找出最有可能預測錯誤的樣本，必須要度量當前分類器對于一個樣本預測錯誤的概率，也就是預測標注和真實標注不一致的概率。

為了得出度量公式，考慮分類器對樣本xi預測的標注為y，則預測標注為y的概率為1，真實標注為y的概率并不知道，但可以近似的估計。

估計真實標注為y的概率可以通過下述的方式進行。在擁有無標記樣本集U的情況下，Pu(y|x)表示分類器預測樣本x的標注為y的概率，相應的，1－Puy|x)表示分類器預測樣本x的標注不為y的概率。由于分類器不是完全正確的，分類正確率為p，所以Puy|x)中有比例p的部分才是實際應標注為y的，同理1－Puy|x)中也有比例1－p的部分是實際應標注為y的。這樣，可以近似地認為Pu(y|x)·p+(1－Pu(y|x)·(1－p)即為真實標注為y的概率。

因此，有公式(1):

當ESi越大時，表明預測標注和真實標注不一致的概率越大。

3 基于MPWPS主動學習的半監(jiān)督協(xié)同分類算法

算法首先利用MPWPS算法在未標記樣本中找出M組最有可能預測錯誤標注的樣本，將這M組樣本交給專家進行標注，在訓練集train中處理這M組樣本后再執(zhí)行Tri－training算法;在Tri－training算法中，首先采用協(xié)同訓練的方法訓練三個分類器，再采用投票法將三個分類器組成一個集成來實現(xiàn)對未標記樣本的標注。

基于MPWPS主動學習的半監(jiān)督協(xié)同分類算法的算法流程如下:

輸入?yún)?shù):有標記樣本集L，無標記樣本集U，測試集test，采樣的樣本數(shù)M;

輸出參數(shù):標注結(jié)果datalabel以及正確率accur;

Step 1 在L和U上調(diào)用MPWPS算法，得到M個由專家標注的有標記樣本AL，U′=U－AL，L′=L+AL;

Step 1.1 根據(jù)L訓練分類器H;

Step 1.2 對ESi，按照公式(1)計算ESi;

Step 1.3 根據(jù)ESi從U中選擇M個ESi最大的未標記樣本;

Step 1.4 將上述未標記樣本交給專家進行標注，得到由專家標注的有標記樣本AL;

Step 2 對有標記樣本集L′進行隨機采樣，產(chǎn)生3個訓練集 S1、S2、S3，分別訓練 H1、H2、H3;

Step 3 對每個Hi(i=1，2，3)，從無標記樣本集U'中由Hj和Hk(j，k≠i)選擇滿足判別條件的集合Li={x|x∈U且Hj(x)=Hk(x)}進行標記，并生成新訓練集

Step 4 用訓練集S′i重新訓練分類器Hi;

Step 5 如果H1、H2、H3中至少有一個發(fā)生變化，則轉(zhuǎn)Step 3;

Step 6 用分類器 H1、H2、H3對測試集 test進行標注得到標注結(jié)果datalabel并計算標注正確率accur;

算法流程圖如圖1所示。

圖1 算法流程圖

4 實驗及結(jié)果

本文在 UCI公共數(shù)據(jù)集 haberman、heart和breast上進行實驗，并將本文算法與Tri－training算法進行了對比實驗，以進一步驗證本文算法的有效性。實驗數(shù)據(jù)集的相關信息如表1所示。

表1 實驗數(shù)據(jù)集描述

本文在整個實驗中只針對2值分類問題進行研究，數(shù)據(jù)的標簽為1或－1。

4.1 實驗結(jié)果

本文在 UCI數(shù)據(jù)集 haberman、heart、breast這三個數(shù)據(jù)集上進行了實驗，并搭建可視化實驗平臺。在此僅以數(shù)據(jù)集heart為例展示基于MPWPS主動學習的半監(jiān)督分類算法的實驗結(jié)果。運行結(jié)果展示如圖2所示。

圖2 結(jié)果顯示界面

4.2 實驗比較

本文將主動學習的思想引入半監(jiān)督學習中，最終完成了基于MPWPS主動學習的半監(jiān)督分類算法，并在3個數(shù)據(jù)集上進行實驗，得到實驗數(shù)據(jù)。為了進一步驗證該算法的有效性，本文將該算法與Tri－training算法進行對比實驗，衡量指標是算法的標注正確率。

本文針對兩種算法在數(shù)據(jù)集上的每一次劃分進行了5次實驗，每一次實驗將訓練集train按劃分比例0.2隨機劃分，得到5組有標記樣本L和無標記樣本U，并對三次劃分共15次實驗的正確率求平均值，見表2。

表2 兩種算法標注正確率對比

通過實驗比較，由表2可以看出，在3個數(shù)據(jù)集上的所有實驗數(shù)據(jù)中，數(shù)據(jù)結(jié)果顯示基于MPWPS主動學習的半監(jiān)督分類算法對測試集數(shù)據(jù)的標注正確率比Tri－training算法高。

5 結(jié)束語

本文實現(xiàn)了基于MPWPS主動學習的半監(jiān)督協(xié)同分類算法，該算法在訓練集較小的情況下也能獲得較高的分類正確率，在UCI公共數(shù)據(jù)集上的實驗驗證了算法的有效性。不足之處在于，若選出的M組最有可能預測錯誤的樣本是無標記樣本集中的邊緣數(shù)據(jù)，那么將這組標記樣本加入有標記樣本集中會造成訓練的過擬和，這將會對分類器的預測精度產(chǎn)生影響，這將是今后需要研究和解決的問題。

［1］X J Zhu.Semi－ supervised learning literature survey.Technical Report TP 1530，University of Wisconsin，Madison，2008.

［2］龍 軍，殷建平，祝 恩，等.選取最大可能預測錯誤樣例的主動學習算法［J］.計算機研究與發(fā)展，2008，45(3):472－478.

［3］鄧 超，郭茂祖.基于Tri－Training和數(shù)據(jù)剪輯的半監(jiān)督聚類算法［J］.軟件學報，2008，19(3):663 －673.

［4］梁吉業(yè)，高嘉偉，常 瑜.半監(jiān)督學習研究進展［J］.山西大學學報(自然科學版)，2009，32(4):528 －534.

［5］周志華，王 玨.半監(jiān)督學習中的協(xié)同訓練風范機器學習及其應用［M］.北京:清華大學出版社，2007:259－275.

［6］Z H Zhou，M Li Tri－ training:Exploiting unlabeled data using three classifiers［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(11):1529 －1541.

［7］王 娜，李 霞.基于監(jiān)督信息特征的主動半監(jiān)督譜聚類算法［J］.電子學報，2010，38(1):172 －176.