维普资讯 http://www.cqvip.com ・３０・ 计算机应用研究 ２００７矩 一种基于群体智能的多主体聚类算法 刘相双 ，徐建良。，杨文琳 ，陈卓 （１．中国海洋大学计算机科学系，山东青岛２６６０７１；２．青岛海信通信有限公司，山东青岛２６６０７１） 摘要：目前聚类算法普遍存在对初始化参数和异常数据敏感，难以找到最优聚类以及聚类的有效性等问题。 利用群体智能和多主体系统具有的自组织性、健壮性、可扩展性和简单性等优点，给出了一种新型的优化聚类算 法。在三维空间搭建主体运行环境，丰富主体的记忆、通信以及信息协调能力，增强主体的分析和判断能力。实 验证明，该新型聚类算法具有运行速度快，准确性高以及对数据的输入顺序不敏感，能应付异常数据，处理高维、 高复杂性数据等优点，可应用于图像处理、模式识别、文档归类等多个领域。 关键词：群体智能；多主体系统；聚类 中图法分类号：ＴＰ３０１．６ 文献标识码：Ａ 文章编号：１００１－３６９５（２００７）０２－００３０－０３ Ｍｕｌｔｉ—Ａｇｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｈｅｏｒｙ ＬＩＵ Ｘｉａｎｇ－ｓｈｕａｎｇ 一，ＸＵ Ｊｉａｎ．１ｉａｎｇ ，ＹＡＮＧ Ｗｅｎ．１ｉｎ ，ＣＨＥＮ Ｚｈｕｏ （１．Ｄｅｐｔ．ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｏｃｅａｎ ＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎａ，Ｑｉｎｇｄａｏ Ｓｈａｎｄｏｎｇ ２６６０７１，Ｃｈｉａ；２．ＨｉｎｓｅｎｓｅＲ＆Ｄ，Ｑｉｎｇｄａｏ Ｓｈａｎｄｏｎｇ ２６６０７１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｒａｄｉｔｉｏｎａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｇｅｎｅｒａｌｌｙ ｈａｓ ｓｏｍｅ ｐｒｏｂｌｅｍｓ，ｓｕｃｈ ａｓ ｔｈｅ ｓｅｎｓｉｔｉｖｉｔｙ ｔｏ ｉｎｉｔｉａｌｉｚｉｎｇ ｐａｒａｍｅｔｅｒ ａｎｄ ａｂｎｏｒｍａｌ ｄａｔａ，ｄｉｉｃｕｌｆｔｙ ｏｆ ｆｉｎｄｉｎｇ ｏｕｔ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔ ａｎｄ ｔｈｅ ｖａｌｉｄｉｔｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａ ｎｅｗ－ ｓｔｙｌｅ ｏｐｔｉｍｉｚｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｓｗａｒｎｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ ｍｕｌｔｉ－Ａｇｅｎｔ ｓｙｓｔｅｍ，ｗｈｉｃｈ ｈａｓ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｓｅｒｆ－ｏｒｇａｎｉｚａｔｉｏｎ，ｒｏｂｕｓｔｎｅｓｓ，ｅｘｐａｎｄａｂｉｌｉｔｙ ａｎｄ ｓｉｍｐｌｉｃｉｔｙ，ｉｓ ｐｒｏｖｉｄｅｄ．Ｉｎ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｔｈｅ ａｇｅｎｔｓ ｍｏｖｅ ｉｎ ａ ｔｈｒｅｅ—ｄｉｍｅｎ－ ｓｉｏｎａｌ ｓｐａｃｅ ａｎｄ ｈａｖｅ ｔｈｅ ａｂｉｌｉｔｉｅｓ ｏｆ ｍｅｍｏｒｙ，ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ ｃｏｏｒｄｉｎａｔｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅ ａｇｅｎｔｓ ａｌｓｏ ａｒｅ ｓｔｒｅｎｇｔｈｅｎｅｄ ｔｈｅ ｃａｐａｂｉｌｉｔｉｅｓ ｏｆ ｊｕｄｇｍｅｎｔ ａｎｄ ａｎａｌｙｓｉｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ＣＯｎｆＯｒｍ ｔｈａｔ ｔｈｉｓ ｌｇｏｒａｉｔｈｍ ｈａｓ ｍａｎｙ ｍｅｒｉｔｓ ｓｕｃｈ ａｓ ｉｎｓｅｎｓｉｔｉｖｅ ｔｏ ｔｈｅ ｏｒｄｅｒ ｏｆ ｔｈｅ ｄａｔａ，ｃａｐａｂｉｌｉｔｙ ｏｆ ｄｅａｌｉｎｇ ｗｉｔｈ ｅｘｃｅｐｔｉｏｎａｌ，ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎ ａｎｄ ｃｏｍｐｌｉｃａｔｅｄ ｄａｔａ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ Ｃａｎ ｂｅ ｕｓｅｄ ｉｎ ｔｈｅ ｆｉｅｌｄｓ ｏｆ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ，ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ，ｄｏｃｕｍｅｎｔ ｃｌａｓｓｉｉｆｃａｔｉｏｎ ａｎｄ ＳＯ ｏｎ． Ｋｅｙ ｗｏｒｄｓ：Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ；Ｍｕｌｔｉ－Ａｇｅｎｔ Ｓｙｓｔｅｍ；Ｃｌｕｓｔｅｒｉｎｇ 信以及信息协调能力，增强了主体的分析和判断能力，从而增 １ 引言 聚类又称分割，是将物理或抽象的数据对象集合分组， 成为由类似的对象组成的多个类，使不同类间的相似性最小 化，而相同类内相似性最大化 。聚类是数据挖掘研究的一 个重要方面，是一种无指导的学习过程 。数据聚类的研究 强了个体的智能性和灵活性，优化了算法性能。 ２基本理论 ２．１群体智能理论 能推动统计学、机器学习、空间数据库技术、生物学以及市场营 销的发展。目前常见的几大类聚类算法的基本思想有 法 Ｊ、层次法 、基于密度的方法 和基于网格的方法 ｊ、基 群体智能是指无智能的主体通过合作表现出智能行为的 特性。一些受群居生物筑巢、觅食、迁徙、清扫蚁穴等行为启发 而设计的算法成功地解决了组合优化、通信网络和机器人等领 域的实际问题。群体智能在没有集中控制并且不提供全局模 型的前提下，为寻找复杂的分布式问题的解决方案提供了基 础 。将群体智能应用于聚类算法，可使聚类算法具有与群 体智能算法相同的特点，它利用个体与个体和个体与环境的交 互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有 于模型的方法 。以上各种算法虽各有优点，但普遍存在对 初始化参数敏感，处理异常数据困难，难以找到最优聚类以及 聚类的有效性等问题。 本文利用群体智能理论和多主体系统具有的自组织性、健 壮性、可扩展性、简单性等优点 Ｊ，在基于群体智能聚类的自 动机和数学模型 的基础上，给出一种新型的优化聚类算法。 该算法在三维空间中搭建主体运行环境，丰富主体的记忆、通 健壮性和可视化等特点。 ２．２多主体系统 多主体系统理论与技术的研究源自分布式人工智能 收稿日期：２００５—１１—２６；修返日期：２００６．０２—２２ 基金项目：国家自然科学基金资助项目（６０３７４０３１）；山东省 （ＤＡＩ），２０世纪９０年代它成了ＤＡＩ领域的研究热点，目前已 在许多领域得到了广泛的应用。多主体系统主要研究在逻辑 上或物理上分离的多个主体之间进行协调智能行为，最终实现 自然科学基金资助项目（Ｙ２００２Ｇ１８） 维普资讯 http://www.cqvip.com 第２期 刘相双等：一种基于群体智能的多主体聚类算法 ・３１・ 问题求解… 。主体是具有信念、愿望、意图、能力、选择、承诺 等心智状态的实体，比对象的粒度更大，智能性更高，而且具有 一定自主性。主体试图自治地、地完成任务，而且可以与 环境交互，与其他主体通信，通过规划达到目标。 ３ 基于群体智能的多主体聚类算法 基于群体智能的聚类算法起源于对蚁群、蚁卵的分类研 究。Ｄｅｎｅｕｂｏｕｒｇ等人提出了基本模型（Ｂａｓｉｃ Ｍｏｄｅ１），这种模型 主要是基于对于单只蚂蚁拾起、放下物体的行为方式进行建 模。Ｌｕｍｅｒ和Ｆａｉｅｔａ将ＢＭ推广应用到数据分析。吴斌等人在 简化分类模型的基础上系统地提出了一种基于群体智能的聚 类算法。本文在借鉴多主体系统相关思想的基础上，提出了一 种基于群体智能的ＭＡＣ（Ｍｕｌｔｉ—Ａｇｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ，多主 体聚类算法），并将其成功应用于新闻文本的自动归类中。 区别于以往的群体智能聚类算法，本文提出的新型聚类算 法具有如下特点： （１）将知识约简后的数据矢量组随机地放入一个三维空 间的二维平面中。 （２）聚类主体具有一定的记忆特点。当其遇到或搭建起 一个堆时，会将该堆的特征信息以及位置信息记录下来。 （３）聚类主体具有分析能力。主体在聚类过程中会遇到 堆或物体，主体会自行区分这两种不同情形，从而采取不同的 行动来区别对待。 （４）聚类主体具有判断能力。当主体拿起一个数据矢量， 它首先去搜寻现有的记忆信息，如果当前数据矢量信息能够与 以往的堆进行合并，那么它会将此矢量直接归并到相似堆中。 （５）聚类主体具有通信功能。它能够将记忆信息传播给 其他主体，这样就能实现聚类主体间的信息共享。 （６）聚类主体具有信息协调能力。为适应网格中数据矢 量分布和堆分布的动态特性，主体需要能够实时地去更新记忆 链表中的堆信息，以保证信息的一致性。 以上的这些特点使群体智能中的个体有了自身的智能特 性，加快了算法的收敛速度，提高了算法性能。 ３．１ ＭＡＣ算法中的聚类主体 根据ＭＡＣ算法中聚类主体所具有的智能特性，其结构体 及通信环境设计如图１所示。 ３．２ ＭＡＣ算法的设计 （１）初始化 在初始化过程中，首先根据待聚类的数据数目Ｎ。，生成一 个二维网格表ｃ，ｃ中网格的数目要大于 。将待聚类的数 据集｛Ｏ ｝随机地放入Ｇ中，保证每个数据Ｏ．占据一个网格 ｇ ；然后将所分配的主体｛Ａ ｝，采取与｛０ ｝相同的方式随机地 放入Ｇ中。初始化结果如图２所示，其中每个网格中的小矩形 代表｛Ｏ ｝，黑圆代表｛Ａ ｝。 （２）各主体进行聚类 ’ 该部分为ＭＡＣ算法的核心内容。所有的聚类主体均按照 同样的规则进行运动。算法流程如图３所示。 （３）结果输出 经过聚类主体对数据根据其相似性进行沿网格的多次搬 运后，会将初试状态下散乱的数据堆积在多个不同的网格中。 如图４所示。因此，ＭＡＣ算法的聚类数目就是 Ｇ中非空网格 的数目，每一类所包含的数据项就是处于同一网格中的数据 项。 外 界 动 ● ● 态 环 境 ● 号 口 口 ● ● 零 图１聚类主体结构及通信环境 图２初始化结果 次数是否 ≥ —、——一 是ｌ 否 记忆及通信＞１＜ 粤 苎曾 裹 蕃篝 所拿物体 否 人已知类 匝亟 否 否 否 图３多主体聚类流程图 ４ 实验结果 本文采用如下两种标准来评价聚类结果： ｍ （１）聚类收缩率（Ｒａｔｅ ｏｆ Ｃｏｎｔｒａｃｔｉｌｉｔｙ，Ｃ，）：Ｃ ＝ ｘ１００％ ｍｒｅｓｕｌＩ ｍ． （２）聚类正确率（Ｒａｔｅ ｏｆＶｅｒａｃｉｔｙ， ）： ＝ 世×１００％ Ｈｌ越 其中ｍ 为完全聚类数目，ｍ…。 为运行结果聚类数目，ｍ 为 正确聚类数据数目，ｍ 为全部数据数目。由上述两个评价标 准的定义可知其取值范围分别是Ｃ，＞０，０≤ ≤１，且最理想的 聚类结果是Ｃ ＝１， ＝１，即由聚类结果所得的收缩率和正确 率越接近１，则聚类效果越好。 为了验证所提出的基于群体智能的多主体聚类算法的有 效性，本文采用新浪网的部分新闻文本进行了多次文本自动归 类试验。试验文本数据的主题包括教育、经济、政治、体育、军 事、娱乐、医疗、科技类共５０３篇新闻报导。首先根据词频 提取出每篇新闻报导的５—１０个关键词，并对其进行标注，对 标注后的结果分别采用传统的蚁群算法和ＭＡＣ算法进行聚 类。对比实验运行结果如表１和表２所示。 由上面的结果可以分析得出，ＭＡＣ算法的聚类收敛速度 维普资讯 http://www.cqvip.com ・３２・ 计算机应用研究 ２００７年 及准确性较传统蚁群算法有了较大提高，ＭＡＣ算法在蚂蚁数 为１００左右时，聚类结果基本稳定，而此时传统蚁群聚类算法 ［３］Ｂｅｒｅｈｔｏｌｄ Ｓ，Ｋｅｉｍ Ｄ，Ｋｒｉｅｇｅｌ Ｈ Ｐ．Ｔｈｅ ｘ．ｔｒｅｅ：Ａｎ Ｉｎｄｅｘ Ｓｔｒｕｃｔｕｒｅ ｆ０ｒ ＨｉｇＩＩ・ｄｉｍｅｎｓｉｏｎａｌ Ｄａｔａ［ｃ］．Ｂｏｍｂａｙ，Ｉｎｄｉａ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｈｔｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ Ｄａｔａｂａｓｅｓ，１９９６．２８－３９． 的正确率约为７５％，收缩率仅为６６％。 实验证明，本文提出的ＭＡＣ算法具有运行速度快，准确性 高以及对数据的输入顺序不敏感等优点。由于其高效性，因此 ［４］Ｓｈｅｉｋｈｏｌｅｓｌａｍｉ Ｇ，Ｃｈａａｅｑｅｅ Ｓ，Ｚｈａｎｇ Ａ．Ｗａｖｅ．Ｃｌｕｓｔｅｒ：Ａ Ｍｕｌｉｔ． ｅｓｒｏｌｕｔｉｏｎ ＣｌｕｓｔｅｒｉｎｇＡｐｐｒｏａｃｈｆｏｒＶｅｙｒ Ｌａｒｇｅ Ｓｐａｔｉｌａ Ｄａｔａｂａｓｅｓ［Ｃ】． Ｎｅｗ Ｙｏｒｋ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ ＬｌＩ葛ｅ Ｄａｔａｂａｓｅｓ，１９９８．４２８－４３９． 该算法适用于处理高维、高复杂性数据，同时该算法也可应用 于图像处理、模式识别、经济分析等多个领域。 表１ ＭＡＣ算法运行结果 主体数 ５０ ６０ ７０ ８０ ９０ ｌ００ ｌｌ０ ［５］Ａｇｒａｗａｌ Ｒ。Ｇｅｈｒｋｅ Ｊ，Ｇｕｎｏｐｕｌｏｓ Ｄ，ｅｔ ．Ａｕｔｏｍａｉｔｃ Ｓｕｂｓａｃｐｅ Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ｈｉｇｈ Ｄｉｍｅｎｓｉｏｎａｌ Ｄａｔａ ｆｏｒ Ｄａｔａ Ｍｉｎｉｎｇ Ａｐｐｌｉｃａｔｉｏｎｓ 目 国 ｖ， 步数 ３０ ３０ ３０ ３０ ３０ ３０ ３０ ［ｃ］．Ｓｅａｔｌｔｅ。ＷＡ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｈｔｅ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔｅｎａｒｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ，１９９８．９４－１０５． Ｃ ７３％ ８０％ ８Ｏ％ ８９％ ｌ０ｏ％ 。ｔ００％ｌｔ００％ ８５％ ９１％ ９３％ ９６％ ９７％ 。９９％ ９９％ ［６］Ｈｉｎｎｅｂｕｒｇ Ａ，Ｋｅｉｍ Ｄ Ａ．Ｏｐｔｉｍａｌ Ｇｉｒｄ－Ｃｌｕｓｔｅｉｒｎｇ，Ｔｏｗａｒｄｓ Ｂｒｅａ－ ｋｉｎｇ ｈｔｅ Ｃｕｒｓｅ ｏｆ Ｄｉｍｅｎｓｉｏｎｌａｉｔｙ ｉｎ Ｈｉｈ－ｇｄｉｍｅｎｓｉｏｎａｌ Ｃｌｕｓｔｅｉｒｎｇ［ｃ］． Ｅｄｉｎｂｕｒｇｈ，Ｓｃｏｔｌａｎｄ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ－ ｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ ＬｌＩ葛ｅ Ｄａｔａｂａｓｅｓ，１９９９．５０６・５１７． 表２传统蚁群聚类算法运行结果 蚂蚁数 ５０ ６０ ７０ ８０ ９０ ｌ００ ｌｌ０ 步数 ３０ ３０ ３０ ３０ ３０ ３０ ３０ Ｃ ５ｏ％ ５０％ ５７％ ６６％ ６６％ ６６％ ７３％ 图４聚类后结果 Ｖ， ６１％ ６３％ ６９％ ７１％ ７４％ ７５％ 舳％ 【７］ＨｉｒｍｅｂｕｒｇＡ，Ｋｅｉｍ Ｄ Ａ．Ａｎ Ｅｆｆｉｃｉｅｎｔ Ａｐｐｒｏａｃｈ ｔｏ Ｃｌｕｓｔｅｒｉｎｇ ｉｎ ５结论 聚类是一个古老的问题，是按照事物间的相似性进行区分 和分类的过程，是一种无监督的分类。它伴随着人类社会的产 生和发展而不断深化，已成为数据挖掘的常用技术，现已广泛 ＩＪａｒｇｅ Ｍｕｌｉｔｍｅｄｉａ Ｄａｔａｂａｓｅｓ ｗｉｈｔ Ｎｏｉｓｅ［ｃ］．Ｎｅｗ Ｙｏｒｋ：Ｐｒｏｃｅｅｄｉｎｇｓ ０ｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｄｇｅ Ｄｉｅｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ（ＫＤＤ’９８），１９９８．５８－６６． ［８］Ｃｈｅｎ Ｚｈｕｏ，Ｍｅｎｇ Ｑｉｎｇ－ｃｈｕｎ．Ａ Ｎｅｗ－ｔｙｐｅ ｎＩｃｅｒｍｅｎｔａｌ Ｃｌｕｓｔｅｉｒｎｇ ｌ－Ａ ｇｏｒｉｈｔｍ Ｂａｓｅｄ ｏｎ Ｓｗａｒｍ Ｉｎｔｅｌｉｇｅｎｃｅ ｈｅＴｏｒｙ［ｃ］．Ｓｈａｎｇｈａｉ：Ｔｈｅ ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ（ＩＣＭ－ 应用于图像处理、文档归类、模式识别等多个领域。群集智能 和多主体系统的研究虽处于初级阶段，但由于其具有的自组织 ＬＣ２００４），２００４．１７６８・１７７２． 性、健壮性、可扩展性、简单性等优点，已经引起越来越多的研 究者的关注，并广泛应用于组合优化、通信网络和智能控制等 领域，其必将成为以后计算机研究发展的一个重要方向。 参考文献： ［１］Ｈａｔｒ Ｊｉａ－ｗｅｉ，ｅｔ ２．Ｄａｔ０ａ Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ ａｎｄ Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．范 明，等．北京：机械工业出版杜，２０００．２．２０． ［９］陈卓，盂庆春，魏振钢．基于群体智能理论的聚类模型及优化算法 ［Ｊ］．计算机工程。２００５，３２（３）：３４－３６． ［１Ｏ］Ｅ Ｂｏｎａｂｅａｕ，Ｍ Ｄｏｒｉｇｏ，Ｇ ｈｅＴｒａｕｌａｚ．Ｓｗａｒｍ ｎＩｔｅｌｌｉｇｅｎｃｅ：Ｆｒｏｍ Ｎａ－ ｔｕｒｌａ ｔｏ Ａｒｔｉｉｆｃｉｌａ Ｓｙｓｔｅｍｓ【Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｏｘｆｏｒｄ Ｕｎｉｖｅｓｒｉｔｙ Ｐｒｅｓｓ， １９９９．５．４３． ． ［１１］王长缨，姚莉，张维明，等．一种新的多主体学习方法［Ｊ］．小型徽 型计算机系统，２００３，２４（３）：３４４．３４７． ［２］Ｅｓｔｅｒ Ｍ，Ｋｒｉｅｇｅｌ Ｈ Ｐ，ｅｔ Ｄｅｎｓｉｔｙ・ｂａｓｅｄ Ａｌｇｏｉｒｔｈｍ ｆｏｒ Ｄｉｃｓｏｖｅｒｉｎｇ 作者简介： 刘相双（１９７４・），男，硕士研究生，主要研究方向为嵌入式系统、图像图 Ｃｌｕｓｔｅｒｓ ｉｎ Ｌａｒｇｅ Ｓｐａｔｉａｌ Ｄａｔａｂａｓｅｓ［ｃ］．Ｐｏｄａｎｄ，ＯＲ：Ｐｒｏｃ．ｏｆ １９９６ ｈｔ．Ｃｏｎｆ．ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ，１９９６．２２６・２３１． 形处理、模糊信息处理等。 （上接第２９页） ｄｉｎｇ Ｕｓｉｎｇ Ｅｆｆｉｃｉｅｎｔ Ｍｕｌｔｉ・ｄｉｍｅｎｓｉｏｎａｌ Ｒａｎｇｅ Ｍａｔｃｈｉｎｇ［ｃ］．Ｐｒｏｃ．ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ，１９９８． ６结束语 本文结合Ａｈｏ－Ｃｏｒａｓｉｃｋ多关键字匹配算法的基本思想，扩 充了ＲＦＣ算法，使新算法能够对含有变长字符串域的报文进 行分类。实验结果表明，新算法具有很快的匹配速度，而且易 ［５】Ｖ Ｓｒｉｎｉｖｓａａｎ，Ｇ Ｖａｒｈｅｇｃ，Ｓ ｓＳｕｒｉ，ｅｔ吐Ｆａｓｔ ｎｄ ａＳｅａｌｂｌａｅ Ｌ￣ｒｅｒ ４ Ｓｗｉｔｃｈｉｎｇ［ｃ］．Ｐｒｏｃ．ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ，１９９８． ［６］ＰＧｕｐｔａ，ＮＭｃＫｅｏｗｎ．Ｐａｃｋｅｔ Ｃｌｓａｓｉｆｉｃａｉｔｏｎ ｏｎＭｕｌｔｉｉｆｅｌｄｓ［ｃ］．Ｐｒｏ－ ｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ．１９９９．１４６・ｌ６ｏ． 【７］Ｖ Ｓｒｉｎｉｖａｓａｎ，Ｓ Ｓｕｒｉ，Ｇ Ｖａｒｇｈｅｃ．Ｐａｓｃｋｅｔ Ｃｌａｓｓｉｉｆｃａｔｉｏｎ Ｕｓｉｎｇ Ｔｕｐｌｅ Ｓｐａｃｅ Ｓｅａｒｃｈ［ｃ］．Ｐｒｏｃ．ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ，１９９９． ［８］Ｅ Ｗ Ｓｐｉｔｚｎａｇｅ１．ＣｏｍｐｒｅｓｓｄＤａｔｅａ ＳｔｒｕｃｔｕｒｅｓｆｏｒＲｅｃｕｒｓｉｖｅ Ｆｌｏｗ Ｃｌｓａ． ｓｉｌｆｃａｔｉｏｎ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｃｓｅ．ｓｅａｓ．ｗｕｓｔ１．ｅｄｕ／ｔｅｅｈｒｅｐｏｒｔｆｄｅｓ／ｇｅ－ ｔｒｅｐｏｒｔ．ａｓｐ？３０５，２００３． 于实现，是一种值得应用的报文分类算法。 当然，新算法仍有局限性，特别是当字符串中包含的字符 数较大时，构造匹配自动机需要较大的存储空间。如何进一步 降低空间开销，将是下一步研究工作的重点。 参考文献： ［１］Ｓｒｉｎｉｖａｓｎ Ｖ，Ｖａｒｇｈｅｓｃ Ｇ．Ｆａｓｔ Ｓｃａｌｂｌａｅ Ｌｅｖｅｌ Ｆｏｕｒ Ｓｗｉｔｃｈｉｎｇ［Ｊ］． ＡＣＭ．［９］Ａｈｏ Ａ Ｖ，Ｍ Ｊ Ｃｏｒａｓｉｃｋ．Ｅｆｉｆｃｉｅｎｔ Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ：Ａｎ Ａｉｄ ｔｏ Ｂｉｂｌｉｏ－ ｇｒａｐｈｉｃ ｅａｒＳｃｈ［ｃ］．Ｃｏｍｍｕｎｉｃａｉｔｏｎｓ ｏｆｔｈｅ ＡＣＭ，１９７９．３３３・３４０． Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｎｅｗ，１９９８，２８（４）：１９１・２０５． 作者简介： 田珂（１９７３－），男，四川成都人，博士研究生，主要研究方向为工作流技 术、电子政务、电信网络管理；朱清新（１９５４－），男，四川成都人，博导， 主要研究方向为算法设计、系统仿真、最优控制与搜索；向培素 （１９７４．）。女，四川成都人，硕士，主要研究方向为电信网络管理、工作 流技术、电子政务。 ［２］Ｖ Ｓｒｉｎｉｖａｓａｎ，Ｇ ＶａｒｇｌＩｅｓｅ．Ｆａｓｔ ＩＰ Ｌｏｏｋｕｐｓ Ｕｓｉｎｇ Ｃｏｎｔｒｏｌｌｄ Ｐｒｅｅｉｆｘ Ｅｘｐａｎｓｉｏｎ［ｃ］．Ｐｒｏｃ．ｏｆ ＡＣＭ ＳＩＧＭＥＴＲＩＣＳ，１９９８． ［３］Ｍ Ｗａｌｄｖｏｇｅｌ，Ｇ Ｖａｒｇｈｅｓｃ。Ｊ Ｔｕｒｎｅｒ，ｅｔ ２０．Ｓｅａｌａｂｌｅ Ｈｉｈ・ｇｓｐｅｅｄ ＩＰ Ｒｏｕｉｔｎｇ Ｌｏｏｋｕｐｓ［ｃ］．Ｐｒｏｅ．ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ，１９９８．２５・３６． ［４］Ｔ Ｖ Ｌａｋｓｈｍａｎ，Ｄ Ｓｔｉｄｉｌａｉｓ、Ｈｉ【ｈ ｇＳｐｅｅｄ Ｐｏｌｉｃｙ－ｂａｓｅｄ Ｐａｃｋｅｔ Ｆｏｒｗａｒ・
