DBSCAN-基于密度的聚类

一、DBSCAN算法介绍

  DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法

• 可以在有噪音的数据中发现各种形状和各种大小的簇。
• 寻找被低密度区域分离的高密度区域，这些高密度区域就是一个一个的簇，这里的密度指的是一个样本点的领域半径内包含的点的数目
• 可以用来过滤噪声孤立点数据，发现任意形状的簇（因为它将簇定义为密度相连的点的最大集合）
• 与k-means算法的不同之处在于它不需要事先指定划分的簇的数目。

二、基本概念

• ε \varepsilon ε邻域：对于任意样本i和给定距离 ε \varepsilon ε，样本i的 ε \varepsilon ε邻域是指所有与样本i距离不大于 ε \varepsilon ε的样本集合；
• 核心点：若样本i的 ε \varepsilon ε邻域中至少包含MinPts个样本，则i是一个核心对象；
• 边界点：如果一个对象i是非核心对象，但它的领域中有核心对象，则为边界点。
• 噪声点：除了核心点和边界点的
• 密度直达：若样本m在样本p的 ε \varepsilon ε邻域中，且p是核心对象，则称样本m由样本p密度直达
• 密度可达：对于样本i和样本j，如果存在样本序列p1，p2，…，pn，其中p1=i，pn=j，并且pm由pm-1密度直达，则称样本i与样本j密度可达；如p与q可达
• 密度相连：对于样本s和样本r，若存在样本o使得s与r均由0密度可达，则称s与r密度相连。

三、优缺点

如下图， eps, MinPoints选取不同，结果会有很大的影响

3.3、瓶颈

  在 DBSCAN 算法中，由于边界点可以被不止一个簇密度相连，对数据不同的处理顺序可能会导致不同的处理结果，所以不确定性是 DBSCAN 的问题之一。DBSCAN 的聚类效果会受到欧式距离的通病维数灾难的影响，与此同时对于在密度上有较大差异的数据，最小样本个数 MinPts 的选取又非常困难。所以如何选择邻域距离e和邻域最小样本个数 MinPts 是DBSCAN 算法中非常关键的问题。

Reference

• DBSCAN算法学习笔记及scala实现