SUCE：基于聚類集成的半監督二分類方法

閔帆，王宏杰，劉福倫，王軒

在機器學習[1]領域中，半監督學習[2-3]和集成學習[4]是當前的研究熱點。它們被廣泛應用于智能信息處理[5]、圖像處理[6]、生物醫學[7]等領域。在許多大數據場景中，樣本屬性的獲取容易且廉價，而其標簽的獲取則困難且昂貴[8]。如果只使用少量已標記樣本進行學習，那么訓練得到的分類模型通常會造成過度擬合[9]。為此，Merz等[10]于1992年提出半監督分類，它不依賴外界交互，充分利用未標記樣本，有效提高分類模型的穩定性和精度。

集成學習是指先構建多個學習器，再采用某種集成策略進行結合，最后綜合各個學習器的結果輸出最終結果。集成學習中的多個學習器可以是同種類型的弱學習器，也可以是不同類型的弱學習器，基于這些弱學習器進行集成后獲得一個精度更高的“強學習器”[11-12]。

基于聚類的分類算法是指先進行數據聚類[13]，然后根據類簇和標簽信息進行分類。其優點是需要的標簽較少，但單一算法的聚類效果不穩定或不符合類標簽分布時，分類效果受到嚴重影響。2002年Strehl等[14]提出“聚類集成”，使用不同類型的聚類算法構造不同的學習器，結合這些學習器可得到更可靠更優的聚類結果；Fred等[15]提出通過對同一種聚類算法選取不同參數來構造學習器；Zhou[16]利用互信息設定權重，采用基于投票、加權投票進行聚類集成學習；Zhang[17]提出一種無標簽數據增強集成學習的方法UDEED，能夠同時最大化基分類器在有標簽數據上的精度和無標簽數據上的多樣性。

本文針對名詞型數據分類問題，在半監督學習的框架之下，融合聚類和集成學習技術，提出一種新的半監督分類算法(semi-supervised binary classification based on clustering ensemble，SUCE)。通過在UCI 4個數據集上的實驗表明，該方法比傳統的ID3、kNN、C4.5等算法的分類效果要好。而且，當標簽較少時，其分類優勢更為明顯。

1 基本概念

分類問題的基礎數據為決策系統。

定義1[18]決策系統S為一個三元組：

式中：U是對象集合也稱為論域；C是條件屬性集合；d是決策屬性。本文只研究名詞型數據的二分類問題，所以決策屬性只有兩個屬性值即|Vd|=2。一般假設所有的條件屬性值已知，而僅有部分樣本決策屬性值已知。這些對象構成了訓練集Ur，而Ut=U–Ur構成了測試集。實際上，在半監督學習中，測試集的對象也參與了訓練模型的構建。

聚類問題不涉及決策屬性d。聚類集成是指關于一個對象集合的多個劃分組合成為一個統一聚類結果的方法，目標就是要尋找一個聚類，使其對于所有的輸入聚類結果來說，盡可能多地符合[19]。

圖1 聚類集成過程示意圖Fig. 1 The diagram of clustering ensemble

集成學習中，學習器之間的差異性被認為是影響集成結果的關鍵因素之一[20]。聚類集成的第一步是通過不同類型聚類基學習器產生多個聚類結果，從不同的方面反映數據集的結構，有利于集成[21]。在本文中，k-Means[22]、EM[23]、Farthest-First[24]和HierarchicalClusterer[25]4個聚類算法將作為聚類集成的基礎學習算法，并且每次運行都設置不同的參數。k-Means原理簡單運行速度較快，但依賴于初始參數設置使得聚類結果存在不穩定性，并且不能有效針對非凸形狀分布數據聚類。EM不需要事先設定類別數目，計算結果穩定、準確，但算法相對復雜，收斂較慢不適用于大規模數據集和高維數據。HierarchicalClusterer沒有任何目標函數，簇合并后不可逆轉，將局部最優作為全局最優解，聚類結果依賴于主觀獲得。FarthestFirst在迭代過程中減少待聚類樣本數和類別數，具有精簡聚類結果的效果。每個算法各有優劣，適用的場景不同；因此需要對它們進行集成化來實現優勢互補。因為本文只研究名詞型數據的二分類問題，所以在聚類時，聚簇的數量直接設為類別數量，在實驗中，本文將所有聚類算法的聚簇數量設定為2。

聚類效果的主要評價指標有JC系數、FM指數、DB指數和DI指數等。本文通過聚類方法研究二分類問題，使用Ur的聚類純度對聚類結果進行評估。通常來說，聚類純度越高則表明聚類效果越好。

