奇怪的离散翻译.docx

Science 344, 1492 (2014)DOI: 10.1126/science.1242072Clustering by fast search and find of density peaks通过快速有哪些信誉好的足球投注网站和查找密度峰的聚类算法Alex Rodriguez and Alessandro Laio翻译：吴昕炜， 201526810422王思远，校对：唐韫摘要：聚类分析的目的是将各种元素以它们的相似性为基础来分类成不同的类别。这种算法的应用范围从天文到生物信息学，文献计量学和模式识别。基于这样的假设：“类簇中心被具有较低局部密度的邻居点包围，且与具有更高密度的任何点有相对较大的距离。”我们提出了一个实现方法。上述的假设构成了一个聚类程序的基础，这个程序中类簇的数量可以直观的展现出来，离群值（outliers）会被自动发现并且在分析过程中被排除。类簇的识别不考虑它们的形状和它们所嵌入空间的维度。在多个测试实例中我们证明了该算法的优秀能力。关键词：无正文：聚类算法试图将不同元素根据它们的相似性分类成不同类别或者簇。已经有一些不同的聚类算法被提出，但是在类簇的定义上没有达成一致。在K-均值算法和K-中心点算法中，簇是以到聚类中心的一小段距离为特征的数据组。对于一个目标函数，典型的像“一组假定的聚类中心的距离的总和”，会在找到最佳聚类中心候选前一直被优化。但是，因为一个数据点总是被分配到最近的中心，这些方法不能用来检测非球形簇。在基于状态分布的算法中，人们试图以预定义的概率分布函数的组合再现观测到的数据点的实现；这些方法的精确度取决于来表示数据的试验概率的能力。具有任意形状的簇通过局域数据点的局部密度的方法可以轻松的检测到。在用到噪点（DBSCAN聚类算法)的基于密度的空间聚类算法的应用中，先要选择一个密度阈值，然后将密度小于阈值的区域的点标记为噪点来舍弃这些点，并分配到不同的不与高于阈值的区域相连的簇中。（discards as noise the points in regions with densities lower than this threshold, and assigns to different clusters disconnected regions of high density.）但是，选择的合适的阈值可以是平凡的，一个缺陷点不会在均值偏移聚类法中被展现出来。（choosing an appropriate threshold can be nontrivial, a drawback not present in the mean-shift clustering method）在这种算法下，一个簇被定义为一组汇聚到相同的密度分布函数的局部最大值。（There a cluster is defined as a set of points that converge to the same local maximum of the density distribution function.）这个方法可以用来判断非球形簇，但是仅仅用来处理通过一组坐标定义的数据在计算上的消耗是很大的。（This method allows the finding of nonspherical clusters but works only for data defined by a set of coordinates and is computationally costly）在这里，我们提出了一种可替代的方法。类似于K-中心点算法，它的基础仅对数据点之间的距离而言。（it has its basis only in the distance between data points）像DBSCAN聚类算法和均值偏移法，它可以检测非球形集群并且自动找到簇的正确数量。如在均值偏移法中，聚类中心被定义为数据点的密度局部最大值。然而，不同于均值偏移法，我们的算法不需要在向量空间中嵌入数据，并明确地最大化每个数据点的密度场。该算法的基础建立在“类簇中心被具有较低局部密度的邻居点包围，且与具有更高密度的任何点有相对较大的距离”的假设上。对于每一个数据点i，我们计算两个量：它局部密度ρi和到较高密度点的距离di。这两个量仅仅依靠于假设满足三角不等式的数据点之间的距离dij。数据点i的局部密度ρi可以定义为：如果x0则否则，此处dc是截止距离。基本上，ρi跟比到点i距离小于dc的点的数量相等。这个算法仅对在不同的点钟ρi的相对幅度敏感，这意味着，对于大的数据集，算法的结果相对于dc的选择来说是稳妥的。（The algorithm is sensitive only to the relative magnitude of ρ