一种基于网格查询的改进DBSCAN算法

冯 玲，刘克剑*，唐福喜, 孟庆瑞

(1.西华大学计算机与软件工程学院，四川 成都 610039;2.西藏飞跃智能科技有限公司，西藏 拉萨 850000)



·计算机软件理论、技术与应用·

一种基于网格查询的改进DBSCAN算法

冯 玲1，刘克剑1*，唐福喜1, 孟庆瑞2

(1.西华大学计算机与软件工程学院，四川 成都 610039;2.西藏飞跃智能科技有限公司，西藏 拉萨 850000)

针对DBSCAN算法聚类时时间复杂度较高、当边界点同时属于多个类时其聚类准确率较低的问题，在网格查询思想和OPTICS算法的基础上，提出一种改进的DBSCAN算法(GO-DBSCAN算法)。进行聚类操作前，为降低聚类的时间复杂度，先基于网格查询的思想将数据集划分成不同的网格，在进行项目邻域查询时，只须遍历项目附近网格数据而不必遍历整个数据集；在进行项目聚类时，主要考虑该项目与其附近核心项目的最小可达距离，因此，将OPTICS算法中的最小可达距离引入到DBSCAN算法中，以提高算法对边界点处理的准确度。仿真实验结果表明，GO-DBSCAN在边界点处理的准确率和运行效率方面较DBSCAN都有所提高。

聚类算法；DBSCAN算法；OPTICS算法；网格聚类；边界点

传统的聚类算法[1-12]分5类：基于划分的聚类、基于层次的聚类、基于网格的聚类、基于模型的聚类、基于密度的聚类。基于密度的聚类的代表算法是DBSCAN[7]、OPTICS[10]等。DBSCAN算法是一种使用范围最广的基于密度的聚类算法。与传统方法相比，DBSCAN算法的优势是可以发现任何形状的数据集，能够有效地处理噪声点，不需要设定聚类后的簇个数[7]；然而，DBSCAN是直接对数据集进行处理，数据集越大，数据预处理的消耗时间过长。该算法时间复杂度为O(n2)，在数据集较大的情况下，其效率会受到明显的影响[8]。该算法对参数敏感性太强，初始参数的设置直接影响算法的质量和效果[9]。如果某一边界点同时属于多个类，也会影响该算法的质量和效果[13]。

在DBSCAN算法的时间复杂度方面，研究者提出基于网格思想的改进。刘淑芬等将数据空间进行网格划分，在数据对象ε-邻域中只遍历k-邻接网格集合所构成的区域，从而降低DBSCAN 的时间复杂度[14]；Huang等将DBSCAN与CLIQUE算法相结合，把DBSCAN中的核心对象转化为核心网格处理，以网格为最小处理对象[15]； Amineh Amini等[16]提出一种将基于密度的聚类算法和基于网格的聚类算法相结合的方法；周水庚等提出在进行类扩展的时候利用核心点邻域中部分邻域点进行扩展，提出一种基于数据取样的DBSCAN算法[7]和一种基于数据分区的DBSCAN算法[8]。

本文对DBSCAN算法的2点不足进行改进： 1)为解决边界点同时属于2个及2个以上类会影响DBSCAN算法质量和效果的问题，将OPTICS算法中最小可达距离引入到DBSCAN算法中；2)为解决DBSCAN算法效率问题，将基于网格查询的思想应用于DBSCAN算法[15]，在每次迭代的时候不用遍历所有数据点，只须遍历邻近网格中的数据点。本文将这2种思想相结合提出一种基于网格的改进DBSCAN算法。由于改进算法参考了OPTICS算法及基于网格(Grid)查询思想，所以改进算法叫GO-DBSCAN。

1 DBSCAN算法和OPTICS算法

DBSCAN是一种典型的基于密度的聚类算法，利用密度的连通性可以发现任何形状的簇[7]。OPTICS是DBSCAN算法的一种改进。这2种算法不仅能根据密度发现任何形状的类，而且能有效地处理噪声点。

1.1 基本概念

定义1 某一对象在ε为半径的邻域至少包含minpts个对象，则该对象称为核心对象。

定义2 某一对象的邻域包含的对象数少于minpts[8]，则该对象称为边界点。

定义3 某一对象的邻域包含的对象数为0，则该对象称为噪声点。

定义4 若对象p是核心对象，对象q在p的邻域内，则对象q与p直接密度可达。

定义5 存在一个数据链p1,p2,…，pn,其中p1=p,pn=q,若对象pi与对象pi+1是直接密度可达，则对象p与对象q是密度可达，如图1所示。

图1 p与q密度可达

