如何高效将pandas DataFrame格式知识图谱KG转换为指定结构的字典
问题描述
我有一个pandas DataFrame格式的知识图谱KG,样例数据如下:
输入
KG: pred subj obj 0 nationality BART USA 1 placeOfBirth BART NEWYORK 2 locatedIn NEWYORK USA 3 hasFather BART HOMMER 4 nationality HOMMER USA 5 placeOfBirth HOMMER NEWYORK
我需要将KG转换为如下结构的字典:
输出结果
{'BART': {'subj': [0, 1, 3], 'obj': []}, 'HOMMER': {'subj': [4, 5], 'obj': [3]}, 'NEWYORK': {'subj': [2], 'obj': [1, 5]}, 'USA': {'subj': [], 'obj': [0, 2, 4]}}
字典的键为KG中subj和obj列的所有实体值,值为子字典;子字典以subj、obj为键,对应值分别为该实体出现在KGsubj列、obj列的行索引列表。
我目前写的代码如下:
entity_list = sorted(set(KG.subj.values).union(set(KG.obj.values))) KG_index = {} for entity in entity_list: KG_index[entity] = {'subj' : KG[KG['subj'] == entity].index.tolist(), 'obj' : KG[KG['obj'] == entity].index.tolist()}
这段代码在处理大规模KG时耗时很长,请问是否有更快更高效的实现方法?
解决方案
原来的代码性能差的核心原因是:循环中每个实体都要对全表做一次布尔匹配,时间复杂度为O(实体数*总条数),数据规模大的时候耗时会指数级上升。以下是两种高效实现方案,时间复杂度均为O(总条数),仅需遍历一次全表即可完成统计:
方案1:用pandas原生groupby实现
利用pandas的分组接口直接按实体值聚合索引,避免逐行循环匹配:
import pandas as pd # 分别按subj、obj分组,得到实体对应行索引的映射 subj_groups = KG.groupby('subj').groups obj_groups = KG.groupby('obj').groups # 取所有实体集合 all_entities = set(subj_groups.keys()).union(obj_groups.keys()) # 构造结果字典 KG_index = { ent: { 'subj': subj_groups.get(ent, pd.Index([])).tolist(), 'obj': obj_groups.get(ent, pd.Index([])).tolist() } for ent in all_entities }
方案2:原生Python遍历(超大规模数据最优)
如果数据量极大,pandas接口的额外开销也可以省去,直接遍历subj和obj列统计索引:
from collections import defaultdict subj_idx_map = defaultdict(list) obj_idx_map = defaultdict(list) # 一次遍历全表完成统计 for idx, (subj_val, obj_val) in enumerate(zip(KG['subj'], KG['obj'])): subj_idx_map[subj_val].append(idx) obj_idx_map[obj_val].append(idx) # 取所有实体集合 all_entities = set(subj_idx_map.keys()).union(obj_idx_map.keys()) # 构造结果字典 KG_index = { ent: { 'subj': subj_idx_map.get(ent, []), 'obj': obj_idx_map.get(ent, []) } for ent in all_entities }
内容的提问来源于stack exchange,提问作者Won chul Shin
相关产品推荐
相关产品推荐

