一种新的聚类有效性函数：模糊划分的模糊熵

卿铭，孙晓梅

（1.西南交通大学 数学学院，四川 成都 600031; 2. 河南工程学院 数学与物理科学系,河南 郑州 451191）



一种新的聚类有效性函数：模糊划分的模糊熵

卿铭1，孙晓梅2

（1.西南交通大学 数学学院，四川 成都 600031; 2. 河南工程学院 数学与物理科学系,河南 郑州 451191）

模糊聚类分析结果是否合理的问题属于模糊聚类有效性判定课题，其核心是模糊聚类有效性函数的构造。文中基于序关系定义了模糊划分模糊熵来描述模糊划分的模糊程度。考虑到现有的一类有效的模糊聚类有效性函数就是基于数据集的模糊划分的，因此文中也用模糊划分的模糊熵作为聚类有效性函数。实验表明，模糊划分的模糊熵作为模糊聚类的有效性函数是合理的、可行的。

模糊C均值聚类；模糊划分的模糊熵；聚类有效性；聚类分析；模糊划分；模糊熵；熵函数；模糊集

聚类是一个在人类认识世界的过程中产生的古老问题。在面对纷繁的大千世界时，关注事物间的相似性并以此来区别不同的事物，对于人类来说是一种清晰而直观的思路。而每个概念的最初形成无不借助于事物间的聚类分析。因此聚类分析的研究不仅具有重要的理论意义，而且具有重要的工程应用价值和人文价值。对于给定的数据集，首先要判断有无聚类结构，这属于聚类趋势研究的课题；如果已经确认有聚类结构，则需要用算法来确定这些结构，这属于聚类分析的研究课题；得到结构后，需要分析、判断聚类的结果是否合理，这属于聚类有效性研究的课题[1]。

传统的聚类分析是一种硬划分。它将每个待辨识的对象严格地划分到某个类中，其聚类结果具有非此即彼的性质。而实际上大多数对象并没有严格的属性，它们在形态和类属方面存在着中介性，往往具有亦此亦彼的性质，因此适合进行软划分。而模糊集理论的提出，对聚类分析软划分的发展起到了重要作用。用模糊的方法来处理聚类问题，称之为模糊聚类分析，是当前聚类分析研究的主流。

关于聚类有效性问题的研究通常是基于硬C均值聚类算法和模糊C均值聚类算法进行的。在模糊聚类有效性函数中，基于数据集的模糊划分的有效性函数是很重要的一类，其观点是：好的分类聚类应对应于数据集较分明的划分，划分的分明性越好，分类的不确定性就越小。尽管以Dunn[4]的划分系数为代表的聚类有效性函数取得一定的效果然而仍存在缺陷：划分系数有随类数增加而递减的趋势。为克服这一缺点，范九伦[2- 3]、Dave[5]和Robubens[6]作了很多的工作。但仍未较好解决这一难题——聚类有效性函数随类数增加而递减（增）的趋势。其他一些学者也对模糊聚类的有效性做了深入的讨论[7-20]，但都不完善，有继续改进的余地。

文中借鉴好的聚类应对应于数据集较分明的划分，划分的分明性越好，分类的不确定性就越小的学术思想，基于序关系定义模糊划分的模糊熵来反映模糊划分的模糊程度，并以其作为聚类有效性函数，实验证明模糊划分的模糊熵作为模糊聚类的有效性函数是合理、有效的。

1 FCM算法

这里

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

下面给出文中采用的从随机初始化模糊划分矩阵开始迭代FCM算法步骤[8-9]。

1）初始化: 给定聚类类别数c（2≤c≤n，n为样本点个数）、模糊加权指数m，设定迭代停止阈值ε，随机初始化划分矩阵U（0），设置迭代计数器b=0。

2）计算或更新聚类原型模式矩阵P（b）:

3）更新模糊划分矩阵U（b+1）;

4）若||U（b+1）-U（b）||<ε，输出划分矩阵U和聚类原型P等聚类信息，算法结束；否则，令b=b+1，转向2）。其中||·||为合适的矩阵范数。

算法从随机初始化模糊划分矩阵开始迭代，这样做的原因主要有3个：1）标准FCM算法本身并不能保证一定收敛到全局最优点，算法可能收敛于某个极值点或局部最优点，由于模糊划分矩阵的随机性选取，通过对FCM算法的多次调用，可能会发现全局最优点。2）若从初始化聚类原型模式矩阵开始迭代，初始聚类原型的选取有很多种方法，考虑到算法的通用性，很难抉择一个优秀的选取方案，并且一旦选取方案（这里不包括随机初始化聚类原型）确定了，迭代过程就随之固定，算法可能始终收敛于某个极值点或局部最优点。3）随机初始化聚类原型显然没有随机初始化划分矩阵方便，而且也没有什么客观的理由。

2 模糊划分的模糊熵

记X上的所有模糊划分为FP（X）。[a]∈FP（X）表示每个元素都是常数a的划分矩阵。

2）硬划分是其极小元，任何2个硬划分都可比，且在同一个等价类中；

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

证明1）设U1=[uij]，U2=[vij]。

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

2）证明略。

