采用双向个体标注的本体匹配技术

薛醒思， 王金水

(福建工程学院信息科学与工程学院， 福建 福州　350118)



采用双向个体标注的本体匹配技术

薛醒思， 王金水

(福建工程学院信息科学与工程学院， 福建 福州350118)

针对现实本体中缺乏双向标注的个体而导致的基于个体的本体匹配技术难以得到广泛应用这一问题， 提出一种采用双向个体标注的本体匹配技术. 该技术通过进化算法实现本体间自动化个体双向标注和概念匹配的过程. 实验采用OAEI 2012的测试数据集， 结果表明所提出的方法是有效的.

双向个体标注； 进化算法； 本体匹配

0　引言

语义网是万维网的一个重要发展方向, 它提供了一个通用框架, 使得数据的共享和重用可以跨越应用系统、 企业和社区的边界. 在语义网环境下， 语义层面的交互是所有基于开放知识的系统和分布式系统的设计中所关注的重要特性， 也是两个或多个信息系统在交互的过程中能够自动地、 准确地理解彼此通信内容的真实含义的能力. 要实现语义层面的交互首先要求对所有数据信息的含义进行充分的细节描述以克服潜在的语义不确定性， 即交互双方都必须使用一个共享的、 正式的信息交换参考模型.

本体作为语义网的关键组件， 是目前最新的信息交换参考模型， 也是迄今为止用于获取最准确的语义规范化描述的技术. 根据最常用的本体定义， 本体是概念化的明确的规范说明， 即对某个领域中存在的对象、 概念、 其他实体以及它们之间关系的正式的和规范化描述. 由于语言的快速进化(例如旧的术语可能不断拥有新的含义)， 创建并维护一个包罗万象的、 可以满足所有应用系统要求的本体是一个不可能的任务. 因此， 目前在不同的系统中使用的都是由不同的团体彼此独立开发的本体. 然而， 不同本体设计者对于某个领域中的相同对象可能会有不同的描述方式(例如, 同一个概念在不同本体中可能会有不同的名字)， 这就会导致术语和概念描述不一致的异质本体的产生， 而异质本体中存在的语义异质问题是实现语义层面交互的最大障碍. 目前, 解决本体异质问题的最有效的方法， 是通过执行本体匹配过程来检测并发现异质本体中在语义上相似的实体之间的对应关系， 最终输出由在语义上相似的实体对组成的本体匹配结果. 由于本体匹配过程在诸如电子商务、 知识管理、 信息检索、 知识获取、 医学、 生物信息学等应用领域中具有重大的实用价值， 近年来开发了大量的本体匹配系统. 这些本体匹配系统通常将源本体中的每一个实体同目标本体中的所有实体进行比较， 通过组合不同相似度度量技术来确定目标本体中与其最相似的实体对象.

由于相比其概念的属性而言， 概念所拥有的个体可以更好地描述其真实的语义， 这使得基于个体的本体匹配技术引起了广泛的关注[1]. 然而， 现实的本体中缺乏同时与两个本体中的概念都相关的个体(即双向标注的个体)， 因此， 基于个体的本体匹配技术难以得到广泛应用[2]. 针对这一问题， 本研究提出一种双向个体标注的本体匹配技术. 该技术通过进化算法(evolutionary algorithm， EA)实现待匹配本体中自动的个体的双向标注过程， 并在此基础上确定本体中概念间的对应关系. 本研究的贡献如下： ① 在采用双向个体标注的本体匹配技术中通过引入近似度量方法以降低该技术对领域专家的依赖； ② 从双向个体标注角度为本体匹配问题构建单目标优化模型， 并设计了采用双向个体标注的本体匹配算法以求解该问题； ③ 通过静态测试技术分析实验结果， 验证采用双向个体标注的本体匹配技术的有效性.

1　基本概念

1.1本体与本体映射

定义1[3]本体是一个八元组O=(C, P, I, ≤c, ≤p, φCP, φCI, φPI)， 其中： C、 P和I分别指本体中的概念、 属性和个体的集合， 三者统称为本体中的实体(entity)； ≤c是C的偏序集合， 即类的概念体系结构； ≤p是P的偏序集合， 即类的属性体系结构； φCP:P→C×C是将属性p∈P同概念间的关系关联起来的函数； φCI:C→R(I)是将概念c∈C同概念c的个体I的子集关联起来的函数； φPI:C→R(I2)是将属性p∈P同笛卡尔集I×I的自己关联起来的函数， 其中， I×I表示通过属性p∈P产生关联关系的个体对.

