一種新的聚類有效性函數(shù)：模糊劃分的模糊熵

卿銘，孫曉梅

（1.西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 600031; 2. 河南工程學(xué)院 數(shù)學(xué)與物理科學(xué)系,河南 鄭州 451191）

?

一種新的聚類有效性函數(shù)：模糊劃分的模糊熵

卿銘1，孫曉梅2

（1.西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 600031; 2. 河南工程學(xué)院 數(shù)學(xué)與物理科學(xué)系,河南 鄭州 451191）

模糊聚類分析結(jié)果是否合理的問題屬于模糊聚類有效性判定課題，其核心是模糊聚類有效性函數(shù)的構(gòu)造。文中基于序關(guān)系定義了模糊劃分模糊熵來描述模糊劃分的模糊程度?？紤]到現(xiàn)有的一類有效的模糊聚類有效性函數(shù)就是基于數(shù)據(jù)集的模糊劃分的，因此文中也用模糊劃分的模糊熵作為聚類有效性函數(shù)。實(shí)驗表明，模糊劃分的模糊熵作為模糊聚類的有效性函數(shù)是合理的、可行的。

模糊C均值聚類；模糊劃分的模糊熵；聚類有效性；聚類分析；模糊劃分；模糊熵；熵函數(shù)；模糊集

聚類是一個在人類認(rèn)識世界的過程中產(chǎn)生的古老問題。在面對紛繁的大千世界時，關(guān)注事物間的相似性并以此來區(qū)別不同的事物，對于人類來說是一種清晰而直觀的思路。而每個概念的最初形成無不借助于事物間的聚類分析。因此聚類分析的研究不僅具有重要的理論意義，而且具有重要的工程應(yīng)用價值和人文價值。對于給定的數(shù)據(jù)集，首先要判斷有無聚類結(jié)構(gòu)，這屬于聚類趨勢研究的課題；如果已經(jīng)確認(rèn)有聚類結(jié)構(gòu)，則需要用算法來確定這些結(jié)構(gòu)，這屬于聚類分析的研究課題；得到結(jié)構(gòu)后，需要分析、判斷聚類的結(jié)果是否合理，這屬于聚類有效性研究的課題[1]。

傳統(tǒng)的聚類分析是一種硬劃分。它將每個待辨識的對象嚴(yán)格地劃分到某個類中，其聚類結(jié)果具有非此即彼的性質(zhì)。而實(shí)際上大多數(shù)對象并沒有嚴(yán)格的屬性，它們在形態(tài)和類屬方面存在著中介性，往往具有亦此亦彼的性質(zhì)，因此適合進(jìn)行軟劃分。而模糊集理論的提出，對聚類分析軟劃分的發(fā)展起到了重要作用。用模糊的方法來處理聚類問題，稱之為模糊聚類分析，是當(dāng)前聚類分析研究的主流。

關(guān)于聚類有效性問題的研究通常是基于硬C均值聚類算法和模糊C均值聚類算法進(jìn)行的。在模糊聚類有效性函數(shù)中，基于數(shù)據(jù)集的模糊劃分的有效性函數(shù)是很重要的一類，其觀點(diǎn)是：好的分類聚類應(yīng)對應(yīng)于數(shù)據(jù)集較分明的劃分，劃分的分明性越好，分類的不確定性就越小。盡管以Dunn[4]的劃分系數(shù)為代表的聚類有效性函數(shù)取得一定的效果然而仍存在缺陷：劃分系數(shù)有隨類數(shù)增加而遞減的趨勢。為克服這一缺點(diǎn)，范九倫[2- 3]、Dave[5]和Robubens[6]作了很多的工作。但仍未較好解決這一難題——聚類有效性函數(shù)隨類數(shù)增加而遞減（增）的趨勢。其他一些學(xué)者也對模糊聚類的有效性做了深入的討論[7-20]，但都不完善，有繼續(xù)改進(jìn)的余地。

