梁　 鮮，曲福恒，才　華，楊　勇（.長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，吉林 長春 300；.長春理工大學(xué)　電子信息工程學(xué)院，吉林　長春 300）

一種新的模糊聚類有效性指標(biāo)*

梁 鮮1，曲福恒1，才華2，楊勇1
（1.長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，吉林 長春 130022；2.長春理工大學(xué)電子信息工程學(xué)院，吉林長春 130022）

針對模糊C均值（FCM）算法聚類數(shù)需要預(yù)先設(shè)定的問題，提出了一種新的模糊聚類有效性指標(biāo)。首先，計(jì)算簇中每個(gè)屬性的方差，給方差較小的屬性賦予較大的權(quán)值，給方差較大的屬性賦予較小的權(quán)值，得到一種基于屬性加權(quán)的FCM算法；然后，根據(jù)FCM改進(jìn)算法得到的隸屬度矩陣計(jì)算類內(nèi)緊致性和類間分離性；最后，利用類內(nèi)緊致性和類間分離性定義一個(gè)新的聚類有效性指標(biāo)。實(shí)驗(yàn)結(jié)果表明，該指標(biāo)可以找到符合數(shù)據(jù)自然分布的類的數(shù)目。基于屬性加權(quán)的FCM算法可以識別不同屬性的重要程度，增加聚類結(jié)果的準(zhǔn)確率，使用FCM改進(jìn)算法得到的隸屬度矩陣定義的有效性指標(biāo)，能夠發(fā)現(xiàn)正確的聚類個(gè)數(shù)，實(shí)現(xiàn)聚類無監(jiān)督的學(xué)習(xí)過程。

模糊聚類；模糊C均值算法；有效性指標(biāo)；最佳聚類數(shù)

0　引言

聚類分析［1-3］是一種無監(jiān)督的分類過程。研究聚類問題的一個(gè)最基本問題是發(fā)現(xiàn)符合數(shù)據(jù)真實(shí)分布的聚類個(gè)數(shù)。借助模糊 C均值算法［4-5］，定義有效性指標(biāo)，發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)成為研究熱點(diǎn)。由于數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的多樣性，導(dǎo)致沒有通用的有效性指標(biāo)。

針對FCM算法在聚類過程中未考慮樣本各維屬性對聚類貢獻(xiàn)不同的問題，使用自適應(yīng)的方法計(jì)算簇中每個(gè)屬性的權(quán)值，得到一種基于屬性加權(quán)的FCM算法。充分考慮數(shù)據(jù)集的幾何結(jié)構(gòu)，使用改進(jìn)FCM算法得到的隸屬度矩陣，計(jì)算類內(nèi)緊致性和類間分離性，定義新的聚類有效性指標(biāo)，發(fā)現(xiàn)符合數(shù)據(jù)真實(shí)分布的聚類個(gè)數(shù)。

1　一種新的模糊聚類有效性指標(biāo)

1.1一種基于屬性加權(quán)的FCM算法

聚類過程中為了使FCM算法能夠區(qū)分不同屬性的重要作用，使用自適應(yīng)的方法計(jì)算簇中每個(gè)屬性的權(quán)值。給簇內(nèi)方差較小的屬性賦予較大的權(quán)值，給簇內(nèi)方差較大的屬性賦予較小的權(quán)值，得到同一屬性在不同簇中具有不同權(quán)值的FCM算法。根據(jù)權(quán)值的大小識別屬性的重要性，增加聚類結(jié)果的準(zhǔn)確率。

改進(jìn)算法通過最小化目標(biāo)函數(shù)J′m實(shí)現(xiàn)：

其中 σit是簇 i中屬性 t距離簇中心的方差，簇內(nèi)屬性的方差越小，對簇的貢獻(xiàn)越大，賦予的權(quán)值越大。為了使J′m達(dá)到最小值，U′和V′的更新公式為：

1.2緊致性和分離性

