基于成對(duì)約束的半監(jiān)督選擇性聚類集成

皋 軍, 黃欣辰, 邵 星

(1.江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 鎮(zhèn)江 212003)(2.鹽城工學(xué)院 信息工程學(xué)院, 鹽城 224002)

聚類分析的目的是依據(jù)對(duì)象之間的相似度將數(shù)據(jù)對(duì)象分組,使得簇內(nèi)對(duì)象相似度盡量高,而簇間對(duì)象相似度盡量低,簇內(nèi)相似性越大,簇間差別越大,聚類就越好[1].常用的聚類分析方法分為:基于劃分的聚類方法[2],將數(shù)據(jù)對(duì)象集劃分成不重疊的簇,使得每個(gè)數(shù)據(jù)對(duì)象僅在一個(gè)簇中;基于層次的聚類方法[3],允許簇有子簇,嵌套簇的集群,組織成一棵樹(shù);基于密度的聚類方法[4],將高密度與低密度區(qū)域分離來(lái)進(jìn)行分類;譜聚類方法[5],依據(jù)譜圖理論將聚類問(wèn)題轉(zhuǎn)化為圖劃分問(wèn)題.

單個(gè)的聚類方法不能產(chǎn)生令人滿意的結(jié)果,因此促進(jìn)了聚類集成的研究. 文獻(xiàn)[6]將多個(gè)不同的聚類結(jié)果進(jìn)行合并,從而獲得比傳統(tǒng)聚類算法更好的聚類結(jié)果. 作為傳統(tǒng)聚集算法的重要擴(kuò)展,聚類集成能取得更加優(yōu)越的聚類結(jié)果,且在處理數(shù)據(jù)樣本時(shí)采用并行的方式進(jìn)行合并,但缺點(diǎn)是若產(chǎn)生了結(jié)構(gòu)不同的初始聚類成員,因此如何取舍對(duì)最終的聚類結(jié)果產(chǎn)生極大的影響[7]. 文獻(xiàn)[8]提出了聚類集成選擇(Cluster Ensemble Selection)的思想,即從初始聚類成員集中選擇滿足某些規(guī)則的部分聚類成員用于集成,進(jìn)而產(chǎn)生最終聚類結(jié)果，該方法可以選擇出差異度大的聚類成員參與集成,以確保最終聚類結(jié)果質(zhì)量.

目前聚類集成和聚類集成選擇技術(shù)的研究主要集中在無(wú)監(jiān)督學(xué)習(xí)領(lǐng)域中,沒(méi)有考慮到用戶或者專家提供的先驗(yàn)知識(shí). 半監(jiān)督聚類集成將少量帶有標(biāo)簽的數(shù)據(jù)帶入到聚類集成中,監(jiān)督與指導(dǎo)集成過(guò)程,最終會(huì)獲得更加優(yōu)越的聚類結(jié)果,使得整個(gè)過(guò)程更具穩(wěn)定性、準(zhǔn)確性和魯棒性[9-11].文獻(xiàn)[12]提出了一種基于成對(duì)約束的判別型半監(jiān)督聚類分析算法,利用成對(duì)約束和線性判別分析對(duì)數(shù)據(jù)同時(shí)進(jìn)行聚類和降維,并在算法目標(biāo)函數(shù)中增加懲罰項(xiàng)，以解決約束違反問(wèn)題,取得了滿意的聚類結(jié)果.

與現(xiàn)有聚類集成算法不同,文中將選擇聚類與半監(jiān)督聚類結(jié)合,首先通過(guò)基于成員質(zhì)量和差異度的選擇方法選出一部分初始聚類成員[13],然后借鑒半監(jiān)督聚類集成的關(guān)鍵思想,利用成對(duì)約束等先驗(yàn)知識(shí),將半監(jiān)督信息帶入到選擇聚類集成過(guò)程,選擇出最終聚類成員集,設(shè)計(jì)了一種半監(jiān)督選擇聚類集成方法(semi-supervised selective cluster ensemble,SSCES). 并在多組基準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),表明SSCES能夠提升聚類質(zhì)量,取得更好的聚類結(jié)果.

1 相關(guān)技術(shù)介紹

選擇性聚類集成是在傳統(tǒng)聚類集成的框架上[6],增加了聚類成員選擇的步驟. 一般分為3步：第一步，聚類成員生成輸入數(shù)據(jù)集,運(yùn)行常用聚類分析算法,輸出聚類成員集P={p1,p2,…,pH};第二步,聚類成員選擇將輸入聚類成員集P,對(duì)聚類成員進(jìn)行選擇,得到集成成員集P′={P′1,P′2,…,P′k};第三步，共識(shí)函數(shù)設(shè)計(jì)輸入集成成員集P′,對(duì)集成成員集進(jìn)行融合,輸出最終結(jié)果Pf.

