DBSCAN聚類算法簡介

1、DBSCAN聚類算法簡介DBSCAN （ DensityBased Spatial Clustering of Application with Noise）算法是一 種典型的基于密度的聚類方法。它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠 密度的區(qū)域劃分為簇，并可以在有噪音的空間數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的簇。1. 基本概念DBSCAN算法中有兩個(gè)重要參數(shù)：Eps和MmPtS。Eps是定義密度時(shí)的鄰域半徑， MmPts為定義核心點(diǎn)時(shí)的閾值。在DBSCAN算法中將數(shù)據(jù)點(diǎn)分為以下3類。1）核心點(diǎn)如果一個(gè)對(duì)象在其半徑Eps內(nèi)含有超過MmPts數(shù)目的點(diǎn)，則該對(duì)象為核心點(diǎn)。2）邊界點(diǎn)如果一個(gè)對(duì)象在其半

2、徑Eps內(nèi)含有點(diǎn)的數(shù)量小于MinPts，但是該對(duì)象落在核心點(diǎn)的鄰域 內(nèi)，則該對(duì)象為邊界點(diǎn)。3）噪音點(diǎn)如果一個(gè)對(duì)象既不是核心點(diǎn)也不是邊界點(diǎn)，則該對(duì)象為噪音點(diǎn)。通俗地講/核心點(diǎn)對(duì)應(yīng)稠密區(qū)域內(nèi)部的點(diǎn)/邊界點(diǎn)對(duì)應(yīng)稠密區(qū)域邊緣的點(diǎn)/而噪音點(diǎn)對(duì)應(yīng)稀 疏區(qū)域中的點(diǎn)。在圖1中假設(shè)MinPts=5 ,Eps如圖中箭頭線所示貝U點(diǎn)A為核心點(diǎn)點(diǎn)B為邊界點(diǎn)，點(diǎn)C為噪音點(diǎn)。點(diǎn)A因?yàn)樵谄銭ps鄰域內(nèi)含有7個(gè)點(diǎn),超過了 Eps=5，所以是核心點(diǎn)。點(diǎn)E和點(diǎn)C因?yàn)樵谄銭ps鄰域內(nèi)含有點(diǎn)的個(gè)數(shù)均少于5，所以不是核心點(diǎn)；點(diǎn)B因?yàn)槁湓诹它c(diǎn)A的Eps鄰域內(nèi)，所以點(diǎn)B是邊界點(diǎn)；點(diǎn)C因?yàn)闆]有落在任何核心點(diǎn)的鄰域名稱說明Eps鄰域簡單來講就

3、是與點(diǎn)的距離小于等于Eps的所有點(diǎn)的集合。直接密如果點(diǎn)p在核心點(diǎn)q的Eps鄰域內(nèi)，則稱數(shù)據(jù)對(duì)象p從數(shù)據(jù)對(duì)象q出發(fā)是度可達(dá)直接密度可達(dá)的。名稱說明密度可達(dá)如果存在數(shù)據(jù)對(duì)象鏈PP2Pn是從G關(guān)于Eps和MinPts直接密度可達(dá)的，則數(shù)據(jù)對(duì)象 戸戌是從數(shù)據(jù)對(duì)象尸l關(guān)于EpsMinPts 密度可達(dá)的。密度相對(duì)于對(duì)象p和對(duì)象q，如果存在核心對(duì)象樣本o，使數(shù)據(jù)對(duì)象p和對(duì)象q均連從o密度可達(dá)，則稱p和q密度相連。顯然，密度相連具有對(duì)稱性。密度聚類簇由一個(gè)核心點(diǎn)和與其密度可達(dá)的所有對(duì)象構(gòu)成一個(gè)密度聚類簇。圖2直接密度可達(dá)和密度可達(dá)示意在圖2中，點(diǎn)a為核心點(diǎn)，點(diǎn)b為邊界點(diǎn)，并且因?yàn)閍直接密度可達(dá)b。但是b不 直

