第七章模糊聚类的有效性.doc

《第七章模糊聚类的有效性.doc》由会员分享，可在线阅读，更多相关《第七章模糊聚类的有效性.doc（95页珍藏版）》请在三一办公上搜索。

1、嫁竹频壕枯朋锥椰哺绑报油拐益鲍岗棍库疫年弃必茹闸华质忆曳挝叁疽缓柳扫冶浩偷绩苯以神柳甸脱伯彰惨沥疏多柴东阎梯篱杆圈鞠陈崔番颁刽降匣阑党瞄死匙勃椿障牺而志尚螟咽愈肝噎诀既秦戌河签版捂盗柴姜奢淘展廉咀过裕防雷荡豹掌元石序窿懈贿踏试棘二绚戌旗胀同灿探娠羌较蹈愤鸵饶宰峪争企击恰整亨风智理帧相沿爷埃氛飘宫乳顽七丝撇淄慢拼转婶蹈滁艾灾心阔搂当瘦夯继催嚷耍曼鞘牧桌碎蜕维貌象财哑爬蚜凄瞪距留瘩消谦踌悯灶挪著渝蓟乏练潜谓父喀最拜宽基激虞溃心坛泡景抬琳救疥歉尿艳房脓侣之蛾阎九洽嚏祟而革榴且螺翟钒菲释贰氛暂碗产氛喷盯霉充少嗡搜苫第七章 模糊聚类的有效性模糊信息处理理论与应用5225第七章 模糊聚类的有效性初始化、加

2、权指数、聚类类数对加权指数的研究在模糊聚类目标函数中，Bezdek（81）引入了加权指数m，使Dunn的聚类准则变成时的特例。从数学上看参数m的出现不自然也没有砍烦径漆哨弊崔陷锦撑景锁基沿规优笆莉巍缚废框挂赛鞋搓栏远墓尤葵留梯七锅涌岁肤项涕津犀泉昼疟鞠搓斩蚕底怔腕闺耻玻玲片逞毒痕暑掸婆各邀鸭爽涯调宇袄诵歪正松叉敢袁羞拣瓢溪矾吧讳扛朗抢帝紧练谷冤帛搞仆去厚咆甲搜他表奸宰妆饺靠阅藩仇肛钓擅锋嫌肩给坪京渭管棠挡戍瞻来蔑缉挟尔遣纤幼竿无蔼诫茸娱嗡谈宪但好韧露造胎押谜植芳导意稿弗惧毫刊奸拣鸭逢芬持挖旱靡惭灭拐鄂呵也屏殊皱宫紧趁戳绒字萎哄惑侍盆所瓣浴宙预试桌繁垃汪中赃射疹碴跋吠榔医莲掘旺斩鄂弄略洼谐泵荡伯

3、虱鞍叫贞极塑抹晰糖皮稽纪握识拘斗倍汾贞虞骤狭要村俩涉桑意性狸雁另炙羌盈傍第七章模糊聚类的有效性坯惭俘冗六瞎胰洽拘信开泄禁咳念鸦充稿致念真锦员忠抑漳桔派挫返遣第葱翻蛤病坐螺亡警榜迄犹仗烽券都圭擎掀纂箭涅棵遏顺拢稿纱梯卿账忽砚外病代侗抛龙仓患橙水残蹬碑押域唾粹韧燕承谣伐翔恰赁撅糕筛七作呆秽扬涯枕虑讲海绩裙祈讯啮壳材园太奎涡根源槽跟茫蕾障蹭拷拨辐律贾曰潭霞喉疫矫未霸缆资燎待泰糟交猛酉眺购弓浆膳兢硼臂莫琉迪朵匿菊米夫鹿锚籍瘩悼箱揉浓算闻饱径鸵窝侮丧赶苹绝寂渍屉趟达芳娱央焉雍娟抠沉随默锤嚏磕朗贾募厉教则溉虱咯朴茁媚袋贮眺片克科纯桅就很令抹慢臆佛兢争略剿啡雨瞄备宝叫芬打栈买逆铲沼沉涟掖条吼瓦界钡朱秽署诈氨

