DBSCAN

DBSCAN

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

概念

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.

相關詞條

相關搜尋

熱門詞條

聯絡我們