積跬步以致千里,積怠惰以致深淵

主要內(nèi)容

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大集合。

該算法利用基于密度的聚類的概念，即要求聚類空間中的一定區(qū)域內(nèi)所包含對(duì)象（點(diǎn)或其他空間對(duì)象）的數(shù)目不小于某一給定閾值。DBSCAN算法的顯著優(yōu)點(diǎn)是聚類速度快且能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類。但是由于它直接對(duì)整個(gè)數(shù)據(jù)庫進(jìn)行操作且進(jìn)行聚類時(shí)使用了一個(gè)全局性的表征密度的參數(shù)，因此也具有兩個(gè)比較明顯的弱點(diǎn)：

（1）當(dāng)數(shù)據(jù)量增大時(shí)，要求較大的內(nèi)存支持I/O消耗也很大；

（2）當(dāng)空間聚類的密度不均勻、聚類間距差相差很大時(shí)，聚類質(zhì)量較差。

基本定義

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

假設(shè)我的樣本集是D=(x1,x2,...,xm)，則DBSCAN具體的密度描述定義如下：

?（1）ε-鄰域：xj∈D，其ε-鄰域包含樣本集D中與xj的距離不大于ε的子樣本集，即

這個(gè)子樣本集的個(gè)數(shù)記為|N(xj)|。

?（2）核心對(duì)象：對(duì)于任一樣本xj∈D，如果其ε-鄰域?qū)?yīng)的Nε(xj)至少包含MinPts個(gè)樣本，即如果|Nε(xj)|≥MinPts，則xj是核心對(duì)象。

?（3）密度直達(dá)：如果xi位于xj的ε-鄰域中，且xj是核心對(duì)象，則稱xi由xj密度直達(dá)。注意反之不一定成立，即此時(shí)不能說xj由xi密度直達(dá), 除非且xi也是核心對(duì)象。

?（4）密度可達(dá)：對(duì)于xi和xj,如果存在樣本樣本序列p1,p2,...,pT,滿足p1=xi,pT=xj, 且pt+1由pt密度直達(dá)，則稱xj由xi密度可達(dá)。也就是說，密度可達(dá)滿足傳遞性。此時(shí)序列中的傳遞樣本p1,p2,...,pT?1均為核心對(duì)象，因?yàn)橹挥泻诵膶?duì)象才能使其他樣本密度直達(dá)。注意密度可達(dá)也不滿足對(duì)稱性，這個(gè)可以由密度直達(dá)的不對(duì)稱性得出。

? （5）密度相連：對(duì)于xi和xj,如果存在核心對(duì)象樣本xk，使xi和xj均由xk密度可達(dá)，則稱xi和xj密度相連。注意密度相連關(guān)系是滿足對(duì)稱性的。

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點(diǎn)都是核心對(duì)象，因?yàn)槠洇?鄰域至少有5個(gè)樣本。黑色的樣本是非核心對(duì)象。所有核心對(duì)象密度直達(dá)的樣本在以紅色核心對(duì)象為中心的超球體內(nèi)，如果不在超球體內(nèi)，則不能密度直達(dá)。圖中用綠色箭頭連起來的核心對(duì)象組成了密度可達(dá)的樣本序列。在這些密度可達(dá)的樣本序列的ε-鄰域內(nèi)所有的樣本相互都是密度相連的。

DBSCAN密度聚類思想

DBSCAN的聚類定義很簡單：由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為我們最終聚類的一個(gè)類別，或者說一個(gè)簇。

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

那么怎么才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個(gè)沒有類別的核心對(duì)象作為種子，然后找到所有這個(gè)核心對(duì)象能夠密度可達(dá)的樣本集合，即為一個(gè)聚類簇。接著繼續(xù)選擇另一個(gè)沒有類別的核心對(duì)象去尋找密度可達(dá)的樣本集合，這樣就得到另一個(gè)聚類簇。一直運(yùn)行到所有核心對(duì)象都有類別為止。

基本上這就是DBSCAN算法的主要內(nèi)容了，是不是很簡單？但是我們還是有三個(gè)問題沒有考慮。

第一個(gè)是一些異常樣本點(diǎn)或者說少量游離于簇外的樣本點(diǎn)，這些點(diǎn)不在任何一個(gè)核心對(duì)象在周圍，在DBSCAN中，我們一般將這些樣本點(diǎn)標(biāo)記為噪音點(diǎn)。

第二個(gè)是距離的度量問題，即如何計(jì)算某樣本和核心對(duì)象樣本的距離。在DBSCAN中，一般采用最近鄰思想，采用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類算法的最近鄰思想完全相同。對(duì)應(yīng)少量的樣本，尋找最近鄰可以直接去計(jì)算所有樣本的距離，如果樣本量較大，則一般采用KD樹或者球樹來快速的搜索最近鄰。

第三種問題比較特殊，某些樣本可能到兩個(gè)核心對(duì)象的距離都小于ε，但是這兩個(gè)核心對(duì)象由于不是密度直達(dá)，又不屬于同一個(gè)聚類簇，那么如果界定這個(gè)樣本的類別呢？一般來說，此時(shí)DBSCAN采用先來后到，先進(jìn)行聚類的類別簇會(huì)標(biāo)記這個(gè)樣本為它的類別。也就是說DBSCAN的算法不是完全穩(wěn)定的算法。

總結(jié)

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

那么我們什么時(shí)候需要用DBSCAN來聚類呢？一般來說，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的，那么用DBSCAN會(huì)比K-Means聚類效果好很多。如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來聚類。

下面對(duì)DBSCAN算法的優(yōu)缺點(diǎn)做一個(gè)總結(jié)。

DBSCAN的主要優(yōu)點(diǎn)有：

1） 可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類，相對(duì)的，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。

2） 可以在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感。

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

DBSCAN的主要缺點(diǎn)有：

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

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

3） 調(diào)參相對(duì)于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜，主要需要對(duì)距離閾值ε，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對(duì)最后的聚類效果有較大影響。