DBSCAN基于密度的聚類算法

1、基于密度的聚類算法基于密度的聚類算法DBSCAN聚類算法聚類算法DBSCANDBSCAN是一個(gè)基于密度是一個(gè)基于密度的聚類算法的聚類算法.(他聚類方法他聚類方法大都是基于對(duì)象之間的距大都是基于對(duì)象之間的距離進(jìn)行聚類，聚類結(jié)果是離進(jìn)行聚類，聚類結(jié)果是球狀的簇球狀的簇)基于密度的聚類是尋找被基于密度的聚類是尋找被低密度區(qū)域分離的高密度低密度區(qū)域分離的高密度區(qū)域。區(qū)域。密度的定義密度的定義傳統(tǒng)基于中心的密度定義為：傳統(tǒng)基于中心的密度定義為： 數(shù)據(jù)集中特定點(diǎn)的密度通過(guò)該點(diǎn)數(shù)據(jù)集中特定點(diǎn)的密度通過(guò)該點(diǎn)EpsEps半徑之內(nèi)的點(diǎn)計(jì)半徑之內(nèi)的點(diǎn)計(jì)數(shù)數(shù)( (包括本身包括本身) )來(lái)估計(jì)。來(lái)估計(jì)。 顯然，密度依賴

2、于半徑。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法傳統(tǒng)的密度定義：基于中心的方法基于密度定義，我們將點(diǎn)分為：基于密度定義，我們將點(diǎn)分為： 稠密區(qū)域內(nèi)部的點(diǎn)稠密區(qū)域內(nèi)部的點(diǎn)( (核心點(diǎn)核心點(diǎn)) ) 稠密區(qū)域邊緣上的點(diǎn)稠密區(qū)域邊緣上的點(diǎn)( (邊界點(diǎn)邊界點(diǎn)) ) 稀疏區(qū)域中的點(diǎn)稀疏區(qū)域中的點(diǎn)( (噪聲或背景點(diǎn)噪聲或背景點(diǎn)). ). DBSCAN核心點(diǎn)核心點(diǎn)( (core point)core point) : :在半徑在半徑EpsEps內(nèi)含有超過(guò)內(nèi)含有超過(guò)MinPtsMinPts數(shù)目的點(diǎn)，則該點(diǎn)為核心點(diǎn)數(shù)目的點(diǎn)，則該點(diǎn)為核心點(diǎn) 這些點(diǎn)都是在簇內(nèi)的邊界點(diǎn)邊界點(diǎn)( (border point)

3、:border point):在半徑在半徑EpsEps內(nèi)點(diǎn)的數(shù)量小內(nèi)點(diǎn)的數(shù)量小于于MinPtsMinPts，但是在核心點(diǎn)的鄰居，但是在核心點(diǎn)的鄰居噪音點(diǎn)噪音點(diǎn)( (noise point):noise point):任何不是核心點(diǎn)或邊界點(diǎn)任何不是核心點(diǎn)或邊界點(diǎn)的點(diǎn)的點(diǎn). . DBSCANDBSCAN: 核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn)核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn)Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4DBSCAN: 核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn)核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn)DBSCAN算法概念Eps鄰域：給定對(duì)象半徑給定對(duì)象

