ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (1): 50-62.doi: 10.7544/issn1000-1239.2017.20150843

• 人工智能 • 上一篇    下一篇



  1. 1(中国科学院信息工程研究所 北京 100093); 2(中国科学院网络数据科学与技术重点实验室(中国科学院计算技术研究所) 北京 100190) (
  • 出版日期: 2017-01-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2012CB316303,2013CB329602);“核高基”国家科技重大专项(2013ZX01039-002-001-001);国家自然科学基金项目(61303056,61402464,61402442,61572469,61502478);北京市自然科学基金项目(4154086) This work was supported by the National Basic Research Program of China (973 Program) (2012CB316303, 2013CB329602), the National Science and Technology Major Projects of Hegaoji (2013ZX01039-002-001-001), the National Natural Science Foundation of China (61303056, 61402464, 61402442, 61572469, 61502478), and the Beijing Natural Science Foundation (4154086).

A Composite Structure Based Method for Knowledge Base Taxonomy Matching

Lin Hailun1, Jia Yantao2, Wang Yuanzhuo2, Jin Xiaolong2, Cheng Xueqi2, Wang Weiping1   

  1. 1(Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093); 2(Key Laboratory of Network Data Science and Technology (Institute of Computing Technology, Chinese Academy of Sciences), Chinese Academy of Sciences, Beijing 100190)
  • Online: 2017-01-01

摘要: 近年来,分类体系匹配由于其在知识库构建和融合等方面的广泛应用,已成为国内外工业界和学术界的研究热点.然而,随着网络大数据的不断发展,分类体系变得越来越庞大和复杂,构造一种通用有效的分类体系匹配器以适应大规模、异构分类体系匹配的扩展性仍然面临很大的挑战.为此,提出了一种基于复合结构的分类体系匹配方法BiMWM,该方法利用分类体系中分类的复合结构信息:微观结构和宏观结构,将分类体系匹配问题转化为二部图上的优化问题进行求解.首先,创建赋权的二部图建模分类体系之间候选的匹配类对关系;然后,通过计算二部图上的最大权匹配剪枝选择最优的分类体系的匹配类对.BiMWM方法可以在多项式时间内为2个分类体系产生最优匹配.实验结果表明:与当前先进的基准方法相比,该方法能够有效提升大规模、异构分类体系匹配的性能.

关键词: 知识库, 分类体系匹配, 复合结构, 二部图, 最大权匹配

Abstract: Taxonomy matching, i.e., an operation of taxonomy merging across different knowledge bases, which aims to align common elements between taxonomies, has been extensively studied in recent years due to its wide applications in knowledge base population and proliferation. However, with the continuous development of network big data, taxonomies are becoming larger and more complex, and covering different domains. Therefore, to pose an effective and general matching strategy covering cross-domain or large-scale taxonomies is still a considerable challenge. In this paper, we presents a composite structure based matching method, named BiMWM, which exploits the composite structure information of class in taxonomy, including not only the micro-structure but also the macro-structure. BiMWM models the taxonomy matching problem as an optimization problem on a bipartite graph. It works in two stages: it firstly creates a weighted bipartite graph to model the candidate matched classes pairs between two taxonomies, then performs a maximum weight matching algorithm to generate an optimal matching for two taxonomies in a global manner. BiMWM runs in polynomial time to generate an optimal matching for two taxonomies. Experimental results show that our method outperforms the state-of-the-art baseline methods, and performs good adaptability in different domains and scales of taxonomies.

Key words: knowledge base, taxonomy matching, composite structure, bipartite graph, maximum weight matching