科技信息 ０本刊重稿０ ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹＩＮＦＯＲＭＡＴＩＯＮ ２０１１年第３３期 一种改进的模糊聚类算法研究 罗琪 （渭南师范学院数学与信息科学学院网络技术研究所陕西渭南７１ ４０００） 【摘要】本文研究了模糊聚类方法，针对模糊ｃ一均￣（Ｆｕｚｚｙ Ｃ－ｍｅａｎｓ Ｍｅｔｈｏｄ，ＦＣＭ）算法的不足，提出新的初始化算法方法，将其应于模 糊聚类数目的初始化，结合近似Ｋ中心对ＦＣＭ算法进行改进。实验表明，改进后的ＦＣＭ算法要有效避免了聚类结果的局部最优．有较好的抗 噪能力．从而提高模糊聚类性能和可靠性 【关键词】模糊聚类；隶属度；模糊Ｃ一均值；近似Ｋ中心 Ａｎ Ｉｍｐｒｏｖｅｄ Ｆｕｚｚｙ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ 【Ａｂｓｔｒａｃｔ］Ｔｈｉｓ ｐａｐｅｒ ｄｅａｌｓ ｗｉｔｈ ｔｈｅ ｆｕｚｚｙ ｃｌｕｓｔｅｉｒｎｇ，ａｎａｌｙｓｅｓ ｔｈｅ ｆｕｚｚｙ Ｃ—ｍｅａｎｓ ｍｅｔｈｏｄ．Ａ ｎｅｗ ｉｎｉｔｉｌａｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｏｖｅｒｃｏｍｅ ｔｈｅ ｓｈｏｒｔｃｏｍｉｎｇｓ ｏｆ ＦＣＭ ｔｈａｔ ｃｌｕｓｔｅｒｉｎｇ ｎｕｍｂｅｒ ｓｈｏｕｌｄ ｂｅ ｄｅｔｅｒｍｉｎｅｄ ｂｅｆｏｒｅｈａｎｄ．Ｉｎ ｃｏｍｂｉｎａｔｉｏｎ ｗｉｔｈ ｔｈｅ ｎｅｗ ｉｎｉｔｉａｌｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ａｎｄ Ａｐｐｒｏｘｉｍａｔｅｄ Ｋ－ｍｅｄｉａｎｓ，ｔｈｉｓ ｐａｐｅｒ ｉｎｔｍｄｕｑｅｓ ａｎ ｉｍｐｒｏｖｅｄ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｅｍｕｌａｔｉｏｎ ｅｘａｍｉｎａｔｉｏｎｓ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ａｄｖａｎｔａｇｅｓ，ｓｕｃｈ ａｓ ａｖｏｉｄｉｎｇ ｌｏｃａｌ ｏｐｔｉｍａ，ｒｏｂｕｓｔ ｔｏ ｎｏｉｓｅ．Ａｃｃｏｒｄｉｎｇｌｙ ｉｔ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｒｅｌｉａｂｉｌｉｔｙ ｏｆ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ． 【Ｋｅｙ ｗｏｒｄｓ］Ｆｕｚｚｙ ｃｌｕｓｔｅｒ；Ｍｅｍｂｅｍｈｉｐ ｄｅｇｒｅｅ；Ｆｕｚｚｙ Ｃ－ｍｅａｎｓ；Ａｐｐｒｏｘｉｍａｔｅｄ Ｋ－ｍｅｄｉａｎｓ ０引言 模糊聚类反映了对象属于不同类别的不确定性程度．表达了对象 类属的中介性．可以更客观地反映现实世界 模糊聚类基于Ｚａｄｅｌ于 １９６５年提出的模糊集合论［１１．人们已经提出了很多基于模糊划分概念 的模糊聚类方法．如系统聚类法、传递闭包法以及与此等价的最大支 撑树的Ｐｒｉｍ算法及Ｋｒｕｓｋａｌ算法、动态直接聚类法．基于摄动的模糊 聚类方法ＦＣＭＢＰ、模糊ｃ一均值法、模糊ＩＳＯＤＡＴＡ算法等。模糊聚类 个聚类．并保存到类集合Ｃ，更新数据集 ： 分析已经广泛应用于经济学、生物学、气象学、信息科学、工程技术科 （３）随机取出数据集 中的一个数据Ｘｉ，计算其与各个巳存在的 学等许多领域 Ｎ（ｘ．，Ｃ ），其中 本文研究了模糊聚类方法．针对模糊ｃ一均值ｆＦｕｚｚｖ Ｃ—ｍｅａｎｓ 聚类集合的聚类中心距离。取其中最小的距离ｄ…＝Ｍ１…， ， 为当前类集合中已建立的聚类个数； Ｍｅｔｈｏｄ，ＦＣＭ）算法的不足．提出具体的改进方案。通过实验．得出改进 ｉ∈１，（４）判断ｄ 。 ，若它ｄｍ ≤如，如为事先定义的聚类宽度值，则将其 后的ＦＣＭ算法要有效避免了聚类结果的局部最优．提高了检测性能 和检测结果的可靠性 放人已存在的一种聚类簇．然后继续处理下一条实例数据：否则如果 当前实例与聚类簇集合中所有聚类实例的距离都大于ｄｏ．则以该实例 １模糊聚类 为中心定义一个新的聚类．并加人到聚类簇集合中： 模糊聚类最常用的就是基于目标函数的模糊聚类．利用非线性化 （５）当训练样本集中的所有数据都处理完，则结束，否则转（３）。 方法搜索目标函数的局部极值点 。模糊聚类中最常用的目标函数是 通过以上的聚类算法后．将得到一个经过初步聚类后的聚类簇．即得 种组内方差和的形式，假定 为输入模式向量 ＝ ，… ｝是 到聚类数目 ２聚类中心的确定 组数据元组，其中 ＝ … ］表示具有ｍ个属性的数据对 ２．用聚类中值表述聚类中心．对噪声和孤立点有较好的抑制作用 象。有使以下代价函数最小作为聚类的目标函数 ： 然而无论是求解广义中值还是限定中值，都存在较高的计算复杂度。 二二 ２ ｍｉｎ｛Ｄｉｄａｙ在文献ｆ４１中提出近似中值（ａｐｐｒｏｘｉｍａｔｅｄ ｍｅｄｉａｎ）算法，它对数 五（ｕ，ｖ ）＝ ｄｉ Ｊ （１） Ｅ．～ｕ ｉ：１ ＝１ 据点的结构和距离函数没有特定的要求．并且具有线性的时间复杂 其中，ｃ为类的个数；ｎ为聚类空间模式的个数： 为类中心；Ｕ为 度。实验表明．在适合的参数下，这种近似算法能够得到比较精确的类 ｃｘｎ维的模糊划分矩阵，Ｕｉｋ ［Ｏ，１］，它表示对象 划分到聚类ｆ中的隶 中值 本文将近似中值用于计算类中值得出近似Ｋ—ｍｅｄｉａｎｓ算法．对 属度。ａ＞ｌ是一个模糊加权指数，用来控制隶属矩阵的模糊程度。ｄ二 于每个类．用近似Ｋ—ｍｅｄｉａｎｓ算法来寻找类的中心。 ３算法描述 ｌ ｌＸｋ 为对象 与第ｉ个簇的质心Ｖｉ的距离，Ａ为正定矩阵，代 ２．用上述初始化方法确定初始聚类数目．用近似中心算法确定模糊 表类的形状 在设计规则库的时候采用的模糊集合通常是单峰的．同 给出改进的模糊聚类算法如下： 时．有可能类划分定义的隶属度函数虽然是凸的模糊集合．但是隶属 聚类中心．（１）用２．１节的方法找出初始聚类数目ｃ，给出阈值∈和最大迭代 度函数本质是柯西函数，文献［３】提出称为ＡＣＥ（Ａｌｔｅｒａｔｉ０ｎ ｃｌｕｓｔｅｒ ｅｓｔｉｍａｔｉｏｎ）的聚类规则．在隶属度函数的选择与类的原型的选择有很 次数 ；一一…、针对ＦＣＭ算法对聚类数目值敏感和容易陷入局部最优的缺点． 本文提出使用ＦＣＭ算法之前先对数据进行初始化聚类．得到聚类数 目和初始聚类的类心．变随机设置为有目的地选择．保证获得的聚类 结果为全局最优解，从而提高检测性能和检测结果的可靠性。 初始化聚类数目算法描述： （１）初始化空聚类集合ｃ： （２）随机取标准化后的数据集 中的一个数据 。把它作为第一 ＝大的自由度．可以根据不同的应用环境选择不同的方案［２１ （２）用 １］间的随机数初始化隶属矩阵 …，并使其满足式 Ｉ“ ２改进的ＦＣＭ算法 ＞０，∑ ＝１的约束条件。利用近似中值计算初始聚类中心，得到Ｖ ， ｋ ｌ 在众多的模糊聚类算法中．应用最广泛而且较成功的是模糊Ｃ一 令迭代次数ｊ＝ｌ。 均值（Ｆｕｚｚｙ Ｃ—ｍｅａｎｓ，ＦＣＭ）算法。ＦＣＭ算法要求用户提供聚类数目．如 （３）利用近似中值计算聚类中心。更新划分矩阵Ｕ 。 果主观设定聚类数目，则聚类结果的稳定性和可靠性就无法保证 同 （４）重新计算隶属度。计算目标函数并保存。 时．ＦＣＭ算法是基于目标函数的聚类算法．由于目标函数存在许多局 （５）若ｍａｘ｛ ＩＪ—ｕ ”１≤ｓ １或 ： 一，则迭代过程结束，否则 ＋ ＋ 部极小点．而算法的每一步迭代都是沿目标函数减小的方向进行 所 转至（３） 以，如果初始化落在了一个局部极小点附近．就可能使算法收敛到局 １．部极小。本节将研究ＦＣＭ算法，并将针对其不足，给出初步的改进方 ３实验及结果分析 案。 ２．１聚类数目的初始化算法 为了验证模糊聚类的有效性．Ｘｉｅ和Ｂｅｎｉ从数据集的几何结构出 １５ ’２０１１年第３３期 ＳＣＩＥＮＣＥ＆ＴＥＣＨＮＯＬＯＧＹ ＩＮＦＯＲＭＡＴＩＯＮ Ｏ本刊重稿。 科技信息 发，提出了Ｘｉｅ—Ｂｅｎｉ有效性指标Ｖ 。 １∑∑ｕ ｌ １（ ，ｃ）＝ ————ｒ （２） ●实际中心 ｍｉｎ ｌ ｌｖｉ－ｘｊ Ａ初始聚类中心 其中，Ｕ是隶属矩阵． 是聚类中心矩阵，ｃ是聚类数，ｍ是模糊因 口加噪聚类中心 子，ｕ 是Ｕ矩阵中的元素， 是类内紧凑度和类间分离度的比例，在 类内紧凑度和类间分离度之间找一个平衡点．使其达到最小．从而获 得最好的聚类结果 本文采用基于数据集几何结构的模糊聚类有效性 函数进行评价。实验数据采用计算机模拟的二维空间的高斯随机数据 集进行检验。每类有１００００个样本．共计６００００个二维点。模糊因子 ｍ：２．分别用ＦＣＭ算法和本节改进算法对实验数据进行测试．实验分 析结果如表１所示 ４结束语 表１ ＦＣＭ算法与改进算法的比较 本文首先探讨了数据挖掘技术中的聚类分析方法：接着研究了模 、糊理论，详细阐述了模糊聚类方法；最后针对模糊ｃ一均值（Ｆｕｚｚ结果＼ 、＼算法 ｙ Ｃ— ＦＣＭ算法 改进算法 ｍｅａｎｓ Ｍｅｔｈｏｄ，ＦＣＭ）算法的不足，提出具体的改进方案。通过实验，得 聚类运行时间（ｓ） ７２５．８０９ ４６５．５ｌ１ 出改进后的ＦＣＭ算法要有效避免了聚类结果的局部最优．提高了检 迭代次数 １３ ９ 测性能和检测结果的可靠性。ｅ 埘 Ｏ．８ ０．７８５ 【参考文献】 ［１］Ｚａｄｅｈ Ｌ Ａ．Ｔｏｗａｒｄ ａ Ｔｈｅｏｒｙ ｏｆ Ｆｕｚｚｙ Ｓｙｓｔｅｍ：Ｆｕｚｚｙ Ｓｅｔｓ ａｎｄ Ｆｕｚｚｙ Ｉｎｆｏｒｍａｔｉｏｎ 从表１中的测试结果可以看出．本节提出的方法得到的初始值有 Ｇｒａｎｕｌａｔｉｏｎ Ｔｈｅｏｒｙ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｂｅｉｊｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，２０００：２９—６１ 比较好的效果，聚类过程有良好的速度和迭代次数。从而提高了检测 ［２］肖建，白裔峰，于龙．模糊系统结构辨识综述ｆＪ１＿西南交通大学学报，２００６，４１ 率。从模糊聚类的有效性指标可以看出改进算法要优于ＦＣＭ算法。 （２）：１３５—１４２． 随机选取属性值范围外的１００个明显偏离实验数据中心的点．将 ［３］ＨＯＰＰＮＥＲ Ｆ，ＫＬＡＷＯＮＮ Ｆ．Ｆｕｚｚｙ ｃｌｕｓｔｅｒ ａｎａｙｓｉｓ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｊｏｈｎ Ｗｉｌｅｙ＆ Ｓｏｎｓ，Ｌｔｄ，１９９９． 其作为噪声加入实验数据集．分别在加入噪声的数据和没有加入噪声 ［４］Ｅ．Ｄｉｄａｙ．Ｔｈｅ Ｓｙｍｂｏｌｉｃ Ａｐｐｒｏａｃｈ ｉｎ Ｃｌｕｓｔｅｒｉｎｇ，Ｃｌａｓｓｉｉｆｃａｔｉｏｎ ａｎｄ Ｒｅｌａｔｅｄ 的数据上用本节方法进行初始聚类中心的选取．与实际中心比较．考 Ｍｅｔｈｏｄｓ ｏｆ Ｄａｔａ Ａｎａｌｙｓｉｓ，Ｈ．Ｈ．Ｂｏｃｋ，Ｅｄ．Ａｍｓｔｅｒｄａｍ，Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ：Ｅｌｓｅｖｉｅｒ， 察算法的抗噪性。从实验结果中选取了几个具有代表性的聚类中心进 １９８８． 行比较．如图１所示 ［５］Ｘｉｅ Ｘ Ｌ，Ｂｅｎｉ Ｇ．Ａ Ｖａｌｉｄｉｔｙ Ｍｅａｓｕｒｅ ｆｏｒ Ｆｕｚｚｙ Ｃｌｕｓｔｅｒｉｎｇ叨．ＩＥＥＥ Ｔｒａｎｓ ｏｎ 图１表明，本节算法取得初始值与数据的实际中心非常接近．在 Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９１，８（１３）：８４１—８４７． 有噪声的数据上的初值的选取也得到了较好的结果．表明该算法有一 定的抗噪能力。以上实验结果表明改进的算法有较好的抗噪能力．保 ※基金项目：陕西省教育厅科研项目（２０１０ＪＫ５３４）：渭南师范学 证了获得的聚类结果为全局最优解．从而提高模糊聚类性能和聚类结 院科研项目（１０ＹＫＺ０５９）；渭南师范学院科研项目（１１ＹＫＳ０１９｝。 果的可靠性 ［责任编辑：王洪泽］ （上接第１页）并通过小组完成项目培养了学生团队意识和合作意 识。Ｑ 作者简介：沈蕴梅（１９７９一），女，江苏太仓人，江苏省太仓市健雄职业技术 学院，讲师，华东师范大学教育科学院，硕士研究生。 【参考文献】 ［１］奕玖华顶目教学法在技能训练中的实践与思索叨．职业技术，２００８（２）． ※本文系健雄职业技术学院教改课题“《平面设计》项目化教学改 ［２］叶健华．《ｃ语言程序》设计项目化教材建设初探叨．南京：南京工业职业技术 革研究与实践”的研究成果。课题编号：教改２００９３１。 学院学报．２０１０（１２）． ［３］李柏山．平面设计教学的现状、问题及对策【Ｊ Ｊｌ ｌ化学院学报，２００８（３）． ［责任编辑：王洪泽］ （上接第２３页）际应用。同时，在科研项目中提炼出一些关键问题作为 ［１］彭启琮，李玉柏，管庆．ＤＳＰ技术的发展与应用ｆＭ ］．２版．北京：高等教育出版 本科生毕业设计的题目或研究生毕业论文的选题．有利于增强学生的 社．２００７． 实践能力，极大地促进了学生自主研究意识和创新能力的提高。 ［２］熊承义，侯建华．“ＤＳＰ技术”本科课程教学改革与探索Ⅲ＿高等理科教育， ２０ｏ８（６１：９４—９６． ３结语 ［３］渠丽岩．让学生在快乐中学习：谈案例教学法在“单片机原理与应用”教学中 ＤＳＰ芯片应用技术是一门实践性比较强的课程．与不断发展的 的应用 ．计算机教育，２００９（１８）：９３—９５． ＤＳＰ技术一样，ＤＳＰ技术的教学也处于不断发展、完善的过程之中。通 作者简介：冯杰（１９８ｏ＿＿），男，辽宁锦州人，博士，讲师，主要从事数字信号处 过案例化的教学方法．以学生为行动的主体．以师生及学生之间互动 理理论与技术等教学与研究。 的合作行动为方式，培养学生的专业能力、实践能力和合作能力，保证 了课程的教学质量．并达到良好的教学效果．构筑教学与科研共进的 ※资助项目：浙江理工大学教育教学改革研究项目青年项目．项 良好环境。ｌ 目编号１１１２００３２３１１０８８。 【参考文献】 ［责任编辑：曹明明］ １６
