奇怪的离散翻译

1、Science 344, 1492 (2014)DOI: 10.1126/science.1242072Clustering by fast search and find of density peaks通过快速搜索和查找密度峰的聚类算法Alex Rodriguez and Alessandro Laio翻译：吴昕炜，201526810422王思远，校对：唐韫摘要：聚类分析的目的是将各种元素以它们的相似性为基础来分类成不同的类别。这种 算法的应用范围从天文到生物信息学，文献计量学和模式识别。基于这样的假设：“类簇中 心被具有较低局部密度的邻居点包围，且与具有更高密度的任何点有相对较大的距离。

2、”我 们提出了一个实现方法。上述的假设构成了一个聚类程序的基础，这个程序中类簇的数量可 以直观的展现出来，离群值（outliers）会被自动发现并且在分析过程中被排除。类簇的识别 不考虑它们的形状和它们所嵌入空间的维度。在多个测试实例中我们证明了该算法的优秀能 力。关键词：无正文：聚类算法试图将不同元素根据它们的相似性分类成不同类别或者簇。已经有一些不同的 聚类算法被提出，但是在类簇的定义上没有达成一致。在K-均值算法和K-中心点算法中， 簇是以到聚类中心的一小段距离为特征的数据组。对于一个目标函数，典型的像“一组假定 的聚类中心的距离的总和”，会在找到最佳聚类中心候选前一直被优化。但是，因为

3、一个数 据点总是被分配到最近的中心，这些方法不能用来检测非球形簇。在基于状态分布的算法中， 人们试图以预定义的概率分布函数的组合再现观测到的数据点的实现;这些方法的精确度取 决于来表示数据的试验概率的能力。具有任意形状的簇通过局域数据点的局部密度的方法可以轻松的检测到。在用到噪点 （DBSCAN聚类算法）的基于密度的空间聚类算法的应用中，先要选择一个密度阈值，然后 将密度小于阈值的区域的点标记为噪点来舍弃这些点，并分配到不同的不与高于阈值的区域 相连的簇中。（discards as noise the points in regions with densities lower than th

4、is threshold, and assigns to different clusters disconnected regions of high density,）但是，选择的合适的阈值可以 是平凡的，一个缺陷点不会在均值偏移聚类法中被展现出来。（choosing an appropriatethreshold can be nontrivial, a drawback not present in the mean-shift clustering method）在这种算 法下，一个簇被定义为一组汇聚到相同的密度分布函数的局部最大值。（There a cluster is defin

5、ed 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)在这里，我们提出了一种

6、可替代的方法。类似于K-中心点算法，它的基础仅对数据点 之间的距离而言。(it has its basis only in the distance between data points)像 DBSCAN 聚类算 法和均值偏移法，它可以检测非球形集群并且自动找到簇的正确数量。如在均值偏移法中， 聚类中心被定义为数据点的密度局部最大值。然而，不同于均值偏移法，我们的算法不需要 在向量空间中嵌入数据，并明确地最大化每个数据点的密度场。该算法的基础建立在“类簇中心被具有较低局部密度的邻居点包围，且与具有更高密度 的任何点有相对较大的距离”的假设上。对于每一个数据点i，我们计算两个量：它局部密 度p

7、 i和到较高密度点的距离1。这两个量仅仅依靠于假设满足三角不等式的数据点之间的 距离dr数据点i的局部密度p i可以定义为：Pi = X (咆凡)如果x0则x (x) = 1否则x (x) = 0，此处d是截止距离。基本上，p i跟比到点i距离小于 dc的点的数量相等。这个算法仅对在不同的:点钟p i的相对幅度敏感，这意味着，对于大的 数据集，算法的结果相对于dc的选择来说是稳妥的。(The algorithm is sensitive only to the relative magnitude of p i in different points, implying that, for l

8、arge data sets, the results of the analysis are robust with respect to the choice of dc)6 i是通过计算点i到任何其他有较高密度的点最小距离得出的：|& = min (%)对于密度最高的点，我们通常采用6 i=max.(dij)o需要注意仅对于那些局部或全局密度 最大的点，6 i比一般的最近的邻近距离大的多。因此把6 |值异常大的点当做聚类中心。这 种想法是该算法的核心，我们用图1中的简单例子来说明：LThe algprithm irii two dimerisinns, (A) Point distrib

9、utton. Data points are ranlwd in order of decreasing density： (B) Decision graph for ttie data in (A). Different colors oorrespofid to different clusters.图1在两个维度的算法。(A)点分布图。数据点按密度的递减标号。(B) (A)图中数据点的判定图。不同的颜色对应不同的簇。IR理.2. RmUHs; far xynthetic powit diKtrAutimirB. (A) Thedfeiritijlion Irpm which povil

