【机器学习】密度聚类算法之HDBSCAN

时间：2024-03-17 21:51:08

链接

一、概述

  • 先看一下HDBSCAN的具体定义：HDBSCAN – Hierarchical Density-Based Spatial Clustering of Applications with Noise. Performs DBSCAN over varying epsilon values and integrates the result to find a clustering that gives the best stability over epsilon. This allows HDBSCAN to find clusters of varying densities (unlike DBSCAN), and be more robust to parameter selection.
  • 可以知道是DBSCAN算法与基于层次聚类算法结合而来的，其实HDBSCAN算法是对OPTICS算法的一种改进。

  • HDBSCAN算法的具体过程分为以下几步
    • 空间变换
    • 构建最小生成树
    • 构建聚类层次结构(聚类树)
    • 压缩聚类树
    • 提取簇

二、空间变换

  • 核心距离：我们将样本与第k个最近邻样本点的距离称为核心距离，并表示为corek(x)core_k (x)：
    corek(x)=d(x,Nk(x))core_k (x)=d(x,N^k (x))
  • 互达距离:两个样本点的互达距离定义为： dmreach−k(a,b)=max{corek(a),corek(b),d(a,b)}d_{mreach-k} (a,b)=max \{core_k (a),core_k (b),d(a,b)\}在该式中密集点（核心距离较小的点）彼此保持相同的距离，但较稀疏的点被推开，使得其与其他点的距离最少是它的核心距离(比较大)。
  • 空间变换：所谓的空间变换，就是我们用互达距离来表示两个样本点之间的距离。这样会使得，密集区域的样本距离不受影响，而稀疏区域的样本点与其他样本点的距离被放大。这增加了聚类算法对散点的鲁棒性。
  • 这里需要注意的是，空间变换的效果显然取决于kk的选择，当KK较大时，会使得核心距离变大所有相互可达距离变大，这样会有更多样本点被分配到稀疏区域。即更多点将被视为散点。
  • 下图为k=5k=5的三个点的核心距离示意图：
    【机器学习】密度聚类算法之HDBSCAN
  • 蓝点和绿点之间的相互可达距离如下：
    【机器学习】密度聚类算法之HDBSCAN
  • 红点和绿点之间的相互可达距离更大如下：
    【机器学习】密度聚类算法之HDBSCAN

三、建立最小生成树

  • 现在我们在数据上有了一个新的距离度量：互达距离。
  • 我们可将数据看作一个加权图，其中数据点为顶点，任意两点之间的边的权重为这些点之间的互达距离。
  • 现在考虑一个阈值，阈值从高开始逐步降低。删除任何权重超过该阈值的边，对图像进行分裂。最终图的变化过程是：从完全连接到完全不连接。
  • 在实践中，这样逐步减小阈值去分裂图的方法时间复杂度(O(n2))(O(n^2))较高。正确的做法是找到一个最小的边集合，这样从集合中删除任何边都会导致图分裂。这个最小的边集合 就是图的最小生成树。
  • 我们可以通过 Prim 算法非常有效地构建最小生成树树，如下图所示：
    【机器学习】密度聚类算法之HDBSCAN

四、构建聚类层次结构

  • 给定最小生成树，下一步是将其转换为图分裂的层次结构。
  • 这很容易以逆向思维完成这件事：
    • 第一步：将树中的所有边按照距离递增排序
    • 第二步：然后依次选取每条边，将边的链接的两个子图进行合并。
    • 这里唯一困难的部分是确定每条边所关联的两个子图，这个可以通过并查集很好的实现
    • 这个分裂算法有点像哈夫曼树的生成过程。
  • 我们可以将结果视为树状图，如下图所示：
    【机器学习】密度聚类算法之HDBSCAN
  • 上图中的纵轴为距离可以理解为第二部分所说的阈值，当确定某个阈值，就相当于在上图中画一个横线，如下图所示：
    【机器学习】密度聚类算法之HDBSCAN
  • 我们可以将红线下面最近的节点作为聚类的一个类，而红线上面的聚起来的都是散点。这就是 DBSCAN的实现逻辑，问题是，我们如何知道界限在哪里？DBCSCAN只是将其作为一个参数。
  • 上图是一个二叉树结构，每个节点代表的是一个样本子集，最上面的根节点表示的是所有样本点，即整个样本集，每个节点的两条边表示的是当前节点的分裂，每次分裂都是去掉最小生成树的一条边，从上到下，相当于先选择最大的边进行分裂，每次分裂都对应着一个距离，就是所去掉的边的长度。
  • 上面的二叉树称为聚类树

