武永成

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

在真實世界的許多問題中通常存在大量的未標(biāo)記樣本，但有標(biāo)記樣本則比較少.研究如何利用少量已標(biāo)簽樣本和大量的未標(biāo)簽樣本來提高學(xué)習(xí)性能的半監(jiān)督學(xué)習(xí)(semi－supervised learning)已成為當(dāng)前機器學(xué)習(xí)的重要研究領(lǐng)域之一［1］.在各種半監(jiān)督學(xué)習(xí)算法中，協(xié)同訓(xùn)練算法［2］(co－training)是最流行的一種.在協(xié)同訓(xùn)練過程中，兩個分類器分別從未標(biāo)記樣本中挑選出若干標(biāo)記置信度較高的樣本進行標(biāo)記，并把標(biāo)記后的樣本加入另一個分類器的有標(biāo)記訓(xùn)練集中，以便對方利用這些新標(biāo)記的樣本進行更新.協(xié)同訓(xùn)練的目的是，通過相互提供未知的信息，使得兩個分類器的準(zhǔn)確性都得以提高.研究表明，協(xié)同訓(xùn)練過程中，兩個分類器的差異性越大，則最終協(xié)同訓(xùn)練的效果越好［3］.最初的協(xié)同訓(xùn)練利用的是同一樣本的兩個不同視圖之間的差異性［2］.但在實際應(yīng)用中，很難得到兩個不同的視圖.于是，不需要兩個不同視圖的協(xié)同訓(xùn)練算法被進行了廣泛研究［4－5］.

本文在對現(xiàn)有協(xié)同訓(xùn)練算法中分類差異性分析的基礎(chǔ)上，提出了一種基于分類置信度差異的新的協(xié)同訓(xùn)練算法，.通過在12個UCI數(shù)據(jù)集上實驗證明，該方法取得比具有代表性的協(xié)同訓(xùn)練算法更好的性能.

1 協(xié)同訓(xùn)練算法及其擴展

Bllum和Mitchel使用的co－training［2］要求必須滿足兩個前提條件:①每個視圖必須是充分的，即在每個視圖上學(xué)習(xí)器都可以學(xué)習(xí)得到一個分類器;②在確定類別(class)的前提下，視圖之間是相互獨立的.標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法co－training使用的兩個視圖是自然生成的.如對于電子郵件的分類問題［2］，兩個視圖中一個視圖來自于郵件的頭(email head)，另一個視圖來自于郵件的體(email body)，它們從兩個不同的方面對郵件的特征進行了描述.對于許多實際問題，并不存在上述相互獨立且冗余的視圖，即不滿足Bllum和Mitchell在標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法中提出的兩個前提條件，此時co－training往往達(dá)不到預(yù)期的效果［6］.因此在許多實際應(yīng)用領(lǐng)域，標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法co－training是不能使用的.為了能夠利用標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法，最直接的方法是對單視圖的樣本數(shù)據(jù)進行視圖分割(即:將一個數(shù)據(jù)集合分成兩個數(shù)據(jù)集合)，人工地生成兩個視圖.文獻［6］使用了該視圖分割的方法，它是隨機分割的，它沒考慮標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法中必須滿足的兩個前提條件.Goldman和Zhou首先提出了一種單視圖的協(xié)同訓(xùn)練算法，即statistical co－training［4］.與標(biāo)準(zhǔn)的協(xié)同訓(xùn)練算法不同，它的訓(xùn)練樣本只有一個視圖，但它使用兩個不同的監(jiān)督算法，一個是ID3(一種常見的決策樹分類算法)，另一個是HOODG(一種構(gòu)造決策圖的算法).ZHOU Zhi－h(huán)ua等提出的tri－training［7］算法是通過增加集成的思想，將co－training算法進行擴展.該算法采用3個分類器進行學(xué)習(xí)，采用投票方式，如果2個分類器對無標(biāo)記數(shù)據(jù)進行預(yù)測的結(jié)果一致，則將它加入第3個分類器的有標(biāo)記樣本集合進行訓(xùn)練.tri－training算法的最大特點是不需計算分類時的概率.在算法 co－fores［8］中，ZHOU Zhi－h(huán)ua等對 tri－training進行擴展.分類器的個數(shù)為N(N≥3)，分類的準(zhǔn)確性對于Tri－training來說，有所提高.隨之帶來的問題是，因為采用投票(majority voting)方式，N個分類器的數(shù)據(jù)逐漸趨于相似，這反過來削弱了分類器的多樣性(the diversity of classifiers).為保持分類器的多樣性，co－forest中采用了Random Forest［9］集成學(xué)習(xí)方法(ensemble learning)，而沒采用Bagging集成學(xué)習(xí)方法.

