DBSCAN原理及实现

2019-05-26 本文已影响0人 d518a9b6ae51

模型概述

DBSCAN是一种聚类算法，首先明确几个概念：

$\epsilon$ -邻域：对任一样本点 $x^{(i)}$ ，数据集 $D$ 中与该样本点的距离不大于 $\epsilon$ 的其余样本点构成的集合，该集合内的样本数为该点的密度，即dense_i $=N_{\epsilon}(x^{(i)})=\{x^{(j)}\in{D}\|dist(x^{(i)},x^{(j)})\le\epsilon\}$
核心对象(core object)：若某一样本的密度不小于一个阈值，即dense_i $\ge$ Min_pts，则该样本是一个核心对象
边界对象：若某一样本的密度小于Min_pts，则该样本成为边界对象；特别地，密度为 $1$ 的样本被称为噪声样本
密度直达：核心对象直达其邻域内的样本点，直达方向由核心对象指向其邻域内的样本点
密度可达：对两个样本点 $x^{(i)}$ 与 $x^{(j)}$ ，若存在一条密度直达链 $x^{(i)}\rightarrow...{\rightarrow}x^{(j)}$ ，则称 $x^{(i)}$ 可达 $x^{(j)}$ ，方向由 $x^{(i)}$ 指向 $x^{(j)}$ ，前者必须为核心对象，后者不作要求
密度相连：同一个核心对象可达的两样本点称为密度相连，即同时存在两条直达链： $x^{(i)}\rightarrow...{\rightarrow}x^{(j)}$ 与 $x^{(i)}\rightarrow...{\rightarrow}x^{(k)}$ ， $x^{(j)}$ 与 $x^{(k)}$ 密度相连

DBSCAN算法将所有密度相连的样本聚成一类。换个角度来说，DBSCAN会尽量多的寻找密度相连的核心对象（容易推出密度相连在核心对象上满足交换律），然后将这些核心对象及其邻域样本都归为一类。