半監(jiān)督模糊聚類算法的研究與改進(jìn)*

白福均，高建瓴，宋文慧，賀思云

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽(yáng) 550025）

0 引 言

半監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)與模式識(shí)別學(xué)科中的研究熱點(diǎn)。本質(zhì)上來(lái)說(shuō)，它的實(shí)質(zhì)是介于監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)之間的一種學(xué)習(xí)方式。根據(jù)學(xué)習(xí)內(nèi)容，它可以分成三類：半監(jiān)督聚類、半監(jiān)督分類以及半監(jiān)督回歸[1-2]。其中，半監(jiān)督聚類的本質(zhì)是在少量先驗(yàn)信息的幫助下去引導(dǎo)無(wú)監(jiān)督的聚類過(guò)程，從而提高聚類算法的精度。1985年，Pedrycz[3]在研究模糊聚類算法的時(shí)候，已經(jīng)提出了半監(jiān)督聚類，不過(guò)在那時(shí)被稱作“部分監(jiān)督”[4]（Partial Supervision）。然而，近幾年，伴隨著實(shí)際應(yīng)用中的問(wèn)題規(guī)模越來(lái)越大，半監(jiān)督聚類算法再次回歸到學(xué)者研究熱門領(lǐng)域中，很多經(jīng)典的聚類算法被不斷引申到“半監(jiān)督”版本。Blum& Mitchell、Joachims等人提出，當(dāng)待聚類的數(shù)據(jù)集中含有少量的標(biāo)記數(shù)據(jù)但無(wú)法完全分布到所有類別時(shí)，可以采用部分的標(biāo)記信息去引導(dǎo)整個(gè)無(wú)監(jiān)督的算法進(jìn)程，從而提升聚類的準(zhǔn)確度[5]。

一般來(lái)說(shuō)，半監(jiān)督聚類中的先驗(yàn)信息通過(guò)相關(guān)行業(yè)專家的專業(yè)知識(shí)得到，可以分成兩大類，即類別標(biāo)記信息和約束信息。類別標(biāo)記信息是指在還沒(méi)有進(jìn)行聚類時(shí)就已經(jīng)知道了某個(gè)數(shù)據(jù)對(duì)象的類別，而約束信息則在實(shí)際生活中最常見(jiàn)，是指根據(jù)常識(shí)可以清楚知道某兩個(gè)數(shù)據(jù)對(duì)象是否屬于同一類。2000年，Wagstaff提出使用must-Link（正關(guān)聯(lián)）和cannot-Link（負(fù)關(guān)聯(lián)）來(lái)形容這種關(guān)系[6]。

鑒于半監(jiān)督聚類可以有效地使用先驗(yàn)信息，從而能夠取得更好的聚類結(jié)果，很多國(guó)內(nèi)外學(xué)者都進(jìn)行了比較深入的探索和學(xué)習(xí)，也提出了一些代表性算法，如Cop-Kmeans算法[7]、CKS算法[8]、Seeded-Kmeans算法[7]和SAP算法[9]等，也都取得了不錯(cuò)的聚類效果。

可是，在實(shí)際應(yīng)用中，雖然可以獲得含有先驗(yàn)信息的數(shù)據(jù)，但是由于先驗(yàn)信息的獲取需要消耗一定的人力、財(cái)力以及物力，導(dǎo)致含有先驗(yàn)信息的數(shù)據(jù)在整個(gè)數(shù)據(jù)集中所占的比重很小，使得半監(jiān)督聚類算法不能充分有效地利用先驗(yàn)信息指導(dǎo)整個(gè)聚類過(guò)程，導(dǎo)致最終的聚類結(jié)果不是很理想。

本文在對(duì)模糊C均值聚類（FCM）算法和半監(jiān)督模糊C均值聚類（SFCM）算法研究的基礎(chǔ)上，提出通過(guò)調(diào)節(jié)監(jiān)督信息比重來(lái)改進(jìn)SFCM算法——SSFCM算法，使之在先驗(yàn)信息稀少時(shí)，SFCM算法仍然可以充分有效地利用先驗(yàn)信 息，提高聚類性能。

1 半監(jiān)督模糊C均值聚類算法

1.1 模糊C均值聚類算法