定义2[3]给定两个待匹配的本体O1和O2， 本体匹配结果A是一组k个映射的集合：

其中： ei是本体O1的第i个实体； ej是本体O2的第j个实体； ηl是第l个映射的可信度值； r是实体对ei和ej之间的语义关系(通常是等价关系).

1.2本体匹配结果评价

传统的评价度量recall、 precision和f-measure最大的缺陷是需要由专家事先给出标准的本体匹配结果， 而该结果在实际应用中往往是不存在的. 为了解决这一问题， 假定所需要的本体匹配结果是1 ∶1(即本体中的任何概念只能同另一个本体中的一个概念对应)， 采用如下的3个近似度量： MatchCover、 MatchRatio和MatchMeasure[4]分别用于近似传统的recall、 precision和f-measure：

(1)

(2)

(3)

2　双向个体标注算法

对于本体O1中的某个个体insti， 首先要确定在本体O2同insti相似的个体集合I2， 然后将insti关联到I2中的个体所直接关联的概念上以实现insti的双向标注.

2.1个体相似度度量技术

基于个体的本体匹配技术的关键问题之一就是如何度量不同个体之间的相似度[5]. 根据文献[6]， 两个个体的相似度可以通过各自属性值的相似程度来确定. 此外， 考虑到在个体相关的背景信息未知的前提下， 通过统计个体中属性间的相似度以进一步确定个体间相似度是目前有效的方法之一. 具体地说， 给定两个个体inst1和inst2， 二者的相似度通过以下公式计算[7]：

(4)

其中：h和k分别是个体inst1和inst2的属性集合的基数； inst1i和inst2j分别表示inst1中第i个属性和inst2中第j个属性； 函数Sim()用于计算inst1i和inst2j的属性值的SMOA距离[8-9].

通过上述度量方法可获取两个本体O1和O2的个体相似度矩阵S. S的第i行和第j列分别表示O1中的第i个个体和O2中的第j个个体， S的元素Sij表示O1中的第i个个体和O2中的第j个个体的相似度值.

2.2双向个体标注算法

在双向个体标注算法中， 有两个关键参数需要确定： ① topN表示前N个同O1中的个体inst1i最相似的O2中的个体可以用于产生inst1i的双向标注； ② instanceThreshold表示只有同inst1i相似度值大于instanceThreshold的O2中的个体可以用于产生inst1i的双向标注. 如何确定这两个参数的值对最终产生的本体映射结果有明显的影响， 关于这两个参数的讨论详见第4小节.

给定待匹配本体O1和O2的个体相似度矩阵S、 参数topN和instanceThreshold， 双向个体标注算法的步骤如下： ① 将S中所有小于instanceThreshold的值置0； ② 遍历S中的所有行， 对每一行的数值另行按照降序排列， 对排号大于topN的数值， 将S中相应的元素置0； ③ 遍历S中的所有列， 对每一列的数值另行按照降序排列， 对排号大于topN的数值， 将S中相应的元素置0； ④ 对S中非零元素对应的行和列的个体执行双向标注， 例如： S中的元素Sij为非0元素， 则将O1中的个体inst1i关联到O2的个体inst2j所关联的概念， 同样将O2的个体inst2j关联到O1中的个体inst1i所关联的概念.

通过上述算法， 实现两个本体间的个体双向标注， 之后首先计算拥有个体的概念间的相似度， 然后通过上下文将相似度扩散到没有个体的概念间.

3　概念相似度度量技术

根据文献[10]， 改进的Jaccard度量可以有效地计算两个拥有个体的概念间的相似度. 因此， 采用改进的Jaccard度量来计算两个拥有个体的概念间的相似度：

(5)

其中：Instc1和Instc2分别是同概念c1和c2直接关联的个体集合.

由于本体通常只有叶子节点的概念有定义个体集合， 为了获取本体中没有定义个体集合的概念间的相似度， 需要通过以下公式将相似度在相邻的概念间进行传播： 给定两个概念c1、 c2和它们的直接子概念集合Sc1和Sc2， c1和c2间的相似度值通过以下公式来计算[7]：

