一般說到聚類算法，大多數人會想到k－means算法，但k－means算法一般只適用于凸樣本集，且需要預先設定k值，而DBSCAN聚類既可以用于凸樣本集，也可以用于非凸樣本集，也不需要提前設定簇族數。關于凸樣本集的解釋如下圖所示。

關于DBSCAN聚類，它是基于密度的聚類，一般通過樣本間的緊密程度來進行聚類，將緊密相連的一類樣本化為一類，直至遍歷所有樣本點。

而DBSCAN聚類有下面幾個定義。

1．ε－鄰域：有一個樣本點x1，以x1為圓心，半徑為ε的一個范圍

2．min＿sample（最小樣本點數）：在樣本點x1的ε－鄰域內的所有樣本點總數n；如果n＞＝min＿sample，樣本點成為核心點，否則為非核心點。而非核心又分為邊界點和噪聲點。他們的區(qū)別在于其ε－鄰域內是否存在核心點，如果存在則為邊界點，否則為噪聲點。

3．密度直達：有樣本點x1位于x2的ε－鄰域內，且x2為核心點，則稱x1由x2密度直達。

4．密度可達：有樣本點x1位于x2的ε－鄰域內，且x1和x2均為核心點，則稱x1和x2密度可達。

5．密度相連：有非核心點x1和x2均在核心點x3的ε－鄰域內，則稱x1和x2密度相連。所有密度相連的樣本點組成一個集合。

上圖中的紅色點為核心點，黑色點為非核心點（包括邊界點和噪音點）。一共有兩組密度可達，第一組（左邊）有七個核心點，其集合包括七個核心點以及各個ε－鄰域內的所有邊界點。第二組（右邊）有五個核心點，其集合包括五個核心點以及各個ε－鄰域內的所有邊界點。當所有非噪聲點均在不同集合內時，聚類結束。

因此，可以將DBSCAN聚類的流程定義如下：

有數據集X＝｛x1，x2，．．．，xn｝，設置好min＿sample和鄰域半徑值。

1．遍歷數據集，將各個樣本點間的距離保存到一個矩陣中；

2．遍歷數據集，將所有的核心點，以及各個核心點鄰域內的樣本點找出；

3．如果核心點間的距離小于半徑值，則將兩個核心點連接到一起；最終會形成若干簇族；

4．將所有邊界點分配到離他最近的核心點；

5．直至所有非噪音點完成分配，算法結束。

python實現

用的是sklearn庫自帶的數據集－－－make＿circles。散點圖如下。

根據上面定義的流程，開始寫代碼啦。

首先要得到各個樣本點間的距離：

def dis（self，va，vb）：    s＝（va－vb）    f＝sqrt（s＊s．T）    return f［0，0］
def get＿distance（self，dataset）：    m，n＝shape（dataset）［0］，shape（dataset）［1］    dataset＝mat（dataset）    dis＝mat（zeros（（m，m）））    for i in range（m）：        for j in range（i，m）：            dis［i，j］＝self．dis（dataset［i，］，dataset［j，］）            dis［j，i］＝dis［i，j］    return dis

然后找到所有的核心點，以及各個核心點鄰域內的所有樣本點集合。

def find＿core＿point（self，dismatrix）：    core＿point＝［］    core＿point＿dict＝｛｝    m＝shape（dismatrix）［0］    for i in range（m）：        ind＝［］        for j in range（m）：            if dismatrix［i，j］＜self．eps：                ind．append（j）        if len（ind）＞＝self．min＿sample：            core＿point．append（i）            core＿point＿dict［str（i）］＝ind    core＿point＿core＝｛｝    for key，value in core＿point＿dict．items（）：        o＝［］        for i in value：            if i in core＿point：                o．append（i）        core＿point＿core［key］＝o    return core＿point，core＿point＿dict，core＿point＿core其中core＿point是一個列表，存儲所有的核心點core＿point＿dict是一個字典，key為核心點，value為該核心點鄰域內的所有樣本點集合core＿point＿core是一個字典，key為核心點，value為該核心點鄰域內所有核心點集合

接下來就是找出密度直達點集合，也就是在鄰域內的核心點集合

def join＿core＿point（self，core＿point，core＿point＿dict，core＿point＿core）：    labels＝array（zeros（（1，len（core＿point））））    num＝1    result＝｛｝    result［str（num）］＝core＿point＿core［str（core＿point［0］）］    for i in range（1，len（core＿point））：        q＝［］        for key，value in result．items（）：            r＝self．get＿same（core＿point＿core［str（core＿point［i］）］，value）            if r：                q．append（key）        if q：            n＝result［q［0］］．copy（）            n．extend（core＿point＿core［str（core＿point［i］）］）            for i in range（1，len（q））：                n．extend（result［q［i］］）                del result［q［i］］            result［q［0］］＝list（set（n））        else：            num＝num＋1            result［str（num）］＝core＿point＿core［str（core＿point［i］）］    return result

再將所有邊界點劃分到其最近的核心點一簇并畫出。

