Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

DBSCAN聚类

DBSCAN 是一种著名的密度聚类算法,它使用一组关于“邻域”的参数来描述样本分布的紧密程度。根据以上概念,DBSCAN 将簇定义为:由密度可达关系导出的最大的密度相连样本集合。通用 DBSCAN (GDNSCAN)算法是是对 DBSCAN 算法的泛化,使之可以处理从二维点,三维点,五维点和以及二维多边形等很多现实世界的问题。

简介

DBSCAN是一种著名的密度聚类算法,它使用一组关于“邻域”的参数来描述样本分布的紧密程度。在描述具体的算法之前,我们首先定义几个相关的概念:

  • 邻域:对于任意样本i和给定距离e,样本i的e邻域是指所有与样本i距离不大于e的样本集合;
  • 核心对象:若样本i的e邻域中至少包含MinPts个样本,则i是一个核心对象;
  • 密度直达:若样本j在样本i的e邻域中,且i是核心对象,则称样本j由样本i密度直达;
  • 密度可达:对于样本i和样本j,如果存在样本序列p1,p2,...,pn,其中p1=i,pn=j,并且pm由pm-1密度直达,则称样本i与样本j密度可达;
  • 密度相连:对于样本i和样本j,若存在样本k使得i与j均由k密度可达,则称i与j密度相连。

上图直观显示 DBSCAN 中这几个概念:当 MinPts=3 的时候,虚线圆圈为 e 邻域,x1 是核心对象,x2 由 x1 密度直达,x3 由 x1 密度可达,x3 与 x4 密度相连。

根据以上概念,DBSCAN 将簇定义为:由密度可达关系导出的最大的密度相连样本集合。

DBSCAN算法步骤大致描述如下:

对于给定的邻域距离e和邻域最小样本个数MinPts:

  1. 遍历所有样本,找出所有满足邻域距离e的核心对象的集合;
  2. 任意选择一个核心对象,找出其所有密度可达的样本并生成聚类簇;
  3. 从剩余的核心对象中移除2中找到的密度可达的样本;
  4. 从更新后的核心对象集合重复执行2-3步直到核心对象都被遍历或移除。

通用 DBSCAN (GDNSCAN)算法是是对 DBSCAN 算法的泛化,使之可以处理从二维点,三维点,五维点和以及二维多边形等很多现实世界的问题。

【描述来源:周志华. (2016). 机器学习: = Machine learning.清华大学出版社.】

【描述来源:Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd (Vol. 96, No. 34, pp. 226-231).】

【描述来源:Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (1998). Density-based clustering in spatial databases: The algorithm gdbscan and its applications. Data mining and knowledge discovery, 2(2), 169-194.】

发展历史

DBSCAN 算法最初有 Ester 等人在1996年最初提出,DBSCAN 自发表后受到了学界的一直推崇,众多科学文献引用该算法,同时DBSCAN 算法也是 PreDeCon 和 SUBCLU 等聚类算法中的一部分,1998年,Sander 和 Ester 提出了适用性更加广泛的 GDBSCAN 算法。 2014年的时候,DBSCAN 算法获得了2014 SIGKDD Test of Time Award, 2007年 Birant 提出了一种名为 ST-DBSCAN 的算法,该算法最显著的优势在于可以用于时空数据的处理。2010年,Kisilevich 等人提出了通过地理标记照片数据从而挖掘地点和事件的算法 P-DBSCAN。

主要事件

年份事件相关论文
1996Ester 等人在提出 DBSCAN 算法Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd (Vol. 96, No. 34, pp. 226-231).
1998Sander 和 Ester 等人提出 GDBSCAN 算法Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (1998). Density-based clustering in spatial databases: The algorithm gdbscan and its applications. Data mining and knowledge discovery, 2(2), 169-194.
2007Birant 提出 ST-DBSCAN 的算法Birant, D., & Kut, A. (2007). ST-DBSCAN: An algorithm for clustering spatial–temporal data. Data & Knowledge Engineering, 60(1), 208-221.
2010Kisilevich 等人提出 P-DBSCAN 算法Kisilevich, S., Mansmann, F., & Keim, D. (2010, June). P-DBSCAN: a density based clustering algorithm for exploration and analysis of attractive areas using collections of geo-tagged photos. In Proceedings of the 1st international conference and exhibition on computing for geospatial research & application (p. 38). ACM.

发展分析

瓶颈

在 DBSCAN 算法中,由于边界点可以被不止一个簇密度相连,对数据不同的处理顺序可能会导致不同的处理结果,所以不确定性是 DBSCAN 的问题之一。DBSCAN 的聚类效果会受到欧式距离的通病维数灾难的影响,与此同时对于在密度上有较大差异的数据,最小样本个数 MinPts 的选取又非常困难。所以如何选择邻域距离e和邻域最小样本个数 MinPts 是 DBSCAN 算法中非常关键的问题。

未来发展方向

DBSCAN 作为密度聚类最常见的方法之一,其应用也越来越多,很多其他的算法与之结合是未来该算法甚至整个聚类研究的一个方向,目前已知的 DBSCAN 和层次聚类有很多的交叉应用。其次,对于 MinPts 和 e 的选择一直是 DBSCAN 研究的关键。

Contributor: Chao Yang

简介