如何基于Linkage Matrix获取每个叶节点的相邻节点？

借助Python的scipy.cluster.hierarchy模块，我们可以将Linkage Matrix转换为ClusterNode树形结构，然后通过遍历树节点的父子关系，提取每个叶节点的相邻节点（即与该叶节点最早被合并到同一簇的所有其他叶节点）。

具体实现步骤 #

1. 转换树形结构：用to_tree方法把聚类链接矩阵转换成树形节点结构。
2. 建立映射关系：构建叶节点ID与名称的双向映射，同时记录每个节点的父节点。
3. 提取相邻节点：对每个叶节点，找到其直接父节点，收集该父节点下所有其他叶节点，即为该节点的相邻节点。

代码实现 #

from scipy.cluster.hierarchy import to_tree

def get_leaf_descendants(node):
    """获取当前节点下所有的叶节点ID"""
    if node.is_leaf():
        return [node.id]
    return get_leaf_descendants(node.left) + get_leaf_descendants(node.right)

def get_adjacent_nodes(linkage_matrix, leaf_names):
    """
    输入：
        linkage_matrix: 聚类生成的Linkage Matrix
        leaf_names: 叶节点名称列表，顺序与Linkage Matrix中叶节点索引一致
    输出：每个叶节点的相邻节点字典
    """
    root_node = to_tree(linkage_matrix)
    # 建立ID与名称的双向映射
    id_to_name = {idx: name for idx, name in enumerate(leaf_names)}
    name_to_id = {name: idx for idx, name in enumerate(leaf_names)}
    
    # 遍历树，记录每个节点的父节点
    parent_map = {}
    def traverse_tree(node, parent):
        parent_map[node.id] = parent
        if not node.is_leaf():
            traverse_tree(node.left, node)
            traverse_tree(node.right, node)
    traverse_tree(root_node, None)
    
    adjacent_dict = {}
    for name in leaf_names:
        leaf_id = name_to_id[name]
        parent = parent_map[leaf_id]
        # 处理只有单个节点的极端情况（示例中不存在）
        if not parent:
            adjacent_dict[name] = []
            continue
        # 获取父节点下所有叶节点，排除自身
        all_siblings = get_leaf_descendants(parent)
        adjacent_nodes = [id_to_name[leaf] for leaf in all_siblings if leaf != leaf_id]
        adjacent_dict[name] = adjacent_nodes
    return adjacent_dict

# 示例测试
if __name__ == "__main__":
    # 示例Linkage Matrix（距离值不影响节点结构，仅作演示）
    sample_linkage = [
        [4, 5, 1, 2],   # 合并E(4)和F(5)
        [3, 6, 2, 3],   # 合并D(3)与上一步的簇(6)
        [0, 1, 1, 2],   # 合并A(0)和B(1)
        [2, 7, 3, 4]    # 合并C(2)与上一步的簇(7)
    ]
    leaf_names = ["A", "B", "C", "D", "E", "F"]
    result = get_adjacent_nodes(sample_linkage, leaf_names)
    print(result)
    # 输出符合预期：{'A': ['B'], 'B': ['A'], 'C': ['D', 'E', 'F'], 'D': ['E', 'F'], 'E': ['F'], 'F': ['E']}

说明 #

• 这里的「相邻节点」定义为：在聚类树中与当前叶节点首次被合并到同一父节点下的所有其他叶节点，完全匹配你给出的示例结果。
• 代码中的leaf_names需要与Linkage Matrix中叶节点的索引顺序一一对应，确保映射关系正确。

内容的提问来源于stack exchange，提问作者Peiqin