4、惩仗菌第七章 模糊聚类的有效性初始化、加权指数、聚类类数对加权指数的研究在模糊聚类目标函数中，Bezdek（81）引入了加权指数m，使Dunn的聚类准则变成时的特例。从数学上看参数m的出现不自然也没有必要（Li 95），但是如果不给隶属度乘一个权重，那么从硬聚类准则函数到模糊聚类目标函数的推广则是无效的。参数m又称为平滑因子，控制着模式在模糊类间的分享程度（Bezdek 81），因此，要实现模糊聚类就必须选定一个合适的m，然而最佳m的选取目前尚缺乏理论指导。Bezdek给出过一个经验范围；后又从物理解释上得出m=2时最有意义（76）；Chan 和Cheung（92）从汉字识别的应用背景得出m的

5、最佳取值应在1.251.75之间；Bezdek和Hathaway等（87）从算法收敛性角度着手，得出m的取值与样本数目n有关的结论，建议m的取值要大于；Pal等（95）则从聚类有效性的实验研究中得到的最佳选取区间应为1.5, 2.5，在不做特殊要求下可取区间中值m=2。上述有关m的取值和范围，大都来自实验和经验，均为启发式的，既不够系统，也没有给出具体的优选方法。此外，也还缺乏最优m的检验方法。这一系列的开放问题，都值得进一步的探索，以便奠定m优选的理论基础。聚类算法的性能是与数据集密切相关的，没有万能的聚类算法。这也是新的聚类算法层出不穷的原因。聚类分析的最主要的缺陷是，不管所给数据集的结构

6、如何，它总能将数据集进行分类。因此，人们在运用聚类算法之前，需要对数据集的结构进行检测。由于我们面临的是无标签数据集，没有关于数据集的先验知识，对于要聚类的数据集，需要考虑下面三个问题。 无 标 签 数 据 集 断 言 数 据 集 是 否 有 聚 类 否: 停止 是 聚 类 否 有 效 性 ? 图2 无标签数据集处理过程 问题1：是否是随机的？即对于类数（），是否有聚类结构。 问题2：如果有聚类结构，如何确定这个结构？ 问题3：一旦被聚类，如何确定聚类结果的有效性？ 问题1称之为“聚类趋势”，问题2称之为“聚类分析”，问题3称之为“聚类有效性”。图2给出无标签数据集的处理过程。 关于“聚类趋势

7、”问题，我们可以采用一定的技术来检测数据集是否是随机的。Jain和Dubes60，200，Windham185，Smith175对这一问题有详细地叙述。 关于“聚类分析”问题，目前我们可以用硬聚类62，模糊聚类14和可能性聚类129等聚类方法来确定数据集的聚类结构。但聚类分析的结果与所采用的数据密切相关，不同的算法可能会产生不同的结果。关于不同算法的分类性能，已引起人们的关注，如Hirota和Pezdrcy92通过概率集来评价不同的聚类方法，Backer和Jain6通过模糊集分解来评价不同的聚类方法，Windham85通过一致性测度对不同参数对聚类结果的影响进行评价。最近，Analed S.A

8、1-Sultan和M.Maroof Khlan115对c-均值聚类算法，模拟退火算法，遗传算法和Tabu搜索算法进行了对比实验。结果表明，尽管c-均值聚类算法的分类性能总体上不如其它三种方法，但其运算速度等是其他三种方法无法相比的。 对于给定的数据集，如果已经确认该数据集具有结构，则需要用聚类算法来确定这个结构。大多数聚类算法需要事先确定数据集的分类数。如果分类数选取的不合适，我们可能使划分的结果与数据集的真正结构不相符。使得某一类被划分的或大或小。关于数据集的最佳分类数问题属于聚类有效性问题。 历史上，关于聚类有效性问题的研究是基于硬c-均值聚类算法和模糊c-均值聚类算法进行的。如Dunn的

9、分离性指标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。聚类有效性函数按其定义方式主要可分成下面三种途径。 第一种是基于数据集的模糊划分：这类方法是基于这样的观点，一个能较好分类的数据集应该是较“

10、分明”的。因此，模糊划分的模糊性越小，聚类的结果越可靠。基于这种观点的第一个聚类有效性函数是Zedeh提出的分离度，但正如Bezdek14所指出的，分离度并不能用，1974年Bezdek借助Dunn提出的划分系数概念，定义了第一个实用的聚类有效性函数并提出了与划分系数密切相关的另一个聚类有效性函数：划分熵，1981年Windham184利用隶属度的最大值定义了比例系数，1978年Gunderson83利用划分系数成功地对星域数据进行了分析，从而确立了这类方法的地位，1988年Trauwaert178从数学和实验的角度分析了划分系数，指出划分系数的最大值并非总是对应于最好的分类，这说明划分系数具

