蚁群聚类算法

什么是聚类

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

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

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

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

蚁群聚类算法的由来

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

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

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

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

算法基本原理

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

算法存在的问题

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