DBSCAN密度聚類

以下內容來自劉建平Pinard-博客園的學習筆記，總結如下：

1 DBSCAN密度聚類演算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有雜訊的基於密度的聚類方法)是一種很典型的密度聚類演算法，和K-Means，BIRCH這些一般只適用於凸樣本集的聚類相比，DBSCAN既可以適用於凸樣本集，也可以適用於非凸樣本集。

下面我們就對DBSCAN演算法的原理做一個總結。

1.1 密度聚類原理

DBSCAN是一種基於密度的聚類演算法，這類密度聚類演算法一般假定類別可以通過樣本分布的緊密程度決定。同一類別的樣本，他們之間的緊密相連的，也就是說，在該類別任意樣本周圍不遠處一定有同類別的樣本存在。

通過將緊密相連的樣本劃為一類，這樣就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃為各個不同的類別，則我們就得到了最終的所有聚類類別結果。

1.2 DBSCAN密度定義

DBSCAN是如何描述密度聚類的。

DBSCAN是基於一組鄰域來描述樣本集的緊密程度的，參數(?, MinPts)用來描述鄰域的樣本分布緊密程度。其中，?描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為?的鄰域中樣本個數的閾值。

假設樣本集 $D=(x_{1},x_{2},...,x_{m})$ ，則DBSCAN具體的密度描述定義如下：

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其?-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達的樣本在以紅色核心對象為中心的超球體內，如果不在超球體內，則不能密度直達。

圖中用綠色箭頭連起來的核心對象組成了密度可達的樣本序列。在這些密度可達的樣本序列的

?-鄰域內所有的樣本相互都是密度相連的。

1.3 DBSCAN密度聚類思想

DBSCAN的聚類定義很簡單：由密度可達關係導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇。

這個DBSCAN的簇裡面可以有一個或者多個核心對象。如果只有一個核心對象，則簇里其他的非核心對象樣本都在這個核心對象的?-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的?-鄰域中一定有一個其他的核心對象，否則這兩個核心對象無法密度可達。這些核心對象的?-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

那麼怎麼才能找到這樣的簇樣本集合呢？

DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。

基本上這就是DBSCAN演算法的主要內容了，但是我們還是有三個問題沒有考慮。

第一個是一些異常樣本點或者說少量遊離於簇外的樣本點，這些點不在任何一個核心對象在周圍，在DBSCAN中，我們一般將這些樣本點標記為噪音點。

第二個是距離的度量問題，即如何計算某樣本和核心對象樣本的距離。

在DBSCAN中，一般採用最近鄰思想，採用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類演算法的最近鄰思想完全相同。對應少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，如果樣本量較大，則一般採用KD樹或者球樹來快速的搜索最近鄰。

第三種問題比較特殊，某些樣本可能到兩個核心對象的距離都小於?，但是這兩個核心對象由於不是密度直達，又不屬於同一個聚類簇，那麼如果界定這個樣本的類別呢？一般來說，此時DBSCAN採用先來後到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說BDSCAN的演算法不是完全穩定的演算法。

1.4 DBSCAN聚類演算法

下面我們對DBSCAN聚類演算法的流程做一個總結。

1.5 DBSCAN小結

和傳統的K-Means演算法相比，DBSCAN最大的不同就是不需要輸入類別數k，當然它最大的優勢是可以發現任意形狀的聚類簇，而不是像K-Means，一般僅僅使用於凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH演算法類似。

那麼我們什麼時候需要用DBSCAN來聚類呢？

一般來說，如果數據集是稠密的，並且數據集不是凸的，那麼用DBSCAN會比K-Means聚類效果好很多。如果數據集不是稠密的，則不推薦用DBSCAN來聚類。

下面對DBSCAN演算法的優缺點做一個總結。

DBSCAN的主要優點有：

1）可以對任意形狀的稠密數據集進行聚類，相對的，K-Means之類的聚類演算法一般只適用於凸數據集。

2）可以在聚類的同時發現異常點，對數據集中的異常點不敏感。

3）聚類結果沒有偏倚，相對的，K-Means之類的聚類演算法初始值對聚類結果有很大影響。

