【数据挖掘】密度聚类DBSCAN讲解及实战应用（图文解释附源码）

港控/mmm° 2023-09-30 18:39 5阅读 0赞

> **需要源码请点赞关注收藏后评论区留言私信~~~**

## 基于密度的聚类 ##

基于划分和聚类和基于层次的聚类往往只能发现凸型的聚类簇，为了更好的发现任意形状的聚类簇，提出了基于密度的聚类算法

## 算法原理 ##

基于密度的聚类算法的主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值 ，就把它加到与之相近的聚类中。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点

基于密度的聚类算法代表算法有：DBSCAN算法、OPTICS算法及DENCLUE算法等

DBSCAN算法涉及2个参数5个定义

2个参数:

Eps: 邻域最大半径

MinPts: 在 Eps 邻域中的最少点数

五个定义如下图所示

![2d66b27484134b5a88a8cb36b3879df4.png][]

定义1（Eps邻域） 给定一个对象 p ，p 的Eps 邻域 NEps（p）定义为以 p 为核心，以Eps为半径的d 维超球体区域，即： 其中，D为d维实空间上的数据集， dist ( p, q)表示D中的2个对象p和q之间的距离。

![717e74256462467b82e8b918c6aeef7b.png][]

定义2（核心点与边界点）对于对象p∈D，给定一个整数MinPts，如果p的Eps邻域内的对象数满足|NEps(p)|≥MinPts ，则称p为(Eps，MinPts ) 条件下的核心点；不是核心点但落在某个核心点的Eps 邻域内的对象称为边界点

![11d03801a4fa40128c236433aa14f1ad.png][]

定义3（直接密度可达） 如图所示，给定 (Eps，MinPts ) ，如果对象 p 和 q 同时满足如下条件： p∈ NEps(q) ； |NEps(q)|≥MinPts （即q是核心点）， 则称对象 p 是从对象 q 出发，直接密度可达的。

![b52dcd8150e14ab988890686ccce982e.png][]

定义4（密度可达）

如图所示，给定数据集D，当存在一个对象链 p1，p2，p3，…，pn， 其中 p1 = q ， p N= p，对于 pi ∈D ，如果在条件(Eps，MinPts ) 下 pi+1从pi 直接密度可达，则称对象p从对象q在条件 (Eps，MinPts )下密度可达。密度可达是非对称的，即p从q密度可达不能推出q也从p密度可达

![e41697d4b28f40d8ad40be5281c40ea2.png][]

定义5（密度相连）

如图所示，如果数据集D中存在一个对象o，使得对象p和q是从o在 (Eps，MinPts )条件下密度可达的，那么称对象p和q在 (Eps，MinPts )条件下密度相连。密度相连是对称的

![2731937f278444f3826f8a16e5e09306.png][]

可视化密度可达 密度不可达等等情况如下

![5fd11930b92b4fcfb6b6742d5cf0abf0.png][]

DBSCAN算法流程图如下

![7a621d593169456d93c68ba4d1463a83.png][]

DBSCAN需要对数据集中的每个对象进行考察，通过检查每个点的参数

邻域寻找聚类，将具有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类

但是，DBSCAN算法对用户设置的参数敏感，Eps和MinPts的设置会影响聚类的效果。针对这一问题，OPTICS（Ordering Points to Identify the Clustering Structure）算法被提出，它通过引入核心距离和可达距离，使得聚类算法对输入的参数不敏感

## DBSCAN算法实现如下 ##

聚类效果如下

![82e091677b36423094e85e7693ba9ab7.png][]

部分代码如下

from sklearn import datasets
    import numpy as np
    import random
    import matplotlib.pyplot as plt
    def findNeighbor(j,X,eps):
        N = []
        for p in range(X.shape[0]):   #找到所有邻域内对象
            temp = np.sqrt(np.sum(np.square(X[j]-X[p])))
    #欧氏距离
            if(temp<=eps):
                N.append(p)
        return N
    def dbscan(X,eps,min_Pts):
        k = -1
        NeighborPts = []      #array,某点领域内的对象
        Ner_Nex for x in range(len(X))] #初始所有点标为未访问
        cluster = [-1 for y in range(len(X))]
        while len(gama)>0:
            j = random.choice(gama)
            gama.remove(j)  #未访问列表中移除
            fil.append(j)   #添加入访问列表
            NeighborPts = findNeighbor(j,X,eps)
            if len(NeighborPts) < min_Pts:
                cluster[j] = -1   #标记为噪声点
            else:
                k = k+1
                cluster[j] = k
                for i in NeighborPts:
                    if i not in fil:
                        gama.remove(i)
                        fil.append(i)
                        Ner_NeighborPts=findNeighbor(i,X,eps)
                        if len(Ner_NeighborPts) >= min_Pts:
                            for a in Ner_NeighborPts:
                                if a not in NeighborPts:
                                    NeighborPts.append(a)
                        if (cluster[i]==-1):
                            cluster[i]=k
        return cluster
    X1, y1 = datasets.make_circles(n_samples=1000, factor=.6,noise=.05)
    X2, y2 = datasets.make_blobs(n_samples = 300, n_features = 2, centers = [[1.2,1.2]], cluster_st
    C = dbscan(X,eps,min_Pts)
    plt.figure(figsize = (12, 9), dpi = 80)
    plt.scatter(X[:,0],X[:,1],c = C)
    plt.show()

**创作不易 觉得有帮助请点赞关注收藏~~~**

[2d66b27484134b5a88a8cb36b3879df4.png]: https://img-blog.csdnimg.cn/2d66b27484134b5a88a8cb36b3879df4.png
[717e74256462467b82e8b918c6aeef7b.png]: https://img-blog.csdnimg.cn/717e74256462467b82e8b918c6aeef7b.png
[11d03801a4fa40128c236433aa14f1ad.png]: https://img-blog.csdnimg.cn/11d03801a4fa40128c236433aa14f1ad.png
[b52dcd8150e14ab988890686ccce982e.png]: https://img-blog.csdnimg.cn/b52dcd8150e14ab988890686ccce982e.png
[e41697d4b28f40d8ad40be5281c40ea2.png]: https://img-blog.csdnimg.cn/e41697d4b28f40d8ad40be5281c40ea2.png
[2731937f278444f3826f8a16e5e09306.png]: https://img-blog.csdnimg.cn/2731937f278444f3826f8a16e5e09306.png
[5fd11930b92b4fcfb6b6742d5cf0abf0.png]: https://img-blog.csdnimg.cn/5fd11930b92b4fcfb6b6742d5cf0abf0.png
[7a621d593169456d93c68ba4d1463a83.png]: https://img-blog.csdnimg.cn/7a621d593169456d93c68ba4d1463a83.png
[82e091677b36423094e85e7693ba9ab7.png]: https://img-blog.csdnimg.cn/82e091677b36423094e85e7693ba9ab7.png