如何将scipy生成的树状图转换为图/树结构以进行计算？

一、直接基于Scipy Linkage矩阵构建树结构 #

Scipy的dendrogram只是可视化工具，层次聚类的核心数据是linkage矩阵——每一行代表一次节点合并，前两列是被合并的节点（叶节点为原始样本索引，合并节点编号为样本数+合并次数），第三列是合并距离，第四列是该节点包含的样本总数。直接基于这个矩阵构建树结构，是Python内计算的最优方案。

1. 自定义TreeNode类实现轻量树结构 #

适合需要灵活遍历、自定义计算的场景：

import numpy as np
from scipy.cluster.hierarchy import linkage

# 生成示例数据（替换为你的数据）
X = np.random.rand(10, 2)
Z = linkage(X, method='ward')  # 生成linkage矩阵

class TreeNode:
    def __init__(self, node_id, left=None, right=None, is_leaf=False, size=1):
        self.id = node_id
        self.left = left
        self.right = right
        self.is_leaf = is_leaf
        self.size = size  # 子树包含的叶节点数量

# 初始化所有叶节点
n_samples = X.shape[0]
nodes = {}
for i in range(n_samples):
    nodes[i] = TreeNode(i, is_leaf=True)

# 根据linkage矩阵构建合并节点
for merge_idx, row in enumerate(Z):
    merged_node_id = n_samples + merge_idx
    left_node = nodes[int(row[0])]
    right_node = nodes[int(row[1])]
    nodes[merged_node_id] = TreeNode(merged_node_id, left=left_node, right=right_node, size=int(row[3]))

# 根节点为最后一个合并的节点
root = nodes[n_samples + len(Z) - 1]

2. 用NetworkX构建图结构 #

适合需要图论操作（如子图提取、路径遍历）的场景：

import networkx as nx

G = nx.DiGraph()

# 添加叶节点
for i in range(n_samples):
    G.add_node(i, is_leaf=True, size=1)

# 添加合并节点与边
for merge_idx, row in enumerate(Z):
    merged_node_id = n_samples + merge_idx
    left_id = int(row[0])
    right_id = int(row[1])
    G.add_node(merged_node_id, is_leaf=False, size=int(row[3]))
    G.add_edge(merged_node_id, left_id)
    G.add_edge(merged_node_id, right_id)

# 示例：获取某个节点的所有叶节点
def get_leaf_nodes(node_id):
    leaves = []
    stack = [node_id]
    while stack:
        curr = stack.pop()
        if G.nodes[curr]['is_leaf']:
            leaves.append(curr)
        else:
            stack.extend(G.successors(curr))
    return leaves

二、Newick格式转换方案（适合跨工具交互） #

转Newick是通用树格式，适合和外部树分析工具（如ete3）配合，但如果仅在Python内计算，直接基于linkage构建更轻量。

1. Linkage转Newick字符串 #

def linkage_to_newick(Z, labels=None):
    if labels is None:
        labels = [str(i) for i in range(Z.shape[0]+1)]
    nodes = {}
    # 初始化叶节点
    for i in range(len(labels)):
        nodes[i] = f"{labels[i]}"
    # 构建合并节点
    for merge_idx, row in enumerate(Z):
        merged_id = len(labels) + merge_idx
        left_str = nodes[int(row[0])]
        right_str = nodes[int(row[1])]
        distance = row[2]
        nodes[merged_id] = f"({left_str}:{distance:.2f},{right_str}:{distance:.2f})"
    return nodes[len(nodes)-1] + ";"

# 生成Newick字符串
newick_str = linkage_to_newick(Z)

2. 用ete3解析Newick并计算 #

from ete3 import Tree

tree = Tree(newick_str)
# 获取所有叶节点
all_leaves = tree.get_leaves()
# 找包含叶节点最多的子树
max_subtree = max(tree.get_descendants(), key=lambda x: len(x.get_leaves()))

三、核心计算操作示例 #

• 统计叶节点：自定义树可递归遍历，NetworkX用上述get_leaf_nodes函数，ete3用tree.get_leaves()
• 计算子树大小：自定义树取node.size，NetworkX取G.nodes[node_id]['size']，ete3用len(node.get_leaves())
• 寻找最大子树：按子树叶节点数排序取最大值；或用fcluster切割树后找最大聚类：

from scipy.cluster.hierarchy import fcluster

# 按距离阈值切割树，得到聚类结果
clusters = fcluster(Z, t=1.0, criterion='distance')
# 统计各聚类大小，找最大聚类
cluster_sizes = np.bincount(clusters)
max_cluster_size = cluster_sizes.max()
max_cluster_idx = np.argmax(cluster_sizes)

内容的提问来源于stack exchange，提问作者gennifer montaño rodriguez