杨亚军，张坤龙，杨晓科

(天津大学计算机科学与技术学院，天津 300072)

1 概述

聚类是一种十分重要的数据挖掘方法。它的目标是将数据对象进行分组，使得组内对象之间的相似性比组间对象之间的相似性大。聚类具有广泛的用途，它既可以用于理解客观世界，同时也可以作为其他数据挖掘方法的预处理，例如可以用于孤立点检测等［1］。许多学者对聚类进行了研究，他们提出了大量聚类算法，包括分层聚类、划分聚类、基于密度的聚类、基于格的聚类、基于模型的方法和一些比较新的方法，例如核聚类、谱聚类、蚁群聚类等。其中基于密度的聚类比较优秀，它可以聚类任意形状和大小的簇。

DBSCAN (Density Based Spatial Clustering of Applications with Noise)［2］是基于密度聚类的基础。它认为簇是由稀疏部分隔开的稠密区域，因此可以通过扩展密度大的点即核点来发现簇。DBSCAN 能够聚类任意形状和大小的簇，并且不受孤立点的影响。但是当数据集的各个簇的密度不同，并且簇之间没有被稀疏部分隔开时DBSCAN 就会遇到困难，无法产生正确的聚类结果。许多算法针对变化密度进行 改 进，如SNN(Shared Nearest Neighbor)［3］和VDBSCAN(Varied Density Based Spatial Clustering of Application with Noise)［4］等，它们虽然可以发现不同密度的簇，但在某些情况下无法产生正确的结果，并且选择合适的参数是十分困难的。

针对参数不易选择和无法处理变化密度的问题，本文对DBSCAN 算法进行了改进，并提出了一种自适应的基于变化密度的空间聚类方法(SAVDBSCAN)。算法以点到其第k 个最邻近邻居的距离作为密度，若一个点的密度与其k 个最邻近邻居中的每个点的密度相似，则将该点作为核点进行扩展。……