聚类笔记：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 主要参数 min_cluster_size一个群组中样本的最小数量，以便将该群组视为一个簇；小于此大小的群组将被视为噪声min_samples一个点被视为核心点的邻域内的样本数量。这包括点本身。cluster_selection_epsilon一个距离阈值。低于此值的簇将被合并metric计算特征数组中实例之间距离时使用的度量。algorithm

用于计算核心点距离的算法

{“auto”, “brute”, “kdtree”, “balltree”}

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