類內(nèi)數(shù)據(jù)的緊致性和類間數(shù)據(jù)的分離性是衡量FCM聚類結(jié)果有效性的重要標(biāo)準(zhǔn)和基本條件［6-7］?；趯傩约訖?quán)的FCM算法，定義類內(nèi)數(shù)據(jù)的緊致性為：

其中，|v|是簇i中樣本個(gè)數(shù)

簇i的平均誤差，是控制函數(shù)單調(diào)遞減的趨勢。Comp（c）的值越小，類內(nèi)數(shù)據(jù)的緊致性越好。

基于屬性加權(quán)的FCM算法，定義類間數(shù)據(jù)的分離性為：

其中，‖μip-μiq‖表示樣本 xi屬于簇 p和簇 q的隸屬度的差值。簇間的分離性越大，Sep（c）的值越大。

對類內(nèi)數(shù)據(jù)緊致性和類間數(shù)據(jù)分離性進(jìn)行歸一化，得到如下公式：

其 中 ，Comp（c）max=Max｛Comp（2），Comp（3），… ，Comp（cmax）｝。

其中，Sep（c）max=Max｛Sep（2），Sep（3），…，Sep（cmax）｝。

結(jié)合式（6）和式（7），定義新的聚類有效性指標(biāo)為：

聚類質(zhì)量越好，fc的值越小。因此，可以通過計(jì)算 fc的最小值，發(fā)現(xiàn)符合數(shù)據(jù)分布的聚類個(gè)數(shù)。

2　仿真實(shí)驗(yàn)及結(jié)果

為了證明本文算法的有效性，進(jìn)行真實(shí)數(shù)據(jù)的測試。取模糊因子m=2，最大聚類個(gè)數(shù)為10。

真實(shí)數(shù)據(jù)使用UCI中的Iris數(shù)據(jù)集、BUPA數(shù)據(jù)集和WDBC數(shù)據(jù)集。在數(shù)據(jù)集上運(yùn)行基于屬性加權(quán)的FCM算法，使用本文提出的聚類有效性指標(biāo)進(jìn)行聚類分析。3個(gè)數(shù)據(jù)集上有效性指標(biāo)與聚類個(gè)數(shù)之間的變化關(guān)系如圖1所示。多個(gè)有效性指標(biāo)確定3個(gè)數(shù)據(jù)集的最佳聚類數(shù)，比較結(jié)果如表1所示。

圖1　3個(gè)數(shù)據(jù)集上fc指標(biāo)與聚類數(shù)關(guān)系圖

表1　多種指標(biāo)確定最佳聚類數(shù)的比較

由圖1可知，3個(gè)數(shù)據(jù)集上有效性指標(biāo)fc的最小值分別對應(yīng)數(shù)據(jù)集的真實(shí)聚類個(gè)數(shù)。由表1可知，有效性指標(biāo)fc和PBMF可以同時(shí)發(fā)現(xiàn)3個(gè)數(shù)據(jù)集的真實(shí)聚類個(gè)數(shù)。XB指標(biāo)僅能發(fā)現(xiàn)WDBC數(shù)據(jù)集的真實(shí)聚類個(gè)數(shù)，SC指標(biāo)不能發(fā)現(xiàn)BUPA數(shù)據(jù)集的真實(shí)聚類個(gè)數(shù)，F(xiàn)HV僅能發(fā)現(xiàn)Iris數(shù)據(jù)集的真實(shí)聚類個(gè)數(shù)，CWB指標(biāo)發(fā)現(xiàn)的聚類個(gè)數(shù)與3個(gè)數(shù)據(jù)集的真實(shí)聚類個(gè)數(shù)均有偏差。由此證明有效性指標(biāo)fc是有效的，且優(yōu)于多個(gè)現(xiàn)有的有效性指標(biāo)。

3　結(jié)論

