DBSCAN

基於密度的聚類演演算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一個比較有代表性的基於密度的聚類演演算法。與劃分和層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，並可在雜訊的空間資料庫中發現任意形狀的聚類。

目錄

1概念 2描述 3步驟

4偽碼 5好處 6缺點

概念

DBSCAN中的幾個定義：

Ε鄰域：給定對象半徑為Ε內的區域稱為該對象的Ε鄰域；

核心對象：如果給定對象Ε鄰域內的樣本點數大於等於MinPts，則稱該對象為核心對象；

直接密度可達：對於樣本集合D，如果樣本點q在p的Ε鄰域內，並且p為核心對象，那麼對象q從對象p直接密度可達。

密度可達：對於樣本集合D，給定一串樣本點p,p….p，p= p,q= p,假如對象p從p直接密度可達，那麼對象q從對象p密度可達。

密度相連：存在樣本集合D中的一點o，如果對象o到對象p和對象q都是密度可達的，那麼p和q密度相聯。

可以發現，密度可達是直接密度可達的傳遞閉包，並且這種關係是非對稱的。密度相連是對稱關係。DBSCAN目的是找到密度相連對象的最大集合。

Eg: 假設半徑Ε=3，MinPts=3，點p的E鄰域中有點{m,p,p1,p2,o}, 點m的E鄰域中有點{m,q,p,m1,m2},點q的E鄰域中有點{q,m},點o的E鄰域中有點{o,p,s},點s的E鄰域中有點{o,s,s1}.

那麼核心對象有p,m,o,s(q不是核心對象，因為它對應的E鄰域中點數量等於2，小於MinPts=3)；

點m從點p直接密度可達，因為m在p的E鄰域內，並且p為核心對象；

點q從點p密度可達，因為點q從點m直接密度可達，並且點m從點p直接密度可達；

點q到點s密度相連，因為點q從點p密度可達，並且s從點p密度可達。

描述

DBSCAN

DBSCAN

DBSCAN演演算法描述:

輸入: 包含n個對象的資料庫，半徑e，最少數目MinPts;

輸出：所有生成的簇，達到密度要求。

(1)Repeat

(2)從資料庫中抽出一個未處理的點；

(3)IF抽出的點是核心點 THEN 找出所有從該點密度可達的對象，形成一個簇；

(4)ELSE 抽出的點是邊緣點(非核心對象)，跳出本次循環，尋找下一個點；

(5)UNTIL 所有的點都被處理。

DBSCAN對用戶定義的參數很敏感，細微的不同都可能導致差別很大的結果，而參數的選擇無規律可循，只能靠經驗確定。

步驟

DBScan需要二個參數：掃描半徑 (eps)和最小包含點數(minPts)。任選一個未被訪問(unvisited)的點開始，找出與其距離在eps之內(包括eps)的所有附近點。

如果附近點的數量 ≥ minPts，則當前點與其附近點形成一個簇，並且出發點被標記為已訪問(visited)。然後遞歸，以相同的方法處理該簇內所有未被標記為已訪問(visited)的點，從而對簇進行擴展。

如果附近點的數量 < minPts，則該點暫時被標記作為雜訊點。

如果簇充分地被擴展，即簇內的所有點被標記為已訪問，然後用同樣的演演算法去處理未被訪問的點。

偽碼

具體演演算法描述如下：

（1）檢測資料庫中尚未檢查過的對象 p，如果 p未被處理(歸為某個簇或者標記為雜訊)，則檢查其鄰域，若包含的對象數不小於minPts，建立新簇 C，將其中的所有點加入候選集 N；

（2）對候選集 N 中所有尚未被處理的對象 q，檢查其鄰域，若至少包含minPts個對象，則將這些對象加入N；如果 q 未歸入任何一個簇，則將 q 加入 C；

（3）重複步驟2)，繼續檢查 N 中未處理的對象，當前候選集 N為空；

（4）重複步驟1)~3)，直到所有對象都歸入了某個簇或標記為雜訊。

其偽代碼描述如下：

輸入：數據對象集合 D，半徑Eps，密度閾值MinPts

輸出：聚類C

DBSCAN（D, Eps, MinPts）

Begin

init C=0; //初始化簇的個數為0

for each unvisited point p in D

mark p as visited; //將p標記為已訪問

N = getNeighbours (p, Eps);

if sizeOf(N) < MinPts then

mark p as Noise; //如果滿足sizeOf(N) < MinPts，則將p標記為雜訊

else

C= next cluster; //建立新簇 C

ExpandCluster (p, N, C, Eps, MinPts);

end if

end for

End

其中ExpandCluster演演算法偽碼如下：

ExpandCluster(p, N, C, Eps, MinPts)

add p to cluster C; //首先將核心點加入 C

for each point p’ in N

mark p' as visited;

N’ = getNeighbours (p’, Eps); //對N鄰域內的所有點在進行半徑檢查

if sizeOf(N’) >= MinPts then

N = N+N’; //如果大於MinPts，就擴展N的數目

end if

if p’ is not member of any cluster

add p’ to cluster C; //將p' 加入簇 C

end if

end for

End ExpandCluster

好處

1. 與K-means方法相比，DBSCAN不需要事先知道要形成的簇類的數量。

2. 與K-means方法相比，DBSCAN可以發現任意形狀的簇類。

3. 同時，DBSCAN能夠識別出雜訊點。

4.DBSCAN對於資料庫中樣本的順序不敏感，即Pattern的輸入順序對結果的影響不大。但是，對於處於簇類之間邊界樣本，可能會根據哪個簇類優先被探測到而其歸屬有所擺動。

缺點

1. DBScan不能很好反映高維數據。

2. DBScan不能很好反映數據集以變化的密度。

3.如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差。

參考

“一種基於密度的演演算法為在大空間資料庫發現群以雜訊”。第2次國際會議記錄關於KDD的AAAI Press。檢索2007-10-15，“實驗在平行成群與DBSCAN”。歐洲同水準2001年：并行處理：第7國際歐洲同水準會議曼徹斯特，英國2001年8月28-31，行動Springer柏林。檢索2004-02-19。

目錄