(6)

4　求解本体匹配问题

在双向个体标注算法中，topN较大意味着inst1i可能同更多的O2中的概念直接关联， 从而产生较多的本体中概念间的匹配. 而较小的topN意味着inst1i只会选择相对更为相似的个体来产生双向标注， 从而保证匹配结果的准确性. 较低的instanceThreshold使得inst1i可能同更多的O2中的概念直接关联， 随着instanceThreshold的增加， O2中的个体可以用于产生inst1i的双向标注的选择性也随着提升， 产生较少的但是准确性高的匹配结果. 这两个参数取值的权衡问题类似于recall和precision之间的权衡： 当想要获取更高的precision的时候， 需要对结果有更严格的选择条件， 这就不可避免地降低了recall的值； 反之亦然， 当想要提高recall的值的时候， 必然要放宽结果的选择条件， 这又导致了precision值的降低. 因此， 为了动态地确定最优的topN与instanceThreshold以获取高质量的本体匹配结果， 本研究提出用EA来确定topN与instanceThreshold从而优化本体匹配结果.

4.1本体匹配问题的优化模型

本研究希望能够通过确定双向个体标注算法中的topN和分别用于过滤个体映射结果和概念映射结果的instanceThreshold和conceptThreshold来获取最优的本体匹配结果. 其中， 本体匹配结果结果的质量度量方法采用的是公式(3)中的MatchMeasure.MatchMeasure的值越大表示获取的本体匹配结果越好. 综上， 提出的本体匹配问题的优化模型如下：

(7)

在该模型中，topN与instanceThreshold是双向个体标注算法中的两个关键参数，conceptThreshold是用于过滤本体匹配结果中的概念映射， 该模型的目标是最大化映射结果的MatchMeasure值.

表1　进化算法伪代码Tab.1　Pseudocode of evolutionary algorithm

本体匹配问题是一种十分复杂(非线性问题且有许多局部最优解)和耗时(计算数据量大)的问题. 尤其当本体中的实体规模庞大的时候， 通常会采用近似的算法来求解本体匹配问题. 从这个角度来看， EA作为一种鲁棒性好且寻优能力强的全局优化方法， 十分适合用于求解本体匹配问题. 表1给出了EA的伪代码.

4.2编码机制

采用实数编码， 种群中的每个个体的第1个染色体代表topN， 其取值范围从0到10； 第2个和第3个染色体分别代表个体和概念的相似度阈值， 取值范围从0到1.

4.3适应度函数

适应度函数用于评价通过种群个体产生的本体匹配结果的质量. 采用在1.2小节介绍的近似度量MatchMeasure作为适应度函数.

4.4 遗传算子

1) 选择算子. 采用赌轮盘选择算子， 该算子为每一个个体赋予一个正比于它们的适应度值的选择概率， 这就使得适应度值最高的个体拥有最高的概率产生下一代个体， 而适应度值不是那么高的个体也有机会产生下一代个体.

2) 交叉算子. 采用单点交叉算子， 首先随机地选择父个体中的一个编码位作为切割点， 切割点将父个体分为左右两个部分， 然后通过交换父个体中的右边的基因来产生新个体.

3) 变异算子. 采用位点变异方法， 如果变异的编码位是第1位， 则将该编码位上的数值随机加上一个整数并取其与10相除后的余数. 如果该变异的编码位是第2位或是第3位， 按照以下公式进行变异：

其中：cnew和cold分别表示变异前与变异后的值，r和rand分别是两个取值范围在0到1之间的随机数.

5　实验结果与分析

实验采用OAEI 2012[11]测试案例集， 其中, 每个测试案例由一个种子本体根据不同方法修改获取的目标本体和一个由专家事先给出的参考匹配结果组成. 表2给出了OAEI 2012测试案例集的简述.

表2　OAEI 2012测试案例集简述Tab.2　Brief introduction of OAEI 2012 test cases

实验中， EA的参数配置遵循以下原则：

① EA以交叉算子为主， 变异算子为辅. 因此， 交叉概率较大而变异概率较小. 如果交叉概率太大， 则会产生过多的解从而增加了计算量， 变异概率太大使得算法成为随机算法， 结果无法收敛. 建议的交叉概率的取值区间为[0.2, 1]， 而变异概率的取值区间为[0.01, 0.05]. 通过实验发现， 交叉概率0.7和变异概率0.02对于测试数据集中的各种异质问题都能产生可接受的解.