1.1 聚類成員生成

常用的聚類成員生成方法有以下幾種：第一種方法是對(duì)原始數(shù)據(jù)集進(jìn)行處理,如對(duì)數(shù)據(jù)集采用不同的采樣方法得到多個(gè)樣本數(shù)據(jù)集；第二種方法是輸入不同的輸入特征,如設(shè)置不同的k值；第三種方法是對(duì)同一數(shù)據(jù)集多次執(zhí)行同一種算法,由于選擇的初值不同,可以獲得不同的聚類結(jié)果[14].

因?yàn)閗-means算法簡(jiǎn)單、實(shí)用,且對(duì)初始化、參數(shù)及其特征的變動(dòng)極為敏感. 一般選擇k-means算法作為聚類成員的生成算法. 假設(shè)有N個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集X={x1,x2,…,xN},令k值固定,通過(guò)隨機(jī)化初始聚類中心來(lái)得到初始聚類成員pi(i=1,2,…,H).運(yùn)行H次,得到聚類成員集P={p1,p2,…,pH}.

1.2 基于質(zhì)量和差異度的聚類成員選擇

聚類成員選擇的目的是為了從聚類成員集中選出部分聚類成員組成集成成員集P′={P′1,P′2,…,P′k}.使用適用的成員選擇方法,選出差異度大的聚類成員參加聚類集成,能夠使聚類集成質(zhì)量提高.文獻(xiàn)[15]設(shè)計(jì)了一種聯(lián)合聚類質(zhì)量和差異度的聚類成員選擇方法，該方法使用聚類評(píng)價(jià)指標(biāo)對(duì)聚類成員進(jìn)行評(píng)價(jià),然后按照評(píng)價(jià)結(jié)果的高低排序,選擇出質(zhì)量好且差異度大的聚類成員參與集成,很好地降低了劣質(zhì)成員的影響.

其中聯(lián)合聚類質(zhì)量和差異度的目標(biāo)函數(shù)為:

SE(Pi)=αQi+(1-α)Di

(1)

式中：α為平衡因子,滿足0<α<1,α值默認(rèn)為0.5;Qi為聚類成員集P中第i個(gè)聚類成員的質(zhì)量；Di為聚類成員集P中第i個(gè)聚類成員的的差異度.SE值越大,聚類成員質(zhì)量越好,差異度越大.

1.3 共識(shí)函數(shù)設(shè)計(jì)

共識(shí)函數(shù)Γ可以定義為RN×H→RN的函數(shù),即將多個(gè)聚類成員融合得到最終聚類結(jié)果：

Γ:{pi|i∈{1,2,…,H}}→Pf

(2)

文獻(xiàn)[16]提出了一種基于譜聚類的聚類集成算法,該方法實(shí)現(xiàn)簡(jiǎn)單,聚類結(jié)果穩(wěn)定,不存在局部極值問(wèn)題. 聚類成員選擇出來(lái)的前K個(gè)聚類成員形成一個(gè)N×K的矩陣P′={P′1,P′2,…,P′k}N×K,兩個(gè)數(shù)據(jù)點(diǎn)xi和xj之間的相似性即P′中第i行和第j行的相似性用歸一化互信息(normalized mutual information,NMI)方法來(lái)評(píng)價(jià).

數(shù)據(jù)點(diǎn)xi和xj之間的相似性矩陣S為:

S=(s(xi,xj))N×K

(3)

式中：s(xi,xj)=NMI(P′(i,:),P′(j,:))

求解拉普拉斯矩陣L的最小特征值(λ1,λ2,…,λk)和對(duì)應(yīng)的特征向量(μ1,μ2,…,μk),將特征向量組成的特征空間用F表示.

F=(μ1,μ2,…,μk)N×K

(4)

譜聚類算法將聚類成員映射到特征向量空間F中,對(duì)特征向量空間F使用k-means算法,就能得到最終的聚類結(jié)果Pf.

2 SSCES方法

選擇性聚類集成研究集中在無(wú)監(jiān)督學(xué)習(xí)領(lǐng)域,未考慮到現(xiàn)實(shí)中用戶能通過(guò)某些手段或途徑收集到數(shù)據(jù)的少量真實(shí)信息,因此文中將半監(jiān)督信息添加到選擇聚類集成中,以提高聚類性能. 具體過(guò)程如圖1.

