文献学习(part33)--Clustering by fast search and find of density peaks

文献学习(part33)--Clustering by fast search and find of density peaks

学习笔记，仅供参考，有错必究

文章目录

​​Clustering by fast search and find of density peaks​​

​​摘要​​​​简介​​​​算法​​​​实验(略)​​

Clustering by fast search and find of density peaks

摘要

聚类分析旨在根据相似性将元素分类。它的应用范围从天文学到生物信息学、文献计量学和模式识别。我们提出了一种基于聚类中心的方法，其特点是聚类中心的密度高于其邻居，并且与密度较高的点之间的距离相对较大。这种思想形成了聚类过程的基础，在该过程中，聚类的数量被直观地体现，异常被自动发现并从分析中排除，并且簇被识别而不管它们的形状和它们嵌入的空间的维度如何。我们在几个测试案例中展示了算法的能力。

简介

聚类算法试图根据元素的相似性将其分类或聚类。已经提出了几种不同的聚类策略(1)，但甚至对聚类的定义也没有达成共识。在K-means(2)和K-medoids(3)方法中，聚类是以与聚类中心距离较小为特征的数据组。一个目标函数，通常是到优化（3-6）一组假定簇中心的距离之和，直到找到最好的簇中心候选者。然而，由于一个数据点总是被分配到最近的中心，这些方法无法检测非球形簇（7）。在基于分布的算法中，人们试图将观察到的数据点的实现重现为预定义概率分布函数的混合(8)，这种方法的准确性取决于试验概率表示数据的能力。

基于数据点的局部密度的方法可以很容易地检测到具有任意形状的聚类。在基于密度的带噪声应用空间聚类(DBSCAN)(9)中，人们选择一个密度阈值，将密度低于该阈值的区域中的点作为噪声丢弃，并将高密度的不相连区域分配给不同的聚类。然而，选择一个合适的阈值可能是不平凡的，这个缺点在平均移动聚类方法中并不存在(10，11)。聚类被定义为一组点的集合，这些点收敛于密度分布函数的相同局部最大值。这种方法可以找到非球形聚类，但只适用于由一组坐标定义的数据，而且计算成本很高。

在这里，我们提出了一种替代方法。与K-medoids方法类似，它基于数据点之间的距离。与DBSCAN和均值漂移法类似，它能够检测非球面聚类，并自动找到正确的聚类数量。与均值移动法类似，簇中心被定义为数据点密度的局部最大值。然而，与均值移动法不同，我们的程序不需要将数据嵌入矢量空间，也不需要明确地最大化每个数据点的密度场。

算法

这是算法的核心，图1中的简单例子就可以说明这点：

在找到簇中心之后，剩余的每个点都被分配到密度更高的最近的同一簇中。与其他目标函数迭代优化的聚类算法(2,8)不同，聚类分配只需一步完成。

在聚类分析中，定量地衡量一个赋值的可靠性往往是有用的。在基于函数优化的方法中(2，8)，其收敛时的值也是一种自然的质量测量。

在像DBSCAN(9)这样的方法中，人们会考虑密度值高于阈值的可靠点，这可能会导致低密度聚类，如图2E中的聚类，被归类为噪声。在我们的算法中，我们并没有引入噪声信号的截止值。

为了对我们的过程进行基准测试，让我们首先考虑图2中的测试用例。数据点是根据非球形和强重叠峰的概率分布绘制的(图2A)；与最大值相对应的概率值几乎相差一个数量级。

为了更定量地证明该过程的稳健性，我们从图2A的分布中绘制了10,000个点进行分析，并将该样本获得的聚类分配作为参考。然后我们通过保留一小部分点来获得约简样本，并对每个约简样本独立进行聚类分配。图2F显示，作为缩小样本大小的函数，分配给一个与参考情况下分配给一个不同的聚类的点的分数。即使是包含1000个点的小样本，错误分类点的比例也远低于1%。

实验(略)

接下来，我们在图3所示的测试用例上对算法进行基准测试。为了计算点较少情况下的密度，我们采用了(11)中描述的指数核。在图3A中，我们考虑了来自(12)的数据集，得到的结果与原始文章的结果相当，其中表明其他常用的方法都失败了。

在图3B中，我们考虑了一个取自(13)的15个数据分布高度重合的簇的例子；我们的算法成功地确定了数据集的簇结构。

在图3C中，我们考虑了FLAME方法(14)的测试用例，结果与原始方法相当。

在图3D所示的最初引入的数据集中，我们的算法正确地找到了三个簇，而不需要生成连接图。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。