机器学习 聚类算法之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 =

For p' in N:

if p'==unvisited:

标记 p' 为 visited

if p'的邻域至少有MinPts对象:

把这些对象添加到N中

把 p' 添加到 C

属于簇C的样本点归位

else:

标记p为噪声

05

—

DBSCAN算法的两个超参数

DBSCAN需要二个超参数： 半径 r 和最小包含点数 minPts.

DBSCAN算法优点：

不用指定簇的个数

可以发现任意形状的簇

容易发现异常点

缺点是它们对超参数的取值很敏感，且它们的选择无规律可循，只能靠经验确定。

算法channel会有系统地，认真地推送：机器学习（包含深度学习，强化学习等）的理论，算法，实践，源码实现。期待您的参与！