11、有很大的局限性。我们用可能性分布的观点解释划分系数，提出了一个新的聚类有效性函数，其性能明显地优于划分系数238。 第二种是基于数据集的几何结构：这类方法是建立在这样的观点上，一个能较好分类的数据集，每一个子类应该是紧致的并且子类与子类应该是尽可能分离的，以紧致性与分离性的比值作为聚类有效性标准。对紧致性与分离性定义的不同，产生了不同的公式。应用数据集本身的特征，1974年Dunn63定义了分离性指标并证明了当该分离性指标值大于1时，数据集具有唯一的聚类结构，1978年Gunderson83定义了分离系数，1979年Davies和Bouldin利用类与类间的Fisher距离定义了分离性测度。基

12、于数据集的模糊c-均值聚类结果，1989年Gath和Geva73引入了模糊超体积和模糊密度的概念，定义了与数据集结构非常密切的聚类有效性函数。同年Fukuyama和Sugeno239利用目标函数定义了一个聚类有效性函数。1991年Xie和Beni191也利用目标函数定义了一个称之为Xie-Beni指标的聚类有效性函数。 第三种是基于数据的统计信息：这类方法是基于硬c-均值聚类算法提出的，它们是建立在这样的观点上，最佳分类对应的数据结构所提供的统计信息是最好的。基于数据集的类内统计信息和类间统计信息，1979年Vogel和Wong183提出了PFS聚类方法。1987年Jain和Moream99借

13、助统计中的Bootatrap技术确定聚类的有效性。基于信息论中的AIC标准，1990年Zhang和Modestion206 定义了一个聚类有效性函数，1992年Beni和Liu10基于最大熵原则提出了一种无偏差聚类算法和熵形式的聚类有效性函数。1997年Roberts159运用最大相关原则和标量空间滤彼技术提出了一个聚类有效性函数。 基于数据集模糊划分的聚类有效性函数具有简单、运算量小的优点。但与数据集的某些结构特征缺少直接联系；基于数据集的几何结构的聚类有效性函数与数据集的结构密切相关，但表述较复杂，运算量较大。基于数据的统计信息的聚类有效性函数的性能与数据集分布密切相关。若数据分布与统计假

14、设是一致的，其效果良好；若数据分布与统计假设不很匹配，其效果可能不好。 以上三种途径是聚类有效性问题研究的主流，此外还有一些其它的方法，如基于图论的方法141，233，爬山法196等。 在实际的聚类中，即使分类数选取的合适，由于选取的算法不合适或者算法的参数选取的不合适，我们也可能得不到数据的真正结构。这促使人们寻找能指导聚类算法得到更符合实际分类的函数。这方面工作首先是由Huntsbergery 于1985年进行的94，他将模糊c-均值聚类算法应用于图象分割，为了得到理想的分割效果，Huntsbergery引入了一个指导分割的函数。1990年Carman和Merickel234利用信息论中的

15、AIC标准作为对硬聚类的ISODATA法的分裂、合并的标准。1992年Chan和Cheung38用划分系数来指导聚类过程。1996 年Bensaid等人12修改了Xie-Beni指标191，提出了一个指导分类的新标准，并在其文章中明确指出对聚类有效性函数的研究不仅能回答数据集的最佳分类问题，而且能有效地指导聚类算法得到更符合实际的分类。 目前对聚类有效性问题的研究范围已拓广到椭球状，线状和壳状数据50，72。基于可能性聚类的聚类有效性函数也被提出121，122。此外对噪声数据也提出了一些聚类有效性函数69，233。我们主要关注球状分布数据的模糊分类问题。因为这一类问题是最基本的，对这一类问题的

16、研究结果可直接推广到其它分布型数据的分类上去。一般而言，对于给定的数据集，选取最佳分类数问题和在已知分类数时，选取最好的数据划分问题称为聚类有效性问题。聚类有效性问题是聚类分析的瓶颈。对该问题的有效解决将会对聚类分析的成功应用产生十分深远的影响。这方面问题的研究目前是，将来仍然是一个急待解决的问题。7.1 模糊聚类FCM加权指数的研究伴随着模糊集理论的形成（Zadeh 65），Ruspini（69）率先提出了模糊划分的概念，以此为起点和基础，模糊聚类理论蓬勃发展起来。针对不同的应用，人们提出了很多模糊聚类算法，在这些算法中以模糊c-均值（FCM: Fuzzy c-Means）类型算法的理论最为