定義2 聚類純度(purity of cluster, PC)

設數據集U=Ut∪Ur，對于任意聚類學習器類結果，其中表示xi∈Ur的真實標簽。

那么基學習器C對于Ur的聚類純度可表示為

另外，聚類集成學習存在一個必須要解決的問題：簇標簽與真實標簽的對應。

本文用t(x)和d'(x)分別表示樣本x∈Ut的聚類標簽和預測標簽。θ是用戶設置的閾值，當PC(Ur)＞θ時，即表示聚類標簽與類標簽相匹配，將調用normal(Ut)函數，并直接把聚類標簽作為預測標簽；當PC(Ur)＞θ時，即表示聚類標簽與類標簽相反，將調用covert(Ut)函數，把聚類標簽取反后作為預測標簽；當PC(Ur)介于1?θ和θ之間，即認為聚類結果不適于指導標簽預測，調用reset(Ut)函數，用?1表示x∈Ut的預測標簽。

例2 采用與例1中相同的Ut和Ur，且|=3，若C1的預測標簽，若C2的預測標簽

2 算法設計與分析

本節首先描述算法的總體框架，然后進行算法偽代碼描述，最后分析算法復雜度。

2.1 算法總體方案

基于集成的半監督分類方法主要是通過集成學習控制無標記樣本的標注過程來減少未標記的不確定性[12]。然而，目前在利用集成學習輔助半監督學習方面的方法研究較少，主要是存在如下矛盾：半監督學習適用于標記樣本不足的情況，然而傳統的集成學習本身就需要大量的標記樣本進行訓練[12]。針對上述問題，SUCE綜合聚類集成與半監督學習，在已知標簽較少的情況下，有效提高分類器的精度。

如圖2所示，基于聚類集成的半監督分類過程為：第1個分圖說明，首先通過聚類集成，將B中部分沒有類別樣本C的類標簽預測出來；達到“擴大”有類別的樣本集合(A變成了A+C)，“縮小”了未標記類別集合(B變成了B')。第2個分圖說明，對于擴大后的集合(A+C)利用分類模型，完成預測沒有類別的樣本B'。

圖2 基于聚類集成的半監督分類示意圖Fig. 2 The diagram of semi-supervised classification based on clustering ensemble

2.2 算法描述

在訓練階段，本算法將依次對數據集進行4步處理，從而生成分類器：

1) 通過getLabel(Ur)獲取訓練集Ur的標簽。然后，利用remove(Ur)對Ur去標簽得到Ur′；并將 Ur′∪Ut得到無標簽 U。

2) 通過多個基于 EM、K-Means、Farthest-First和HierarchicalClusterer等聚類算法的個體學習器對U進行全局聚類。根據已獲取的，計算第i個聚類學習器在Ur上的聚類純度PC(i)。如果PC(i)高于閾值θ，將繼續參加集成學習，并將移入到學習器集合E中即E∪。

3) 對測試集的預測標簽進行集成學習。通過h(x)一致性函數依次對測試集每個樣本x∈Ut的預測標簽進行一致性處理。如果E中所有學習器對x的預測標簽均一致，將預測標簽d'(x)賦給x得到x'=(x, d'(x))。x'移入到訓練集Ur∪{x'}，同時在測試集中將其刪除Ut-{x}。

4) 對擴大規模后的Ur進行學習，再對縮減規模后的Ut進行分類=classifier(Ur, Ut)得到Ut的類標簽；然后，獲取Ur的標簽=getLabel(Ur)。最終得到U類標簽=combine(,)。

SUCE：基于集成聚類的半監督分類算法

算法 SUCE

輸入 訓練集Ur，測試集Ut，閾值；

輸出 Ut的類標簽向量。

優化目標：最大化分類精度；

1）U=?，E=?；//初始化

9）for (i=0; i＜4; i++) do //篩選基學習器

10） if (PC(i)＞θ) then

12）end if

13）end for

14）for (each x∈Ut) do //標簽一致性處理

17）else then

19）end if

20）end for

21）for (each x∈Ut) do //擴充訓練集

23）x'=(x, d'(x))

24）Ur∪{x'};

25）Ut-{x};

2.3 復雜度分析

為方便討論，假設訓練集Ur的對象數量為n，條件屬性數量為c，測試集Ut的對象數量為m。基學習器數量為|E|， 迭代次數為t、聚類簇數為k。SUCE算法細分為以下4個階段。

1) 對數據集進行去標簽化預處理。在隱藏Ur類標簽之前，需先記錄其真實類標簽，如第2)行所示再隱藏Ur中的類標簽，如第(3)行所示。至此，需要對Ur進行兩次遍歷，共執行2n次計算。接下來是合并去標簽后的Ur和Ut，構建無標簽論域U。第1階段，計算機將共執行3n+m次運算，故該階段的時間復雜度為O(n+m)。

