简单一文助你理解DBSCAN是什么

一般说到聚类算法，大多数人会想到k－means算法，但k－means算法一般只适用于凸样本集，且需要预先设定k值，而DBSCAN聚类既可以用于凸样本集，也可以用于非凸样本集，也不需要提前设定簇族数。关于凸样本集的解释如下图所示。

关于DBSCAN聚类，它是基于密度的聚类，一般通过样本间的紧密程度来进行聚类，将紧密相连的一类样本化为一类，直至遍历所有样本点。

而DBSCAN聚类有下面几个定义。

1．ε－邻域：有一个样本点x1，以x1为圆心，半径为ε的一个范围

2．min＿sample（最小样本点数）：在样本点x1的ε－邻域内的所有样本点总数n；如果n＞＝min＿sample，样本点成为核心点，否则为非核心点。而非核心又分为边界点和噪声点。他们的区别在于其ε－邻域内是否存在核心点，如果存在则为边界点，否则为噪声点。

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”上面三种算法中做权衡，选择一个拟合最好的最优算法。

leaf＿size：使用“ball＿tree”或“kd＿tree”时，停止建子树的叶子节点数量的阈值

p：只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p＝1为曼哈顿距离， p＝2为欧式距离。如果使用默认的欧式距离不需要管这个参数。

n＿jobs ：CPU并行数，若值为 －1，则用所有的CPU进行运算

DBSCAN聚类的优缺点

优点：

可以很好的发现噪声点，但是对其不敏感；

可以对任意形状的稠密数据进行聚类；

缺点：

1．需要设定min＿sample和eps；不同的组合差别非常大；

2．数据量很大时，效率会特别低，收敛时间很长；

3．对于密度不均匀，聚类间差距很大的数据集效果很差。

最后，送一个基于DBSCAN聚类的笑脸给大家。可以去这个网站自行尝试。

文章到这里就暂时告一段落啦，小伙伴们有没有收获满满咧？

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