1.1.1 FCM算法的基本思想

FCM算法[10-12]是理論知識(shí)最為完善的算法之一，在實(shí)際應(yīng)用中也很常見(jiàn)。從本質(zhì)上來(lái)講，它屬于基于劃分算法的范疇，但它是一種柔性的模糊劃分，是在聚類的基礎(chǔ)上引入了模糊理論，從而利用隸屬度函數(shù)確定某一數(shù)據(jù)對(duì)象的劃分類別。

FCM算法是一種基于目標(biāo)函數(shù)的算法，把含有n個(gè)數(shù)據(jù)對(duì)象的集合X={x1,x2,…,xn}?Rs分為c類，其聚類中心用ci表示，目標(biāo)函數(shù)是：

式中，uij取值在0到1之間，ci表示第i類的聚類中心，dij=||ci-xj||表示第i個(gè)聚類中心ci與第j個(gè)數(shù)據(jù)對(duì)象xj之間的歐幾里德距離，而m∈[1,+∞)是加權(quán)指數(shù)，用來(lái)控制聚類的模糊程度。m值越大，表示模糊程度越大。

在約束條件的約束下，利用Lagrange數(shù)乘法求取式（1）的最小值，得到聚類中心和隸屬度的迭代表達(dá)式如下：

1.1.2 FCM算法的具體步驟

對(duì)FCM算法的具體實(shí)現(xiàn)步驟描述如下。

步驟1：初始化隸屬度矩陣U，保證其值均在0到1之間，并使之符合約束條件；

步驟2：利用式（2）計(jì)算新的聚類中心ci,i=1,…,c；

步驟3：利用式（3）計(jì)算新的隸屬度矩陣U；

步驟4：按照式（1）計(jì)算目標(biāo)函數(shù)，如果它取得最小值或是超過(guò)最大的迭代次數(shù)，則算法結(jié)束，輸出隸屬度矩陣和聚類中心；反之，則返回到步驟2。

1.2 半監(jiān)督模糊C均值聚類算法

1.2.1 SFCM算法的基本思想

SFCM算法把少量的labeled數(shù)據(jù)的類別標(biāo)記當(dāng)作監(jiān)督信息，通過(guò)加入到FCM算法的目標(biāo)函數(shù)，從而在整個(gè)聚類的迭代優(yōu)化進(jìn)程中起到一定的監(jiān)督作用。另外，在隸屬度方面也加入了帶有半監(jiān)督性質(zhì)的表達(dá)式。此時(shí)，SFCM算法的目標(biāo)函數(shù)為：

式中，m表示加權(quán)指數(shù)，是一個(gè)經(jīng)驗(yàn)值，通常取值為2；α(α≥0)表示平衡因子，用來(lái)調(diào)節(jié)式（4）中的無(wú)監(jiān)督信息與監(jiān)督信息彼此間的平衡，其中α的具體值和總樣本數(shù)L與標(biāo)記樣本數(shù)L的比值成正比例關(guān)系；fij為labeled樣本的隸屬度矩陣，其值具體表示為xj歸于ci的程度大小；bj為一個(gè)布爾型的二值向量，按照它的實(shí)際取值可以用來(lái)判斷xj是否是已經(jīng)標(biāo)記的數(shù)據(jù)。bj需要滿足的條件如下：

同樣地，用Lagrange數(shù)乘法對(duì)式（1）所表示的目標(biāo)函數(shù)求解，最終獲得的模糊隸屬度uij和聚類中心vi的迭代表達(dá)式為：

1.2.2 SFCM算法的具體步驟

輸入：需要聚類的數(shù)據(jù)對(duì)象集合X，聚類的類別數(shù)c以及帶有l(wèi)abeled信息的約束集S。

輸出：聚類中心V，隸屬度矩陣U。

（1）首先利用帶有l(wèi)abeled信息的數(shù)據(jù)在集合S中進(jìn)行初始劃分，然后把得到的結(jié)果看作是算法的初始聚類中心；

（2）計(jì)算需要聚類的數(shù)據(jù)集合X和約束集S中所有樣本點(diǎn)與聚類中心的距離，并按照式（5）生成初始隸屬度矩陣；

