了解用于切割树状图的 DynamicTreeCut 算法
Understanding DynamicTreeCut algorithm for cutting a dendrogram
树状图是一种与层次聚类算法一起使用的数据结构，该算法将聚类分组在树的不同 "heights" - 其中高度对应于聚类之间的距离度量。
从一些输入数据集创建树状图后，找出 "cut" 树状图的位置通常是一个进一步的挑战，这意味着 select 设置一个高度，以便只有低于该高度的簇被认为是有意义的。
并不总是清楚在什么高度切割树状图，但存在一些算法，例如 DynamicTreeCut 算法，它试图以编程方式 select 树状图中有意义的聚类。
参见：
https://stats.stackexchange.com/questions/3685/where-to-cut-a-dendrogram
Cutting dendrogram at highest level of purity
所以我一直在阅读 DynamicTreeCut 算法，以及 Java 实现的算法。我了解算法是如何工作的以及它在做什么，根据对正在发生的事情的逐步细分。但是，我无法理解 这个算法是如何做任何有意义的事情的。我想我在这里遗漏了一些关键概念。
一般来说，算法会从树状图中迭代 "height sequence"。我不确定，但我假设 "height sequence" 仅表示沿树状图 Y 轴的值，即聚类连接发生的各种高度。如果是这样的话，我们可以假设 "height sequence" 是按 升序 .
排序的
然后该算法要求取 "reference height"、l，并从输入 "height sequence" 中的每个高度中减去它。这为您提供了高度序列中每个高度 h[i] 与参考高度 l 之间的差异向量 (D)。
然后算法尝试找到 "transition points" - 这是差异向量中的点，其中 D[i] > 0 和 D[i+1] < 0。换句话说，差向量中差值从正变为负的点。
而在这里我完全迷路了。我不明白这些过渡点怎么会有意义。首先，我的理解是输入高度序列 H 只是树状图 Y 轴上的值。因此高度序列H应该是升序。因此，在我们从 positive 过渡到 negative?
的差异向量中怎么会有一个点？
例如：
假设我们输入的身高序列 H 是 {1, 1.5, 2, 2.5, 3, 7, 9}，我们的参考值 l 是平均身高（即 3.7）。因此，如果我们通过从 H 中的每个高度减去 l 来创建差异向量 D，我们将得到 {-2.7, -2.2, -1.7, -1.2, -0.7, 3.3, 5.3}。很明显这里没有过渡点，也不可能有，因为在 D[i] > 0 和 D[i+1] < 0 的差异向量中没有点，因为高度序列 H 在 升序.
很明显，我完全误解了这个算法的一些基本原理。也许我不明白 "height sequence" 是什么意思。我假设它只是树状图 Y 轴上的值，但显然这对于算法实际执行的操作没有任何意义。不幸的是，作者并没有真正解释 "dendrogram height sequence" 的含义，它似乎也不是数据科学界使用的某种标准术语。
那么可以解释 DynamicTreeCut 算法在这里试图实现什么，以及我的理解哪里出了问题吗？
我完全同意你对论文和算法的理解。我得出了和你一样的结论。
我提供的是猜测。但我对此很有信心。
- 该论文指出，断点为您提供了集群之间的限制。两个连续的断点定义一个簇
直接得出的结论是，您不能将 H 作为高度的有序列表。相反，它应该是您重新排序可视化点时的高度，即 "such that the lines in the resulting plot do not cross"
在示例中，H 将变为 (0.70, 0.35, 0.90, 0.45, 0.77, 0.40, 0.30, 0.55, 0.05)。为澄清起见，第一个条目 0.70 是第一个点和第二个点（此处称为 3 和 7）之间合并线的高度。注意可视化不是唯一的，但是最终算法的结果会是。
- 断点和转换定义为 0 线上方的一组连续点。
结论：因为集群内部的合并高度较低，并且集群的 H-l 值为正，所以您需要一大堆低合并高度（即：集群）站在 0 线上方。因此，不要使用合并高度，而是使用负值
在示例中，H 将变为 (-0.70, -0.35, -0.90, ...)。
让我们试试我的假设，让 l = -0.75
H-l 变为 (0.05, 0.40, -0.15, 0.30, -0.02, 0.35, 0.45, 0.20, 0.70)
并且您有两个定义 3 个簇的转换：(3-7-6)、(1-4) 和 (9-5-8-10-2)。请参阅图片以供参考。感觉挺有道理的。
我还可以得出结论，这是一种非常迂回的说法，它是固定高度的分支切割。请注意，这只是 TreeCutCore，因此所有动态部分都需要完成。老实说，当你意识到它们只是在越来越小的集群上以不同的高度递归调用 TreeCutCore 时，它并没有那么复杂。
此外，作为另一种保险，当你有几个负值一个接一个地出现时，我并没有完全错，这意味着它对应于异常值的单例，这正是节点 54（本文图 5 的你链接）是。几个连续的负值本身不会形成一个簇，它们是彼此完全不同的单例。只有0以上的连续组才能形成一个簇
树状图是一种与层次聚类算法一起使用的数据结构，该算法将聚类分组在树的不同 "heights" - 其中高度对应于聚类之间的距离度量。
从一些输入数据集创建树状图后，找出 "cut" 树状图的位置通常是一个进一步的挑战，这意味着 select 设置一个高度，以便只有低于该高度的簇被认为是有意义的。
并不总是清楚在什么高度切割树状图，但存在一些算法，例如 DynamicTreeCut 算法，它试图以编程方式 select 树状图中有意义的聚类。
参见：
https://stats.stackexchange.com/questions/3685/where-to-cut-a-dendrogram
Cutting dendrogram at highest level of purity
所以我一直在阅读 DynamicTreeCut 算法，以及 Java 实现的算法。我了解算法是如何工作的以及它在做什么，根据对正在发生的事情的逐步细分。但是，我无法理解 这个算法是如何做任何有意义的事情的。我想我在这里遗漏了一些关键概念。
一般来说，算法会从树状图中迭代 "height sequence"。我不确定，但我假设 "height sequence" 仅表示沿树状图 Y 轴的值，即聚类连接发生的各种高度。如果是这样的话，我们可以假设 "height sequence" 是按 升序 .
排序的然后该算法要求取 "reference height"、l，并从输入 "height sequence" 中的每个高度中减去它。这为您提供了高度序列中每个高度 h[i] 与参考高度 l 之间的差异向量 (D)。
然后算法尝试找到 "transition points" - 这是差异向量中的点，其中 D[i] > 0 和 D[i+1] < 0。换句话说，差向量中差值从正变为负的点。
而在这里我完全迷路了。我不明白这些过渡点怎么会有意义。首先，我的理解是输入高度序列 H 只是树状图 Y 轴上的值。因此高度序列H应该是升序。因此，在我们从 positive 过渡到 negative?
例如：
假设我们输入的身高序列 H 是 {1, 1.5, 2, 2.5, 3, 7, 9}，我们的参考值 l 是平均身高（即 3.7）。因此，如果我们通过从 H 中的每个高度减去 l 来创建差异向量 D，我们将得到 {-2.7, -2.2, -1.7, -1.2, -0.7, 3.3, 5.3}。很明显这里没有过渡点，也不可能有，因为在 D[i] > 0 和 D[i+1] < 0 的差异向量中没有点，因为高度序列 H 在 升序.
很明显，我完全误解了这个算法的一些基本原理。也许我不明白 "height sequence" 是什么意思。我假设它只是树状图 Y 轴上的值，但显然这对于算法实际执行的操作没有任何意义。不幸的是，作者并没有真正解释 "dendrogram height sequence" 的含义，它似乎也不是数据科学界使用的某种标准术语。
那么可以解释 DynamicTreeCut 算法在这里试图实现什么，以及我的理解哪里出了问题吗？
我完全同意你对论文和算法的理解。我得出了和你一样的结论。
我提供的是猜测。但我对此很有信心。
- 该论文指出，断点为您提供了集群之间的限制。两个连续的断点定义一个簇
直接得出的结论是，您不能将 H 作为高度的有序列表。相反，它应该是您重新排序可视化点时的高度，即 "such that the lines in the resulting plot do not cross"
在示例中，H 将变为 (0.70, 0.35, 0.90, 0.45, 0.77, 0.40, 0.30, 0.55, 0.05)。为澄清起见，第一个条目 0.70 是第一个点和第二个点（此处称为 3 和 7）之间合并线的高度。注意可视化不是唯一的，但是最终算法的结果会是。
- 断点和转换定义为 0 线上方的一组连续点。
结论：因为集群内部的合并高度较低，并且集群的 H-l 值为正，所以您需要一大堆低合并高度（即：集群）站在 0 线上方。因此，不要使用合并高度，而是使用负值
在示例中，H 将变为 (-0.70, -0.35, -0.90, ...)。
让我们试试我的假设，让 l = -0.75
H-l 变为 (0.05, 0.40, -0.15, 0.30, -0.02, 0.35, 0.45, 0.20, 0.70)
并且您有两个定义 3 个簇的转换：(3-7-6)、(1-4) 和 (9-5-8-10-2)。请参阅图片以供参考。感觉挺有道理的。
我还可以得出结论，这是一种非常迂回的说法，它是固定高度的分支切割。请注意，这只是 TreeCutCore，因此所有动态部分都需要完成。老实说，当你意识到它们只是在越来越小的集群上以不同的高度递归调用 TreeCutCore 时，它并没有那么复杂。
此外，作为另一种保险，当你有几个负值一个接一个地出现时，我并没有完全错，这意味着它对应于异常值的单例，这正是节点 54（本文图 5 的你链接）是。几个连续的负值本身不会形成一个簇，它们是彼此完全不同的单例。只有0以上的连续组才能形成一个簇