圖1 SSCES算法流程Fig.1 Algorithm flowchart of SSCES

2.1 半監(jiān)督信息的添加

受到文獻(xiàn)[12]的啟發(fā),利用成對(duì)約束的方法來(lái)指導(dǎo)半監(jiān)督信息的添加.

定義1Must-link集合M={(xi,xj)},若(xi,xj)∈M,則表明數(shù)據(jù)xi和xj必屬于同類,即xi和xj滿足正關(guān)聯(lián)約束關(guān)系.

定義2Cannot-link集合C={(xi,xj),若(xi,xj)∈C，則表明數(shù)據(jù)xi和xj必屬于不同類,即xi和xj滿足負(fù)關(guān)聯(lián)約束關(guān)系.

故可用aij來(lái)表示樣本點(diǎn)i和樣本點(diǎn)j之間的相似度:

(5)

即樣本點(diǎn)i和j滿足Must-link約束aij=1，否則aij=0.

根據(jù)公式(5),可以得到包含Must-link約束繼續(xù)的矩陣M和包含Cannot-link約束信息的矩陣C. 矩陣M和矩陣C的維度與數(shù)據(jù)集X的相似性矩陣S相同.

加入半監(jiān)督信息后的相似性矩陣用D表示：

D=S-C+M

(6)

因?yàn)榫仃嘢、M和C的取值范圍都在0～1,所以矩陣D的取值范圍在-1～2之間,因此需要對(duì)矩陣D繼續(xù)優(yōu)化. 若兩個(gè)樣本的相似度大于1則必屬于同一類,相似度取1即可;若兩個(gè)樣本的相似度小于0,1則必屬于不同類,相似度取0即可. 因此用式(7)來(lái)優(yōu)化矩陣D,獲得半監(jiān)督相似性矩陣S′：

(7)

2.2 算法實(shí)現(xiàn)

半監(jiān)督選擇性聚類集成算法(表1)實(shí)現(xiàn)如下:首先選擇簡(jiǎn)單實(shí)用的k-means算法作為基礎(chǔ)算法,生成初始聚類集成成員,將結(jié)果保存在成員集P中；然后根據(jù)聯(lián)合聚類質(zhì)量和差異度的選擇策略,形成集成成員集P′，利用歸一化互信息NMI計(jì)算獲得相似性矩陣S;接著根據(jù)成對(duì)約束原理,獲得約束信息矩陣M和C;輸入相似性矩陣S,得到半監(jiān)督相似性矩陣S′；最后使用譜聚類算法進(jìn)行集成,得到最終聚類結(jié)果.

表1 半監(jiān)督選擇性聚類集成算法Table 1 Semi-supervised selective clustering ensemble

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集和評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)中共選用了9組數(shù)據(jù)集(表2),其中5組UCI數(shù)據(jù)集,2組手寫(xiě)體圖像數(shù)據(jù)集,2組人臉數(shù)據(jù)集. 樣本數(shù)從98～2 500不等,特征數(shù)從4～1 024不等,類別數(shù)從2～40不等.

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental Data Setse

因?yàn)樗x的數(shù)據(jù)集類別標(biāo)簽已知,真實(shí)的類別標(biāo)簽可以為各類評(píng)價(jià)指標(biāo)使用. 實(shí)驗(yàn)采用宏查準(zhǔn)率(Mp)和純度(Pu)兩種常見(jiàn)的聚類性能評(píng)價(jià)指標(biāo)來(lái)判斷聚類效果.

宏查準(zhǔn)率具體公式為:

(8)

式中：k為數(shù)據(jù)集的類別數(shù)；n為數(shù)據(jù)集中對(duì)象的總數(shù)；ai為聚類結(jié)果中正確分到第i個(gè)類的個(gè)數(shù). 顯然Mp值越大,聚類結(jié)果和真實(shí)類別標(biāo)簽越匹配,當(dāng)聚類結(jié)果和真實(shí)類別標(biāo)簽一一對(duì)應(yīng)時(shí),Mp值達(dá)到最大值1.

純度是簇中單個(gè)類的對(duì)象的一種度量方式,反映了算法的簇劃分能力．具體公式為:

(9)

