人工智能在本体映射中的应用

苗永昌

(92349部队 淄博 255178)



人工智能在本体映射中的应用

苗永昌

(92349部队 淄博 255178)

本体映射被认为是异构信息集成的关键,研究者们提出了很多本体映射的方法,论文主要从三个方面说明人工智能思想在本体映射中的应用。 1) 基于元素文本相似度计算的方法,往往会借助于自然语言处理技术,对文本进行相关处理。 2) 本体映射问题本质上是一个二元分类问题,可以借助于机器学习的方法提高本体映射的质量。 3) 利用聚类算法将本体分块,从而将大规模本体映射任务划分成若干个子任务,有效地解决了大规模本体映射的挑战。

本体映射; 自然语言处理; 机器学习; 聚类

Class Number TP399

1 引言

信息和通信技术的快速发展导致越来越多的异构信息充斥着互联网,面对信息的海洋,如何组织、管理、维护、共享这些分布异构的信息显得越来越困难。本体作为一种能在语义和知识层次上描述信息系统的概念模型建模工具[1],已经广泛应用于语义信息集成、数据交换、Web服务自动组合等领域,被认为是异构信息集成的基础。然而由于Web本身的分布性和自发性,不同的领域甚至是同一领域的不同组织,必然会定义不同的本体,这时本体自身就是异构的。因此,为了实现语义信息共享,首先必须建立异构本体中元素(概念、关系、实例等)之间的映射关系,这个过程称之为本体映射[2]。

目前,本体映射已经成为了语义Web中的研究热点,相关领域研究者进行了大量研究,提出了很多方法,概括起来可以分为:基于相似度的方法[3]、基于机器学习的方法[4]、基于逻辑推理的方法[5]以及基于背景知识的方法[6]。本体映射的综述请参见文献[7～8]。

人工智能是研究理解和模拟人类智能、智能行为及其规律的一门学科[9],因此可以利用人类进行本体映射的思想,为自动本体映射服务。本文将从以下三个方面说明人工智能在本体映射中的应用。

1) 基于自然语言处理的本体元素文本预处理;

2) 基于分类的本体映射方法;

3) 基于聚类的大规模本体映射。

2 本体及本体映射

为了便于表述,本节将有关术语定义如下。

1) 本体

本体的形式化定义有很多,但都离不开几个关键的概念,即类、属性、关系、实例以及公理,可形式化为

O={C,P,R,I,Ao}

其中,C为类集合,P为属性集合,R为关系集合,I为实例集合,Ao为公理的集合。为便于表述,本文将本体中的类和属性统称为元素。

2) 本体映射

给定两个本体O1和O2,本体映射就是建立这两个异构本体的元素之间的语义关系,如图1所示。在这个过程中,还有一些可选的输入,例如已有的映射结果、外部资源、参数等。

图1 本体映射过程

本体映射的输出是一系列匹配元素对的集合,其中每一项为一个四元组:

M=〈e,e′,r,n〉

其中e和e′分别为O1和O2中的元素,r表示e和e′之间的语义关系(等价、包含等),n为e与e′之间关系r的置信度,通常取值为[0,1]。同大多数研究一样,本文只考虑一对一的等价映射。

3 基于自然语言处理的本体元素文本预处理

在基于相似度的本体映射方法中,最重要的一类就是利用本体元素的文本特征计算相似度,从而得到映射。本体元素的文本特征包括id、label、comment以及其他描述性信息。提取出两个本体对应元素的文本特征后,如果直接对这些文本进行相似度计算,则可能准确度不高,因此一般会对文本进行一些预处理,包括:

1) 托肯化。利用空格、下划线、“驼峰式拼写法”等特征,将字符串划分成托肯集,例如,对“programCommittee”进行托肯化后得到单词集{“program”,“Committee”}。

2) 正规化。消除大小写、拼写等文本风格上的差异,形成统一规范。

3) 提取词干。语法上单词存在各种变形,例如名词复数、动词的过去分词等。可以利用很多方法(例如Porter stemming算法)提取单词的词干。例如“matched”和“matching”提取词干后都为“match”。

4) 去除停用词。有很多单词是非常常见的,对于整个文本的含义不起关键作用的,可以去除。例如“has”、“the”等。

