基于关联规则的本体相似度综合计算方法

李华;苏乐

【摘 要】目前较为流行的最小风险的本体映射(RiMOM)框架通过采用“多策略”的思想虽然取得了一定的效果,但其框架比较臃肿庞杂,且采用的计算结构相似度的选择策略存在一定的局限性.针对上述问题,提出一种基于关联规则的本体相似度综合计算方法.首先,构造关联规则的结构“树”模型,得出相应事务集；其次,进行关联规则的挖掘,根据关联规则计算概念结构的相似性；然后,计算概念的实例、属性、名称的相似度；最后,对多个特征相似度进行综合加权处理,实现本体相似度的最优计算.实验结果表明,该方法较RiMOM在查全率、查准率方面均有较大提高；同时该方法省去了策略选择的步骤,有效降低了时间复杂度.%The recent Risk

Minimization based Ontology Mapping (RiMOM), based on multi-strategy, in spite of certain improvements, has the shortcomings in complexity and redundancy, and limitations in similarity selection of structure characteristics. Therefore, a comprehensive method of computing ontology similarity based on association rules was proposed. First, the \" tree\" model of association rules was constructed to compute the structure similarity. Then the similarity of instances, properties, and names were also computed. Finally, a comprehensive method was used to achieve the optimal calculation of the ontology similarity. The experimental results show that this method has higher recall and precision ratio and less time complexity than RiMOM. 【期刊名称】《计算机应用》

【年(卷),期】2012(032)009 【总页数】4页(P2472-2475)

【关键词】本体;数据挖掘;关联规则;本体映射;语义分析 【作 者】李华;苏乐

【作者单位】重庆大学计算机学院,重庆400044;重庆大学计算机学院,重庆400044

【正文语种】中 文

【中图分类】TP311.11;TP182 0 引言

随着语义网的大力发展，本体的数量激增，其规模也逐渐扩大，使用异构本体是语义网应用中非常常见的情况。因此本体映射技术应运而生，在语义网应用中扮演着非常重要的角色。本体映射的目的是为了建立异构本体间的交互规则，异构信息可借助这些规则在不同本体间传递，使异构本体间能相互沟通，实现语义互操作。针对模型之间的异构问题研究早在面向对象建模和数据库领域中就已经开展，并积累了一些经验［1］。然而，由于本体是一种语义信息描述形式，其组成和成分比面向对象模型和数据库模式复杂，因此本体间的异构处理比数据库中的模式映射和模式匹配问题更困难［2－3］，传统数据库中的很多匹配方法并不能直接适用于处理本体映射问题。近年来，寻找有效、实用的本体映射方法已成为本体研究领域的一项重要任务。

最近，各种本体匹配技术和系统框架层出不穷［4］，其中最小风险的本体映射

［5］(Risk Minimization based Ontology Mapping，RiMOM)框架就是一个比较好的基于多策略选择的本体映射框架。而相比较而言，在本体映射技术的评价［6］方面却进展缓慢，这些系统框架在对本体映射方面也显现出了一定的效果。比如RiMOM系统能够根据本体特征选择不同的策略方法。但是该系统对本体的特征判断的过程本身也需要一定的时间，特别是当本体数量比较庞大时，这个时间会成为一个影响匹配效果的不可忽视的影响因素。而且随着本体映射技术的不断发展，将会出现越来越多优秀的映射方法，每种方法的计算形式和关注点都不一样，这样RiMOM系统如果要想将这些方法加入其策略计算中，必然会使得系统框架变得越来越臃肿庞杂。

本文方法主要基于概念在本体结构中的位置。节点的位置代表了在本体结构中的概念，同时也决定了其相邻概念。因此可由概念节点的位置信息构造关联规则，从而推知概念在结构方面的相似性，再加上对这两个概念在名称、属性、实例的相似度计算，从而得到一个加权的综合相似度值，最终得到匹配结果。 1 理论依据

1)本文方法关键是在两个输入本体之间建立概念的相似性，该方法基于概念在本体结构中的位置。一般情况下，两个概念如果相似，则由它们派生出的关联规则也是相似的，节点的位置代表了在本体结构中的概念，同时决定了相邻概念，因为本体的创建间接地由本体结构的定义所决定。

2)同时仅仅基于结构的本体匹配也并不是完全有效的，因为两个概念的相似性往往受多种因素的影响，所以常常结合大规模字典如WordNet［7］和概念的实例、名称、属性等相似度计算。

3)本文中，考虑关联规则挖掘的方法也就是通常所说的市场篮子问题，概念－属性被视为物品，初始数据库集是一系列客户购买的东西(事务)，在关联规则的结构“树”模型中将本体结构树中的每条从根节点到叶子节点的路径作为一个事务。对

