数据挖掘概念与技术笔记（8）：聚类（2）

基于密度的聚类

密度聚类方法的指导思想是，只要样本点的密度大于某阈值，则将该样本添加到最近的簇中。这类算法能克服基于距离的算法只能发现“类圆”（凸）的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。

DBSCAN：一种基于高密度连通区域的密度聚类

DBCSAN（Density-Based Spatial Clustering of Applications with Noise）是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的数据中发现任意形状的聚类。

基础概念

对象的ϵ−领域：给定对象在半径ϵϵ内的区域
核心对象：对于给定的数目m，如果一个对象的ϵ−领域至少包含m个对象，则称该对象为核心对象。
直接密度可达：给定一个对象集合D，如果p是在q的ϵ−领域内，而q是一个核心对象，我们说对象p从对象q出发时直接密度可达的。

如图ϵ=1 ，m=5， q是一个核心对象，从对象q出发到对象p是直接密度可达的。

密度可达：如果存在一个对象链$p_1,p_2,⋅⋅⋅,p_n$，使得$p_1=q$，$p_n=p$，并且对$p_i (1≤i≤n)∈D$，有$p_{i+1}$是从$p_i$关于ϵ和m直接密度可达的，则p是从q密度可达的(也就是中间连接了多个直接密度可达)。注意密度可达不是等价关系，因为它不是对称的。如果$o_1$和$o_2$都是核心对象，则都是密度可达；如果$o_2$是核心对象$o_1$不是，则$o_1$可能是从$o_2$密度可达，反过来就不可以。（需要从核心出发到不核心）

密度相连：如果对象集合D中存在一个对象o，使得对p和q是从o关于ϵ和m密度可达的，那么对象p和q是关于ϵ和m密度相连的。 (存在中间点o，分别到q和p两条路线都是密度可达，则q和p密度相连)。不像密度可达，密度相连是等价的。

算法步骤：

下面这张图来自WIKI，图上有若干个点，其中标出了A、B、C、N这四个点，据此来说明这个算法的步骤：

1、首先随机选择A点为算法实施的切入点，我们将ϵϵ设置为图中圆的半径，对象密度个数$m（minPts）$设定为4。这里我们看到，A点的ϵϵ领域包含4个对象（自己也包含在内），大于等于$m(minPts)$，则创建A作为核心对象的新簇，簇内其他点都（暂时）标记为边缘点。
2、然后在标记的边缘点中选取一个重复上一步，寻找并合并核心对象直接密度可达的对象。对暂时标记为边缘点反复递归上述算法，直至没有新的点可以更新簇时，算法结束。这样就形成了一个以A为起始的一个聚类，为图中红色的中心点和黄色的边缘点（黄红点都形成簇）
3、如果还有Points未处理，再次新产生一个类别来重新启动这个算法过程。遍历所有数据，如果有点既不是边缘点也不是中心点，将其标记为噪音。

初始，给定数据集D中的所有对象都标记为”unvisited”。DBSCAN随机地选择一个未访问的对象p，标记p为”visited”，并检查p是否为核心对象。如果不是，标记p为噪点，否则为p创建一个新的簇C，并且将领域内所有对象都放到候选集合N中（这个集合会慢慢加大）。DBSCAN迭代地把N中不属于其他簇的对象添加C中。在此过程中，对于N中标记为”unvisited”的对象p’ ，标记为”visited”，如果它是核心对象，则将它的领域节点都添加到N中。DBSCAN继续从候选集N中添加到C，直到N的集合为空。此时，簇C完全生成，于是被输出。

从上述算法可知：

每个簇至少包含一个核心对象；
非核心对象可以是簇的一部分，构成了簇的边缘（edge）；
包含过少对象的簇被认为是噪声；

DBSCAN的主要优点有：

　　1）可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。

　　2）可以在聚类的同时发现异常点，对数据集中的异常点不敏感。

　　3）聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。

DBSCAN的主要缺点有：

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

　　2）如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。

　　3）调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值$m(MinPts)$联合调参，不同的参数组合对最后的聚类效果有较大影响。

OPTICS:通过点排序识别聚类结构