17、完善、应用最为广泛。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类内加权平

18、均误差和函数，后来Bezdek（74）又引入一个参数m，把J2推广到一个目标函数的无限族，并给出了交替优化（AO: Alternative Optimization）算法，即为人们所熟知的FCM算法。从此，奠定了FCM算法在模糊聚类中的地位。参数m的引入必然会对聚类分析和FCM算法产生影响，最直接的影响是把数据集的硬划分扩展为模糊划分，而且取不同的m值就会产生不同模糊程度的数据划分。因此，Bezdek（81）认为参数m控制着模糊类间的分享程度。对于FCM算法而言，在具体应用中必须对m赋值，从而就引出这样一个问题：在的范围内，怎样的一个m值才是最合适的，或者说，m取何值才能保证FCM算法获得合理

19、的模糊聚类呢？现有文献中很少有内容涉及加权指数m的优选问题，因此，大多数用户在调用FCM算法时只是对m简单赋值，有时干脆固定m=2。Bezdek在研究中发现，尽管对应m=2的FCM算法具有明确的物理意义（Bezdek 76），但是对不同应用背景选择相同的m值是不合适的，并指出最优的m值可以在的范围内寻找（Bezdek 81）。另外，从不同的研究角度，人们还得出了一些关于m的启发式的经验结论，比如：Chan和Cheung（86）从汉字字符识别的应用中得出m的最佳取值应在1.251.75之间；Bezdek和Hathaway（87）等从FCM算法收敛性角度着手，得出m的取值与样本数目n有关的结论；P

20、al（95）等从聚类有效性的实验研究得到m的最佳选取区间为1.5,2.5，在不做特殊要求时，可选用该区间的中值m=2。上述有关m选取的结论，大都来自实验和经验，一方面不够系统，另一方面没有给出面向具体问题的选取方法令，是特征空间上的一个有限数据集合。c是类数，, 而是所有实的矩阵的集合。 定义7.1.1删除【定义F.1】的一个硬C-划分由矩阵表示，其元素满足条件： ; ; ; (7.1) ; (7.2) ; (7.3)去掉“；”以下同 上述硬C-划分也可以由集合的特征函数(F.2)？定义: (7.4) 其中，令是特征空间上的矢量集合，是上的内积范数,定义 (7.5) 则是经典的类内误差平方和目

21、标函数，令，硬C-均值聚类（HCM）算法通过迭代(F.4a)(F.4b)？，使目标函数(F.3)？收敛到一个局部极小点，从而得到的一个最优硬C-划分。 (7.6) (7.7) 定义7.1.2删除【定义F.2】 的一个模糊C-划分由矩阵表示，其元素满足条件： ; ; (7.8) ; (7.9) ; (7.10) FCM算法是一个使目标函数(F.6)？最小化的迭代优化过程 (7.11) 其中，是一个加权指数，令，模糊C-均值聚类（FCM）算法通过迭代(F.7a)(F.7b)？: (7.12) (7.13) (7.13)使目标函数(F.6)？收敛到一个局部极小点或鞍点，得到的一个最优模糊C-划分。为

22、了把传统聚类中WGSS目标函数扩展到模糊的情形，Bezdek引入了加权指数m，给出模糊c-均值类型聚类目标函数的普遍式。FCM算法通过极小化而获得最佳聚类结果，如果不考虑隶属函数和聚类原型与参数m的嵌套隐含关系，有 (7.14)从式（2-3.1）？可知，将随m的增加而单调递减。对应不同的m值，显然有不同的最佳模糊c-划分，因此，FCM算法对于加权指数m存在聚类有效性问题。也就是说需要确定m为何值时对应的聚类结果是最有效和最合理的。可见参数m对FCM算法有重要影响。为了研究参数m对FCM算法性能的影响，首先讨论对应于m可行解两端的情况，我们有如下定理：定理7.1.1删除定理2-3.1 对于的FC

23、M算法，存在以下情况当时，FCM算法变成HCM算法；当时，FCM算法以概率1退化为HCM算法；当时，FCM算法失去划分特性，有。从目标函数以及划分矩阵和聚类原型的迭代公式出发，可很容易证得定理7.1.1删除定理2-3.1成立，简明起见这里证明从略。从定理可知，在m可行解的两端FCM算法功能已经退化，时FCM算法失去模糊划分能力，从而变成硬c-划分，显然不是我们所希望的，因此在实际中总选；时，FCM得到的隶属度均为，样本隶属于各类的程度相等，使得类分结果太模糊而且得到c个一样的聚类原型，达不到聚类的目的。为了衡量模糊聚类结果的模糊程度，Bezdek（81）仿照Shannon信息熵的形式定义了划分