10、 功4心5*1十5The前峰 with bwit iriljnsrtyccrmespond Io a badqvDund uwlorm protHtNlUv 20%. (B and C) rt?nE WElntWons tor saiT0i?E or 4000 and ilOOO poims. rsspeclirelv Hsnts an? coiiMd according to the cktster to which tlwy are afidgiDed. Bladk purrts bwog 汩 tile duster halos. D nd ) The DMTesfBndrig g招ion

11、 grapti&, wrth the caen 站脉 蛇 或皿 (F) The，祀财I d ipc*岷 swwsHe itic got顽 duller as a hndcii the sanipte 5a财on Eg tjwrs the sferrwi 5M M 日衅 imotl图2合成点分布的结果（A）由点分布得出的概率分布已经在图上画出。最低密度的区域对应着全图 20%的均匀概率（The regions with lowest intensity correspond to a background uniform probability of 20%）（B和C）分别有4000个和1000

12、个点的样本的点分布图。点根 据它们被分配的簇着色。黑色的点属于簇光晕。（D和E）根据簇着色中心的对应的判定图。（F）被分配到错误的簇的点的分数关于样品尺度的函数。误差棒形线表示平均值的标准误 差。图1A展示了 28个点嵌入在一个两位空间中的情况。我们发现密度极大值是在被我们 确定为聚类中心的点1和10。图1B展现了每个点的0 i的值是关于p i的函数；我们将这样 的图像叫做判断图。（Figure 1B shows the plot of d as a function of r for each point; we will call this representation the decis

13、ion graph.）点9和10的p值很相似，但是它们的0值却不同：点 9属于点1的簇，并有非常靠近它的一些p值更高的其他的点而离点10最近的有比它更高 密度的近邻点属于其他簇。因此，跟预期的一样，唯一0值大且p值比较大的点就是聚类中 心。因为点26,27和28是孤立的，它们具有相对较高的0值和低的p值；它们可以看做由 单个点组成的簇，即离群值。（outliers）发现聚类中心后，剩下的每一个点就作为最近较高密度点被分配给相同的簇。跟其他的 聚类算法把一个目标函数反复的优化不同，簇的分配在一个步骤中进行。在聚类算法中，定量测定分配的可靠性常常是很有用的。在一个基于函数优化的方法中， 它在收敛部

14、分的值同样是一个自然质量的量（its value at convergence is also a natural quality measure）在像DBSCAN的算法中，一般考虑密度在阈值之上的可靠的点，这样 得出的结果可能是低密度的簇，像这些在图2E中的簇就被归类为噪点了。在我们的算法中， 我们不引入发现噪点就截止的方法（we do not introduce a noise-signal cutoff.）相反，我们 先找到每个簇被定义为一组分配给这个簇的点但是在其他簇的数据点的距离dc之内的边界 区域。然后我们发现，对于每一个簇，最高密度的点包含在它的边界区域内。我们用p b表 示其密

15、度。这个簇中密度大于p b的点可以认为是簇芯的一部分（鲁棒分配）（robustassignation) o其他的可以认为是簇光晕的一部分(适合当做噪点处理)(suitable to beconsidered as noise)为了对我们的程序进行基准测试，让我们先考虑如图2所示的测试案例。数据点是根据 非球形和强烈重叠峰的概率分布绘制的(图2A)；对应于最大值的概率值几乎是不同的顺序 的幅度(the probability values corresponding to the maxima differ by almost an order of magnitude.)在图2B和C中，分别有

16、4000和1000个点根据图2A的分布而绘制。在相应的 判断图中(图2 D和E)，我们观察到只有五个点具有较大的0值和相当大的密度。这些点 在途中用大的实心圆圈表示，并对应着聚类中心。在中心选定后，每个点或者被分配给一个 簇或者被分配给一个光晕。这个算法会捕获概率峰的位置和形状，甚至可以是对应于非常不 同的密度和非球形的峰(图2C中蓝色和绿色的光点)而且被分配给对应的通过图2A的概 率分布的视觉检查得到的区域的光晕的点不会被分配给任何峰区(Moreover, points assigned to the halo correspond to regions that by visual ins

17、pection of the probability distribution in Fig. 2A would not be assigned to any peak.)很可能有问题为了更加定量地演示程序的鲁棒性，我们把图2A中1000个点的分布当做簇分配在这 个样本上拥有的一个参考来演绎算法(we performed the analysis by drawing 10,000 points from the distribution in Fig. 2A, considering as a reference the cluster assignment obtained on that

18、 sample.)然后我们通过仅保留各个点的分数获得了还原样本，并对每个还原样本独立的进 彳亍簇分配。(We then obtained reduced samples by retaining only a fraction of points and performed cluster assignment for each reduced sample independently) 如图 2F 所示，作为还原 样本大小的函数，分配给簇的点的分数跟分配给参考的不一样(Figure 2F shows, as a function of the size of the reduced samp

19、le,the fraction of points assigned to a cluster different than the one they were assigned to in the reference case.)即使对于1000个点的小型样本来说，误分类点的 比例仍远低于1%o对于图2B中的数据，即使改变dc的值仍得到了相互一致的结果(图S1).作为一个经 验法则，人们可以通过选择dc的值使近邻点的平均数目大约在一个数据组的总点数的1%到 2%。对于由少量的点构成的数据组，p i可能被大统计误差影响。在这样的情况下，通过更 精确的测量来估计密度是更有用的。1Fig. 3.

