基于密度的聚類算法（1）——DBSCAN詳解

這篇具有很好參考價值的文章主要介紹了基于密度的聚類算法（1）——DBSCAN詳解。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

基于密度的聚類算法（1）——DBSCAN詳解
基于密度的聚類算法（2）——OPTICS詳解
基于密度的聚類算法（3）——DPC詳解

1. DBSCAN簡介
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）是一種典型的基于密度的空間聚類算法。和K-Means，BIRCH這些一般只適用于凸樣本集的聚類相比，DBSCAN既可以適用于凸樣本集，也可以適用于非凸樣本集。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點的最大集合。

該算法利用基于密度的聚類的概念，即要求聚類空間中的一定區(qū)域內(nèi)所包含對象（點或其他空間對象）的數(shù)目不小于某一給定閾值。DBSCAN算法的顯著優(yōu)點是聚類速度快且能夠有效處理噪聲點和發(fā)現(xiàn)任意形狀的空間聚類。但是當(dāng)空間聚類的密度不均勻、聚類間距差相差很大時，聚類質(zhì)量較差。

2. DBSCAN的優(yōu)缺點
和傳統(tǒng)的K-Means算法相比，DBSCAN最大的不同就是不需要輸入類別數(shù)k，最大的優(yōu)勢是可以發(fā)現(xiàn)任意形狀的聚類簇，而不是像K-Means，一般僅僅使用于凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH算法類似。

那么什么時候需要用DBSCAN來聚類呢？一般來說，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的，那么用DBSCAN會比K-Means聚類效果好很多。如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來聚類。
（1）DBSCAN的優(yōu)點：
1）可以對任意形狀的稠密數(shù)據(jù)集進行聚類，相對的，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。
2）可以在聚類的同時發(fā)現(xiàn)異常點，對數(shù)據(jù)集中的異常點不敏感。
3）聚類結(jié)果沒有偏倚，相對的，K-Means之類的聚類算法初始值對聚類結(jié)果有很大影響。
（2）DBSCAN的缺點：
1）如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質(zhì)量較差，這時用DBSCAN聚類一般不適合。
2）如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰時建立的KD樹或者球樹進行規(guī)模限制來改進。
3）調(diào)參相對于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜，主要需要對距離閾值?，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對最后的聚類效果有較大影響

3. DBSCAN詳細(xì)描述及參數(shù)含義
DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，參數(shù)(?, MinPts)用來描述鄰域的樣本分布緊密程度。其中，?描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為?的鄰域中樣本個數(shù)的閾值。
　　　　假設(shè)樣本集是*D=(x1,x2,...,xm)*,則DBSCAN具體的密度描述如下：
　　　　1） ?-鄰域：對于xj∈D，其?-鄰域包含樣本集D中與xj的距離不大于?的子樣本集，即N?(xj)={xi∈D|distance(xi,xj)≤?}, 這個子樣本集的個數(shù)記為|N?(xj)|　
　　　　2) 核心對象：對于任一樣本xj∈D，如果其?-鄰域?qū)?yīng)的N?(xj)至少包含MinPts個樣本，即如果|N?(xj)|≥MinPts，則xj是核心對象。　
　　　　3）密度直達(dá)：如果xi位于xj的?-鄰域中，且xj是核心對象，則稱xi由xj密度直達(dá)。注意反之不一定成立，即此時不能說xj由xi密度直達(dá), 除非且xi也是核心對象。
　　　　4）密度可達(dá)：對于xi和xj,如果存在樣本樣本序列p1,p2,...,pT,滿足p1=xi,pT=xj, 且pt+1由pt密度直達(dá)，則稱xj由xi密度可達(dá)。也就是說，密度可達(dá)滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT?1均為核心對象，因為只有核心對象才能使其他樣本密度直達(dá)。注意密度可達(dá)也不滿足對稱性，這個可以由密度直達(dá)的不對稱性得出。
　　　　5）密度相連：對于xi和xj,如果存在核心對象樣本xk，使xi和xj均由xk密度可達(dá)，則稱xi和xj密度相連。注意密度相連關(guān)系是滿足對稱性的。

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其?-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達(dá)的樣本在以紅色核心對象為中心的超球體內(nèi)，如果不在超球體內(nèi)，則不能密度直達(dá)。圖中用綠色箭頭連起來的核心對象組成了密度可達(dá)的樣本序列。在這些密度可達(dá)的樣本序列的?-鄰域內(nèi)所有的樣本相互都是密度相連的。
dbscan聚類,聚類算法原理解析及實現(xiàn),聚類,算法
4. DBSCAN思想
　　DBSCAN的聚類定義很簡單：由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇。
　　這個DBSCAN的簇里面可以有一個或者多個核心對象。如果只有一個核心對象，則簇里其他的非核心對象樣本都在這個核心對象的?-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的?-鄰域中一定有一個其他的核心對象，否則這兩個核心對象無法密度可達(dá)。這些核心對象的?-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。
　　　　
　　那么怎么才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然后找到所有這個核心對象能夠密度可達(dá)的樣本集合，即為一個聚類簇。接著繼續(xù)選擇另一個沒有類別的核心對象去尋找密度可達(dá)的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。

