改進的FCM半監督聚類算法

郭新辰, 樊秀玲, 郗仙田, 韓 嘯

(1.東北電力大學 理學院, 吉林 吉林 132012; 2.吉林大學 學報編輯部, 長春 130012)

研究簡報

改進的FCM半監督聚類算法

郭新辰1, 樊秀玲1, 郗仙田1, 韓 嘯2

(1.東北電力大學 理學院, 吉林 吉林 132012; 2.吉林大學 學報編輯部, 長春 130012)

通過將類間分離度函數引入到模糊C-均值聚類算法中, 結合半監督的思想, 建立基于信息熵的半監督模糊C-均值聚類模型, 并對該模型的求解過程進行推導, 提出一種新的算法.為了驗證算法的有效性, 將該算法在UCI數據集上進行實驗, 實驗結果表明, 該算法比僅引入信息熵的模糊C-均值聚類方法聚類性能更好.

半監督聚類； 模糊C-均值算法； 信息熵

在機器學習問題中, 人們容易獲取大量未標簽的樣本和少量已標簽的樣本, 若從這些樣本中挖掘出潛在的價值信息, 常采用半監督學習方法提高對樣本的學習泛化能力.半監督學習方法主要利用有標記數據構造學習機, 并對部分無標記數據進行預測, 再將無標記數據和對應的預測標記加入訓練集中, 重新對學習機進行訓練, 以提高學習機性能.

半監督學習方法[1]一般分為半監督分類和半監督聚類.二者區別在于半監督聚類能使用標記樣本轉化成分類, 也能根據需要擴展和修改存在的分類, 以反映數據中的其他規則.模糊聚類算法中應用較典型的是模糊C-均值聚類算法, 簡稱FCM, 這種方法存在一定的局限性, 即在每次聚類過程中數據均勻收縮.文獻[2]通過在標準FCM目標函數的約束條件中增加信息熵約束, 提高了聚類性能, 彌補了模糊聚類存在數據收縮問題的不足, 即常用的引入信息熵模糊C-均值聚類方法, 簡稱IEFCM, 但該方法未利用部分樣本的監督信息; 為了減少有價值信息的浪費, 文獻[3-5]結合半監督思想及標記樣本隸屬度賦值問題, 在FCM算法的數學模型中引進輔助變量加入先驗信息以影響聚類.由于實際生產的干擾因素過多且環境多變, 因此獲得的數據樣本信息通常會包含一些干擾信息； 文獻[6]根據FCM的目標函數物理意義, 引進隸屬度補償項和類中心最大項, 通過迭代優化代價函數, 得到了較滿意的聚類結果.

本文將引入信息熵的模糊C-均值聚類方法與半監督性質及類間分離度相結合, 提出一種改進的聚類算法, 即基于模糊C-均值的半監督聚類算法, 簡稱SIEFCM.

1 基于信息熵的模糊C-均值半監督聚類算法

1.1 模糊C-均值聚類算法 FCM算法[7-9]是目前廣泛采用的一種聚類算法, 即使對于很難明顯分類的變量, 模糊C-均值聚類也能得到較滿意的效果.

傳統的模糊C-均值聚類是用隸屬度確定聚類程度的一種聚類算法, 即把n個d維樣本xj(j=1,2,…,n)分為c個組, 每組即為一類, 聚類中心集為{v1,v2,…,vc}, 其中vi為類i的類中心.

標準FCM算法的數學模型為

其中:uij表示樣本xj屬于類i的程度；U為uij構成的c×N隸屬度矩陣；V為vi構成的c×n類中心矩陣；m∈(1,+∞)表示一個加權模糊指數, 反映控制隸屬度在各類間共享的程度；dij=‖xj-vi‖表示樣本點xj到類中心vi的歐氏距離.

1.2 基于信息熵的FCM聚類算法 約束條件中引入信息熵的FCM算法數學模型為

其等價于優化問題

其中:dkj=‖xj-vk‖表示樣本點xj到類中心vk的歐氏距離；η∈(0,1)為類中心影響程度調節因子參數；

其他參數與式(1)定義相同.式(3)與式(1)相比, 顯然考慮了數據在每次聚類過程中數據空間上的實際分布特性.

1.3 基于信息熵的模糊C-均值半監督聚類算法 對隸屬度引入半監督性質的補償項Ψ, 描述監督信息, 其表達式為

類間分離度函數Φ描述不同類間的分散度問題, 其表達式為

根據式(3)和半監督聚類的定義, 本文希望類間超平面間隔更大.已知信息樣本具有引導聚類的能力, 其隸屬度值的影響使最終聚類質量盡可能比用隨機數聚類的準確性更高.因此, 對式(3)做修改, 對隸屬度引入半監督性質的補償項和類間分離度函數, 得到新的目標函數, 進而得到本文提出的基于模糊C-均值的半監督聚類方法的數學模型, 其表達形式為

對于模型(6), 利用Lagrange乘數因子法進行求解, 構造Lagrange函數為

基于信息熵的模糊C-均值半監督聚類算法步驟如下：

1) 初始化隸屬度U(t),V(t), 其中t為迭代次數；

2) 將V(t)按式(7)更新為V(t+1)；

4) 當|J(t+1)-J(t)|<ε, 或迭代次數t超過最大迭代次數M時, 算法終止; 否則轉2).

圖1 性能指標與監督信息比的變化曲線Fig.1 Curves of performance index vs the weight of supervised information

2 仿真實驗

為了驗證本文算法的合理性, 在UCI機器學習數據庫中, 采用常用于聚類方法檢測的Iris數據集、Wine數據集和Balance-scale數據集進行實驗, 數據集信息列于表1.

