描述

本文对经典点云聚类算法DBSCAN进行分析

论文名称:A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise

1. 介绍

如今,数据是从许多不同类型的设备自动接收的。卫星、x射线和交通摄像头只是其中的一小部分。为了使我们能够理解这些信息/数据,必须对其进行处理。

在处理大型数据集时,在大多数情况下,能够通过将数据划分为较小的类别来分离信息,并最终进行类识别是非常有用的。在处理大型空间数据库时,这一点尤为重要。例如,一颗卫星在绕地球运行时收集图像。需要对图像的哪些部分进行分类,包括房屋、汽车、道路、湖泊、森林等。由于图像数据库很大,因此需要一种良好的分类算法。例如,分类可以借助聚类算法来完成,聚类算法将相似的数据聚集到不同的聚类中。然而,使用聚类算法涉及到一些问题:如果用户没有足够的领域知识,通常很难知道应该为特定数据库使用哪些输入参数。此外,空间数据集可能包含大量数据,试图在多个维度中找到聚类模式的计算成本非常高。计算时间短总是有利的。最后,簇的形状可以是任意的,在坏的情况下非常复杂。找到这些形状可能非常麻烦。

有一些很好使用的聚类算法;其中一位是著名的CLARANS。其他方法有K-means、K-medoid、层次聚类和自组织映射。然而,这些算法都不能很好地处理上述三个问题。本报告将不讨论这些方法,而是重点讨论DBSCAN[1](基于密度的噪声应用程序空间聚类)算法,该算法介绍了这些问题的解决方案。

本文将采用以下结构。第2节将讨论DBSCAN算法的工作原理。第3节将介绍DBSCAN的各种可能应用,并在效率方面与CLARANS进行一些比较。最后,第4节包含了本文的结论,并总结了DBSCAN算法的积极和消极方面。

2. DBSCAN算法

DBSCAN算法可以通过查看数据库元素的局部密度,仅使用一个输入参数来识别大型空间数据集中的聚类。此外,用户可以获得关于哪个参数值合适的建议。因此,需要最少的领域知识。DBS还可以确定哪些信息应归类为噪声或异常值。尽管如此,它的工作过程很快,并且可以很好地随数据库的大小扩展——几乎是线性的。

通过使用数据库中节点的密度分布,DBSCAN可以将这些节点分类为单独的簇,这些簇定义了不同的类。DBSCAN可以找到任意形状的簇,如图1所示。然而,相互靠近的集群往往属于同一类。

(分析:任意形状的点云聚类是工程时算法必须可以处理的情况,无法提取任意形状的点云聚类算法根本无法使用)font>


下一节将进一步描述DBSCAN算法的工作原理。其计算过程基于六个规则或定义,创建两个引理。


定义1:一个点的Eps邻域
定义点的邻域范围

要使一个点属于一个簇,它需要至少有一个比距离Eps更靠近它的点。 (至少簇里面有一个点,距离它的距离是小于阈值的)

定以2:直接密度可达

核心点到它的边界点,是直接密度可达
有两种点属于一个簇;有边界点和核心点,如图2所示。


“边界点的Eps邻域往往比核心点的Eps邻域具有更少的点。”. 边界点仍然是集群的一部分,为了包含这些点,它们必须属于核心点q的Eps邻域,如图3所示。

为了使点q成为核心点,它需要在其Eps邻域内具有最小数量的点。

图3. 点p可以从点q直接达到密度,但反之亦然。

定义3:密度可达
核心点经过一些核心点才到达边界点,是密度可达
“如果存在点链p_1…,p_n,p_1=q,p_n=p,使得p_i+1可以直接从p_i密度到达,则点p是从点q相对于Eps和MinPts密度可达的。” 图4显示了密度可达点的图示。


定义4:密度相连
同一类中点和点的关系,是密度相连

有时,两个边界点将属于同一个集群,但两个边界点不共享特定的核心点。在这些情况下,这些点彼此无法达到密度。然而,必须存在一个核心点q,从该点可以达到密度。图5显示了密度连接的工作原理。

“点p是相对于Eps和MinPts连接到点q的密度,如果存在点o,则p和q都是相对于Eps和MINPT从o的密度可达。”

定义5:(集群)

同一聚类
如果点p是簇C的一部分,并且点q是相对于给定距离和该距离内的最小点数从点p可达的密度,则q也是簇C的一部分。

1) “∀ p、 q:如果pϵC和q的密度可从p关于Eps和MINPT达到,则qϵC。

两个点属于同一个簇C,这与p是相对于给定距离和该给定距离内的点数连接到q的密度相同。

