半監督模糊聚類演算法的研究與改進
摘要：介紹了半監督模糊聚類（SFCM）演算法的原理和基礎，針對當先驗信息量稀少時演算法無法真正有效地利用labeled數據的監督信息的缺點，提出了一種改進的半監督模糊聚類演算法，即SSFCM演算法。該方法把表示labeled數據點權重的參數放在聚類中心的迭代表達式里，從而可以調節監督信息的影響力。最後，在標準Iris數據集下，通過matlab編程實現演算法。實驗結果表明：無論從聚類結果的準確率還是演算法運行迭代次數來看，SSFCM演算法均優於FCM演算法和SFCM演算法。
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.1 FCM演算法的基本思想
FCM演算法[10-12]是理論知識最為完善的演算法之一，在實際應用中也很常見。從本質上來講，它屬於基於劃分演算法的範疇，但它是一種柔性的模糊劃分，是在聚類的基礎上引入了模糊理論，從而利用隸屬度函數確定某一數據對象的劃分類別。
FCM演算法是一種基於目標函數的演算法，把含有 n個數據對象的集合 分為 c類，其聚類中心用ci 表示，目標函數是：
式中，uij 取值在0到1之間，ci 表示第i 類的聚類中心，表示第i 個聚類中心ci 與第j 個數據對象xj 之間的歐幾里德距離，而是加權指數，用來控制聚類的模糊程度。m 值越大，表示模糊程度越大。
在約束條件的約束下，利用Lagrange數乘法求取式（1）的最小值，得到聚類中心和隸屬度的迭代表達式如下：
1.1.2 FCM演算法的具體步驟
對FCM演算法的具體實現步驟描述如下。
步驟1：初始化隸屬度矩陣U ，保證其值均在0到1之間，並使之符合約束條件；
步驟2：利用式（2）計算新的聚類中心cimi=1,…,c ；
步驟3：利用式（3）計算新的隸屬度矩陣U ；
步驟4：按照式（1）計算目標函數，如果它取得最小值或是超過最大的迭代次數，則演算法束，輸出隸屬度矩陣和聚類中心；反之，則返回到步驟2。
1.2 半監督模糊C均值聚類演算法
1.2.1 SFCM演算法的基本思想
SFCM演算法把少量的labeled數據的類別標記當作監督信息，通過加入到FCM演算法的目標函數，從而在整個聚類的迭代優化進程中起到一定的監督作用。另外，在隸屬度方面也加入了帶有半監督性質的表達式。此時，SFCM演算法的目標函數為：
式中，M 表示加權指數，是一個經驗值，通常取值為2；a 表示平衡因子，用來調節式（4）中的無監督信息與監督信息彼此間的平衡，其中a 的具體值和總樣本數N 與標記樣本數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數據難以大量獲取，所以先驗信息具有稀少性，即代表labeled樣本的數量，代表unlabeled樣本的數量）。這將會導致SFCM演算法的聚類性能降低，和FCM演算法相比，體現不出本身的優越性。此時，labeled數據的類標記信息相對unlabeled數據來說已經很稀少，如果仍然僅僅依靠目標函數中的，不可避免將忽略labeled數據的指導作用。
為了避免出現上述現象，參照文獻[13]，採用把表示labeled數據點權重的參數放在聚類中心的迭代表達式的方法，以調節監督信息的影響力。具體做法是把表示SFCM演算法聚類中心的迭代表達式更改為：
式（6）表示的是SFCM演算法中的隸屬度矩陣的迭代公式，因為標記信息的初始隸屬度矩陣fij 滿足，且，把式（5）代入，則SFCM演算法中的labeled數據和unlabeled數據的隸屬度矩陣的迭代公式分別變為：
按照式（8），對聚類中心的迭代表達式式（7）進行修改，相當於保持SFCM演算法的迭代方式，仍為原樣。另外，對於隸屬度矩陣的迭代表達式式（6），根據式（11）和式（12）對labeled數據和unlabeled數據的隸屬度矩陣的權重做出對應形式的修改：
為了使改進演算法的隸屬度矩陣和聚類中心的迭代表達式與SFCM演算法的表達式保持相似，對於（12），這裡採用1+a 替換a 。此時，相對應的式子將變成如下形式：
2.2 SSFCM演算法的具體步驟
（1）初始化。設置聚類個數c ，平衡指數a ，由標記信息計算給出二值向量b= 和標記信息的初始隸屬度矩陣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中10次測試獲得的正確率，可以繪製如圖1所示的對比結果，由其中的折線可以更直觀地觀察分析。
由圖1的3條折線可以清楚看出，FCM演算法、SFCM演算法和SSFCM演算法的準確率大小依次為：SSFCM演算法最大，SFCM演算法其次，最後是FCM演算法，與理論分析結果一致。和FCM演算法相比，SFCM演算法充分利用了labeled數據的監督信息，而SSFCM演算法在整個聚類的迭代進程中不斷更新調整監督信息的比重，所以才會出現圖1所示的情況。觀察圖中的折線可以清楚看到，FCM演算法的準確率波動最大。演算法中，除了初始聚類中心，剩下的所有參數都是固定不變的。所以，可以得到如下結論：在聚類演算法中，初始聚類中心位置的選擇將會對整個聚類結果的優劣起到很大作用。從圖1中也可以看出，SSFCM演算法的準確率和FCM、SFCM演算法相對比更加平穩，數值上也高於FCM和SFCM演算法。計算3種測試結果的平均值，得到如圖2所示的柱形圖。
表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種聚類演算法。
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 Engineering,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.
[9] 肖宇,於劍.基於近鄰傳播演算法的半監督聚類[J].軟體學報,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.
[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.
作者簡介：
白福均，貴州大學大數據與信息工程學院碩士，主要研究方向為數據挖掘、雲計算。
高建瓴，貴州大學大數據與信息工程學院碩士，副教授，主要研究方向為數據挖掘、雲計算。
宋文慧，貴州大學大數據與信息工程學院碩士，主要研究方向為數據挖掘、半監督聚類。
賀思雲，貴州大學大數據與信息工程學院碩士，主要研究方向為數據挖掘、雲計算。
（本文選自《通信技術》2018年第五期）
原創聲明 >>>
本微信公眾號刊載的原創文章，歡迎個人轉發。未經授權，其他媒體、微信公眾號和網站不得轉載。
