DBSCAN聚類算法簡介

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

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

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

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

5、法的描述如下。輸入：數(shù)據(jù)集，鄰域半徑Eps，鄰域中數(shù)據(jù)對象數(shù)目閾值MinPts;輸出：密度聯(lián)通簇。處理流程如下。1）從數(shù)據(jù)集中任意選取一個數(shù)據(jù)對象點p；2）如果對于參數(shù)Eps和MinPts，所選取的數(shù)據(jù)對象點p為核心點，則找出所有從p密 度可達(dá)的數(shù)據(jù)對象點，形成一個簇；3）如果選取的數(shù)據(jù)對象點p是邊緣點，選取另一個數(shù)據(jù)對象點;4)重復(fù)(2)(3 )步，直到所有點被處理。DBSCAN算法的計算復(fù)雜的度為O(nO , n為數(shù)據(jù)對象的數(shù)目。這種算法對于輸入?yún)?shù)Eps和MinPts是敏感的。算法實例下面給出一個樣本數(shù)據(jù)集，如表1所示，并對其實施DBSCAN算法進行聚類，取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 點 8)p8(7, 9).p9 (9, 5)M3)圖3直接密度可達(dá)和密度可達(dá)示意第一步，順序掃描數(shù)據(jù)集的樣本點，首先取到p1(1,2)。1)計算pl的鄰域，計算出每一點到p1的距離，如d(p1,

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

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

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

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