张辉 韩发 鹿方凯

摘 要：针对空间局部密度变化和需要用户输入参数的空间聚类问题，提出自适应局部密度变化的空间聚类方法。借助 Delaunay三角网构建空间邻近关系的优势，首先给出点密度的度量标准，即与点直接相连的边长度均值。将核点定义为一阶邻域中至少存在一个密度相似点，在此基础上应用广度优先搜索算法对一阶邻域进行搜索，对密度相似的核点进行扩展，将密度远小于核点密度的点作为簇的边界点。在判断点密度是否相似时，根据已加入核点的平均密度和密度变化率自动调整参数值。通过模拟实验，对比DBSCAN算法实验结果，对提出的算法进行验证。实验结果表明，该算法不仅能够自动适应局部密度变化和识别出离散点，而且能适应不同形态的空间簇。

关键词：空间聚类;自适应;局部密度不同;点密度;Delaunay三角网

DOI：10. 11907/rjdk. 182134

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）001-0095-04

Abstract：In order to solve the problems of spatial clustering with local density changes and requiring parameters given by the user， this paper proposes a spatial clustering method with self-adaptive local density variation. In this paper， the Delaunay triangulation is used to construct the spatial proximity relationship. The metric of the point density and the mean value of the first-order neighbors side-length are firstly given. The core point is defined as that there is at least one point with similar density in the first-order neighborhood. On this basis， the breadth-first search algorithm is used to perform search on the first-order neighborhood， and the core points with similar density are extended， and points far less than the density of the core is considered as the boundary points of the cluster. When judging whether the density of points is similar， the parameter values are automatically adjusted according to the average density and the rate of the density change of the core points that have been added. Through simulation experiments and comparison of experimental results of DBSCAN algorithm， the proposed algorithm is verified. Experimental results show that the algorithm can automatically adapt to local density changes and different forms of spatial clusters and identify discrete points.

0 引言

随着数据获取技术快速发展，空间数据量变得庞大，并且成为探索空间领域知识的重要依据，因此迫切需要利用空间数据挖掘技术发现空间数据中隐含的有用知识。空间聚类作为空间数据挖掘的一个重要分支，是将数据对象进行分组，使得每一个组内对象之间相似性最小，且组间对象之间的相似性最大[1]。

基于划分的聚类方法和基于層次的聚类方法，是较早提出的较为有效的基本聚类方法，旨在发现球状簇，却很难发现任意形状的簇[2-4]。为了发现任意形状的簇，基于密度的聚类方法能够过滤低密度区域，发现稠密样本点组成的类簇，并能识别噪声数据[5-8];基于格网的聚类方法[9]，在某种程度上类似于基于密度的方法，采用基于格网的数据结构对数据集进行聚类。……