【聚类】篇四之理解密度聚类算法DBSCAN
一、密度聚类概述
密度聚类假设聚类结构能通过样本的紧密程度确定，同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。从样本密度出发考虑样本间的可连接性，然后基于可连接样本不断扩展聚类的簇实现聚类的目的。基于原型（划分）和层次的聚类方法一般只能发现球状的簇，很难去发现任意形状的簇，为了发现任意形状的簇，我们可以把簇看成是数据空间中被稀疏区域划分开的稠密区域。那么如何在基于密度的聚类中发现稠密区域呢？原则是一个对象的密度可以用靠近它的对象的数量来表示。
二、DBSCAN聚类
（一）、基础概念
DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。
DBSCAN的核心在于确定某个对象的邻域，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度，其中，ϵ描述了某一样本xj的邻域距离阈值,即样本集D中与xj距离不大于ϵ的样本，即：
MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。
首先，先明确两个概念：
1） ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|
2) 核心对象：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心对象。
然后，再利用刘建平老师博客中的一个例子理解其他几个概念密度直达，密度可达，密度相连：
假设规定MinPts=5，那么红点的ϵ邻域样本个数均不小于5，也就是说红点均是核心对象，密度直达就是指由核心对象到它的ϵ邻域样本是密度直达的；密度可达，图中用绿色箭头连起来的核心对象组成了密度可达的样本序列；在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。
（二）、算法原理
DBSCAN的核心是由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。另外需要注意的是这个簇里如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。
那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。
（三）、算法流程
主要是两大步：一个是找出样本集中的全部核心对象
另一个是任意选择一个核心对象作为种子出发，找出这个核心对象密度可达的其他核心对象，直到所有核心对象都被访问为止。
理解蓝色圈出的区域是关键，Q中最初存的是某次我们随机选出的核心对象，然后以此核心对象开始进行if语句内的步骤，找出该核心对象的 ϵ-邻域内的样本与数据集的交集，存入Q中，从数据集中剔除它们，接着如果Q不为空继续循环内，找出Q中的是核心对象的样本继续if语句内，直到Q为空，代表一个簇的完成。
(四）、优缺点
和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。
那么我们什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
DBSCAN的主要优点有：
1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
DBSCAN的主要缺点有：
1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2） 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。
参考
周志华的机器学习
刘建平老师的博客https://www.cnblogs.com/pinard/p/6208966.html
sklearn官网文档