机器学习 - DBSCAN聚类算法

1. DBSCAN简介

密度聚类 （亦称基于密度的聚类算法，density-based clustering）算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本的密度的角度来考察样本之间的可连接性，并基于可连接性不断扩展聚类簇已获得最终的聚类结果。
DBSCAN是一种著名的密度聚类算法，它基于一组“领域”参数 $(\epsilon, MinPts)$ 来刻画样本分布的紧密程度。 和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。
凸样本集定义： 简单来说，数据集D中任意两点的连线上的点，也会在数据集D内，那么数据集D就是一个凸集。如下图所示就是一个非凸样本集，Kmeans效果表现非常差。

Kmeans聚类和DBSCAN聚类效果对比.png

2. DBSCAN基本概念

对于给定的数据集 $D = (x_1, x_2, ..., x_m)$ ，定义以下几个基本概念：

$\epsilon$ -领域： 对 $x_j \in D$ , 其 $\epsilon$ -领域包含样本集 $D$ 中与 $x_j$ 的距离不大于 $\epsilon$ 的样本，即 $N_{\epsilon}(x_j) = \{x_i \in D | dist(x_i,x_j) \leq \epsilon \}$ ；

核心对象（core object）： 若 $x_j$ 的 $\epsilon$ -领域至少包含MinPts个样本，即 $|N_{\epsilon}(x_j)| \geq MinPts$ ，则 $x_j$ 是一个核心对象；

密度直达（directly density-reachable）： 若 $x_j$ 位于 $x_i$ 的 $\epsilon$ -领域中，且 $x_i$ 是核心对象，则称 $x_j$ 由 $x_i$ 密度直达；

密度可达（density-reachable）： 对 $x_i$ 与 $x_j$ ，若存在样本序列 $p_1, p2, ..., p_n$ 其中 $p_1 = x_i, p_n = x_j$ 且 $p_{i+1}$ 由 $p_i$ 密度直达，则称 $x_j$ 由 $x_i$ 密度可达；

密度相连（density-connected）： 对 $x_i$ 与 $x_j$ ，若存在 $x_k$ 使得 $x_i$ 与 $x_j$ 均由 $x_k$ 密度可达，则称 $x_i$ 与 $x_j$ 密度相连；

下图中蓝色点为核心对象，假设MinPts=3

DBSCAN基本概念举例.png

3. DBSCAN核心思想

DBSCAN将“簇”定义为：由密度可达关系导出的最大的密度相连样本集合。DBSCAN算法首先任选数据集中的一个核心对象为“种子”，再由此出发确定相应的聚类簇。首先根据领域参数 $(\epsilon,MinPts)$ 找出所有核心对象，然后以任意核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。