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

武永成

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

在真實世界的許多問題中通常存在大量的未標記樣本，但有標記樣本則比較少.研究如何利用少量已標簽樣本和大量的未標簽樣本來提高學(xué)習(xí)性能的半監(jiān)督學(xué)習(xí)(semi－supervised learning)已成為當前機器學(xué)習(xí)的重要研究領(lǐng)域之一［1］.在各種半監(jiān)督學(xué)習(xí)算法中，協(xié)同訓(xùn)練算法［2］(co－training)是最流行的一種.在協(xié)同訓(xùn)練過程中，兩個分類器分別從未標記樣本中挑選出若干標記置信度較高的樣本進行標記，并把標記后的樣本加入另一個分類器的有標記訓(xùn)練集中，以便對方利用這些新標記的樣本進行更新.協(xié)同訓(xù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)的前提下，視圖之間是相互獨立的.標準協(xié)同訓(xùn)練算法co－training使用的兩個視圖是自然生成的.如對于電子郵件的分類問題［2］，兩個視圖中一個視圖來自于郵件的頭(email head)，另一個視圖來自于郵件的體(email body)，它們從兩個不同的方面對郵件的特征進行了描述.對于許多實際問題，并不存在上述相互獨立且冗余的視圖，即不滿足Bllum和Mitchell在標準協(xié)同訓(xùn)練算法中提出的兩個前提條件，此時co－training往往達不到預(yù)期的效果［6］.因此在許多實際應(yīng)用領(lǐng)域，標準協(xié)同訓(xùn)練算法co－training是不能使用的.為了能夠利用標準協(xié)同訓(xùn)練算法，最直接的方法是對單視圖的樣本數(shù)據(jù)進行視圖分割(即:將一個數(shù)據(jù)集合分成兩個數(shù)據(jù)集合)，人工地生成兩個視圖.文獻［6］使用了該視圖分割的方法，它是隨機分割的，它沒考慮標準協(xié)同訓(xùn)練算法中必須滿足的兩個前提條件.Goldman和Zhou首先提出了一種單視圖的協(xié)同訓(xùn)練算法，即statistical co－training［4］.與標準的協(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個分類器對無標記數(shù)據(jù)進行預(yù)測的結(jié)果一致，則將它加入第3個分類器的有標記樣本集合進行訓(xùn)練.tri－training算法的最大特點是不需計算分類時的概率.在算法 co－fores［8］中，ZHOU Zhi－h(huán)ua等對 tri－training進行擴展.分類器的個數(shù)為N(N≥3)，分類的準確性對于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在對無標記數(shù)據(jù)標記時所做的復(fù)雜的判斷.首先，從無標記集合U中隨機選u個無標記樣本放在集合M中(這u個數(shù)據(jù)從U中刪除).然后，使用基礎(chǔ)算法1和2，利用有標記訓(xùn)練樣本集合L，訓(xùn)練得到兩個分類器h1和h2.利用h1和h2，對集合M中的無標記數(shù)據(jù)進行分類，并記下分類的置信度(概率).對于M集合中那些分類類別相同(標記相同)、且分類置信度差異最大的無標記數(shù)據(jù)，給它們加上新預(yù)測的標記，并將它們添加到集合L中，即:使得L集合得到擴充.然后不斷循環(huán)，使得L集合不斷擴大，并在其上訓(xùn)練得到跟好的分類器h1和h2，直到程序規(guī)定的循環(huán)次數(shù)到達或者是U中的數(shù)據(jù)小于u時，程序結(jié)束.其算法如下.

3 實驗

實驗中用到12個UCI數(shù)據(jù)集［10］.數(shù)據(jù)集的相關(guān)信息如表2所示.這些數(shù)據(jù)集都不滿足標準協(xié)同訓(xùn)練的兩個必要條件.對于每個數(shù)據(jù)集，25%的數(shù)據(jù)作為測試樣本，其余的則作為訓(xùn)練樣本，也就是:L∪U.L∪U組成的訓(xùn)練樣本中，無標記數(shù)據(jù)的比例分別設(shè)為80%，60%.循環(huán)次數(shù)K設(shè)為30，M的大小為70，n的值設(shè)為4.采用的基礎(chǔ)訓(xùn)練算法為決策樹算法(J4.8)和樸素貝葉斯(NB).標準協(xié)同訓(xùn)練co－training作為比較算法.由于標準協(xié)同訓(xùn)練需要兩個視圖，隨機地對表2中的數(shù)據(jù)進行了視圖分割，將每個數(shù)據(jù)集分成具有兩個視圖的數(shù)據(jù)集.初始狀態(tài)時的錯誤率是指:沒有利用協(xié)同訓(xùn)練的思想，即根本沒有利用無標記數(shù)據(jù)，而直接用基礎(chǔ)算法(NB)在有標記訓(xùn)練樣本上訓(xùn)練得到分類器，然后對該分類器進行測試得到的分類錯誤率.最好狀態(tài)時的錯誤率是指:利用協(xié)同訓(xùn)練的思想，即利用有標記數(shù)據(jù)和無標記數(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 無標記數(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 無標記數(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)練的方法對于標準協(xié)同訓(xùn)練算法，在不同的無標記率下，都有較高的提高率，12個數(shù)據(jù)集上的平均提高率分別為15.24%和15.09%.而且，在80%的無標記率下，算法比標準的協(xié)同訓(xùn)練算法在8個數(shù)據(jù)集上的提高率都高;在60%的無標記率下，算法比標準的協(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)練不斷進行，自動標記示例中的噪音會不斷積累，其負作用會越來越大.如何發(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.