专栏首页Soul Joy Hub密度聚类DBSCAN、HDBSCAN

密度聚类DBSCAN、HDBSCAN

密度聚类DBSCAN、HDBSCAN

DBSCAN

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合。 在DBSCAN算法中将数据点分为三类:

  • 核心点(Core point)。若样本??的?邻域内至少包含了MinPts个样本,即??(??)≥??????,则称样本点??为核心点。
  • 边界点(Border point)。若样本??的?邻域内包含的样本数目小于MinPts,但是它在其他核心点的邻域内,则称样本点??为边界点。
  • 噪音点(Noise)。既不是核心点也不是边界点的点

1、算法的流程

  • 根据给定的邻域参数Eps和MinPts确定所有的核心对象
  • 对每一个核心对象
    • 选择一个未处理过的核心对象,找到由其密度可达的的样本生成聚类“簇”
  • 重复以上过程

伪代码:

(1) 首先将数据集D中的所有对象标记为未处理状态  

(2) for(数据集D中每个对象p) do  

(3)    if (p已经归入某个簇或标记为噪声) then  

(4)         continue;  

(5)    else  

(6)         检查对象p的Eps邻域 NEps(p) ;  

(7)         if (NEps(p)包含的对象数小于MinPts) then  

(8)                  标记对象p为边界点或噪声点;  

(9)         else  

(10)                 标记对象p为核心点,并建立新簇C, 并将p邻域内所有点加入C  

(11)                 for (NEps(p)中所有尚未被处理的对象q) do  

(12)                       检查其Eps邻域NEps(q),若NEps(q)包含至少MinPts个对象,则将NEps(q)中未归入任何一个簇的对象加入C;  

(13)                 end for  

(14)        end if  

(15)    end if  

(16) end for

2、优点

  • 相比K-Means,DBSCAN 不需要预先声明聚类数量。
  • 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。
  • 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。
  • 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。

3、缺点

  • 当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差,因为这种情况下参数MinPts和Eps选取困难。
  • 如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
  • 在两个聚类交界边缘的点会视乎它在数据库的次序决定加入哪个聚类,幸运地,这种情况并不常见,而且对整体的聚类结果影响不大(DBSCAN*变种算法,把交界点视为噪音,达到完全决定性的结果。)
  • 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值eps,邻域样本数阈值MinPts联合调参,不同的参数组合对最后的聚类效果有较大影响。

HDBSCAN聚类

1、空间变换

所谓的空间变换,就是我们用互达距离来表示两个样本点之间的距离。这样会使得,**密集区域的样本距离不受影响,而稀疏区域的样本点与其他样本点的距离被放大。这增加了聚类算法对散点的鲁棒性。**空间变换的效果显然取决于K的选择,当K较大时,会使得核心距离变大,所以互达距离也变大,这样会有更多样本点被分配到稀疏区域。即更多点将被视为散点。

2、建立最小生成树

我们可将数据看作一个加权图,其中数据点为顶点,任意两点之间的边的权重为这些点之间的互达距离。对图像进行分裂。最终图的变化过程是:从完全图到极小连通子图。HDBSCAN使用最小生成树算法:

3、层次聚类结构

  • 第一步:将树中的所有边按照距离递增排序
  • 第二步:然后依次选取每条边,将边的链接的两个子图进行合并。

这样就构建出了聚合树:

可以理解,类似于哈夫曼树的构造,这棵树自上而下数据之间的距离是从大到小的。

4、剪枝

同时进行剪枝,即最小子树做了限制,主要是为了控制生成的类簇不要过小:

  • 第一步:确定最小族大小n
  • 第二步:自上而下遍历聚类树,并在每个节点分裂时:看分裂产生的两个样本子集的样本数是否大于n
    • 如果左右儿子中有一个子结点的样本数< n,我们就直间将该节点删除,并且另一个子节点保留父节点的身份
    • 如果两个子结点中的样本数都<n,那么就将其两个子节点都删除,即当前节点不再向下分裂
    • 如果两个子结点中的样本数都>=n,那么我们进行正常分裂,即保持原聚类树不变。