DBSCAN的主要缺點有：

1）如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合。

2）如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰時建立的KD樹或者球樹進行規模限制來改進。

3）調參相對於傳統的K-Means之類的聚類演算法稍複雜，主要需要對距離閾值?，鄰域樣本數閾值MinPts聯合調參，不同的參數組合對最後的聚類效果有較大影響。

2 用scikit-learn學習DBSCAN聚類

2.1 scikit-learn中的DBSCAN類

在scikit-learn中，DBSCAN演算法類為sklearn.cluster.DBSCAN。要熟練的掌握用DBSCAN類來聚類，除了對DBSCAN本身的原理有較深的理解以外，還要對最近鄰的思想有一定的理解。集合這兩者，就可以玩轉DBSCAN了。

2.2 DBSCAN類重要參數

DBSCAN類的重要參數也分為兩類，一類是DBSCAN演算法本身的參數，一類是最近鄰度量的參數，下面我們對這些參數做一個總結。

1）eps： DBSCAN演算法參數，即我們的?-鄰域的距離閾值，和樣本距離超過?的樣本點不在

?-鄰域內。默認值是0.5.一般需要通過在多組值裡面選擇一個合適的閾值。eps過大，則更多的點會落在核心對象的?-鄰域，此時我們的類別數可能會減少，本來不應該是一類的樣本也會被劃為一類。反之則類別數可能會增大，本來是一類的樣本卻被劃分開。

2）min_samples： DBSCAN演算法參數，即樣本點要成為核心對象所需要的?-鄰域的樣本數閾值。默認值是5. 一般需要通過在多組值裡面選擇一個合適的閾值。通常和eps一起調參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內部分本來是一類的樣本可能會被標為噪音點，類別數也會變多。反之min_samples過小的話，則會產生大量的核心對象，可能會導致類別數過少。

3）metric：最近鄰距離度量參數。可以使用的距離度量較多，一般來說DBSCAN使用默認的歐式距離（即p=2的閔可夫斯基距離）就可以滿足我們的需求。可以使用的距離度量參數有：

還有一些其他不是實數的距離度量，一般在DBSCAN演算法用不上，這裡也就不列了。

4）algorithm：最近鄰搜索演算法參數，演算法一共有三種，第一種是蠻力實現，第二種是KD樹實現，第三種是球樹實現。對於這個參數，一共有4種可選輸入，『brute』對應第一種蠻力實現，『kd_tree』對應第二種KD樹實現，『ball_tree』對應第三種的球樹實現，『auto』則會在上面三種演算法中做權衡，選擇一個擬合最好的最優演算法。

需要注意的是，如果輸入樣本特徵是稀疏的時候，無論我們選擇哪種演算法，最後scikit-learn都會去用蠻力實現『brute』。個人的經驗，一般情況使用默認的『auto』就夠了。如果數據量很大或者特徵也很多，用"auto"建樹時間可能會很長，效率不高，建議選擇KD樹實現『kd_tree』，此時如果發現『kd_tree』速度比較慢或者已經知道樣本分布不是很均勻時，可以嘗試用『ball_tree』。而如果輸入樣本是稀疏的，無論你選擇哪個演算法最後實際運行的都是『brute』。

5）leaf_size：最近鄰搜索演算法參數，為使用KD樹或者球樹時，停止建子樹的葉子節點數量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數越深，建樹時間越長，反之，則生成的KD樹或者球樹會小，層數較淺，建樹時間較短。默認是30. 因為這個值一般隻影響演算法的運行速度和使用內存大小，因此一般情況下可以不管它。

6） p: 最近鄰距離度量參數。只用於閔可夫斯基距離和帶權重閔可夫斯基距離中p值的選擇，p=1為曼哈頓距離， p=2為歐式距離。如果使用默認的歐式距離不需要管這個參數。

以上就是DBSCAN類的主要參數介紹，其實需要調參的就是兩個參數eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響。

1.3 scikit-learn DBSCAN聚類實例

首先，我們生成一組隨機數據，為了體現DBSCAN在非凸數據的聚類優點，我們生成了三簇數據，兩組是非凸的。代碼如下：