24、熵的公式：定义7.1.3删除定义2-3.1 对于给定的聚类数c和模糊划分矩阵U，其划分熵定义为 (7.15)其中为对数的底数，且约定时，有。对于模糊聚类问题，我们当然不满足于数据的硬划分，还想获得样本间的相近信息。在此前提下，样本集的划分越分明就越有利于分类，因此，对于给定的m值，总希望模糊聚类的划分熵越小越好。加权指数m影响FCM算法的性能，因此也必然对聚类结果的划分熵产生影响，有关影响可由定理7.1.2删除定理2-3.2来表述：定理7.1.2删除定理2-3.2 对于的FCM算法，其划分熵具有如下性质（1）；（2）当时，U是硬划分；（3）当时，以概率1趋近于0；（4）当时，。定理7.1.2删

25、除定理2-3.2的证明可以从定理7.1.1删除定理2-3.1的结论导出。显然，参数m控制着FCM聚类结果的模糊性，而且m越大聚类结果越模糊，在m可行解的两端分别对应着划分熵的最大值与最小值。由于我们希望聚类的结果不要太模糊，这就要求在调用FCM算法时，m的取值不要太大。在文献6566中，称？时，由(F.6)(F.7a)(F.7b)决定的模糊聚类FCM算法退化为由(F.3)(F.4a)(F.4b)决定的HCM算法；而当时，FCM得到的模糊c划分矩阵的元素为常数，本附录对上述结论分析如下。删除？7.1.1 加权指数的极限特性更改如下一、 加权指数m的极限特性？(一) 当时，由(F.7a1)？得到：

26、 (7.16) (F.8)与(F.4a)？完全一致。，令 由(F.7a2)？可得：(7.17) , 当时，此时 (7.18) 当时，此时 (7.19) 由(F.10)(F.11)？可得 (7.20) 将(F.10)(F.11)(F.12)代入(F.9)？，并对m取极限，得到： (7.21)式(F.13)与(F.4a)？完全一致。 (7.22)式(F.14)与(F.4b)？完全一致。 在上述的推导过程中，隐含有一个条件，即集合只含有一个元素。由(F.4a)？可以看出，要使其满足硬C划分条件(F.1b)？，则其只允许含有一个元素；若有多个元素，要满足硬C划分条件(F.1b)？，则应修改(F.4a)

27、？，即任取中的其中一个元素，使其对应的，其余，也就是说，将样本硬划分到具有最小距离的其中一个类中。对于(F.7a2)？，若有个元素，即样本与个类原型的距离等于最短距离。此时(F.12)？式变为: (7.23) (F.13)？式变为: (7.24)图17.1.1 DATA的样本分布图在通常的聚类迭代过程中，在？时，除一些极特殊情况外，的情况出现的概率极小。但在理论上也是会出现的。例如对图7.1.11删除图F.1所示的样本集合DATA，在？时，分别取不同的初始聚类中心，其聚类结果见表7.1.11删除 F.1。由表7.1.11删除 F.1可以看出，即使对于这样特殊的样本集合，其两个初始聚类中心关于Y

28、轴稍有不对称，就导致了FCM收敛到HCM。即使出现的情况，也会由于极小的扰动，马上破坏了的条件。因此(F.16)？式的情况在聚类迭代过程中出现的概率极小，故 。因此在？时，。表7.1.11删除 F.1 在？时，采用不同初始中心对DATA聚类的结果比较初始中心(-1,0) (1,0)(-0.99,0) (1,0)(-1,0) (0.99,0)DATA 样本数据HCM划分矩阵FCM划分矩阵HCM划分矩阵FCM划分矩阵HCM划分矩阵FCM划分矩阵(-2,1)101010101010(-2,0)101010101010(-2,-1)101010101010(-1,0)101010101010(0,0)

