蚁群聚类算法

什么是聚类

聚类分析是数据挖掘领域中的一个重要分支, 是人们认识和探索事物之间内在联系的有效手段, 它既可以用作独立的数据挖掘工具, 来发现数据库中数据分布的一些深入信息, 也可以作为其他数据挖掘算法的预处理步骤。

所谓聚类,就是忽略一些数据的细节,依据某些属性将数据划分为同构子组(称为类或簇),从而简化数据。聚类可以看作是一种提供简明数据摘要的数据建模技术,划分的目标是双重的:

  • 同一类中的数据项必须彼此相似;
  • 不同类中的数据项应该不同。

聚类在许多学科中得到应用,并在广泛的应用中发挥着重要作用,因此,聚类算法一直是研究热点。现在的聚类算法可以分为四大类 :分区、分层、基于密度和基于网格的聚类方法。

蚁群聚类算法的由来

基于蚁群的聚类算法是一种相对较新的聚类方法,其灵感来自于对蚁群中蚂蚁尸体的聚类和幼虫的分类活动。

Deneubourg等人曾提出一个基本模型,该模型允许蚂蚁根据周围相似物体的数量随机移动、拾取和贮存食物。该基本模型已成功应用于机器人领域。

后Lumer和Faieta将基本模型修改为LF算法,并将其推广到数值数据分析。该算法的基本原理很简单:将蚂蚁抽象为其环境中具有周期性边界条件的正方形网格,分散在环境中的数据由“蚂蚁”拾取、传输和删除。在“蚂蚁”的局部邻域内,数据的相似性和密度会影响拾取和丢弃操作,也就是说环境中的“蚂蚁”很可能拾取孤立的或被不相似的数据包围的数据,并倾向于将其贮存在相似的数据附近,以此在网格上对数据元素进行聚类和排序。

这样由蚁群行为启发而来的聚类算法作为一种新兴的仿生优化算法,相对于传统算法具有灵活性、鲁棒性、分散性、自组织性等优点,这些特点非常适合离散的现实环境,因此该类算法在数据挖掘、图分割、文本挖掘等领域应用广泛。

算法基本原理

首先,数据对象被随机投影到一个平面上。其次,每只“蚂蚁”随机选择一个对象,根据当前对象与局部区域内对象的相似程度,得到拾取或丢弃对象的概率,并以此进行拾取、移动和丢弃对象。最后,在平面上收集划分完成的类(簇)。

算法存在的问题

由于蚂蚁的移动是随机的,并且需要大量的时间寻找合适的位置拾取或丢弃物体,蚁群聚类算法的计算效率和精度会受此影响降低。