奇怪的離散翻譯

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、”我 們提出了一個實現(xiàn)方法。上述的假設構成了一個聚類程序的基礎，這個程序中類簇的數(shù)量可 以直觀的展現(xiàn)出來，離群值（outliers）會被自動發(fā)現(xiàn)并且在分析過程中被排除。類簇的識別 不考慮它們的形狀和它們所嵌入空間的維度。在多個測試實例中我們證明了該算法的優(yōu)秀能 力。關鍵詞：無正文：聚類算法試圖將不同元素根據(jù)它們的相似性分類成不同類別或者簇。已經(jīng)有一些不同的 聚類算法被提出，但是在類簇的定義上沒有達成一致。在K-均值算法和K-中心點算法中， 簇是以到聚類中心的一小段距離為特征的數(shù)據(jù)組。對于一個目標函數(shù)，典型的像“一組假定 的聚類中心的距離的總和”，會在找到最佳聚類中心候選前一直被優(yōu)化。但是，因為

3、一個數(shù) 據(jù)點總是被分配到最近的中心，這些方法不能用來檢測非球形簇。在基于狀態(tài)分布的算法中， 人們試圖以預定義的概率分布函數(shù)的組合再現(xiàn)觀測到的數(shù)據(jù)點的實現(xiàn);這些方法的精確度取 決于來表示數(shù)據(jù)的試驗概率的能力。具有任意形狀的簇通過局域數(shù)據(jù)點的局部密度的方法可以輕松的檢測到。在用到噪點 （DBSCAN聚類算法）的基于密度的空間聚類算法的應用中，先要選擇一個密度閾值，然后 將密度小于閾值的區(qū)域的點標記為噪點來舍棄這些點，并分配到不同的不與高于閾值的區(qū)域 相連的簇中。（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,）但是，選擇的合適的閾值可以 是平凡的，一個缺陷點不會在均值偏移聚類法中被展現(xiàn)出來。（choosing an appropriatethreshold can be nontrivial, a drawback not present in the mean-shift clustering method）在這種算 法下，一個簇被定義為一組匯聚到相同的密度分布函數(shù)的局部最大值。（There a cluster is defin

5、ed as a set of points that converge to the same local maximum of the density distribution function.)這個方法可以用來判斷非球形簇，但是僅僅用來處理通過一組坐標定義的數(shù)據(jù)在 計算上的消耗是很大的(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-中心點算法，它的基礎僅對數(shù)據(jù)點 之間的距離而言。(it has its basis only in the distance between data points)像 DBSCAN 聚類算 法和均值偏移法，它可以檢測非球形集群并且自動找到簇的正確數(shù)量。如在均值偏移法中， 聚類中心被定義為數(shù)據(jù)點的密度局部最大值。然而，不同于均值偏移法，我們的算法不需要 在向量空間中嵌入數(shù)據(jù)，并明確地最大化每個數(shù)據(jù)點的密度場。該算法的基礎建立在“類簇中心被具有較低局部密度的鄰居點包圍，且與具有更高密度 的任何點有相對較大的距離”的假設上。對于每一個數(shù)據(jù)點i，我們計算兩個量：它局部密 度p

7、 i和到較高密度點的距離1。這兩個量僅僅依靠于假設滿足三角不等式的數(shù)據(jù)點之間的 距離dr數(shù)據(jù)點i的局部密度p i可以定義為：Pi = X (咆凡)如果x0則x (x) = 1否則x (x) = 0，此處d是截止距離。基本上，p i跟比到點i距離小于 dc的點的數(shù)量相等。這個算法僅對在不同的:點鐘p i的相對幅度敏感，這意味著，對于大的 數(shù)據(jù)集，算法的結果相對于dc的選擇來說是穩(wěn)妥的。(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)點分布圖。數(shù)據(jù)點按密度的遞減標號。(B) (A)圖中數(shù)據(jù)點的判定圖。不同的顏色對應不同的簇。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）由點分布得出的概率分布已經(jīng)在圖上畫出。最低密度的區(qū)域對應著全圖 20%的均勻概率（The regions with lowest intensity correspond to a background uniform probability of 20%）（B和C）分別有4000個和1000

12、個點的樣本的點分布圖。點根 據(jù)它們被分配的簇著色。黑色的點屬于簇光暈。（D和E）根據(jù)簇著色中心的對應的判定圖。（F）被分配到錯誤的簇的點的分數(shù)關于樣品尺度的函數(shù)。誤差棒形線表示平均值的標準誤 差。圖1A展示了 28個點嵌入在一個兩位空間中的情況。我們發(fā)現(xiàn)密度極大值是在被我們 確定為聚類中心的點1和10。圖1B展現(xiàn)了每個點的0 i的值是關于p i的函數(shù)；我們將這樣 的圖像叫做判斷圖。（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的簇，并有非?？拷囊恍﹑值更高的其他的點而離點10最近的有比它更高 密度的近鄰點屬于其他簇。因此，跟預期的一樣，唯一0值大且p值比較大的點就是聚類中 心。因為點26,27和28是孤立的，它們具有相對較高的0值和低的p值；它們可以看做由 單個點組成的簇，即離群值。（outliers）發(fā)現(xiàn)聚類中心后，剩下的每一個點就作為最近較高密度點被分配給相同的簇。跟其他的 聚類算法把一個目標函數(shù)反復的優(yōu)化不同，簇的分配在一個步驟中進行。在聚類算法中，定量測定分配的可靠性常常是很有用的。在一個基于函數(shù)優(yōu)化的方法中， 它在收斂部

14、分的值同樣是一個自然質量的量（its value at convergence is also a natural quality measure）在像DBSCAN的算法中，一般考慮密度在閾值之上的可靠的點，這樣 得出的結果可能是低密度的簇，像這些在圖2E中的簇就被歸類為噪點了。在我們的算法中， 我們不引入發(fā)現(xiàn)噪點就截止的方法（we do not introduce a noise-signal cutoff.）相反，我們 先找到每個簇被定義為一組分配給這個簇的點但是在其他簇的數(shù)據(jù)點的距離dc之內的邊界 區(qū)域。然后我們發(fā)現(xiàn)，對于每一個簇，最高密度的點包含在它的邊界區(qū)域內。我們用p b表 示其密

15、度。這個簇中密度大于p b的點可以認為是簇芯的一部分（魯棒分配）（robustassignation) o其他的可以認為是簇光暈的一部分(適合當做噪點處理)(suitable to beconsidered as noise)為了對我們的程序進行基準測試，讓我們先考慮如圖2所示的測試案例。數(shù)據(jù)點是根據(jù) 非球形和強烈重疊峰的概率分布繪制的(圖2A)；對應于最大值的概率值幾乎是不同的順序 的幅度(the probability values corresponding to the maxima differ by almost an order of magnitude.)在圖2B和C中，分別有