定义2一个实函数E:FP（X）→R+称为有限论域X上模糊c划分的模糊熵（简称模糊划分模糊熵），如果E满足：

1）E（U,c）=0当且仅当U是硬划分；

若定义

式中：参数p>0。

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

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

定理3当1

2）Ep（U;c）=0 ⟺U是硬划分；

则

性质2）、3）显然成立。

若记熵函数h（u）=4u（1-u），则

为第j个类模糊集Aj的模糊熵，j=1,2,…,c，则

3）如果采用其他的熵函数，也可以得到类似的结果。

范九伦和吴成茂[3]基于模糊熵来定义聚类有效性函数：

显然式（3）与式（4）有类似之处。式（3）中p=0即得式（4）。但强调2点：1）基于序关系得到公式（3）；2）参数p在聚类有效性分析中也起作用，给出参数p的初衷是克服划分系数及其他类似的聚类有效性函数的缺陷。

3 模糊划分模糊熵作为聚类有效性函数的实验结果

文中采用3组不同的数据，对Ep（U;c）的聚类有效性进行实验。实验所用数据如表1所示。它们都是适合作为聚类有效性分析的典型数据集。

表1 3组典型实验数据Table 1 Three types of classical experiment data

对数据集Ⅰ，调用FCM算法在不同分类数目c下的情况见图1至图8，其中m=2,ε=10-4。

图1 c=2的聚类结果

图2 c=3的聚类结果

图3 c=4的聚类结果

图4 c=5的聚类结果

图5 c=6的聚类结果

图6 c=7的聚类结果

图7 c=8的聚类结果

图8 c=9的聚类结果

对数据集Ⅱ与Ⅲ，取m=2,ε=10-4调用FCM算法在不同分类数目c下的聚类情况略去。

对数据集Ⅰ、Ⅱ与Ⅲ，取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时调用FCM算法在不同分类数目c下Ep（U;c）的取值情况做了计算。部分情况见表2～4。表中黑体部分对应Ep（U;c）的最小值，相应的c值即聚类算法决定的“最优”分类数。

表2 数据集ⅠEp（U;c）的值Table 2 Values of Ep（U;c） for data Ⅰ

可以知道数据集Ⅰ真正的最优分类数是6，由此可见此时Ep（U;c）在m=1.5时有效，在m=2.0和m=2.5时未得到最优分类,得到的是次优分类。

表3 数据集ⅡEp（U;c）的值Table 3 Values of Ep（U;c） for data Ⅱ

可以知道数据集Ⅱ真正的最优分类数是5，由此可见,此时Ep（U;c）在m=1.7时有效，在m=2.0和m=2.3时未得到最优分类,得到的是次优分类。

表4 数据集Ⅲ Ep（U;c）的值Table 4 Values of Ep（U;c） for data Ⅲ

可以知道数据集Ⅲ真正的最优分类数是4，由此可见，此时Ep（U;c）在m=1.6时有效，在m=2.0和m=2.4时未得到最优分类,得到的是次优分类。

4 结束语

基于序关系定义了数据集模糊划分的模糊熵并将其作为模糊聚类有效性函数。从3个实验数据集的模糊聚类有效性验证来看，Ep（U;c）中的参数取p=1/n，也总存在合适的参数m（对数据据集Ⅰ, m=1.5;对数据集Ⅱ, m=1.7;对数据集Ⅲ，m=1.6）使得模糊划分的模糊熵Ep（U;c）作为聚类有效性函数是有效、可行的。下一步，将考虑参数p与m的最优组合问题。

[1]范九伦. 模糊聚类新算法与聚类有效性问题研究[D]. 西安：西安电子科技大学, 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]范九伦，吴成茂．可能性划分系数和模糊变差相结合的聚类有效性函数[J]．电子与信息学报， 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]范九伦，吴成茂．基于模糊熵的聚类有效性函数[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]岳士弘，黄媞，王鹏龙. 基于矩阵特征值分析的模糊聚类有效性指标[J]. 天津大学学报，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]张大庆，徐再花. 一种新的模糊聚类有效性指标[J]. 沈阳农业大学学报， 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]朱文婕，吴楠，胡学钢. 一个改进的模糊聚类有效性指标[J]. 计算机工程与应用， 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]胡春春，孟令奎，谢文君，等. 空间数据模糊聚类的有效性评价[J].武汉大学学报， 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]郑弘亮，徐本强，赵晓慧，等. 新的模糊聚类有效性指标[J]. 计算机应用， 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]. 微电子学与计算机, 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]张宇献，刘通，董晓，等. 基于改进划分系数的模糊聚类有效性函数[J]. 沈阳工业大学学报，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]普运伟，金炜东，朱明，等. 核模糊C均值算法的聚类有效性研究[J]. 计算机科学，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]姚晓红，任珂珂，赵花妮，等. 一种新的模糊聚类有效性指标的验证[J]. 洛阳理工学院学报， 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年生，副教授，主要研究方向为智能信息处理、系统可信性分析，发表学术论文20余篇。

孙晓梅，女，1962年生，副教授，主要研究方向为组合最优化。

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.

中央高校基础研究基金资助项目（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

卿铭，孙晓梅.一种新的聚类有效性函数：模糊划分的模糊熵[J]. 智能系统学报， 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.