SUCE：基于聚類集成的半監(jiān)督二分類方法

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

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

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

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

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

1 基本概念

分類問題的基礎(chǔ)數(shù)據(jù)為決策系統(tǒng)。

定義1[18]決策系統(tǒng)S為一個三元組：

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

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

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

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

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

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

設(shè)數(shù)據(jù)集U=Ut∪Ur，對于任意聚類學(xué)習(xí)器類結(jié)果，其中表示xi∈Ur的真實標簽。

那么基學(xué)習(xí)器C對于Ur的聚類純度可表示為

另外，聚類集成學(xué)習(xí)存在一個必須要解決的問題：簇標簽與真實標簽的對應(yīng)。

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

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

2 算法設(shè)計與分析

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

2.1 算法總體方案

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

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

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

2.2 算法描述

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

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

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

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

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

SUCE：基于集成聚類的半監(jiān)督分類算法

算法 SUCE

輸入 訓(xùn)練集Ur，測試集Ut，閾值；

輸出 Ut的類標簽向量。

優(yōu)化目標：最大化分類精度；

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

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

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 //擴充訓(xùn)練集

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

24）Ur∪{x'};

25）Ut-{x};

2.3 復(fù)雜度分析

為方便討論，假設(shè)訓(xùn)練集Ur的對象數(shù)量為n，條件屬性數(shù)量為c，測試集Ut的對象數(shù)量為m?；鶎W(xué)習(xí)器數(shù)量為|E|， 迭代次數(shù)為t、聚類簇數(shù)為k。SUCE算法細分為以下4個階段。

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

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

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

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

3 實驗及分析

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

3.1 實驗設(shè)置

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

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

表 1 數(shù)據(jù)集的描述Table 1 Description of the data set

3.2 實驗結(jié)果與分析

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

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

通過表2可以統(tǒng)計發(fā)現(xiàn)，SUCE獲勝14次，打平5次，失敗5次。在Sonar、Wdbc和Ionosphere數(shù)據(jù)集上的分類效果要優(yōu)于基礎(chǔ)算法。但SUCE在Voting數(shù)據(jù)集上對基礎(chǔ)算法分類效果的提升不明顯。

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

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

現(xiàn)在可以回答本節(jié)提出的問題。1)取為0.8左右較合適；2) SUCE應(yīng)用于ID3、C4.5、OneR等基礎(chǔ)算法效果更好；3)相比基礎(chǔ)算法，SUCE通?？梢蕴岣叻诸惼鞯木?。

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

4 結(jié)束語

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