4、半徑Eps內(nèi)的鄰域稱為該對(duì)象的內(nèi)的鄰域稱為該對(duì)象的Eps鄰域，鄰域，我們用我們用 表示點(diǎn)表示點(diǎn)p的的Eps-半徑內(nèi)的點(diǎn)的集合，即半徑內(nèi)的點(diǎn)的集合，即:核心對(duì)象：如果對(duì)象的如果對(duì)象的Eps鄰域至少包含最小數(shù)目鄰域至少包含最小數(shù)目MinPts的的對(duì)象，則稱該對(duì)象為核心對(duì)象。對(duì)象，則稱該對(duì)象為核心對(duì)象。邊界點(diǎn)：邊界點(diǎn)不是核心點(diǎn)，但落在某個(gè)核心點(diǎn)的鄰域內(nèi)。邊界點(diǎn)不是核心點(diǎn)，但落在某個(gè)核心點(diǎn)的鄰域內(nèi)。噪音點(diǎn)：既不是核心點(diǎn)，也不是邊界點(diǎn)的任何點(diǎn)既不是核心點(diǎn)，也不是邊界點(diǎn)的任何點(diǎn))( pNEpsEpsq),distance(pDq|q)(中，在數(shù)據(jù)集pNEpsDBSCAN算法概念直接密度可達(dá)：給定一個(gè)對(duì)象集

5、合給定一個(gè)對(duì)象集合D，如果，如果p在在q的的Eps鄰域內(nèi)，而鄰域內(nèi)，而q是一是一個(gè)核心對(duì)象，則稱對(duì)象個(gè)核心對(duì)象，則稱對(duì)象p 從對(duì)象從對(duì)象q出發(fā)時(shí)是直接密度可達(dá)的出發(fā)時(shí)是直接密度可達(dá)的(directly density-reachable)。密度可達(dá)：如果存在一個(gè)對(duì)象鏈如果存在一個(gè)對(duì)象鏈 ，對(duì)于，對(duì)于 ， 是從是從 關(guān)于關(guān)于Eps和和MinPts直接密度可達(dá)的，則對(duì)象直接密度可達(dá)的，則對(duì)象p是從對(duì)象是從對(duì)象q關(guān)于關(guān)于Eps和和MinPts密度可達(dá)的密度可達(dá)的(density-reachable)。密度相連：如果存在對(duì)象如果存在對(duì)象OD，使對(duì)象，使對(duì)象p和和q都是從都是從O關(guān)于關(guān)于Eps和和Min

6、Pts密度可達(dá)的，那么對(duì)象密度可達(dá)的，那么對(duì)象p到到q是關(guān)于是關(guān)于Eps和和MinPts密度相連的密度相連的(density-connected)。ppqppppnn ,121)1 (niDpi1ipipDBSCAN算法概念示例算法概念示例 如圖所示，如圖所示，Eps用一個(gè)相應(yīng)的半徑表示，設(shè)用一個(gè)相應(yīng)的半徑表示，設(shè)MinPts=3，請(qǐng)分析，請(qǐng)分析Q,M,P,S,O,R這這5個(gè)樣本點(diǎn)之間的關(guān)系。個(gè)樣本點(diǎn)之間的關(guān)系。 “直接密度可達(dá)”和“密度可達(dá)”概念示意描述解答：根據(jù)以上概念知道：由于有標(biāo)記的各點(diǎn)M、P、O和R的Eps近鄰均包含3個(gè)以上的點(diǎn)，因此它們都是核對(duì)象；M是從P“直接密度可達(dá)”；而Q則是

7、從M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無(wú)法“密度可達(dá)”(非對(duì)稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。DBSCAN算法原理算法原理 DBSCAN通過(guò)檢查數(shù)據(jù)集中每點(diǎn)的通過(guò)檢查數(shù)據(jù)集中每點(diǎn)的Eps鄰域來(lái)搜索簇鄰域來(lái)搜索簇，如果點(diǎn)，如果點(diǎn)p的的Eps鄰域包含的點(diǎn)多于鄰域包含的點(diǎn)多于MinPts個(gè)，則創(chuàng)個(gè)，則創(chuàng)建一個(gè)以建一個(gè)以p為核心對(duì)象的簇。為核心對(duì)象的簇。 然后，然后，DBSCAN迭代地聚集從這些核心對(duì)象直接密度迭代地聚集從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及一些密度可達(dá)簇的可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及一些密度可達(dá)簇的合并。合

8、并。 當(dāng)沒(méi)有新的點(diǎn)添加到任何簇時(shí)，該過(guò)程結(jié)束當(dāng)沒(méi)有新的點(diǎn)添加到任何簇時(shí)，該過(guò)程結(jié)束.DBSCAN算法偽代碼算法偽代碼 輸入：數(shù)據(jù)集輸入：數(shù)據(jù)集D，參數(shù)，參數(shù)MinPts,Eps 輸出：簇集合輸出：簇集合(1) 首先將數(shù)據(jù)集首先將數(shù)據(jù)集D中的所有對(duì)象標(biāo)記為未處理狀態(tài)中的所有對(duì)象標(biāo)記為未處理狀態(tài)(2) for 數(shù)據(jù)集數(shù)據(jù)集D中每個(gè)對(duì)象中每個(gè)對(duì)象p do(3) if p已經(jīng)歸入某個(gè)簇或標(biāo)記為噪聲已經(jīng)歸入某個(gè)簇或標(biāo)記為噪聲 then(4) continue;(5) else (6) 檢查對(duì)象檢查對(duì)象p的的Eps鄰域鄰域 ；(7) if 包含的對(duì)象數(shù)小于包含的對(duì)象數(shù)小于MinPts then(8) 標(biāo)記

9、對(duì)象標(biāo)記對(duì)象p為邊界點(diǎn)或噪聲點(diǎn)；為邊界點(diǎn)或噪聲點(diǎn)；(9) else(10) 標(biāo)記對(duì)象標(biāo)記對(duì)象p為核心點(diǎn)，并建立新簇為核心點(diǎn)，并建立新簇C, 并將并將p鄰域內(nèi)所有點(diǎn)加入鄰域內(nèi)所有點(diǎn)加入C(11) for 中所有尚未被處理的對(duì)象中所有尚未被處理的對(duì)象q do(12) 檢查其檢查其Eps鄰域鄰域 ， 若若 包含至少包含至少M(fèi)inPts個(gè)對(duì)象，個(gè)對(duì)象， 則將則將 中未歸入任何一個(gè)簇的對(duì)象加入中未歸入任何一個(gè)簇的對(duì)象加入C；(13) end for(14) end if(15) end if(16) end for (p) NEps(p) NEps(q) NEps(q) NEps(p) NEps(q)

10、NEpsDBSCAN聚類算法的細(xì)節(jié)聚類算法的細(xì)節(jié)DBSCAN運(yùn)行效果好的時(shí)候運(yùn)行效果好的時(shí)候Original PointsClusters 對(duì)噪音不敏感對(duì)噪音不敏感 可以處理不同形狀和大小的數(shù)據(jù)可以處理不同形狀和大小的數(shù)據(jù)DBSCAN運(yùn)行不好的效果運(yùn)行不好的效果Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) 密度變化的數(shù)據(jù)密度變化的數(shù)據(jù)高維數(shù)據(jù)高維數(shù)據(jù)DBSCAN的其它問(wèn)題的其它問(wèn)題DBSCAN的時(shí)間復(fù)雜性的時(shí)間復(fù)雜性 時(shí)間復(fù)雜度時(shí)間復(fù)雜度DBSCANDBSCAN的基本時(shí)間復(fù)雜度是的基本時(shí)間復(fù)雜度是 O(N O(N* *找出找

11、出EpsEps領(lǐng)域中的點(diǎn)所需領(lǐng)域中的點(diǎn)所需要的時(shí)間要的時(shí)間), N), N是點(diǎn)的個(gè)數(shù)。最壞情況下時(shí)間復(fù)雜度是是點(diǎn)的個(gè)數(shù)。最壞情況下時(shí)間復(fù)雜度是O(NO(N2 2) )在低維空間數(shù)據(jù)中在低維空間數(shù)據(jù)中, ,有一些數(shù)據(jù)結(jié)構(gòu)如有一些數(shù)據(jù)結(jié)構(gòu)如KDKD樹，使得可以有樹，使得可以有效的檢索特定點(diǎn)給定距離內(nèi)的所有點(diǎn)，時(shí)間復(fù)雜度可以降效的檢索特定點(diǎn)給定距離內(nèi)的所有點(diǎn)，時(shí)間復(fù)雜度可以降低到低到O(NlogN)O(NlogN)DBSCAM的空間復(fù)雜性的空間復(fù)雜性 空間復(fù)雜度空間復(fù)雜度低維或高維數(shù)據(jù)中，其空間都是低維或高維數(shù)據(jù)中，其空間都是O(N)O(N)，對(duì)于每個(gè)點(diǎn)它只需，對(duì)于每個(gè)點(diǎn)它只需要維持少量數(shù)據(jù)，即簇標(biāo)號(hào)和每個(gè)點(diǎn)的標(biāo)識(shí)要維持少量數(shù)據(jù)，即簇標(biāo)號(hào)和每個(gè)點(diǎn)的標(biāo)識(shí)( (核心點(diǎn)或邊核心點(diǎn)或邊界點(diǎn)或噪音點(diǎn)界點(diǎn)或噪音點(diǎn)) )如何合適選取如何合適選取EPS和和MinPts思想是這樣的對(duì)于在一個(gè)類中的所有點(diǎn)思想是這樣的對(duì)于在一個(gè)類中的所有點(diǎn),它們的第它們的第k個(gè)最近鄰大概距離是一樣的個(gè)最近鄰大概距離是一樣的噪聲點(diǎn)的第噪聲點(diǎn)的第k個(gè)最近鄰的距離比較遠(yuǎn)個(gè)最近鄰的距離比較遠(yuǎn)所以所以, 嘗試根據(jù)每個(gè)點(diǎn)和它的第嘗試根據(jù)每個(gè)點(diǎn)和它的第k個(gè)最近鄰之間的個(gè)最近鄰之間的距離來(lái)選取