1. 密度聚類原理

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

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

2. DBSCAN密度定義

??????? 在上一節(jié)我們定性描述了密度聚類的基本思想，本節(jié)我們就看看DBSCAN是如何描述密度聚類的。DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，參數(shù)(? ?, MinPts)用來描述鄰域的樣本分布緊密程度。其中，? ?描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為? ?的鄰域中樣本個數(shù)的閾值。

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

??????? 1） ? ?-鄰域：對于x j ∈D xj∈D，其? ?-鄰域包含樣本集D中與x j xj的距離不大于? ?的子樣本集，即N ? (x j )={x i ∈D|distance(x i ,x j )≤?} N?(xj)={xi∈D|distance(xi,xj)≤?}, 這個子樣本集的個數(shù)記為|N ? (x j )| |N?(xj)|

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

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

??????? 4）密度可達(dá)：對于x i xi和x j xj,如果存在樣本樣本序列p 1 ,p 2 ,...,p T p1,p2,...,pT,滿足p 1 =x i ,p T =x j p1=xi,pT=xj, 且p t+1 pt+1由p t pt密度直達(dá)，則稱x j xj由x i xi密度可達(dá)。也就是說，密度可達(dá)滿足傳遞性。此時序列中的傳遞樣本p 1 ,p 2 ,...,p T?1 p1,p2,...,pT?1均為核心對象，因?yàn)橹挥泻诵膶ο蟛拍苁蛊渌麡颖久芏戎边_(dá)。注意密度可達(dá)也不滿足對稱性，這個可以由密度直達(dá)的不對稱性得出。

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

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

?3. DBSCAN密度聚類思想

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

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

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

??????? 基本上這就是DBSCAN算法的主要內(nèi)容了，是不是很簡單？但是我們還是有三個問題沒有考慮。 　　　　第一個是一些異常樣本點(diǎn)或者說少量游離于簇外的樣本點(diǎn)，這些點(diǎn)不在任何一個核心對象在周圍，在DBSCAN中，我們一般將這些樣本點(diǎn)標(biāo)記為噪音點(diǎn)。

??????? 第二個是距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般采用最近鄰思想，采用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類算法的最近鄰思想完全相同。對應(yīng)少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，如果樣本量較大，則一般采用KD樹或者球樹來快速的搜索最近鄰。如果大家對于最近鄰的思想，距離度量，KD樹和球樹不熟悉，建議參考之前寫的另一篇文章K近鄰法(KNN)原理小結(jié)。

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

4. DBSCAN聚類算法

下面我們對DBSCAN聚類算法的流程做一個總結(jié)。

??????? 輸入：樣本集D=(x 1 ,x 2 ,...,x m ) (x1,x2,...,xm)，鄰域參數(shù)(?,MinPts) (?,MinPts), 樣本距離度量方式 　　　　??????? 輸出： 簇劃分C.

??????? 1）初始化核心對象集合Ω=? Ω=?, 初始化聚類簇數(shù)k=0，初始化未訪問樣本集合Γ Γ = D, 簇劃分C = ? ?

??????? 2) 對于j=1,2,...m, 按下面的步驟找出所有的核心對象：

??????????????? a) 通過距離度量方式，找到樣本x j xj的? ?-鄰域子樣本集N ? (x j ) N?(xj)

????????????????b) 如果子樣本集樣本個數(shù)滿足|N ? (x j )|≥MinPts |N?(xj)|≥MinPts， 將樣本x j xj加入核心對象樣本集合：Ω=Ω∪{x j } Ω=Ω∪{xj}

??????? 3）如果核心對象集合Ω=? Ω=?，則算法結(jié)束，否則轉(zhuǎn)入步驟4.

??????? 4）在核心對象集合Ω Ω中，隨機(jī)選擇一個核心對象o o，初始化當(dāng)前簇核心對象隊(duì)列Ω cur ={o} Ωcur={o}, 初始化類別序號k=k+1，初始化當(dāng)前簇樣本集合C k ={o} Ck={o}, 更新未訪問樣本集合Γ=Γ?{o} Γ=Γ?{o}

??????? 5）如果當(dāng)前簇核心對象隊(duì)列Ω cur =? Ωcur=?，則當(dāng)前聚類簇C k Ck生成完畢, 更新簇劃分C={C 1 ,C 2 ,...,C k } {C1,C2,...,Ck}, 更新核心對象集合Ω=Ω?C k Ω=Ω?Ck， 轉(zhuǎn)入步驟3。

??????? 6）在當(dāng)前簇核心對象隊(duì)列Ω cur Ωcur中取出一個核心對象o ′ o′,通過鄰域距離閾值? ?找出所有的? ?-鄰域子樣本集N ? (o ′ ) N?(o′)，令Δ=N ? (o ′ )∩Γ Δ=N?(o′)∩Γ, 更新當(dāng)前簇樣本集合C k =C k ∪Δ Ck=Ck∪Δ, 更新未訪問樣本集合Γ=Γ?Δ Γ=Γ?Δ, 更新Ω cur =Ω cur ∪(Δ∩Ω)?o ′ Ωcur=Ωcur∪(Δ∩Ω)?o′，轉(zhuǎn)入步驟5.

??????? 輸出結(jié)果為： 簇劃分C={C 1 ,C 2 ,...,C k } {C1,C2,...,Ck}

5. DBSCAN小結(jié)

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

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

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

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

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

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

??????????????? 3） 聚類結(jié)果沒有偏倚，相對的，K-Means之類的聚類算法初始值對聚類結(jié)果有很大影響。 　　　　??????? DBSCAN的主要缺點(diǎn)有：

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

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

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

參考：http://www.cnblogs.com/pinard/p/6208966.html