DBSCAN聚類算法,LI XIN,目錄,基于密度的聚類算法的介紹 DBSCAN算法的介紹 DBSCAN算法在生物學(xué)領(lǐng)域的應(yīng)用,基于密度聚類算法,開(kāi)發(fā)原因： 彌補(bǔ)層次聚類算法和劃分式聚類算法往往只能發(fā)現(xiàn)凸型的聚類簇的缺陷。 核心思想： 只要一個(gè)區(qū)域中的點(diǎn)的密度大過(guò)某個(gè)閾值，就把它加到與之相近的聚類中去。 稠密樣本點(diǎn) 低密度區(qū)域（noise）,基于密度聚類算法,密度的定義,傳統(tǒng)基于中心的密度定義為： 數(shù)據(jù)集中特定點(diǎn)的密度通過(guò)該點(diǎn)Eps半徑之內(nèi)的點(diǎn)計(jì)數(shù)(包括本身)來(lái)估計(jì)。 顯然，密度依賴于半徑。,DBSCAN點(diǎn)分類,基于密度定義，我們將點(diǎn)分為： 稠密區(qū)域內(nèi)部的點(diǎn)(核心點(diǎn)) 稠密區(qū)域邊緣上的點(diǎn)(邊界點(diǎn)) 稀疏區(qū)域中的點(diǎn)(噪聲或背景點(diǎn)).,DBSCAN點(diǎn)分類,核心點(diǎn)(core point) :在半徑Eps內(nèi)含有超過(guò)MinPts數(shù)目的點(diǎn)，則該點(diǎn)為核心點(diǎn) 這些點(diǎn)都是在簇內(nèi)的 邊界點(diǎn)(border point):在半徑Eps內(nèi)點(diǎn)的數(shù)量小于MinPts，但是在核心點(diǎn)的鄰居 噪音點(diǎn)(noise point):任何不是核心點(diǎn)或邊界點(diǎn)的點(diǎn). MinPts：給定點(diǎn)在E領(lǐng)域內(nèi)成為核心對(duì)象的最小領(lǐng)域點(diǎn)數(shù),DBSCAN: 核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn),DBSCAN: 核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn),Original Points,Point types: core, border and noise,Eps = 10, MinPts = 4,DBSCAN算法概念,Eps鄰域：給定對(duì)象半徑Eps內(nèi)的鄰域稱為該對(duì)象的Eps鄰域，我們用 表示點(diǎn)p的Eps-半徑內(nèi)的點(diǎn)的集合，即: 核心對(duì)象：如果對(duì)象的Eps鄰域至少包含最小數(shù)目MinPts的對(duì)象，則稱該對(duì)象為核心對(duì)象。 邊界點(diǎn)：邊界點(diǎn)不是核心點(diǎn)，但落在某個(gè)核心點(diǎn)的鄰域內(nèi)。 噪音點(diǎn)：既不是核心點(diǎn)，也不是邊界點(diǎn)的任何點(diǎn),DBSCAN算法概念,直接密度可達(dá)：給定一個(gè)對(duì)象集合D，如果p在q的Eps鄰域內(nèi)，而q是一個(gè)核心對(duì)象，則稱對(duì)象p 從對(duì)象q出發(fā)時(shí)是直接密度可達(dá)的(directly density-reachable)。 密度可達(dá)：如果存在一個(gè)對(duì)象鏈 ，對(duì)于 ， 是從 關(guān)于Eps和MinPts直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于Eps和MinPts密度可達(dá)的(density-reachable) 密度相連：如果存在對(duì)象OD，使對(duì)象p和q都是從O關(guān)于Eps和MinPts密度可達(dá)的，那么對(duì)象p到q是關(guān)于Eps和MinPts密度相連的(density-connected)。,DBSCAN算法概念示例,如圖所示，Eps用一個(gè)相應(yīng)的半徑表示，設(shè)MinPts=3，請(qǐng)分析Q,M,P,S,O,R這5個(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則是從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)的Eps鄰域來(lái)搜索簇，如果點(diǎn)p的Eps鄰域包含的點(diǎn)多于MinPts個(gè)，則創(chuàng)建一個(gè)以p為核心對(duì)象的簇。 然后，DBSCAN迭代地聚集從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及一些密度可達(dá)簇的合并。 當(dāng)沒(méi)有新的點(diǎn)添加到任何簇時(shí)，該過(guò)程結(jié)束.,DBSCAN算法偽代碼,輸入：數(shù)據(jù)集D，參數(shù)MinPts,Eps 輸出：簇集合 (1) 首先將數(shù)據(jù)集D中的所有對(duì)象標(biāo)記為未處理狀態(tài) (2) for 數(shù)據(jù)集D中每個(gè)對(duì)象p do (3) if p已經(jīng)歸入某個(gè)簇或標(biāo)記為噪聲 then (4) continue; (5) else (6) 檢查對(duì)象p的Eps鄰域 ； (7) if 包含的對(duì)象數(shù)小于MinPts then (8) 標(biāo)記對(duì)象p為邊界點(diǎn)或噪聲點(diǎn)； (9) else (10) 標(biāo)記對(duì)象p為核心點(diǎn)，并建立新簇C, 并將p鄰域內(nèi)所有點(diǎn)加入C (11) for 中所有尚未被處理的對(duì)象q do (12) 檢查其Eps鄰域 ， 若 包含至少M(fèi)inPts個(gè)對(duì)象，則 將 中未歸入任何一個(gè)簇的對(duì)象加入C； (13) end for (14) end if (15) end if (16) end for,DBSCAN運(yùn)行效果好的時(shí)候,對(duì)噪音不敏感 可以處理不同形狀和大小的數(shù)據(jù),Clusters,Original Points,DBSCAN運(yùn)行不好的效果,Original Points,（MinPts=4, Eps=9.75）,(MinPts=4, Eps=9.92),密度變化的數(shù)據(jù) 高維數(shù)據(jù),DBSCAN算法的一些問(wèn)題,時(shí)間復(fù)雜度 DBSCAN的基本時(shí)間復(fù)雜度是 O(N*找出Eps領(lǐng)域中的點(diǎn)所需要的時(shí)間), N是點(diǎn)的個(gè)數(shù)。最壞情況下時(shí)間復(fù)雜度是O(N2) 在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹(shù)，使得可以有效的檢索特定點(diǎn)給定距離內(nèi)的所有點(diǎn)，時(shí)間復(fù)雜度可以降低到O(NlogN),DBSCAN算法的一些問(wèn)題,空間復(fù)雜度 低維或高維數(shù)據(jù)中，其空間都是O(N)，對(duì)于每個(gè)點(diǎn)它只需要維持少量數(shù)據(jù)，即簇標(biāo)號(hào)和每個(gè)點(diǎn)的標(biāo)識(shí)(核心點(diǎn)或邊界點(diǎn)或噪音點(diǎn)),如何合適選取EPS和MinPts,對(duì)于在一個(gè)類中的所有點(diǎn),它們的第k個(gè)最近鄰大概距離是一樣的 噪聲點(diǎn)的第k個(gè)最近鄰的距離比較遠(yuǎn) 所以, 嘗試根據(jù)每個(gè)點(diǎn)和它的第k個(gè)最近鄰之間的距離來(lái)選取 然后: Eps取什么？ MinPts取什么？,DBSCAN算法的優(yōu)缺點(diǎn),優(yōu)點(diǎn) 基于密度定義，相對(duì)抗噪音，能處理任意形狀和大小的簇 缺點(diǎn) 當(dāng)簇的密度變化太大時(shí)，會(huì)有麻煩 對(duì)于高維問(wèn)題，密度定義是個(gè)比較麻煩的問(wèn)題,DBSCAN的應(yīng)用,DBSCAN的應(yīng)用,DBSCAN的應(yīng)用,6x6 m Box,Eps：100nm,MinPts：10,DBSCAN的應(yīng)用,DBSCAN的應(yīng)用,DBSCAN的應(yīng)用,198,247 variably sized clusters of somatic mutations within ex