定义6 若数据集中存在一对象o，使得对象p与对象q对对象o是密度可达的，则对象p和对象q是密度相连，如图2所示。

图2 p与q密度相连

定义7 使某对象成为核心对象的最小邻域半径ε'称为核心距离，若p不是核心对象即不存在核心距离之说。

定义8 对象q到核心对象p的可达距离是指对象q到对象p的欧几里得距离，若p不是核心对象，则不存在q到p的可达距离的定义。

1.2 DBSCAN算法思想

遍历数据集，得到任意一个核心对象p，将p的ε-邻域中的没被处理的对象归属到与p同一类，然后把p的ε-邻域中的对象作为即将遍历的对象(种子对象)，再对种子对象进行同对象p操作，直到种子对象遍历完成，得到一个完整的类。重复以上操作，发现其他类。当所有数据点遍历完成后，不属于任何类的数据对象即为噪声点[17]。

1.3 OPTICS算法思想

遍历数据集，得到任意一个核心对象p，计算p的核心距离和p的ε邻域中的对象到p的可达距离，然后把p放入结果队列，p的ε-邻域中的对象放入有序队列中，并通过可达距离排序，把有序队列中可达距离最小的对象取出，重复对象p的操作，直到可达队列中的对象操作完成，都放入结果队列中。重复以上全部操作，当所有数据对象操作完成后，得到一个以可达距离排序的结果序列。

OPTICS算法虽有ε和minpts 2个参数，但是OPTICS对参数的敏感度较DBSCAN算法已大大减小。OPTICS算法聚类得到的有序序列通过处理可以得到DBSCAN算法在任何参数下的聚类结果。

2 GO-DBSCAN算法

本文针对DBSCAN算法的时间复杂度较高和边界点同时属于多个类时聚类准确率较低的问题，提出一种改进算法(GO-DBSCAN)。GO-DBSCAN实现思想主要分2步：1)在进行聚类操作之前，基于网格查询思想对数据集进行划分，将数据集划分成不同的网格；2)用改进的聚类算法对划分后的数据集进行聚类。

2.1 GO-DBSCAN对数据集进行网格划分

本文提出的GO-DBSCAN结合网格查询思想，在进行聚类之前将数据集划分成不同的网格单元，在计算对象ε-邻域时就无须遍历整个数据集，只须遍历其邻近网格即可，这样大大提高算法的运行效率。

本文对网格单元的定义为：选取网格单元的长度为算法的邻域半径ε的2倍，即2ε，将数据在每个维度上以长度为2ε进行相同的划分[18]，从而将整个数据空间划分成不同的网格；网格单元表示为(d1,d2,…，dn),其中n为数据维度，di表示网格在不同维度上的序号，1≤i≤n。

数据对象p所属网格定义为：(x1,x2,…,xn)表示n维数据对象p每个维度上的坐标；p第i维对应网格序号di应满足xi/2ε≤di≤(xi+2ε)/2ε且di为整数。

设定网格单元后，在计算对象ε-邻域时，在每个维度上最多遍历9个网格单元，以二维数据为例，数据对象p(x,y)所属网格为(d1,d2),则其在计算ε-邻域所须遍历的范围如图3所示。

(d1-1，d2+1)(d1，d2+1)(d1+1，d2+1)(d1-1，d2)(d1，d2)•(x，y)(d1+1，d2)(d1-1，d2-1)(d1，d2-1)(d1+1，d2-1)d1d1+1d1-1

图3 二维空间的邻域网格

2.2 GO-DBSCAN对数据集进行聚类

DBSCAN算法在运行过程中每个数据对象只会被处理一次，运行完后，每个数据对象的类标签属性被确定，而且类标签是唯一的、不能更改的，这样同时属于2个类的边界点在聚类过程中出现错误也是无法更改的。GO-DBSCAN算法把OPTICS算法中的关键因素——最小可达距离(MAD)，融入其中，利用每个数据点的MAD来确定该数据点属于哪类。在这个过程中，不仅每个数据点被处理一次，而且在ε-邻域核心数据点改变的情况下数据点的MAD会不断更新。类标签随着MAD的改变而改变，就是说数据点的类标签始终跟离该数据点最近的核心对象的类标签一样。在GO-DBSCAN中，这样的改进会更精确地处理同时属于多个类的边界点，也在一定程度上减小了算法对初始参数的依赖。

当聚类数据集每个类之间分布较为稠密，而且边界点也比较多时，边界点同时属于多个类的情况很常见，如图4所示的数据集，其中，绿色表示核心点，黑色表示边界点，红色表示噪声点。DBSCAN处理时容易出现误差，然而，GO-DBSCAN可以很好地处理这样的数据集。GO-DBSCAN伪代码实现如图5所示。