五、压缩聚类树

  • 簇抽取的第一步是将庞大而复杂的聚类树压缩到一个更小的树中。其实质就是去掉散点。
  • 最小族大小：每个族中样本数的最小值。我们将它作为HDBSCAN的一个参数。
  • 压缩聚类树步骤：
    • 第一步：确定最小族大小
    • 第二步：当最小簇大小确定了后，我们就可以自上而下遍历聚类树，并在每个节点分裂时：看分裂产生的两个样本子集的样本数是否大于最小族大小
      • 如果左右儿子中有一个子结点的样本数少于最小族大小，我们就直间将该节点删除，并且另一个子节点保留父节点的身份
      • 如果两个子结点中的样本数都小于最小族大小，那么就将其两个子节点都删除，即当前节点不再向下分裂
      • 如果两个子结点中的样本数都大于最小族大小，那么我们进行正常分裂，即保持原聚类树不变。
  • 在遍历了整个聚类树之后，我们最终得到了一个拥有少量节点的聚类树.如下图所示：
    【机器学习】密度聚类算法之HDBSCAN
    用线的宽度来表示簇中的点数。由于有节点的删除宽度随逐渐变小
  • 图中λλ为距离的倒数，即：λ=1distanceλ=\frac{1}{distance}

六、提取簇

  • 这一步我们需要从压缩的聚类树种提取聚类的族。所谓的提取族就是为压缩聚类树的每个节点打上一个类标签。
  • 这里有一个显而易见的原则：如果你选择了某个节点作为某一族(即给它打上某族的标签)，那么它的子结点都属于这个族。
  • 经过聚类树的压缩操作，树中已经没有了散点，我现在的任务只是将比较相近的节点合并到一族中去，我们最后选择的簇能够有更好的稳定性
  • 那么如何来定义树中节点的稳定性呢？
    • 我们先定义一个λλ，它是距离的倒数： λ=1distanceλ=\frac{1}{distance}
    • 对于树中的某个节点定义两个量：λbirth，λdeathλ_{birth}，λ_{death}
      • λbirthλ_{birth}表示：分裂产生当前节点时，对应断开边长度的倒数。
      • λdeathλ_{death}表示：当前节点被分裂成两个子结点时，对应断开边长度的倒数。
      • 根据定义有:λbirth<λdeathλ_{birth}<λ_{death}
    • 对于每个节点种每个样本点pp定义一个量：λpλ_p
      • λpλ_p表示：样本点pp因为分裂离开该节点时，对应断开边长度的倒数。当前节点分裂使得样本pp离开当前节点有两种情况：
        • 当前节点分裂出的右儿子中有一个子结点的样本数少于最小族大小，这时我们是直间将该节点删除，并且另一个子节点保留父节点的身份，而并且样本pp在被删掉的子结点中，即样本pp是散点，这时λbirth<λp<λdeathλ_{birth}<λ_p<λ_{death}
        • 当前节点分裂出的两个子结点中的样本数都大于最小族大小，这时我们进行正常分裂，这样样本pp进入当前节点的一个子结点。λp=λdeathλ_p=λ_{death}
    • 现在我们将每个节点的稳定性定义为：scluster=∑p∈cluster(λp−λdeath)s_{cluster}=∑_{p∈cluster}(λ_p-λ_{death} )
    • 由上面公式可知：scluster≤0s_{cluster}≤0并且稳定性越大说明该节点中的散点越少。

  • 提取簇步骤：
    • 第一步：初始化族
      • 将压缩聚类树的每个叶节点都选定为某个簇。
    • 第二步：自下而上遍历遍历整棵树，并且每一步进行下面操作：
      • 如果当前节点的稳定性小于两个子结点的稳定性总和，那么我们将该节点的稳定性设置为其子节点的稳定性之和
      • 如果当前节点的稳定性大于两个子结点的稳定性总和，那么将当前节点定为某个簇，并且删除所有子节点。
  • 我们可以通过这个算法选择上面压缩聚类树的聚类，得到下面结果：
    【机器学习】密度聚类算法之HDBSCAN
    不同颜色的圈表示不同的族，上图将样本分为三个族。

  • 我们将聚类产生的散点(即压缩聚类树时删除的节点)标为-1类，
  • 对于每个簇，族中每个样本点PP都有一个λpλ_p；我们将其进行简单地规范化使其取值范围从0到1，用它来度量度样本点pp成员资格的强度，即λpλ_p越大说明样本点pp越接近该族的中心。下图用不同颜色表示不同族，颜色的深浅表示标准的λpλ_p的大小：
    【机器学习】密度聚类算法之HDBSCAN

相关文章