式中：B={B1，B2,…,Bk}為聚類子簇集，Bk為聚類子簇集B中第k個(gè)子簇；C={C1,C2,…,Ci}為真實(shí)類簇集,Ci為真實(shí)類簇集C中第i個(gè)類別；n為數(shù)據(jù)集C數(shù)據(jù)總數(shù)；純度值越接近1,純度越高,聚類效果越好.

3.2 實(shí)驗(yàn)設(shè)計(jì)

通過(guò)實(shí)驗(yàn)驗(yàn)證提出的SSCES算法能否取得較好的聚類效果. 實(shí)驗(yàn)分為兩個(gè)部分：第一部分測(cè)試所提算法的基本聚類能力,SSCES算法是半監(jiān)督算法,集成過(guò)程中,選擇多少帶標(biāo)簽的數(shù)據(jù)參與集成特別重要，文中選取了比例10%～20%的約束信息進(jìn)行實(shí)驗(yàn)；第二部分與其他聚類集成算法進(jìn)行對(duì)比. 對(duì)比算法包括:無(wú)監(jiān)督聚類集成算法CSPA、HGPA[6],聯(lián)合質(zhì)量和差異度的選擇聚類集成算法JPsel[17],半監(jiān)督聚類集成算法SDPE[11]. 為了實(shí)驗(yàn)具有可對(duì)比性,實(shí)驗(yàn)以k-means算法生成初始聚類成員P={p1,p2,…,pH},作為幾種聚類集成算法的輸入.

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 測(cè)試算法基本聚類能力

UCI數(shù)據(jù)集常用來(lái)測(cè)試聚類算法的聚類效果. 通過(guò)測(cè)試UCI數(shù)據(jù)集的5個(gè)數(shù)據(jù)子集:IRIS數(shù)據(jù)集、lymphography數(shù)據(jù)集、ZOO數(shù)據(jù)集、Ionosphere數(shù)據(jù)集和Segment數(shù)據(jù)集來(lái)表明所提方法的基本聚類能力. 表3為選取10%～20%的有標(biāo)簽數(shù)據(jù)時(shí),得到的成對(duì)約束數(shù)量.表4為SSCES算法分別在10%、12%、14%、16%、18%、20%不同比例有標(biāo)簽數(shù)據(jù)下的Mp值(算法用SSCES1、SSCES2、SSCES3、SSCES4、SSCES5、SSCES6表示). 表5為SSCES算法在不同比例有標(biāo)簽數(shù)據(jù)下的Pu值.為了更直觀的將算法不同比例下的Mp值和Pu值進(jìn)行比較,將表4和表5中的數(shù)據(jù)以柱形圖的方式,展現(xiàn)在圖2和圖3中.

從表3、4、5，圖2和3可以得到出:

(1) 表3顯示隨著帶標(biāo)簽數(shù)據(jù)比例的增加,約束信息對(duì)的個(gè)數(shù)也大幅增加,其中負(fù)關(guān)聯(lián)約束個(gè)數(shù)多于正正關(guān)聯(lián)約束對(duì)個(gè)數(shù)

(2) 從表4中可以看出,SSCES算法在實(shí)驗(yàn)所選的5個(gè)數(shù)據(jù)集上的最大Mp值超過(guò)0.420. 在IRIS、ZOO、Ionosphere、Segment等4個(gè)數(shù)據(jù)集上最大Mp值超過(guò)0.620. 表明SSCES算法在這些數(shù)據(jù)集上能取得較好的聚類效果.從表5可以看出SSCES算法在所選5個(gè)數(shù)據(jù)集上的Pu值均超過(guò)0.7, 說(shuō)明算法得到的子簇內(nèi)部類別較為單一,算法具有較好的聚類性能.

(3) 從圖2可以發(fā)現(xiàn),當(dāng)半監(jiān)督比例為10%時(shí),SSCES算法在4個(gè)數(shù)據(jù)集IRIS、lymphography、ZOO、Segment上取得了較高M(jìn)p值. 當(dāng)半監(jiān)督比例為14%時(shí),SSCES算法在IRIS數(shù)據(jù)集上取得了較高M(jìn)p值. 當(dāng)半監(jiān)督比例為20%時(shí),SSCES在數(shù)據(jù)集Ionosphere上可以取得較高值.

(4) 結(jié)合表3和圖2,可以發(fā)現(xiàn)隨著約束信息對(duì)的增加,聚類算法在Ionosphere數(shù)據(jù)集上的Mp值一定值在增加,但在其他數(shù)據(jù)集上不總是在增加.

