基于蚁群系统的聚类算法研究

山东大学学报(工学版) ›› 2010, Vol. 40 ›› Issue (3): 13-18.

基于蚁群系统的聚类算法研究

沙露^1,2, 鲍培明^1,2*, 李尼格^1,2

1. 南京师范大学计算机系, 江苏南京 210097; 2. 江苏省信息安全保密技术工程研究中心, 江苏南京 210097

收稿日期:2009-12-22 出版日期:2010-06-16 发布日期:2009-12-22
通讯作者: 鲍培明(1966-),女,江苏南京人,副教授,硕士生导师,主要研究方向为数据挖掘技术及其应用. E-mail:E-mail: baopeiming@163.com
作者简介:沙露(1985-),女,江苏泰州人,硕士研究生,主要研究方向为数据挖掘技术.E-mail: sl-njnu@163.com
基金资助:
国家自然科学基金资助项目(40871176)

The research of a clustering algorithm based on the ant colony system

SHA Lu^1,2, BAO Pei-ming^1,2*, LI Ni-ge^1,2

1. Department of Computer, Nanjing Normal University, Nanjing 210097, China;
2. Research Center of Information Security Technology, Jiangsu Province, Nanjing 210097, China

Received:2009-12-22 Online:2010-06-16 Published:2009-12-22

摘要/Abstract

摘要：

针对传统聚类算法在对复杂密集型数据集聚类时不能取得较好聚类结果的问题,利用进化聚类算法对复杂密集型数据集进行聚类,提出一种基于蚁群系统的聚类算法(clustering algorithm based on ant colony system,CAACS),利用蚂蚁在行进路径中释放信息素且追求浓信息素的原理来实现蚂蚁的随机搜索,并引入近邻函数值的概念来确定样本数据之间的相似性,通过蚂蚁在行走过程中不断建立样本数据之间的最相似连接来形成各个子连通图,各个子连通图中的样本数据构成一个类。实验采用随机产生的不规则数据集以及一系列合成的数据集将CAACS算法与DBSCAN算法(density-based spatial clustering of application with noise)及面向非规则非致密空间分布数据的蚁群聚类方法进行比较。实验结果表明CAACS算法对复杂密集型数据集能达到较好的聚类结果。

关键词: 聚类算法;蚁群系统, DBSCAN算法

Abstract:

For solving the problem that traditional clustering algorithms can not get good results on clustering of complex data sets, a clustering algorithm based on the ant colony system is presented. The ant’s random search is realized based on the principle that the ant leaves pheromone on its path and pursuit concentrated pheromone. The similarity among the data is determined based on the concept of neighboring function values. Ants establish connections between the most similar data in the process of walking, draw the various sub-connected graph, and the data in the same subconnected graph are given the same cluster number. Some experiments have been made to compare the results of the proposed CAACS algorithm with those of the DBSCAN algorithm. The experiments are based on randomly generated irregular data sets and a series of synthetic data sets. The experimental results show that the CAACS algorithm can achieve good results on complex data sets.

Key words: clustering algorithm, ant colony system, density-based spatial clustering of application with noise

沙露1,2, 鲍培明1,2*, 李尼格1,2. 基于蚁群系统的聚类算法研究[J]. 山东大学学报(工学版), 2010, 40(3): 13-18.

SHA Lu1,2, BAO Pei-ming1,2*, LI Ni-ge1,2. The research of a clustering algorithm based on the ant colony system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 13-18.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed