Abstract: On the DBSCAN algorithm, a fast clustering algorithm based on quad-tree was proposed. It chose the points in the cirque-shaped neighborhood of a core point as seeds to expand the cluster, which decreased the execution frequency of region query and reduced the I/O cost. It used a fast-created quad-tree to execute region query, which not only improved the query efficiency, but also shortened the time of constructing a spatial index. Experiment results show that the new algorithm is effective.

Key words: clustering, DBSCAN, quad-tree

摘要： 以DBSCAN算法为基础,提出一种基于四叉树的快速聚类算法。新算法选择处于核心点的中空球形邻域中的点作为种子点来扩展类,大大减少区域查询的次数,降低I/O开销;使用快速生成的四叉树进行区域查询,在提高查询效率的同时,有效缩短构造空间索引的时间。文中对二维模拟数据和真实数据进行测试,结果表明新算法是有效的。

关键词:  , 聚类, DBSCAN, 四叉树