HDBSCAN

HDBSCAN，一种聚类算法，由 Campello、Moulavi 和 Sander 发明。它通过将 DBSCAN 转化为层次聚类算法，然后采用一种基于聚类稳定性的方法来提取扁平聚类，从而扩展了原始算法。本笔记旨在概述该算法的运行和原理。与 HDBSCAN 的研究不同，我将不提及 DBSCAN 来解释它。相反，我将讨论我个人更喜欢的理解该算法的方式，这种方式更符合鲁棒性单链接加扁平聚类提取。

接下来需要一些信息。数据量应该相对较小，以便观察和创建信息丰富的示例。最好有多个不同类型的集群。此时描述 HDBSCAN 的最简单方法是使用它，然后逐步回顾所发生的步骤，并解释每一步正在发生的事情。现在，让我们开始吧。

数据已被聚类，究竟发生了什么？它可以分为几个步骤。

• 根据密度和稀疏性调整区域。
• 创建距离加权图的最小生成树。
• 创建聚类的连通分量层次结构。
• 根据最小的集群大小，压缩集群层次结构。
• 从压缩树中移除稳定的集群。

转换空间

通过在稀疏噪声的海洋中寻找更高密度的岛屿来定位聚类，并且至关重要的是假设噪声存在，因为真实数据是混乱的，包含异常值、损坏数据和噪声。单链接聚类是聚类方法的基本组成部分，它可能非常容易受到噪声的影响：一个错误放置的噪声数据点可以充当岛屿之间的桥梁，将它们连接在一起。显然，我们希望我们的算法能够抵抗噪声；因此，在执行单链接方法之前，我们必须弄清楚如何“降低海平面”。

在不先聚类的情况下，如何描述“陆地”和“海洋”？只要我们能估计出低密度区域的密度，就可以称它们为“海洋”。使我们的聚类核心对噪声的抵抗力稍强是这里的主要目标；精确地分离“陆地”和“海洋”并不是结果；相反，这只是聚类过程的第一步。因此，因为“海洋”已被识别，我们希望降低海平面。在实际中，这包括增加“海洋”点与“陆地”之间的距离。

以极低的成本估算密度的最简单方法是找到到第 k 个最近邻的距离。如果我们有距离矩阵，我们可以很容易地读出它，我们很快就会需要它；如果没有，kd-树在这种查询中效果很好，前提是我们的度量受支持且维度较小。为了形式化，我们可以称之为为点 x 定义的核心距离，并根据 DBSCAN、LOF 和 HDBSCAN 的文献来表示它。我们现在需要一种分散低密度点（相应的大核心距离）的方法。

其中 a 和 b 之间的初始度量距离表示为 d(a,b)。但在此度量下，密集点（核心距离低）之间的距离保持不变。因此，稀疏的“海洋”位置被分散开，从而“降低了海平面”，而“陆地”则不受影响。请注意，这显然取决于 k 的值；更高的 k 值将更多的点解释为属于“海洋”。使用图片可以让一切更清晰，所以我们使用 k=5。

• 选择另一个位置，我们可以用一组新的邻居（其中一个甚至可能是我们最初选择的那个）重复此过程。
• 为了增加安全性，我们可以使用一个半径略有不同、选择六个最近邻的圆来重复第三次。
• 现在，如果我们想知道绿点和蓝点之间的相互可达性距离，我们可以通过放置一个指示它们之间距离的箭头来开始。
• 由于绿圆的核心比蓝圆远，它穿过蓝圆而不穿过绿圆。由于以绿点为起点最容易可视化，因此我们必须将蓝点和绿点之间的相互可达性距离指定为较大，等于绿圆的半径。
• 相反，由于相互可达性距离（即距离箭头穿过两个圆）高于任一核心距离，因此它仅仅是红点和绿点之间的距离。
• 相互可达性距离作为一种变换，通常在使单链接聚类更接近我们所取点的真实密度分布的层次结构方面效果很好。底层理论支持这一点。

构建最小生成树。

现在我们有了数据上新的相互可达性度量，我们希望开始在密集数据上定位岛屿。自然，岛屿之间的密度存在差异，密集区域可以位于不同的地方。我们将在概念上通过以下方式进行：将数据视为一个加权图，数据点是顶点，连接任意两点的任何连接都根据其相互可达性距离加权。

在不同的阈值级别下，我们最终将拥有一个从完全连接到完全不连接的连通分量层次结构。

这实际上非常昂贵，因为我们希望避免执行 n^2 次连通分量算法，而有 n^2 条边。正确的做法是找到最小的边集，该边集在移除集合中的一条边时会导致组件断开。然而，我们还需要更多；这个集合必须安排好，以便没有较低权重的边能够连接这些部分。值得庆幸的是，图论为我们提供了这一点：图的最小生成树。

Prim 算法允许我们相对快速地构建最小生成树。我们通过一次添加一条边来构建树，每当它连接一个当前不在树中的顶点时，就添加权重最低的边。下面显示了 HDBSCAN 构建的树；请注意，与图中的纯距离相比，这是相互可达性距离的最小生成树。在这种情况下，k 值为 5。

如果数据存储在度量空间中，我们可以通过使用 Dual Tree Boruvka 等技术来更快地构建最小生成树。

构建层次聚类。

下一步是将最小生成树转换为连通分量层次结构。完成此操作的最简单方法是按相反的顺序进行：首先，按距离（升序）对树的边进行排序，然后，对于每条边，通过迭代它们来创建新的合并的集群。找到每条边将连接的两个集群是这里唯一的挑战。但是，使用并查集数据结构可以轻松完成。结果可以看作是一个树状图，如下所示。