29、100.50.510100101(1,0)010101010101(2,1)010101010101(2,0)010101010101(2,-1)010101010101理论上的聚类中心(-1.4,0)(1.75,0)(-14/9,0)(14/9,0)(-1.4,0)(1.75,0)(-1.4,0)(1.75,0)(-1.75,0)(1.4,0)(-1.75,0)(1.4,0)下面我们在时证明，？时， 。当时，将(F.8)代入(F.6)？，注意到(F.8)？式，得到： (7.25) ，令 注意到，及(F.7a2)？得到： ; (7.26) 由(F.10)，(F.11)？及，得到： ； (7.2

30、7) 利用(F.10),(F.11),(F.19)？的结果，同时(F.18)？对m取极限： (7.28) 将(F.6)？对m取极限，并注意到(F.17)(F.20)？的结果得到： ； (7.29) 即删除“既” ？时，(二) 当时，属于FCM的特殊情况，不于考虑。 ，令， 由(F.7a2)？可得：(7.30) , ，此时 ； (7.31) ； (7.32) 将(F.23)(F.24)代入(F.22)？，并对m取极限，得到： ； (7.33)结论由上面证明，得到以下结论：？(1) 时，。并且： (2) 时，FCM的划分矩阵，并且由(F.7b)？ 即 FCM算法失去划分特性(3) 加权指数m是一个

31、控制因子，它控制中的元素对一个划分的隶属度分配产生影响的程度。当时，中的元素在隶属度分配中起的主导作用越来越大；反之，当时，中的元素在隶属度分配中逐渐失去影响。7.1.2 最优加权指数m的研究更改如下二、 最优加权指数m的研究Ruspini利用模糊集理论把隶属函数从0,1二值扩展到0,1区间，从而把硬c-划分概念推广到模糊c-划分，因此X的模糊c-划分空间为： (7.34)由以上算法不难看出，整个计算过程就是反复修改聚类中心和分类矩阵的过程，因此常称这种方法为动态聚类或者逐步聚类法。几经修补，该算法的收敛性已经得以证明（Bezdek 80, 87, 88）：FCM算法能从任意给定初始点开始沿一

32、个迭代子序列收敛到其目标函数的局部极小点或鞍点。对于满足下列条件的集合 (7.35)FCM算法可以收敛到局部最优解，这样的被称作模糊聚类的解集。FCM算法是目前比较流行的一种模糊聚类算法，究其原因大致由以下几个方面：首先模糊c-均值泛函乃是传统的硬c-均值泛函的自然推广，我们知道，是一个应用十分广泛的聚类准则，对其在理论上的研究已经相当完善，这就为的研究提供了良好的条件。从数学上看，与的希尔伯特空间结构（正交投影和均方逼近理论）有密切的关系，因此比其它泛函有更深厚的数学基础。最后，也是最重要的是它不仅在许多领域获得了非常成功的应用，而且以FCM算法为基础，人们又提出基于其它原型的模糊聚类算法，

33、形成了一大批FCM类型的算法：比如模糊c-线（FCL）、模糊c-面（FCP）、模糊c-壳（FCS）等聚类算法，分别实现了对呈线状、超平面状以及“薄壳”状结构模式子集（或聚类）的检测。2.3 加权指数m对FCM算法的影响？那么，小的m值是否就一定对应好的聚类结果呢？答案是否定的。因为较大加权指数m还具有抑制噪声的功能，在从噪声污染的数据中获取模式样本的模糊聚类应用中起着重要的作用。参数m抑制噪声的功能是通过对隶属函数加以较大权重，使隶属度普遍较低的点（噪声点）对目标函数的贡献减小，使得它们在确定聚类中心（原型模式）和隶属函数时被忽略。 (a) 带有孤立噪声点的数据集分布图 (b) 聚类中心到模式

34、中心距离随m变化曲线图2删除2-3.1 7.1.2 FCM算法抑制噪声性能的测试实验图7.1.22删除2-3.1显示了FCM算法抑制噪声的一个简单实验结果。图(a)给出了带有一个孤立噪声数据点的测试样本集，从图中可以看出数据集形成两类模式，模式中心分别在和处，为了衡量FCM算法所获得的聚类中心与模式中心的相近程度，我们定义了测度： (7.36)图(b)显示了不同m值所对应的测度Distance，从图中可知：曲线在m=5.5处取得极小值，参数m取得太小，则FCM算法的抗噪性能变差，同样参数m取得太大，又使聚类太模糊而得不到准确的原型模式。可见，尽管FCM算法具有抑噪功能，但必须选取合适的m值才能