于所有的事务运用关联规则挖掘算法，然后根据提取的关联规则来决定每个输入概念的主要邻居。最后，这些关联规则的相似性就决定了基于位置的概念的相似性。 2 本体相似度矩阵的实现

本文方法首先对两个本体进行事务集的获取，得到关联规则树模型，然后在该模型的基础上根据得到的事务集进行关联规则挖掘，最后由关联规则的相似度结合概念的语义相似度进行加权综合，得出最终的相似度矩阵，映射模型如图1所示。 图1 基于关联规则和语义分析的本体映射模型 2.1 关联规则树模型的构造

构建映射模型的第一步是关联规则树模型的构造，也即关联规则集合的获得。为了计算概念的结构相关性，可以将本体结构看作一棵树，每一条从根节点到叶子节点所经过的路径构成一个事务，所有从根节点到叶子节点所经过的路径集合形成一个事务集，这样就可以利用Apriori算法［8］对这个事务集进行处理，进行关联规则的挖掘。其中，对本体树的检索，可以采用宽度优先搜索(Breadth First Search，BFS)［9］算法，所有子节点都会被加进一个先进先出的队列中。一般在算法实现时，其相邻且未被检验过的节点会被放置在一个被称为open的容器中(例如队列或是链表)，而被检验过的节点则被放置在被称为closed的容器中，遍历时，每个节点都存放有从根节点到该节点的路径。

图2所示为计算机部门本体，经过BFS算法后，形成带编号的树结构，如图2叶子节点所示为最终的事务集{(1，2，4，9)、(1，2，5，10)、(1，2，5，11)…}。 2.2 关联规则相似度计算

根据得到的事务集，本文采用改进的Apriori算法进行关联规则挖掘，由于该算法已经是非常成熟的理论，再此就不再赘述。对两个本体采用Apriori算法后将得到规则集R1和R2。为了计算R1中概念X与R2中概念Y之间的关联规则相似度值，将R1和R2中的关于X和Y的规则集划分如下:X的出度集Xout和入度集Xin，

Y的出度集Yout和入度集Yin。 图2 本体编号及事务集构成 图3 关联规则集

Xin与Yin的相似度计算公式定义为:

其中:s(i)表示X的入度集Xin中第i个规则的支持度计数，s(j)表示Y的入度集Yin中第j个规则的支持度计数，n和m分别表示X和Y的入度集的规则个数。 同理，定义Xout与Yout相似度计算公式为:

其中:s(i)表示X的出度集Xout中第i个规则的支持度计数，s(j)表示Y的出度集Yout中第j个规则的支持度计数，n和m分别表示X和Y的出度集的规则个数。 因为两个概念如果相似，则其关联规则也有一定的相似性。规定如果两个规则的支持度|S(X)－S(Y)|＞θ，表明这两个概念的规则相似度差异较大，在计算式(1)～(2)时，令其等于0。其中θ是人为定义的一个阈值，则最后X，Y的关联规则相似度计算为:

2.3 概念名称、实例、属性相似度计算 2.3.1 名称相似度

通常情况下，如果两个概念的名称用相同或是相近的字符来表示，那么这两个概念的意义通常也是相同或相近的，通过概念名称来计算相似度正是基于这种思想，因此，可以从语言级上对相似度进行判断。本文采用结合知网常识知识库来进行语义相似度计算。知网中的概念通过义原来描述，义原是描述概念的最小单位。假设两个义原在由上下位关系构成的树状层次体系中的路径为d，那么，可以得到两个义原之间的语义相似度［10］ 为:

其中α是一个调节因子。概念的语义通常由多个义原表示，因此首先计算出所有义原的相似度，然后综合加权得出概念名称的相似度。公式如下:

其中:m、n为x，y的义原数，wi是第i个义原所占的权重。 2.3.2 实例相似度

文献［11］提出了一种在语义Web环境下进行本体映射的方法，此方法利用概念的实例作为计算概念间相似度的依据来进行本体映射。采用其中的分布估计模块来求联合分布概念。

其中:P(X，Y)表示实例集中既属于概念X又属于概念Y的概率;P(X，¯Y)表示一个实例属于概念X但不属于概念Y的概率，其他类似。在相似度计算模块中，根据分布估计利用如下公式计算两个概念的相似度:

2.3.3 属性相似度

