Wordnet同义词集最小包含分类树构建：大集合异常问题

问题背景 #

需要为给定的WordNet同义词集构建最小包含分类树：任意两个同义词集都作为其**最低共同上位词（Lowest Common Hypernym）**的子节点。小集合测试能得到正确结果，但处理30个同义词集的大集合时出现分类错误，比如great_grey_owl.n.01（大灰猫头鹰）没有被归类到鸟类节点下。

小集合测试示例 #

输入集合 #

[{'name': 'tench.n.01'},
 {'name': 'goldfish.n.01'},
 {'name': 'great_white_shark.n.01'},
 {'name': 'tiger_shark.n.01'},
 {'name': 'hammerhead.n.03'}]

预期结果 #

{'name': 'fish.n.01',
 'children': [{'name': 'cyprinid.n.01',
   'children': [{'name': 'tench.n.01'}, {'name': 'goldfish.n.01'}]},
  {'name': 'shark.n.01',
   'children': [{'name': 'tiger_shark.n.01'},
    {'name': 'great_white_shark.n.01'},
    {'name': 'hammerhead.n.03'}]}]}

原实现代码 #

# import nltk
# nltk.download('wordnet')
from nltk.corpus import wordnet as wn
from itertools import combinations
import pandas as pd
def synset_tree(synsets):
    # 计算所有叶子节点间的相似度
    synsets_sim = []
    for i,j in combinations(range(len(synsets)),2):
        synsets_sim.append(pd.DataFrame({'syn1':[synsets[i]["name"]], 'syn2':[synsets[j]["name"]], 
        'sim':[wn.synset(synsets[i]["name"]).path_similarity(wn.synset(synsets[j]["name"]))]}))
    synsets_sim = pd.concat(synsets_sim, axis=0)

    while len(synsets)>1:
        synsets_sim = synsets_sim.sort_values('sim', ascending=False)
        
        # 找到相似度最高的两个节点的最低共同上位词
        common_hype = wn.synset(synsets_sim.syn1.iloc[0]).lowest_common_hypernyms(wn.synset(synsets_sim.syn2.iloc[0]))[0].name()
        # 提取两个节点
        syn_dict1 = list(filter(lambda x: x["name"] == synsets_sim.syn1.iloc[0], synsets))[0]
        syn_dict2 = list(filter(lambda x: x["name"] == synsets_sim.syn2.iloc[0], synsets))[0]
        # 从列表中移除这两个节点
        synsets = [syn_dict for syn_dict in synsets if syn_dict not in [syn_dict1, syn_dict2]]
        
        # 计算新上位词与剩余节点的相似度并加入列表
        new_sim = []
        for i in range(len(synsets)):
            new_sim.append(pd.DataFrame({'syn1':[synsets[i]["name"]], 'syn2':[common_hype], 
            'sim':[wn.synset(synsets[i]["name"]).path_similarity(wn.synset(common_hype))]}))
        if len(new_sim) > 0:
            new_sim = pd.concat(new_sim, axis=0)
            new_sim = new_sim[new_sim.sim<1]
            synsets_sim = pd.concat([synsets_sim, new_sim],axis=0)

        # 将被移除的节点作为子节点添加到共同上位词下
        if common_hype == syn_dict1["name"]:
            if syn_dict1.get("children"):
                common_hype = {"name":common_hype, "children":[syn_dict2] + syn_dict1.get("children")}
            else:
                common_hype = {"name":common_hype, "children":[syn_dict2]}
            synsets_sim = synsets_sim[~((synsets_sim.syn1 == syn_dict2["name"]) | (synsets_sim.syn2 == syn_dict2["name"]))]
        elif common_hype == syn_dict2["name"]:
            if syn_dict2.get("children"):
                common_hype = {"name":common_hype, "children":[syn_dict1] + syn_dict2.get("children")}
            else:
                common_hype = {"name":common_hype, "children":[syn_dict1]}
            synsets_sim = synsets_sim[~((synsets_sim.syn1 == syn_dict1["name"]) | (synsets_sim.syn2 == syn_dict1["name"]))]
        elif common_hype in [x["name"] for x in synsets]:
            for i in range(len(synsets)):
                if common_hype == synsets[i]["name"]:
                    if synsets[i]["children"]:
                        synsets[i]["children"] = synsets[i]["children"] + [syn_dict1, syn_dict2]
                    else:
                        synsets[i]["children"] = [syn_dict1, syn_dict2]
        else:
            common_hype = {"name":common_hype, "children":[syn_dict1, syn_dict2]}
            synsets_sim = synsets_sim[~((synsets_sim.syn1 == syn_dict1["name"]) | (synsets_sim.syn2 == syn_dict1["name"]))]
            synsets_sim = synsets_sim[~((synsets_sim.syn1 == syn_dict2["name"]) | (synsets_sim.syn2 == syn_dict2["name"]))]
 

        synsets.append(common_hype)
        

    return synsets[0]

大集合测试（分类异常） #

