基于閉包準(zhǔn)則和成對約束的半監(jiān)督聚類算法

向力宏，金應(yīng)華，徐圣兵

（廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院，廣東廣州510520）

聚類分析是數(shù)據(jù)挖掘的重要組成部分，其作為常用的數(shù)據(jù)分析方法被廣泛應(yīng)用于人工智能、模式識別和機(jī)器學(xué)習(xí)領(lǐng)域中。以往的機(jī)器學(xué)習(xí)一般只考慮無標(biāo)簽和有標(biāo)簽兩類課題，使用的方法有無監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)。傳統(tǒng)的聚類分析主要是無監(jiān)督學(xué)習(xí)，如K-means聚類［1］、分層聚類［2］、密度聚類［3］、極大熵聚類［4］等，對于有標(biāo)簽的數(shù)據(jù)往往采用監(jiān)督學(xué)習(xí)方法，如 k-近鄰［5］、決策樹［6］、支持向量機(jī)［7］等。

現(xiàn)實(shí)生活中我們所獲得的數(shù)據(jù)大多是復(fù)雜的，數(shù)據(jù)中不僅包含了未標(biāo)記數(shù)據(jù)，而且還包含了標(biāo)記數(shù)據(jù)，無監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)在對這類數(shù)據(jù)進(jìn)行模式求解的過程中所得到的模型精度一般。因此如何解決樣本數(shù)據(jù)標(biāo)簽不充分所導(dǎo)致的聚類數(shù)據(jù)性能下降問題，是近年來機(jī)器學(xué)習(xí)領(lǐng)域研究的方向之一。半監(jiān)督學(xué)習(xí)算法能夠較好地解決以上問題，該方法能夠利用少量已有樣本數(shù)據(jù)標(biāo)記監(jiān)督信息進(jìn)行分類。

現(xiàn)有的半監(jiān)督聚類形式一般通過兩種先驗(yàn)信息來指導(dǎo)算法聚類，即標(biāo)記信息和成對約束信息，由于標(biāo)記信息能夠轉(zhuǎn)化為成對約束信息，我們將所得到的成對約束信息設(shè)置為半監(jiān)督聚類先驗(yàn)信息來進(jìn)行監(jiān)督聚類。聚類算法通過標(biāo)記信息的引導(dǎo)來推進(jìn)聚類過程的劃分調(diào)整，從而不斷改善聚類效果，這類半監(jiān)督聚類算法已經(jīng)有了大量開創(chuàng)性研究，例如，尹學(xué)松等［8］提出了基于成對約束的判別型半監(jiān)督聚類分析方法解決了高維數(shù)據(jù)計(jì)算性能不足和成對約束的違反問題；肖宇等［9］基于近鄰傳播算法，運(yùn)用標(biāo)簽類數(shù)據(jù)和成對約束數(shù)據(jù)構(gòu)成的相似度矩陣進(jìn)行聚類指導(dǎo)，進(jìn)而提高近鄰傳播方法的聚類性能；王君言等［10］基于DL1圖和KNN圖疊加圖的高光譜圖像半監(jiān)督分類算法，構(gòu)建了空譜信息聯(lián)合的圖框架結(jié)構(gòu)，提高小樣本高光譜圖像自動分類的精度。成對約束信息是一種普遍存在于樣本數(shù)據(jù)之間的相互信息，這對于研究聚類過程具有十分重大的意義。

本文延著向思源等［11］（PD-sSC算法）的研究思路，提出了一種基于閉包準(zhǔn)則的成對約束打包算法（CCPC），該算法解決了聚類過程不受成對約束數(shù)目變大而導(dǎo)致的聚類性能相對下降的問題。在不降低聚類效果的前提下，提出了一種程序改進(jìn)方法，降低了編程難度。實(shí)驗(yàn)結(jié)果表明了CCPC算法的有效性。

1 算法

1.1 構(gòu)建成對約束及閉包

首先對本文所需要的數(shù)學(xué)符號進(jìn)行定義，如表1所示。

表1 CCPC目標(biāo)函數(shù)符號定義

假設(shè)給定樣本集合空間 X=｛xi│xi∈Rd，i=1，2，…，n｝，其中，n 表示樣本點(diǎn)數(shù)，R 為實(shí)數(shù)，d 為樣本維數(shù)。本文所采用的成對約束可分為must-link約束和cannot-link約束，并將所有must-link集合記為ML，所有cannot-link集合記為CL，兩者的定義如下：

定義1 must-link，定義集合ML=｛（xi，xj）│i＜j｝，若兩個樣本滿足（xi，xj）∈ML，則表明xi和xj兩個樣本屬于同一類，也稱xi和xj存在正關(guān)聯(lián)約束關(guān)系。