2 基于分類置信度差異的協(xié)同訓(xùn)練算法

上述不同協(xié)同訓(xùn)練算法的一個共同點是:它們都利用了協(xié)同訓(xùn)練過程中各個分類器之間的差異性.學(xué)習(xí)過程中分類器之間差異越大，則提供給對方的信息越重要，越能提高最終協(xié)同學(xué)習(xí)的效果.表1對各種協(xié)同訓(xùn)練算法中分類差異性產(chǎn)生方法進行了小結(jié).

表1 各種協(xié)同訓(xùn)練算法中分類差異性產(chǎn)生方法Tab.1 Taxonomy of SSL algoritih ms

本文提出的算法與statistical co－training算法很相似，也是一個視圖，兩種不同的基礎(chǔ)分類算法.但比其更簡單，采用了一種使分類置信度差異性最大的策略，避免了statistical co－training在對無標(biāo)記數(shù)據(jù)標(biāo)記時所做的復(fù)雜的判斷.首先，從無標(biāo)記集合U中隨機選u個無標(biāo)記樣本放在集合M中(這u個數(shù)據(jù)從U中刪除).然后，使用基礎(chǔ)算法1和2，利用有標(biāo)記訓(xùn)練樣本集合L，訓(xùn)練得到兩個分類器h1和h2.利用h1和h2，對集合M中的無標(biāo)記數(shù)據(jù)進行分類，并記下分類的置信度(概率).對于M集合中那些分類類別相同(標(biāo)記相同)、且分類置信度差異最大的無標(biāo)記數(shù)據(jù)，給它們加上新預(yù)測的標(biāo)記，并將它們添加到集合L中，即:使得L集合得到擴充.然后不斷循環(huán)，使得L集合不斷擴大，并在其上訓(xùn)練得到跟好的分類器h1和h2，直到程序規(guī)定的循環(huán)次數(shù)到達(dá)或者是U中的數(shù)據(jù)小于u時，程序結(jié)束.其算法如下.

3 實驗

實驗中用到12個UCI數(shù)據(jù)集［10］.數(shù)據(jù)集的相關(guān)信息如表2所示.這些數(shù)據(jù)集都不滿足標(biāo)準(zhǔn)協(xié)同訓(xùn)練的兩個必要條件.對于每個數(shù)據(jù)集，25%的數(shù)據(jù)作為測試樣本，其余的則作為訓(xùn)練樣本，也就是:L∪U.L∪U組成的訓(xùn)練樣本中，無標(biāo)記數(shù)據(jù)的比例分別設(shè)為80%，60%.循環(huán)次數(shù)K設(shè)為30，M的大小為70，n的值設(shè)為4.采用的基礎(chǔ)訓(xùn)練算法為決策樹算法(J4.8)和樸素貝葉斯(NB).標(biāo)準(zhǔn)協(xié)同訓(xùn)練co－training作為比較算法.由于標(biāo)準(zhǔn)協(xié)同訓(xùn)練需要兩個視圖，隨機地對表2中的數(shù)據(jù)進行了視圖分割，將每個數(shù)據(jù)集分成具有兩個視圖的數(shù)據(jù)集.初始狀態(tài)時的錯誤率是指:沒有利用協(xié)同訓(xùn)練的思想，即根本沒有利用無標(biāo)記數(shù)據(jù)，而直接用基礎(chǔ)算法(NB)在有標(biāo)記訓(xùn)練樣本上訓(xùn)練得到分類器，然后對該分類器進行測試得到的分類錯誤率.最好狀態(tài)時的錯誤率是指:利用協(xié)同訓(xùn)練的思想，即利用有標(biāo)記數(shù)據(jù)和無標(biāo)記數(shù)據(jù)，經(jīng)過協(xié)同訓(xùn)練，得到一個分類器并進行測試得到的分類錯誤率.improve=(initial－best)/initial.實驗的相關(guān)結(jié)果如表3和表4所示.

