閔帆,王宏杰,劉福倫,王軒
在機器學(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)勢更為明顯。
分類問題的基礎(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ù)測標簽
本節(jié)首先描述算法的總體框架,然后進行算法偽代碼描述,最后分析算法復(fù)雜度。
基于集成的半監(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
在訓(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};
為方便討論,假設(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ù)所采用的具體分類算法變化而變化。
本節(jié)通過實驗回答以下3個問題:1) 如何設(shè)置合適的θ閾值;2) SUCE應(yīng)用于哪些基礎(chǔ)算法效果更好;3) 相比于流行的分類算法,SUCE能否提高分類器的精度。
實驗采用了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顯示了 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
本文提出的基于集成聚類的半監(jiān)督二分類算法SUCE解決了樣本過少情況下的分類效果較差的問題。優(yōu)點在于通過集成聚類的學(xué)習(xí)充分挖掘大量未標記樣本中的重要信息,而不需要去求助外界來解決,降低了學(xué)習(xí)的成本。在未來的工作中,進一步研究以下3個方向:1)由目前只能解決二分類問題過渡到多分類問題;2)加入更多學(xué)習(xí)能力強的聚類算法,擴大集成學(xué)習(xí)個體學(xué)習(xí)器的規(guī)模;3)引入代價敏感,增強集成學(xué)習(xí)的能力。