论文中的机器学习算法——基于密度峰值的聚类算法

一、前言

    最近有一篇Science上的文章引起了大家的关注，是由Alex Rodriguez和Alessandro Laio发表的《Clustering by fast search and find of density peaks》。网上有人做了一些说明，其实很多时候我在读论文的过程中，也是学到了很多的知识，只是很少将这些内容整理在网上，前段时间我主要写了一些有关机器学习的博文，搭建这样的博客只是记录我的学习过程，伴随着我的成长与进步。     在这个系列中，我会将自己阅读过的论文的主要思想通过我自己的理解拿出来与大家分享，以前读了一些论文没有做好笔记，更多的是现实中一些条件的限制，没有机会和组内的人分享一些学习的心得，遂想在这样的一个平台上与大家一起讨论，也希望这样的过程能够伴随我的进步，促进我的进步。下面还是主要来谈谈论文的主要思想。

二、算法的主要思想思想

    在聚类算法中主要有这样几种：

• 划分的方法，如K-Means
• 层次的方法，如CURE
• 基于密度的方法，如DBSCAN
• 基于网格的方法，如CLIQUE
• 基于模型的方法，主要是一些概率分布

在以往的学习过程中，我只关注过划分的方法，如K-Means(见博文“简单易学的机器学习算法——kMeans”)。     Science上的这篇文章《Clustering by fast search and find of density peaks》主要讲的是一种基于密度的聚类方法，基于密度的聚类方法的主要思想是寻找被低密度区域分离的高密度区域。而在文章中提出的聚类方法(以下称为“Desity Peaks Clusering Algorithm, DPCA”)也同样基于这样的一种假设：对于一个数据集，聚类中心被一些低局部密度的数据点包围，而且这些低局部密度的点距离其他有高局部密度的点的距离都比较大。在这样的模型中，DPCA主要有两个需要计算的量：第一，局部密度；第二，与高密度点之间的距离。

1、局部密度的定义为：

其中，
称为截断距离(Cut-off distance)。这个公式的含义是说找到与第个数据点之间的距离小于截断距离的数据点的个数。

2、与高密度点之间的距离

这个公式的含义是说找到所有比第个数据点的局部密度都大的数据点中，与第个数据点之间的距离的最小值。而对于具有最大密度的数据点，通常取。

3、如何聚类

   对于聚类问题，我们需要回答的是聚类中心是什么，对于每个数据点，如何定义所属的类别。DPCA中将那些具有较大距离且同时具有较大局部密度的点定义为聚类中心。
(图片来源于文章) 如上图B，数据点1和数据点10同时具有相对较高的距离和局部密度，所以是聚类中心。而在图中具有相对较高的距离，但是局部密度却较小的数据点26,27和28称为异常点。对于那些非异常点，如何对他们聚类呢？DPCA采用的是将他们归类到比他们的密度更大的最相近的类中心所属的类别中。到此，整个算法的基本思想解释结束。     对于这样的算法，如何去定义相对较高，作者并没有给出解释，在作者提供的程序和数据中，我做了实验，实验结果如下：
(实验结果)

参考文献：

1、Clustering by fast search and find of density peaks
2、Science上发表的超赞聚类算法 http://www.52ml.net/16296.html 3、Clustering By Fast Search And Find Of Density Peaks http://www.52ml.net/16351.html