表2 實驗中用到的UCI數(shù)據(jù)集Tab.2 Enperimental UCI data sets

表3 無標(biāo)記數(shù)據(jù)的比例在80%時，初始狀態(tài)、最好狀態(tài)下的分類錯誤率及相應(yīng)的增長率Tab.3 Test error rates of the initial and best models and the relative improvements of under 80%unlabeling rate

表4 無標(biāo)記數(shù)據(jù)的比例在60%時，初始狀態(tài)、最好狀態(tài)下的分類錯誤率及相應(yīng)的增長率Tab.4 Test error rates of the initial and best models and relative improvemets of under 80%unbabeling rate

從表3和表4看出，協(xié)同訓(xùn)練的方法對于標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法，在不同的無標(biāo)記率下，都有較高的提高率，12個數(shù)據(jù)集上的平均提高率分別為15.24%和15.09%.而且，在80%的無標(biāo)記率下，算法比標(biāo)準(zhǔn)的協(xié)同訓(xùn)練算法在8個數(shù)據(jù)集上的提高率都高;在60%的無標(biāo)記率下，算法比標(biāo)準(zhǔn)的協(xié)同訓(xùn)練算法在9個數(shù)據(jù)集上的提高率都高.實驗中的基礎(chǔ)學(xué)習(xí)算法只用到J4.8和樸素貝葉斯.進一步的研究需在別的基礎(chǔ)學(xué)習(xí)算法如人工神經(jīng)網(wǎng)絡(luò)和KNN(k－nearest neighbors classifier)等上展開.但總的來說，本文提出的基于分類差異性最大化的協(xié)同訓(xùn)練算法在解決半監(jiān)督問題上是有效的.

4 結(jié)束語

協(xié)同訓(xùn)練是半監(jiān)督學(xué)習(xí)中的一個熱點.協(xié)同訓(xùn)練的本質(zhì)是利用各個分類器之間的差異性進行相互學(xué)習(xí)，從而提高性能.論文分析了各種協(xié)同訓(xùn)練算法差異性的不同點，提出了一種基于分類置信度差異性的協(xié)同訓(xùn)練算法.實驗驗證了算法的有效性.半監(jiān)督學(xué)習(xí)協(xié)同訓(xùn)練過程中，隨著訓(xùn)練不斷進行，自動標(biāo)記示例中的噪音會不斷積累，其負(fù)作用會越來越大.如何發(fā)現(xiàn)和處理這些噪音數(shù)據(jù)，將有待進一步研究.

［1］周志華.機器學(xué)習(xí)及其應(yīng)用［M］.北京:清華大學(xué)出版社，2007:259－275.

［2］Blum A，Mitchell T.Combining labeled and unlabeled data with co－training［C］//Proc of the 11th Annual Conf.on Computational Learning Theory(COLT 1998).Morgan Kaufmann，1998，pp.92－100.http://citeseer.ist.psu.edu/article/blum98combining.html.

［3］Zhou Z H，Li M.Semi－supervised learning by disagreement［J］.Knowl Inf Syst，2010，24(3):415－439.

［4］Goldman S，Zhou Y.Enhancing supervised learning with unlabeled data［C］//Proceedings of the 17th International Conference on Machine Learning，2000:327－334.

［5］Zhou Y，Goldman S.Democratic co－learning［C］//Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence(ICTAI’04)，2004:594－202.

［6］Nigam K，Ghani R.Analyzing the effectiveness and applicability of co－training［C］//Proc of the 9th Int.Conf.on Information and Knowledge Management.New York:ACM，2000:86－93.

［7］Zhou Z H，Li M.Tri－Training:Exploiting unlabeled data using three classifiers［J］.IEEE Trans On Knowledge and Data Engineering，2005，17(11):1529－1541.

［8］Li M，Zhou Z H.Improve computer－aided diagnosis with machine learning techniques using undiagnosed samples［J］.IEEE Trans Syst Man Cybern，2007，37(6):1088－1098.

［9］韓家煒.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京:機械工業(yè)出版社，2004.

［10］Blake C，Keogh E，Merz C J.UCI repository of machine learning databases［http://www.ics.uci.edu/?mlearn/MLRepository.html］，Department of Information and Computer Science，University of California，Irvine，CA，1998.