计算机科学与探索 ›› 2012, Vol. 6 ›› Issue (10): 903-911.DOI: 10.3778/j.issn.1673-9418.2012.10.005

• 学术研究 • 上一篇    下一篇

基于数据场的改进DBSCAN聚类算法

杨  静1,2+,高嘉伟1,2,梁吉业1,2,刘杨磊1,2   

  1. 1. 山西大学 计算智能与中文信息处理教育部重点实验室,太原 030006
    2. 山西大学 计算机与信息技术学院,太原 030006
  • 出版日期:2012-10-01 发布日期:2012-09-28

An Improved DBSCAN Clustering Algorithm Based on Data Field

YANG Jing1,2+, GAO Jiawei1,2, LIANG Jiye1,2, LIU Yanglei1,2   

  1. 1. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006, China
    2. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China
  • Online:2012-10-01 Published:2012-09-28

摘要: DBSCAN(density based spatial clustering of applications with noise)算法是一种典型的基于密度的聚类算法。该算法可以识别任意形状的类簇,但聚类结果依赖于参数Eps和MinPts的选择,而且对于一些密度差别较大的数据集,可能得不到具有正确类簇个数的聚类结果,也可能将部分数据错分为噪声。为此,利用数据场能较好描述数据分布,反映数据关系的优势,提出了一种基于数据场的改进DBSCAN聚类算法。该算法引入平均势差的概念,在聚类过程中动态地确定每个类的Eps和平均势差,从而能够在一些密度相差较大的数据集上得到较好的聚类结果。实验表明,所提算法的性能优于DBSCAN算法。

关键词: DBSCAN算法, 数据场, 聚类

Abstract: DBSCAN (density based spatial clustering of applications with noise) algorithm is a typical density-based clustering algorithm. The algorithm can discover the arbitrary-shaped clusters. However, the clustering results depend on the two parameters Eps and MinPts which are chosen by users. And for some datasets with large density differences, either the clustering results may have the incorrect cluster number, or the algorithm may label part of the data as noise. Using the advantages that data field can commendably describe the data distribution and reflect the data relationship, this paper proposes a new clustering algorithm called improved DBSCAN algorithm based on data field. The algorithm introduces the concept of average potential difference and dynamically determines Eps and average potential difference of each class during the clustering process. In this way, it can receive better clustering results for some clusters with large density differences. Experimental results indicate that the proposed algorithm performs better than DBSCAN algorithm.

Key words: DBSCAN algorithm, data field, clustering