20、Results for test cases in the literature. Synthetic point distnbutions from (12) (A), (13) (B). (14) (C), and (15) (D).图片3对于文献中测试数据的结果。图（A）, （B）, （C）, （D）的合成点分布。接下来，我们将利用图3所示的测试数据对算法进行基准测试。对于计算只有少数点的 样例的密度，我们采用在引例11中描述的指数内核。在图3A中，我们分析了引例12中的 数据组，得到了媲美原来文章的结果，而在这个引例12中其他常用方法是不可行的（In Fig. 3A, we consi

21、der a data set from （12）, obtaining results comparable to those of the original article, where it was shown that other commonly used methods fail.）在图 3B 中我们分析了一个在引例 13中有15个在数据分布上有高度重叠的样例；我们的算法成功的确定了所述数据组的簇结 构。在图片3C中，我们分析了引例14的火焰测试用例（we consider the test case for the FLAME approach （14）（由成员局部逼近的模糊聚类）

22、，其结果相当于原来的方法。在图4D 展现的最初用来演示基于路径的引例15的谱聚类算法的数据组中，我们的算法正确的找到 了 3个不需要产生连通图的簇。作为对比，在图S3和S4中我们展示了这四个测试样例和 图2中的例子通过K-均值算法得到的簇分布。即使K-均值优化算法采用了正确的K值进行 计算，在大多数情况下，分布结果是不符合视觉直观的。这个方法相对于不会显著影响低于dc的距离测量的变化是具有鲁棒性的，也就是说可 以保持在等式 1 中密度估计值不变（The method is robust with respect to changes in the metric that do not sign

23、ificantly affect the distances below d, that is, that keep the density estimator in Eq.1 unchanged.）显然，等式2中的距离会受到测量变化的影响，但是很容易发现判定图的 结构（尤其是有很大S值的数据点的数量）是对密度大小进行排行的结果，而不是两个原点 之间实际距离的结果。许多实例证明了在图S5中展示的结论。我们的方法值需要测量（或计算）所有数据点对之间的距离，并不需要进行参数化概率 分布（引例8）或者多维密度函数（引例10）。因此，该算法的性能不会受到数据点嵌入空 间的固有维度的影响。在一组分布于2

24、56个维度的16簇的测试数据中（引例16），我们已 经证实该算法可以正确的找到簇的数量并且正确的分配数据点。（图S6）对于一组对三种小 麦种子的7个x射线特征的210个测量数据（引例17）中，该算法正确预测了三个簇的存 在并将97%的分配给簇芯的点正确地分类。（图S7和S8）。我们还将这个算法应用到了 Olivetti面部数据库（引例18）。Olivetti面部数据库是一个 普遍的机器学习算法的基准测试，在没有任何预先的训练的情况下，机器学习算法需要判断 出受试者在数据库中的数目。这个数据集是对我们的算法的一个巨大挑战，因为理想化的簇 的数量（即不同的受试者）与数据集中元素的数量相当（即不同的

25、图像，每个受试者都有 10个）。（namely of different images,10 for each subject）这使得很难可靠的估计密度。两个图像 之间的相似性是这样计算的（引例19）。这个密度是通过高斯核函数令方差d =0.07得到的 c对于这样的一个小数据组，对于密度的估计将不可避免的受到大统计误差的影响。因此，我 们以一个比之前的例子稍加严格的标准将图像分配给簇。图像将被分配给离它最近的有更高 密度图像所在的同一个簇中，除非他们之间的距离比dc还小。其结果是，跟任何其他有较 高密度的图像的距离超过dc的图像都未被分配。在图4中，我们展示了该算法分析了数据 集的第一组100

