聚类算法 -- DBSCAN 算法


当佛已无能为力,魔渡众生


转载

https://www.ibm.com/developerworks/cn/analytics/library/ba-1607-clustering-algorithm/index.html#N100CF


简要说明

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合

该算法利用基于密度的聚类的概念,即要求聚类空间中的一定区域内所包含对象(点或其他空间对象)的数目不小于某一给定阈值。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。但是由于它直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征密度的参数,因此也具有两个比较明显的弱点:

(1)当数据量增大时,要求较大的内存支持I/O消耗也很大

(2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差


算法流程

  1. 设定扫描半径 Eps, 并规定扫描半径内的密度值。若当前点的半径范围内密度大于等于设定密度值,则设置当前点为核心点;若某点刚好在某核心点的半径边缘上,则设定此点为边界点;若某点既不是核心点又不是边界点,则此点为噪声点
  2. 删除噪声点
  3. 将距离在扫描半径内的所有核心点赋予边进行连通
  4. 每组连通的核心点标记为一个簇
  5. 将所有边界点指定到与之对应的核心点的簇总

算法举例

如上图坐标系所示,我们设定扫描半径 Eps 为 1.5,密度阈值 threshold 为 3,则通过上述算法过程,我们可以得到下图:

通过计算各个点之间的欧式距离及其所在扫描半径内的密度值来判断这些点属于核心点,边界点或是噪声点。因为我们设定了扫描半径为 1.5,密度阈值为 3,所以:

  • P0 点为边界点,因为在以其为中心的扫描半径内只有两个点 P0 和 P1
  • P1 点为核心点,因为在以其为中心的扫描半径内有四个点 P0,P1,P2,P4
  • P8 为噪声点,因为其既非核心点,也非边界点
  • 其他点依次类推