5) 同义词扩展。利用WordNet获取单词的同义词,进行补充。例如“contribution”与“paper”。

文献[10]对本体映射常用的文本预处理策略进行了大量的实验对比,发现常用的预处理策略并没有较大程度上提高本体映射的质量。并且不难猜想,预处理策略消耗了更多时间,例如查询WordNet数据库会消耗较长时间。因此,这些预处理策略应根据实际应用情况进行合理选取。

4 基于分类的本体映射方法

本体映射的过程,实质上就是遍历两个本体的元素,然后判断两个元素是否存在语义联系,即“等价(+1)”或者“不等价(-1)”。因此,本体映射问题可以转换为一个二元分类问题:

m(e,e′,r)→{+1,-1}

其中,e和e′分别为O1和O2中的元素,r为e和e′之间的语义关系,此处为“等价”。因此,运用机器学习的方法,利用已有的本体映射结果训练一个本体映射分类器,当面临新的未知的本体映射任务时,可以很简单地对本体映射的结果进行分类,如图2所示。

需要说明的几点是:

1) 训练集的获取。一种是采用专家验证的方法,此过程需要消耗较长时间,并且准确度达不到100%。另外一种是利用公开的数据集,例如每年的OAEI本体映射竞赛都提供了很多公开的、已知结果的本体映射数据集。但是,很多数据集都是关于某一领域的,利用一个领域的数据集训练的分类器,是否在另外一个领域的本体映射任务上达到很高的分类效果,值得进一步研究。

2) 特征的提取。可以提取很多本体自身的特征,例如托肯比率、是否都为叶子节点等等;也可以直接利用各种相似度计算方法(matcher),例如编辑距离等。有兴趣的读者请参见文献[11],该研究利用了相似度特征、本体特征、文本特征、结构特征,最后对这些特征进行了对比实验,并指出相似度值对于分类效果有反作用。

图2 基于分类的本体映射方法

3) 分类器的选择。基本上满足二元分类要求的分类器都可以使用,文献[12]通过实验对比了SVM、KNN、DT、AdaBoost等分类器,发现效果相当。

5 基于聚类的大规模本体映射

随着本体应用的越来越广泛,本体的规模越来越大,并且往往涉及多个领域,逐渐向通用本体发展。例如AGROVOC本体[13]包含28439个概念,涉及农业、森林、渔业、食品、环境等多个领域。

基于相似度的本体映射方法是目前最普遍的方法,在映射过程中对两个本体的每一对元素对进行考虑,当面临大规模的本体映射任务时,不仅会消耗大量的时间,占用大量的内存,并且映射的质量也会有所影响。因此,大规模本体映射是目前本体映射研究的一个挑战[7]。

基于聚类的大规模本体映射采用了“分治法”的思想,如图3所示,其基本过程为:首先将本体转换成有向无环图,然后给出本体内元素间相似度计算公式,并以此为基础构造簇内凝聚度和簇间耦合度的计算方法,然后利用层次聚类方法(包括凝聚的层次聚类方法和分裂的层次聚类方法)将本体划分成若干个大小合适的块,并利用特定的方法找出两个本体之间相似的块,最后对这些块对进行通用的本体映射。

图3 基于聚类的大规模本体映射方法

文献[14]利用了改进的ROCK聚类算法,基于结点的结构相似度将本体的元素分成若干个块,然而不是直接对相似的块进行映射,而是利用“RDF语句”重构RDF片段,然后进行映射,有效地解决了“空白结点”的问题。文献[15]利用了AHSCAN聚类算法,它是一种社会网络结点聚类算法,主要利用了结点之间的联系,算法达到了O(n)的时间复杂度。

基于聚类的分块思想,有效地解决了大规模本体映射的难题,但是划分使得本体元素间的语义关系被强行地分割开来,映射结果的质量必然会有所影响,如何消除这些影响有待进一步研究。

6 相关研究

本体映射相关综述参见文献[7～8]。根据研究策略的不同,可以将本体映射相关研究分为基于相似度计算的方法、基于机器学习的方法、基于背景知识的方法和基于逻辑推理的方法。

6.1 基于相似度计算的本体映射