synsets = [{'name': 'tench.n.01'},
 {'name': 'goldfish.n.01'},
 {'name': 'great_white_shark.n.01'},
 {'name': 'tiger_shark.n.01'},
 {'name': 'hammerhead.n.03'},
 {'name': 'electric_ray.n.01'},
 {'name': 'stingray.n.01'},
 {'name': 'cock.n.05'},
 {'name': 'hen.n.02'},
 {'name': 'ostrich.n.02'},
 {'name': 'brambling.n.01'},
 {'name': 'goldfinch.n.02'},
 {'name': 'house_finch.n.01'},
 {'name': 'junco.n.01'},
 {'name': 'indigo_bunting.n.01'},
 {'name': 'robin.n.02'},
 {'name': 'bulbul.n.01'},
 {'name': 'jay.n.02'},
 {'name': 'magpie.n.01'},
 {'name': 'chickadee.n.01'},
 {'name': 'water_ouzel.n.01'},
 {'name': 'kite.n.04'},
 {'name': 'bald_eagle.n.01'},
 {'name': 'vulture.n.01'},
 {'name': 'great_grey_owl.n.01'},
 {'name': 'european_fire_salamander.n.01'},
 {'name': 'common_newt.n.01'},
 {'name': 'eft.n.01'},
 {'name': 'spotted_salamander.n.01'},
 {'name': 'axolotl.n.01'}]

wow = synset_tree(synsets) # 生成的树出现分类异常，比如great_grey_owl.n.01未归入鸟类节点

问题根源分析 #

1. 相似度计算逻辑缺陷：使用path_similarity作为合并优先级，但该指标仅反映路径长度，未考虑节点在WordNet层级中的实际分类关系。当大集合中跨类别的节点出现较高相似度时，会错误地优先合并非同类节点。
2. 节点移除与相似度清理不彻底：合并两个节点后，旧的相似度记录未完全清除，导致后续循环中可能选取已被移除的节点对，破坏分类逻辑。
3. 共同上位词合并逻辑漏洞：当共同上位词已存在于synsets列表中时，直接追加子节点，但未验证子节点是否属于该上位词的正确分类路径，导致跨类节点被错误归入。

修复后的代码 #

from nltk.corpus import wordnet as wn
from itertools import combinations

def get_hypernym_chain(synset_name):
    """获取同义词集到根节点的完整上位词链"""
    syn = wn.synset(synset_name)
    chain = [syn.name()]
    current = syn
    while current.hypernyms():
        current = current.hypernyms()[0]
        chain.append(current.name())
    return chain

def synset_tree_fixed(synsets):
    # 预处理：将所有节点转换为带上位词链的结构
    nodes = []
    for s in synsets:
        name = s['name']
        nodes.append({
            'name': name,
            'hypernym_chain': get_hypernym_chain(name),
            'children': []
        })

    while len(nodes) > 1:
        max_common_depth = -1
        pair_to_merge = None
        lch = None

        # 遍历所有节点对，找到具有最深共同上位词的节点对
        for i in range(len(nodes)):
            for j in range(i+1, len(nodes)):
                syn1 = wn.synset(nodes[i]['name'])
                syn2 = wn.synset(nodes[j]['name'])
                # 获取最低共同上位词
                common_hypes = syn1.lowest_common_hypernyms(syn2)
                if not common_hypes:
                    continue
                current_lch = common_hypes[0]
                # 计算共同上位词在链中的深度（越靠近叶子节点深度越高）
                depth1 = nodes[i]['hypernym_chain'].index(current_lch.name())
                depth2 = nodes[j]['hypernym_chain'].index(current_lch.name())
                current_depth = min(depth1, depth2)

                # 优先选择最深的共同上位词对应的节点对
                if current_depth > max_common_depth:
                    max_common_depth = current_depth
                    pair_to_merge = (i, j)
                    lch = current_lch.name()

        if not pair_to_merge:
            break

        i, j = pair_to_merge
        node1 = nodes[i]
        node2 = nodes[j]

        # 移除两个节点
        nodes = [nodes[k] for k in range(len(nodes)) if k != i and k != j]

        # 检查LCH是否已存在于当前节点列表中
        existing_node = next((n for n in nodes if n['name'] == lch), None)
        if existing_node:
            # 将两个节点添加为已有LCH的子节点
            existing_node['children'].extend([node1, node2])
        else:
            # 创建新的LCH节点
            lch_node = {
                'name': lch,
                'hypernym_chain': get_hypernym_chain(lch),
                'children': [node1, node2]
            }
            nodes.append(lch_node)

    # 递归整理树结构，移除冗余的中间节点（如果子节点唯一）
    def prune_tree(node):
        while len(node.get('children', [])) == 1:
            child = node['children'][0]
            node['name'] = child['name']
            node['children'] = child.get('children', [])
        for child in node.get('children', []):
            prune_tree(child)
        return node

    return prune_tree(nodes[0]) if nodes else None

修复说明 #

1. 改用最深共同上位词作为合并优先级：不再依赖路径相似度，而是直接计算两个节点的最低共同上位词在其上位词链中的深度，优先合并共享更深层级上位词的节点，确保分类逻辑符合WordNet的层级结构。
2. 完整的节点生命周期管理：每次合并时彻底移除旧节点，仅保留当前活跃节点，避免无效的相似度记录干扰。
3. 添加树结构修剪：合并完成后自动修剪只有单个子节点的中间节点，生成更紧凑的最小分类树。
4. 上位词链预处理：提前获取每个节点的完整上位词路径，避免重复计算，提升效率。

内容的提问来源于Stack Exchange，提问作者Iyar Lin