（3）按照式（4）計(jì)算目標(biāo)函數(shù)。假如它比預(yù)先給定的閾值小，又或者是前后兩次的差小于閾值，那么算法結(jié)束；否則，轉(zhuǎn)到步驟（4）；

（4）按照式（7）計(jì)算更新后的聚類中心，返回步驟（2）。

2 改進(jìn)半監(jiān)督模糊C均值聚類算法

2.1 SSFCM算法的基本思想

在SFCM算法中，隨著監(jiān)督信息的比重增大，算法的聚類性能指標(biāo)也會(huì)更好。但在實(shí)際應(yīng)用中，因?yàn)閘abeled數(shù)據(jù)難以大量獲取，所以先驗(yàn)信息具有稀少性，即|XL|＜|XU|（|XL|代表labeled樣本的數(shù)量，|XU|代表unlabeled樣本的數(shù)量）。這將會(huì)導(dǎo)致SFCM算法的聚類性能降低，和FCM算法相比，體現(xiàn)不出本身的優(yōu)越性。此時(shí)，labeled數(shù)據(jù)的類標(biāo)記信息相對(duì)unlabeled數(shù)據(jù)來(lái)說(shuō)已經(jīng)很稀少，如果仍然僅僅依靠目標(biāo)函數(shù)中的不可避免將忽略labeled數(shù)據(jù)的指導(dǎo)作用。

為了避免出現(xiàn)上述現(xiàn)象，參照文獻(xiàn)[13]，采用把表示labeled數(shù)據(jù)點(diǎn)權(quán)重的參數(shù)放在聚類中心的迭代表達(dá)式的方法，以調(diào)節(jié)監(jiān)督信息的影響力。具體做法是把表示SFCM算法聚類中心的迭代表達(dá)式更改為：

式（6）表示的是SFCM算法中的隸屬度矩陣的迭代公式，因?yàn)闃?biāo)記信息的初始隸屬度矩陣fij滿足0≤fij≤1，且，把式（5）代入，則SFCM算法中的labeled數(shù)據(jù)和unlabeled數(shù)據(jù)的隸屬度矩陣的迭代公式分別變?yōu)椋?/p>

按照式（8），對(duì)聚類中心的迭代表達(dá)式式（7）進(jìn)行修改，相當(dāng)于保持SFCM算法的迭代方式，仍為原樣。另外，對(duì)于隸屬度矩陣的迭代表達(dá)式式（6），根據(jù)式（11）和式（12）對(duì)labeled數(shù)據(jù)和unlabeled數(shù)據(jù)的隸屬度矩陣的權(quán)重做出對(duì)應(yīng)形式的修改：

為了使改進(jìn)算法的隸屬度矩陣和聚類中心的迭代表達(dá)式與SFCM算法的表達(dá)式保持相似，對(duì)于式（12），這里采用1+α替換α。此時(shí)，相對(duì)應(yīng)的式子將變成如下形式：

2.2 SSFCM算法的具體步驟

（1）初始化。設(shè)置聚類個(gè)數(shù)c，平衡指數(shù)α，由標(biāo)記信息計(jì)算給出二值向量b=[ bj]和標(biāo)記信息的初始隸屬度矩陣F=[ fij]。

（2）計(jì)算labeled和unlabeled的所有樣本點(diǎn)與聚類中心的距離；

（3）由式（13）計(jì)算新的隸屬度矩陣U；

（4）由式（14）計(jì)算新的聚類中心V；

（5）本次計(jì)算得出的聚類中心與上次相比；不發(fā)生變化或者滿足迭代次數(shù)超出最大次數(shù)，則算法停止；否則，返回步驟（2）。

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

為了驗(yàn)證本文算法的合理性，選取美國(guó)加州大學(xué)歐文分校提出的UCI數(shù)據(jù)庫(kù)中的Iris數(shù)據(jù)集，使用matlab編程驗(yàn)證及評(píng)估SSFCM算法的聚類性能。