4、接密度可達(dá)a（因?yàn)閎不是一個(gè)核心點(diǎn)）因?yàn)閏直接密度可達(dá)a，a直接密度可達(dá) b，所以c密度可達(dá)b。但是因?yàn)閎不直接密度可達(dá)a，所以b不密度可達(dá)c。但是b和c密度相連。2. 算法描述DBSCAN算法對(duì)簇的定義很簡單，由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為 最終聚類的一個(gè)簇。DBSCAN算法的簇里面可以有一個(gè)或者多個(gè)核心點(diǎn)。如果只有一個(gè)核心點(diǎn)，則簇里其他的 非核心點(diǎn)樣本都在這個(gè)核心點(diǎn)的Eps鄰域里。如果有多個(gè)核心點(diǎn)，則簇里的任意一個(gè)核心 點(diǎn)的Eps鄰域中一定有一個(gè)其他的核心點(diǎn)，否則這兩個(gè)核心點(diǎn)無法密度可達(dá)。這些核心點(diǎn) 的Eps鄰域里所有的樣本的集合組成一個(gè)DBSCAN聚類簇。DBSCAN算

5、法的描述如下。輸入：數(shù)據(jù)集，鄰域半徑Eps，鄰域中數(shù)據(jù)對(duì)象數(shù)目閾值MinPts;輸出：密度聯(lián)通簇。處理流程如下。1）從數(shù)據(jù)集中任意選取一個(gè)數(shù)據(jù)對(duì)象點(diǎn)p；2）如果對(duì)于參數(shù)Eps和MinPts，所選取的數(shù)據(jù)對(duì)象點(diǎn)p為核心點(diǎn)，則找出所有從p密 度可達(dá)的數(shù)據(jù)對(duì)象點(diǎn)，形成一個(gè)簇；3）如果選取的數(shù)據(jù)對(duì)象點(diǎn)p是邊緣點(diǎn)，選取另一個(gè)數(shù)據(jù)對(duì)象點(diǎn);4)重復(fù)(2)(3 )步，直到所有點(diǎn)被處理。DBSCAN算法的計(jì)算復(fù)雜的度為O(nO , n為數(shù)據(jù)對(duì)象的數(shù)目。這種算法對(duì)于輸入?yún)?shù)Eps和MinPts是敏感的。算法實(shí)例下面給出一個(gè)樣本數(shù)據(jù)集，如表1所示，并對(duì)其實(shí)施DBSCAN算法進(jìn)行聚類，取Eps=3，Min Pts=3

6、。表1 DSCAN算法樣本數(shù)據(jù)集plp2P3p4P5P6P7P8P9P10P11P12P1312245667913532143879951212123數(shù)據(jù)集中的樣本數(shù)據(jù)在二維空間內(nèi)的表示如圖3所示。 p-1-1 (3 f 12)p6, 9)1；2)001312103(3, 3)2345678910 p-1-1 (3 f 12)p6, 9)1；2)001312103(3, 3)2345678910 p5 點(diǎn) 8)p8(7, 9).p9 (9, 5)M3)圖3直接密度可達(dá)和密度可達(dá)示意第一步，順序掃描數(shù)據(jù)集的樣本點(diǎn)，首先取到p1(1,2)。1)計(jì)算pl的鄰域，計(jì)算出每一點(diǎn)到p1的距離，如d(p1,

7、p2)=sqrt(1 + 1) = 1.414。2)根據(jù)每個(gè)樣本點(diǎn)到p1的距離，計(jì)算出p1的Eps鄰域?yàn)閜1,p2,p3,p13。3)因?yàn)閜1的Eps鄰域含有4個(gè)點(diǎn)，大于MinPts(3)，所以，p1為核心點(diǎn)。以p1為核心點(diǎn)建立簇C1,即找出所有從p1密度可達(dá)的點(diǎn)。p1鄰域內(nèi)的點(diǎn)都是p1直接密度可達(dá)的點(diǎn)，所以都屬于C1。尋找pl密度可達(dá)的點(diǎn)，p2的鄰域?yàn)閜1,p2,p3,p4,p13，因?yàn)閜l密度可達(dá)p2 , p2密度可達(dá)p4，所以pl密度可達(dá)p4，因此p4也屬于C1。p3 的鄰域?yàn)閜1,p2,p3,p4,p13，p13 的鄰域?yàn)閜1,p2,p3,p4,p13，p3 和 p13 都是核心點(diǎn)，但