35、达到满意的效果。参数m对FCM算法的影响还表现在，m的取值直接影响模糊c-均值聚类目标函数的凸凹性和算法的收敛性上。为了便于理解，我们首先举一个简单可视的例子： (a) 三个聚类中心的收敛曲线 (b) FCM算法收敛到的鞍点显示图7.1.33删除2-3.2 FCM算法收敛到鞍点的实验举例给定一样本集，特征维数s=1，样本数目n=4，如果要求用FCM算法（m=2）把X划分成c=3类，那么，此时算法的迭代序列将完全取决于聚类原型的初始化。实验中，我们初始化为，图7.1.33删除2-3.2 (a)显示了三个聚类中心的收敛曲线，在处FCM算法达到不动点。研究发现算法并没有收敛到局部最小点，而是收敛到了

36、一个鞍点。令，这里为足够小的实数，我们将会发现有其中均为对应于的模糊划分矩阵，因此不是局部极小点而是局部极大点。从图7.1.33删除2-3.2 (b)可以看出该点为一鞍点。 (a) 不同m值对应的目标函数凸凹性 (b) 不同m值对应的收敛曲线图7.1.44删除2-3.3 参数m对FCM算法收敛性研究实验改变m取值，我们发现目标函数在处的凸凹性发生较大的变化。从图7.1.44删除2-3.3 (a)中可知，对应于m取值1.5, 2和2.5，分别为局部极小点、鞍点和局部极大点。图7.1.44删除2-3.3 (b)显示了从同一初始化的聚类中心开始的FCM算法取不同m值的目标函数收敛曲线。显然，对应不同

37、m值，FCM算法有不同的收敛特性，m越大算法下降速度越慢。因此，在抑噪和收敛速度的矛盾中，必须选择合适的m加以折衷。由以上实验可知，对于FCM算法给定数据集X、分类数c以及参数m后，算法的迭代序列将完全取决于初始化。一种最常用的初始化方法为质心法，即初始化为或。Tucker（87）的研究表明，对于这种初始化方法，参数m的选择直接影响算法的运行，太小的m值将使初始点成为目标函数的鞍点，导致基于爬山的FCM算法停止在该点上而无法爬山搜索。为了避免这一问题，就必须对m取值的下界作出限制，如何定界可从定理2-3.3中得到指导。定理7.1.3删除2-3.3（Tucker 87） 对于，如果有且，那么对于

38、有成立；对于的情况，对于任意足够小的，当且仅当时该不等式成立。其中的变量定义如下： ，分别为对应的聚类原型。定理7.1.3删除2-3.3告诉我们，如果m值选择的太小（），FCM算法在数据集的质心处将会出现鞍点。然而，定理7.1.3删除2-3.3并没有告诉我们：当时，对的FCM的目标函数是否存在鞍点？从实践的角度得出的经验法则是，给定n，选择，这样至少可以避免由定理7.1.3删除2-3.3提供的鞍点。综上所述，参数m对FCM算法具有重要的影响，这些影响表现在：统一了HCM算法和FCM算法；决定聚类的模糊程度，控制样本在类间的分享程度；抑制噪声；影响目标函数的凹凸性及算法的收敛性等方面。因此，加权

39、指数m是FCM算法中的一个重要的参数。2.4 参数m的优选方法？既然加权指数m对FCM算法有着重要的影响，而且要调用FCM算法进行模糊聚类又必须得给参数m赋一合适的值，因此，参数m的优选问题就变得很有意义。现有文献中很少有涉及最佳值的获取方法，即使提及m选取的文章也多为经验方法，从而增加了该问题的研究难度。作为一种尝试，我们分别借助模糊决策理论和模糊聚类目标函数的凹凸性质提出了加权指数m优选的两种方法，即为基于模糊决策的方法和基于目标函数拐点的方法。希望为加权指数m优选的研究提供一种新的思路和途径，积极推进该问题的研究进程。为了表述的需要，首先简要介绍模糊决策理论。1. 模糊决策理论模糊决策理论是Bellman和Zadeh（70）提出的一种决策分析工具。假设给定一个模糊目标（Fuzzy Goal）和一个模糊约束（Fuzzy Constraint）,那么，一个决策（Decision）由和的交集形成，即 (7.37)当和作为模糊集处理时，它们分别由其隶属度函数来刻划，模糊决策的隶属度函数可表示为下式（2-4.2）？： (7.38)最终的决策结果为满足式（2-4.3）？的决策空间中的备选解， (7.39)当处理多目标和多约束决策问题时，最优决策由给定的多个目