在前面介绍的DBSCAN算法中，有两个初始参数Eps（邻域半径）和minPts(Eps邻域最小点数)需要手动设置，并且聚类的结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果。为了克服DBSCAN算法这一缺点，提出了OPTICS算法（Ordering Points to identify the clustering structure），翻译过来就是，对点排序以此来确定簇结构。

OPTICS是对DBSCAN的一个扩展算法。该算法可以让算法对半径Eps不再敏感。只要确定minPts的值，半径Eps的轻微变化，并不会影响聚类结果。OPTICS并不显示的产生结果类簇，而是为聚类分析生成一个增广的簇排序，从这个排序中可以得到基于任何参数Eps和minPts的DBSCAN算法的聚类结果。

核心距离与可达距离

要搞清楚OPTICS算法，需要搞清楚2个新的定义：核心距离和可达距离。

核心距离：一个对象p的核心距离是使得其成为核心对象的最小半径，如果p不是核心点，其可达距离没有定义。
可达距离：从q到p的可达距离是$\max \{core-distance(q), dist(p,q)\}$。如果q不是核心点，其从q到p的可达距离没有定义。另外对象p关于不同的核心对象，p可能有多个可达距离。p的最小可达距离代表离一个稠密簇的距离越短，越处于核心密集地段。

举例，下图中假设minPts=3，半径是ϵϵ。那么P点的核心距离是d(1,P)，点2的可达距离是d(1,P)，点3的可达距离也是d(1,P)，点4的可达距离则是d(4,P)的距离。

OPTICS算法描述

输入：样本集D, 邻域半径ϵϵ, 给定点在ϵϵ领域内成为核心对象的最小领域点数MinPts

输出：具有可达距离信息的样本点输出排序

首先创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序。你可以把有序队列里面放的理解为待处理的数据，而结果队列里放的是已经处理完的数据）。

步骤：

D: 待聚类的集合
Q: 有序队列，元素按照可达距离排序，可达距离最小的在队首
O: 结果队列，最后输出结果的点集的有序队列

首先从D中取出一个核心对象p，首先p要先标记加入结果队列，它的领域则加入有序队列。从有序队列取队首q，先把队首q标记且加入结果队列，若q不为核心对象则继续从Q队列中取队首处理；否则若为核心队列则将q的领域加入到有序队列并重新排列顺序。加入新元素后再取有序队列队首依次循环处理。算法结束，输出结果队列中的有序样本点。

得到结果队列后，使用如下算法得到最终的聚类结果：

从结果队列中按顺序取出点，如果该点的可达距离不大于给定半径ϵϵ，则该点属于当前类别，否则至步骤2
如果该点的核心距离大于给定半径ϵ，则该点为噪声，可以忽略，否则该点属于新的聚类，跳至步骤1
结果队列遍历结束，则算法结束

上面的算法处理完后，我们得到了输出结果序列，每个节点的可达距离和核心距离。我们以可达距离为纵轴，样本点输出次序为横轴进行可视化：

其中：

X轴代表OPTICS算法处理点的顺序，Y轴代表可达距离。
簇在坐标轴中表述为山谷，并且山谷越深，簇越紧密
黄色代表的是噪声，它们不形成任何凹陷。

当你需要提取聚集的时候，参考Y轴和图像，自己设定一个阀值就可以提取聚集了。再来一张凹陷明显的：

OPTICS的核心思想：

较稠密簇中的对象在簇排序中相互靠近
一个对象的最小可达距离给出了一个对象连接到一个稠密簇的最短路径

DPCA算法

2014年6月，Alex Rodriguez和Alessandro Laio在ScienceScience上发表了一篇名为《Clustering by fast search and find of density peaks》的文章，提供了一种简洁而优美的聚类算法，是一种基于密度的聚类方法，可以识别各种形状的类簇，并且参数很容易确定。它克服了DBSCAN中不同类的密度差别大、邻域范围难以设定的问题，鲁棒性强。在文章中提出的聚类方法DPCA算法（Desity Peaks Clustering Algorithm）基于这样一种假设：对于一个数据集，聚类中心被一些低局部密度的数据点包围，而且这些低局部密度点距离其他有高局部密度的点的距离都比较大。