广西科学院学报 ２００８，２４（４）：２８４～２８６ Ｊｏｕｒｎａｌ ｏｆ Ｇｕａｎｇｘｉ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ Ｖｏ１．２４，ＮＯ．４ Ｎｏｖｅｍｂｅｒ ２００８ 一种新的Ｋ—Ｍｅａｎｓ蚁群聚类算法 Ａ Ｎｅｗ ＡｎｔＣｌ ｕｓｔ Ａｌ ｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｋ－－Ｍｅａｎｓ Ａｌ ｇｏｒｉｔｈｍ 莫锦萍，陈 琴，马 琳，苏一丹 ＭＯ Ｊｉｎ—ｐｉｎｇ，ＣＨＥＮ Ｑｉｎ，ＭＡ Ｉ ｉｎ，ＳＵ Ｙｉ—ｄａｎ （广西大学计算机与电子信息学院，广西南宁 ５３０００４） （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ，Ｇｕａｎｇｘｉ， ５３０００４，Ｃｈｉｎａ） 摘要：针对蚁群聚类算法聚类质量不高的原因，使用Ｋ—Ｍｅａｎｓ算法改进蚁群聚类规则，提出一种新的Ｋ Ｍｅａｎｓ蚁群聚类算法（ＫＭ—ＡｎｔＣｌｕｓｔ），并通过实验验证新算法的聚类效果。实验结果表明，新的算法可以明显 提高聚类质量。 关键词：聚类蚁群算法 Ｋ一平均算法 中图法分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１００２—７３７８（２００８）０４—０２８４—０３ Ａｂｓｔｒａｃｔ：Ｄｕｅ ｔｏ ｔｈｅ ｌｏｗ ｃｌｕｓｔｅｒｉｎｇ ｑｕａｌｉｔｙ ｏｆ ＡｎｔＣｌｕｓｔ ａｌｇｏｒｉｔｈｍ，ａｎ ｉｍｐｒｏｖｅｄ ＡｎｔＣｌｕｓｔ ａｌｇｏｒｉｔｈｍ ｉＳ ｐｒｏｐｏｓｅｄ．ｗｈｉｃｈ ｏｐｔｉｍｉｚｅ ｔｈｅ ｒｕｌｅｓ ｏｆ ＡｎｔＣｌｕｓｔ ｍｏｄｅｌ ｗｉｔｈ Ｋ—Ｍｅａｎｓ ｍｉｎｄ。ｉＳ ｃａｌｌｅｄ ＫＭ—ＡｎｔＣｌｕｓｔ．Ｔｈｅｎ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｅｃｔｉｏｎ ｉＳ ｖｅｒｉｆｉｅｄ ｂｙ ｅｘｐｅｒｉｍｅｎｔｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｃａｎ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｉｍｐｒｏｖｅ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ，ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ，Ｋ—Ｍｅａｎｓ 聚类是数据在算法的指导下进行无人监督的分 遇则将无巢蚂蚁归到对方所属巢中；（３）两只同巢蚂 类。以Ｋ—Ｍｅａｎｓｌ】 和Ｋ—Ｍｅｄｏｉｄ＿２］为代表的划分法是 蚁 目遇，若相互接受，则增大 、Ｍ，和Ｍ 、 常用聚类算法中的一种。常用聚类算法多面向数值 Ｍ， 值；（４）两只同巢蚂蚁 相遇，若互不接受，则 属性，而蚁群聚类算法（ＡｎｔＣｌｕｓｔ）一 能处理任意类 减小 、 和 ， 、 。。值并将 值小的蚂蚁移 型的数据，具有强鲁棒性和适应性；但是其聚类结果 出巢；（５）两只不同巢蚂蚁相遇并相互接受则将两巢 随机，受数据和参数影响较大，聚类质量不高。本文 合并；（６）若不出现以上各情况，则不做任何操作。 使用Ｋ—Ｍｅａｎｓ算法思想改进蚁群聚类算法，提出一 蚁群聚类算法具有较好的鲁棒性和适应性，但 种新的Ｋ—Ｍｅａｎｓ蚁群聚类算法（ＫＭ—ＡｎｔＣｌｕｓｔ），并 是其聚类结果不稳定，主要原因是：第一，规则（３）依 在ＵＣＩ数据集上对新算法的聚类效果进行测试。 据Ｍ 判断踢出蚂蚁，但是根据算法思想，Ｍ， 为随 １ 传统蚁群聚类算法聚类质量分析 机量，其值不仅与蚂蚁所属巢规模有关，还与循环 次数相关。Ｍ 是蚂蚁 被巢成员接受的程度，而不 蚁群聚类方法是利用化学识别系统原理来聚 类，它不需假设对象的表示，仅用相似度ｓｉｅｒ（ ． ）表 是反应蚂蚁与巢的依存关系， 大并不能说明此 示对象 和 的关系 “］。每只人工蚁均有标签 巢是蚂蚁ｉ的最优归属，故依此踢出蚂蚁产生累积 Ｌａｂｅｌ，、基因Ｇｅｎｅｔｉｃ 、和模板Ｔｅｍｐｌａｔｅ 以及两个判 误差导致聚类质量降低。第二，循环迭代参数Ｉｔｅｒ和 断参数 、Ｍ 一。算法规则如下：（１）两只无巢蚂蚁 删除概率Ｐｄｅｌ的设置不尽合理。如果循环次数 相遇时创建一个新巢；（２）无巢蚂蚁与一有巢蚂蚁相 ＮＢ 一ｈｅｒ＊Ⅳ 不足，数据覆盖率低；太大则导 致过学习。参数Ｐｄｅｌ太大聚出的类数目较少，相反 收稿日期：２００８—１０—１２ 则类过多，影响聚类质量。因此，参数ｈｅｒ和Ｐｄｅｌ的 作者简介：莫锦萍（１９８４），女，硕士研究生，主要从事电子商务研究。 确定是保证聚类质量的重要环节。 莫锦萍等：一种新的Ｋ—Ｍｅａｎｓ蚁群聚类算法 ２８５ ２ Ｋ—Ｍｅａｎｓ蚁群聚类算法 ２．１使用Ｋ—Ｍｅａｎｓ改进蚁群聚类规则 ３聚类实验 ３．１实验平台、数据集及度量标准 实验平台：ＰＣ（配置Ｐｅｎｔｉｕｍ ４，ＣＰＵ ２．４ＧＨｚ， Ｋ—Ｍｅａｎｓ聚类算法基于误差平方和最小准则， 聚类结果通常不受初始中心的影响，较为稳定。对于 内存５１２Ｍ），操作系统是Ｗｉｎｄｏｗｓ ＸＰ。算法使用 ＶＣ编写。 大数据集，其强伸缩性和高效性常使聚类结果以局 部最优结束。因此我们引入Ｋ～Ｍｅａｎｓ算法改进聚类 数据集采用ＵＣＩ公共数据库（ｈｔｔｐ：／／ｋｄｄ．Ｉｃｓ． 规则。 设ｄ 为蚂蚁 到其所属巢中心的距离，规则改 进如下：（１）两只无巢蚂蚁ｉ， 相遇时创建一新巢并 计算巢中心；（２）无巢蚂蚁ｉ与有巢蚂蚁 相遇则将 蚂蚁ｉ归到蚂蚁Ｊ所属巢中并更新该巢中心；（３）同 巢互不接受的两只蚂蚁ｉ，Ｊ相遇时，计算ｄ 、ｄ ，将ｄ 值大的蚂蚁踢出巢并更新巢中心；（４）两只不同巢的 蚂蚁相遇且相互接受时，将两巢合并并更新巢中心； （５）若不出现以上各情况，则不做任何操作。 ２．２ Ｋ—Ｍｅａｎｓ蚁群聚类算法 模拟蚂蚁相遇过程完成后，蚁群聚类算法通过 将无巢蚂蚁分配到有巢且与其最相似的蚂蚁所属巢 中来完成重新分配操作。有巢这一前提了所找 到的蚂蚁实际上不一定最相似，这将导致聚类质量 下降。因此用Ｋ—Ｍｅａｎｓ算法将蚂蚁分配到巢中心与 其距离最小的巢来优化此操作。 设相遇过程完成后无巢蚂蚁个数为ｇ，存留的 大类个数为ＣｌａｓｓＮｕｍ，Ｃｌａｓｓ［－ＣｌａｓｓＮｕｍ３，蚂蚁总数 为Ⅳ。Ｋ—Ｍｅａｎｓ蚁群聚类算法描述为： ＭｉｎＤｉｓＣｌａｓｓｌ（ｉ，Ｃｌａｓｓ［３）／＊求巢中心距蚂蚁 ｉ最近的巢＊／ Ｃｌｕｓｔ（） ｆｏｒ（ｒ一１；ｒ＜一Ｉｔｅｒ＊Ｎ；ｒ＋＋） ｛ ｉ＝ｒａｎｄ（） ｎ； ｊ—ｒａｎｄ（）％ｎ； Ｃｌｕｓｔｅｒ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｒｕｌｅｓ ｉｎ Ｓｅｃｔ ２．２ ｝ Ｒｅａｓｓｉｇｎ（） ｛ ｆｏｒ（ｉ一１；ｉ％ｑ；ｉ＋＋） Ｌａｂｅｌ 一ＭｉｎＤｉｓＬａｂｅｌ（ｉ，ＣｌａｓｓＦ￣）； ｝ Ｕｃｉ．ｅｄｕ）提供的数据集（见表１）。 表１ ＵＣＩ数据集 聚类性能评价采用文献［６］中介绍的Ｆ— ｍｅａｓｕｒｅ方法。Ｆ—ｍｅａｓｕｒｅ组合了信息检索中查准率 （ｐｒｅｃｉｓｉｏｎ）和查全率（ｒｅｃａｌ１）的思想。一个聚类 相 对于分类 的ｐｒｅｃｉｓｉｏｎ和ｒｅｃａｌｌ定义为：Ｐ— ｐｒｅｃｉｓｉｏｎ（ ， ）一Ｎｕ／Ⅳ ，Ｒ＝ｒｅｃａｌｌ（ ， ）＝Ｎｕ／Ⅳ ，其 中Ⅳ ，是在聚类 中分类 的数目，Ⅳ 是聚类Ｊ所有 对象的数目，Ⅳ 是分类ｉ所有对象的数目。分类ｉ的 Ｆ—ｍｅａｓｕｒｅ定义为：Ｆ（ ）一２ ＰＲ／（尸＋Ｒ）。 对分类ｉ而言，哪个聚类的Ｆ—ｍｅａｓｕｒｅ值高，就 认为该聚类代表分类 的映射，即Ｆ—ｍｅａｓｕｒｅ表示分 类ｉ的评判分值。对聚类结果 来说，其总Ｆ— ｍｅａｓｕｒｅ可由每个分类ｉ的Ｆ—ｍｅａｓｕｒｅ加权平均得 （１ｉ ｌ＊Ｆ（ ）） 到：Ｆ 一 ＿＿＿＿，其中ｌｉＩ为分类ｉ中所有对 象的数目。 ３．２ 实验步骤 步骤１ 使用Ｂｒｅａｓｔ—ｃａｎｃｅｒ数据集进行参数训 练，训练结果如图１和图２所示。从图１和图２结果 可知，当Ｐｄｅｌ一０．０６，ｈｅｒ：６０时聚类取得最佳效 果，故实验中我们取Ｐｄｅｌ＝０．０６，ｈｅｒ＝６０。 遥 霹 ＊ 籁 Ｏ Ｏ１ ｏ ０２ ｏ ０３ ｏ ０４ Ｏ ０５ ｏ ０６ ｏ ０７ ｏ ｏ８ 删除概率 图１删除概率与聚类总数平均值关系 ２８６ 广西科学院学报第２４卷第４期２００８年１１月 坦 ４ 结束语 露 １斗 本文将Ｋ—Ｍｅａｎｓ聚类思想引入蚁群聚类算法 景 嚣 中，并在ＵＣＩ数据集上进行实验。实验结果表明，Ｋ— Ｅ Ｍｅａｎｓ优化的蚁群聚类算法从距离角度反应蚂蚁与 巢成员的接受程度，使得聚类有更加合理的判断依 据，聚类质量得到了进一步的提高。 图２循环迭代参数与Ｆ ｍｅａｓｕｒｅ平均值关系 参考文献： 步骤２ 用ＡｎｔＣｌｕｓｔ算法对ＵＣＩ数据集进行 ［１］ＭａｃＱｕｅｅｎ Ｊ．Ｓｏｍｅ ｍｅｔｈｏｄｓ ｆｏｒ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｎｄ 聚类。 ａｎａｌｙｓｉｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｏｂｓｅｒｖａｔｉｏｎｓ：ｐｒｏｃ ｏｆ ｔｈｅ ５ｔｈ 步骤３用改进的蚁群聚类算法（Ｋ—Ｍｅａｎｓ蚁 Ｂｅｒｋｅｌｅｙ Ｓｙｍｐ ｏｎ Ｍａｔｈ Ｓｔａｔｉｓｔ［ｃ］．Ｉ９６７：２８１—２９７． 群聚类算法）对ＵＣＩ数据集进行聚类。 Ｅ２］Ｋａｕｆｍａｎ Ｊ，Ｒｏｕｓｓｅｅｕｗ Ｐ Ｊ．Ｆｉｎｄｉｎｇ ｇｒｏｕｐｓ ｉｎ ｄａｔａ：ａｎ 步骤４结果比较与分析。 ｉｎｔｒｏｄｕｃｔｉｏｎ ｔＯ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ ＥＭ］．Ｎｅｗ Ｙｏｒｋ：Ｊｏｈｎ ３．３实验结果及分析 Ｗｉｌｅｙ＆Ｓｏｎｓ，１９９０． 两个算法均运行１０次后取Ｆ—ｍｅａｓｕｒｅ平均值 ｒ３］ Ｎ Ｌａｂｒｏｃｈｅ，Ｎ Ｍｏｎｍａｒｃｈｅ，Ｇ Ｖｅｎｔｕｒｉｎｉ．Ａ ｎｅｗ 作为实验结果，结果如表２所示。 ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｃｈｅｍｉｃａｌ ｒｅｃｏｇｎｉｔｉｏｎ 表２ ＵＣＩ数据集聚类结果 ｓｙｓｔｅｍ ｏｆ ａｎｔｓ：ｐｒｏｃ ｏｆ １ ５ｔｈ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ（ＥＣＡＩ ２００２）［Ｃ］．Ｌｙｏｎ ＦＲＡＮＣＥ，２００２：３４５—３４９． ｒ４］Ｎｉｃｏｌａｓ Ｌａｂｒｏｃｈｅ，Ｎｉｃｏｌａｓ Ｍｏｎｍａｒｃｈｅ，Ｇｉｌｌｅｓ Ｖｅｎｔｕｒｉｎｉ． Ｗｅｂ ｓｅｓｓｉｏｎｓ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ａｒｔｉｆｉｃｉａｌ ａｎｔｓ ｃｏｌｏｎｉｅｓ． ［ＥＢ／ＯＬ］．［２００６一Ｏ１—１２］．ｈｔｔｐ：／ｗｗｗ．ｈａｎｔ．ｉ． ｕｎｉｖｔｏｕｒｓ ｆｒ／ｗｅｂｈａｎｔ／ｐｕｂ／ＬａｂＭｏｎＶｅｎ０３ａ．ｗｗｗ．ｐｄｆ． ｒ５］Ｎｉｃｏｌａｓ Ｉ ａｂｒｏｃｈｅ，Ｎｉｃｏｌａｓ Ｍｏｎｍａｒｃｈ６，Ｇｉｌｌｅｓ Ｖｅｎｔｕｒｉｎｉ． 文献［７］中说明数据集Ｉｒｉｓ用于聚类时可以作 ＡｎｔＣｌｕｓｔ：ａｎｔ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｗｅｂ ｕｓａｇｅ ｍｉｎｇ［ｃ］． 两类处理。从表２可知，Ｋ—Ｍｅａｎｓ蚁群聚类算法获得 Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００３：２５—３６． 更好的聚类效果，其Ｆ—ｍｅａｓｕｒｅ平均值均比蚁群聚 Ｅ６３ Ｙａｎｇ Ｙ，Ｋａｍｅｉ Ｍ．Ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ ｕｓｉｎｇ ｓｗａｒｍ 类算法的高，最高达到了０．９８８７２２；另外，改进算法 ｉｎｔｅｌｌｉｇｅｎｃｅ：ＩＥＥＥ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｙｍｐｏｓｉｕｍ 聚类总数平均值也比蚁群聚类算法的更接近实际分 ［Ｍ］．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ，２００３： ６５—７１． 类数。在实验中虽然聚类质量均有提高，但是有的效 ［７ ２ Ｐａｒａｇ Ｍ Ｋａｎａｄｅ，Ｌａｗｒｅｎｃｅ Ｏ Ｈａｌ１．Ｆｕｚｚｙ ａｎｔｓ ａｓ ａ 果并不明显，如表２中的Ｗｉｎｅ数据集，这主要是数 ｃｌｕｓｔｅｒｉｎｇ ｃｏｎｃｅｐｔ：ｐｒｏｃ ｏｆ ｔｈｅ ２２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ 据集中类与类间的差别不大，数据交叉重合比较多 Ｃｏｎｆｅｒｅｎｃｅ ｏｆ ｔｈｅ Ｎｏｒｔｈ Ａｍｅｒｉｃａｎ Ｆｕｚｚｙ Ｉｎｆｏｒｍａｔｉｏｎ 导致聚类效果不明显，聚类质量不高。 Ｐｒｏｃｅｓｓｉｎｇ Ｓｏｃｉｅｔｙｍｃ］．２００３：２２７—２３２． （责任编辑：韦廷宗） 瑞典研究显示高热量快餐食品易诱发老年痴呆症 老年痴呆症是发生在老年期及老年前期的一种原发性退行性脑病，指的是在没有意识障碍的状态下，记 忆、思维、分析判断、情绪等方面出现障碍。瑞典卡罗林斯卡医学院的研究人员研究显示，高热量的快餐食品 容易诱发老年痴呆症。研究人员在用脂肪、糖和胆固醇含量丰富的快餐食品喂食老鼠９个月后发现，老鼠脑 中出现了类似老年痴呆症患者脑部的Ｔａｕ蛋白纤维状缠结情况。Ｔａｕ蛋白纤维状缠结是老年痴呆症患者典 型的病理特征之一，这种蛋白纤维状缠结会影响患者的认知能力。研究人员指出，虽然上述成果对老年痴呆 症的防治研究有启发，但是仍需进一步研究高热量快餐食品易诱发老年痴呆症的具体原因。 （据科学网）
