改進(jìn)的FCM半監(jiān)督聚類算法

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

(1.東北電力大學(xué) 理學(xué)院, 吉林 吉林 132012; 2.吉林大學(xué) 學(xué)報(bào)編輯部, 長(zhǎng)春 130012)

研究簡(jiǎn)報(bào)

改進(jìn)的FCM半監(jiān)督聚類算法

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

(1.東北電力大學(xué) 理學(xué)院, 吉林 吉林 132012; 2.吉林大學(xué) 學(xué)報(bào)編輯部, 長(zhǎng)春 130012)

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

半監(jiān)督聚類； 模糊C-均值算法； 信息熵

在機(jī)器學(xué)習(xí)問(wèn)題中, 人們?nèi)菀撰@取大量未標(biāo)簽的樣本和少量已標(biāo)簽的樣本, 若從這些樣本中挖掘出潛在的價(jià)值信息, 常采用半監(jiān)督學(xué)習(xí)方法提高對(duì)樣本的學(xué)習(xí)泛化能力.半監(jiān)督學(xué)習(xí)方法主要利用有標(biāo)記數(shù)據(jù)構(gòu)造學(xué)習(xí)機(jī), 并對(duì)部分無(wú)標(biāo)記數(shù)據(jù)進(jìn)行預(yù)測(cè), 再將無(wú)標(biāo)記數(shù)據(jù)和對(duì)應(yīng)的預(yù)測(cè)標(biāo)記加入訓(xùn)練集中, 重新對(duì)學(xué)習(xí)機(jī)進(jìn)行訓(xùn)練, 以提高學(xué)習(xí)機(jī)性能.

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

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

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

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

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

標(biāo)準(zhǔn)FCM算法的數(shù)學(xué)模型為

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

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

其等價(jià)于優(yōu)化問(wèn)題

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

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

1.3 基于信息熵的模糊C-均值半監(jiān)督聚類算法 對(duì)隸屬度引入半監(jiān)督性質(zhì)的補(bǔ)償項(xiàng)Ψ, 描述監(jiān)督信息, 其表達(dá)式為

類間分離度函數(shù)Φ描述不同類間的分散度問(wèn)題, 其表達(dá)式為

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

對(duì)于模型(6), 利用Lagrange乘數(shù)因子法進(jìn)行求解, 構(gòu)造Lagrange函數(shù)為

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

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

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

4) 當(dāng)|J(t+1)-J(t)|<ε, 或迭代次數(shù)t超過(guò)最大迭代次數(shù)M時(shí), 算法終止; 否則轉(zhuǎn)2).

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

2 仿真實(shí)驗(yàn)

為了驗(yàn)證本文算法的合理性, 在UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中, 采用常用于聚類方法檢測(cè)的Iris數(shù)據(jù)集、Wine數(shù)據(jù)集和Balance-scale數(shù)據(jù)集進(jìn)行實(shí)驗(yàn), 數(shù)據(jù)集信息列于表1.

表1 實(shí)驗(yàn)數(shù)據(jù)集信息Table 1 Related information description ofthe experimental data sets

對(duì)于每個(gè)數(shù)據(jù)集, 隨機(jī)選取總體樣本的10%,20%,30%,40%作為測(cè)試集.為了客觀進(jìn)行不同算法性能的優(yōu)劣比較, 設(shè)參數(shù)m=2,η=0.000 1.

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

表2 實(shí)驗(yàn)結(jié)果RI的比較Table 2 Comparison of experimental results (RI value)

綜上所述, 本文提出了一種新的基于信息熵的模糊C-均值半監(jiān)督聚類算法, 在聚類過(guò)程中利用已知樣本信息減少了信息的浪費(fèi), 同時(shí)考慮了類內(nèi)緊度信息和類間分散度信息, 有效改善了基于信息熵?zé)o監(jiān)督FCM聚類方法的盲目性.將本文方法在UCI數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn), 實(shí)驗(yàn)結(jié)果表明, 本文所提出的新算法總體上優(yōu)于基于信息熵?zé)o監(jiān)督FCM聚類算法的性能.

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

[2]邢婷, 邢志國(guó), 王鳳領(lǐng).基于信息熵的FCM聚類算法 [J].計(jì)算機(jī)工程與設(shè)計(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]李春芳, 龐雅靜, 錢(qián)麗璞, 等.半監(jiān)督FCM聚類算法目標(biāo)函數(shù)研究 [J].計(jì)算機(jī)工程與應(yīng)用, 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]姚紫陽(yáng)． 半監(jiān)督中心最大化模糊C-均值算法 [J].計(jì)算機(jī)工程與應(yīng)用, 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]唐亮, 黃培之, 謝維信.顧及數(shù)據(jù)空間分布特性的模糊C-均值聚類算法研究 [J].武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 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—), 男, 漢族, 博士, 教授, 從事數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的研究, E-mail: neduer@163.com.通信作者: 韓 嘯(1981—), 男, 漢族, 博士研究生, 編輯, 從事數(shù)據(jù)挖掘和網(wǎng)絡(luò)協(xié)同等的研究, E-mail: hanxiao@jlu.edu.cn.

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào): 11226263; 11201057; 61202261)和吉林省自然科學(xué)基金(批準(zhǔn)號(hào): 201215165).

TP181

A

1671-5489(2014)06-1293-04

10.13413/j.cnki.jdxblxb.2014.06.35

韓 嘯)