DBSCAN算法

Density-Based Spatial Clusting of Applications with Nosie

1、关键概念

如果某个点的密度达到算法设定的阈值，则为核心点。即半径r的邻域内点的数量不小于minPts

直接密度可达：如果点p在点q的r邻域内，且q是核心点，则成p到q是直接密度可达。

密度可达：如果有点序列：q0，q1,...qk，对任意的qi，qi-1是直接密度可达的，则称从q0到qk是密度可达的。（实际是直接密度可达的“传播”）

密度相连：如果从某个核心点p出发，到点q和点k都是密度可达的，则称点q和点k是密度相连的。

边界点：属于某一类的非核心点。

噪声点：不属于任何一个类簇的点，从任何一个核心点出发都是密度不可达的。

应用：异常检测，聚类。 

2、算法工作流程

1. 标记所有对象为unvisited；
2. Do
3. 随机选择一个unvisited对象p；
4. 标记p为visited；
5. if p的ε-邻域至少有minpts个对象
6.         创建一个新簇C，并把p添加到C；
7.         令N为p的ε-邻域中的对象集合
8.         FOR N 中每个点p*
9.            if p*是unvisited;
10.                标记p*为visited;
11.                if p*的ε-邻域至少有minpts个对象，把这些对象添加到N;
12.                如果P*还不是任何簇的成员，把p*添加到C;
13.        END for;
14.        输出C；
15.    Else标记p为噪声
16. Until没有标记为unvisited的对象;

参数D：数据集;

参数ε：指定半径；可以通过K距离（给定集合P中所有点到集合D的子集S中所有点的距离，然后依次按照距离从小到大排序）来设定半径。

参数minpts：密度阈值;一般取的比较小，多次尝试。

3、算法优缺点

4、可视化展示dbscan

https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/