綜上可以得出,文中所提出的SSCES算法在實(shí)驗(yàn)所選的5個(gè)UCI數(shù)據(jù)集上能取得較好的聚類效果,但隨著約束信息對(duì)的增多,聚類性能不一定得到提升,這可能與過(guò)多的負(fù)關(guān)聯(lián)約束引起的約束違反有關(guān),當(dāng)帶標(biāo)簽的數(shù)據(jù)比例為10%時(shí),所獲得聚類效果最佳.

表3 SSCES算法獲得的約束對(duì)Table 3 Constraint pairs obtained by SSCES algorithm

表4 SSCES算法的宏查準(zhǔn)率Table 4 Micro-p of SSCES algorithm

表5 SSCES算法的純度值Table 5 Purity value of SSCES algorithm

圖2 宏查準(zhǔn)率Fig.2 Micro-p

圖3 純度Fig.3 Purity

3.3.2 與其他聚類算法進(jìn)行對(duì)比

在大容量數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),能更好的驗(yàn)證聚類算法性能. 在大容量數(shù)據(jù)集USPS、MNIST、ORL和Yale上,將文中提出的算法SSCES與CSPA、HGPA、 JPsel、SDPE進(jìn)行比較.

表6為大容量數(shù)據(jù)集上SSCES算法在不同比例參數(shù)下的Mp值.從中可以發(fā)現(xiàn)當(dāng)半監(jiān)督比例參數(shù)為10%時(shí),SSCES算法取得了最高M(jìn)p值.將表6中SSCES算法的最高M(jìn)p值加入到表7中,得到表8，以此驗(yàn)證所提算法的聚類性能.

表6 SSCES算法在大容量數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 6 Results of SSCES algorithm on data sets

表7 其他算法在大容量數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 7 Results of different algorithms on data sets

表8 文中算法與其他算法的結(jié)果比較Table 8 Results of SSCES and other different algorithms

同時(shí)為了更直觀地比較SSCES算法和其他幾種聚類算法的Mp值,將表8中不同聚類算法的Mp值以柱形圖展示在圖4中.

圖4 文中算法與其他算法的結(jié)果比較Fig.4 Results of SSCES and other different algorithms

觀察表8和圖4,可以更直觀的發(fā)現(xiàn):

(1) 在實(shí)驗(yàn)所取得4個(gè)大容量數(shù)據(jù)集上,SSCES、JPsel、SDPE 3種改進(jìn)算法的Mp值都普遍高于傳統(tǒng)的聚類集成算法CSPA和GSPA,在數(shù)據(jù)集USPS、MNIST、Yale上,SSCES算法取得了最高M(jìn)p值. 在數(shù)據(jù)集ORL上,JPsel算法取得了最高M(jìn)p值. 說(shuō)明SCES算法在這些數(shù)據(jù)集上有較好的聚類效果,但無(wú)法保證一定能提升原有模型的聚類效果.

(2) 從圖4可以發(fā)現(xiàn)，SSCES的柱狀圖在大多數(shù)數(shù)據(jù)集上比其他聚類算法更占據(jù)優(yōu)勢(shì),且優(yōu)勢(shì)較為明顯. 說(shuō)明在加入半監(jiān)督信息后,半監(jiān)督選擇聚類集成取得了較好的聚類效果.

總體來(lái)看,SSCES算法相比較傳統(tǒng)的聚類集成算法、選擇性聚類集成算法和半監(jiān)督聚類集成算法更具有優(yōu)勢(shì),在多數(shù)組數(shù)據(jù)集上都獲得了最好的聚類結(jié)果,因此文中提出的半監(jiān)督選擇聚類集成方法能提高選擇性聚類集成的聚類效果.

4 結(jié)論

文中在選擇性聚類集成算法的基礎(chǔ)上,將半監(jiān)督的信息添加到選擇性聚類集成中,提出一種半監(jiān)督選擇性聚類集成方法(SSCES),提高了聚類算法的性能. 實(shí)驗(yàn)結(jié)果表明,基于成對(duì)約束的半監(jiān)督信息加入的SSCES算法能夠改善選擇聚類集成算法的表現(xiàn),在一定條件下,SSCES算法取得的聚類效果優(yōu)于其他聚類集成算法. 同時(shí)實(shí)驗(yàn)也顯示在某些數(shù)據(jù)集上,SSCES算法沒(méi)能取得較高的聚類結(jié)果,起到了相反的作用. 如何消除半監(jiān)督信息添加后帶來(lái)的消極作用,獲得更加優(yōu)越的結(jié)果,將是今后研究的重點(diǎn).