【机器学习】密度聚类

本文介绍了一种无参的密度聚类算法-DBSCAN。首先介绍了DBSCAN的类表示为一簇密度可达的样本点，相似性度量为密度可达。然后介绍了DBSCAN中几个基本定义： -邻域，核心对象，密度可达，密度直达，噪声点，基于此绍了DBSCAN算法的实现流程。最后介绍了算法的特点，能发现任意簇，抗噪性强，聚类时间长，存在维度灾难问题。

作者 | 文杰

编辑 | yuquanle

密度聚类-DBSCAN

DBSCAN的类表示是一簇密度可达的样本，相似性度量定义为密度可达，密度可达即为一类，属于硬划分。

密度聚类是一种基于密度的聚类，其根据样本的空间分布关系进行聚类。一般来讲，用带参的模型来定义样本的分布可以看作是带参的密度估计，比如高斯混合模型，高斯判别分析；用无参的模型来描述样本的分布称为无参密度估计，比如直方图，核密度估计，山峰聚类，DBSCAN，meanshift。

假设样本集是，在DBSCAN中为了描述样本分布的关系，定义了如下几个概念：

1） -邻域：对于，其-邻域包含样本集中与的距离不大于的子样本集，即 这个子样本集的个数记为。

2）核心对象：对于任一样本，如果其-邻域对应的 至少包含个样本，即如果，则是核心对象。

3）密度直达：如果位于的-邻域中，且是核心对象，则称由密度直达。注意反之不一定成立，即此时不能说由密度直达, 除非且也是核心对象。

4）密度可达：如果由密度直达，且由密度直达，那么由密度可达。密度可达满足封闭性。

其中密度可达是相似性度量，由于密度可达具有封闭性，所以簇内的所有点与簇内的核心均密度可达，否则即不是一个簇，所以密度可达可以对样本进行聚类，其中密度可达涉及的参数有和和距离度量。

5）噪声点：对于非核心点和不能由核心点密度可达的点即为噪声点。

DBSCAN算法流程

输入：样本集，邻域参数， 样本距离度量方式

输出：簇划分

1）初始化核心对象为，簇划分，未访问样本集合。

2）变量所有样本点，找出的核心对象并入核心对象。

3）如果核心对象，算法结束，否则从核心对象集中随机选择一个核心对象，初始化当前簇，当前核心对象集为，循环：

a）从当前的核心对象集中选择，循环：

aa）找出密度直达的未访问的点加入到，把其中未访问的核心对象加入到

ab）更新当前核心对象集

ac）更新核心对象集，更新未访问样本集

b）如果当前核心对象集，结束内部循环

4）输出簇划分。

可以看出，外层循环为簇的个数，内层循环是构建一个密度可达的簇。当算的执行完，对应既不是核心点，也不是密度可达的点我们称为异常点或者噪声点。

DBSCAN的特点：

1）由于密度可达的定义，DBSCAN具有发现任意形状的簇划分。

2）聚类的同时可发现异常点，抗噪性强。

3）不需要预先指点类数，但和的直观性不强，参数选择麻烦。

4）样本集较大时，聚类收敛时间较长，密度估计存在维度灾难问题。

5）如果样本集的密度不均匀、聚类间距差差别很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。

The End