圖1為成對約束must-link約束示意圖，樣本點(diǎn)用球表示，虛線圍成的區(qū)域樣本為同一類簇，實(shí)心圓分別代表樣本點(diǎn)xi和xj，兩個樣本點(diǎn)之間通過直線連接表示must-link約束，說明xi和xj屬于同一類簇，滿足正關(guān)聯(lián)約束條件。

圖1 must-link約束關(guān)系示意圖

定義2 cannot-link，定義集合CL=｛（xk，xl）│k＜l｝，若（xk，xl）∈CL，則表明xk和xl兩個樣本不屬于同一類，也稱xk和xl存在負(fù)關(guān)聯(lián)約束關(guān)系。

圖2為成對約束cannot-link示意圖，球形所表示的含義與圖1一致，實(shí)心圓分別代表樣本點(diǎn)xk和xl，兩個樣本點(diǎn)之間通過虛線連接表示cannot-link約束，說明兩個樣本點(diǎn)在聚類過程中分別屬于不同的類簇，滿足負(fù)關(guān)聯(lián)約束條件。

圖2 cannot-link約束關(guān)系示意圖

受尹學(xué)松等［8］研究的啟發(fā)，本文先基于must-link約束類對數(shù)據(jù)進(jìn)行打包處理，降低原始數(shù)據(jù)成對約束容量，重新構(gòu)造新的cannot-link約束，使得算法在聚類過程中不會產(chǎn)生違反must-link約束問題，為了便于理解對閉包準(zhǔn)則進(jìn)行如下定義。

定義 3 假設(shè)有 3 個樣本 a1，a2，a3，滿足（a1，a2）∈ML，（a1，a3）∈ML，則（a2，a3）∈ML，此時(shí)稱 a1，a2，a3構(gòu)成的集合為同類閉包，簡稱閉包。類似地，可定義含有任意有限個樣本點(diǎn)的同類閉包。若在某樣本點(diǎn)處沒有must-link約束，此時(shí)可約定該樣本點(diǎn)就是一個獨(dú)立的同類閉包。

定義5設(shè)兩個閉包為A=｛a1，a2，…，aq｝和B=｛b1，b2，…，bp｝。若存在（ai，bj）∈CL，其中ai∈A，bj∈B，則稱A，B為異類閉包。

一旦完成基于must-link約束類的打包，就可以用閉包中心替代整個閉包；若兩個閉包中的樣本點(diǎn)之間存在cannot-link約束，此時(shí)可設(shè)定對應(yīng)的兩個閉包中心之間存在cannot-link約束。如圖3所示，已知兩個閉包｛a1，a2，a3，a4｝和｛b1，b2，b3｝，a，b 分別為閉包中心，其中實(shí)線表示 must-link約束，虛線表示cannot-link約束，黑色節(jié)點(diǎn)為樣本點(diǎn)，白色節(jié)點(diǎn)為閉包中心；此閉包之間存在一對cannot-link約束，即（a1，b1）；打包完成后，可設(shè)定 cannot-link約束（a，b）來表示原始樣本的 cannot-link約束（a1，b1）。

圖3 must-link約束合成及cannot-link約束的閉包轉(zhuǎn)換示意圖

在完成打包操作并更新cannot-link約束后，會得到一組新樣本，記為，其中 nml為樣本量。一般地，nml＜n；另記，更新后的cannot-link約束集合為CL'。

尹學(xué)松等［8］基于數(shù)據(jù)打包操作設(shè)計(jì)了PCBKM聚類算法。經(jīng)過分析和實(shí)驗(yàn)，可知該算法有如下兩方面不足。1）在與PD-sSC算法［1］進(jìn)行實(shí)驗(yàn)對比時(shí)發(fā)現(xiàn)，PCBKM算法在成對約束數(shù)目相對較大時(shí)表現(xiàn)優(yōu)異，但在成對約束數(shù)目較小時(shí)，聚類效果比不上PD-sSC算法。2）PCBKM算法中step-2-（b）步驟對cannot-link約束處理得太過簡單，沒有考慮異類閉包之間可能存在的復(fù)雜的分布形式。若采用step-2-（b）步驟進(jìn)行計(jì)算，不同異類閉包對的選擇會產(chǎn)生不同的聚類結(jié)果。圖4列舉了較復(fù)雜的異類閉包對的分布形式，其中帶編號的白色圓形節(jié)點(diǎn)為閉包中心（新樣本點(diǎn)），虛線表示cannot-link約束，橢圓結(jié)構(gòu)表示計(jì)算過程中可以選擇的異類閉包對。以圖4的第1幅圖為例，存在3對異類閉包配對（1，2），（1，3），（2，3）；當(dāng)用PCBKM算法中step-2-（b）步驟分別處理這三對異類閉包的cannot-link約束時(shí)，三個閉包點(diǎn)｛1，2，3｝都有兩個聚類結(jié)果，此時(shí)可能出現(xiàn)同一閉包點(diǎn)在不同異類閉包的cannot-link約束對下得到不同的聚類結(jié)果。如果想改進(jìn)step-2-（b）步驟中的這點(diǎn)不足，需要充分考慮異類閉包對的分布形式，但是異類閉包對的分布形式不可枚舉，圖4僅列舉了幾類簡單的情況。

