騰訊高級工程師教你玩轉聚類

最新 05-24

何為聚類？聚類是使同一類的相似度儘可能大，不同類之間的相似度儘可能小的行為。

目前聚類的演算法按照原理有這幾種：基於劃分的聚類演算法，基於層次的聚類演算法，基於密度的聚類演算法，基於網格的聚類演算法等等。

基於劃分的聚類演算法的代表是k-means。K-means的缺點是必須先指定劃分類的數量。

基於層次聚類演算法的代表是BIRCH演算法。BIRCH演算法的缺點也很明顯，由於要每一層都要所有點兩兩之間的距離，所以計算量很大。一些奇異值（躁點）會對結果產生很大影響。

何為密度？密度是衡量一個空間內點的稠密程度的指標。以平面空間為例，我們可以設定一個小的範圍，比如一個半徑為1的小圓的面積作為單位面積。這個所謂的單位面積上包含的點的個數，就可以作為一個稠密的指標。高於這個值算為稠密，低於這個值算為稀疏。很顯然，不夠稠密的點，都可以歸為躁點。所以可以看出，密度的概念就是空間中相似度表現的一種局部描述。局部表現可以按照某種規則任意方向擴充到整個空間，就像經典遊戲貪吃蛇那般。從而發現任意類型的類別。所以基於密度的演算法可以很好的在其劃分聚類和層次聚類之間取得平衡：無需指定分類的數量，性能又有很大提升，還可以發現任何形狀的類和去除躁點。

本文基於密度的聚類原理介紹兩個演算法：

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

OPTICS(Ordering Points To Identify the Clustering Structure)。

DBSCAN演算法

1.基礎概念

DBSCAN的介紹，先從幾個概念開始。

ε-鄰域：以對象O為中心，ε為半徑的空間，其中ε>0, 成為對象O的ε-鄰域。

MinPts：對象鄰域中的所有需要聚類的對象的個數，學名叫領域密度閾值，俗稱閾值。

核心對象：所有對象中滿足ε-鄰域內，對象數量至少包括MinPts個的對象。

直接密度可達：如果對象q在對象m的ε-鄰域內，則p是從m直接密度可達的。

密度可達：對象p可以通過直接密度可達到ε-鄰域內的m，而對象m又可以通過直接密度可達到ε-鄰域內的q，即當直接密度可以傳遞時，對象p和對象q為密度可達（間接密度可達）。通俗來講，如果兩個對象之間有幾個點可以以直接密度可達的方式串聯起來，那麼這兩個點就是密度可達的（間接）。

密度相連：如果存在對象qεD，使得對象p1和p2都是從q關於和MinPts密度可達的，則稱P1，p2是關於ε和MinPts密度相連的。

案例：

假定MinPts=3，由上圖可看出m,p,o,r 是核心對象，因為他們ε-鄰域內包含3個或3個以上的對象。

對象q是從m直接密度可達的，對象m從p直接密度可達的。

對象q是從p（間接）密度可達的，因為q從m直接密度可達，m從p直接密度可達；對象r也是從o密度可達的，對象s是從o密度可達的。

s是從o密度可達的，而r是從o密度可達的，他們三者都是互相密度可達的，所以s,r是密度相連的。

2.核心要點

以平面二維空間為例，可以使用歐式距離來表述點與點之間的密度衡量，用歐式距離的判定來識別點與點之間能不能聚合在一起。

從基礎概念中可以看到DBSCAN的輸入參數有兩個值，即半徑ε表示以給定點對象點P為中心的圓形鄰域的範圍，和密度閾值MinPts表示以某一點P為中心的鄰域內要求最少擁有的點的數量。

演算法核心思想是使用小範圍的圓形區域劃分出足夠稠密的點的集合，然後將多個圓形區域以某種更適合集合的規則連接到一起形成聚合，以達成聚類的功能。雖然ε-鄰域區域以圓形的存在，但由於多個ε-鄰域圓形區域可以以任意方向和其他ε-鄰域鄰域組合到一起，所以最終可以形成的集合簇並不會是圓形的，而是任意形狀的簇(類)。

基於密度的聚類演算法，因為設定了密度和核心對象的概念，任何非核心對象的點，都無法和其他點組成足夠稠密的集合，所以這些非核心對象就是躁點，因此基於密度的聚類演算法相較於劃分聚類來說，還可以達到去噪點的效果。

3.演算法流程

4.參數選定

至此，知曉了DBSCAN的演算法概念和核心原理以及演算法流程後，嘗試寫代碼進行聚類的試點。事先準備的一些數據，設置EPS(半徑ε)=102，MINPTS=50，聚類情況如下，從直觀上看黃色的聚類似乎存在問題。

於是調整參數，EPS=100，MINPTS=50。得到了如下結果，相對看似合理了。

由此可見，參數的不同，會讓聚類結果的效果和形態呈現很不一樣。那麼問題就是，參數是沒有限制可以調整的，如何更快更好的找到適合的參數值呢，規避不停的調整嘗試呢？

接下來提到另外一個概念和方法：K距離和K距離選擇法，用來決策半徑ε和其圓形範圍內需要包含的MinPts對象數。

5.K距離選擇法

