11 聚类算法 - 密度聚类 - DBSCAN、MDCA

09 聚类算法 - 层次聚类
10 聚类算法 - 代码案例四 - 层次聚类(BIRCH)算法参数比较

七、密度聚类概述

1、密度聚类方法的指导思想: 只要样本点的密度大于某个阈值，则将该样本添加到最近的簇中。
2、这类算法可以克服基于距离的算法只能发现凸聚类的缺点，可以发现任意形状的聚类，而且对噪声数据不敏感。
3、计算复杂度高，计算量大。

常用算法：
1、具有噪声的基于密度的聚类方法 - DBSCAN
2、密度最大值算法 - MDCA

八、DBSCAN算法

__DBSCAN__(Density-Based Spatial Clustering of Applications with Noise) - 具有噪声的基于密度的聚类方法

一个比较有代表性的基于密度的聚类算法，相比于基于划分的聚类方法和层次聚类方法，DBSCAN算法将簇定义为__密度相连的点的最大集合__，能够将足够高密度的区域划分为簇，并且在具有噪声的空间数据商能够发现任意形状的簇。

DBSCAN算法的核心思想是：__用一个点的ε邻域内的邻居点数衡量该点所在空间的密度__，该算法可以找出形状不规则的cluster，而且聚类的时候事先不需要给定cluster的数量。

DBSCAN算法基本概念 (一) ：

ε邻域(ε neighborhood，也称为Eps)：给定对象在半径ε内的区域

密度(density)：ε邻域中x的密度，是一个整数值，依赖于半径ε

MinPts定义核心点时的阈值，也简记为M

核心点(core point)：如果p(x)>=M,那么称x为X的核心点；记由X中所有核心点构成的集合为Xc，并记Xnc=XXc表示由X中所有非核心点构成的集合。直白来讲，核心点对应于稠密区域内部的点。

DBSCAN算法基本概念 (二) ：

边界点(border point): 如果非核心点x的ε邻域中存在核心点，那么认为x为X的边界点。由X中所有的边界点构成的集合为Xbd。直白来将，边界点对应稠密区域边缘的点：

噪音点(noise point)：集合中除了边界点和核心点之外的点都是噪音点，所有噪音点组成的集合叫做Xnoi；直白来讲，噪音点对应稀疏区域的点。

DBSCAN算法基本概念 (三) ：

直接密度可达(directly density-reachable)：给定一个对象集合X，如果y是在x的ε邻域内，而且x是一个核心对象，可以说对象y从对象x出发是直接密度可达的。

密度可达(density-reachable)：如果存在一个对象链p1,p2,..pm,如果满足pi+1是从pi直接密度可达的，那么称pm是从p1密度可达的。

密度相连(density-connected)：在集合X中，如果存在一个对象o，使得对象x和y是从o关于ε和m密度可达的，那么对象x和y是关于ε和m密度相连的。

DBSCAN算法基本概念 (四) ：

簇(cluster)：一个基于密度的簇是最大的密度相连对象的集合C；满足以下两个条件：
1、Maximality：若x属于C，而且y是从x密度可达的，那么y也属于C。
2、Connectivity：若x属于C，y也属于C，则x和y是密度相连。

九、DBSCAN算法流程

算法流程：
1、如果一个点x的ε邻域包含多余m个对象，则创建一个x作为核心对象的新簇；
2、寻找并合并核心对象直接密度可达的对象；
3、没有新点可以更新簇的时候，算法结束。

算法特征描述:
1、每个簇至少包含一个核心对象。
2、非核心对象可以是簇的一部分，构成簇的边缘。
3、包含过少对象的簇被认为是噪声。

看上图，顺便回顾知识点：
A->B: 密度可达。
B->A: 密度相连。(B->A走不过去)
A->A附近的点：直接密度可达。
所以只要密度可达，必然密度相连。但是密度相连不一定能推出密度可达。

上图中，只要A和A附近的点直接密度可达，就可以归为一类。所以红点之间可以形成一个簇。
此外，B和C点都与A点密度相连，所以能可以归入这个簇。

所以构建算法的思路是：先找核心点，然后再把边界找到。将核心点和边界点归入一个簇。

DBSCAN算法优缺点：

优点：
1、不需要事先给定cluster的数目。
2、可以发现任意形状的cluster。
3、能够找出数据中的噪音，且对噪音不敏感。
4、算法只需要两个输入参数。
5、聚类结果几乎不依赖节点的遍历顺序。

缺点：
1、DBSCAN算法聚类效果依赖距离公式的选取，最常用的距离公式为欧几里得距离。但是对于高维数据，由于维数太多，距离的度量已变得不是那么重要。__维度灾难__ 02 聚类算法 - 相似度距离公式、维度灾难

2、DBSCAN算法不适合数据集中密度差异很小的情况。

十、密度最大值聚类算法(MDCA)

MDCA(Maximum Density Clustering Application)算法基于__密度的思想__引入__划分聚类__中，使用密度而不是初始点作为考察簇归属情况的依据，能够自动确定簇数量并发现任意形状的簇；另外MDCA一般不保留噪声，因此也避免了阈值选择不当情况下造成的对象丢弃情况。

MDCA算法的基本思路是寻找__最高密度__的对象和它所在的__稠密区域__；MDCA算法在原理上来讲，和密度的定义没有关系，采用任意一种密度定义公式均可，一般情况下采用DBSCAN算法中的密度定义方式。

MDCA概念 (一) ：

最大密度点：

有序序列: 根据所有对象与pmax的距离对数据重新排序：

密度阈值density₀；当节点的密度值大于密度阈值的时候，认为该节点属于一个比较固定的簇，在第一次构建基本簇的时候，就将这些节点添加到对应簇中，如果小于这个值的时候，暂时认为该节点为噪声节。

MDCA概念 (二) ：

簇间距离：对于两个簇C1和C2之间的距离，采用两个簇中最近两个节点之间的距离作为簇间距离。

聚簇距离阈值dist₀：当两个簇的簇间距离小于给定阈值的时候，这两个簇的结果数据会进行合并操作。

M值：初始簇中最多数据样本个数。

MDCA算法聚类过程步骤如下：

一、将数据集划分为基本簇。
1、对数据集X选取最大密度点P_max，形成以最大密度点为核心的新簇C_i，按照距离排序计算出序列S_pmax,对序列的前M个样本数据进行循环判断，如果节点的密度大于等于density₀，那么将当前节点添加C_i中；
2、循环处理剩下的数据集X，选择最大密度点P_max，并构建基本簇C_i+1，直到X中剩余的样本数据的密度均小于density₀。

二、使用凝聚层次聚类的思想，合并较近的基本簇，得到最终的簇划分。
在所有簇中选择距离最近的两个簇进行合并，合并要求是：簇间距小于等于dist₀,如果所有簇中没有簇间距小于dist₀的时候，结束合并操作。

三、处理剩余节点，归入最近的簇。
最常用、最简单的方式是：将剩余样本对象归入到最近的簇。

12 聚类算法 - 代码案例五 - 密度聚类(DBSCAN)算法案例