梁　 鮮，曲福恒，才　華，楊　勇（.長春理工大學 計算機科學技術學院，吉林 長春 300；.長春理工大學　電子信息工程學院，吉林　長春 300）

一種新的模糊聚類有效性指標*

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

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

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

0　引言

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

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

1　一種新的模糊聚類有效性指標

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

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

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

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

1.2緊致性和分離性

類內(nèi)數(shù)據(jù)的緊致性和類間數(shù)據(jù)的分離性是衡量FCM聚類結(jié)果有效性的重要標準和基本條件［6-7］。基于屬性加權(quán)的FCM算法，定義類內(nèi)數(shù)據(jù)的緊致性為：

其中，|v|是簇i中樣本個數(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ù)分離性進行歸一化，得到如下公式：

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

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

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

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

2　仿真實驗及結(jié)果

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

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

圖1　3個數(shù)據(jù)集上fc指標與聚類數(shù)關系圖

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

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

3　結(jié)論

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

［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實現(xiàn)［J］．數(shù)學技術與應用，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］.軟件學報，2011，28（8）：2852-2855.

［5］楊草原，劉大有，楊博，等.聚類集成方法研究［J］.計算機科學，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-），男，博士，副教授，主要研究方向：并行計算，圖像處理，模式識別。

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