為了便于對(duì)后面實(shí)驗(yàn)的聚類結(jié)果進(jìn)行評(píng)價(jià)，這里引入一個(gè)指標(biāo)RI=n0/n。對(duì)測(cè)試集進(jìn)行實(shí)驗(yàn)后，把得到的分類結(jié)果與標(biāo)準(zhǔn)數(shù)據(jù)集本身分好的類進(jìn)行對(duì)比，計(jì)算得到正確分類的數(shù)據(jù)條數(shù)即為n0，n則為測(cè)試集中數(shù)據(jù)的總條數(shù)。很明顯，由表達(dá)式可知，RI表示的數(shù)值越大，聚類實(shí)驗(yàn)的準(zhǔn)確性越高，即聚類性能越好。

實(shí)驗(yàn)過(guò)程中，分別使用FCM、SFCM和SSFCM算法進(jìn)行測(cè)試比較。為了說(shuō)明實(shí)驗(yàn)結(jié)果的可靠性，F(xiàn)CM、SFCM和SSFCM這3種算法在實(shí)驗(yàn)中均采用歐式距離。另外，SFCM和SSFCM算法的labeled樣本點(diǎn)要選取相同的，數(shù)量均為10個(gè)，且labeled樣本點(diǎn)的初始隸屬度相同。分別利用3種算法依次對(duì)Iris數(shù)據(jù)集測(cè)試，每種算法都測(cè)試10次，最終的測(cè)試結(jié)果如表1所示。

表1 FCM、SFCM、SSFCM算法準(zhǔn)確率 /（%）

根據(jù)表1中10次測(cè)試獲得的正確率，可以繪制如圖1所示的對(duì)比結(jié)果，由其中的折線可以更直觀地觀察分析。

圖1 FCM、SFCM及SSFCM算法對(duì)比

由圖1的3條折線可以清楚看出，F(xiàn)CM算法、SFCM算法和SSFCM算法的準(zhǔn)確率大小依次為：SSFCM算法最大，SFCM算法其次，最后是FCM算法，與理論分析結(jié)果一致。和FCM算法相比，SFCM算法充分利用了labeled數(shù)據(jù)的監(jiān)督信息，而SSFCM算法在整個(gè)聚類的迭代進(jìn)程中不斷更新調(diào)整監(jiān)督信息的比重，所以才會(huì)出現(xiàn)圖1所示的情況。觀察圖中的折線可以清楚看到，F(xiàn)CM算法的準(zhǔn)確率波動(dòng)最大。算法中，除了初始聚類中心，剩下的所有參數(shù)都是固定不變的。所以，可以得到如下結(jié)論：在聚類算法中，初始聚類中心位置的選擇將會(huì)對(duì)整個(gè)聚類結(jié)果的優(yōu)劣起到很大作用。從圖1中也可以看出，SSFCM算法的準(zhǔn)確率和FCM、SFCM算法相對(duì)比更加平穩(wěn)，數(shù)值上也高于FCM和SFCM算法。計(jì)算3種測(cè)試結(jié)果的平均值，得到如圖2所示的柱形圖。

圖2 FCM、SFCM及SSFCM算法平均準(zhǔn)確率對(duì)比

表2從準(zhǔn)確率、迭代次數(shù)和運(yùn)行時(shí)間3個(gè)方面多角度對(duì)比顯示了3種算法的聚類結(jié)果。從運(yùn)行時(shí)間方面來(lái)說(shuō)，SSFCM算法運(yùn)行時(shí)間最少，僅僅用了0.065 s；FCM算法其次，用時(shí)0.188 s；最后是SFCM算法。從迭代次數(shù)方面來(lái)說(shuō)，SSFCM、FCM和SFCM這3種算法的迭代次數(shù)依次增多，和算法的運(yùn)行時(shí)間保持一致。從聚類準(zhǔn)確度方面分析，SSFCM算法達(dá)到最大值，為94.26%；而FCM算法因?yàn)闆](méi)有l(wèi)abeled樣本做指導(dǎo)，聚類的準(zhǔn)確率是3種算法中最小的，為89.33%；SFCM算法居中，為91.12%。綜合來(lái)看，無(wú)論用3個(gè)方面的哪一個(gè)評(píng)價(jià)，SSFCM算法的聚類性能都要優(yōu)于其他3種聚類算法。

表2 FCM、SFCM及SSFCM算法聚類效果對(duì)比

4 結(jié) 語(yǔ)

