了解用于剪切树状图的DynamicTreeCut算法
Sil*_*ler 11 algorithm cluster-analysis hierarchical-clustering dendrogram unsupervised-learning
树形图是与层次聚类算法一起使用的数据结构,其在树的不同"高度"处对聚类进行分组 - 其中高度对应于聚类之间的距离度量.
在从某些输入数据集创建树形图之后,通常还需要确定"切割"树状图的位置,这意味着选择高度使得仅低于该高度的聚类被认为是有意义的.
在剪切树状图的高度并不总是很清楚,但是存在一些算法,例如DynamicTreeCut算法,它试图以编程方式从树形图中选择有意义的聚类.
看到:
https://stats.stackexchange.com/questions/3685/where-to-cut-a-dendrogram
所以我一直在阅读DynamicTreeCut算法,以及该算法的Java实现.从逐步分解正在发生的事情的角度来看,我理解算法是如何工作的以及它在做什么.但是,我无法理解这个算法是如何做任何有意义的事情的.我想我在这里缺少一些关键概念.
通常,该算法在树形图上迭代"高度序列".我不确定,但我认为"高度序列"只是指树状图沿Y轴的值,即簇连接发生的各种高度.如果是这种情况,我们可以假设"高度序列"按升序排序.
然后算法要求获取"参考高度",l并从输入"高度序列"中的每个高度减去它.这为您提供了高度序列中D每个高度h[i]与参考高度之间差异()的向量l.
然后算法尝试找到"转换点" - 它们是差异向量中的点,其中D[i] > 0和D[i+1] < 0.换句话说,差异向量中的点,其中差值从正变为负.
就在这里,我完全迷失了.我不明白这些过渡点是如何有意义的.首先,我的理解是输入高度序列H只是树形图Y轴上的值.因此,高度序列H应按升序排列.因此,如何在差异向量中找到一个从正向过渡到负向的点？
例如:
假设我们的输入高度序列H是{1, 1.5, 2, 2.5, 3, 7, 9},我们的参考值l是平均高度(将是3.7).因此,如果我们D通过l从每个高度中减去来创建差异向量H,我们就会得到{-2.7, -2.2, -1.7, -1.2, -0.7, 3.3, 5.3}.很明显,这里没有过渡点,也没有过,因为差异向量中没有点D[i] > 0和D[i+1] < 0,因为高度序列H是按升序排列的.
很明显,我完全误解了这个算法的基本原理.也许我不明白"高度序列"是什么意思.我假设它只是来自树形图的Y轴上的值,但显然对于算法实际上做的事情没有任何意义.不幸的是,作者并没有真正解释"树状图高度序列"的含义,它似乎也不是数据科学界使用的某种标准术语.
那么可以解释一下DynamicTreeCut算法在这里尝试实现的内容,以及我理解错误的地方吗？
我完全同意你对论文和算法的理解。我得出了和你一样的结论。
我所提供的是猜测。但我对此很有信心。
- 该论文指出，断点为您提供了集群之间的限制。两个连续的断点定义一个簇
直接的结论是您不能将 H 作为高度的有序列表。相反，它应该是您重新排序可视化点时的高度，即“使得结果图中的线不交叉”
在该示例中，H 将变为 (0.70, 0.35, 0.90, 0.45, 0.77, 0.40, 0.30, 0.55, 0.05)。澄清一下，第一个条目 0.70 是第一个点和第二个点（此处称为 3 和 7）之间的合并线的高度。请注意，可视化不是唯一的，但最终算法的结果将是唯一的。
- 断点和转换被定义为 0 线上方的一组连续点。
结论：因为在簇内，合并高度较低，并且簇的 Hl 值为正，因此您希望一大堆低合并高度（即：簇）位于 0 线上方。因此，不要使用合并高度，而是使用负值
在本例中，H 将变为 (-0.70, -0.35, -0.90, ...)。
让我们尝试一下我的假设，得到 l = -0.75
Hl 变为 (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 的连续组才形成簇