至此，我们已经达到了鲁棒性单链接的极限。然而，我们确实想要一组扁平的集群；集群层次结构很好，但需要纠正。我们可以选择上述图中的集群，横线与之相交。DBSCAN 在实践中通过将切割水平的任何单例集群归类为噪声来有效地完成此功能。

问题是我们如何确定在哪里画线。DBSCAN 将其留作一个（非常违反直觉的）参数。更糟糕的是，我们只希望处理单一的固定密度级别，因为任何切割线的选择都是切割相互可达性距离的选择。

理想情况下，我们可以通过对树进行不同的切割来选择要包含的集群。HDBSCAN 的后续步骤从这里开始，使其与鲁棒性单链接区分开来。

压缩集群树。

将庞大而复杂的集群层次结构压缩成一棵较小的树，并在每个节点上附加一点额外信息，这是集群提取过程的第一步。关键的见解是，与其将集群分裂视为两个独立集群的分裂，不如将其视为一个“失去点”的持久集群。从上面的层次结构可以看出，集群分裂通常是一个或两个点从集群中分离出来。

我们需要一个最小集群大小的概念，我们将其作为 HDBSCAN 参数提供，以便具体化这一点。一旦确定了最小集群大小，我们就可以沿着层次结构进行，并在每次分裂时询问新形成的集群是否少于最小集群大小。如果点数少于最小集群大小，我们将其标记为“从集群中脱落”，并让较大的集群保留父集群的集群标识。我们还记录了哪些点“从集群中脱落”以及何时发生的距离值。

相比之下，我们将分裂成至少等于最小集群大小的两个集群视为合法的集群分裂，并允许该分裂保留在树中。在遍历整个层次结构并执行此操作后，我们得到一棵节点很少的更小的树。每个节点包含有关该节点处集群大小在不同距离下如何减小信息。这可以显示为类似于之前树状图的树状图，线条的宽度再次表示集群中的点数。

这一次，然而，随着点从集群中脱落，宽度会随着线的整个长度而变化。对于我们的数据，最小集群大小为 5，结果如下。

特别是当处理像我们用于测试数据集的简单聚类问题时，这要容易得多，也更容易处理。不过，我们仍然需要选择要用于扁平聚类的集群。您应该能够从上面的图表中获得一些关于如何处理此问题的想法。

提取集群。

我们自然会倾向于持久且长期的集群；短期的集群很可能只是单链接策略的副产品。从上一张图中，我们可以得出结论，我们应该选择墨迹区域最大的集群。为了创建扁平聚类，我们必须添加一个条件，即一旦选择了某个集群，就不能选择该集群的任何后代集群。实际上，HDBSCAN 执行了这种内在的、需要做什么的感知。当然，要将其变成一个实际的算法，我们必须将所有内容形式化。

声明所有叶节点都属于选定的集群。然后，按照相反的拓扑排序顺序向上遍历树。如果子集群的稳定性之和大于集群本身的稳定性，我们就将集群稳定性设为子集群稳定性的总和。另一方面，如果集群的稳定性大于其子集群的稳定性的总和，我们就将该集群指定为选定集群，并取消选择其所有后代。当我们到达根节点后，我们将当前选定的集群集合称为我们的扁平聚类并返回它。

好了，这部分内容冗长且技术性强，但实际上，它只是遵循我们之前描述的“选择树状图中小墨迹总面积最大的集群”的过程，并加上后代限制。使用这种方法，我们可以选择压缩树状图中的集群，并获得您期望的结果。

使用 sklearn API，一旦获得集群，聚类标签的生成就是一个简单的过程。任何不在选定集群内的点都被视为噪声，并被指定为 -1。但是，我们可以做得更多。通过对值进行归一化（使它们在 0 到至少 1 的范围内），我们可以使用每个因子 p 在每个集群中的 lambda_p 来计算每个因子在集群内的成员能量。这由 hdbscan 库作为聚类器对象的 probabilities_ 属性返回。

因此，在我们获得标签和成员强度后，我们可以创建常规图，通过根据集群标签对点的颜色进行去饱和处理，并使未聚类的点呈纯灰色。

这就是 HDBSCAN 的运作方式。尽管算法中有许多活动部件，但每个部件都相对简单，并且尽管该技术表面上很复杂，但仍然可以很好地进行优化。通过对 HDBSCAN 的直觉有了更好的掌握，以及对其一些实现细节的了解，您将受到启发尝试一下。该库仍在不断发展，并将为未来的概念奠定基础，例如一种新的半监督聚类方法和一种几乎无参数的持久性密度聚类算法。

HDBSCAN 是一种基于密度的聚类技术。与 k-means 等传统聚类算法相比，HDBSCAN 可以发现不同大小和形状的集群，并且不需要预先指定集群数量。这是 HDBSCAN 工作原理的摘要。

估算密度

算法首先估算数据点的密度。它通过计算数据点之间的相互可达性距离来做到这一点。

构建 MST（最小生成树）

基于相互可达性距离，该技术从成对距离矩阵中创建一个最小生成树。

简化树

之后，定义了一个集群层次结构，以简化树。层次结构有助于在不同粒度级别上识别集群。

聚类

最终，算法从层次结构中提取集群。未分配给任何集群的点被视为噪声或异常值。通过在不同级别分割层次结构来创建集群。

结论

总之，HDBSCAN（具有噪声的应用的层次基于密度的空间聚类）是一种强大的聚类方法，在处理噪声或异常值、处理具有不同密度的**数据以及自动计算集群数量方面表现出色。为了在使用 HDBSCAN 时正确理解聚类结果，考虑数据的特性、试验参数以及可视化结果至关重要。上述方法在探索性数据分析、异常检测以及数据结构指定不佳或未知的情况下尤其有用。