聚类笔记：HDBSCAN

1 算法介绍

• DBSCAN/OPTICS+层次聚类
• 主要由以下几步组成
  • 空间变换
  • 构建最小生成树
  • 构建聚类层次结构(聚类树)
  • 压缩聚类树
  • 提取簇

2  空间变换

• 用互达距离来表示两个样本点之间的距离
  • ——>密集区域的样本距离不受影响
  • ——>稀疏区域的样本点与其他样本点的距离被放大
  • ——>增加了HDBSCAN聚类算法对散点的鲁棒性
• 空间变换的效果取决于ε的选择
  • 当ε较大的时候，核心距离会变大
  • ——>互达距离变化
  • ——>更多样本点被分配到稀疏区域（更多点被视为散点）

2.1 核心距离

• 同OPTICS（算法笔记：OPTICS 聚类-CSDN博客）的核心距离

2.2 互达距离

• 
• 比如下图，蓝点和绿点的互达距离，就是绿点的核心距离（绿线）
  • 
• 红点和绿点的互达距离，就是他们两个点之间的距离（黄线）
  • 

3 建立最小生成树

使用Prim算法生成最小生成树

NTU课程：MAS714（4）：贪心-CSDN博客

4 构建聚类层次结构

• 给定最小生成树，下一步是将其转换为图分裂的层次结构
• 这里用逆向思维完成这件事
  • 第一步：将树中的所有边按照距离递增排序
  • 第二步：然后依次选取每条边，将边的链接的两个子图进行合并。（类似于层次聚类的思路）
• 以下得到的树又称为聚类树

此时如果和层次聚类一样，设置一条distance的阈值

• 我们就可以将红线下面最近的节点作为聚类的一个类，而红线上面的聚起来的都是散点。

但是这样得到的聚类结果，会有很多有很少量节点的簇

——>我们需要压缩聚类树

5 压缩聚类树

通过压缩聚类树，我们可以得到一棵拥有少量节点的聚类树

5.1 具体步骤

• 1，确定最小簇的大小（HDBSCAN的一个参数）
• 2，当最小簇大小确定了后，我们就可以自上而下遍历聚类树，并在每个节点分裂时：看分裂产生的两个样本子集的样本数是否大于最小簇大小
  • 如果左右儿子中有一个子结点的样本数少于最小族大小，我们就直间将该节点删除，并且另一个子节点保留父节点的身份
  • 如果两个子结点中的样本数都小于最小族大小，那么就将其两个子节点都删除，即当前节点不再向下分裂
  • 如果两个子结点中的样本数都大于最小族大小，那么我们进行正常分裂，即保持原聚类树不变。
  • （删除的点都是HDBSCAN视为的噪点）

6 提取簇

• 从压缩的聚类树种提取聚类的簇
  • 为压缩聚类树的每个节点打上一个类标签
• 提取簇的一个原则是：某个节点属于某一个簇，那么他的子节点都属于这个簇
• 经过聚类树的压缩操作，树中已经没有了散点（散点在压缩聚类树的过程中已经被删除）
  • 现在的任务只是将较近的节点合并到一簇中去，使得最后选择的簇能够有更好的稳定性

6.1 聚类树节点稳定性

• 首先定义一个λ，表示距离的倒数
• 对于树中的某个节点（一个节点里有一堆样本点）定义两个量：
  • :分裂产生当前节点时，对应断开边长度的倒数（分类当前节点的父节点）
  • ：当前节点被分裂成两个子结点时，对应断开边长度的倒数。
  • 分裂父节点时，断开边长度肯定比分裂当前点的时候长，所以倒数正好反过来
    • 也即：<
• 之后的我就没看懂了。。。可以参考【机器学习】密度聚类算法之HDBSCAN_hdbscan速度慢-CSDN博客 r

如果有会的同学，欢迎赐教~

7  sklearn实现

class sklearn.cluster.HDBSCAN(
    min_cluster_size=5, 
    min_samples=None, 
    cluster_selection_epsilon=0.0, 
    max_cluster_size=None, 
    metric='euclidean', 
    metric_params=None, 
    alpha=1.0, 
    algorithm='auto', 
    leaf_size=40, 
    n_jobs=None, 
    cluster_selection_method='eom', 
    allow_single_cluster=False, 
    store_centers=None, 
    copy=False)

7.1 主要参数

参考内容： 【机器学习】密度聚类算法之HDBSCAN_hdbscan速度慢-CSDN博客