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

關(guān)于DBSCAN聚類，它是基于密度的聚類，一般通過(guò)樣本間的緊密程度來(lái)進(jìn)行聚類，將緊密相連的一類樣本化為一類，直至遍歷所有樣本點(diǎn)。

而DBSCAN聚類有下面幾個(gè)定義。

1．ε－鄰域：有一個(gè)樣本點(diǎn)x1，以x1為圓心，半徑為ε的一個(gè)范圍

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

3．密度直達(dá)：有樣本點(diǎn)x1位于x2的ε－鄰域內(nèi)，且x2為核心點(diǎn)，則稱x1由x2密度直達(dá)。

4．密度可達(dá)：有樣本點(diǎn)x1位于x2的ε－鄰域內(nèi)，且x1和x2均為核心點(diǎn)，則稱x1和x2密度可達(dá)。

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

上圖中的紅色點(diǎn)為核心點(diǎn)，黑色點(diǎn)為非核心點(diǎn)（包括邊界點(diǎn)和噪音點(diǎn)）。一共有兩組密度可達(dá)，第一組（左邊）有七個(gè)核心點(diǎn)，其集合包括七個(gè)核心點(diǎn)以及各個(gè)ε－鄰域內(nèi)的所有邊界點(diǎn)。第二組（右邊）有五個(gè)核心點(diǎn)，其集合包括五個(gè)核心點(diǎn)以及各個(gè)ε－鄰域內(nèi)的所有邊界點(diǎn)。當(dāng)所有非噪聲點(diǎn)均在不同集合內(nèi)時(shí)，聚類結(jié)束。

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

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

1．遍歷數(shù)據(jù)集，將各個(gè)樣本點(diǎn)間的距離保存到一個(gè)矩陣中；

2．遍歷數(shù)據(jù)集，將所有的核心點(diǎn)，以及各個(gè)核心點(diǎn)鄰域內(nèi)的樣本點(diǎn)找出；

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

4．將所有邊界點(diǎn)分配到離他最近的核心點(diǎn)；

5．直至所有非噪音點(diǎn)完成分配，算法結(jié)束。

python實(shí)現(xiàn)

用的是sklearn庫(kù)自帶的數(shù)據(jù)集－－－make＿circles。散點(diǎn)圖如下。

根據(jù)上面定義的流程，開(kāi)始寫代碼啦。

首先要得到各個(gè)樣本點(diǎn)間的距離：

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

然后找到所有的核心點(diǎn)，以及各個(gè)核心點(diǎn)鄰域內(nèi)的所有樣本點(diǎn)集合。

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．a(chǎn)ppend（j）        if len（ind）＞＝self．min＿sample：            core＿point．a(chǎn)ppend（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．a(chǎn)ppend（i）        core＿point＿core［key］＝o    return core＿point，core＿point＿dict，core＿point＿core其中core＿point是一個(gè)列表，存儲(chǔ)所有的核心點(diǎn)core＿point＿dict是一個(gè)字典，key為核心點(diǎn)，value為該核心點(diǎn)鄰域內(nèi)的所有樣本點(diǎn)集合core＿point＿core是一個(gè)字典，key為核心點(diǎn)，value為該核心點(diǎn)鄰域內(nèi)所有核心點(diǎn)集合

接下來(lái)就是找出密度直達(dá)點(diǎn)集合，也就是在鄰域內(nèi)的核心點(diǎn)集合

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．a(chǎn)ppend（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

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

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（）

最后的結(jié)果圖如下：

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

效果如上所示。而且代碼也只有幾行。代碼復(fù)制于（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（）

關(guān)于DBSCAN這個(gè)函數(shù)有幾個(gè)要注意的地方：

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

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

核心參數(shù)：

eps： float－鄰域的距離閾值

min＿samples ：int，樣本點(diǎn)要成為核心對(duì)象所需要的 ？－鄰域的樣本數(shù)閾值

其他參數(shù)：

metric ：度量方式，默認(rèn)為歐式距離，可以使用的距離度量參數(shù)有：

歐式距離 “euclidean”

曼哈頓距離 “manhattan”

切比雪夫距離“chebyshev”

閔可夫斯基距離 “minkowski”

帶權(quán)重閔可夫斯基距離 “wminkowski”

標(biāo)準(zhǔn)化歐式距離 “seuclidean”

馬氏距離“mahalanobis”

自己定義距離函數(shù)

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

“brute”蠻力實(shí)現(xiàn)

“kd＿tree” KD樹(shù)實(shí)現(xiàn)

“ball＿tree”球樹(shù)實(shí)現(xiàn)

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

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

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

n＿jobs ：CPU并行數(shù)，若值為 －1，則用所有的CPU進(jìn)行運(yùn)算

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

優(yōu)點(diǎn)：

可以很好的發(fā)現(xiàn)噪聲點(diǎn)，但是對(duì)其不敏感；

可以對(duì)任意形狀的稠密數(shù)據(jù)進(jìn)行聚類；

缺點(diǎn)：

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

2．?dāng)?shù)據(jù)量很大時(shí)，效率會(huì)特別低，收斂時(shí)間很長(zhǎng)；

3．對(duì)于密度不均勻，聚類間差距很大的數(shù)據(jù)集效果很差。

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

文章到這里就暫時(shí)告一段落啦，小伙伴們有沒(méi)有收獲滿滿咧？

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