這基本上就是DBSCAN算法的主要內(nèi)容了，但是還有三個問題沒有考慮：
　　1）一些異常樣本點或者說少量游離于簇外的樣本點，這些點不在任何一個核心對象在周圍，在DBSCAN中，我們一般將這些樣本點標(biāo)記為噪音點。
　　2）距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般采用最近鄰思想，采用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類算法的最近鄰思想完全相同。對應(yīng)少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，如果樣本量較大，則一般采用KD樹或者球樹來快速的搜索最近鄰。
　　3）第三種問題比較特殊，某些樣本可能到兩個核心對象的距離都小于?，但是這兩個核心對象由于不是密度直達(dá)，又不屬于同一個聚類簇，那么如果界定這個樣本的類別呢？一般來說，此時DBSCAN采用先來后到，先進行聚類的類別簇會標(biāo)記這個樣本為它的類別。也就是說DBSCAN的算法不是完全穩(wěn)定的算法

5. DBSCAN算法步驟
下面是DBSCAN聚類算法的主要步驟
　　輸入：樣本集D=(x1,x2,...,xm)，鄰域參數(shù)(?,MinPts), 樣本距離度量方式
　　輸出：簇劃分C.　
　　
　　1）初始化核心對象集合Ω=?, 初始化聚類簇數(shù)k=0，初始化未訪問樣本集合Γ = D, 簇劃分C = ?
　　2) 對于j=1,2,…m, 按下面的步驟找出所有的核心對象：
　　　 a) 通過距離度量方式，找到樣本xj的?-鄰域子樣本集N?(xj)
　　　 b) 如果子樣本集樣本個數(shù)滿足|N?(xj)|≥MinPts，將樣本xj加入核心對象樣本集合：Ω=Ω∪{xj}
　　3）如果核心對象集合Ω=?，則算法結(jié)束，否則轉(zhuǎn)入步驟4.
　　4）在核心對象集合Ω中，隨機選擇一個核心對象o，初始化當(dāng)前簇核心對象隊列Ωcur={o}, 初始化類別序號k=k+1，初始化當(dāng)前簇樣本集合Ck={o}, 更新未訪問樣本集合Γ=Γ?{o}
　　5）如果當(dāng)前簇核心對象隊列Ωcur=?，則當(dāng)前聚類簇Ck生成完畢, 更新簇劃分C={C1,C2,...,Ck}, 更新核心對象集合Ω=Ω?Ck，轉(zhuǎn)入步驟3。否則更新核心對象集合Ω=Ω?Ck。
　　6）在當(dāng)前簇核心對象隊列Ωcur中取出一個核心對象o′,通過鄰域距離閾值?找出所有的?-鄰域子樣本集N?(o′)，令Δ=N?(o′)∩Γ, 更新當(dāng)前簇樣本集合Ck=Ck∪Δ, 更新未訪問樣本集合Γ=Γ?Δ, 更新Ωcur=Ωcur∪(Δ∩Ω)?o′，轉(zhuǎn)入步驟5.
　　輸出結(jié)果為：簇劃分C={C1,C2,…,Ck}