16、4000和1000個點根據(jù)圖2A的分布而繪制。在相應的 判斷圖中(圖2 D和E)，我們觀察到只有五個點具有較大的0值和相當大的密度。這些點 在途中用大的實心圓圈表示，并對應著聚類中心。在中心選定后，每個點或者被分配給一個 簇或者被分配給一個光暈。這個算法會捕獲概率峰的位置和形狀，甚至可以是對應于非常不 同的密度和非球形的峰(圖2C中藍色和綠色的光點)而且被分配給對應的通過圖2A的概 率分布的視覺檢查得到的區(qū)域的光暈的點不會被分配給任何峰區(qū)(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.)然后我們通過僅保留各個點的分數(shù)獲得了還原樣本，并對每個還原樣本獨立的進 彳亍簇分配。(We then obtained reduced samples by retaining only a fraction of points and performed cluster assignment for each reduced sample independently) 如圖 2F 所示，作為還原 樣本大小的函數(shù)，分配給簇的點的分數(shù)跟分配給參考的不一樣(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中的數(shù)據(jù)，即使改變dc的值仍得到了相互一致的結果(圖S1).作為一個經(jīng) 驗法則，人們可以通過選擇dc的值使近鄰點的平均數(shù)目大約在一個數(shù)據(jù)組的總點數(shù)的1%到 2%。對于由少量的點構成的數(shù)據(jù)組，p i可能被大統(tǒng)計誤差影響。在這樣的情況下，通過更 精確的測量來估計密度是更有用的。1Fig. 3.

20、Results for test cases in the literature. Synthetic point distnbutions from (12) (A), (13) (B). (14) (C), and (15) (D).圖片3對于文獻中測試數(shù)據(jù)的結果。圖（A）, （B）, （C）, （D）的合成點分布。接下來，我們將利用圖3所示的測試數(shù)據(jù)對算法進行基準測試。對于計算只有少數(shù)點的 樣例的密度，我們采用在引例11中描述的指數(shù)內核。在圖3A中，我們分析了引例12中的 數(shù)據(jù)組，得到了媲美原來文章的結果，而在這個引例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個在數(shù)據(jù)分布上有高度重疊的樣例；我們的算法成功的確定了所述數(shù)據(jù)組的簇結 構。在圖片3C中，我們分析了引例14的火焰測試用例（we consider the test case for the FLAME approach （14）（由成員局部逼近的模糊聚類）

22、，其結果相當于原來的方法。在圖4D 展現(xiàn)的最初用來演示基于路徑的引例15的譜聚類算法的數(shù)據(jù)組中，我們的算法正確的找到 了 3個不需要產(chǎn)生連通圖的簇。作為對比，在圖S3和S4中我們展示了這四個測試樣例和 圖2中的例子通過K-均值算法得到的簇分布。即使K-均值優(yōu)化算法采用了正確的K值進行 計算，在大多數(shù)情況下，分布結果是不符合視覺直觀的。這個方法相對于不會顯著影響低于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中的距離會受到測量變化的影響，但是很容易發(fā)現(xiàn)判定圖的 結構（尤其是有很大S值的數(shù)據(jù)點的數(shù)量）是對密度大小進行排行的結果，而不是兩個原點 之間實際距離的結果。許多實例證明了在圖S5中展示的結論。我們的方法值需要測量（或計算）所有數(shù)據(jù)點對之間的距離，并不需要進行參數(shù)化概率 分布（引例8）或者多維密度函數(shù)（引例10）。因此，該算法的性能不會受到數(shù)據(jù)點嵌入空 間的固有維度的影響。在一組分布于2

24、56個維度的16簇的測試數(shù)據(jù)中（引例16），我們已 經(jīng)證實該算法可以正確的找到簇的數(shù)量并且正確的分配數(shù)據(jù)點。（圖S6）對于一組對三種小 麥種子的7個x射線特征的210個測量數(shù)據(jù)（引例17）中，該算法正確預測了三個簇的存 在并將97%的分配給簇芯的點正確地分類。（圖S7和S8）。我們還將這個算法應用到了 Olivetti面部數(shù)據(jù)庫（引例18）。Olivetti面部數(shù)據(jù)庫是一個 普遍的機器學習算法的基準測試，在沒有任何預先的訓練的情況下，機器學習算法需要判斷 出受試者在數(shù)據(jù)庫中的數(shù)目。這個數(shù)據(jù)集是對我們的算法的一個巨大挑戰(zhàn)，因為理想化的簇 的數(shù)量（即不同的受試者）與數(shù)據(jù)集中元素的數(shù)量相當（即不同的

25、圖像，每個受試者都有 10個）。（namely of different images,10 for each subject）這使得很難可靠的估計密度。兩個圖像 之間的相似性是這樣計算的（引例19）。這個密度是通過高斯核函數(shù)令方差d =0.07得到的 c對于這樣的一個小數(shù)據(jù)組，對于密度的估計將不可避免的受到大統(tǒng)計誤差的影響。因此，我 們以一個比之前的例子稍加嚴格的標準將圖像分配給簇。圖像將被分配給離它最近的有更高 密度圖像所在的同一個簇中，除非他們之間的距離比dc還小。其結果是，跟任何其他有較 高密度的圖像的距離超過dc的圖像都未被分配。在圖4中，我們展示了該算法分析了數(shù)據(jù) 集的第一組100

26、個圖像的結果。判斷圖（圖4A）表現(xiàn)了幾個不同的密度極大值的存在。不 同于其他的實例，它們確切的數(shù)量并不明確，是數(shù)據(jù)點稀疏性帶來的結果之一。按遞減順序 排列公式Y廣P p i的結果為我們提供了一個需要選擇中心數(shù)量的提示。（圖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面部數(shù)據(jù)庫的簇分析（A）對于數(shù)據(jù)集的第一組100個圖片的判定圖（18）（B） 對于（A）的數(shù)據(jù)按遞減順序排列的公式y(tǒng) i=p i6 i的值（C）算法對于整個數(shù)據(jù)庫的受試者的辨 別的性能關于簇數(shù)量的函數(shù)：以個體被識別出來的受試者的數(shù)量（黑色線）包含了多個受試 者的簇的數(shù)量（紅色線）被分割在多個簇的受

30、試者數(shù)目（綠色線）除以10后的分配給同一 個簇的圖片數(shù)量（紫色線）（D）對于第一組100個圖片的簇分布的圖像展示。具有相同顏色 的臉屬于同一個簇，而灰色的圖像是沒有被分配個任何一個簇的。聚類中心都有白色圓圈標 記。該圖顯示，根據(jù)相對于聚類中心的大定義的數(shù)量在次序9之下開始異常的增加。(This graph shows that this quantity that is by definition large for cluster centers, starts growing anomalously below a rank order 9.)因此，我們通過使用9個中心點來執(zhí)行算法。在圖片

31、4D 中，我們用不同的顏色展示了對應于不同受試者的簇，這表明該算法可以在10個受試者中 識別出7個。第八個受試者出現(xiàn)了被分裂在兩個不同的簇中的現(xiàn)象。當算法處理完數(shù)據(jù)庫中 400個圖像后，我們再一次無法通過判斷圖來清楚的分辨出簇的數(shù)量(圖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.)根 據(jù)引例20我們還可以計算出正確關聯(lián)到同一個簇(T tu

33、re)的同一個受試者的圖像組的分數(shù) 和被錯誤的分配到同一簇(T false)的不同受試者的圖像組的分數(shù)(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%，這個性能堪比國家的最先進的無監(jiān)督圖像分類方法。false最后，我們通過計算300K溫度的水中三丙氨酸的分子運動軌跡來對該聚類算法進行基 準測試(21)。在這種情況下，簇將近似對應于動力學盆地(kinetic basins)，即是一個在相 當長時間內穩(wěn)定、被自由能量屏障分割的系統(tǒng)的一個獨立的構象，這個構象在微觀時間尺度 上僅僅存在一小段時間。 (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)，其中頻譜的特征值與系統(tǒng)的弛豫時間相關 聯(lián)。在第七特征值之后出現(xiàn)了一個間隙(圖S10)，表明這個系統(tǒng)有八個動力學盆地；與之 相吻合的，我們的算法分析(圖S10)產(chǎn)生了八個包含與定義了動力學盆地(22)的構象一 一對應的構象的簇。 (in agreement with that, our cluster analysis (fig. S10) gives rise to eight clusters, including conformations in a one-to-one corresp