圖4 異類閉包選取結(jié)構(gòu)示意圖

為了解決以上兩個問題，本文提出一種基于閉包準(zhǔn)則的成對約束打包算法（CCPC）。

1.2 MEC中熵項(xiàng)的推廣

一般稱經(jīng)典MEC聚類算法［12，14-18］所含的熵項(xiàng)為自信息熵，其僅能刻畫樣本點(diǎn)的內(nèi)部信息，代表樣本點(diǎn)自身的信息。在聚類過程中不僅需要利用樣本內(nèi)部的信息，還需要挖掘利用其外部之間的信息。向思源等［11］引入了功效散度（power-divergence,PD）族，它可度量兩個概率向量之間的距離，概率向量之間相似度越高，對應(yīng)的PD散度越小。具體定義如下：

由定義6可知，PD散度是一族，當(dāng)指標(biāo)p=0時(shí)PD散度也為KL（Kullback-Leibler）散度［19］，即樣本對之間的相對熵。以下給出KL散度的明確定義。

李晁銘等［13］利用相對熵（KL散度）構(gòu)造了CE-sSC聚類算法。PD散度可隨著指標(biāo)p的改變而改變，還可將PD散度推廣到更一般的形式，例如?散度［20］。基于PD散度和相對熵之間的關(guān)系，向思源等［11］在李晁銘等［13］研究成果的基礎(chǔ)上提出了基于PD散度的PD-sSC聚類算法，克服了CE-sSC算法中熵項(xiàng)之間的干擾問題，提高了懲罰系數(shù)的選擇效率。

1.3 目標(biāo)函數(shù)

定義 8 懲罰系數(shù)矩陣 Γ=（Γjk）nml×nml

顯然，Γ為上三角形矩陣，其中所有γjk元素皆為正數(shù)。類似于PD-sSC算法，通過融合懲罰項(xiàng)系數(shù)和PD散度得到目標(biāo)函數(shù)的懲罰項(xiàng)為

1.4 參數(shù)求解

由式（5）可得

將式（8）變形得到

將式（9）代入到式（6）可以得到隸屬度迭代公式為

式（6）～（10）中的參數(shù) aij定義如下

2 算法流程

總結(jié)上述推導(dǎo)，得到CCPC算法的具體流程如下：

輸入原始目標(biāo)數(shù)據(jù)集Y，懲罰系數(shù)矩陣Γ＝（Γjk）nml×nml，初始隸屬度矩陣U(0)，聚類數(shù)c（2≤c≤nml），PD散度指標(biāo)p，算法最大迭代次數(shù)T，終止條件ε。

輸出 最優(yōu)隸屬度矩陣U和聚類中心V。

迭代過程為：

（1）初始化迭代計(jì)數(shù)器t=0；

（2）根據(jù)式（7）和 U(t)計(jì)算出 V(t)；

（3）根據(jù)式（10）和 V(t)更新 U(t)為 U(t+1)；

（4）當(dāng)‖U(t+1)-U(t)‖≤ε或t=T時(shí)，終止算法運(yùn)算；否則，令t=t+1返回到（2）；

（5）算法收斂后，輸出最優(yōu)隸屬度矩陣U和聚類中心V。

以上算法是對打包后的樣本集合Y進(jìn)行聚類分析，在打包規(guī)則的基礎(chǔ)上，可將此聚類分析結(jié)果反射到原樣本集合X上，至此才算完成原樣本組的聚類分析。圖5列出了CCPC算法的基本框架。

圖5 CCPC算法的框架圖

在編程實(shí)現(xiàn)CCPC算法的過程中，對隸屬度向量(10)式進(jìn)行歸一化操作時(shí)，很容易碰到算術(shù)溢出問題，此時(shí)就需要對算法流程加入若干相應(yīng)的控制項(xiàng)，這給編程帶來了難度。為解決這一問題，定義如下的截尾指數(shù)函數(shù)

