DBSCAN

算法介绍

该聚类算法是具有噪声的基于密度可达关系的聚类方法，它将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

那么该算法在定义簇时是根据设定密度阈值作为划分簇的依据，也就是满足该阈值时才认为可以分为一个簇。

从名字来看，该算法的原理似乎更加贴近人们的认知，因为是基于密度的。

算法优势

不用人为提前确定聚类类别数K
聚类速度快
能够有效处理噪声点（因为异常点不会被包含于任意一个簇，则认为是噪声）
能够应对任意形状的空间聚类

算法缺点

由于算法直接对整个数据库进行操作，并且聚类时使用了一个全局性的表征密度的参数，因此，当数据量过大时：
1）要求较大的内存支持I/O消耗很大；
2）当空间聚类的密度不均匀、聚类间距差别很大时、聚类效果有偏差。
3）调参相对复杂，主要调整距离阈值以及minPts。

什么时候选择DBSCAN

如果数据稠密、数据集不是凸集，DB会优于Kmeans

算法原理

1. 参数定义

   
   

2. 算法流程
   1）首先确定模型中的两个参数：Eps（邻域范围）、MinPts（最少个数阈值）
   2）检查数据集中每点的Eps邻域来搜索簇，如果点p的Eps邻域包含的点多于MinPts个，则创建一个以p为核心
   对象的簇；
   3）然后，DBSCAN迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并；
   4）当没有新的点添加到任何簇时，该过程结束。

算法伪代码

(1) 首先将数据集D中的所有对象标记为未处理状态
(2) for（数据集D中每个对象p） do
(3)    if （p已经归入某个簇或标记为噪声） then
(4)         continue;
(5)    else
(6)         检查对象p的Eps邻域 NEps(p) ；
(7)         if (NEps(p)包含的对象数小于MinPts) then
(8)                  标记对象p为边界点或噪声点；
(9)         else
(10)                 标记对象p为核心点，并建立新簇C, 并将p邻域内所有点加入C
(11)                 for (NEps(p)中所有尚未被处理的对象q)  do
(12)                       检查其Eps邻域NEps(q)，若NEps(q)包含至少MinPts个对象，则将NEps(q)中未归入任何一个簇的对象加入C；
(13)                 end for
(14)        end if
(15)    end if
(16) end for

三个问题

1）异常点
一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些
样本点标记为噪音点。

2）距离衡量
可候选欧氏距离、马氏距离、曼哈顿等

3）某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？
一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。

转载注明：https://www.jianshu.com/p/1e87b9a305e7