基于相似度计算的本体映射方法的基本思想是:本体O1和O2之间的映射发现问题可以分解为:对于O1中的每一个元素e,搜索其在O2中最相似的元素e′。根据使用特征的不同,又可以分为基于语言的策略、基于结构的策略、基于实例的策略。

基于语言的策略利用元素(及其邻近元素)的描述性信息计算两个对应元素的相似度,例如文献[16]提出了“虚拟文档”的概念,实际上就是一系列带加权的托肯集,然后利用TF/IDF以及向量空间模型计算文档间相似度。

基于结构的策略利用利用本体内元素之间的联系,计算两个对应元素的相似度。例如similarity flooding算法[17]是一种通用的图匹配算法,通过建立相似度传播图,在每次迭代过程中,每对结点的相似度都将一部分传递给其邻近的结点对,当达到稳定的状态或最大迭代次数后,停止迭代,并获得相似度。

基于实例的策略的基本思想是,如果两个对应元素共有的实例越多,则它们越相似。这里共有的实例不一定完全相等,也可以是满足一定相似度条件下的实例。文献[18]分析了五种不同的实例相似度计算方法,并做了大量实验对比,最后发现Jaccard方法效果最好。

6.2 基于机器学习的方法

基于机器学习的本体映射方法将映射问题转换成分类问题,为某个元素选择最优映射的问题就转换成对其进行分类的问题。通常利用已知映射结果的数据集训练分类器,当面临新的映射任务时,对每对元素是否匹配进行预测。

GLUE[4]系统通过学习实例的联合概率分布发现映射关系,文献[19]利用各种相似度学习映射过程,并建立实例间的映射关系(本体映射的一种),文献[20]通过机器学习的方法解决了多语言和不同语言间本体映射的问题。文献[21]还研究了跨领域学习和分类的效果。

6.3 基于背景知识的方法

基于背景知识的方法利用其他的、通用的或领域内的知识,发现映射关系。例如利用上层通用本体,这些本体逐渐成为了领域的标准,比如Gene本体、UMLS本体等。

文献[6]利用Google搜索引擎模拟元素之间的相似度,并建立映射关系。文献[22]利用DBpedia发现模式映射。

6.4 基于逻辑推理的方法

基于逻辑推理的方法往往作为一种辅助方法,事先定义好一系列规则,在得到初步映射之后,对映射结果进行逻辑推理,如果发现矛盾,则给出相应的解决方案,从而提高映射结果的质量。

文献[23]基于描述逻辑公式发现映射中的不一致性,并自动删除错误的映射,并且该文章作者还开发了基于逻辑推理的开源API[24]。文献[5]不仅能够发现矛盾,并且能够验证正确的映射。

7 结语

在当前信息要求高度共享的条件下,异构信息集成显得越来越重要,在语义Web环境下,本体映射被认为是解决语义异构问题的关键。人工的建立映射耗时而且容易出错,因此,人工智能思想必然可以为本体映射服务。本文首先介绍了本体及本体映射相关定义,然后从三个方面详细说明了人工智能思想在本体映射中的应用,同时也给出了下一步研究方向,最后对本体映射相关研究进行了综述。

[1] 邓志鸿,唐世渭,张铭,等.Ontology研究综述[J].北京大学学报(自然科学版),2002,38(5):730-738.

[2] 仲茜,李涓子,唐杰,等.基于数据场的大规模本体映射[J].计算机学报,2010,33(6):955-965.

[3] 蒋湛,姚晓明,林兰芬.基于特征自适应的本体映射方法[J].浙江大学学报(工学版),2014,48(1):76-84.

[4] Doan A H, Madhavan J, Dhamankar R, et al. Learning to match ontologies on the semantic web[J]. The VLDB Journal—The International Journal on Very Large Data Bases,2003,12(4):303-319.

[5] Jean-Mary Y R, Shironoshita E P, Kabuka M R. Ontology matching with semantic verification[J]. Web Semantics: Science, Services and Agents on the World Wide Web,2009,7(3):235-251.

[6] Gligorov R, ten Kate W, Aleksovski Z, et al. Using Google distance to weight approximate ontology matches[C]//Proceedings of the 16th international conference on World Wide Web. ACM,2007:767-776.