6. DBSCAN算法在python scikit-learn實現(xiàn)
　　在scikit-learn中，DBSCAN算法類為sklearn.cluster.DBSCAN。要熟練的掌握用DBSCAN類來聚類，除了對DBSCAN本身的原理有較深的理解以外，還要對最近鄰的思想有一定的理解。
　　DBSCAN重要參數(shù)也分為兩類，一類是DBSCAN算法本身的參數(shù)，一類是最近鄰度量的參數(shù)：
　　1）eps： DBSCAN算法參數(shù)，即我們的?-鄰域的距離閾值，和樣本距離超過?的樣本點不在?-鄰域內(nèi)。默認(rèn)值是0.5.一般需要通過在多組值里面選擇一個合適的閾值。eps過大，則更多的點會落在核心對象的?-鄰域，此時我們的類別數(shù)可能會減少，本來不應(yīng)該是一類的樣本也會被劃為一類。反之則類別數(shù)可能會增大，本來是一類的樣本卻被劃分開。
　　2）min_samples： DBSCAN算法參數(shù)，即樣本點要成為核心對象所需要的?-鄰域的樣本數(shù)閾值。默認(rèn)值是5. 一般需要通過在多組值里面選擇一個合適的閾值。通常和eps一起調(diào)參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內(nèi)部分本來是一類的樣本可能會被標(biāo)為噪音點，類別數(shù)也會變多。反之min_samples過小的話，則會產(chǎn)生大量的核心對象，可能會導(dǎo)致類別數(shù)過少。
　　3）metric：最近鄰距離度量參數(shù)?？梢允褂玫木嚯x度量較多，一般來說DBSCAN使用默認(rèn)的歐式距離（即p=2的閔可夫斯基距離）就可以滿足我們的需求?？梢允褂玫木嚯x度量參數(shù)有：
　　　　a) 歐式距離 “euclidean”
　　　　b) 曼哈頓距離 “manhattan”
　　　　c) 切比雪夫距離“chebyshev”
　　　　d) 閔可夫斯基距離 “minkowski”
　　　　e) 帶權(quán)重閔可夫斯基距離 “wminkowski”
　　　　f) 標(biāo)準(zhǔn)化歐式距離 “seuclidean”: 即對于各特征維度做了歸一化以后的歐式距離。此時各樣本特征維度的均值為0，方差為1.
　　　　g) 馬氏距離“mahalanobis”：當(dāng)樣本分布獨立時，馬氏距離等同于歐式距離。
　還有一些其他不是實數(shù)的距離度量，一般在DBSCAN算法用不上，這里也就不列了。
　　
　　4）algorithm：最近鄰搜索算法參數(shù)，算法一共有三種，第一種是蠻力實現(xiàn)，第二種是KD樹實現(xiàn)，第三種是球樹實現(xiàn)。對于這個參數(shù)，一共有4種可選輸入，‘brute’對應(yīng)第一種蠻力實現(xiàn)，‘kd_tree’對應(yīng)第二種KD樹實現(xiàn)，‘ball_tree’對應(yīng)第三種的球樹實現(xiàn)， ‘a(chǎn)uto’則會在上面三種算法中做權(quán)衡，選擇一個擬合最好的最優(yōu)算法。需要注意的是，如果輸入樣本特征是稀疏的時候，無論我們選擇哪種算法，最后scikit-learn都會去用蠻力實現(xiàn)‘brute’。個人的經(jīng)驗，一般情況使用默認(rèn)的 ‘a(chǎn)uto’就夠了。如果數(shù)據(jù)量很大或者特征也很多，用"auto"建樹時間可能會很長，效率不高，建議選擇KD樹實現(xiàn)‘kd_tree’，此時如果發(fā)現(xiàn)‘kd_tree’速度比較慢或者已經(jīng)知道樣本分布不是很均勻時，可以嘗試用‘ball_tree’。而如果輸入樣本是稀疏的，無論你選擇哪個算法最后實際運行的都是‘brute’。
　　5）leaf_size：最近鄰搜索算法參數(shù)，為使用KD樹或者球樹時，停止建子樹的葉子節(jié)點數(shù)量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數(shù)越深，建樹時間越長，反之，則生成的KD樹或者球樹會小，層數(shù)較淺，建樹時間較短。默認(rèn)是30. 因為這個值一般只影響算法的運行速度和使用內(nèi)存大小，因此一般情況下可以不管它。
　　6） p: 最近鄰距離度量參數(shù)。只用于閔可夫斯基距離和帶權(quán)重閔可夫斯基距離中p值的選擇，p=1為曼哈頓距離， p=2為歐式距離。如果使用默認(rèn)的歐式距離不需要管這個參數(shù)。
　　以上就是DBSCAN類的主要參數(shù)介紹，需要調(diào)參的兩個參數(shù)eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響。因此，DBSCAN聚類算法的結(jié)果對參數(shù)比較敏感，基于DBSCAN開發(fā)的OPTICS聚類算法則很好的解決了這個問題，后續(xù)會更新OPTICS算法的詳解。