表1 實驗數據集信息Table 1 Related information description ofthe experimental data sets

對于每個數據集, 隨機選取總體樣本的10%,20%,30%,40%作為測試集.為了客觀進行不同算法性能的優劣比較, 設參數m=2,η=0.000 1.

性能評價指標為RI=n0/n, 其中n0為測試集的聚類結果與標準數據集對比后得到正確分類樣本的平均個數；n為測試數據集的樣本總數；RI值越大, 表示聚類準確性越大, 聚類效果越好.重復5次實驗, 實驗結果RI的平均值列于表2.由表2可見, 隨著監督信息的增多, 聚類的正確率有增大趨勢, 表明監督信息數據具有指導作用.在Iris數據集、Wine數據集和Balance-scale數據集上性能指標與監督信息比的變化曲線如圖1所示.由圖1可見： 在不同數據集上,RI值隨監督信息比值的增大而增大； 雖然聚類正確率的上升速度不能按監督信息量的增幅而變化, 但總體上仍高于原有聚類算法的聚類精度, 進而驗證了該算法的合理性和有效性.

表2 實驗結果RI的比較Table 2 Comparison of experimental results (RI value)

綜上所述, 本文提出了一種新的基于信息熵的模糊C-均值半監督聚類算法, 在聚類過程中利用已知樣本信息減少了信息的浪費, 同時考慮了類內緊度信息和類間分散度信息, 有效改善了基于信息熵無監督FCM聚類方法的盲目性.將本文方法在UCI數據集上進行仿真實驗, 實驗結果表明, 本文所提出的新算法總體上優于基于信息熵無監督FCM聚類算法的性能.

[1]Watts D J, Strogatz S H.Collective Dynamic of “Small-World” Networks [J].Nature, 1998, 393: 440-442.

[2]邢婷, 邢志國, 王鳳領.基于信息熵的FCM聚類算法 [J].計算機工程與設計, 2010, 31(23)： 5092-5096.(XING Ting, XING Zhiguo, WANG Fengling.FCM Clustering Algorithm Based on Information Entropy [J].Computer Engineering and Design, 2010, 31(23)： 5092-5096.)

[3]李春芳, 龐雅靜, 錢麗璞, 等.半監督FCM聚類算法目標函數研究 [J].計算機工程與應用, 2009, 45(14)： 128-132.(LI Chunfang, PANG Yajing, QIAN Lipu, et al.Objective Function of Semi-supervised FCM Clustering Algorithm [J].Computer Engineering and Applications, 2009, 45(14)： 128-132.)

[4]Amini M, Gallinari P.Semi-supervised Learning with Explicit Misclassification Modeling [C]//Proceedings of the 18th International Joint Conference on Artificial Intelligence.San Francisco: Morgan Kaufmann, 2003: 555-560.

[5]Bouchachia A, Pedrycz W.Enhancement of Fuzzy Clustering by Mechanisms of Partial Supervision [J].Fuzzy Sets and Systems, 2006, 157(13): 1759-1773.

[6]姚紫陽． 半監督中心最大化模糊C-均值算法 [J].計算機工程與應用, 2012, 48(33)： 188-193． (YAO Ziyang.Semi-supervised FuzzyC-Means Algorithm with Maximum Center Distance [J].Computer Engineering and Applications, 2012, 48(33)： 188-193.)

[7]CHEN Musong, WANG Shinnwen.Fuzzy Clustering Analysis for Optimizing Fuzzy Membership Function [J].Fuzzy Sets and Systems, 1999, 103(2): 239-254.

[8]唐亮, 黃培之, 謝維信.顧及數據空間分布特性的模糊C-均值聚類算法研究 [J].武漢大學學報: 信息科學版, 2003, 28(4): 476-479.(TANG Liang, HUANG Peizhi, XIE Weixin.A New Method of FCM Considering the Distribution of Spatial Data [J].Geomatic and Information Science of Wuhan University, 2003, 28(4): 476-479.)

[9]Bezdek J C, Hathaway R J, Sabin M J, et al.Convergence Theory for FuzzyC-Means: Connterexamples and Repairs [J].IEEE System, Man, and Cybernetics, 1987, 17(5): 873-877.

ImprovedFuzzyC-MeansClusteringAlgorithm

GUO Xinchen1, FAN Xiuling1, XI Xiantian1, HAN Xiao2
(1.CollegeofScience,NortheastDianliUniversity,Jilin132012,JilinProvince,China;
2.EditorialDepartmentofJournalofJilinUniversity,Changchun130012,China)

A new fuzzyC-means clustering algorithm was proposed by the introduction of functions of separation between clusters into FCM clustering algorithm and with the nature of semi-supervised learning considered.The model of semi-supervised FCM clustering algorithm with the information entropy as constraints was established and the solution to the model was derived.The simulation experiments were performed on UCI data sets to verify the effectiveness of the proposed algorithm.The experimental results show that this modified algorithm gets the better validity and performance.

semi-supervised clustering; fuzzyC-means algorithm (FCM); information entropy

2014-01-10.

郭新辰(1971—), 男, 漢族, 博士, 教授, 從事數據挖掘和機器學習的研究, E-mail: neduer@163.com.通信作者: 韓 嘯(1981—), 男, 漢族, 博士研究生, 編輯, 從事數據挖掘和網絡協同等的研究, E-mail: hanxiao@jlu.edu.cn.

國家自然科學基金(批準號: 11226263; 11201057; 61202261)和吉林省自然科學基金(批準號: 201215165).

TP181

A

1671-5489(2014)06-1293-04

10.13413/j.cnki.jdxblxb.2014.06.35

韓 嘯)