图4 每个类分布较为稠密的聚类

为比较边界点的准确度，本文提出边界点聚类准确率(rate)的概念。

rate=correct_num/all_num。

(1)

式中：correct_num表示边界点聚类正确点数；all_num表示所有边界点的个数。

本文判断边界点聚类正确与否是根据对象与确定对象所属簇的核心点的可达距离(acceptable-distance ，AD)来确定。若2种聚类方法中，一些边界点的聚类结果不同，则比较这些边界点在不同方法中的AD，AD较小的类则为聚类正确，反之则聚类错误。

距离采用欧式距离，其计算公式为

(2)

式中：n表示数据对象维数；x1i表示第1个点第i维坐标；x2i表示第2个点第i维坐标。

输入：D：样本数据集ε：邻域半径Minpts：邻域密度阈值输出：聚类完成的数据集方法：对样本数据集进行网格划分，并标记数据对象所属网格编号将所有对象标记为unvisitedfor数据集中每一个对象p将p标记为visitedifp的ε邻域E中对象数>=Minpts新建一个簇C，将p添加到C；forE中的每个对象qifq是unvisited标记q为visited；令MAD为q的最小可达距离；令q的MAD等于q到p的欧式距离；将q添加到C；ifq的ε邻域中对象数>=Minpts将其邻域中所有对象添加到E；endifelse令d为q到p的欧式距离ifdistance=Minpts将其邻域中所有对象添加到E；并将其邻域中的所有对象从原属类中删除；endifendifendifend forendifendfor

图5 GO-DBSCAN伪代码

3 实验与结果

本文参照T. N. Tran等[13]对DBSCAN算法在MATLAB上的实现思路，分析GO-DBSCAN算法，把它与DBSCAN算法的聚类质量进行比较，并将GO-DBSCAN、DBSCAN和OPTICS算法的运行时间进行比较。其中GO-DBSCAN对数据进行划分网格预处理所需时间不算在运行时间内。

首先对聚类质量进行比较。表1是DBSCAN和GO-DBSCAN算法对图4的模拟数据库进行聚类的结果，实验参数minpts统一为5。从表1看出：DBSCAN在处理边界点时会存在误差；当初始参数设置较大时，GO-DBSCAN可以减小DBSCAN对初始参数的依赖。

表1 DBSCAN算法与GO-DBSCAN算法聚类质量比较

实验结果表明：DBSCAN算法对模拟数据库进行聚类的最佳参数ε=6；当ε发生变化时，DBSCAN算法的聚类结果受到明显的影响，GO-DBSCAN算法的聚类结果受到的影响较小。图6和图7分别示出DBSCAN算法和GO-DBSCAN算法在ε=7时得到的聚类结果。可以看出，当ε设置较大时，DBSCAN算法的聚类结果受到参数变化的影响明显，比GO-DBSCAN算法受到的影响大，这说明GO-DBSCAN算法在一定程度上减小了DBSCAN算法对参数的敏感度。

图6 DBSCAN在ε=7的聚类结果

图7 GO-DBSCAN在ε=7的聚类结果

图8示出GO-DBSCAN与DBSCAN和OPTICS的运行时间的比较结果。由于主机内存问题，本测试最大数据量为1万。可以看出，随着数据量逐渐增大，GO-DBSCAN的时间耗费明显比DBSCAN小。

图8 3种算法的运行时间对比

4 结束语

DBSCAN算法是传统的基于密度的聚类算法中最常用的一种。本文主要就DBSCAN算法的时间复杂高，对边界点同时属于多个类从而使聚类质量低的问题进行分析，提出一种改进算法(GO-DBSCAN算法)。GO-DBSCAN算法首先对数据集进行网格划分，以提高算法的运行效率，接着在对数据集进行聚类时，采用最小可达距离，有效地解决了边界点聚类准确率不高的问题，同时在一定程度上减小了初始参数对聚类质量的影响。实验结果表明，GO-DBSCAN算法对类之间分布稠密的数据集的聚类准确率比DBSCAN算法高，运行效率也比DBSCAN算法高。

[1]孙吉贵,刘杰,赵连宇.聚类算法研究[J].Journal of Software,2008,19(1):48.

[2]周涛,陆惠玲.数据挖掘中聚类算法研究进展[J].计算机工程与应用,2012,48(12):100.

[3]王千,王成，冯振元，等.K-means聚类算法研究综述[J].电子设计工程，201,20(7):21.

[4]陈旭玲,楼佩煌.改进层次聚类算法在文献分析中应用[J].数值计算与计算机应用,2009,30(4):277.

