第七章 模糊聚类的有效性
初始化、加权指数、聚类类数 对加权指数m的研究
在模糊聚类目标函数{Jm:1?m??}中，Bezdek（81）引入了加权指数m，使Dunn的聚类准则变成m?2时的特例。从数学上看参数m的出现不自然也没有必要（Li 95），但是如果不给隶属度乘一个权重，那么从硬聚类准则函数到模糊聚类目标函数的推广则是无效的。参数m又称为平滑因子，控制着模式在模糊类间的分享程度（Bezdek 81），因此，要实现模糊聚类就必须选定一个合适的m，然而最佳m的选取目前尚缺乏理论指导。
Bezdek给出过一个经验范围1.1?m?5；后又从物理解释上得出m=2时最有意义（76）；Chan 和Cheung（92）从汉字识别的应用背景得出m的最佳取值应在1.25~1.75之间；Bezdek和Hathaway等（87）从算法收敛性角度着手，得出m的取值与样本数目n有关的结论，建议m的取值要大于n(n?2)；Pal等（95）则从聚类有效性的实验研究中得到m的最佳选取区间应为[1.5, 2.5]，在不做特殊要求下可取区间中值m=2。
上述有关m的取值和范围，大都来自实验和经验，均为启发式的，既不够系统，也没有给出具体的优选方法。此外，也还缺乏最优m的检验方法。这一系列的开放问题，都值得进一步的探索，以便奠定m优选的理论基础。
聚类算法的性能是与数据集密切相关的，没有万能的聚类算法。这也是新的聚类算法层出不穷的原因。聚类分析的最主要的缺陷是，不管所给数据集的结构如何，它总能将数据集进行分类。因此，人们在运用聚类算法之前，需要对数据集的结构进行检测。由于我们面临的是无标签数据集，没有关于数据集的先验知识，对于要聚类的数据集X??x1,?,xn?，需要考虑下面三个问题。
无 标 签 数 据 集
断 言
数 据 集 是 否 有 聚 类 否: 停止
是
聚 类
否
有 效 性 ?
图2 无标签数据集处理过程
问题1：X是否是随机的？即对于类数c（1?c?n），X是否有聚类结构。 问题2：如果X有聚类结构，如何确定这个结构？ 问题3：一旦X被聚类，如何确定聚类结果的有效性？
问题1称之为“聚类趋势”，问题2称之为“聚类分析”，问题3称之为“聚类有效性”。图2给出无标签数据集的处理过程。
关于“聚类趋势”问题，我们可以采用一定的技术来检测数据集是否是随机的。Jain和Dubes[60，200]，Windham[185]，Smith[175]对这一问题有详细地叙述。
关于“聚类分析”问题，目前我们可以用硬聚类[62]，模糊聚类[14]和可能性聚类[129]等聚类方法来确定数据集的聚类结构。但聚类分析的结果与所采用的数据密切相关，不同的算法可能会产生不同的结果。关于不同算法的分类性能，已引起人们的关注，如Hirota和Pezdrcy[92]通过概率集来评价不同的聚类方法，Backer和Jain[6]通过模糊集分解来评价不同的聚类方法，Windham[85]通过一致性测度对不同参数对聚类结果的影响进行评价。最近，Analed S.A1-Sultan和M.Maroof Khlan[115]对c-均值聚类算法，模拟退火算法，遗传算法和Tabu搜索算法进行了对比实验。结果表明，尽管c-均值聚类算法的分类性能总体上不如其它三种方法，但其运算速度等是其他三种方法无法相比的。
对于给定的数据集，如果已经确认该数据集具有结构，则需要用聚类算法来确定这个结构。大多数聚类算法需要事先确定数据集的分类数。如果分类数选取的不合适，我们可能使划分的结果与数据集的真正结构不相符。使得某一类被划分的或大或小。关于数据集的最佳分类数问题属于聚类有效性问题。
历史上，关于聚类有效性问题的研究是基于硬c-均值聚类算法和模糊c-均值聚类算法进行的。如Dunn的分离性指标[63]，Davies和Bouldin的分离性测度[52]，Vogel和Wong提出的PFS聚类方法[183]等都是基于硬c-均值聚类算法的。基于模糊c-均值聚类算法的有效性函数有Dunn的划分系数[15]，Bezdek的划分熵[14，15]，Windham的比例系数[184，185]，Gunderson的分离系数[83]， Xie-Beni指标[191]，Bensaid指标[12]等。
Dubes和Jain对1980年以前的聚类有效性函数研究工作给予了很好地评述[58，59，60］。聚类有效性函数按其定义方式主要可分成下面三种途径。
第一种是基于数据集的模糊划分：这类方法是基于这样的观点，一个能较好分类的数据集应该是较“分明”的。因此，模糊划分的模糊性越小，聚类的结果越可靠。基于这种观点的第一个聚类有效性函数是Zedeh提出的分离度，但正如Bezdek[14]所指出的，分离度并不能用，1974年Bezdek借助Dunn提出的划分系数概念，定义了第一个实用的聚类有效性函数并
提出了与划分系数密切相关的另一个聚类有效性函数：划分熵，1981年Windham[184]利用隶属度的最大值定义了比例系数，1978年Gunderson[83]利用划分系数成功地对星域数据进行了分析，从而确立了这类方法的地位，1988年Trauwaert[178]从数学和实验的角度分析了划分系数，指出划分系数的最大值并非总是对应于最好的分类，这说明划分系数具有很大的局限性。我们用可能性分布的观点解释划分系数，提出了一个新的聚类有效性函数，其性能明显地优于划分系数[238]。
第二种是基于数据集的几何结构：这类方法是建立在这样的观点上，一个能较好分类的数据集，每一个子类应该是紧致的并且子类与子类应该是尽可能分离的，以紧致性与分离性的比值作为聚类有效性标准。对紧致性与分离性定义的不同，产生了不同的公式。应用数据集本身的特征，1974年Dunn[63]定义了分离性指标并证明了当该分离性指标值大于1时，数据集具有唯一的聚类结构，1978年Gunderson[83]定义了分离系数，1979年Davies和Bouldin利用类与类间的Fisher距离定义了分离性测度。基于数据集的模糊c-均值聚类结果，1989年Gath和Geva[73]引入了模糊超体积和模糊密度的概念，定义了与数据集结构非常密切的聚类有效性函数。同年Fukuyama和Sugeno[239]利用目标函数定义了一个聚类有效性函数。1991年Xie和Beni[191]也利用目标函数定义了一个称之为Xie-Beni指标的聚类有效性函数。 第三种是基于数据的统计信息：这类方法是基于硬c-均值聚类算法提出的，它们是建立在这样的观点上，最佳分类对应的数据结构所提供的统计信息是最好的。基于数据集的类内统计信息和类间统计信息，1979年Vogel和Wong[183]提出了PFS聚类方法。1987年Jain和Moream[99]借助统计中的Bootatrap技术确定聚类的有效性。基于信息论中的AIC标准，1990年Zhang和Modestion[206] 定义了一个聚类有效性函数，1992年Beni和Liu[10]基于最大熵原则提出了一种无偏差聚类算法和熵形式的聚类有效性函数。1997年Roberts[159]运用最大相关原则和标量空间滤彼技术提出了一个聚类有效性函数。
基于数据集模糊划分的聚类有效性函数具有简单、运算量小的优点。但与数据集的某些结构特征缺少直接联系；基于数据集的几何结构的聚类有效性函数与数据集的结构密切相关，但表述较复杂，运算量较大。基于数据的统计信息的聚类有效性函数的性能与数据集分布密切相关。若数据分布与统计假设是一致的，其效果良好；若数据分布与统计假设不很匹配，其效果可能不好。
以上三种途径是聚类有效性问题研究的主流，此外还有一些其它的方法，如基于图论的方法[141，233]，爬山法[196]等。
在实际的聚类中，即使分类数选取的合适，由于选取的算法不合适或者算法的参数选取的不合适，我们也可能得不到数据的真正结构。这促使人们寻找能指导聚类算法得到更符合实际分类的函数。这方面工作首先是由Huntsbergery 于1985年进行的[94]，他将模糊c-均值聚类算法应用于图象分割，为了得到理想的分割效果，Huntsbergery引入了一个指导分割的函数。1990年Carman和Merickel[234]利用信息论中的AIC标准作为对硬聚类的ISODATA法的分裂、合并的标准。1992年Chan和Cheung[38]用划分系数来指导聚类过程。1996 年Bensaid
等人[12]修改了Xie-Beni指标[191]，提出了一个指导分类的新标准，并在其文章中明确指出对聚类有效性函数的研究不仅能回答数据集的最佳分类问题，而且能有效地指导聚类算法得到更符合实际的分类。
目前对聚类有效性问题的研究范围已拓广到椭球状，线状和壳状数据[50，72]。基于可能性聚类的聚类有效性函数也被提出[121，122]。此外对噪声数据也提出了一些聚类有效性函数[69，233]。我们主要关注球状分布数据的模糊分类问题。因为这一类问题是最基本的，对这一类问题的研究结果可直接推广到其它分布型数据的分类上去。
一般而言，对于给定的数据集，选取最佳分类数问题和在已知分类数时，选取最好的数据划分问题称为聚类有效性问题。聚类有效性问题是聚类分析的瓶颈。对该问题的有效解决将会对聚类分析的成功应用产生十分深远的影响。这方面问题的研究目前是，将来仍然是一个急待解决的问题。
7.1 模糊聚类FCM加权指数m的研究
伴随着模糊集理论的形成（Zadeh 65），Ruspini（69）率先提出了模糊划分的概念，以此为起点和基础，模糊聚类理论蓬勃发展起来。针对不同的应用，人们提出了很多模糊聚类算法，在这些算法中以模糊c-均值（FCM: Fuzzy c-Means）类型算法的理论最为完善、应用最为广泛。
c-均值类型的算法最早是从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，从此类内平方误差和（WGSS: Within-Groups Sum of Squared Error）J1成为聚类目标函数的普遍形式。为极小化该目标函数而采取的Pikard迭代优化方案就是著名的硬c-均值（HCM）算法和ISODATA（Iterative Self-Organizing Data Analysis Technique A）算法（Duda 73）。模糊划分概念提出后，Dunn（73）首先把WGSS函数J1扩展到J2——类内加权平均误差和函数，后来Bezdek（74）又引入一个参数m，把J2推广到一个目标函数的无限族?Jm,1?m???，并给出了交替优化（AO: Alternative Optimization）算法，即为人们所熟知的FCM算法。从此，奠定了FCM算法在模糊聚类中的地位。
参数m的引入必然会对聚类分析和FCM算法产生影响，最直接的影响是把数据集的硬划分扩展为模糊划分，而且取不同的m值就会产生不同模糊程度的数据划分。因此，Bezdek（81）认为参数m控制着模糊类间的分享程度。对于FCM算法而言，在具体应用中必须对m赋值，从而就引出这样一个问题：在1?m??的范围内，怎样的一个m值才是最合适的，或者说，m取何值才能保证FCM算法获得合理的模糊聚类呢？
现有文献中很少有内容涉及加权指数m的优选问题，因此，大多数用户在调用FCM算法时只是对m简单赋值，有时干脆固定m=2。Bezdek在研究中发现，尽管对应m=2的FCM算法具有明确的物理意义（Bezdek 76），但是对不同应用背景选择相同的m值是不合适的，并指出最
优的m值可以在1.1?m?5的范围内寻找（Bezdek 81）。另外，从不同的研究角度，人们还得出了一些关于m的启发式的经验结论，比如：Chan和Cheung（86）从汉字字符识别的应用中得出m的最佳取值应在1.25~1.75之间；Bezdek和Hathaway（87）等从FCM算法收敛性角度着手，得出m的取值与样本数目n有关的结论；Pal（95）等从聚类有效性的实验研究得到m的最佳选取区间为[1.5,2.5]，在不做特殊要求时，可选用该区间的中值m=2。上述有关m选取的结论，大都来自实验和经验，一方面不够系统，另一方面没有给出面向具体问题的选取方法
令X?{xs1,x2,Lxn}?R，是特征空间Rs上的一个有限数据集合。c是类数，2?c?n, 而
Rcn是所有实的c?n矩阵的集合。
定义7.1.1X的一个硬C-划分由矩阵U?[ucnik]?R表示，其元素满足条件：
uik?{0，1}; 1?i?c; 1?k?n; (7.1) c
?uik?1; 1?k?nlimx?? (7.2)
i?1n
?uik?0; 1?i?c (7.3) k?1上述硬C-划分也可以由集合的特征函数(F.2)定义:
ui(xk)?uik???1；xk?Si?0；otherwise (7.4) 其中S1?S2?LSc?X， ?i?j，Si?Sj??
令V?{v1，v2，Lvsc}?R是特征空间Rs上的矢量集合，?A是Rs上的内积范数,定义 c J1(U,V)???n(uik)xk?v2ik?1i?1A (7.5) 则J1是经典的类内误差平方和目标函数，令dik?xk?v2iAb2?4ac ，硬C-均值聚类
（HCM）算法通过迭代(F.4a)(F.4b)，使目标函数(F.3)收敛到一个局部极小点，从而得到X的
一个最优硬C-划分U?[u?ik]。
u?1；minj{djk}ik??dik??0；otherwise；1?i?c；1?k?n； (7.6)
第七章模糊聚类的有效性
