人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

    DBSCAN聚类算法(无师自通)

    < 上一篇:K-Means++算法 下一篇:标签传播算法 >
    K-Means 算法K-Means++ 算法和 Mean Shift 算法都是基于距离的聚类算法,基于距离的聚类算法的聚类结果是球状的簇,当数据集中的聚类结果是非球状结构时,基于距离的聚类算法的聚类效果并不好,然而,基于密度的聚类算法能够较好地处理非球状结构的数据。与基于距离的聚类算法不同的是,基于密度的聚类算法可以发现任意形状的聚类。

    在基于密度的聚类算法中,通过在数据集中寻找被低密度区域分离的高密度区域,将分离出的高密度区域作为一个独立的类别。DBSCAN是一种典型的基于密度的聚类算法。

    基于距离的聚类算法存在的问题

    K-Means 算法,K-Means++ 算法和 Mean Shift 算法都是基于距离的聚类算法,当数据集中的聚类结果是球状结构时,基于距离的聚类算法能够得到比较好的结果,球状结构的聚类结果如图 1 所示。

    球状结构的聚类
    图 1 球状结构的聚类

    然而,除了上述的球状结构的聚类数据外,有一些数据集的聚类结果是非球状的结构,如图 2 所示。

    非球状结构的聚类数据
    图 2 非球状结构的聚类数据

    利用 K-Means++ 聚类算法对图 2 中的数据进行聚类,设置聚类中心的个数为 2,得到如图 3 所示的聚类结果。

    K-Means++算法的聚类结果
    图 3 K-Means++ 算法的聚类结果

    在图 2 中,“+”表示的是最终的两个聚类中心,由图 2 可知,对于图中的非球状结构的聚类数据,基于距离的 K-Means++ 算法并不能得到正确的聚类结果。

    利用 Mean Shift 聚类算法对图 2 中的数据进行聚类,设置高斯核函数中的 h=1 时,得到如图 4 所示的聚类结果。

    Mean Shift算法的聚类结果
    图 4 Mean Shift算法的聚类结果

    在图 4 中,“+”表示最终的聚类中心,与 K-Means++ 算法类似,基于距离的 Mean Shift 算法对图中的非球状聚类结构的数据也不能得到正确的聚类结果。

    从图 2 中,我们可以看出,数据点在图中呈现上下两个弧形,同时,分别在两个弧形中,数据点之间较为密集,而两个弧形彼此之间较为稀疏。由这样的现象,我们猜测是否存在一种方法能够利用样本之间的紧密程度对数据进行聚类?基于密度的聚类便是这样一种利用数据之间的紧密程度来对样本进行聚类的算法。

    DBSCAN算法的基本概念

    DBSCAN 是一种典型的基于密度的聚类算法,在 DBSCAN 算法中,有两个最基本的邻域参数,分别为 ε 邻域和 MinPts。其中 ε 邻域表示的是在数据集 D 中与样本点 xi 的距离不大于 ε 的样本,即:


     
    样本点 xi 的 ε 邻域如图 5 所示。

    xi的ε邻域
    图 5 xi 的 ε 邻域

    在图 5 中,样本点 x 不在样本点 xi 的 ε 邻域内。xi 的密度可由 xi 的 ε 邻域内的点的数量来估计。MinPts 表示的是在样本点 xi 的 ε 邻域内的最少样本点的数目。

    基于邻域参数 ε 邻域和 MinPts,在 DBSCAN 算法中将数据点分为以下三类:
    • 核心点(Core Points):若样本 xi 的 ε 邻域内至少包含了 MinPts 个样本,即 |Nε(xi)|≥MinPts,则称样本点 xi 为核心点。
    • 边界点(Border Points):若样本 xi 的 ε 邻域内包含的样本数目小于 MinPts,但是它在其他核心点的邻域内,则称样本点 xi 为边界点。
    • 噪音点(Noise):指的是既不是核心点也不是边界点的点。

    核心点、边界点和噪音点如图 6 所示。

    核心点、边界点和噪音点
    图 6 核心点、边界点和噪音点

    在图 6 中,设置 MinPts 的值为 9,对应的样本点 x1 的 ε 邻域内包含 11 个样本点,大于 MinPts,则样本点 x1 为核心点。样本点的 x2 在样本点 x1 的 ε 邻域内,且样本点 x2 的 ε 邻域内只包含 8 个样本点,小于 MinPts,则样本点 x2 为边界点。样本点 x3 为噪音点。

    在 DBSCAN 算法中,还定义了如下的一些概念:
    • 直接密度可达。若样本点 xj 在核心点 xi 的 ε 邻域内,则称样本点 xj 从样本点 xi 直接密度可达。
    • 密度可达。若在样本点 xi,1 和样本点 xi,n 之间存在序列 xi,2 ,…,xi,n-1 ,且 xi,j+1 从 xi,j 直接密度可达,则称 xi,n 从 xi,1 密度可达。由密度可达的定义可知,样本点 xi,1,xi,2 ,…,xi,n-1 均为核心点,直接密度可达是密度可达的特殊情况。
    • 密度连接。对于样本点 xi 和样本点 xj ,若存在样本点 xk ,使得 xi 和 xj 都从 xk 密度可达,则称 xi 和 xj 密度相连。

    直接密度可达、密度可达如图 7 所示。

    直接密度可达与密度可达
    图 7 直接密度可达与密度可达

    在图 7 中,设置 MinPts 的值为 9,则样本点 x1 和样本点 x2 为核心点,样本点 x3 为边界点。样本点 x2 在核心点 x1 的 ε 邻域内,则样本点 x2 从样本点 x1 直接密度可达;样本点 x3 在核心点 x2 的 ε 邻域内,则样本点 x3 从核心点 x2 直接密度可达;在样本点 x1 和 x3 之间存在样本点 x2,且样本点 x2 从样本点 x1 直接密度可达,则样本点 x3 从样本点 x1 密度可达。

    DBSCAN 算法原理

    基于密度的聚类算法通过寻找被低密度区域分离的高密度区域,并将高密度区域作为一个聚类“簇”。在 DBSCAN 算法中,聚类“簇”定义为:由密度可达关系导出的最大的密度连接样本的集合。

    若 x 为核心对象,由 x 密度可达的所有样本组成的集合记为:


     
    则 X 满足连接性和最大性的簇。

    DBSCAN 算法流程

    在 DBSCAN 算法中,由核心对象出发,找到与该核心对象密度可达的所有样本形成一个聚类“簇”。DBSCAN 算法的算法流程为:
    1. 根据给定的邻域参数 ε 和 MinPts 确定所有的核心对象;
    2. 对每一个核心对象选择一个未处理过的核心对象,找到由其密度可达的样本生成聚类“簇”;
    3. 重复以上过程;

    现在,让我们利用 Python 实现 DBSCAN 算法的核心部分,即 dbscan 函数。在 dbscan 函数中,需要用到矩阵的相关计算,因此,我们需要导入 numpy 模块:

    import numpy as np

    DBSCAN 算法的具体实现如下所示:
    def dbscan(data, eps, MinPts):
        m = np.shape(data)[0]
        # 区分核心点1,边界点0和噪音点-1
        types = np.mat(np.zeros((1, m)))
        sub_class = np.mat(np.zeros((1, m)))
        # 用于判断该点是否处理过,0表示未处理过
        dealed = np.mat(np.zeros((m, 1)))
        # 计算每个数据点之间的距离
        dis = distance(data)
        # 用于标记类别
        number = 1
       
        # 对每一个点进行处理
        for i in xrange(m):
            # 找到未处理的点
            if dealed[i, 0] == 0:
                # 找到第i个点到其他所有点的距离
                D = dis[i, ]
                # 找到半径eps内的所有点
                ind = find_eps(D, eps)
                # 区分点的类型
                # 边界点
                if len(ind) > 1 and len(ind) < MinPts + 1:
                    types[0, i] = 0
                    sub_class[0, i] = 0
                # 噪音点
                if len(ind) == 1:
                    types[0, i] = -1
                    sub_class[0, i] = -1
                    dealed[i, 0] = 1
                # 核心点
                if len(ind) >= MinPts + 1:
                    types[0, i] = 1
                    for x in ind:
                        sub_class[0, x] = number
                    # 判断核心点是否密度可达
                    while len(ind) > 0:
                        dealed[ind[0], 0] = 1
                        D = dis[ind[0], ]
                        tmp = ind[0]
                        del ind[0]
                        ind_1 = find_eps(D, eps)
                       
                        if len(ind_1) > 1:  # 处理非噪音点
                            for x1 in ind_1:
                                sub_class[0, x1] = number
                            if len(ind_1) >= MinPts + 1:
                                types[0, tmp] = 1
                            else:
                                types[0, tmp] = 0
                               
                            for j in xrange(len(ind_1)):
                                if dealed[ind_1[j], 0] == 0:
                                    dealed[ind_1[j], 0] = 1
                                    ind.append(ind_1[j])
                                    sub_class[0, ind_1[j]] = number
                    number += 1
       
        # 最后处理所有未分类的点为噪音点
        ind_2 = ((sub_class == 0).nonzero())[1]
        for x in ind_2:
            sub_class[0, x] = -1
            types[0, x] = -1
           
        return types, sub_class
    程序中,函数 dbscan 是 DBSCAN 算法的主要部分。dbscan 函数的输入为需要聚类的数据集 data、半径的大小 eps 和半径内的最少的数据点的个数 MinPts,输出为每个节点的类型 types 和每个节点所属的类别 sub_class。

    在 dbscan 函数中,首先初始化一些参数,包括:
    • 每个样本所属的类型 types,其中,在 types 中,1 为核心点,0 为边界点,-1 为噪音点;
    • 每个样本所属的类别 sub_class;
    • 每个样本是否被处理过的 dealed;
    • 样本之间的距离的 dis,函数 distance 的具体实现如下程序所示:
    def distance(data):
        m, n = np.shape(data)
        dis = np.mat(np.zeros((m, m)))
        for i in xrange(m):
            for j in xrange(i, m):
                # 计算i和j之间的欧式距离
                tmp = 0
                for k in xrange(n):
                    tmp += (data[i, k] - data[j, k]) * (data[i, k] - data[j, k])
                dis[i, j] = np.sqrt(tmp)
                dis[j, i] = dis[i, j]
        return dis
    在完成初始化后,对每一个样本,区分其是核心点、边界点还是噪音点。对于核心点,找到其密度可达的点。函数 find_eps 找到与指定样本之间的距离小于或等于 eps 的样本的小标,该函数的具体实现如下所示:
    def find_eps(distance_D, eps):
        ind = []
        n = np.shape(distance_D)[1]
        for j in xrange(n):
            if distance_D[0, j] <= eps:
                ind.append(j)
        return ind
    对于图 2 所示的非球状结构的聚类数据,DBSCAN 算法得到的结果如图 8 所示。

    利用 DBSCAN 处理的非球状的聚类数据
    图 8 利用 DBSCAN 处理的非球状的聚类数据

    从图 8 中可以看出,利用 DBSCAN 算法可以完全将非球状的聚类数据正确划分。对比 K-Means++ 算法的聚类结果和 Mean Shift 算法的聚类结果,基于密度的 DBSCAN 算法能够处理任意形状的聚类问题。
    < 上一篇:K-Means++算法 下一篇:标签传播算法 >