② EA的群体规模以及算法的终止条件取决于问题的规模， 建议将取值区间分别设为[30, 300]和[200, 1000]. 由于所求解的问题规模不大， 因此, EA法的群体规模以及算法的终止条件分别设置为30个个体和300次适应度评价.

综上， EA算法采用的参数目的是为了获取最高的平均匹配结果质量. 通过这种方式获取的参数配置对于OAEI 2012测试案例集中所有的测试数据是鲁棒的， 因此, 也有望对于现实世界中常见的异质问题是鲁棒的. 实验中， EA的参数配置如下：

数值精度=0.01， 群体规模=40个个体， 交叉概率=0.7， 变异概率=0.02， 最大代数=300

为了同前沿的本体匹配系统比较， 将已获取的本体匹配结果用传统的评价度量recall、 precision和f-measure重新评价. 表3中描述了本方法同前沿的本体匹配系统eTuner[12]和GOAL[13]的比较结果.

在表3中， 1XX、 2XX和3XX分别代表表2中的编号以1、 2和3开始的测试案例集， 符号R、P和f分别表示recall、 precision和f-measure， 表中的数值是相应的测试数据集匹配结果评价的均值. 本方法的结果是在30次独立运行后的平均结果. 在前沿的本体匹配系统中， 本研究选择eTuner和GOAL的原因如下： ① eTuner采用自动化调谐参数的技术， 但它是基于枚举搜索的策略； ② GOAL同本文提出的方法类似， 是著名的基于EA的本体匹配系统. 实验比较的过程由两个步骤组成： ① 通过静态测试技术， 即Friedman测试[14]， 判断是否比较的系统产生的结果之间存在差异； ② 如果第一个步骤判断出比较的系统间存在差异， 则执行后续的静态测试， 即Holm测试[15]， 以确定性能较优的系统.

Friedman测试是一种无参数的静态测试过程， 致力于检测两个或两个以上的算法之间是否存在明显的行为差异. 具体地说， 该测试假设所有的算法都是等价的， 对这一假定的否决意味着被研究的算法间存在差异. 为了否决Friedman测试的假设， 计算的χr的值必须等于或大于在特定级别的卡方临界值[16]. 实验中， 级别α=0.05. 由于比较的是3个本体匹配方法， 因此, 分析的过程需要考虑自由度为二的临界值χ0.05， 该临界值为5.991. 表3中圆括号中的数字是该结果相应的排名. 通过执行Friedman测试， 计算的χr的值是44.53. 由于χr的值大于χ0.05， Friedman的假设被否决， 因此, 比较的3个本体匹配系统之间可能存在明显的差异.

根据这一结果， 需要执行后续的关于系统间成对比较的静态测试. Holm测试先要选择一个控制算法， 并将其同其余的算法进行比较. 一般情况下， 控制算法是在Friedman测试中排名值最低的算法. 从表3中的最后一行的平均值可以看出， 本方法排名值最低.

表3　本方法同前沿的本体匹配系统的比较Tab.3　Comparison between the state-of-the-art ontology matching systems and our approach

Holm测试在比较第i和第j算法的时候， 指定使用z值来从正态分布表中确定相关的概率(即p值)， 然后将p值同级别参数α(实验中α=0.05)进行比较. Holm测试的结果在表4中给出. 通过表4中的数据， 可以得出以下结论： 本方法在5%级别上静态优于eTuner和GOAL.

表4　Holm测试Tab.4　Holm’s test

6　结语

本体匹配是本体工程中的重要步骤， 然而本体匹配过程中仍然有许多问题有待解决. 其中一个问题是由于现实的本体中缺乏双向标注的个体， 使得基于个体的本体匹配技术难以得到广泛的应用. 为此， 提出一种双向个体标注的本体匹配技术， 该技术通过EA来实现本体间自动化个体双向标注和概念匹配的过程. 实验采用OAEI 2012的测试数据集， 同前沿的本体匹配系统的结果比较表明本方法是有效的.