生成一組隨機數(shù)據(jù)，為了體現(xiàn)DBSCAN在非凸數(shù)據(jù)的聚類優(yōu)點，我們生成了三簇數(shù)據(jù)，兩組是非凸的

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
%matplotlib inline
X1, y1=datasets.make_circles(n_samples=5000, factor=.6,
                                      noise=.05)
X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]],
               random_state=9)

X = np.concatenate((X1, X2))
plt.scatter(X[:, 0], X[:, 1], marker='o')
plt.show()

dbscan聚類,聚類算法原理解析及實現(xiàn),聚類,算法

1）利用K-Means聚類，代碼如下：

from sklearn.cluster import KMeans
y_pred = KMeans(n_clusters=3, random_state=9).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

dbscan聚類,聚類算法原理解析及實現(xiàn),聚類,算法
2）使用DBSCAN，用默認(rèn)參數(shù)，代碼如下：

from sklearn.cluster import DBSCAN
y_pred = DBSCAN().fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

dbscan聚類,聚類算法原理解析及實現(xiàn),聚類,算法
但是聚類結(jié)果是只有一類。。。

3）使用DBSCAN，調(diào)整兩個重要參數(shù)：
從上圖可以發(fā)現(xiàn)，類別數(shù)太少，因此需要增加類別數(shù)，可以通過減少?-鄰域的大小來實現(xiàn)，默認(rèn)是0.5，減到0.1看看效果。代碼如下：

y_pred = DBSCAN(eps = 0.1).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

dbscan聚類,聚類算法原理解析及實現(xiàn),聚類,算法
可以看到聚類效果有了改進。繼續(xù)調(diào)參增加類別，有兩個方向都是可以的，一個是繼續(xù)減少eps，另一個是增加min_samples。將min_samples從默認(rèn)的5增加到10，代碼如下：

y_pred = DBSCAN(eps = 0.1, min_samples = 10).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

dbscan聚類,聚類算法原理解析及實現(xiàn),聚類,算法
此時的聚類效果基本是可以令人滿意的。

7. 總結(jié)
DBSCAN需要調(diào)參的兩個參數(shù)eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響，即DBSCAN聚類算法的結(jié)果對參數(shù)比較敏感。
基于DBSCAN開發(fā)的OPTICS聚類算法，則很好的解決了這個問題，后續(xù)會更新OPTICS算法的詳解與應(yīng)用。
此外，DBSCAN的matlab函數(shù)也已更新在資源中，有需要的也可以評論或者留言找我要??！
https://download.csdn.net/download/weixin_50514171/85192429?spm=1001.2014.3001.5503文章來源地址http://www.zghlxwxcb.cn/news/detail-821902.html

到了這里，關(guān)于基于密度的聚類算法（1）——DBSCAN詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！