def ddbscan（self，data， label）：        m＝shape（data）［0］        dismatrix＝self．get＿distance（data）        types＝array（zeros（（1，m）））        number＝1        core＿point， core＿point＿dict，core＿point＿core＝self．find＿core＿point（dismatrix）        if len（core＿point）：            core＿result＝self．join＿core＿point（core＿point，core＿point＿dict，core＿point＿core）            for key，value in core＿result．items（）：                k＝int（key）                for i in value：                    types［0，i］＝k                    for j in core＿point＿dict［str（i）］：                        types［0， j］ ＝ k            print（types）        newlabel＝types．tolist（）［0］        data＝array（data）        q＝list（set（newlabel））        print（q）        colors ＝ ［＇r＇， ＇b＇， ＇g＇， ＇y＇， ＇c＇， ＇m＇， ＇orange＇］        for ii in q：            i＝int（ii）            xy＝data［types［0，：］＝＝i，：］            plt．plot（xy［：， 0］， xy［：， 1］， ＇o＇， markerfacecolor＝colors［q．index（ii）］， markeredgecolor＝＇w＇， markersize＝5）        plt．title（＇DBSCAN＇ ）        plt．show（）

最后的結果圖如下：

雖然效果不錯，但自己寫的就是比較辣雞，一共用了10．445904秒；如果真的要用這個算法的話，不推薦大家用自己寫的，事實上sklearn庫就有DBSCAN這個函數，只需要0．0284941秒。

效果如上所示。而且代碼也只有幾行。代碼復制于（http：／／itindex．net／detail／58485－％E8％81％9A％E7％B1％BB－％E7％AE％97％E6％B3％95－dbscan）

def skdbscan（self，data，label）：        data ＝ array（data）        db ＝ DBSCAN（eps＝self．eps， min＿samples＝self．min＿sample， metric＝＇euclidean＇）．fit（data）        core＿samples＿mask ＝ zeros＿like（db．labels＿， dtype＝bool）        core＿samples＿mask［db．core＿sample＿indices＿］ ＝ True        labels ＝ db．labels＿        n＿clusters＿ ＝ len（set（labels）） － （1 if －1 in labels else 0）        unique＿labels ＝ set（labels）        colors ＝ ［＇r＇， ＇b＇， ＇g＇， ＇y＇， ＇c＇， ＇m＇， ＇orange＇］        for k， col in zip（unique＿labels， colors）：            if k ＝＝ －1：                col ＝ ＇k＇            class＿member＿mask ＝ （labels ＝＝ k）            xy ＝ data［class＿member＿mask ＆ core＿samples＿mask］            plt．plot（xy［：， 0］， xy［：， 1］， ＇o＇， markerfacecolor＝col， markeredgecolor＝＇w＇， markersize＝10）        plt．title（＇Estimated number of clusters： ％d＇ ％ n＿clusters＿）        plt．show（）

關于DBSCAN這個函數有幾個要注意的地方：

DBSCAN（eps＝0．1， min＿samples＝5， metric＝＇euclidean＇，

algorithm＝＇auto＇， leaf＿size＝30， p＝None， n＿jobs＝1）

核心參數：

eps： float－鄰域的距離閾值

min＿samples ：int，樣本點要成為核心對象所需要的 ？－鄰域的樣本數閾值

其他參數：

metric ：度量方式，默認為歐式距離，可以使用的距離度量參數有：

歐式距離 “euclidean”

曼哈頓距離 “manhattan”

切比雪夫距離“chebyshev”

閔可夫斯基距離 “minkowski”

帶權重閔可夫斯基距離 “wminkowski”

標準化歐式距離 “seuclidean”

馬氏距離“mahalanobis”

自己定義距離函數

algorithm：近鄰算法求解方式，有四種：

“brute”蠻力實現

“kd＿tree” KD樹實現

“ball＿tree”球樹實現

“auto”上面三種算法中做權衡，選擇一個擬合最好的最優(yōu)算法。

leaf＿size：使用“ball＿tree”或“kd＿tree”時，停止建子樹的葉子節(jié)點數量的閾值

p：只用于閔可夫斯基距離和帶權重閔可夫斯基距離中p值的選擇，p＝1為曼哈頓距離， p＝2為歐式距離。如果使用默認的歐式距離不需要管這個參數。

n＿jobs ：CPU并行數，若值為 －1，則用所有的CPU進行運算

DBSCAN聚類的優(yōu)缺點

優(yōu)點：

可以很好的發(fā)現噪聲點，但是對其不敏感；

可以對任意形狀的稠密數據進行聚類；

缺點：

1．需要設定min＿sample和eps；不同的組合差別非常大；

2．數據量很大時，效率會特別低，收斂時間很長；

3．對于密度不均勻，聚類間差距很大的數據集效果很差。

最后，送一個基于DBSCAN聚類的笑臉給大家�？梢匀ミ@個網站自行嘗試。

文章到這里就暫時告一段落啦，小伙伴們有沒有收獲滿滿咧？

－－－－－－－－－－－－－－－－－－－ End －－－－－－－－－－－－－－－－－－－