万方数据第２９卷第２期北京交通大学学报Ｖｏｌ．２９ Ｎｏ． ２文章编号：１６７３－０２９１（２００５）０２－００１７－０５一种模糊聚类算法归类的研究李翠霞，于剑（北京交通大学计算机与信息技术学院，北京１０００４４）摘要：模糊Ｃ均值（ＦＣＭ）算法是模式识别领域应用最广的聚类算法之一但是ＦＣＭ算法存在很多缺点，其中以对噪声数据敏感，鲁棒性较差最为突出．针对这种情况，Ｌｅｅ于１９９４年提出了一种所谓的改进模糊Ｃ均值算法一Ｌｅｅ＇ｓ算法．但是本文证明了Ｌｅｅ＇ｓ算法并不是一种真正意义上的模糊Ｃ均值改进算法，而是Ｋｒｉｓｈｎａｐｕｒａｍ和Ｋｅｌｌｅｒ于１９９３年所提出的ＰＣＭ算法的一种特珠情况．数值实验进一步证明了我们的结论．这时合理地使用模糊聚类算法提供了一定的理论依据．关键词：聚类；模糊Ｃ均值（ＦＣＭ）算法；隶属度；权重指数；目标函数中图分类号：ＴＰ１８文献标识码：Ａ Ｓｔｕｄｙ ｏｎ ｔｈｅ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆＡ Ｋｉｎｄ ｏｆ Ｆｕｚｚｙ Ｃｌｕｓｔｅｒｉｎｇ ＡｌｇｏｒｉｔｈｍＬＩ Ｃｕｉ－ｘｉａ，ＹＵ Ｊｉａｎ（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １０００４４， Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ： Ｆｕｚｚｙ Ｇｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｗｉｄｅｌｙ ｕｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｐａｔｔｅｎｒｒｅｃｏｇｎｉｔｉｏｎ． Ｈｏｗｅｖｅｒ， ＦＣＭ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｌｏｔ ｏｆ ｄｒａｗｂａｃｋｓ． Ａｍｏｎｇ ｔｈｅｓｅ ｄｒａｗｂａｃｋｓ， ｂｅｉｎｇ ｓｅｎｓｉ－ｔｉｖｅ ｔｏ ｔｈｅ ｎｏｉｓｅ ｉｓ ｔｈｅ ｍｏｓｔ ｏｕｔｓｔａｎｄｉｎｇ． Ｉｎ ｏｒｄｅｒ ｔｏ ｏｖｅｒｃｏｍｅ ｔｈｉｓ ｄｒａｗｂａｃｋ， Ｌｅｅ ｐｒｏｐｏｓｅｄ ａ ｍｏｄｉｆｉｅｄＦＣＭ ａｌｇｏｒｉｔｈｍ－Ｌｅｅ＇ｓ ａｌｇｏｒｉｔｈｍ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ ｗｅ ｗｉｌｌ ｐｒｏｖｅ ｔｈａｔ Ｌｅｅ’ｓ ｍｏｄｅｌ ｉｓｎ＇ｔ ａ ｋｉｎｄ ｏｆ ＦＣＭａｌｇｏｒｉｔｈｍ， ｂｕｔ ａ ｓｐｅｃｉａｌ ｃａｓｅ ｏｆ ＰＣＭ ｗｈｉｃｈ ｗａｓ ｐｒｏｐｏｓｅｄ ｂｙ Ｋｒｉｓｈｎａｐｕｒａｍ＆Ｋｅｌｌｅｒ ｉｎ １９９３． Ｍｏｒｅ－ｏｖｅｒ， ｔｈｅ ｎｕｍｅｒｉｃａｌ ｅｘｐｅｒｉｍｅｎｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｏｕｒ ｃｏｎｃｌｕｓｉｏｎ．Ｋｅｙ ｗｏｒｄｓ： ｃｌｕｓｔｅｒｉｎｇ； ｆｕｚｚｙ ｃ－ｍｅａｎｓ（ＦＣＭ） ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｍｅｍｂｅｒｓｈｉｐ； ｗｅｉｇｈｔｉｎｇ ｅｘｐｏｎｅｎｔ；ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ 随着互联网技术的发展和计算机处理能力的同意义下相似性较低．目前，聚类分析已被广泛地应不断提升，处理海量数据成了目前计算机的主要任用在模式识别、特征提取、图像分割、古生物类别分务之一如何把海量数据很好的进行归类以发现知析、市场研究和Ｗｅｂ网上的文档分类等很多领域．识也成了很多学科领域的研究重点．和简单的分类正因为聚类分析应用广泛， 所以各种不同的聚相比，聚类根据“物以类聚”的原则，按照数据间的相类算法层出不穷．在众多的聚类算法中，最早由研究似程度进行区分和分类．在这个过程中，事先并不清者提出的聚类方法是硬划分方法，其中以Ｃ均值算楚每个数据的类别，是一种无监督的分类过程．其目法最为有名．Ｃ均值算法中的隶属度不是０就是１，的是要获得一个划分，这些划分将一组数据集合分也就是说，硬Ｃ均值算法会把每个待处理的对象严成几个子集，每个子集为一类，划分的标准是同类的格地划分到某个类中，而现实世界中数据的归类有数据在某种意义下相似性较高，不同类的数据在相时并没有如此严格的界限．Ｚｅｄｅｈ所提出的模糊集收稿日期：２００５－０１－０１基金项目：国家自然科学基金资助项目（６０３０３０１４）作者简介：李翠霞（１９７８－），女，河南焦作人，硕士生，ｅｍａｉｌ ： ｇｙｌｉｙｉｎｇ）１２６． ｃｏｍ于剑（１ ９６９－），男，山东淄博人，教授，博士．北京交通合理论为解决这一问题提供了有力的工具．人们开始用隶属度来刻画界限并不鲜明的划分问题．模糊聚类方法就是在此基础上发展起来的．这种类型的聚类方法用隶属度来描述样本隶属的不确定性，能够比较客观地反映现实世界．其中，由Ｄｕｎｎ首先提出，之后又被Ｂｅｚｄｅｋ加以推广的模糊Ｃ均值（Ｆｕｚｚｙｃ－ ｍｅａｎｓ， ＦＣＭ）算法〔‘〕是被实践证明的最有效的方法之一 ＦＣＭ算法本身也存在一些缺点，其中以对噪声数据敏感尤为突出．为克服该缺点，有很多学者进行了相应研究，并提出了不少新算法，例如Ｋｒｉｓｈｎａｐｕ－ｒａｍ和Ｋｅｌｌｅｒ［２１基于可能性理论所提出的可能Ｃ均值（Ｐｏｓｓｉｂｉｌｉｓｔｉｃ‘一ｍｅａｎｓ， ＰＣＭ）算法，以及Ｌｅｅ Ｄ］于１９９４年在改变ＦＣＭ算法约束条件的基础上所提出的算法（以下称该算法为Ｌｅｅ＇ｓ算法）等等．由于ＦＣＭ算法中数据点在类之间的隶属度之 和等于１，对于包含ｎ个数据点的待分类集合来说，所有隶属度的和就是ｎ．在条件相同的情况下，Ｌｅｅ＇ｓ算法中所有隶属度的和也为ｎ．两者都根据有关隶属度的约束条件来求得隶属度和类中心的更新迭代公式．表面上看起来，Ｌｅｅ＇ｓ算法和ＦＣＭ算法中的类中心之间都是互相影响的，彼此并不．故而很多学者认为Ｌｅｅ＇ｓ算法是ＦＣＭ型的算法［］’．但是，我们可以从理论上证明，Ｌｅｅ＇ｓ算法并不是真正意义上的ＦＣＭ算法的改进算法，而是ＰＣＭ算法的一种特殊模型．本文作者将利用理论和实验两种手段证明 Ｌｅｅ＇ｓ算法应该属于ＰＣＭ型的算法，这将有助于聚类算法使用者们正确地认识Ｌｅｅ＇ｓ算法，使其能够根据实际应用需要合理地选择聚类算法．１ ＦＣＭ算法 ＦＣＭ算法是Ｄｕｎｎ于１９７４年提出的，之后又被Ｂｅｚｄｅｋ加以推广．为了更好的描述ＦＣＭ算法．我们做如下假设：Ｘ｛ｘｌ＋ｘ２，…，ｘ，｝ＣＲ，是一个数据集，Ｕ＝｝Ｉ斤ｃｘｎ Ｅ Ｍｆｍ是一个隶属度矩阵，｛ＶＩ，ｖ２，二．，ｖｃ｝是‘个聚类中心，ｖｉ Ｅ Ｒ＇，２（ｃ镇ｎ．ＦＣＭ算法的目标函数如下Ｊ，ｎ（。，ｖ）＝艺Ｅｕ ：－ｄ （ｘｋ，。‘）（１）－１式中，习ｕｉｋ＝１， ｕ，ｋ －Ｃ（０，１），ｔ／ ｋ，ｄ （ｘｋ，ｖｉ）＝｝｝ｘ＊一ｖ川２（以下记做ｄｉｋ，若未做特殊说明，都与此定义相同），ｍ通常叫做权重指数．ＦＣＭ算法即是求出使目标函数Ｉｍ达到最小值 万方数据大学学报第２９卷的隶属度矩阵Ｕ＝Ｉｕ；ｋ｛ｃｘ二与类中心ｖ＝ Ｉｖ１｝Ｖ２｝…，ｖｃ｝，ＶｋＣ－Ｉｋ｝１镇ｋ镇ｎ｝，ＶｉＥ Ｉｉ！１镇ｉ镇ｃ｝，ｘ；属于模糊集合Ｘ，的隶属度为ｕ；ｋ．初始时，类中心和隶属度矩阵都是随机产生的，之后根据如下更新规则对其进行迭代更新ｎｕＸｋＶｉ＝（ｉ＝１，２，…，。）（２ａ）艺 ｕｍ１ 止立ｒ ．ｌ １１／ｍ一１艺一ｉ＝１‘“Ｊｋ 护｝Ｊ（ｉ＝１，２，。；ｋ＝１，２，…，ｎ）（２ｂ）因此，ＦＣＭ算法的基本步骤可描述如下．步骤１指定算法中的参数，包括类数目。，权重指数ｍ，最大迭代次数丁和ｒＧｉｌ值：．步骤２初始化隶属度矩阵Ｕ， 使其满足约束条件Ｘｕｉｋ＝１，。二Ｅ （０ ，１）．ｉ＝１ 步骤３使用式（ ２ａ）计算。个聚类中心Ｖｉ （１镇ｉ镇ｃ）．步骤４计算新的目标函数值Ｊ． （ｕ， ｖ）．如果它与上一次目标函数值之差小于闭值。或者迭代次数大于Ｔ，算法停止；否则，用式（２ｂ）重新计算隶属度矩阵Ｕ，返回步骤３．从以上的分析可以看出，ＦＣＭ算法简单，实现 起来也比较容易．目标函数采用的是欧氏距离，具有比较直观的几何意义．但是，正因为它采用了欧氏距离，所以只适于发现球状的簇．习 ｕｉｋ＝１的条ｉ＝１ 件假设各个数据点的影响力相同．在这种条件下，点ｘ＊隶属于模糊集合Ｘ１的程度还要受到该点隶属于其他模糊集合Ｘ， （ｌ二１，２，…，。，且ｌ＃１）程度的影响，因此也间接受到类数目的影响．换言之，ＦＣＭ中的隶属度事实上描述的是点隶属于某一类的相对程度，并非点隶属于该类的绝对程度．这样做虽然有一定的道理，但却使得各个类中心之间互相影响，并不相互，一个类中心的变化会影响到其他的类中』Ｌ＂．因此，ＦＣＭ算法对噪声数据非常敏感．当数据中包含噪声和孤立点时，很可能会给噪声和孤立点的隶属度赋予一个较大的值，而导致聚类效果不好．对于ＦＣＭ算法而言，不能区分“证据相等”和“一无所知”．即使两个数据点都是不规则点，ＦＣＭ算法也不能区分不规则的程度，文献【３］．虽然ＦＣＭ算法引人了权重指数来实现模糊化划分，在某种程度上可以很好地反映现实情况，但是算法本身第２期李翠霞等：一种模糊聚类算法归类的研究的效果受ｍ的影响也较大，近来很多学者对ｍ的选择问题进行了研究，详细内容可参考文献〔５，６］．为了克服ＦＣＭ算法对噪声数据敏感的缺点， 文献中提出了很多新的算法．ＰＣＭ算法就是众多新算法中的一种．３ Ｌｅｅ＇ ｓ算法Ｌｅ ｅ于１９９４年提出了一种改进的模糊Ｃ均值算法．Ｌｅｅ＇ｓ算法的目标函数为Ｊ（ｕ，ｖ）＝习ＥＵＰｉｋｋ＝１ ｉ二１（长Ｕ２ ＰＣＭ算法 ＰＣＭ算法放松了对隶属度归一化的要求，改变＝ｎ．类中心这里，Ｖ ｉ，ｋ，。二翔，艺艺ｕｉｋｉ＝１ ｋ＝１一士Ｔ 刀１万方数据了隶属度函数的约束条件，对噪声数据有较好的处理能力．ＰＣＭ算法中，各个数据点的隶属度只需满足大于零的条件，并且在产生隶属度和类中心更新迭代公式时，也没有归一化的约束条件．通过这种方法产生的各个类中心之间相互，即：某一类中心的改变并不会影响到其他的类中心．因此，ＰＣＭ算法中的隶属度可以解释为数据点属于某一类的绝对程度的值．ＰＣＭ算法的目标函数如下 Ｊ（ｕ，。）一艺艺ｕ ｄ；ｋ十习＇７ｉ名（１一。二）！＝１盖＝１（３） 这里，０镇ｕｉｋ成１， ｝ｉ是一个合适的正整数． 利用拉格朗日乘子法，可以得到使得式（３）取最小值的必要条件如下月 乙 ｕｉｍｋｘｋｋ＝１ ｖｉ＝（４ａ） ＼－ｌ －ｒ －， ｕｉ＿＿ｍｋｋ＝１ ｕｉ ｋ＝［１＋（ｊＺ ｌｄｉｋ）１／（ｍ－１）］一‘（４ｂ）其中，Ｋｒｉｓｈｎａｐｕｒａｍ和Ｋｅｌｌｅｒ还给出了，‘的定义为 艺 ｕ ｋｄｉｋ，‘＝Ｋ ｋ＝１ｎＫ＝１ （５） ＰＣＭ算法首次把可能性理论运用于聚类，可以较好地处理噪声数据．但是，它也存在一定的缺点．由于ＦＣＭ算法中各个类中心之间互相影响，所以产生重合类中心的概率很小．而对于ＰＣＭ算法，情况就截然不同了．ＰＣＭ算法中各个类中心之间相互，彼此并不影响，易于产生重合的类中心．显然，此时产生的结果是不理想的结果，我们并不期望这种情况发生．文献【７］中对ＰＣＭ的这一缺点进行了，详细描述．也有一些研究者提出了其他的聚类算法，如文献「８，９］中所提到的ＷＰＣＭ算法，这些聚类算法的目标函数及更新公式与式（３）一式（５）相似，我们称这类算法为ＰＣＭ型算法．隶属度ｕ；的更新公式如下 ｎ ｕ黔ｋ Ｖ１＝（ １１ｌａ， ｕ ｋ ｄｎ １ｉｋ‘ｉ（一ｍ）了‘、７，ｂ艺又ｄｌｉｋｌ（‘一’走二１ ｉ＝１ 本文如果能够证明Ｌｅｅ＇ｓ算法的目标函数与ＰＣＭ型算法的目标函数等价，并且隶属度和类中心的更新迭代等式也分别与ＰＣＭ型算法的相同，那么就可以证明Ｌｅｅ＇ｓ算法是ＰＣＭ型的算法．把式（ ７ｂ）代人到式（７ａ）中去，可以得到如下等式ｎＵ Ｕｋ习ｄｍｉｋ（‘一ｍ ）ｘｋ公 ｉ＝Ｒ＝一、，ａｍ／（１－ｍ）（８）艺 ｕｍ‘“动ｋ二１ 得知，同时使用式（７ａ）和式（７ｂ）进行迭代与只用式（８）进行迭代完全相同．下边来分析ＰＣＭ型算法的目标函数和类中心及隶属度的更新公式．ＰＣＭ型算法的目标函数一般为如下形式， 见文献［９一１２］Ｊ（ ｕ，ｖ）＝习习ｕ ｋｄｉｋ＋ｆ（ｕｉｋ）（９）ｋ＝１ ｉ＝１式中，ｆ（ｕ动是ｕ二的函数．如果取ｆ（ ｕｚｋ ）＝一Ｅ又ｍｕ＝ｋ，那么就变成了如下形式Ｊ（ｕ，。） Ｅ Ｅｕ ｐ．一ｚ Ｅｍ ｕ；ｋ（ １０）ｋ＝１ ｚ＝１利用拉格朗日乘子法， 可求得式（１０）取最小值的必要条件为＝ｄ１／沃（１一ｍ）（１１）类中心ｖ、的迭代与式（７ａ）相同，如果把式（１１）代到式（７ａ）中去，那么式（７ａ）就变成了与式（８）完全相同的形式，也就是说，对于同一数据集合，若ｄ＊定义相同，ｍ取值也相同，玫ｅ’ｓ算法中类中心的更新公北京交通大学学报第２９卷式与（４ａ）是完全一样的．可以证明， 在式（１１）成立的条件下，最小化式表１实验１结果Ｔａｂ． ｌ Ｒｅｓｕｌｔｓ ｏｆ Ｔｅｓｔ １（１０）和最小化Ｌｅｅ＇ｓ算法的目标函数式（６）也等价．初始类中心类中心万方数据在此，将以目标函数为式（１０），隶属度更新公式为式（１１），类中心更新公式为式（７ａ）的聚类算法称作ＰＣＭ１算法． 综上所述，Ｌｅｅ＇ｓ算法模型的目标函数、迭代过程和ＰＣＭ算法的一种特殊模型一ＰＣＭ１算法的目标函数、迭代过程分别等价，换句话说，Ｌｅｅ＇ｓ算法模型是ＰＣＭ型的算法，而非改进的ＦＣＭ算法．４实验结果分析 下边通过实验来验证以上的结论．为了验证本文提出的观点，分别对Ｉｒｉｓ数据和人为数据进行了实验．在做实验时，ＦＣＭ算法的目标函数和迭代分别采用第１节中给出的式（１）和式（２ａ）与式（２ｂ）；ＰＣＭ算法的目标函数和迭代分别采用第２节中给出的式（３）和式（４ａ）与式（４ｂ）， Ｘ７２采用式（５）的定义；Ｌｅｅ＇ｓ算法的目标函数和迭代分别采用式（６）和式（８） ， ＰＣＭ１算法的目标函数和迭代分别采用第３节中给出的式（１０）和式（８）．实验１在本实验中， 采用Ｉｒｉｓ数据作为待聚类的数据集合．Ｉｒｉｓ数据集合中包含３类，每一类有５０个样本点，其中有两个类的样本点之间有重合．每一样本点有４个属性特征．本实验中只取前三维属性，权重指数ｍ取值为２，迭代次数为１００次，误差取为０．００００１，类别个数为３．图１为Ｉｒｉｓ数据分布图，从中可以清楚地看到数据的分布情况，图１ Ｉｒｉｓ数据分布图Ｆｉ ｇ． １ Ｉｉｒｓ ｄａｔａ ｄｉｓｔｉｒｂｕｔｉｏｎ ｆｉｇｕｒｅ 表１列出了实验结果．从表１中可看出，ＦＣＭ算法的结果基本上可以代表数据的结构，输出了３个类中心，而ＰＣＭ算法得到的却是３个重合的类中心，同样，当Ｌｅｅ＇ｓ算法的初始类中心与我们所推导出的ＰＣＭ１算法相同时，得到了与ＰＣＭ１算法完全相同的３个重合的类中心，这与前边的推断一致．（５．７１１３，３．０５４０，３．５９０８）（５．００３２，３．４０１６，１．４８７０）（５．８６５１，３．０４９２，３．７８１５）（５．８７４２，２．７６０４，４．３８２７）（５．９４４９，３．０８６９，３．８２５６）（６．７９３６，３．０５４５，５．６４４３）ＰＣＭ（５．８５６１，３．０４５９，３．８４４５）（６．１７７０，２．８８２３，４．８０７９）（５．８１５０，３．０９５４，３．７３７９）（６．１７７０，２．８８２３，４．８０７９）（５．７７２２，３．０９５８，３．６４５２）（６．１７７０，２．８８２３，４．８０７９）Ｌｅｅ’ｓ（５．８４８１，３．０２５７，３．８９８１）（５．７０００，２．８０００，４．１０００）（５．９０６７，３．０６１３，３．８４２３）（５．７０００，２．８０００，４．１０００）（５．８５４４，３．０１８０，３．８７８８）（５．７０００，２．８０００，４．１０００）ＰＣＭｌ（５．８４８１，３．０２５７，３．８９８１）（５．７０００，２．８０００，４．１０００）（５．９０６７，３．０６１３，３．８４２３）（５．７０００，２．８０００，４．１０００）（５．８５４４，３．０１８０，３．８７８８）（５．７０００，２．８０００，４．１０００） 实验２随机产生如图２所示的数据集合，ｍ仍然取２，迭代次数取１００次，误差为０，００００１，类别个数为２．数据集中样本点的个数为２００，每个样本点有２个属性．其数据分布图如图２所示，实验结果如表２所示．从表２可以看出，ＦＣＭ算法得到了２个不同的类中心，ＰＣＭ算法得到的是重合的类中心，ＰＣＭｉ和Ｌｅｅ＇ｓ算法得到的却是近乎重合的２个类中心．Ｎ「 。Ｏ ０｝ｐ＂．．ｐ．０ｎｍ０ ｋ Ｖ ０９Ｑ，Ｏ ＧＯＣ。０．０夕 日０。￣入 ？０ ０ 寸．０．．‘．．．．凶．．０Ｌｎｘ／ ｃｍ图２人工数据分布图Ｆｉｇ． ２ Ｍａｎｕａｌ ｄａｔａ ｄｉｓｔｉｒｂｕｔｉｏｎ ｆｉｇｕｒｅ表２实验２结果 Ｔａｂ． ２ Ｒｅｓｕｌｔｓ ｏｆ Ｔｅｓｔ ２算法初始类中心类中心ＦＣＭ（０．３０１ ７，０．７２２ ８）（０．１９６ ７，０．８１９ ２）（０．３０１ ６，０．７１２ ６）（Ｕ．５１７ ２，０．５０４ ４）ＰＣＭ（０．３００ １，０．７１５ ６）（０３００ ３，０．７１２ ５）（０３０４ １，０．７１９ ６）（０．３０８ ８，０．７１９ ２）喊（０．２９４ １，０．７１５ ５）（０．３００ ３，０．７１２５）（０．２９８ ７，０．７２３ ８）（０．３００ ３，０．７１２５）钟（０．２９４ １，０．７１５ ５）（０．３００ ３，０．７１２ ５）（０．２９８ ７，０．７２３ ８ ）（０．３００ ３，０．７１２ ５） 实验３采用与实验２相同的数据集合，类别个数取２． ｍ取１．８，迭代次数取１００次，误差为０．００００１，实验结果如表３所示．表２的结果仍然是第２期李翠霞等：一种模糊聚类算法归类的研究ＦＣＭ算法可以得到指定的２个不同的类中心，ＰＣＭＦｕｎｃ ｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ〔Ｍ］．Ｎｅｗ Ｙｏｒｋ： Ｐｌｅｎｕｍ Ｐｒｅｓｓ，１９８１． 算法得到的是重合的类中心，ＰＣＭ１及Ｌｅｅ＇ｓ算法［２］ Ｋｒｉｓｈｎａｐｕｒａｍ Ｒ， Ｋｅｌｅｒ Ｊ Ｍ． Ａ Ｐｏｓｓｉｂｉｌｉｓｔｉｃ Ａｐｐｒｏａｃｈ ｔｏ得到的又是２个近乎重合的类中心．Ｃｌ ｕｓｔｅｒｉｎｇ ［ Ｊ ］．ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ， １９９３， １ 表３实验３结果万方数据Ｔａｂ． ３ Ｒｅｓｕｌｔｓ ｏｆ Ｔｅｓｔ ３算法初始类中心类中心ＦＣＭ（０．３１４ ８，０．６９３ ２）（０．５１８ ９，０．５０３ ０）（０．２９３ ２，０．７３６ ８）（０．１９８ ０，０．８１８ ３）哪（０３０６ ２，０．７１８ ９） （０．３１１ ４，０．７２１２）（０．３０９ ６，０．７０７ ３） （０．３００ ３，０．７１２５）贼（０．３０４ １，０．７１５５）（０．３００ ３，０．７１２５）（０．２９２ ５，０．７３１９）（０．２９０ ３，０．７３４２）ＰＣＭＩ（０．３０４ １，０．７１５５）（０．３００ ３，０．７１２ ５）（０．２９２ ５，０．７３１９）（０．２９０ ３，０．７３４ ２） 如果正如有些研究者认为，Ｌｅｅ＇ｓ算法是改进的ＦＣＭ算法，那么类中心彼此影响，就不会产生重合的类中心．而如果它是ＰＣＭ型的算法，它就会有ＰＣＭ型算法的缺点，也就是容易产生重合的类中心．从实验结果表１、表２、表３可以看出，当初始划分相同时，Ｌｅｅ＇ｓ算法的聚类结果与我们所推导出的ＰＣＭＩ算法的结果完全相同，而与ＦＣＭ算法的结果差别较大；每次实验中，ＦＣＭ算法所产生的类中心都各不相同，而ＰＣＭ算法和ＰＣＭ１算法及Ｌｅｅ＇ｓ算法产生的却是重合的类中心，这与我们前边的理论分析完全一致．５结论 在本文中，对Ｌｅｅ＇ｓ算法模型进行了深人研究：（１） 从理论上证明了Ｌｅｅ＇ｓ算法并不是ＦＣＭ算法的改进算法，应该属于ＰＣＭ型算法．（ ２）通过实验验证了Ｌｅｅ＇ｓ算法易于产生重合类中心的缺点．这将有助于聚类算法的研究者重新认识Ｌｅ ｅ＇ ｓ算法，又可以为数据挖掘、模式识别、图像分割等诸多聚类分析应用领域的算法使用者们合理地使用聚类算法提供一定的理论依据．参考文献：［１」Ｂｅｚｄｅｋ Ｊ Ｃ． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ｗｉｔｈ Ｆｕｚｚｙ Ｏｂｊｅｃｔｉｖｅ（ ２）：９８一１１０．［３］ Ｃｈｅｒｋａｓｓｋｙ Ｖ， Ｍｕｌｉｅｒ Ｆ． Ｌｅａｒｎｉｎｇ ｆｏｒｍ Ｄａｔａ Ｃｏｎｃｅｐｔｓ，Ｔｈｅ ｏｒｙ， ａｎｄ Ｍｅｔｈｏｄｓ［ ＭＩ．Ｊｏｈｎ Ｗｉｌｅｙ＆Ｓｏｎｓ， Ｉｎｃ． １９９８．４１３一４１７． ［４〕边肇棋，张学工．模式识别〔Ｍ］．北京：清华大学出版社，１９９９ ＢＩＡＮ Ｚｈａ－ｏｑｉ， ＺＨＡＮＧ Ｘｕｅ－ｇｏｎｇ． ＰａｔｅｎｒＲ ｅｏｃｇｎｉｔｉｏｎ［Ｍ］．Ｂｅ ｉｊｉｎｇ： Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， １９９９． （ｉｎ Ｃｈｉｎｅｓｅ）［ｓ〕于剑论模糊Ｃ均值算法的模糊指标〔Ｊ］．计算机学报，２００３， ２６（８）：９７４一９８１．ＹＵ Ｒａｎ． Ｏｎ ｔｈｅ Ｆｕｚｚｉｎｅｓｓ Ｉｎｄｅｘ ｏｆ ｔｈｅ ＦＣＭ Ａｌｇｏｒｉｔｈｍｓ［ Ｊ ］ ． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ， ２００３， ２６ （８）：９７４一 ９８１． （ｉｎ Ｃｈｉｎｅｓｅ）［６」于剑，程乾生．关于ＦＣＭ算法中的权重指数ｍ的一点注记［ Ｊ］．电子学报，２００３，３１（３）：４７８一４８０．ＹＵ Ｊｉａｎ， ＣＨＥＮＧ Ｑｉａｎ－ｓｈｅｎｇ． Ａ Ｎｏｔｅ ｏｎ Ｗｅｉｇｈｔｉｎｇ Ｅｘ－ｐｏ ｎｅｎｔ ｍ ｏｆ ＦＣＭ Ａｌｇｏｒｉｔｈｍ［Ｊ］．Ａｃｔａ Ｅｌｅｃｔｒｅｎｉｃａ ＳｉｎｉｃａＩ２００３， ３１（３）：４７８一４８０． （ｉｎ Ｃｈｉｎｅｓｅ）［ ７ ］ Ｂａｒｎｉ Ｍ， Ｃａｐｐｅｌｉｎｉ Ｖ， Ｍｅｏｏｃｃｉ Ａ． Ｃｏｍｍｅｎｔｓ ｏｎ ｀ Ａ Ｐｏｓ－ｓ ｉｂｉｌｉｓｔｉｃ Ａｐｐｒｏａｃｈ ｔｏ Ｃｌｕｓｔｅｒｉｎｇ＇【Ｊ〕．ＩＥＥＥ Ｔｒａｎｓ． ｏｎＦｕｚ ｚｙ Ｓｙｓｔｅｍｓ， １９９６，４（３）：３９３一３９６．［８］ Ｓｃｈｎｅｉｄｅｒ Ａ． Ｗｅｉｇｈｔｅｄ Ｐｏｓｓｉｂｉｌｉｓｔｉｃ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍｓ［ Ｊ］． Ｉｎ： Ｐｒｏｃ． ｏｆ ｔｈｅ ９ｔｈ ＩＥＥＥ Ｉｎｔ＇ ｌ Ｃｏｎｆ． ｏｎ Ｆｕｚｚｙ Ｓｙｓ－ｔ ｅｎｒｓ． Ｔｅｘａｓ： ＩＥＥＥ， ２０００，１：１７６一１８０．［９」张敏，于剑．基于划分的模糊聚类方法【Ｊ］．软件学报，２００４， １５（６）：８５８一８６８． ＺＨＡＮＧ Ｍｉｎ， ＹＵ Ｊｉａｎ． Ｆｕｚｚｙ Ｐａｒｔｉｔｉｏｎａｌ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏ－ｒ ｉｔｈｍｓ［Ｊ ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ． ２００４，１５（６）：８５８一８６８．（ｉ ｎ Ｃｈｉｎｅｓｅ）［１０］ Ｋｒｉｓｈｎａｐｕｒａｍ Ｒ， Ｋｅｌｅｒ Ｊ Ｍ． Ｐｏｓｓｉｂｉｌｉｓｔｉｃ Ｍｅａｎｓ Ａｌｇｏ－ ｒｉｔｈｍｓ： Ｉｎｓｉｇｈｔｓ ａｎｄ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ．ｏ ｎＦｕｚｚｙ Ｓｙｓｔｅｍｓ， １９９６，４（３）：９８一１１０．［ １１１ Ｓｃｈｎｅｉｄｅｒ Ａ． Ｗｅｉｇｈｔｅｄ Ｐｏｓｓｉｂｉｌｉｓｔｉｃ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍｓ［ Ｊ］．Ｉｎ： Ｐｒｏｃ． ｏｆ ｔｈｅ ９ｔｈ ＩＥＥＥ Ｉｎｔ＇ １ Ｃｏｎｆ． ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ． Ｔｅｘａｓ： ＩＥＥＥ， ２０００，１：１７６一１８０．［１２］ Ｋｒｉｓｈｎａｐｕｒａｍ Ｒ， Ｋｅｌｌｅｒ Ｊ Ｍ． Ｔｈｅ Ｐｏｓｓｉｂｉｌｉｓｔｉｃ Ｍｅａｎｓ Ａｌ－ｇｏｒｉｔｈｘｎｓ： Ｉｎｓｉｇｈｔｓ ａｎｄ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ〔Ｊ］．ＩＥＥＥＴｒａｎｓ． ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ， １９９６，４（３）：９８一１１０．
