聚类笔记：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 聚类树节点稳定性

首先定义一个λ，表示距离的倒数 $\lambda=\frac{1}{distance}$
对于树中的某个节点（一个节点里有一堆样本点）定义两个量：
- $\lambda_{birth}$ :分裂产生当前节点时，对应断开边长度的倒数（分类当前节点的父节点）
- $\lambda_{death}$ ：当前节点被分裂成两个子结点时，对应断开边长度的倒数。
- 分裂父节点时，断开边长度肯定比分裂当前点的时候长，所以倒数正好反过来
  - 也即： $\lambda_{birth}$ < $\lambda_{death}$
之后的我就没看懂了。。。可以参考【机器学习】密度聚类算法之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 主要参数

min_cluster_size	一个群组中样本的最小数量，以便将该群组视为一个簇；小于此大小的群组将被视为噪声
min_samples	一个点被视为核心点的邻域内的样本数量。这包括点本身。
cluster_selection_epsilon	一个距离阈值。低于此值的簇将被合并
metric	计算特征数组中实例之间距离时使用的度量。
algorithm	用于计算核心点距离的算法 {“auto”, “brute”, “kdtree”, “balltree”}