密度聚类

密度聚类,顾名思义将一些密度大的地方归为一类,另一些密度大的地方归为另一类.

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种基于密度的聚类算法，通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。

DBSCAN密度定义

DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数用来描述邻域的样本分布紧密程度。其中，描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为的邻域中样本个数的阈值。

假设我的样本集是,则DBSCAN具体的密度描述定义如下：

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

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

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

• 密度可达：对于和,如果存在样本样本序列,满足, 且由密度直达，则称由密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。

• 密度相连：对于和,如果存在核心对象样本，使和均由密度可达，则称和密度相连。注意密度相连关系是满足对称性的。

图中是核心对象,由密度直达,由密度可达,与密度相连.

根据以上定义可以通俗的理解他们的区别:

两点密度直达必须有一个是核心对象,一个必须在另一个的邻域圈内

两点密度可达也必须有一个是核心对象.

两点密度相连,则都可以不是核心对象

DBSCAN密度聚类思想

DBSCAN密度聚类定义一个类别为最大密度相连的样本集合，或者说一个簇。

那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。

第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。

第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。

第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。

DBSCAN小结

和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，如下图中的聚类则不能使用K-Means，K-Means一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似。

编程实现:
https://www.kaggle.com/swimmingwhale/bdscan

参考:
周志华<机器学习>
https://www.cnblogs.com/pinard/p/6208966.html