第１２卷第４期 哈尔滨理工大学学报 ＶｏＬ １２ Ｎｏ．４ ２００７年８月 Ｊ０ＵＲＮＡＬ ＨＡＲＢＩＮ ＵＮＩＶ．ＳＣＩ．＆ＴＥＣＨ． Ａｕｇ．，２００７ 一种改进的模糊Ｃ均值聚类算法 宋清昆， 郝 敏 （哈尔滨理工大学自动化学院，黑龙江哈尔滨１５００８０） 摘要：针对模糊ｃ均值（ＦＣＭ）聚类算法中，聚类效果往往受到聚类数目和初始聚类中心的 影响这一问题，提出了基于平均信息熵确定聚类数目的方法，并采用密度函数法来获得初始聚类中 心．实验结果表明，改进后的算法较好地解决了初值问题，与随机初始化方法相比，迭代次数少，收 敛速度快． 关键词：模糊Ｃ均值聚类；信息熵；初始化；密度函数 中图分类号：ＴＰ２７３ 文献标识码：Ａ 文章编号：１００７－２６８３（２００７）０４—０００８－０３ ｌ ｍｐｒｏｖｅａ ｕｚｚｖ ｐｒｏｖｅｄ Ｆｕｚｚｙ Ｃ—ｍｅａｎｓ Ｃｌ— ｅａｎｓ ｕｓｔｅｒｕｓｔｅｒｉ ｎｇ Ａｌｎｇ ＡＩｇｏｒｉｇｏｎｍｍ ｔｈｍＳＯＮＧ Ｑ 一ｋｕｎ，ＨＡＯ Ｍｉｎ （Ｃｏｌｌｅｇｅ ｏｆ Ａｕｔｏｍａｔｉｏｎ，Ｈａ￣ｉｎ Ｕｎｉｖ．Ｓｃｉ．Ｔｅｃｈ．，Ｈａｒｂｉｎ １５００８０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｆｕｚｚｙ Ｃ—ｍｅａｎｓ（ＦＣＭ）ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｄｅｐｅｎｄｓ ｏｎ ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｏｆ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ａｎｄ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ．Ｔｏ ａｎｓｗｅｒ ｔｈｅ ｔｗｏ ｑｕｅｓｔｉｏｎｓ，ｔｈｉｓ ｐａｐｅｒ ｐｕｔｓ ｆｏｒｗａｒｄ ａ ｎｅｗ ａｌｇｏ— ｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ａｖｅｒａｇｅ ｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ｔｏ ｆｉｎｄ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ａｎｄ ａｄｏｐｔｓ ａ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ ａｌｇｏ— ｒｉｔｈｍ ｔｏ ｆｉｎｄ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ．Ｉｔ ｉｓ ｓｈｏｗｎ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｒｅｓｏｌｖｅ ｔｈｅ ｉｎｉｔｉａｌ ｐｒｏｂｌｅｍｓ ｅｆｆｅｃ— ｔｉｖｅｌｙ．Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｓｔｏｃｈａｓｔｉｃ ｉｎｉｔｉａｌｉｚａｔｉｏｎ，ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ｈａｖｅ ｆｅｗｅｒ ｎｕｍｂｅｒｓ ｏｆ ｉｔｅｒａｔｉｏｎｓ ａｎｄ ｈａｖｅ ｆａｓｔｅｒ ｓｐｅｅｄ ｔｏ ｃｏｎｖｅｒｇｅ． Ｋｅｙ ｗｏｒｄｓ：ｆｕｚｚｙ Ｃ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ；ｉｎｆｏｒｍａｔｉｏｎ ｅｎ￣ｏｐｙ；ｉｎｉｔｉａｌｉｚａｔｉｏｎ；ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ 信息熵的方法，采用密度函数法来确定初始聚类中 心，与随机方法相比具有收敛速度快，分类准确等 优点． 模糊聚类算法中以模糊ｃ均值（ＦＣＭ）聚类算 法¨ 应用最为广泛，但是ＦＣＭ聚类算法存在多方 ２ ＦＣＭ算法 面问题，诸如聚类数目难以确定，如何确定有效的初 始聚类中心和初始隶属度矩阵，迭代容易陷入局部 模糊ｃ均值聚类就是求使聚类目标函数．，最小 极值等． 的模糊划分矩阵Ｕ＝［ｕ ］。 ，以及类别中心 ｆｖ Ｃ 许多研究是针对ＦＣＭ聚类算法中聚类数目和 初始聚类中心选择问题的，但相关研究，或者只考虑 ．，：∑∑（ｕ ） ｌ ｌ一 ｌ ｌ聚类数目的确定，或者只对初始聚类中心进行选择． 其中：Ｖ 表示第ｉ个聚类中心，ｉ＝１，２，…，ｃ；＿『＝１， 本文针对聚类数目确定的问题，提出一种基于平均 ２，…，Ⅳ；ｍ∈（１，∞）是加权指数，目标函数表示了 各类数据到相应聚类中心的加权距离平方和．具体 收稿日期：２００６—０７—０２ 作者简介：宋清昆（１９６４一），男，哈尔滨理工大学教授 第４期 算法如Ｆ： 宋清昆等：一种改进的模糊ｃ均值聚类算法 ９ １）确定聚类数目Ｃ，初始化ｍ及聚类中心 ； ２）对第 次迭代，根据式 ＝ — 一 和 ＝ Ｈ （ ）＝０，则Ｈ （ ）＝Ｈｋ（ ）；如ＨＩ（ ）＜ （ ）， 则Ｈｍ（ ）＝Ｈ （ ），用当前ｋ值更新Ｃ值． ６）如果ｋ＞Ｃ ，则Ｃ即为最终聚类数目；否 则，返回２）． ３．２ 初始聚类中心的选择 ∑（ ） ＿～ｌ，计算新的隶属度函数和Ｃ个聚类中心； 在文［４］给出的初始化方法中，势函数是以指 数运算为基础，这在样本量较大的情况下会影响速 ∑（ ） ３）若Ｉ 一，“ Ｉ≤ ，则停止，否则返回２） ３ 改进的ＦＣＭ聚类算法 ＦＣＭ聚类算法中，聚类数目是需要用户预先设 置的参数．选择合适的聚类数目是正确聚类的前提． 另外，ＦＣＭ聚类算法从某种程度上说，可看作初始 聚类中心到聚类结果的映射．若选取的初始中心接 近数据真正的类别中心，算法的收敛速度和准确性 都将得到改善． ３．１ 聚类数目的确定 熵是用来描述原子分布的无序程度的，数据点 的分布类似于原子的分布，当聚类的划分越合理，数 据点在某一聚类上的归属越确定时，该聚类的信息 熵值越小．本文对文［３］提出的基于信息熵理论的 聚类算法进行改进，以平均信息熵的大小作为评判 聚类数目的标准． 在用户使用此算法时，首先确定希望产生的聚 类数目范围［ｃ ｃ ］．平均信息熵值的定义为 Ｃ 日（ ）＝一∑∑｛Ｉ＝１ Ｊ １ ［ ×］ｏｇ２（ ）＋ （１一 ）Ｘ ｌｏｇ２（１一 ）］／，ｖ｝ 其中： 表示样本 属于聚类ｉ的程度， ［０，１］， Ｖ 当ｋ从ｃ 增加到ｃ一时，就产生ｃｎ 一ｃ ＋１ 个 （ ），选取最小的一个 （ ）所对应的聚类数 目ｋ作为最终的聚类数目Ｃ． 该算法的思想如下： １）设置最大聚类数目Ｃ 和最小聚类数目 Ｃ ，阈值 ，并设 ＝Ｃ ｉ 一１． ２）随机初始化隶属矩阵Ｕ ，ｔ＝０，ｋ增加１． ３）更新隶属度矩阵 “ 和聚类中心 “，ｔ增加１． Ｉ Ｉ４）当ｆ，“ 一，ｎ ｆ＞ 时，返回３）． Ｉ Ｉ ５）计算 （戈），记下此时聚类数目ｋ．如果 度．为此，本文采用一种密度函数法进行初始化，定 义样本点 ｉ处的密度函数如下： ・ 』ｖ １ Ｄ ∞ （ ） ＝ １ ０ ｄ ｌｌ 一 川 其中 ＝４／ｒ ， 是领域密度有效半径，它的选择 应该与数据集合的分布特性有关．这里取 为，ｖ个 样本的均方根距离的÷，即 １厂— ———可— ———一 ＝ 一√ ／ 可刍刍ｌ∑∑Ｉ Ｉｘ —ｘ一‘ｊｌ （２）） 由式（１）可知，在 周围样本点越密集，则Ｄ ∞值越 大．故可以用来表示在样本空间中样本点的密集程 度．与势函数法相似，令Ｄ１．＝ｍａｘ｛Ｄ 们，ｉ＝１，２， …，，ｖ｝，对应的 取为第１个初始聚类中心．求后续 初始聚类中心的密度函数调整关系式，即 Ｄ ” ｋ＝１，２，…，Ｃ一１ （３） 其中，ｃ为聚类数目，由前面基于平均信息熵的聚类 数目法事先确定．Ｄ ＝ｍａｘ｛Ｄ ¨，ｉ＝１，…，，ｖ｝， 对应的样本点 取为第ｋ个初始聚类中心位置．由 式（１）一（３）决定中心初始化方法，其原理与势函 数方法相似，但运算量却比势函数法小得多． ４ 实验结果 为说明上述算法的有效性，本文利用文［５］中 的数据集进行实际检验．这组数据是１５０个关于３种 花的生物统计数据，通常称为ＩＲＩＳ数据集．所有的 实验取模糊控制参数ｍ＝２． 首先，验证基于平均信息熵的聚类数目确定方 法的有效性：输人参数为Ｃ ＝２，Ｃ ＝８，Ｎ＝ １５０（数据个数），Ｓ＝４（数据维数）．采用基于平均 信息熵的聚类数目的确定方法后，由表１可见，当类 数为３时，平均信息熵最小，多次运行该算法，得到 的结果比较稳定，显然这与已知的花的种类数相符， 结果令人满意． １０ 哈尔滨理工大学学报 第１２卷 表ｌ ＩＲＩＳ数据集分类平均熵值表 类数 对应平均熵值 类数 对应平均熵值 ２ １．Ｏ６４ ｌ ６ １．９４８ ８ ３’０．５６５ ２ ７ ２．１７６０ ４ １．４２９ ８ ８ ２．３６３ ５ ５ １．６５６ ９ 下面检验基于密度函数法的初始聚类中心的 选择是否有效．密度函数法得到的３个初始聚类中 心如表２所示．可知，初始聚类中心对应的数据样本 编号分别为７９，８和１１３，它们分别落在了ＩＲＩＳ数据 集的三个标准分类样本子集中，即５０—１００，１～５０ 和１０１—１５０．采用密度函数法得到了比较理想的初 始聚类中心． 表２ 经密度函数法得到的初始聚类中心 对于ＩＲＩＳ数据集，采用随机初始化的ＦＣＭ聚 类算法和采用本文提出的改进的ＦＣＭ聚类算法得 到的目标函数的变化趋势如图１，图２所示．比较图 １，图２可见：①ＦｃＭ聚类采用本文提出的改进算法 初始化后，目标函数初始值较小，迭代次数少；②与 随机产生聚类中心相比，改进的ＦＣＭ聚类算法的收 敛更快． 迭代次数 图１随机初始化的ＦＣＭ目标函数趋势图 籁 闼 皿 迭代次数 图２基于改进算法的ＦＣＭ目标函数趋势图 ５ 结 语 现有的绝大多数ＦＣＭ聚类算法中，在解决确定 聚类数目的问题上都采取了事先给定的方法，本文 引入了平均信息熵的概念来确定最佳聚类数目．实 验结果表明，采用此方法能够得到理想的结果．在聚 类数目已知的前提下，通过密度函数法来获得有效 的初始聚类中心．与随机初始化方法相比较，基于密 度函数的初始化法迭代次数少，收敛速度快，可以很 快达到所需要的最优解． 参考文献： 【１］ＤＵＮＮ Ｊ Ｃ．Ａ Ｆｕｚｚｙ Ｒｅｌａｔｉｖｅ ｏｆｔｈｅ ＩＳＯＤＡＴＡ Ｐｒｏｃｅｓｓ ａｎｄ Ｉｔｓ Ｕｓｅ ｉｎ Ｄｅｔｅｃｔｉｎｇ Ｃｏｍｐａｃｔ Ｗｅｌｌ—ｓｅｐａｒａｔｅｄ Ｃｌｕｓｔｅｒｓ［Ｊ］．Ｊ．Ｃｙｂｅｍｅｔ— ｉｃｓ，１９７３，３（３）：３２—５７． ［２］ＢＥＺＤＥＫ Ｊ Ｃ．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ｗｉｔｈ Ｆｕｚｚｙ Ｏｂｊｅｃｔｉｖｅ Ｆｕｎｃｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｐｌｅｎｕｍ Ｐｒｅｓｓ，１９８１． ［３］ 王元珍，王健李，李晨阳．一种改进模糊聚类算法［Ｊ］，华中 科技大学学报，２００５，３３（２）：９２—９４． ［４］ ＣＨＩＵ ｓ Ｌ．Ｆｕｚｙｚ Ｍｏｄｅｌ Ｉｄｅｎｔｉｉｆｃａｔｉｏｎ Ｂａｓｄｅ ｏｎ Ｃｌｕｓｔｅｒ Ｅｓｔｉｍａｔｉｏｎ ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ ａｎｄ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ，１９９４，２（３）：２６７ —２７８． ［５］ＰＡＬ Ｎ Ｒ，ＢＥＺＤＥＫ Ｊ Ｃ．Ｏｎ Ｃｌｕｓｔｅｒ Ｖａｌｉｄｉｔｙ ｆｏｒ ｔｈｅ Ｆｕｚｚｙ Ｃ— ｍｅａｎｓ Ｍｏｄｅｌ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ，１９９５，３ （３）：３７０—３７９． （编辑：王萍）