[7] Shvaiko P, Euzenat J. Ontology matching: state of the art and future challenges[J]. IEEE Transactions on Knowledge and Data Engineering,2013,25(1):158-176.

[8] Shvaiko P, Euzenat J. A survey of schema-based matching approaches[C]//Journal on Data Semantics IV. Berlin: Springer Heidelberg,2005:146-171.

[9] 贲可荣,张彦铎.人工智能[M].第2版.北京:清华大学出版社,2013.

[10] Cheatham M, Hitzler P. String similarity metrics for ontology alignment[C]//The Semantic Web-ISWC 2013. Berlin: Springer Heidelberg,2013:294-309.

[11] Eckert K, Meilicke C, Stuckenschmidt H. Improving ontology matching using meta-level learning[M]. Semantic Web: Research and Applications. Heidelbery: Springer,2009:158-172.

[12] Nezhadi A H, Shadgar B, Osareh A. Ontology alignment using machine learning techniques[J]. International Journal of Computer Science & Information Technology,2011,3(2):139-150.

[13] http://www.fao.org/aims/ag_intro.htm[EB/OL].

[14] Hu W, Qu Y, Cheng G. Matching large ontologies: A divide-and-conquer approach[J]. Data & Knowledge Engineering,2008,67(1):140-160.

[15] Algergawy A, Massmann S, Rahm E. A clustering-based approach for large-scale ontology matching[C]//Advances in Databases and Information Systems. Springer Berlin Heidelberg,2011:415-428.

[16] Qu Y, Hu W, Cheng G. Constructing virtual documents for ontology matching[C]//Proceedings of the 15th international conference on World Wide Web. ACM,2006:23-31.

[17] Melnik S, Garcia-Molina H, Rahm E. Similarity flooding: A versatile graph matching algorithm and its application to schema matching[C]//Data Engineering, 2002. Proceedings. 18th International Conference on. IEEE,2002:117-128.

[18] Isaac A, van der Meij L, Schlobach S, et al. An Empirical Study of Instance-Based Ontology Matching[J]. The Semantic Web,2008:253-266.

[19] Rong S, Niu X, Xiang E W, et al. A machine learning approach for instance matching based on similarity metrics[C]//The Semantic Web-ISWC 2012. Springer Berlin Heidelberg,2012:460-475.

[20] Spohr D, Hollink L, Cimiano P. A machine learning approach to multilingual and cross-lingual ontology matching[C]//The Semantic Web-ISWC 2011. Springer Berlin Heidelberg,2011:665-680.

[21] Mao M, Peng Y, Spring M. Ontology mapping: as a binary classification problem[J]. Concurrency and Computation: Practice and Experience,2011,23(9):1010-1025.

[22] Gillani S, Naeem M, Habibullah R, et al. Semantic Schema Matching Using DBpedia[J]. International Journal of Intelligent Systems and Applications(IJISA),2013,5(4):72-80.

[23] Meilicke C, Stuckenschmidt H, Tamilin A. Repairing ontology mappings[C]//Proceedings of the 22nd national conference on Artificial intelligence-Volume 2. AAAI Press,2007:1408-1413.

[24] Meilicke C. Alignment incoherence in ontology matching[D]. Mannbeim: University Mannheim,2011.

Application of Artificial Intelligence in Ontology Matching

MIAO Yongchang

(No. 92349 Troops of PLA, Zibo 255178)

Ontology matching is considered as the key to heterogeneous information integration, and researchers have proposed many approaches of ontology matching. This paper mainly illustrates the application of the artificial intelligence idea in the ontology matching process from three aspects. First, the elements text based similarity computing approach often process of related text with the help of natural language processing technology. Second, the nature of ontology matching problem is one of the binary classification problems, which can use machine learning methods to improve the quality of ontology matching. Third, the ontology partition method based on clustering algorithm, which divides a large-scale ontology matching task into several sub-tasks, effectively solves the problem of large-scale ontology matching challenge.

ontology matching, nature language processing, machine learning, clustering

2015年1月11日,

2015年2月13日 作者简介:苗永昌,男,工程师,研究方向:信息保障等。

TP399

10.3969/j.issn1672-9730.2015.07.019