基于密度的DBSCAN算法.pdfVIP

基于密度的DBSCAN 算法 邢冬丽，赵美红，陈文成 辽宁工程技术大学工商管理学院，辽宁葫芦岛 (125105) E-mail：jevile@163.com 摘 要：本文主要探讨聚类算法DBSCAN ，以及DBSCAN 在二维空间上的实现。 关键词：数据挖掘，聚类算法，DBSCAN 1. 引言 [1] 聚类方法主要有分层聚类、划分聚类、密度聚类、网络聚类和模型聚类等 。绝大部分 划分方法都是基于对象之间的距离进行聚类，这样的方法只能发现球状的簇，而不能发现其 他形状的簇。密度聚类则只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继 续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个 数目的点[2] 。这样密度聚类方法就可用于过滤“ 噪声”孤立点数据，发现任意形状的簇。 DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一个典型的基于密度 聚类的方法，它根据一个密度阈值来控制簇的增长。 2. DBSCAN算法的理论分析 基于密度的聚类算法DBSCAN 在处理空间数据时具有快速、有效处理噪声点和发现任 意形状的聚类等优点。 2.1 DBSCAN算法的几个基本概念 定义2.1 （密度）空间中任意一点的密度是以该点为圆心、以Eps 为半径的圆区域内包 含的点数目[1] 。 定义2.2 （邻域：Neighborhood ）空间中任意一点的邻域是以该点为圆心、以Eps 为半 径的圆区域内包含的点集合，记作N Eps(p)={q ∈D βdist(p,q)≤ Eps } 。这里D 为数据库[1] 。 定义2.3 （核心点：Core Points ）空间中某一点的密度，如果大于某一给定阈值MinPts ， 则称该为核心点[3] 。 定义2.4 （边界点：Border Points ）空间中某一点的密度，如果小于某一给定阈值MinPts ， 则称该为边界点[3] 。 定义2.5 （直接密度可达到）点p 从点q 直接密度可达，若它们满足： 1) p 处于q 的邻域中，即p ∈N Eps(q) ； 2) q 是核心点，即β N Eps(q) β≥MinPts[3] 。 定义2.6 （密度可达到）点p 从点q 密度可达，若（p1 ，p2 ，...，pn ），其中p1=p ，pn=q ， 且有pi 从pi+1 直接密度可达[3] 。 定义2.7 （密度连接）点p 和点q 是密度连接的，若vo ，使p 和q 都从o 密度可达[1] 。 定义2.8 （类：Cluster ）数据库D 的非空集合C 是一个类，当且仅当C 满足以下条件： 1) 对于Pp，q，若p ∈C，且从p 密度可达q，则q ∈C ； 2) 对于Pp，q，有p ∈C 和q ∈C，则p 和q 是密度连接的[3] 。 定义2.9 （噪声：Noise ）数据库D 中不属于任何类的点为噪声[1] 。 -1- 2.2 DBSCAN算法的基本思路 考察数据库D 中的某一点o，若o 是核心点，则通过区域查询得到该点的邻域，邻域中 的点和o 同属于一个类，这些点将作为下一轮的考察对象（即种子点），并通过不断地对种 子点进行区域查询来扩展它们所在的类，直至找到一个完整的类。然后，依此程序寻找其它 的类。最后剩下的不属于任何类的点即为噪声。 DBSCAN 算法的思想是：对于某一聚类中的每个对象，在给定半径（文中用Eps 表示） 的邻域内数据对象个数必须大于某个给定值，也就是说，邻域密度必须超过某一阈值（文中 用MinPts 表示）[4] 。DBSCAN 算法的聚类过程基于如下事实，