简单一文助你理解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 －－－－－－－－－－－－－－－－－－－