基本介紹
概念,描述,步驟,偽碼,好處,缺點,參考,
概念
DBSCAN中的幾個定義：
Ε鄰域：給定對象半徑為Ε內的區域稱為該對象的Ε鄰域；
核心對象：如果給定對象Ε鄰域內的樣本點數大於等於MinPts，則稱該對象為核心對象；
直接密度可達：對於樣本集合D，如果樣本點q在p的Ε鄰域內，並且p為核心對象，那么對象q從對象p直接密度可達。
密度可達：對於樣本集合D，給定一串樣本點p1,p2….pn，p= p1,q= pn,假如對象pi從pi-1直接密度可達，那么對象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算法描述:
輸入: 包含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 unvisited 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.如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差。