K距離：給定數據集P=，對於任意點p(i)，計算點p(i)到集合P的子集S=中所有點的距離，距離按照從小到大的順序排序，假設排序後的距離集合為D=，則d(k)就被稱為k-距離；即所謂k-距離就是點p(i)到其集合內其他所有點之間的距離第k遠的點的一個距離值。

我們可以對聚類集合中每個點p(i)都計算他們的k-距離，最後可以得到所有點的k-距離集合E=。

K距離選擇參數法：所有點K距離計算完畢後，將集合E按升序排序，連成曲線，如下圖所示。在曲線急劇變化的開始點的位置所對應的K距離值可以選取作為半徑ε的值；而此時這一個點的K值就是MinPTS，因為MinPTS表示的是距離核心點在半徑範圍內至少要包含的點的個數，第K遠的距離自然就是MinPTS了。

利用K距離選擇初始的輸入參數，可以讓我們較為有效的選定一個可能的最佳參數的大概位置，但其實本質上這個演算法要篩選到可靠的K值和K距離值，也需要不斷的變化形成集合E的曲線，選擇變化梯隊較大的曲線所在的變化起點位置，因此也需要變化K的選擇來調整修改得到。

OPTICS演算法

從上一節的DBSCAN演算法可以看到，如果半徑ε和MinPTS的值選擇的不同，會造成聚類結果差異很大。例如下圖，你認為圖中可以聚類出多少簇呢？3個？5個？說明DBSCAN演算法對於輸入參數是很敏感的。

OPTICS是對DBSCAN的一個擴展演算法。該演算法可以讓演算法對半徑ε不再敏感。只要確定MinPTS的值，半徑ε的輕微變化，並不會影響聚類結果。

1.新增概念：核心距離、可達距離

核心距離：對於集合M而言，假設讓其中x點作為核心，找到以x點為圓心，且剛好滿足最小鄰點數MinPTS的最外層的一個點為 x"，則x點到 x"點的距離稱為核心距離，其他情況為正無窮

可達距離：對於核心點 x 的鄰點 x1、x2、…xn 而言，如果他們到點x的距離大於點x』的核心距離，則其可達距離為該點到點x的實際距離；如果他們到點x的距離核心距離小於點x』的核心距離的話，則其可達距離就是點x的核心距離，即在x』以內的點到x的距離都以此核心距離來記錄。

舉例，下圖中假設MinPTS=3，半徑是ε。那麼P點的核心距離是d(1,P)，點2的可達距離是d(1,P)，點3的可達距離也是d(1,P)，點4的可達距離則是d(4,P)的距離。

2.演算法流程

D: 待聚類的集合。

Q: 有序隊列，元素按照可達距離排序，可達距離最小的在隊首。

O: 結果隊列，最後輸出結果的點集的有序隊列。

得到結果隊列後，使用如下演算法得到最終的聚類結果：

3.實例演示

假設存在以下點集：

a=; b=; c=;d=; e=; f=;g=;h=;i=;j=;k=;l=;//孤立點m=;n=;o=;p=;q=;

設定ε=2 MinPts=4 使用OPTICS演算法，依次輸出的結果隊列為下圖：

所以從圖中可以看出，結果隊列分三次輸出了三組值：

第一組： a，e，b，d，c，f

第二組： g，j，k，i，h

第三組： n，q，o，m

4. OPTICS為何對ε不敏感？

從實例演示中，會有兩個疑問：

1. 為什麼說OPTICS演算法對於ε不敏感，在演算法參數上還要輸入ε呢？

因為基於密度的聚類演算法需要確定哪些點是核心點，哪些是躁點。所以為了這個目的，需要有個半徑 ε。所以ε是必須給定的。

2. 為什麼當ε發生了變化，根據輸出隊列O還是可以得到新的分類？

在OPTICS演算法中MinPTS並沒有發生變化，雖然給定了ε，但最終得到的不是直接的分類結果，而是在這個ε和MinPts下的有序隊列，以及所有點的核心距離和可達距離。我們使用另外一個小的演算法從隊列中得到分類。簡而言之：OPTICS演算法通過給定一個ε值和MinPts，計算出來的所有小於等於ε的情況的特徵，最後利用這些特徵，做一些簡要的邏輯計算就可以得到分類。在對結果隊列O的處理中，判斷核心距離≤ε』這實則已經是在判斷P是否為新半徑ε』下的核心點了。所以ε發生了變化，核心點即使變化了也沒關係，在O的處理中已經照顧到了，不是核心點的元素一定會被認定為躁點。保證了分類的正確性。

綜上所述，OPTICS可以在MinPts固定的前提下，對於任意的ε』 (其中ε』小於等於ε)都可以直接經過簡單的計算得到新的聚類結果。

兩種密度演算法異同

問題1：DBSCAN和OPTICS演算法效率哪個高？

問題2：DBSCAN和OPTICS演算法結果是否一致？

兩種演算法效率上，從流程方面看由於OPTICS避免了重複計算核心距離，雖然在一次計算的時間上要高於DBSCAC演算法，但如果計算多個ε值的結果，OPTICS的時間明顯少於DBSCAN的時間。

兩種演算法思想上，都是按照核心點朝著稠密的方向劃分，所以最終結果兩種演算法都是一致的。下圖展示了幾個聚類效果。