基于密度的聚類算法DBSCAN聚類算法

1、基于密度的聚類算法DBSCAN聚類算法DBSCANDBSCAN是一個基于密度的聚類算法.(他聚類方法大都是基于對象之間的距離進行聚類，聚類結(jié)果是球狀的簇)基于密度的聚類是尋找被低密度區(qū)域分離的高密度區(qū)域。密度的定義傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點的密度通過該點Eps半徑之內(nèi)的點計數(shù)(包括本身)來估計。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法基于密度定義，我們將點分為：稠密區(qū)域內(nèi)部的點(核心點)稠密區(qū)域邊緣上的點(邊界點)稀疏區(qū)域中的點(噪聲或背景點). DBSCAN核心點(core point) :在半徑Eps內(nèi)含有超過MinPts數(shù)目的點，則該點為核心點這些點都是在簇內(nèi)的

2、邊界點(border point):在半徑Eps內(nèi)點的數(shù)量小于MinPts，但是在核心點的鄰居噪音點(noise point):任何不是核心點或邊界點的點. DBSCANDBSCAN: 核心點、邊界點和噪音點Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4DBSCAN: 核心點、邊界點和噪音點DBSCAN算法概念Eps鄰域：給定對象半徑Eps內(nèi)的鄰域稱為該對象的Eps鄰域，我們用 表示點p的Eps-半徑內(nèi)的點的集合，即:核心對象：如果對象的Eps鄰域至少包含最小數(shù)目MinPts的對象，則稱該對象為核心對

3、象。邊界點：邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。噪音點：既不是核心點，也不是邊界點的任何點DBSCAN算法概念直接密度可達(dá)：給定一個對象集合D，如果p在q的Eps鄰域內(nèi)，而q是一個核心對象，則稱對象p 從對象q出發(fā)時是直接密度可達(dá)的(directly density-reachable)。密度可達(dá)：如果存在一個對象鏈 ，對于 ， 是從 關(guān)于Eps和MinPts直接密度可達(dá)的，則對象p是從對象q關(guān)于Eps和MinPts密度可達(dá)的(density-reachable)。密度相連：如果存在對象OD，使對象p和q都是從O關(guān)于Eps和MinPts密度可達(dá)的，那么對象p到q是關(guān)于Eps和MinPt

4、s密度相連的(density-connected)。DBSCAN算法概念示例如圖所示，Eps用一個相應(yīng)的半徑表示，設(shè)MinPts=3，請分析Q,M,P,S,O,R這5個樣本點之間的關(guān)系。 “直接密度可達(dá)”和“密度可達(dá)”概念示意描述解答：根據(jù)以上概念知道：由于有標(biāo)記的各點M、P、O和R的Eps近鄰均包含3個以上的點，因此它們都是核對象；M是從P“直接密度可達(dá)”；而Q則是從M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無法“密度可達(dá)”(非對稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。DBSCAN算法原理DBSCAN通過檢查數(shù)據(jù)集中每點的Eps鄰域來搜索

5、簇，如果點p的Eps鄰域包含的點多于MinPts個，則創(chuàng)建一個以p為核心對象的簇。然后，DBSCAN迭代地聚集從這些核心對象直接密度可達(dá)的對象，這個過程可能涉及一些密度可達(dá)簇的合并。當(dāng)沒有新的點添加到任何簇時，該過程結(jié)束.DBSCAN算法偽代碼 輸入：數(shù)據(jù)集D，參數(shù)MinPts,Eps 輸出：簇集合(1) 首先將數(shù)據(jù)集D中的所有對象標(biāo)記為未處理狀態(tài)(2) for 數(shù)據(jù)集D中每個對象p do(3) if p已經(jīng)歸入某個簇或標(biāo)記為噪聲 then(4) continue;(5) else (6) 檢查對象p的Eps鄰域 ；(7) if 包含的對象數(shù)小于MinPts then(8) 標(biāo)記對象p為邊界點

6、或噪聲點；(9) else(10) 標(biāo)記對象p為核心點，并建立新簇C, 并將p鄰域內(nèi)所有點加入C(11) for 中所有尚未被處理的對象q do(12) 檢查其Eps鄰域 ， 若 包含至少MinPts個對象， 則將 中未歸入任何一個簇的對象加入C；(13) end for(14) end if(15) end if(16) end for DBSCAN聚類算法的細(xì)節(jié)DBSCAN運行效果好的時候Original PointsClusters 對噪音不敏感 可以處理不同形狀和大小的數(shù)據(jù)DBSCAN運行不好的效果Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) 密度變化的數(shù)據(jù)高維數(shù)據(jù)DBSCAN的其它問題DBSCAN的時間復(fù)雜性時間復(fù)雜度DBSCAN的基本時間復(fù)雜度是 O(N*找出Eps領(lǐng)域中的點所需要的時間), N是點的個數(shù)。最壞情況下時間復(fù)雜度是O(N2)在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹，使得可以有效的檢索特定點給定距離內(nèi)的所有點，時間復(fù)雜度可以降低到O(NlogN)DBSCAM的空間復(fù)雜性空間復(fù)雜度低維或高維數(shù)據(jù)中，其空間都是O(N)，對于每個點它只需要維持少量數(shù)據(jù)，即簇標(biāo)號和每個點的標(biāo)識(核心點或邊界點或噪音點)如何合適選取E