[5]WANG Wei， YANG Jiong, MUNTZ Richard. STING:A Statistical Information Grid Approach to Spatial Data Mining[C]//Athens Proceedings of the 23rd Conference on CLDB.[S.l.]:IEEE,1997:186-195.

[6]宋浩远.基于模型的聚类方法研究[J].重庆科技学院学报(自然科学版),2008,10(3):71.

[7]周水庚,范晔,周傲英.基于数据取样的DBSCAN算法[J].小型微型计算机系统,2000,21(12):1270.

[8]周水庚,周傲英,曹英.基于数据分区的DBSCAN算法[J].计算机研究与发展,2000,37(10):1153.

[9]于亚飞,周爱武.一种改进的DBSCAN密度算法[J].计算机研究与发展,2011,21(2):30.

[10]曾依灵,许洪波,白硕.改进的OPTICS算法及其在文本聚类中的应用[J].中文信息报,2008,22(1):51.

[11]杜红乐,张燕.密度不均衡数据分类算法[J].西华大学学报(自然科学版)，2015，34(5)：16.

[12]金珠，马小平.基于蚁群聚类算法的SVM监督式训练方法[J].西华大学学报(自然科学版),2011,30(1):56.

[13]Tran T N, Drab K,Daszykowski M. Revised DBSCAN Algorithm to Cluster Data with Dense Adjacent Clusters[J]. Chemometrics & Intelligent Laboratory Systems, 2013, 120(2):92.

[14]刘淑芬,孟冬雪,王晓燕.基于网格单元的DBSCAN算法[J].吉林大学学报(工学版),2014,44(4):1135.

[15]HUANGDarong,WANG Peng.Grid-based DBSCAN Algorithm with Referential Parameters[J].Pthysics Procedia,2012：24：1166.

[16]Amineh Amini, The Ying Wah, Mahmoud Reza Saybani, et al. A Study of Density-grid Based Clustering Algorithms on Data Streams[C]// Eighth International Conference on Fuzzy Systems and Knowledge Discovery. [S.l.]:IEEE, 2011:1652-1656.

[17]SELIM Mimariglu, EMIN Aksehirli.Improving DBSCAN’s Execution Time by Using a Pruning Technique on Bit Vector[J].Pattern Recognition Letters,2011,32:1572.

[18]陈燕俐,洪龙,金达文,等.一种简单有效的基于密度的聚类分析[J].南京邮电学院学报,2005,25(4):24.

(编校：饶莉)

Improvements of DBSCAN Algorithm Based on Grid

FENG Ling1, LIU Kejian1*, TANG Fuxi1，MENG Qingrui2

(1.School of Computer and Software Engineering,Xihua University, Chengdu 610039 China;2.TibetFeiyueIntelligentTechnologyCO.,Ltd.,Lasa850000China)

In view of the low accuracy of boundary point clustered and the excessively high time complexity of DBSCAN algorithm, a DBSCAN algorithm is proposed based on GO-DBSCAN algorithm and OPTICS algorithm. The algorithm introduced the minimum reachable distance of OPTICS algorithm into the DBSCAN algorithm. Generally, the minimum distance between object and the near core object is a mainly considered factor for the clustering based on DBSCAN algorithm. Therefore, the introduce improves the clustering accuracy. The idea of grid query is proposed to reduce the size of traversal data of objects and this results in the decrease of DBSCAN algorithm’s time complexity. Before clustering, data set is divided into different grid based on grid query rules to reduce clustering time complexity. When project neighborhood is to be queried, it is necessary to traverse only the project near grid data other than the entire data set. The theoretical analysis and simulation results show that GO-DBSCAN can effectively improve the accuracy of boundary point clustered and reduce the time complexity.

clustering algorithm; DBSCAN algorithm；OPTICS algorithm; grid clustering; boundary point

2016-03-31

西华大学重点科研基金项目(Z1320607)；国家科技支撑计划项目西藏自然科学博物馆数字馆关键技术研究及集成示范(2011BAH26B01)；国家自然科学基金(61271413、61472329、61532009)；数字空间安全保障四川省高校重点实验室开放基金课题资助(szjj2015-055)；四川省教育厅重点项目资助(16ZA0165)；西华大学研究生创新基金(YCJJ2015187；YCJJ2016169)；西华大学校重点项目(Z1222625)。

TP181；TP301.6

A

1673-159X(2016)05-0025-5

10.3969/j.issn.1673-159X.2016.05.005

*通信作者：刘克剑(1974—)，男，副教授，硕士，CCF会员，主要研究方向为计算机网络和无线网络技术、智能信息处理技术、高性能计算技术。E-mail:liukejian@gmail.com