内容发布更新时间 : 2024/5/31 2:02:49星期一 下面是文章的全部内容请认真阅读。

－5009－ 0引言

俗话说“物以类聚，人以群分”，人们在不知不觉中进行着 聚类活动，它是人们认识和探索事物之间内在联系的有效手 段。聚类在数据挖掘中有着重要的地位，它既可以用作独立 的数据挖掘工具，来发现数据库中数据分布的一些深入信息， 也可以作为其它数据挖掘算法的预处理步骤。因此，聚类算 法的研究具有很重要的现实意义。

蚁群算法不依赖于具体问题，具有全局优化能力，因此受 到了广大学者的注意。此后蚁群算法不断被改进并应用于不 同领域。在聚类分析方面，Deneubourg等人受蚂蚁堆积尸体 和分类它们的幼体启发，最早将蚁群算法用于聚类分析，从此 开始了蚁群聚类算法的研究。

本文详细地讨论了现有的蚁群聚类算法的基本原理与性

能，在归纳总结的基础上提出需要完善的地方，以推动蚁群聚 类算法的进一步研究及在更广阔的领域内得到应用。 1聚类概念及数学模型

聚类就是把一组个体按照相似性归为若干类或簇，使得 属于同一类或簇的个体之间的差别尽可能的小，而不同类或 簇的个体间的差别尽可能大。聚类质量是用对象的相异度来 评估，而不同类型变量的相异度的计算方法是不同的，常用的 度量方法是区间标度变量中的欧几里得距离。 聚类的数学描述：设样本集={,=1,2,?,}，其中为 维模式向量，其聚类问题就是找到一个划分={ 1 , 2 ,…,

}，满足= =1

，≠，=，,=1,2,?,，≠，且使 得总的类内离散度和= =1

,最小，其中为的

聚类中心，=1,2,?,；,为样本到其聚类中心的距 离，即,=‖‖。聚类目标函数为各样本到对应 聚类中心的距离总和，聚类中心=1 ，||为的样 本数目。

2蚁群聚类算法分类及应用

由于现实的蚁群运动过程接近于实际的聚类问题，所以 近年来涌现出大量的蚁群聚类算法。这些算法不仅思想、原 理不同，而且算法的特性也根据解决问题的不同而不同，如初 始参数及待聚类数据的要求、聚类形状等。

根据改进方式的不同，蚁群聚类算法可分3类：①基于蚂 收稿日期：2007-10-17 E-mail：05lihua@sohu.com

作者简介：裴振奎(1962－)，男，山东东营人，博士研究生，副教授，硕士生导师，研究方向为机器学习与计算智能；李华(1977－)，女，山

东滨州人，硕士研究生，研究方向为数据挖掘、自然计算；宋建伟(1982－)，女，河北廊坊人，硕士研究生，研究方向为网络安全、计算智能；

韩锦峰(1981－)，女，山西大同人，硕士研究生，研究方向为计算智能、数据库系统理论。 蚁群聚类算法研究及应用

裴振奎，李华，宋建伟，韩锦峰

(中国石油大学(华东)计算机与通信工程学院，山东东营257061)

摘要：聚类作为数据挖掘技术的重要组成部分，在很多领域有着广泛应用。蚁群算法是近几年研究的一种新算法，该算法

采用分布式并行计算和正反馈机制，具有易于与其它方法相结合的优点。根据蚁群算法在聚类中的应用及改进型式的不同，

文章主要介绍了几种基本的流行的蚁群聚类算法，分析了它们的不同之处，并对蚁群聚类算法今后的研究方向作了展望。

关键词：聚类;蚁群算法;信息素;正反馈机制;蚁群聚类算法

中图法分类号：TP301文献标识码：A文章编号：1000-7024(2008)19-5009-05 Investigation and application of ant colony clustering algorithms PEI Zhen-kui,LI Hua,SONG Jian-wei,HAN Jin-feng

(College of Computer and Communication Engineering,China University of Petroleum(East China),

Dongying 257061,China)

Abstract：Clustering is widely used in some fields as a part of important data mining.Ant colony algorithms are novel algorithms in re-

cently years.These methods have several virtues such as distributed parallel computing,positive feedback mechanism and combination

with certain heuristics.Some kinds of basic and popular ant colony clustering algorithms are introduced,the differences of them are

analyzed and the direction for study of ant colony algorithms based on application and improving modality in clustering.

Key words：clustering;ant colony algorithm;pheromone;positive feedback mechanism;ant colony clustering algorithm

计算机工程与设计2008年10月 Oct.2008

第29卷第19期

Vol.29 No.19 Computer Engineering and Design－5010－

蚁行为特征的聚类算法，如：蚂蚁觅食原理为基础的聚类、受 蚂蚁堆积尸体启发的聚类等。这类算法大多是根据具体情况 对系数、参数及公式等的改进。②多种群的蚁群聚类算法，这 类算法主要是将上述的单种群扩大为多种群，以完善聚类效 果、提高速度。③与其它方法结合，通过优势互补来改善聚类 效果、提高聚类质量、缩短聚类时间，如与K-Means算法结合 [1]

，

与遗传算法结合的算法等。

蚁群聚类算法应用很广，从Deneubourg发现蚂蚁能将分 散在蚁穴各处的蚂蚁尸体按一定规律垒堆起来，并依此提出 了基于蚂蚁的聚类基本模型开始。之后，Lumer和Faieta在此 基础上提出了用于聚类分析的LF算法 [2]

，并将其应用到数据 分析当中。Monmarché [1]

引入AntClass系统，交替使用蚁群聚类

和k均值算法修正误差，获到“高质量”的聚类。Ramos等人 [3] 、

Handl等人 [4]

将LF算法用于文本聚类。Kuntz和Snye则对每

对图像节点的非相似度值函数做了修改，将之用于图像的分 割，韩彦芳等人 [5]

从模糊角度出发结合蚁群特点提出了用于图 像分割的蚁群聚类算法。吴斌等人 [6]

将基于蚁群的聚类算法

用于客户关系管理中的客户行为分析以及Web文档聚类。翁 怀荣等人 [7]

引入随机扰动和感觉知觉特征以指导信息素的更

新，并将改进后的蚁群聚类算法用到企业人力资源管理中。总 之，随着蚁群聚类算法研究的深入，其应用领域也在不断扩大。 3算法分析

3.1基于蚂蚁行为特征的聚类算法 3.1.1基于蚂蚁觅食原理

蚂蚁觅食主要分搜索和搬运食物两步。蚂蚁移动时在所

经路径留下信息素，通过感知信息素的强弱进行非直接通信， 形成正反馈加强搜索。在该算法中，一般将数据视为具有不 同属性的蚂蚁，聚类中心即蚂蚁所要寻找的“食物源”，数据聚 类过程被看作是蚂蚁寻找食物源的过程。 基本思想 [8]

：假设待聚类对象为={|=( 1 , 2