一种改进的DBSCAN算法

唐亮

摘要：DBSCAN算法是基于密度的聚类算法，传统的DBSCAN聚类算法在聚类过程中需要遍历核心点邻域里的点，这就大大增加了DBSCAN算法的运行时间。针对DBSCAN算法时间性能低效的问题，提出一种新的改进的DBSCAN算法。该算法在不丢失对象的基础上，通过改变遍历核心对象邻域点选取方式来扩展类，从减少每次区域查询次数及查询时间，提高了算法的时间性能。实验结果表明，改进的DBSCAN算法是正确和高效的。

关键词：聚类；DBSCAN算法；邻域；核心对象

中图分类号：TP301 文献标识码： A 文章编号：1009-3044（2017）06-0132-02

1 概述

聚类分析[1]是数据挖掘中的重要组成部分。所谓聚类分析， 就是将一组数据集分成多个簇，在同一个簇中的数据相似度较高，而不同簇中的数据相似度较低，人们能够通过识别不同数据密度分布的区域发现数据属性之间的相互关系。在数据挖掘中，人们通过聚类对簇的特点进行分析，获取数据分布的信息。此外，人们还将聚类分析作为其他算法数据处理的步骤。到现在为止，已经有许多聚类算法[2]被提出来了，比如基于划分的方法KMeans[3]算法、基于层次的聚类算法CURE算法 、基于密度的DBSCAN[4]算法、基于网格的CLIQUE等算法。其中DBSCAN算法可以在数据集中发现任意形状的聚类，但由于其遍历节点的次数较多，其时间性能较低。本文提出了一个DBSCAN算法的改进方法，该方法使得DBSCAN改進算法在时间性能上有较大提高。

2 基于密度的DBSCAN算法

2.1 基本概念

DBSCAN 算法是使用基于距离的方法对数据对象进行聚类，聚类结果是球状的簇。其思想是：通过检测数据集中数据点的Eps邻域内的数据点的数目来搜索簇，如果数据点p的邻域内包含的数据点的数目多于MinPts，则创建一个以p为核心对象的簇，然后，聚集直接密度可达的对象，如果不同簇之间密度可达，则将簇合并。一直到没有新的点添加到簇中结束。下面给出DBSCAN聚类算法的一些定义[5] 。

定义1：邻域

对于对象p以半径为Eps的范围称为对象p的Eps邻域，我们用表示点p的Eps半径内的点的集合，即：

定义2：核心对象

对于给定对象p，如果p点的邻域内包含的数据点数目不小于MinPts，则称点p为核心对象。

定义3：边界点

对于给定对象p，如果对象p点不是核心点，但是对象p在核心对象q的邻域内，则称p为边界点。

定义4：噪音点

对于给定对象p，如果对象既不是核心点，也不是边界点，则称对象p为噪音点。

定义5：直接密度可达

给定一个对象集合D，如果p在q的Eps邻域内，而q是一个核心对象，则称对象p 从对象q出发时是直接密度可达的。

定义6：密度可达

如果存在一组对象，对，是从直接密度可达的，则对象p是从对象q密度可达的。

定义7：密度相连

如果存在对象，使对象p和q都是从O密度可达的，那么对象p到q是密度相连的。

2.2 DBSCAN 算法

DBSCAN 算法是一个基于密度的聚类算法，通过迭代遍历查找所有和核心点直接密度可达的数据点， 来找到所有簇中包含的密度可达的数据对象[6]，具体的过程如下所示：

1）对于数据集D中还没有被检查过的数据点p，如果数据点p未被处理，则检查该数据点Eps邻域内的数据点的数目，若数据点数不小于MinPts，则新建一个簇C，将该数据点Eps 邻域内其他所有的数据点添加到簇C中 。

2）对于簇C中任意一个还没有被处理的数据点q，检查它的Eps邻域，若其邻域里的数据点数不小于MinPts，则将该数据点的邻域中还没有属于任何一个簇的数据点加入簇C中 。

3）重复步骤2），直到没有新的对象加入当前簇C 。

4）重复步骤1）?3），直到所有的数据点被处理。

DBSCAN算法在聚类过程中，可以发现数据集中任意形状的簇，但是DBSCAN算法也有其局限性，就是需要对每个数据点对象都要进行邻域查询，时间性能低。

3 DBSCAN改进算法

本文对DBSCAN算法的改进思想是：就是在核心对象进行邻域查询时无需遍历邻域内的所有节点，选择当前邻域内距离核心对象较远但未被标记的点，以减小邻域查询次数和查询时间。算法的聚类过程如下：

1）在数据集上随机选取一个节点p 开始邻域查询，如果数据点p 是核心节点，则将它邻域内的所有数据点点用C进行类别标记。

2）选择里核心点p较远的点q进行邻域查询，如果它是核心点，则将q点邻域里的不在簇C里的点加入到簇C里，如果不是核心点，则继续进行遍历，知道将p邻域里较远的数据点全部遍历完为止。

3）重复以上过程，直到所有节点都被标记。

4 实验

本文所涉及的算法均是用matlab语言编写的，并在win7系统环境下运行。

4.1 改进算法的对比实验

为了验证DBSCAN改进算法正确性，采用了三个二维数据集进行了实验验证，如图1所示：

其中，data1自然聚成6类，data2自然聚成5类，data3自然聚成9类。

本文采用相同的参数验证DBSCAN算法和改进算法，所得到的聚类结果完全相同，如下图2所示：

通过对比实验，我们发现，DBSCAN算法和其改进算法在data1、data2和data3上的运行结果完全一样，由此可以看出DBSCAN改进算法与DBSCAN算法的相同的聚类功效，改进算法的正确性得以保证。

4.2 执行时间的对比实验

测试改进算法的时间对比实验仍然采用上面的3个数据集，期执行时间如表1所示：

从表中可以看出改进算法的执行时间总是比DBSCAN算法执行时间少，由此可见，改进算法与DBSCAN算法比，其时间性能高效。

5 结束语

虽然改进算法和DBSCAN算法具有相同的时间复杂度，但是DBSCAN需要遍历每一个核心节点并计算其邻域，而改进算法只遍历距离核心点较远的点，降低了计算量，从而减少了时间，提高了时间性能。

参考文献：

[1] HAN Jia Wei，KAMBER M.数据挖掘概念与技术[M].范明，孟晓峰，译.北京：机械工业出版社，2001.

[2] 杨小兵.聚类分析中若干关键技术的研究[D].杭州：浙江大学，2005.

[3] KAUFANL， RPUSSEEUW P J.Finding groups in data：Anintroduction to cluster analysis[M] .New York：JohnWiley& Sons，1990.

[4] 陈刚，刘秉权，吴岩.一种基于高斯分布的自适应DBSCAN 算法[J].微电子学与计算机，2013（3）：27-30，34.

[5] 周水庚，周傲英，曹晶，等.一种基于密度的快速聚类算法[J].计算机研究与发展，2000，37（11）：1287-1292.

[6] NANNI M，PEDRESCHI D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems，2006，27（3）：267-289.