半監督模糊聚類算法的研究與改進*

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

（貴州大學 大數據與信息工程學院，貴州 貴陽 550025）

0 引 言

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

一般來說，半監督聚類中的先驗信息通過相關行業專家的專業知識得到，可以分成兩大類，即類別標記信息和約束信息。類別標記信息是指在還沒有進行聚類時就已經知道了某個數據對象的類別，而約束信息則在實際生活中最常見，是指根據常識可以清楚知道某兩個數據對象是否屬于同一類。2000年，Wagstaff提出使用must-Link（正關聯）和cannot-Link（負關聯）來形容這種關系[6]。

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

可是，在實際應用中，雖然可以獲得含有先驗信息的數據，但是由于先驗信息的獲取需要消耗一定的人力、財力以及物力，導致含有先驗信息的數據在整個數據集中所占的比重很小，使得半監督聚類算法不能充分有效地利用先驗信息指導整個聚類過程，導致最終的聚類結果不是很理想。

本文在對模糊C均值聚類（FCM）算法和半監督模糊C均值聚類（SFCM）算法研究的基礎上，提出通過調節監督信息比重來改進SFCM算法——SSFCM算法，使之在先驗信息稀少時，SFCM算法仍然可以充分有效地利用先驗信 息，提高聚類性能。

1 半監督模糊C均值聚類算法

1.1 模糊C均值聚類算法

1.1.1 FCM算法的基本思想

FCM算法[10-12]是理論知識最為完善的算法之一，在實際應用中也很常見。從本質上來講，它屬于基于劃分算法的范疇，但它是一種柔性的模糊劃分，是在聚類的基礎上引入了模糊理論，從而利用隸屬度函數確定某一數據對象的劃分類別。

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

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

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

1.1.2 FCM算法的具體步驟

對FCM算法的具體實現步驟描述如下。

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

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

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

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

1.2 半監督模糊C均值聚類算法

1.2.1 SFCM算法的基本思想

SFCM算法把少量的labeled數據的類別標記當作監督信息，通過加入到FCM算法的目標函數，從而在整個聚類的迭代優化進程中起到一定的監督作用。另外，在隸屬度方面也加入了帶有半監督性質的表達式。此時，SFCM算法的目標函數為：

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

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

1.2.2 SFCM算法的具體步驟

輸入：需要聚類的數據對象集合X，聚類的類別數c以及帶有labeled信息的約束集S。

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

（1）首先利用帶有labeled信息的數據在集合S中進行初始劃分，然后把得到的結果看作是算法的初始聚類中心；

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

（3）按照式（4）計算目標函數。假如它比預先給定的閾值小，又或者是前后兩次的差小于閾值，那么算法結束；否則，轉到步驟（4）；

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

2 改進半監督模糊C均值聚類算法

2.1 SSFCM算法的基本思想

在SFCM算法中，隨著監督信息的比重增大，算法的聚類性能指標也會更好。但在實際應用中，因為labeled數據難以大量獲取，所以先驗信息具有稀少性，即|XL|＜|XU|（|XL|代表labeled樣本的數量，|XU|代表unlabeled樣本的數量）。這將會導致SFCM算法的聚類性能降低，和FCM算法相比，體現不出本身的優越性。此時，labeled數據的類標記信息相對unlabeled數據來說已經很稀少，如果仍然僅僅依靠目標函數中的不可避免將忽略labeled數據的指導作用。

為了避免出現上述現象，參照文獻[13]，采用把表示labeled數據點權重的參數放在聚類中心的迭代表達式的方法，以調節監督信息的影響力。具體做法是把表示SFCM算法聚類中心的迭代表達式更改為：

式（6）表示的是SFCM算法中的隸屬度矩陣的迭代公式，因為標記信息的初始隸屬度矩陣fij滿足0≤fij≤1，且，把式（5）代入，則SFCM算法中的labeled數據和unlabeled數據的隸屬度矩陣的迭代公式分別變為：

按照式（8），對聚類中心的迭代表達式式（7）進行修改，相當于保持SFCM算法的迭代方式，仍為原樣。另外，對于隸屬度矩陣的迭代表達式式（6），根據式（11）和式（12）對labeled數據和unlabeled數據的隸屬度矩陣的權重做出對應形式的修改：

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

2.2 SSFCM算法的具體步驟

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

（2）計算labeled和unlabeled的所有樣本點與聚類中心的距離；

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

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

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

3 實驗驗證

為了驗證本文算法的合理性，選取美國加州大學歐文分校提出的UCI數據庫中的Iris數據集，使用matlab編程驗證及評估SSFCM算法的聚類性能。

為了便于對后面實驗的聚類結果進行評價，這里引入一個指標RI=n0/n。對測試集進行實驗后，把得到的分類結果與標準數據集本身分好的類進行對比，計算得到正確分類的數據條數即為n0，n則為測試集中數據的總條數。很明顯，由表達式可知，RI表示的數值越大，聚類實驗的準確性越高，即聚類性能越好。

實驗過程中，分別使用FCM、SFCM和SSFCM算法進行測試比較。為了說明實驗結果的可靠性，FCM、SFCM和SSFCM這3種算法在實驗中均采用歐式距離。另外，SFCM和SSFCM算法的labeled樣本點要選取相同的，數量均為10個，且labeled樣本點的初始隸屬度相同。分別利用3種算法依次對Iris數據集測試，每種算法都測試10次，最終的測試結果如表1所示。

表1 FCM、SFCM、SSFCM算法準確率 /（%）

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

圖1 FCM、SFCM及SSFCM算法對比

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

圖2 FCM、SFCM及SSFCM算法平均準確率對比

表2從準確率、迭代次數和運行時間3個方面多角度對比顯示了3種算法的聚類結果。從運行時間方面來說，SSFCM算法運行時間最少，僅僅用了0.065 s；FCM算法其次，用時0.188 s；最后是SFCM算法。從迭代次數方面來說，SSFCM、FCM和SFCM這3種算法的迭代次數依次增多，和算法的運行時間保持一致。從聚類準確度方面分析，SSFCM算法達到最大值，為94.26%；而FCM算法因為沒有labeled樣本做指導，聚類的準確率是3種算法中最小的，為89.33%；SFCM算法居中，為91.12%。綜合來看，無論用3個方面的哪一個評價，SSFCM算法的聚類性能都要優于其他3種聚類算法。

表2 FCM、SFCM及SSFCM算法聚類效果對比

4 結 語

半監督聚類中標簽數據的獲取需要一定的代價。所以，在實際應用的數據集中，標簽數據的量都是比較少的，此時SFCM算法并不能很好地體現它的優勢。因此，本文重新定義了SFCM算法的迭代公式，把表示labeled數據點權重的參數放在聚類中心的迭代表達式中，從而調節監督信息的影響力。其次，通過matlab編程對機器學習庫中的Iris數據集進行了測試驗證。最后，具體分析了該改進算法SSFCM的準確率，并與前面的基本算法進行實驗對比，通過實驗結果證明了該改進算法具有的良好性能。

參考文獻：

[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] 何振峰,熊范綸.結合限制的分隔模型及K-Means算法 [J].軟件學報 ,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] 肖宇,于劍.基于近鄰傳播算法的半監督聚類[J].軟件學報 ,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] 唐亮,黃培之,謝維信.顧及數據空間分布特性的模糊C均值聚類算法研究[J].武漢大學學報(信息科學版 ),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.