半監(jiān)督聚類中標(biāo)簽數(shù)據(jù)的獲取需要一定的代價(jià)。所以，在實(shí)際應(yīng)用的數(shù)據(jù)集中，標(biāo)簽數(shù)據(jù)的量都是比較少的，此時(shí)SFCM算法并不能很好地體現(xiàn)它的優(yōu)勢(shì)。因此，本文重新定義了SFCM算法的迭代公式，把表示labeled數(shù)據(jù)點(diǎn)權(quán)重的參數(shù)放在聚類中心的迭代表達(dá)式中，從而調(diào)節(jié)監(jiān)督信息的影響力。其次，通過(guò)matlab編程對(duì)機(jī)器學(xué)習(xí)庫(kù)中的Iris數(shù)據(jù)集進(jìn)行了測(cè)試驗(yàn)證。最后，具體分析了該改進(jìn)算法SSFCM的準(zhǔn)確率，并與前面的基本算法進(jìn)行實(shí)驗(yàn)對(duì)比，通過(guò)實(shí)驗(yàn)結(jié)果證明了該改進(jìn)算法具有的良好性能。

參考文獻(xiàn)：

[1] Wagstaff K,Cardie C,Rogers S,et al.Constrained K-means Clustering with Background Knowledge[C].Eighteenth International Conference on Machine Learning,2001：577-584.

[2] Huang H,Cheng Y,Zhao R.A Semi-supervised Clustering Algorithm Based on Must-Link Set[M].Advanced Data Mining and Applications. Springer Berlin Heidelberg,2008：492-499.

[3] Pedrycz W.Algorithms of Fuzzy Clustering with Partial Supervision[J].Pattern Recognition Letters,1985,3(01)：13-20.

[4] Li K,Cao Z,Cao L,et al.A Novel Semi-supervised Fuzzy C-means Clustering Method[C].Control and Decision Conference,2009：3761-3765.

[5] Blum A,Mitchell T.Combining Labeled and Unlabeled Data with Co-training[C].Eleventh Conference on Computational Learning Theory,2000：92-100.

[6] Wu L,Hoi S C H,Jin R,et al.Learning Bregman Distance Functions for Semi-Supervised Clustering[J].IEEE Transactions on Knowledge & Data Engineeri ng,2010,24(03)：478-491.

[7] Roy M,Ghosh S,Ghosh A.Change Detection in Remotely Sensed Images Using Semi-supervised Clustering Algorithms[J].International Journal of Knowledge Engineering & Soft Data Paradigms,2013,4(02)：118-137.

[8] 何振峰,熊范綸.結(jié)合限制的分隔模型及K-Means算法 [J].軟件學(xué)報(bào) ,2005,16(05)：799-809.HE Zhen-feng,XIONG Fan-lun.Limited Separation Model and K-Means Algorithm[J].Journal of Software,2005,16(05)：799-809.

[9] 肖宇,于劍.基于近鄰傳播算法的半監(jiān)督聚類[J].軟件學(xué)報(bào) ,2008,19(11)：2803-2813.XIAO Yu,YU Jian.Semi-supervised Clustering Based on Nearest Neighbor Propagation Algorithm[J].Journal of Software,2008,19(11)：2803-2813.

[10] Chen M S,Wang S W.Fuzzy Clustering Analysis for Optimizing Fuzzy Membership Functions[J].Fuzzy Sets &Systems,1999,103(02)：239-254.

[11] 唐亮,黃培之,謝維信.顧及數(shù)據(jù)空間分布特性的模糊C均值聚類算法研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版 ),2003,28(04)：476-479.TANG Liang,HUANG Pei-zhi,XIE Wei-xin.Study on Fuzzy C-means Clustering Algorithm Considering Spatial Distribution of Data[J].Engineering Journal of Wuhan University(Information Science Edition),2003,28(04)：476-479.

[12] Bezdek J,Hathaway R,Sobin M,et al.Convergence Theory for Fuzzy C-means：Counterexamples and Repairs[J].Systems Man & Cybernetics IEEE Transactions on,1987,7(05)：873-877.

[13] Bensaid A M,Hall L O,Bezdek J C,et al.Partially Supervised Clustering for Image Segmentation[J].Pattern Recognition,1996,29(05)：859-871.