DBSCAN
2018-10-12 本文已影响1人
0过把火0
算法介绍
该聚类算法是具有噪声的基于密度可达关系的聚类方法，它将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
那么该算法在定义簇时是根据设定密度阈值作为划分簇的依据，也就是满足该阈值时才认为可以分为一个簇。
从名字来看，该算法的原理似乎更加贴近人们的认知，因为是基于密度的。
算法优势
不用人为提前确定聚类类别数K
聚类速度快
能够有效处理噪声点（因为异常点不会被包含于任意一个簇，则认为是噪声）
能够应对任意形状的空间聚类
算法缺点
由于算法直接对整个数据库进行操作，并且聚类时使用了一个全局性的表征密度的参数，因此，当数据量过大时：
1）要求较大的内存支持I/O消耗很大；
2）当空间聚类的密度不均匀、聚类间距差别很大时、聚类效果有偏差。
3）调参相对复杂，主要调整距离阈值以及minPts。
什么时候选择DBSCAN
如果数据稠密、数据集不是凸集，DB会优于Kmeans
算法原理
-
参数定义
- 算法流程
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的算法不是完全稳定的算法。
