李捷，陈雁彬

（重庆大学计算机学院，重庆 400044）

0 引言

在数据挖掘中，聚类算法占据重要地位，它是按照一定的规律和方法对事物进行区分和归类[1]，而聚类算法细分为基于层次的聚类方法、基于划分的聚类算法、基于密度的聚类算法与基于网格的聚类算法，基于密度的聚类算法是聚类中的一个重要的研究分支，相比于其他算法，基于密度的聚类算法可以在有噪声的数据中发现各种形状与各种大小的类别，DBSCAN[4]是该方法中最典型的代表算法之一，其核心思想是首先发现具有高密度的点，然后将相邻近的高密度点逐步的连接在一起，进而形成各种簇；由于DBSCAN算法使用的是全局的密度阈值MinPts，只能发现密度不少于MinPts的点组成的簇，无法发现不同密度的簇，为了解决这些问题，OPTICS[5]（Ordering Points to Identify the Clustering Structure）算法将邻域点按照密度大小进行排序，最后使用可视化的方法来发现不同密度的簇，然而该方法需要在可视化的图上查找“山谷”，进而发现簇，因此算法性能直接受到这些可视化方法的约束；SNN（shared Nearest Neighbor）算法采用一种基于KNN方式计算相似度的方法来改进DBSCAN，其核心思想是在空间中找出离其最近的k个点，两个点的相似程度使用这两个点的k邻域范围中共享的近邻数量来度量，然而SNN算法需要设定近邻个数k，且该算法的性能对k的取值很敏感。

基于以上分析，考虑到数据集中可能存在不同形状、不同密度的簇，本文提出一种使用自然邻居算法进行改进的DBSCAN算法，以后称作NN-DBSCAN算法，首先……