由于本研究提出的近似度量MatchCover、 MatchRatio和MatchFmeasure的前提条件是一种非常强的约束(标准匹配结果是1 ∶1)， 该前提使得这些度量不适用于标准匹配结果是m∶n的应用场景. 关于如何设计不依赖标准匹配结果且具有更好的普适性的本体匹配结果的质量度量方法是未来需要解决的问题.

[1] WANG Z, LI J, ZHAO Y,etal. A unified approach to matching semantic data on the Web[J]. Knowledge-Based Systems, 2013, 39: 173-184.

[2] THOR A, KIRSTEN T, RAHM E. Instance-based matching of hierarchical ontologies[C]//BTW. Aachen: [s.n.], 2007: 436-448.

[3] ACAMPORA G, LOIA V, VITIELLO A. Enhancing ontology alignment through a memetic aggregation of similarity measures[J]. Information Sciences, 2013, 250: 1-20.

[4] KIRSTEN T, THOR A, RAHM E. Instance-based matching of large life science ontologies[C]//Proceeding of 10th International Conference on Data Integration in the Life Sciences. Philadelphia: [s.n.], 2007: 172-187.

[5] DUAN S, FOKOUE A, HASSANZADEH O,etal. Instance-based matching of large ontologies using locality-sensitive hashing[M]. Boston: Springer, 2012: 49-64.

[6] RONG S, NIU X, XIANG E W,etal. A machine learning approach for instance matching based on similarity metrics[M]. Boston: Springer, 2012: 460-475.

[7] ENGMANN D, MASSMANN S. Instance matching with coma++[C]// BTW. Aachen: [s.n.], 2007: 28-37.

[8] STOILOS G, STAMOU G, KOLLIAS S. A string metric for ontology alignment[M]. Galway: Springer, 2005: 624-637.

[9] WINKLER W E. The state of record linkage and current research problems: RR99/04[R]. Washington DC： Statistical Research Division, US Census Bureau, 1999.

[10] ISAAC A, VAN DER MEIJ L, Schlobach S,etal. An empirical study of instance-based ontology matching[M]. Busan: Springer, 2007: 253-266.

[11] AGUIRRE J L, GRAU B C, ECKERT K,etal. Results of the ontology alignment evaluation initiative 2012[C]//Proceeding of 7th ISWC Workshop on Ontology Matching. Boston: [s.n.], 2012: 73-115.

[12] LEE Y, SAYYADIAN M, DOAN A H,etal. eTuner: tuning schema matching software using synthetic scenarios[J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2007, 16(1): 97-122.

[13] MARTINEZ-GIL J, ALBA E, ALDANA-MONTES J F. Optimizing ontology alignments by using genetic algorithms[C]//Proceedings of The Workshop on Nature Based Reasoning for The Semantic Web. Karlsruhe: [s.n.], 2008: 1-14, .

[14] GARCIA S, MOLINA D, LOZANO M,etal. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization[J]. Journal of Heuristics, 2009, 15(6): 617-644.

[15] HOLM S. A simple sequentially rejective multiple test procedure[J]. Scandinavian Journal of Statistics， 1979 (6): 65-70.

[16] NASH M S. Handbook of parametric and nonparametric statistical procedures[J]. Technometrics, 2001, 43(3): 374-374.

(责任编辑： 沈芸)

An ontology matching technology usingdually individual annotation

XUE Xingsi， WANG Jinshui

(College of Information Science and Engineering, Fujian University of Technology, Fuzhou, Fujian 350118, China)

Since individuals can better represent the real semantics of the concept they belong to, individual based ontology matching technology is able to improve the precision of the ontology alignment. However, in the real scenarios, the lack of the dually annotated individuals seriously limits the application of the individual based ontology matching technology. To overcome this shortcoming, in this paper, an ontology matching technology using dually individual annotation is proposed. In particular, our proposal utilizes the evolutionary algorithm (EA) to implement the process of automatic dually individual annotation and concept matching. The experiment uses the OAEI 2012 benchmarks, and the results show the effectiveness of our proposal.

dually instances annotation； evolutionary algorithm； ontology matching

10.7631/issn.1000-2243.2016.01.0064

1000-2243(2016)01-0064-07

2014-11-14

薛醒思(1981-)， 讲师， 主要从事智能计算与本体匹配技术研究， jack8375@gmail.com

国家自然科学基金资助项目(61503082， 61402108)； 福建工程学院校科研启动基金(GY-Z15007)

TP182

A