3 實(shí)驗(yàn)及分析

本文選取6個數(shù)據(jù)集對CCPC算法和其他相關(guān)的聚類算法進(jìn)行實(shí)驗(yàn)比較。

3.1 實(shí)驗(yàn)數(shù)據(jù)與評價(jià)準(zhǔn)則

實(shí)驗(yàn)選取了UCI數(shù)據(jù)庫中的四組常用數(shù)據(jù)集，分別為breast、iris、seeds、wine數(shù)據(jù)，還選取了池塘水質(zhì)評價(jià)水色圖像特征數(shù)據(jù)集X1和用于區(qū)域環(huán)境質(zhì)量狀況評價(jià)的空氣質(zhì)量數(shù)據(jù)集X2作為實(shí)驗(yàn)數(shù)據(jù)。選取以上數(shù)據(jù)集的原因是算法性能檢測的結(jié)果直觀可靠，表2列出了數(shù)據(jù)集的特征描述。

表2 數(shù)據(jù)集的特征

在進(jìn)行實(shí)驗(yàn)之前，對所有數(shù)據(jù)集進(jìn)行中心化與標(biāo)準(zhǔn)化處理，目的是消除量綱差異。本文選擇的對比算法有基于功效散度和成對約束的半監(jiān)督聚類的PD-sS算法［11］、基于成對約束的交叉熵半監(jiān)督聚類的CE-sSC算法［13］、基于成對約束的K均值聚類的PCBKM算法［8］和基于譜圖和成對約束的主動半監(jiān)督聚類 SSC 算法［20］。

實(shí)驗(yàn)對比中采用了三種評價(jià)指標(biāo)：1）準(zhǔn)確率指標(biāo)（Accuracy Cluster，AC）：評價(jià)聚類準(zhǔn)確程度；2）標(biāo)準(zhǔn)互信息指標(biāo)（Normalized Mutual Information，NMI）：衡量兩個數(shù)據(jù)分布的吻合程度；3）蘭德指數(shù)（Rand Index，RI）：評價(jià)算法聚類結(jié)果與真實(shí)情況的吻合程度。以上三種評價(jià)指標(biāo)的取值都在0至1之間，指標(biāo)值越接近1就說明聚類效果越好，使用多個評價(jià)指標(biāo)進(jìn)行對比能夠更加充分地評價(jià)聚類效果。

3.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

實(shí)驗(yàn)前，先采取數(shù)據(jù)清洗操作，然后通過隨機(jī)抽樣方式構(gòu)建成對約束信息，在實(shí)驗(yàn)過程中，忽略數(shù)據(jù)的標(biāo)簽信息。根據(jù)數(shù)據(jù)樣本量和實(shí)驗(yàn)結(jié)果選取成對約束的數(shù)量點(diǎn)，具體信息如下：breast數(shù)據(jù)的成對約束數(shù)目設(shè)置為 20、40、60、80、100、120、140、160、180、200；iris 數(shù)據(jù)成對約束數(shù)目設(shè)置為 10、15、20、25、30、35、40、45、50、55；seeds、X2數(shù)據(jù)的成對約束數(shù)目設(shè)置為 10、20、30、40、50、60、70、80、90、100；wine、X1數(shù)據(jù)的成對約束數(shù)目設(shè)置為 8、16、24、32、40、48、56、64、72、80。進(jìn)行 1 000 次重復(fù)實(shí)驗(yàn)，求得評價(jià)指標(biāo)的平均值，將該平均值當(dāng)作評價(jià)指標(biāo)的估計(jì)值。在實(shí)驗(yàn)中，CCPC算法的實(shí)驗(yàn)參數(shù)為：功效指標(biāo)p=-1，算法迭代終止條件ε=1e-5，最大迭代次數(shù)T=100。圖6～11依次列出了表2中數(shù)據(jù)集的評價(jià)指標(biāo)估計(jì)，其中橫坐標(biāo)為成對約束數(shù)目，每幅圖中的縱坐標(biāo)分別為AC、NMI、RI評價(jià)指標(biāo)估計(jì)值。