基于属性计算概念相似度的理论依据是:如果两个概念的属性是相同(相似)的，那么这两个概念是相同(相似)的;如果两个属性的域和范围是相同的，那么这两个属性也是相同的。属性有属性名称、属性数据类型、属性实例数据等要素，判断两个属性是否相似主要从这3个要素进行考虑。属性名称、属性类型都是文本类型，是字符串，因此，可以采用字符串相似度的计算方法进行计算。为便于计算，在此采用文献［12］中用到的Humming Distance方法来比较字符串相似度，而不必采用2.4节所用的方法。设两个字符串s和t，则它们之间的相似度为:

其中:若 s［i］=t［i］，则 f(i)=0;否则 f(i)=1。由于每个概念的实例对该概念的每

一个属性都分配了一个相应的值，因此对于概念属性实例数据相似度可以采用基于概念实例相似度的计算方法进行计算。

设概念X的属性为xi，概念Y的属性为yj，两个属性之间的相似度计算公式为:

其中:wi(i=1，2，3)是权重，代表属性的名称、属性数据类型、属性实例对属性相似度计算的重要程度，且w1+w2+w3=1，其中s1(xi，yj)和s2(xi，yj)采用式(10)的计算方法，s3(xi，yj)采用式(9)的计算方法。假设总共计算出 m个Sim(xi，yj)，并设置相应的权值lk，则概念之间基于属性的相似度为:

一个概念通常拥有很多个属性，如果将所有属性都计算在内，计算量无疑会非常大，而且很多计算是没有必要的。考虑到每个属性对概念的描述和作用各不相同，所以可以参考文献［13］方法，先根据机器学习的方法给出属性的信息增益，确定各个属性优先级的高低，最后只选择信息增益大的属性进行属性相似度的计算，由于不是本文的重点，所以在此不再赘述。 2.4 概念综合相似度计算

将关联规则相似度及概念名称、实例、属性相似度进行加权综合，得到最终概念综合相似度，加权模型如下:

3 实验分析 3.1 性能评价标准

在实验评估上，本文采用传统的查准率、查全率以及F1-Measurea［14］(F1)作为检验标准。

3.2 实验设定

实验采用Java语言实现，采用JENA的API对本体进行解析，在对概念相似度计算时，采用Java WordNet提供的API操作WordNet 2.0，获得本体的基于概念的相似度值。

OAEI 2011推荐了3个本体测试数据集，分别是benchmark、conference和 anatomy。在此本文选用 benchmark作为测试数据集。在benchmark集中，主要选取几组本体数据进行编号并测试。

