三分钟看懂密度峰值聚类算法
假设待聚类的数据集：X = (𝑥1, 𝑥2, … , 𝑥n)
1.计算每个节点的两个指标：
1)局部密度𝜌：原论文中给的公式
其中， 𝑑𝑖𝑗表示点𝑥𝑖与𝑥𝑗之间的距离，而𝑑𝑐表示截断距离
不难看出， 局部密度𝜌就是与节点𝑥𝑖距离小于等于𝑑𝑐的节点的个数
2)相对距离𝛿：相对距离𝛿𝑖表示密度比𝑥𝑖大而离𝑥𝑖最近的点与𝑥𝑖之间的距离
2.聚类点选取
聚类过程如下图所示
左图为原始的数据集，右图是以局部密度𝜌为横坐标，相对距离𝛿为纵坐标的决策图，选择具有较高值𝜌和𝛿的点作为聚类中心
3.聚类
其他非聚类中心点归类到比他们的密度更大的且距离最近类中心所属的类别中
4.可以看出，整个聚类思想相对来说比较简单。但是存在几个问题：
1）截断距离dc的选取需要人工选取，它的值会对聚类结果产生影响
2）聚类点的选取需要人工取，限制其在大规模数据集上的应用
聚类算法
1. 概述
K-means聚类算法也称k均值聚类算法，是集简单和经典于一身的基于距离的聚类算法。它采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到 紧凑且独立的簇作为最终目标。
2. 算法核心思想
K-means聚类算法是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
3. 算法实现步骤
1、首先确定一个k值，即我们希望将数据集经过聚类得到k个集合。
2、从数据集中随机选择k个数据点作为质心。
3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。
4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。
5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。
6、如果新质心和原质心距离变化很大，需要迭代3~5步骤。
4. 算法步骤图解
上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。
K-means术语：
簇：所有数据的点集合，簇中的对象是相似的。
质心：簇中所有点的中心（计算所有点的中心而来）
5. K-means算法优缺点
优点：
1、原理比较简单，实现也是很容易，收敛速度快。
2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
3、主要需要调参的参数仅仅是簇数k。
缺点：
1、K值需要预先给定，很多情况下K值的估计是非常困难的。
2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
3、对噪音和异常点比较的敏感。用来检测异常值。
4、采用迭代方法，可能只能得到局部的最优解，而无法得到全局的最优解。
dbscan聚类算法是什么？
dbscan聚类算法是基于密度的聚类算法，与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。聚类算法的应用DBScan需要二个参数扫描半径 和最小包含点数。 任选一个未被访问的点开始，找出与其距离在eps之内的所有附近点。如果附近点的数量≥minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问。 然后递归，以相同的方法处理该簇内所有未被标记为已访问的点，从而对簇进行扩展。附近点的数量<minPts，则该点暂时被标记作为噪声点。如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点检测数据库中尚未检查过的对象p。如果p未被处理归为某个簇或者标记为噪声，则检查其邻域，若包含的对象数不小于minPts，建立新簇C，将其中的所有点加入候选集N；对候选集N中所有尚未被处理的对象q，检查其邻域，若至少包含minPts个对象，则将这些对象加入N；如果q未归入任何一个簇，则将q加入C。
dbscan聚类算法是什么？
DBSCAN是基于密度空间的聚类算法，与KMeans算法不同，它不需要确定聚类的数量，而是基于数据推测聚类的数目，它能够针对任意形状产生聚类。DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。 DBSCAN算法需要首先确定两个参数：1、epsilon：在一个点周围邻近区域的半径。2、minPts：邻近区域内至少包含点的个数。通常根据以上两个参数，结合epsilon-neighborhood的特征，可以把样本中的点分成核点、边缘点、离群点三类。
DBSCAN聚类算法
DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的 密度聚类算法 ，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现 任意形状的空间聚类 。
该算法利用基于密度的聚类的概念，即要求聚类空间中的一定区域内所包含对象（点或其他空间对象）的数目不小于某一给定阈值。过滤低密度区域，发现稠密度样本点。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。
DBSCAN密度定义：DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数 (ϵ, MinPts) 用来描述邻域的样本分布紧密程度。其中， ϵ 描述了某一样本的邻域距离阈值， MinPts 描述了某一样本的距离为ϵ的邻域中样本个数的阈值。
从上图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。
由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。
1、DBSCAN发现簇的过程
初始，给定数据集D中所有对象都被标记为“unvisited”，DBSCAN随机选择一个未访问的对象p，标记p为“visited”，并检查p的 ϵ- 领域是否至少包含MinPts个对象。如果不是，则p被标记为噪声点。否则为p创建一个新的簇C，并且把p的 ϵ- 领域中所有对象都放在候选集合N中。DBSCAN迭代地把N中不属于其他簇的对象添加到C中。在此过程中，对应N中标记为“unvisited”的对象 P' ,DBSCAN把它标记为“visited”，并且检查它的 ϵ- 领域，如果 P' 的 ϵ- 领域至少包含MinPts个对象，则P' 的 ϵ- 领域中的对象都被添加到N中。DBSCAN继续添加对象到C，直到C不能扩展，即直到N为空。此时簇C完成生成，输出。
为了找到下一个簇，DBSCAN从剩下的对象中随机选择一个未访问过的对象。聚类过程继续，直到所有对象都被访问。
还需考虑三个问题：
第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。DBSCAN算法很容易检测异常点。
第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。
第三种问题，某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。
2、DBSCAN算法流程
优点：
和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，对数据集中的异常点不敏感。一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
缺点：
1、如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2、调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。一般这两个参数的确定靠经验值。如果觉得经验值聚类的结果不满意，可以适当调整ϵ和MinPts的值，经过多次迭代计算对比，选择最合适的参数值。如果MinPts不变，ϵ取得值过大，会导致大多数点都聚到同一个簇中，ϵ过小，会导致一个簇的分裂；如果ϵ不变，MinPts的值取得过大，会导致同一个簇中点被标记为离群点，ϵ过小，会导致发现大量的核心点。
3、不适合高维数据，可以先进行降维操作
4、Sklearn中效率很慢，可以先执行数据削减策略
可视化演示的网址
参考文章
刘建平
