FDBSCAN:一种快速 DBSCAN算法(英文)

FDBSCAN: A Fast DBSCAN Algorithm

聚类分析是一门重要的技术 ,在数据挖掘、统计数据分析、模式匹配和图象处理等领域具有广泛的应用前景 .目前 ,人们已经提出了许多聚类算法 .其中 ,DBSCAN是一种性能优越的基于密度的空间聚类算法 .利用基于密度的聚类概念 ,用户只需输入一个参数 ,DBSCAN算法就能够发现任意形状的类 ,并可以有效地处理噪声 .文章提出了一种加快 DBSCAN算法的方法 .新算法以核心对象邻域中所有对象的代表对象为种子对象来扩展类 ,从而减少区域查询次数 ,降低 I/ O开销 .实验结果表明 ,FDBSCAN能够有效地对大规模数据库进行聚类 ,速度上数倍于 DBSCAN.

Clustering is an important application area for many fields including data mining, statistical data analysis, pattern recognition, image processing, and other business applications. Up to now, many algorithms for clustering have been developed. Contributed from the database research community, DBSCAN algorithm is an outstanding representative of clustering algorithms for its good performance in clustering spatial data. Relying on a density based notion of clusters, DBSCAN is designed to discover clusters of arbitrary shape. It requires only one input parameter and supports the user in determining an appropriate value of it. In this paper, a fast DBSCAN algorithm (FDBSCAN) is developed which considerably speeds up the original DBSCAN algorithm. Unlike DBSCAN, FDBSCAN uses only a small number of representative points in a core point's neighborhood as seeds to expand the cluster such that the execution frequency of region query and consequently the I/O cost are reduced. Experimental results show that FDBSCAN is effective and efficient in clustering large scale databases, and it is faster than the original DBSCAN algorithm by several times.