N1(#101～#104):除#102外，其他3个本体在文本和层次结构两方面都基本一样。 N2(#201～#210):这几个本体都是在#101的基础上对元素的名称或元素的描述信息进行一定的改变而得到的。

N3(#221～#247):在这几个本体中，元素的名字和相应的描述信息全部得到保留。所不同的是，这些本体是不同类型的结构性信息缺失的组合。

实验将对α、β、γ、δ赋予不同的参数值观察效果，并将实验的效果与RiMOM本体映射框架进行比较，其他一些计算过程中需要用到的参数可根据经验值设定。 3.3 实验结果及分析 3.3.1 参数设置

为了测试不同的参数值对本体匹配效果的影响，将α、β、γ、δ分为几组参数进行实验:

分别选用N1、N2、N3本体测试集对测试本体的F1值进行对比。

从L6对应的F1可看出，此时N3的匹配效果较好，这主要是由于N3本体测试集是由元素的名字和相应的描述信息全部得到保留而结构性信息缺失的组合，这样由于概念名字相似度参数值设置得较大(β=0.6)，导致Simname(X，Y)值较高所致。而对于N1、N2都是集中在L2附近，所以效果较佳。并没有像想象的那样，α值越大越好，所以综合来看，如果不知道要比较的本体结构情况，应将各参数值

设得比较均匀。从图4还可看出，N1本体测试集的各测试点均高于N2、N3。这主要是因为N1的结构特征较好，而本文引入了关联规则相似性计算，使得结构的相似性高的本体间，这个值就比较大。 图4 基于参数选择的F1值 3.3.2 与RiMOM系统的比较

根据上面分析的经验，本次实验选取α、β、γ、δ系数分别为:0.3，0.25，0.25，0.2。

与RiMOM［5］系统中的查全率、查准率和综合评估F1的对比实验结果如表1所示。

表1 匹配效果数据对比 %N1 100.00 100.00100.00 100.00 100.00100.00 N2 98.90 99.00 98.95 98.50 95.30 96.90 N 3 99.00 97.50 98.25 98.90 100.00 99.40

从表1可看出:对于N1本体集，两种方法的效果是一样的，其匹配结果都十分令人满意，主要是因为N1本体集在结构、概念、名称方面变化都不大，所以两种方法都能达到一个非常好的匹配结果。但是对于N2测试集合，本文方法比RiMOM所使用的方法明显要好一些，这主要是因为本文采用了基于关联规则的相似度计算，而N2测试集这几个本体都是在#101的基础上对元素的名称或元素的描述信息进行一定的改变而得到的，其结构信息基本上没发生什么变化，这样所得的Sar(X，Y)值就比较高。而对于N3本体，因为这些本体是不同类型的结构性信息缺失的组合，其匹配效果较RiMOM系统并未有明显优势，从而可见，本体的结构对本文方法是有一定的影响的。由于RiMOM系统是一种综合多策略的本体匹配框架，对于输入的本体前期还要进行匹配策略的选择，而本文方法则没有这一步的判断，直接进行匹配过程，并且概念名称、属性、实例相似度等计算是可以并行进行的，相互之间并没有依赖关系，所以从这一点来说，本文方法在时间复杂度上具有一定

优势。如果输入本体的结构性特征比较明显或相似的情况下，将其定义为结构型本体，则本文方法效果将明显好于RiMOM。 4 结语

对于一个本体中的概念，包含了概念的名称描述、实例、属性以及概念在本体中的结构特征等信息。本文在数据挖掘理论和领域本体的基础上，综合考虑以上特点提出了一种基于关联规则挖掘和语义分析的本体映射综合方法。其中基于关联规则挖掘的相似度计算就是计算两个概念在结构方面的相似性，再加以概念的名称、实例、属性的相似度计算，得出本文的一种综合相似度值。实验结果表明本文方法在匹配效果方面令人满意。但是，由于本文方法采用关联规则挖掘计算本体结构的相似性，所以对于结构层次比较明显的本体结构，其匹配效果较好，而对于结构特征不明显的本体则需要人为地调节参数设置，否则其效果将不是特别理想。同时，随着本体技术的发展，本体演化［15］现象也会越来越严重，这些问题也是下一步需重点考虑并在系统中作相应改进的地方。 参考文献:

［1］BELLAHSENE Z，BONIFATI A，RAHM E.Schema matching and mapping［M］.Berlin:Springer-Verlag，2011:53 －73.

［2］RAHM E.Towards large-scale schema and ontology matching［C］//Proceedings of Schema Matching and Mapping(Data-Centric Systems and Applications).Berlin:Springer-Verlag，2011:3 －27.

［3］SHVAIKO P， EUZENAT J.Ten challenges for ontology matching［C］//Proceedings of the 2008 Conference on Ontologies， DataBases， and Applications of Semantics.Berlin:Springer-Verlag，2008:1163－1181. ［4］MARTINEZ-GIL J， NAVAS-DELGADO I， ALDANA-MONTES J F.MaF:An ontology matching framework［J］.Journal of Universal

Computer Science，2012，18(2):194 －217.

［5］LIJUANZI， TANG JIE， LI YI， et al.RiMOM:A dynamic multistrategy ontology alignment framework［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21(8):1218 －1232.

［6］VACCARI L， SHVAIKO P， PANE J， et al.An evaluation of ontology matching in geo-service applications［J］.GeoInformatica，2012，16(1):31－66.

［7］边振兴.WordNet中概念语义相似度IC参数模型研究［J］.计算机工程与应用，2011，47(19):128 －131.

［8］CHANGRUI， LIU ZHIYI.An improved Apriori algorithm［C］//Proceedings of 2011 International Conference on Electronics and Optoelectronics.Washington， DC:IEEE Computer Society，2011:476－478. ［9］严蔚敏，吴伟民.数据结构［M］.北京:清华大学出版社，2002:169－170. ［10］徐猛，刘宗田，周文.一种基于知网语义相似度计算的应用研究［J］.微计算机信息，2010，26(3):207 －209.

［11］EHRIG M， SURE Y.Ontology mapping:An integrated approach［C］//Proceedings of the 1st European Semantic Web Symposium.Heraklion， Greece: ［s.n.］， 2004:10 －12.

［12］曹泽文，钱杰，张维明.一种综合的概念相似度计算方法［J］.计算机科学，2007，34(3):174－175.

［13］谷志锋，刘勇，郭跟成.基于相似度计算的本体映射优化方法［J］.计算机工程，2008，34(19):56 －57.

［14］EUZENAT J， RHONE-ALPES I.Semantic precision and recall for ontology alignment evaluation［C］//Proceedings of the 20th

International Joint Conference on Artificial Intelligence.San Francisco:［s.n.］，2007:248 －253.

［15］刘金花，张友华，李绍稳.本体演化研究进展［J］.计算机系统应用，2011，20(7):239 －243.