文中借鑒好的聚類應(yīng)對應(yīng)于數(shù)據(jù)集較分明的劃分，劃分的分明性越好，分類的不確定性就越小的學(xué)術(shù)思想，基于序關(guān)系定義模糊劃分的模糊熵來反映模糊劃分的模糊程度，并以其作為聚類有效性函數(shù)，實(shí)驗證明模糊劃分的模糊熵作為模糊聚類的有效性函數(shù)是合理、有效的。

1 FCM算法

這里

Mfc={U∈Rnc|uij∈[0,1],?i,j

下面給出文中采用的從隨機(jī)初始化模糊劃分矩陣開始迭代FCM算法步驟[8-9]。

1）初始化: 給定聚類類別數(shù)c（2≤c≤n，n為樣本點(diǎn)個數(shù)）、模糊加權(quán)指數(shù)m，設(shè)定迭代停止閾值ε，隨機(jī)初始化劃分矩陣U（0），設(shè)置迭代計數(shù)器b=0。

2）計算或更新聚類原型模式矩陣P（b）:

3）更新模糊劃分矩陣U（b+1）;

4）若||U（b+1）-U（b）||<ε，輸出劃分矩陣U和聚類原型P等聚類信息，算法結(jié)束；否則，令b=b+1，轉(zhuǎn)向2）。其中||·||為合適的矩陣范數(shù)。

算法從隨機(jī)初始化模糊劃分矩陣開始迭代，這樣做的原因主要有3個：1）標(biāo)準(zhǔn)FCM算法本身并不能保證一定收斂到全局最優(yōu)點(diǎn)，算法可能收斂于某個極值點(diǎn)或局部最優(yōu)點(diǎn)，由于模糊劃分矩陣的隨機(jī)性選取，通過對FCM算法的多次調(diào)用，可能會發(fā)現(xiàn)全局最優(yōu)點(diǎn)。2）若從初始化聚類原型模式矩陣開始迭代，初始聚類原型的選取有很多種方法，考慮到算法的通用性，很難抉擇一個優(yōu)秀的選取方案，并且一旦選取方案（這里不包括隨機(jī)初始化聚類原型）確定了，迭代過程就隨之固定，算法可能始終收斂于某個極值點(diǎn)或局部最優(yōu)點(diǎn)。3）隨機(jī)初始化聚類原型顯然沒有隨機(jī)初始化劃分矩陣方便，而且也沒有什么客觀的理由。

2 模糊劃分的模糊熵

記X上的所有模糊劃分為FP（X）。[a]∈FP（X）表示每個元素都是常數(shù)a的劃分矩陣。

2）硬劃分是其極小元，任何2個硬劃分都可比，且在同一個等價類中；

3）[1/c]是其最大元。

證明1）設(shè)U1=[uij]，U2=[vij]。

min{uij,1-uij}≤min{vij,1-vij}≤1/2。

2）證明略。

定義2一個實(shí)函數(shù)E:FP（X）→R+稱為有限論域X上模糊c劃分的模糊熵（簡稱模糊劃分模糊熵），如果E滿足：

1）E（U,c）=0當(dāng)且僅當(dāng)U是硬劃分；

若定義

式中：參數(shù)p>0。

顯然，下述的定理2、3是成立的。

定理2Ep（U;c） 是有限論域X上模糊劃分模糊熵。

定理3當(dāng)1

2）Ep（U;c）=0 ?U是硬劃分；

則

性質(zhì)2）、3）顯然成立。

若記熵函數(shù)h（u）=4u（1-u），則

為第j個類模糊集Aj的模糊熵，j=1,2,…,c，則

3）如果采用其他的熵函數(shù)，也可以得到類似的結(jié)果。

范九倫和吳成茂[3]基于模糊熵來定義聚類有效性函數(shù)：

顯然式（3）與式（4）有類似之處。式（3）中p=0即得式（4）。但強(qiáng)調(diào)2點(diǎn)：1）基于序關(guān)系得到公式（3）；2）參數(shù)p在聚類有效性分析中也起作用，給出參數(shù)p的初衷是克服劃分系數(shù)及其他類似的聚類有效性函數(shù)的缺陷。

3 模糊劃分模糊熵作為聚類有效性函數(shù)的實(shí)驗結(jié)果

文中采用3組不同的數(shù)據(jù)，對Ep（U;c）的聚類有效性進(jìn)行實(shí)驗。實(shí)驗所用數(shù)據(jù)如表1所示。它們都是適合作為聚類有效性分析的典型數(shù)據(jù)集。

表1 3組典型實(shí)驗數(shù)據(jù)Table 1 Three types of classical experiment data

對數(shù)據(jù)集Ⅰ，調(diào)用FCM算法在不同分類數(shù)目c下的情況見圖1至圖8，其中m=2,ε=10-4。

圖1 c=2的聚類結(jié)果

圖2 c=3的聚類結(jié)果

圖3 c=4的聚類結(jié)果

圖4 c=5的聚類結(jié)果

圖5 c=6的聚類結(jié)果

圖6 c=7的聚類結(jié)果

圖7 c=8的聚類結(jié)果

圖8 c=9的聚類結(jié)果

對數(shù)據(jù)集Ⅱ與Ⅲ，取m=2,ε=10-4調(diào)用FCM算法在不同分類數(shù)目c下的聚類情況略去。

對數(shù)據(jù)集Ⅰ、Ⅱ與Ⅲ，取p=1/n，ε=10-4，且m分別取1.5, 1.6, 1.7，1.8, 1.9, 2.0, 2.1, 2.2, 2.3, 2.4, 2.5時調(diào)用FCM算法在不同分類數(shù)目c下Ep（U;c）的取值情況做了計算。部分情況見表2～4。表中黑體部分對應(yīng)Ep（U;c）的最小值，相應(yīng)的c值即聚類算法決定的“最優(yōu)”分類數(shù)。

表2 數(shù)據(jù)集ⅠEp（U;c）的值Table 2 Values of Ep（U;c） for data Ⅰ

可以知道數(shù)據(jù)集Ⅰ真正的最優(yōu)分類數(shù)是6，由此可見此時Ep（U;c）在m=1.5時有效，在m=2.0和m=2.5時未得到最優(yōu)分類,得到的是次優(yōu)分類。

表3 數(shù)據(jù)集ⅡEp（U;c）的值Table 3 Values of Ep（U;c） for data Ⅱ

可以知道數(shù)據(jù)集Ⅱ真正的最優(yōu)分類數(shù)是5，由此可見,此時Ep（U;c）在m=1.7時有效，在m=2.0和m=2.3時未得到最優(yōu)分類,得到的是次優(yōu)分類。

表4 數(shù)據(jù)集Ⅲ Ep（U;c）的值Table 4 Values of Ep（U;c） for data Ⅲ

可以知道數(shù)據(jù)集Ⅲ真正的最優(yōu)分類數(shù)是4，由此可見，此時Ep（U;c）在m=1.6時有效，在m=2.0和m=2.4時未得到最優(yōu)分類,得到的是次優(yōu)分類。

4 結(jié)束語

基于序關(guān)系定義了數(shù)據(jù)集模糊劃分的模糊熵并將其作為模糊聚類有效性函數(shù)。從3個實(shí)驗數(shù)據(jù)集的模糊聚類有效性驗證來看，Ep（U;c）中的參數(shù)取p=1/n，也總存在合適的參數(shù)m（對數(shù)據(jù)據(jù)集Ⅰ, m=1.5;對數(shù)據(jù)集Ⅱ, m=1.7;對數(shù)據(jù)集Ⅲ，m=1.6）使得模糊劃分的模糊熵Ep（U;c）作為聚類有效性函數(shù)是有效、可行的。下一步，將考慮參數(shù)p與m的最優(yōu)組合問題。

[1]范九倫. 模糊聚類新算法與聚類有效性問題研究[D]. 西安：西安電子科技大學(xué), 1998: 52-77. FAN Jiulun. The studies on some new algorithms of fuzzy clustering and clustering validity [D]. Xian: Xidian University, 1998: 1-165.

[2]范九倫，吳成茂．可能性劃分系數(shù)和模糊變差相結(jié)合的聚類有效性函數(shù)[J]．電子與信息學(xué)報， 2002， 24（8）： 1017-1021. FAN Jiulun, WU Chengmao. Clustering validity function based on possibilistic partition coefficient combined with fuzzy variation [J]. Journal of Electronics and Information Technology, 2002， 24（8）： 1017-1021.

[3]范九倫，吳成茂．基于模糊熵的聚類有效性函數(shù)[J]. 模式識別與人工智能，2001，14（4）: 390-394. FAN Jiulun, WU Chengmao. Clustering validity function based on fuzzy entropy [J]. Pattern Recongnition and Artificial Intelligence, 2001，14（4）: 390-394.

[4]DUN J C. Some recent investigations of a new fuzzy partitions algorithm and its application to classification problems [J]. J Cybernet, 1974（4）: 1-15.

[5]DAVE R N. Validating fuzzy partition obtained through c-shells clustering [J]. Pattern Recognition Letters, 1996（ 17）: 613-623.

[6]ROBUBENS M. Pattern classification problems and fuzzy sets [J]. Fuzzy Sets Systems, 1978, 1: 239-253.

[7]BEZDEK J C, HARRIS J. Fuzzy partitions and relations—an axiomatic basis for clustering[J]. Fuzzy Sets and Systems, 1978（1）: 111-126.

[8]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms [M]. New York：Plenum Press, 1981: 105-133.

[9]PAL N R, BEZDEK J C. On cluster validity for fuzzy C-means model [J]. IEEE Trans Fuzzy Systems, 1995（3）: 370-379.

[10]ZHANG Huangxiang, LU Jin. Creating ensembles of classifiers via fuzzy clustering and deflection [J]. Fuzzy Sets and Systems, 2010（160）: 1790-1802.

[11]YU Jian, YANG Minshen, LEE E S. Sample-weighted clustering methods [J]. Computers and Mathematics with Applications, 2011（62）: 2200-2208.

[12]岳士弘，黃媞，王鵬龍. 基于矩陣特征值分析的模糊聚類有效性指標(biāo)[J]. 天津大學(xué)學(xué)報，2014, 47（8）: 689-696. YUE Shihong, HUANG Ti, WANG Penglong. Matrix eigenvalue analysis-based clustering validity index [J]. Journal of Tianjin University, 2014, 47（8）: 689-696.

[13]張大慶，徐再花. 一種新的模糊聚類有效性指標(biāo)[J]. 沈陽農(nóng)業(yè)大學(xué)學(xué)報， 2012, 14（5）: 636-639. ZHANG Daqing, XU Zaihua. A new validity index for fuzzy clustering [J]. Journal of Shenyang Agricultural University, 2012, 14（5）: 636-639.

[14]朱文婕，吳楠，胡學(xué)鋼. 一個改進(jìn)的模糊聚類有效性指標(biāo)[J]. 計算機(jī)工程與應(yīng)用， 2011, 45（5）: 206-209.

ZHU Wenjie, WU Nan, HU Xuegang. Improved cluster validity index for fuzzy clustering [J]. Computer Engineering and Applications, 2011, 45（5）: 206-209.

[15]胡春春，孟令奎，謝文君，等. 空間數(shù)據(jù)模糊聚類的有效性評價[J].武漢大學(xué)學(xué)報， 2007, 32（8）: 740-743. HU Chunchun, MENG Lingkui, XIE Wenjun, et al. Validity measure on fuzzy clustering for spatial data [J]. Journal of Wuhan University, 2007, 32（8）: 740-743.

[16]鄭弘亮，徐本強(qiáng)，趙曉慧，等. 新的模糊聚類有效性指標(biāo)[J]. 計算機(jī)應(yīng)用， 2014, 34（8）: 2166-2169. ZHENG Hongliang, XU Benqiang, ZHAO Xiaohui, et al. Novel validity index for fuzzy clustering [J]. Journal of Computer Applications, 2014, 34（8）: 2166-2169.

[17]王麗娜，馬曉曉. 一種改進(jìn)的模糊聚類有效性指標(biāo)[J]. 微電子學(xué)與計算機(jī), 2014, 31（4）: 68-74. WANG Lina, MA Xiaoxiao. An improved validity index for clustering [J]. Microelectronics and Computer, 2014, 31（4）: 68-74.

[18]張宇獻(xiàn)，劉通，董曉，等. 基于改進(jìn)劃分系數(shù)的模糊聚類有效性函數(shù)[J]. 沈陽工業(yè)大學(xué)學(xué)報，2014, 36（4）: 431-435. ZHANG Yuxian, LIU Tong, DONG Xiao, et al. Validity function for fuzzy clustering based on improved partition coefficient [J]. Journal of Shenyang University of Technology, 2014, 36（4）: 431-435.

[19]普運(yùn)偉，金煒東，朱明，等. 核模糊C均值算法的聚類有效性研究[J]. 計算機(jī)科學(xué)，2007, 34（2）: 207-210. PU Yunwei, JIN Weidong, ZHU Ming, et al. On cluster validity for kernelized fuzzy C-means algorithm [J]. Computer Science, 2007, 34（2）: 207-210.

[20]姚曉紅，任珂珂，趙花妮，等. 一種新的模糊聚類有效性指標(biāo)的驗證[J]. 洛陽理工學(xué)院學(xué)報， 2012, 22（3）: 76-79. YAO Xiaohong, REN Keke, ZHAO Huani, et al. The verification of a new fuzzy clustering validity index [J]. Journal of Luoyang Institute of Science and Technology, 2012, 22（3）: 76-79.

卿銘，男，1971年生，副教授，主要研究方向為智能信息處理、系統(tǒng)可信性分析，發(fā)表學(xué)術(shù)論文20余篇。

孫曉梅，女，1962年生，副教授，主要研究方向為組合最優(yōu)化。

A new clustering effectiveness function: fuzzy entropy of fuzzy partition

QING Ming1， SUN Xiaomei2

（1.School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China; 2. Department of Mathematical and Physical Science, Henan Institution of Engineering, Zhengzhou 451191, China）

In this paper, the determination that whether a fuzzy clustering analysis result is reasonable or not is decided by the effectiveness of fuzzy clustering and its core is the construction of fuzzy clustering effectiveness function. This paper proposed a new concept of fuzzy entropy for a fuzzy partition to describe fuzzy degree of a fuzzy partition based on an order relation. Fuzzy entropy for a fuzzy partition is also considered as a clustering effectiveness function because some existing fuzzy clustering effectiveness functions are based on fuzzy partition of data sets. The experiments demonstrated that it is reasonable and practicable to utilize fuzzy entropy for a fuzzy partition as the effectiveness function of a fuzzy clustering.

fuzzyC-means clustering; fuzzy entropy of fuzzy partition; clustering effectiveness; clustering analysis; fuzzy partition; fuzzy entropy; entropy function; fuzzy set

2014-10-08.

日期：2015-01-13.

中央高?；A(chǔ)研究基金資助項目（2682014ZT28）.

卿銘. E-mail：qingming@swjtu.edu.cn.

10.3969/j.issn.1673-4785.201410004.

http://www.cnki.net/kcms/detail/23.1538.TP.20150113.1130.006.html

TP O235

A

1673-4785（2015）01-0075-06

卿銘，孫曉梅.一種新的聚類有效性函數(shù)：模糊劃分的模糊熵[J]. 智能系統(tǒng)學(xué)報， 2015, 10（1）: 75-80.

英文引用格式：QING Ming，SUN Xiaomei. A new clustering effectiveness function: fuzzy entropy of fuzzy partition[J]. CAAI Transactions on Intelligent Systems, 2015, 10（1）: 75-80.