5、提取簇

经过聚类树的压缩操作,树中已经没有了散点,我现在的任务只是将比较相近的节点合并到一族中去,我们最后选择的簇能够有更好的稳定性。

我们可以这里理解,有一个阈值distance,如上图的红线。用它切割,面最近的节点作为聚类的一个类,而红线上面的聚起来的都是散点。问题是,我们如何知道阈值在哪里?能不能有更好的提取族的方式呢?HDBSCAN定义了一种基于稳定度的提取族方式那么如何来定义树中节点的稳定度呢? 我们先定义一个λ,它是距离的倒数:

对于树中的某个节点定义两个量:λbirth,λdeath λbirth表示:分裂产生当前节点时,distance的倒数。 λdeath表示:当前节点被分裂成两个子结点时,distance的倒数。 λp表示:当前节点(族)下各节点p从前节点(族)分离出去时,distance的倒数。 在这里对λp做下说明,p从聚类族分离出去有两种情况:

  • λp = λdeath时,即该节点(簇)被分裂成两个子结点了
  • λbirth <= λp < λdeath时,即在该之间距离变化中可能切割出散点。此时,原来的节点(簇)并没有分裂成两个子结点,而是直接把散点给移除了。

我们定义稳定度为:

提取簇步骤:

  • 第一步:初始化族

将压缩聚类树的每个叶节点都选定为某个簇。

  • 第二步:自下而上遍历遍历整棵树,并且每一步进行下面操作:

如果当前节点的稳定性小于两个子结点的稳定性总和,那么我们将该节点的稳定性设置为其子节点的稳定性之和。如果当前节点的稳定性大于两个子结点的稳定性总和,那么将当前节点定为某个簇。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DBSCAN密度聚类算法

        DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度...

    刘建平Pinard
  • DBSCAN聚类

    物以类聚,人以群分,平常我们把人和物进行分类,今天来讲一讲如何通过DBSCAN用数据把样本进行聚类。

    阿黎逸阳
  • DBSCAN聚类︱scikit-learn中一种基于密度的聚类方式

    一、DBSCAN聚类概述 基于密度的方法的特点是不依赖于距离,而是依赖于密度,从而克服基于距离的算法只能发现“球形”聚簇的缺点。 DBSCAN的核心思想是从...

    素质
  • 主流机器学习算法简介与其优缺点分析

    机器学习算法的分类是棘手的,有几种合理的分类,他们可以分为生成/识别,参数/非参数,监督/无监督等。

    全球资讯翻译官
  • 机器学习算法分类与其优缺点分析

    机器学习算法的分类是棘手的,有几种合理的分类,他们可以分为生成/识别,参数/非参数,监督/无监督等。 例如,Scikit-Learn的文档页面通过学习机制对算法...

    企鹅号小编
  • 机器学习算法分类与其优缺点分析

    机器学习算法的分类是棘手的,有几种合理的分类,他们可以分为生成/识别,参数/非参数,监督/无监督等。 例如,Scikit-Learn的文档页面通过学习机制对算法...

    机器人网
  • 主流机器学习算法简介与其优缺点分析

    机器学习算法的分类是棘手的,有几种合理的分类,他们可以分为生成/识别,参数/非参数,监督/无监督等。 例如,Scikit-Learn的文档页面通过学习机制对算法...

    WZEARW
  • 20分钟学会DBSCAN聚类算法

    DBSCAN是一种非常著名的基于密度的聚类算法。其英文全称是 Density-Based Spatial Clustering of Applications ...

    lyhue1991
  • Python+sklearn使用DBSCAN聚类算法案例一则

    DBSCAN聚类算法概述: DBSCAN属于密度聚类算法,把类定义为密度相连对象的最大集合,通过在样本空间中不断搜索最大集合完成聚类。 DBSCAN能够在带有噪...

    Python小屋屋主

扫码关注云+社区

领取腾讯云代金券