层次聚类树状图中的节点索引

Question

我正在寻找注释层次聚类 dendrogram, but I have some trouble associating the node indices produced by scipy.cluster.hierarchy.dendrogram when plotting, to the node indices in the original linkage matrix (e.g. produced with scipy.cluster.hierarchy.linkage)。

例如，假设我们有以下示例（改编自此 SO question），

import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt
%matplotlib inline

# generate two clusters: a with 10 points, b with 5:
np.random.seed(1)
a = np.random.multivariate_normal([10, 0], [[3, 1], [1, 4]], size=[10,])
b = np.random.multivariate_normal([0, 20], [[3, 1], [1, 4]], size=[5,])
X = np.concatenate((a, b),)
Z = linkage(X, 'ward')
# make distances between pairs of children uniform 
# (re-scales the horizontal (distance) axis when plotting)
Z[:,2] = np.arange(Z.shape[0])+1 

def plot_dendrogram(linkage_matrix, **kwargs):

    ddata = dendrogram(linkage_matrix, **kwargs)
    idx = 0
    for i, d, c in zip(ddata['icoord'], ddata['dcoord'], 
                       ddata['color_list']):       
        x = 0.5 * sum(i[1:3])
        y = d[1]
        plt.plot(y, x, 'o', c=c)
        plt.annotate("%.3g" % idx, (y, x), xytext=(15, 5),
                             textcoords='offset points',
                             va='top', ha='center')
        idx += 1
plot_dendrogram(Z, labels=np.arange(X.shape[0]),
                truncate_mode='level', show_leaf_counts=False, 
               orientation='left')

生成以下树状图：

原始X矩阵有(X.shape[0] == 15)个样本，纵轴上的刻度标签对应每个树叶的样本id。每个节点的数字是 dendrogram 函数返回的该节点的 ID。现在，如果我们查看原始链接矩阵，第一个两列给出每个树节点的子节点，

print(Z[:,:2].astype('int'))
  [[ 0  3]
   [ 1  8]
   [ 6 16]
   [ 2  5]
   ...
   [22 24]
   [23 25]
   [26 27]]

例如，链接矩阵中的节点 0 有子叶 [0, 3]，但在上面的树状图上它被标记为数字 9。同样，节点 1 被标记为数字 4，等等

我想知道找到这两个指数之间对应关系的最简单方法是什么？我查看了 dendrogram 函数，但没有看到任何简单的方法（特别是如果我们将树状图截断到某个级别（例如 truncate_mode='level', p=2）...

注意：我实际上使用的是sklearn.cluster.AgglomerativeClustering but that doesn't really matter for this question (as illustrated in this github issue)给出的链接矩阵。

注2：或者，如果有一种方法可以计算每个树状图节点的叶子列表，这也可以解决我的问题。

Answer 1

我可以从发布的 material 中推断出的是我希望您已经注意到的事情：

链接矩阵节点按聚类顺序编号。这原始节点为 0-14。 [0 3] 成为节点 15，[1 8] 成为节点 16， [6[1 8]]是节点17等
树状图节点从根开始编号，深度优先，上（右）分支在左（下）之前，标签 N-1 到 0。
左右由链接矩阵中的列决定。

链接矩阵有2N+1行：N+1个原始节点和N个聚类。要重建树状图标签，请从矩阵的最后一行开始，[26 27]。这得到标签 N-1，或 13。在右侧节点（第 1 列）上重复出现，然后在左侧（第 0 列）上重复出现。每次分配标签值时递减它。

够清楚了吗？

递归深度对你来说是个问题？对于 N 个节点，树的深度不应超过 log2(N)，对于一百万个节点，树的深度不应超过 22-25。您的运行-time 堆栈无法处理？我的默认是一千

无论如何，并不难转换为迭代。从根节点开始创建一堆未解析的节点。

stack = [root]
while stack is not empty:
    node = stack.pop()
    stack.push (node.right)
    stack.push (node.left)
    process node  # assign node number, etc.

这使得维护节点计数器变得更加容易，因为它现在是一个局部变量。另请注意，这是一个基本的图形搜索算法："While we have nodes, grab the next one on the list, push its neighbors onto the list (but check to see whether each one is already handled), and process the current node."

对于深度优先，使用堆栈；对于广度优先，使用队列。

Answer 2

我发现的另一种解决方案是使用图中的几何坐标从树状图（_DendrogramChildren class here¹ 中提供的代码）计算给定节点的所有 children。然后因为每个节点都有一个唯一的列表children，我们可以将图中的节点索引与链接矩阵的节点索引相关联。

但是这个解决方案并不令人满意（使用图中节点的坐标），不能很好地缩放并且不适用于截断的树状图。上面@Prune提出的方案比较合适

¹ 不是 re-posting 因为它太长了

层次聚类树状图中的节点索引

Node indexing in hierarchical clustering dendrograms

python

machine-learning

tree

scipy

cluster-analysis