圖6 breast數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖7 iris數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖8 seeds數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖9 wine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖10 X1數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖11 X2數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從圖6可看出，CCPC算法對應(yīng)的三個評價(jià)指標(biāo)都是最高的，聚類效果表現(xiàn)最好。由于breast數(shù)據(jù)量相對較大，對比算法的SSC算法運(yùn)算速度不佳，因此在計(jì)算過程中不考慮SSC算法的主動學(xué)習(xí)部分，只研究其半監(jiān)督聚類算法。在成對約束數(shù)目不斷增加的過程中，PD-sSC、CE-sSC和PCBKM算法的三個指標(biāo)值都顯示下降趨勢，其中PCBKM算法的降幅最大，此趨勢是因?yàn)檫x擇了固定的懲罰項(xiàng)系數(shù)，此時(shí)，當(dāng)成對約束數(shù)目增加時(shí)，目標(biāo)函數(shù)中的懲罰項(xiàng)相對比重會增加，從而影響了聚類效果。但CCPC算法評價(jià)指標(biāo)卻基本呈現(xiàn)上升趨勢，圖6～11都有該現(xiàn)象，這是CCPC算法的優(yōu)點(diǎn)，即對懲罰系數(shù)的選擇不敏感，具有抗干擾性。

從圖7可看出，CCPC算法的AC與RI指標(biāo)值都比其他4個算法高，NMI指標(biāo)值也僅次于SSC算法。隨著成對約束數(shù)目的增加，CCPC算法與PCBKM算法的評價(jià)指標(biāo)是單增的，PD-sSC和CE-sSC算法存在明顯的下降趨勢。雖然SSC算法的NMI指標(biāo)值最優(yōu)，但是SSC算法包含兩個對算法影響較大的超參數(shù)，并且算法運(yùn)算時(shí)間較長，因此SSC算法不是最好的選擇。

從圖8可看出，CCPC算法的三個評價(jià)指標(biāo)也是優(yōu)于其他4個算法，且值都高于0.8。當(dāng)成對約束數(shù)目大于30時(shí)，PD-sSC和CE-sSC算法隨著成對約束數(shù)目的增加，聚類性能不斷下降，而CCPC算法保持了與PCBKM算法相近的增加值，該現(xiàn)象說明了閉包準(zhǔn)則能有效提高聚類效果，CCPC算法吸取了PCBKM算法的優(yōu)點(diǎn)。從圖9也可看出，CCPC算法的3個指標(biāo)值都要優(yōu)于其他4個算法，算法性能與seeds數(shù)據(jù)相似，3個指標(biāo)值都大于0.8，進(jìn)一步表明CCPC算法聚類效果最好。

從圖10可看出，當(dāng)成對約束小于32的時(shí)候，除了SSC算法其他4個算法的AC、NMI和RI指標(biāo)值之間差別較小，隨著成對約束數(shù)目的增加，CCPC算法的增長趨勢明顯優(yōu)于其他算法，說明聚類效果優(yōu)于其他4個算法。從圖11可看出，PCBKM算法在X2數(shù)據(jù)中聚類表現(xiàn)最好，當(dāng)成對約束數(shù)目不足時(shí)，PD-sSC和PCBKM算法性能會出現(xiàn)小幅度下降，而當(dāng)成對約束數(shù)目在20至70區(qū)間范圍內(nèi)取值時(shí)，CE-sSC算法優(yōu)于CCPC和PD-sSC算法且三類算法效果都保持遞增趨勢。在接下來不斷增加的過程中，CCPC算法的評價(jià)值也不斷上升。

綜合圖6～11的結(jié)果，可得出CCPC算法有較好的聚類效果。在成對約束數(shù)目增加的情況下，CCPC算法的聚類性能呈現(xiàn)出上升趨勢；一旦成對約束數(shù)目較為充分時(shí)，CCPC算法就能夠給出優(yōu)于其他算法的聚類結(jié)果?？傮w上，可以得出如下結(jié)論：CCPC算法優(yōu)于對比算法。

4 結(jié)語

為解決PD-sSC算法在處理成對約束數(shù)目相對較多時(shí)聚類性能不夠理想的問題，本文提出了基于閉包準(zhǔn)則和成對約束的半監(jiān)督聚類算法（CCPC）。該算法通過引入PCBKM算法中基于must-link約束對樣本進(jìn)行打包的思想，得到了只帶更新了的cannot-link約束的新樣本組，再用PD-sSC算法進(jìn)行聚類分析，最后根據(jù)打包原則將聚類結(jié)果反射到原樣本組上；克服了PCBKM算法在處理cannot-link約束時(shí)的不足；糅合了PD-sSC算法和PCBKM算法的各自優(yōu)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，在成對約束數(shù)目較少時(shí)，CCPC算法在聚類性能上與PD-sSC算法保持一致；在成對約束數(shù)目相對較大時(shí)，CCPC算法在聚類性能上與PCBKM算法保持一致。因此，無論成對約束數(shù)目是大是小，CCPC算法都有不錯的聚類效果。