DBSCAN 算法介紹以及C++實作

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

一、算法簡介

什麼是DBSCAN？

DBSCAN(Density-Based Spatial Clustering of Application with Noise)，是一個比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它将簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，并可在噪聲的空間資料庫中發現任意形狀的聚類。其目标是尋找被低密度區域分離的高密度區域，通俗點說就是把紮堆的點（高密度）找出來，而點很少很稀疏的地方（低密度）就作為分割區域。

一、算法詳解

1）、關鍵參數及其概念

關鍵參數：E（半徑）、 MinPts（最小樣本點數）

2)、描述：

DBSCAN算法描述:

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

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

(1)Repeat

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

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

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

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

DBSCAN對使用者定義的參數很敏感，細微的不同都可能導緻差别很大的結果，而參數的選擇無規律可循，隻能靠經驗确定。

3）、算法步驟

步驟：

DBScan需要二個參數： 掃描半徑 E(eps)和最小包含點數MinPts(minPts)。

1、 任選一個未被通路(unvisited)的點開始，找出與其距離在eps之内(包括eps)的所有附近點。

如果 附近點的數量 ≥ minPts，則目前點與其附近點形成一個簇，并且出發點被标記為已通路(visited)。

2、然後遞歸，以相同的方法處理該簇内所有未被标記為已通路(visited)的點，進而對簇進行擴充。

3、如果 附近點的數量 < minPts，則該點暫時被标記作為噪聲點。

4、如果簇充分地被擴充，即簇内的所有點被标記為已通路，然後用同樣的算法去處理未被通路的點。

4）、具體描述

具體算法描述如下：

（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
    for each unvisited point p in D
        mark p as visited; //将p标記為已通路
        N = getNeighbours (p, Eps);
        //如果滿足sizeOf(N) < MinPts，則将p标記為噪聲
        if sizeOf(N) < MinPts then
            mark p as Noise; 
                    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
           

部分實驗結果截圖：

算法總結

好處：

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

1. 與K-means方法相比，DBSCAN可以發現任意形狀的簇類。
2. 同時，DBSCAN能夠識别出噪聲點。

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

缺點：

1. DBScan不能很好反映高維資料。
2. DBScan不能很好反映資料集以變化的密度。

有關參數選擇問題

DBSCAN聚類算法的Eps及MinPts參數選擇問題

為解決DBSCAN聚類算法的Eps及MinPts參數選擇問題，提出一種領域無關的參數動态選擇方法。首先，基于k-均值算法對資料集進行初步聚類，聚類中采用最大最小距離方法确定初始聚類中心。其次，針對k-均值聚類結果，計算統計各聚類中樣本間距離的分布情況，選擇使得具有最大樣本對數的距離值作為對應類的Eps值，并通過Eps獲得MinPts值。最後，對DBSCAN算法進行改進，使其可根據目前核心點所屬k-均值聚類對應的Eps對其運作值進行自适應調整。

源碼下載下傳連接配接

http://download.csdn.net/detail/u011557212/9700546