《DBSCAN聚類算法【教育知識】》由會員分享，可在線閱讀，更多相關(guān)《DBSCAN聚類算法【教育知識】（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、DBSCANDBSCAN聚類算法聚類算法LI XIN1教書育人目錄目錄 基于密度的聚類算法的介紹 DBSCAN算法的介紹 DBSCAN算法在生物學(xué)領(lǐng)域的應(yīng)用 2教書育人基于密度聚類算法基于密度聚類算法 開發(fā)原因：彌補層次聚類算法和劃分式聚類算法往往只能發(fā)現(xiàn)凸型的聚類簇凸型的聚類簇的缺陷。核心思想：只要一個區(qū)域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。稠密樣本點稠密樣本點 低密度區(qū)域（低密度區(qū)域（noise）3教書育人基于密度聚類算法基于密度聚類算法4教書育人密度的定義密度的定義 傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點的密度通過該點Eps半徑之內(nèi)的點計數(shù)(包括本身)來估計。顯然，
2、密度依賴于半徑。5教書育人DBSCANDBSCAN點分類點分類 基于密度定義，我們將點分為：稠密區(qū)域內(nèi)部的點(核心點核心點)稠密區(qū)域邊緣上的點(邊界點邊界點)稀疏區(qū)域中的點(噪聲或背景點噪聲或背景點).6教書育人DBSCANDBSCAN點分類點分類核心點(core point):在半徑Eps內(nèi)含有超過MinPts數(shù)目的點，則該點為核心點 這些點都是在簇內(nèi)的邊界點(border point):在半徑Eps內(nèi)點的數(shù)量小于MinPts，但是在核心點的鄰居噪音點(noise point):任何不是核心點或邊界點的點.MinPts：給定點在E領(lǐng)域內(nèi)成為核心對象的最小領(lǐng)域點數(shù) 7教書育人DBSCAN:DB
3、SCAN:核心點、邊界點和噪音點核心點、邊界點和噪音點8教書育人DBSCAN:DBSCAN:核心點、邊界點和噪音點核心點、邊界點和噪音點Original PointsPoint types:core,border and noiseEps=10,MinPts=49教書育人DBSCANDBSCAN算法概念算法概念 Eps鄰域鄰域：給定對象半徑Eps內(nèi)的鄰域稱為該對象的Eps鄰域，我們用 表示點p的Eps-半徑內(nèi)的點的集合，即:核心核心對象對象：如果對象的Eps鄰域至少包含最小數(shù)目MinPts的對象，則稱該對象為核心對象。邊界點：邊界點：邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。噪音點：噪音點：
4、既不是核心點，也不是邊界點的任何點)(pNEpsEpsq),distance(pDq|q)(中，在數(shù)據(jù)集pNEps10教書育人DBSCANDBSCAN算法概念算法概念 直接密度可達：直接密度可達：給定一個對象集合D，如果p在q的Eps鄰域內(nèi)，而q是一個核心對象，則稱對象p 從對象q出發(fā)時是直接密度可達的(directly density-reachable)。密度可達：密度可達：如果存在一個對象鏈 ，對于 ，是從 關(guān)于Eps和MinPts直接密度可達的，則對象p是從對象q關(guān)于Eps和MinPts密度可達的(density-reachable)密度相連：密度相連：如果存在對象OD，使對象p和q都
5、是從O關(guān)于Eps和MinPts密度可達的，那么對象p到q是關(guān)于Eps和MinPts密度相連的(density-connected)。ppqppppnn,121)1(niDpi1ipip11教書育人DBSCANDBSCAN算法概念示例算法概念示例 如圖所示，Eps用一個相應(yīng)的半徑表示，設(shè)MinPts=3，請分析Q,M,P,S,O,R這5個樣本點之間的關(guān)系?！爸苯用芏瓤蛇_”和“密度可達”概念示意描述12教書育人解答解答 根據(jù)以上概念知道：由于有標(biāo)記的各點M、P、O和R的Eps近鄰均包含3個以上的點，因此它們都是核對象；M是從P“直接密度可達”；而Q則是從M“直接密度可達”；基于上述結(jié)果，Q是從P“
6、密度可達”；但P從Q無法“密度可達”(非對稱)。類似地，S和R從O是“密度可達”的；O、R和S均是“密度相連”的13教書育人DBSCANDBSCAN算法原理算法原理 DBSCAN通過檢查數(shù)據(jù)集中每點的Eps鄰域來搜索簇，如果點p的Eps鄰域包含的點多于MinPts個，則創(chuàng)建一個以p為核心對象的簇。然后，DBSCAN迭代地聚集從這些核心對象直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并。當(dāng)沒有新的點添加到任何簇時，該過程結(jié)束.14教書育人DBSCANDBSCAN算法偽代碼算法偽代碼 輸入：數(shù)據(jù)集輸入：數(shù)據(jù)集D，參數(shù)，參數(shù)MinPts,Eps 輸出：簇集合輸出：簇集合(1)首先將數(shù)據(jù)集D
7、中的所有對象標(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為邊界點或噪聲點；(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(p)NEps(q)
8、NEps15教書育人DBSCANDBSCAN運行效果好的時候運行效果好的時候 對噪音不敏感對噪音不敏感 可以處理不同形狀和大小的數(shù)據(jù)可以處理不同形狀和大小的數(shù)據(jù)ClustersOriginal Points16教書育人DBSCANDBSCAN運行不好的效果運行不好的效果Original Points（MinPts=4,Eps=9.75）(MinPts=4,Eps=9.92)密度變化的數(shù)據(jù)密度變化的數(shù)據(jù)高維數(shù)據(jù)高維數(shù)據(jù)17教書育人DBSCANDBSCAN算法的一些問題算法的一些問題 時間復(fù)雜度時間復(fù)雜度 DBSCAN的基本時間復(fù)雜度是 O(N*找出Eps領(lǐng)域中的點所需要的時間),N是點的個數(shù)。最
9、壞情況下時間復(fù)雜度是O(N2)在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹，使得可以有效的檢索特定點給定距離內(nèi)的所有點，時間復(fù)雜度可以降低到O(NlogN)18教書育人DBSCANDBSCAN算法的一些問題算法的一些問題 空間復(fù)雜度空間復(fù)雜度 低維或高維數(shù)據(jù)中，其空間都是O(N)，對于每個點它只需要維持少量數(shù)據(jù)，即簇標(biāo)號和每個點的標(biāo)識(核心點或邊界點或噪音點)19教書育人如何合適選取如何合適選取EPSEPS和和MinPtsMinPts 對于在一個類中的所有點,它們的第k個最近鄰大概距離是一樣的 噪聲點的第k個最近鄰的距離比較遠 所以,嘗試根據(jù)每個點和它的第k個最近鄰之間的距離來選取 然后:Eps取
10、什么取什么？MinPts取什么取什么？20教書育人DBSCANDBSCAN算法的優(yōu)缺點算法的優(yōu)缺點 優(yōu)點 基于密度定義，相對抗噪音，能處理任意形狀和大小的簇 缺點 當(dāng)簇的密度變化太大時，會有麻煩 對于高維問題，密度定義是個比較麻煩的問題21教書育人DBSCANDBSCAN的應(yīng)用的應(yīng)用22教書育人DBSCANDBSCAN的應(yīng)用的應(yīng)用23教書育人DBSCANDBSCAN的應(yīng)用的應(yīng)用6x6 m BoxEps：100nmMinPts：1024教書育人DBSCANDBSCAN的應(yīng)用的應(yīng)用25教書育人DBSCANDBSCAN的應(yīng)用的應(yīng)用26教書育人DBSCANDBSCAN的應(yīng)用的應(yīng)用 198,247 variably sized clusters of somatic mutations within exon proximal domains of the human genome Eps=dp/ds（10500bp）（dp：突變位置的平均距離 ds：突變域的大?。㎝inPts：P0.05 二項式檢驗 Eps和MinPts不是一成不變的27教書育人Thanks28教書育人
DBSCAN聚類算法【教育知識】
