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

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

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

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

X={x₁,x₂,···,x_n}⊂R^s是数据集，n是数据的个数，c是事先确定的数据集的分类数目(1<c<n，c的最大取值限通常为)，d_ij=|| x_i-v_j||是样本点x_i与聚类中心或聚类原型(clustering prototype) v_j的某个距离度量(反映了样本x_i与v_j的失真度)，v_j∈R^s(1≤j≤c)。u_ij是第i个样本属于第j个中心的隶属度，则模糊聚类问题可表示成下面的数学规划问题^[1]：

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

1)初始化: 给定聚类类别数c(2≤c≤n，n为样本点个数)、模糊加权指数m，设定迭代停止阈值ε，随机初始化划分矩阵U⁽⁰⁾，设置迭代计数器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)随机初始化聚类原型显然没有随机初始化划分矩阵方便，而且也没有什么客观的理由。

文中基于序关系定义模糊划分的模糊熵反映了一个模糊划分的模糊程度。用F(X)表示X上所有模糊集，对任意A,B∈F(X)，称A≤_M^FB当且仅当，其中分别为A、B的补集，∩表示交集运算,∧是取小运算。

定义1 若U₁=[A₁,A₂,···,A_c]，U₂=[B₁,B₂,···,B_c]是X上的2个模糊c划分，且满足A_j≤_M^FB_j，j=1,2,···,c，则称U₁是U₂的分明修改，记为U₁^FMU₂。

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

定理1 (FP(X),_M^F)满足以下性质：

1)(FP(X),_M^F)是拟序集不是偏序集；

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

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

证明 1)设U₁=[u_ij]，U₂=[v_ij]。

由定义1，U_1M^FU₂当且仅当任意j=1,2,···,c，A_j≤_M^FB_j。

即U_1M^FU₂当且仅当任意i=1,2,···,n，j=1,2,···,c，min{u_ij,1－u_ij}≤min{v_ij,1－v_ij}≤1/2。

对X上的任意模糊划分U,U_M^FU显然成立。若U_1M^FU2，U_2M^FU3，则U_1M^FU₃。所以，(FP(X),_M^F)是一个拟序集。显然(FP(X),_M^F)不是一个偏序集，因为对任意2个不同的硬划分U₁、U₂，都有U_1M^FU₂且U_2M^FU₁，但U₂≠U₁。

2)证明略。

3)由于U₁、U₂是模糊划分，即，，所以，(FP(X),_M^F)的最大元是[1/c]而不是[1/2]。由于[1/c]是(FP(X),_M^F)最大元，所以[1/c]是最模糊的划分。

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

1)E(U,c)=0当且仅当U是硬划分；

2) 若U₁和U₂都是模糊c划分，且U_1M^FU2，则E(U₁ ,c)≤ E(U₂,c)。

若定义

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

定理2 E_p(U;c) 是有限论域X上模糊划分模糊熵。

定理3 当1<c<n时，E_p(U;c)有如下性质：

1) 0≤E_p(U;c)≤；

2) E_p(U;c)=0U是硬划分；

3) 。

证明 1) 因为E_p(U;c)≥0明显成立，只须证E_p(U;c)≤。用拉格朗日乘数法： ，

则 ，

解出，1≤i≤n,1≤j≤c为唯一驻点，显然E_p(U;c)≤E_p([];c)=。

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

若记熵函数h(u)=4u(1－u)，则

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

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

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

聚类有效性准则 Ω_c表示U∈M_fc的“最优”的有限集合，若存在(U^*,c^*)满足E_p(U^*;c^*)= 则(U^*,c^*)为最佳的有效性聚类，c^*为最好的分类数目。

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

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

图 1 c=2的聚类结果Fig. 1 Clustering result for c=2

图选项

图 2 c=3的聚类结果Fig. 2 Clustering result for c=3

图选项

图 3 c=4的聚类结果Fig. 3 Clustering result for c=4

图选项

图 4 c=5的聚类结果Fig. 4 Clustering result for c=5

图选项

图 5 c=6的聚类结果Fig. 5 Clustering result for c=6

图选项

图 6 c=7的聚类结果Fig. 6 Clustering result for c=7

图选项

图 7 c=8的聚类结果Fig. 7 Clustering result for c=8

图选项

图 8 c=9的聚类结果Fig. 8 Clustering result for 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下E_p(U;c)的取值情况做了计算。部分情况见表 2~4。表中黑体部分对应E_p(U;c)的最小值，相应的c值即聚类算法决定的“最优”分类数。

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

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

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

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