26、个图像的结果。判断图（图4A）表现了几个不同的密度极大值的存在。不 同于其他的实例，它们确切的数量并不明确，是数据点稀疏性带来的结果之一。按递减顺序 排列公式Y广P p i的结果为我们提供了一个需要选择中心数量的提示。（图AB）（A hint for choosing the number of centers is provided by the plot of A sorted in decreasing order （Fig. 4B）.） plot怎么翻译是个问题。Fig. 4. Cluster analysts of the Olivetti Face Database. (A) Th

27、e decision graph for the first hundred images in the database (18). (B) The value of y, p,& in decreasing order for the data in (A). (C) The performance of the algorithm in recognizing subjects in the full database as a function of the number of clusters: number of subjects recognized as individuals

28、 (black line), number of clusters that include more than one subject (redline), number of subjects split in more than one cluster (green), and number of images assigned to a cluster divided by 10 (purple) (D) Pictorial representation of the cluster assignations for the first 100 images. Faces with t

29、he same color belong to the same cluster, whereas gray images are not assigned to any cluster. Cluster centers are labeled with white circles.图4 Olivet面部数据库的簇分析（A）对于数据集的第一组100个图片的判定图（18）（B） 对于（A）的数据按递减顺序排列的公式y i=p i6 i的值（C）算法对于整个数据库的受试者的辨 别的性能关于簇数量的函数：以个体被识别出来的受试者的数量（黑色线）包含了多个受试 者的簇的数量（红色线）被分割在多个簇的受

30、试者数目（绿色线）除以10后的分配给同一 个簇的图片数量（紫色线）（D）对于第一组100个图片的簇分布的图像展示。具有相同颜色 的脸属于同一个簇，而灰色的图像是没有被分配个任何一个簇的。聚类中心都有白色圆圈标 记。该图显示，根据相对于聚类中心的大定义的数量在次序9之下开始异常的增加。(This graph shows that this quantity that is by definition large for cluster centers, starts growing anomalously below a rank order 9.)因此，我们通过使用9个中心点来执行算法。在图片

31、4D 中，我们用不同的颜色展示了对应于不同受试者的簇，这表明该算法可以在10个受试者中 识别出7个。第八个受试者出现了被分裂在两个不同的簇中的现象。当算法处理完数据库中 400个图像后，我们再一次无法通过判断图来清楚的分辨出簇的数量(图S9)o(When the analysis is performed on all 400 images of the database, the decision graph again does not allow recognizing clearly the number of clusters(fig.S9)不过在图 4C 中，我们展示了通过添加更多

32、 的假定中心，大约有30个受试者就可以被正确识别了。(图S9)当更多的中心包括在内时， 部分受试者的图像就被分在了两个簇里，但是所有的簇仍然保持单一，即仅包括同一个受试 者的图像。(When more centers are included,the images of some of the subjects are split in two clusters, but still all the clusters remain pure,namely include only images of the same subject.)根 据引例20我们还可以计算出正确关联到同一个簇(T tu

33、re)的同一个受试者的图像组的分数 和被错误的分配到同一簇(T false)的不同受试者的图像组的分数(we also computed the fraction of pairs of images of the same subject correctly associated with the same cluster and the fraction of pairs of images of different subjects erroneously assigned to the same cluster)如果在 分配中不在dc中应用截断(即如果有人以一般形式应用我们的算法)(n

34、amely if one applies our algorithmin its general formulation)对于一个42 到50 的中心点，就会得到T ture 68% 和T门1.2%，这个性能堪比国家的最先进的无监督图像分类方法。false最后，我们通过计算300K温度的水中三丙氨酸的分子运动轨迹来对该聚类算法进行基 准测试(21)。在这种情况下，簇将近似对应于动力学盆地(kinetic basins)，即是一个在相 当长时间内稳定、被自由能量屏障分割的系统的一个独立的构象，这个构象在微观时间尺度 上仅仅存在一小段时间。 (clusters will approximately

35、 correspond tokinetic basins, namely independent conformations of the systemthat are stable for a substantial time andseparated by free energy barriers), thatarecrossed only rarely on a microscopic time scale.)我们首先通过基于动 力学矩阵的频谱分析的标准方法分析轨迹(22)，其中频谱的特征值与系统的弛豫时间相关 联。在第七特征值之后出现了一个间隙(图S10)，表明这个系统有八个动力学盆地；与之 相吻合的，我们的算法分析(图S10)产生了八个包含与定义了动力学盆地(22)的构象一 一对应的构象的簇。 (in agreement with that, our cluster analysis (fig. S10) gives rise to eight clusters, including conformations in a one-to-one corresp