為了使FCM算法在聚類過程中能夠識別不同屬性對聚類貢獻(xiàn)的大小，使用自適應(yīng)的方法計(jì)算簇中每個(gè)屬（ ）性的權(quán)值，給簇內(nèi)方差較小的屬性賦予較大的權(quán)值，給簇內(nèi)方差較大的屬性賦予較小的權(quán)值，得到每個(gè)屬性在不同簇中具有不同權(quán)值的FCM算法。利用改進(jìn)FCM算法得到的隸屬度矩陣計(jì)算類內(nèi)數(shù)據(jù)的緊致性和類間數(shù)據(jù)的分離性，定義聚類有效性指標(biāo)，自動獲得最佳聚類數(shù)，實(shí)現(xiàn)聚類無監(jiān)督的學(xué)習(xí)過程。通過實(shí)驗(yàn)證明了該指標(biāo)的有效性和可行性。

［1］Su Tieming，Ye Sanpai，Sun Wei，et al.Compen sation model for thermal error of machiningcenter basedon gray-fuzzy clustering and LS-SVM ［J］.Journal of Shenyang University of Technology，2011，33（5）：524-530.

［2］向培素．近鄰半監(jiān)督聚類算法的MATLAB實(shí)現(xiàn)［J］．?dāng)?shù)學(xué)技術(shù)與應(yīng)用，2012（8）：100-101.

［3］Yu Haitao，Li Zi，Yao Nianmin.Research on optimization method for K-Means clustering algorithm［J］.Journal of Chinese Computer Systems，2012，33（10）：2273-2277.

［4］王亮，王士同.動態(tài)權(quán)值混合C-均值模糊核聚類算法［J］.軟件學(xué)報(bào)，2011，28（8）：2852-2855.

［5］楊草原，劉大有，楊博，等.聚類集成方法研究［J］.計(jì)算機(jī)科學(xué)，2011，38（2）：166-170.

［6］KANNAN S R，RAMATHILAGAM S，DEVI R，et al.Robust kernel FCM in segmentation of breastmedical images［J］.Expert System with Applications，2011，38（4）：4382-4389.

［7］ZALIK K R，ZALIK B.Validity index for clusters of different sizes and densities［J］.Pattern Recognition Letters，2011，32（2）：221-234.

A novel validity index for fuzzy clustering

Liang Xian1，Qu Fuheng1，Cai Hua2，Yang Yong1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022，China；2.School of Electronic and Information Engineering，Changchun Univercity of Science and Technology，Changchun 130022，China）

Aiming at the problem that the number of clustering of Fuzzy C-means（FCM）algorithm needs setting in advance，a new fuzzy cluster validity index was presented.Firstly，through the calculation of variance of each attribute in the cluster，giving the big weight to the attributes of small variance，while giving the small weight to the attributes of big variance，to get a FCM algorithm based on weighted attribute.Secondly，the inter class compactness and the inter class separability were computed by using the membership matrix which was calculated by the improved algorithm of FCM.Finally，a new cluster validity index was defined by using the inter class compactness and separability.Experimental results show that the optimal cluster number can be effectively found by the proposed index.The FCM algorithm based on weighted attribute can identify the degree of importance of different attributes，increase the accuracy of clustering results.The new cluster validity index defined by the membership matrix which was calculatedby the improvedalgorithmof FCM，can find the correct number of clusters，andrealize the learning process of unsupervised clustering.

fuzzy clustering；fuzzy C-means algorithm；validity index；optimal cluster number

TP391

A

1674-7720（2015）08-0074-02

2014-11-24）

梁鮮（1990-），女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、聚類分析。

曲福恒（1979-），通信作者，男，博士，副教授，主要研究方向：圖像處理，數(shù)據(jù)挖掘，模式識別。E-mail：1179954525@qq.com。

才華（1977-），男，博士，副教授，主要研究方向：并行計(jì)算，圖像處理，模式識別。

吉林省自然科學(xué)基金（ 20130101179JC -13 ， 201215145 ）