python - sklearn的凝聚聚类中提取从根到叶的路径

Question

给定由 sklearn.AgglomerativeClustering 创建的凝聚聚类的一些特定叶节点，我试图确定从根节点(所有数据点)到给定叶节点以及每个中间节点的路径步骤(树的内部节点)对应数据点的列表，请参见下面的示例。

在此示例中，我考虑了五个数据点，并重点关注点 3，这样我希望提取从根开始到叶 3 结束的每个步骤中考虑的实例，因此所需的结果是[[1,2,3,4,5],[1,3,4,5],[3,4],[3]]。我如何使用 sklearn 实现这一目标(或者如果使用不同的库无法实现这一点)？

Answer 1

下面的代码首先查找焦点点的所有祖先(使用下面的find_ancestor函数)，然后查找并添加每个祖先的所有后代(find_descendent)。

首次加载和训练数据:

iris = load_iris()
N = 10
x = iris.data[:N]
model = AgglomerativeClustering(compute_full_tree=True).fit(x)

主要代码如下:

ans = []
for a in find_ancestor(3)[::-1]:
    ans.append(find_descendent(a))
print(ans)

在我的例子中输出:

[[1, 9, 8, 6, 2, 3, 5, 7, 0, 4],
 [1, 9, 8, 6, 2, 3],
 [8, 6, 2, 3],
 [6, 2, 3],
 [2, 3],
 [3]]

要理解 find_ancestor 的代码，请记住索引为 i 的非叶节点的 2 个子节点位于 model.children_[i]

def find_ancestor(target):
    for ind,pair in enumerate(model.children_):
        if target in pair:
            return [target]+find_ancestor(N+ind)
    return [ind+N]

递归find_descendent使用mem将其输出保存在内存中，这样它们就不会被不必要地重新计算。

mem = {}
def find_descendent(node):
    global mem
    if node in mem: return mem[node]
    if node<N: return [node]
    pair = model.children_[node-N]
    mem[node] = find_descendent(pair[0])+find_descendent(pair[1])
    return mem[node]