机器学习|聚类算法之DBSCAN
DBSCAN，全称：Density-Based Spatial Clustering of Applications with Noise，是一个比较有代表性的基于密度的聚类算法。
DBSCAN将簇定义为密度相连的点的最大集合，并可在噪声的空间中发现任意形状的聚类。
01
—
基本概念
邻域：以给定对象P为圆心，半径为r的圆形区域，称为P的邻域。
核心对象：给定对象P，其领域内的样本点数 >= MinPts，则称P为核心对象，如下图所示，设定MinPts=5，可以看到P的邻域内的样本点数为7个，所以P为核心对象，可以理解为点P的密度比较大。
边界点：非核心对象，如下所示，p的邻域内样本数小于MinPts.
噪音点：不与任何密度区域相连，如下所示
密度可达：o在p的邻域内，从p到o是直接密度可达，而q对象的邻域内不包括p，但是包括o，这样p->o->q，称p到q是密度可达的。
密度相连：q和p是密度可达的, q和t也是密度可达的，则p和t是密度相连的。
02
—
DBSCAN目标
DBSCAN目标是找到密度相连对象的最大集合。
03
—
DBSCAN算法
DBSCAN算法描述：
输入: 包含n个对象的数据集，半径e，最少数目MinPts;
输出:所有生成的簇。
(1)从数据集中抽出一个未处理的点；
(2)if 抽出的点是核心点:
then 找出所有从该点密度可达的对象，形成一个簇；
else:
抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点；
until 所有的点都被处理。
04
—
DBSCAN算法伪代码
标记所有对象为 unvisited
while unvisited元素个数>0:
随机选择一个unvisited对象p:
标记p为visited
if p 的邻域至少有MinPts个对象:
创建一个新簇 C，并把 p 添加到C
N = {p的邻域中的对象集合}
For p' in N:
if p'==unvisited:
标记 p' 为 visited
if p'的邻域至少有MinPts对象:
把这些对象添加到N中
把 p' 添加到 C
属于簇C的样本点归位
else:
标记p为噪声
05
—
DBSCAN算法的两个超参数
DBSCAN需要二个超参数： 半径 r 和最小包含点数 minPts.
DBSCAN算法优点：
- 不用指定簇的个数
- 可以发现任意形状的簇
- 容易发现异常点
缺点是它们对超参数的取值很敏感，且它们的选择无规律可循，只能靠经验确定。
更多聚类算法请参考之前的推送：
机器学习|K-Means算法
机器学习高斯混合模型：聚类原理分析（前篇）
机器学习高斯混合模型（中篇）：聚类求解
机器学习高斯混合模型（后篇）：GMM求解完整代码实现
高斯混合模型：不掉包实现多维数据聚类分析