2) 分別通過基于 K-Means、EM、Farthest-First和HierarchicalClusterer基學習器對U進行全局聚類，如第5)～8)行所示。其時間復雜度分別為 O(kt(n+m))、O(ct(n+m))、O(k(n+m))、O((n+m)2lg(n+m))，然后計算基學習器的聚類純度，并對其進行篩選，共執行n×|E|次運算，如第9)～13)行所示。

3) 對Ut中的對象進行一致化處理。遍歷Ut中對象，共執行m次處理，如第14)-20)行所示。然后將Ut中置信度高的對象移入到Ur，如第21)～27)行所示，共執行2m次計算，故時間復雜度為O(m)。

4) 對擴展后的Ur進行學習，并對Ut進行分類。該階段的時間復雜度根據所采用的具體分類算法變化而變化。

3 實驗及分析

本節通過實驗回答以下3個問題：1) 如何設置合適的θ閾值；2) SUCE應用于哪些基礎算法效果更好；3) 相比于流行的分類算法，SUCE能否提高分類器的精度。

3.1 實驗設置

實驗采用了UCI數據庫中的Sonar、Iono-sphere、Wdbc和 Voting4個數據集。Sonar、Wdbc是連續型數據，因此通過Weka應用默認方法對其進行離散化處理。

根據UCI數據集的樣本數量，實驗設置的訓練集規模分別為2%、4%、6%、8%、10%、12%、14%和16%。在測試集中，樣本標簽不可見，直到所有的未分類樣本都得到預測標簽。為減小實驗隨機誤差，每個結果均為200次相同實驗的平均值。所有(對比)實驗均采用上述相同的實驗參數，如表1所示。

表 1 數據集的描述Table 1 Description of the data set

3.2 實驗結果與分析

圖3顯示了 Sonar、Wdbc、Ionosphere和 Voting數據集在不同閾值θ和訓練集規模下的平均分類精度變化。通過實驗數據觀察發現，θ=0.8左右時，SUCE在4個數據集上均能取得最好的分類效果。在Sonar和Voting數據集上，對于不同的θ取值，隨著訓練集規模的擴大，平均分類精度會呈現出先增加后趨于穩定的趨勢。因為隨著閾值θ的提高，篩選過后還保留的個體學習器通常會變得更少，所以獲得的樣本標簽并沒有提高，從而導致分類效果沒有提升。對于Ionosphere和Wdbc，訓練集規模并不太影響平均分類精度。

表2顯示了SUCE作用在ID3、J48、Bayes、kNN、Logistic、OneR等基礎算法上，并對Sonar、Wdbc、Ionosphere和Voting數據集進行半監督分類的分類結果。實驗參數設置為：θ=0.8，訓練集比例=4%。Win值的計算如下：在某一數據集上，如果某種算法效果比其對比算法精度高1%以上，則該算法得1分；否則兩種算法效果相當且均不得分。

通過表2可以統計發現，SUCE獲勝14次，打平5次，失敗5次。在Sonar、Wdbc和Ionosphere數據集上的分類效果要優于基礎算法。但SUCE在Voting數據集上對基礎算法分類效果的提升不明顯。

SUCE更適用于ID3、C4.5、OneR等基礎算法。例如，在Sonar數據上，SUCE-C4.5獲得了高達14%的精度提升。然而，SUCE對Naive Bayes算法的改進不明顯。

圖3 SUCE-ID3在不同數據集上的分類比較Fig. 3 The diagram of comparison of SUCE-ID3 classification on different datasets

現在可以回答本節提出的問題。1)取為0.8左右較合適；2) SUCE應用于ID3、C4.5、OneR等基礎算法效果更好；3)相比基礎算法，SUCE通常可以提高分類器的精度。

表 2 SUCE與基礎算法分類精度對比Table 2 Comparing the classification accuracy of SUCE and basic algorithms

4 結束語

本文提出的基于集成聚類的半監督二分類算法SUCE解決了樣本過少情況下的分類效果較差的問題。優點在于通過集成聚類的學習充分挖掘大量未標記樣本中的重要信息，而不需要去求助外界來解決，降低了學習的成本。在未來的工作中，進一步研究以下3個方向：1)由目前只能解決二分類問題過渡到多分類問題；2)加入更多學習能力強的聚類算法，擴大集成學習個體學習器的規模；3)引入代價敏感，增強集成學習的能力。