2) “∀ p、 qϵC:p是相对于Eps和MinPts与q的密度相连。

定义6:(噪声)

没在任何聚类的点是噪声

噪声是数据库中不属于任何集群的点集。

引理1:

点云聚类结果是稳定的
簇可以由其任何核心点形成,并且始终具有相同的形状。

引理2:

聚类过程
假设p是C簇中的核心点,具有给定的最小距离(Eps)和该距离内的最小点数(MINPT)。如果集合O对于相同的Eps和minpt可以从p获得密度,那么C等于集合O。

“为了找到聚类,DBSCAN从任意点p开始,检索从p到Eps和MinPts的所有点密度。如果p是核心点,此过程生成关于Eps和MinPts的聚类(请参阅引理2)。如果p是边界点,则没有从p到密度的点,DBSCAN访问数据库的下一个点。”

3、应用

WEKA是实现DBSCAN算法的软件程序示例。本节下文给出了DBSCAN算法的一些实际应用示例。

  • 卫星图像

    从世界各地的卫星接收到大量数据,这些数据必须转化为可理解的信息,例如,根据森林、水和山脉对卫星拍摄图像的区域进行分类。在DBSCAN算法能够在数据库中对这三个元素进行分类之前,必须对图像处理进行一些工作。一旦完成图像处理,数据显示为空间数据,DBS可以根据需要对聚类进行分类。

  • X射线晶体学

    X射线结晶学是另一种定位晶体中所有原子的实际应用,这会产生大量数据。DBSCAN算法可用于发现和分类数据中的原子。

  • 温度数据中的异常检测

    这种应用程序侧重于数据中的模式异常,这在一些情况下很重要,例如信贷欺诈、健康状况等。这种应用程序测量温度异常,这与环境变化(全球变暖)有关。它还可以发现设备错误等。需要检测和检查这些异常模式,以控制局势。DBSCAN算法能够在数据中发现此类模式。

4.比较(DBSCAN与CLARANS)

通过原始报告[1],将DBSCAN算法与另一种聚类算法进行了比较。这一个被称为CLARANS(基于随机搜索的集群大型应用程序)。这是对k-medoid算法的改进(聚类的一个对象位于聚类中心附近,而不是聚类的重心,即k-means)。与k-medoid相比,CLARANS的良好特性是,它对具有大约1000个对象的数据库非常有效。当数据库变大时,CLARANS将落后,因为算法将所有对象临时存储在主存中,即运行时间将增加。

以下部分显示了DBSCAN和CLARANS之间的性能差异很大。使用的数据库如图1所示,使用CLARANS的结果如图6所示。如图6所示,与DBSCAN不同的是,CLARANS未能为三个不同的数据库正确分类所有集群,如图7所示。


到目前为止,DBSCAN算法已经很好地对所有集群进行了分类。然而,在比较两种算法之间的运行时间时,它也具有优越性。图1显示了比较结果,由此产生的时间差异很大

综上所述,DBSCAN的计算时间相对于数据库中的点数几乎呈线性增加。然而,CLARANS增益是指数级的,在本测试中表现出色,系数为250到1900。随着数据库大小的增加,该系数将继续增大。

5. 总结

大型空间数据库的分类是一项困难且计算量大的任务。使用聚类算法是一种方法,我们已经看到有几种方法可以完成这项工作。然而,我们也看到了使用这些方法时包括的问题;找到正确的输入参数,定位任意形状的簇,最后但并非最不重要的是,在合理的时间内完成整个过程。DBSCAN算法解决了所有这些问题,因为它可以非常快速地找到那些复杂的簇形状,只需分配一个输入参数。还建议用户使用此参数的值。

我们讨论了DBSCAN算法与著名的CLARANS算法相比在准确性方面的效率。结果极为片面。在某些情况下,使用大型数据库时,DBSCAN算法的速度要快1900多倍,最终结果仍然更好。它唯一真正的缺点是,如果彼此距离太近,即使密度不同,也很难区分分离的簇。

总结

本文的分析是基于论文《DBSCAN A Density-Based Spatial Clustering of Application with Noise》,它并不是DBSCAN的原文,但知识内容是一致的。

我总结的DBSCAN的特点如下

优点:

  1. 可以发现任意形状的聚类簇
  2. 不需要输入类别数K
  3. 聚类同时找到噪声点
  4. 聚类结果稳定

缺点:

  1. 样本集较大时,聚类收敛时间较长(可以 使用KD树来加速)
  2. 密度不同,但距离相近时,很难区分
  3. 有两个输入参数:距离阈值及邻域样本数阈值

写的不容易,欢迎各位朋友点赞并加关注,谢谢!