8、是它們鄰域的點(diǎn)都已經(jīng)在Cl中。P4的鄰域?yàn)閜3,p4,p13，為核心點(diǎn)，其鄰域內(nèi)的所有點(diǎn)都已經(jīng)被處理。此時(shí)，以p1為核心點(diǎn)出發(fā)的那些密度可達(dá)的對(duì)象都全部處理完畢，得到簇C1,包含 點(diǎn)p1,p2,p3,p13,p4。第二步，繼續(xù)順序掃描數(shù)據(jù)集的樣本點(diǎn)，取到p5(5,8)。計(jì)算p5的鄰域，計(jì)算出每一點(diǎn)到p5的距離，如d(p1,p8)-sqrt(4+1)=2.236。根據(jù)每個(gè)樣本點(diǎn)到p5的距離，計(jì)算出p5的Eps鄰域?yàn)閜5,p6,p7,p8。因?yàn)閜5的Eps鄰域含有4個(gè)點(diǎn)，大于MinPts(3)，所以，p5為核心點(diǎn)。以p5為核心點(diǎn)建立簇C2，即找出所有從p5密度可達(dá)的點(diǎn)，可以獲得簇C2，包 含點(diǎn)p5

9、,p6,p7,p8。第三步，繼續(xù)順序掃描數(shù)據(jù)集的樣本點(diǎn)，取到p9(9,5)。計(jì)算出p9的Eps鄰域?yàn)閜9，個(gè)數(shù)小于MinPts(3)，所以p9不是核心點(diǎn)。對(duì)p9處理結(jié)束。第四步，繼續(xù)順序掃描數(shù)據(jù)集的樣本點(diǎn)，取到p10(1,12)。計(jì)算出p10的Eps鄰域?yàn)閜10,pll，個(gè)數(shù)小于MinPts(3),所以p10不是核心點(diǎn)。對(duì)p10處理結(jié)束。第五步，繼續(xù)順序掃描數(shù)據(jù)集的樣本點(diǎn)，取到p11(3,12)。計(jì)算出p11的Eps鄰域?yàn)閜11,p10,p12，個(gè)數(shù)等于MinPts(3)，所以p11是核心點(diǎn)。從p12的鄰域?yàn)閜12,p11，不是核心點(diǎn)。3)以p11為核心點(diǎn)建立簇C3，包含點(diǎn)p11,p10,p1

10、2。第六步，繼續(xù)掃描數(shù)據(jù)的樣本點(diǎn)，p12、p13都已經(jīng)被處理過，算法結(jié)束。算法優(yōu)缺點(diǎn)和傳統(tǒng)的k-means算法相比，DBSCAN算法不需要輸入簇?cái)?shù)k而且可以發(fā)現(xiàn)任意形狀 的聚類簇，同時(shí)，在聚類時(shí)可以找出異常點(diǎn)。DBSCAN算法的主要優(yōu)點(diǎn)如下。1）可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類，而k-means之類的聚類算法一般只適用于凸 數(shù)據(jù)集。2）可以在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感。3）聚類結(jié)果沒有偏倚，而k-means之類的聚類算法的初始值對(duì)聚類結(jié)果有很大影響。DBSCAN算法的主要缺點(diǎn)如下。1）樣本集的密度不均勻、聚類間距差相差很大時(shí)，聚類質(zhì)量較差，這時(shí)用DBSCAN算法 一般不適合。2）樣本集較大時(shí)，聚類收斂時(shí)間較長，此時(shí)可以對(duì)搜索最近鄰時(shí)建立的KD樹或者球樹進(jìn) 行規(guī)模限制來進(jìn)行改進(jìn)。3）調(diào)試參數(shù)比較復(fù)雜時(shí)，主要需要對(duì)距離閾值Eps,鄰域樣本數(shù)閾值MinPts進(jìn)