一种基于蚁群算法的聚类组合方法

Clustering Combination Based on Ant Colony Algorithm

蚂蚁等群居类昆虫被看作能解决复杂问题的分布式系统,研究者从它们的协作性能以及自组织、信息素通信、任务划分等机理中获得灵感,已在组合优化、通信网络、机器人等许多应用领域找到解决问题的新方法。聚类作为一种无监督的学习,能根据数据间的相似程度自动地进行分类。基于蚁群算法的聚类方法已经在当前数据挖掘研究中得到应用。本文提出的基于蚁群算法的聚类组合新方法,模仿多蚁群的协作性能,将运动速度类型各异的多个蚁群,独立而并行地进行聚类分析,然后组合其聚类结果为超图,再用蚁群算法对超图进行2次划分。实验结果表明,该方法能自动决定聚类的数目,聚类组合方法能明显改善聚类质量。

Social insects such as ants can be viewed as distributed systems capable of solving complex problems. The collective behavior of ant colonies and the mechanisms of their self-organization, pheromone communication and task partitioning have inspired researchers to design new algorithms for solving problems in many application fields, e.g. combinatorial optimization, communication networks, robotics. As an unsupervised learning technique, clustering is a division of data into groups of similar objects. The ant-based clustering algorithm has currently applications in the data mining community. This paper presents a new ant-based clustering combination algorithm, which imitates the cooperative behavior of multi-ant colonies. Initially each ant colony takes different types of ant moving speeds to generate independent clustering results, and then these results are combined using a hypergraph. Finally an ant-based graph-partitioning algorithm is used to cluster the hypergraph again. Results on real data sets are given to show that the number of clusters can be adaptively determined and clusterings combination can improve the clustering performance.