语义 Web 服务匹配中的概念相似度算法1.doc

《语义 Web 服务匹配中的概念相似度算法1.doc》由会员分享，可在线阅读，更多相关《语义 Web 服务匹配中的概念相似度算法1.doc（8页珍藏版）》请在三一文库上搜索。

1、精品论文推荐语义 Web 服务匹配中的概念相似度算法1刘倩，双锴，陈炜 北京邮电大学网络与交换技术国家重点实验室，北京 (100876) E-mail：，，摘要：本文提出了在语义 web 服务匹配过程中两个概念之间相似度的计算方法，在考虑继 承关系和二元关系的前提下，采用基于权重的语义距离的方法进行衡量，并提出了根据该语 义距离计算相似度的计算公式，且通过仿真实验获取了合适的参数。实验数据证明，采用本 方法计算出来的相似度和领域专家的判断极其相近，可应用于 web 服务匹配中单个概念之间 的匹配。关键词：语义 Web 服务；服务匹配；语义相似度1.引言互联网的创始人 Tim Berners-L

2、ee 在 2000 年提出了语义 Web 的概念和体系结构：“语义 Web 是现有 Web 的扩展，信息被赋予定义良好的含义，更便于计算机和人的协同”1。 语 义 Web 提供了一个通用的框架，主要基于 XML 和 RDF/RDFS2，并在此之上构建本体和 逻辑推理规则，以完成基于语义的知识表示和推理，从而能够为计算机所理解和处理。语义Web服务是语义Web和Web服务的结合,可为Web服务的发现、执行、解释组合的自 动化提供有效的支持。为了实现这一目标，语义Web服务的主要方法是利用Ontology来描述 Web服务，然后通过这些带有语义信息的描述实现Web服务来实现服务的自动发现、调用和

3、组合。语义web服务匹配是其中一个重要的研究方向，目的是根据用户对服务接口的描述去 寻找能够满足要求的服务。在web服务使用OWL-S3描述的前提下，服务匹配其实是基于本 体概念的匹配，而两个概念之间的匹配过程本质上是通过某种方式来选取最接近的概念：4 提出了有限等级的匹配算法，将匹配程度分成了四个等级；5在4的基础上扩充了匹配的 等级，并引入了属性的匹配；6通过对概念分配不同的权重来计算概念间的相似度；7认 为概念的特性是由其具有的属性共同决定的，因而采用属性的个数来计算相似度；8通过 基于权重的语义距离和相似度函数来计算相似度。然而在两个概念的匹配过程中，不仅需要 考虑概念之间存在的继承关

4、系或二元关系，也要考虑概念深度对相似度的影响，且尽量细化 概念之间的匹配程度也有助于待匹配概念的排序和选择，因此综合上述因素的评价方式可以 更好地体现出概念之间的匹配度差别，本文在这种综合考虑之下，提出了一种新的基于语义 距离的相似度算法，并通过实验对比选取了合适的参数，使得通过本算法计算得出的结果更 为合理，与领域专家给出的判断结果基本一致。2.算法的基本思想本算法综合考虑了概念之间的继承关系和二元关系，以及概念所处深度对匹配度的影响 8，通过语义相似度 DoM( Degree of Match)来度量两个概念之间的匹配程度。本算法可分 为如下步骤：（1） 分配权重：为概念之间的关系分配权重

5、。（2） 生成节点路径表：记录每一个节点到根节点的所有路径。（3） 计算语义距离：根据节点路径表计算语义距离。语义距离指的是基于继承关系1本课题由国家自然科学基金项目(60672121)，国家高技术研究发展计划(863)( 2006AA01Z164)，国家基础研 究与开发程序(973)( 2003CB314806)资助。-8-和二元关系来计算概念的加权关系长度。（4） 计算相似度：构造相似度函数基于语义距离计算概念间的相似度。在具体介绍算法步骤前，作如下定义：定义 1：给任意一对概念 C1 和 C2，定义它们之间的语义距离为 Dis(C1,C2) 。定义 2：两个概念 C1 和 C2 之间的继

6、承关系用 sub(C1，C2)表示，代表 C1 是 C2 的子 概念；二元关系用 prop(C1，C2)表示；代表 C1 具有属性 C2。定义 3：关系 r 包括继承关系 sub 和二元关系 prop。定义 4：节点路径表中的记录表示为 path(C1, C2.Cn)，其中 Cn 为根节点。定义 5：如果在概念 C1 或者 C2 的路由表中两个概念相邻，则概念 C1 和 C2 存在直接 路径关系。定义 6：如果在概念 C1 或者 C2 的路由表中两个概念存在路径相连，且不相邻，则 C1和 C2 存在间接路径关系。2.1 权重分配为了使得概念之间的距离随着深度的增加而减小，且二元关系要比继承关系

7、的语义距离 远，权重分配应满足上述原则。由于要同时考虑二元关系和继承关系，因而不适宜采用文献 6的方法将权重分配在概念节点上，而是分配在两个概念 C1 和 C2 之间的关系上，也即本 体图中的“边”。本算法的权重分配公式如下所示。1继承关系权重：Wsub(C1,C2) 1f (dep(c2 )1-公式 1二元关系权重：Wprop(C1,C2) m（1在上述公式中：f (dep(c1 )），(m1)-公式 2(1) dep(c)表示概念的深度，规定根概念的深度为 0，其它概念的深度等于它到根节点的路径 长度，这个路径只考虑继承关系的路径。(2)kdep ( c ) f (dep(c) 是以 de

8、p（c）为自变量的增函数，如 k; dep(c) ;k * dep(c) (k1)等。虽然这些函数的增长速率不一致，但都反映了所要求的趋势，因此从数理上都是合理的。 采用不同函数得到的结果差别只在于相似度的数值，而对整体的匹配度趋势没有影响。 具体使用哪个函数，和本体图中节点的平均深度有一定关系，例如在平均深度较大的情 况下，使用指数类型的函数会使得继承关系的权重区别很小，不容易体现概念之间的差距，因此选择上升趋势比较平缓的函数更为合适。在如图一所示的本体图中，由于其平dep ( c ) 均深度大概为四，因此本算法以函数 k为例，取 k=2，图一给出了在这种本体图中的权重分配值。图 1 权重分

9、配图需要注意的是，如果图中存在多继承的情况（如 H 是 B 和 E 的子类），则该概念节点的 深度具有多个值，取决于该继承关系所位于的具体路径对应的深度，也即，在实际计算一对 概念的距离时，其权重值取决于他们经由哪一条权重路径关联起来。因此在上图中，H 和 E 之间的权重有两个取值，其中对于权重路径(H,E,C,A), Wsub(H,E) = 1+ 1/22 = 1.25；对于权 重路径(H,E,F,D,A)，Wsub(H,E) = 1+ 1/23 = 1.125 。2.2 生成节点路径表对于本体树的每一个节点，保存其到根节点的所有路径，以及每条路径上节点间的关系 权重，构成一个节点路径表，如

10、图二所示。通过这个节点路径表可以直接计算并比较两个节 点之间的路径长度以得出最短的语义距离，而不需要在每次计算前都对整个本体图进行遍 历。图 2 节点路径表每个节点的路径表由若干条路径记录组成，每条记录包括节点路径和权重两部分，其中 节点路径是从该节点到根节点的路径，权重是该条路径上两两节点之间的权重，其构建方法 如下：从根节点起进行广度遍历，子节点记录的路径部份为其父节点的路径加上本节点构成， 权重部分由其父节点的权重列表添上该节点和其父节点之间的权重构成。在图二中，以节点 F 为例，F 的邻接节点有 C,D 和 G，因此 F 的路径表可以根据这三个 节点分别的路径表生成，根据 C 的路径表

11、，可以得出一条 F 的路径记录是(F,C,A) (3,2), C 的其它两条路径是经过 F 的，所以为冗余路径，可以不加入 F 的路径表；根据 D 的路径表 可以得出另一条记录(F,D,A) (1.5,2)；同样可以得到记录(F,G,A) (1.5,2)。在路径表的基础 上计算每条路径的加权关系链长度时，只需取出路径中两点之间的权重加起来即可，如 (F,D,A)的关系链长度为 1.5+2 =3.5 。需要注意的是，在某个节点有多个父节点的情况下，由于其具有多条权重路径和多个权 重值（如节点 H），需要将节点路径和权重路径结合起来，进行前缀匹配，取和节点路径最 为匹配的权重路径对应的权重值。以

12、H 节点为例，其 Wsub(H,E)的权重路径为：(H,E,C,A), 对应的权重 1.25；(H,E,F,D,A)，对应的权重为 1.125。因此对于路径(H,E,C,F,D,A)，通过前 缀匹配 (H,E,C,A) 更加匹 配，此时 Wsub(H,E)=1.25 ，所 以该 路 径 对应的 权 重 应该是 (1.25,1.5.3.1.5,2)；同样可以得到，(H,E,F,C,A)的权重部分应该是(1.125,1.25,3.2)。2.3 计算语义距离根据 2.2 的节点路径表，对于任意两点之间的语义距离，可以通过如下算法得到。(1) 查看 C1 和 C2 是否是同一个概念。如果是，则 Dis

13、(C1,C2) = 0；如果否，转入 2。(2) 查看 C1 和 C2 之间是否存在直接路径关系。如果是，在 C1/C2 的路由表中它们应该是相邻的，则 Dis(C1,C2) = minWr(C1,C2), Wr(C2,C1)；如果否，转入 3。(3) 查看 C1 和 C2 之间是否存在间接的路径关系。如果是，在 C1/ C2 的节点路径表中应该存在某些记录如 path(C1,Cm, Cm+i，C2)， 记 Dis1(C1, C2) = sumWr(C1,Cm) + + Wr(Cm+i,C2)（如果有多条路径取最小值）, 记 Dis2(C1,C2) = minDis(C1,Cn) + minD

14、is(C2,Cn)则 Dis(C1, C2) = min Dis1(C1, C2),Dis2(C1,C2)； 如果否，转入 4.(4) C1 和 C2 之间无间接路径关系，语义距离应等于概念 C1 和 C2 分别到根节点的最短语 义距离，也即 Dis(C1, C2) = minDis(C1,Cn) + minDis(C2,Cn)例 1：计算 Dis(H,D)满足算法的第三种情况，H到D存在两条间接的路径关系(H,E,C,F,D,A) (1.25,1.5,2.5,1.5,2)(H,E,F,D,A) (1.125,1.25,1.5,2)，因此有Dis1(H,D) = min(1.25+1.5+2.

15、5+1.5), (1.125 + 1.25+ 1.5) = min 6.75 , 3.875 = 3.875; Dis2(H,D) = min (Dis (H,A) + min(Dis(D,A) = (1.25+2) + 2 = 5 .25Dis(H,D) = min Dis1, Dis2, Dis3 = Dis2 = 3.875例 2：计算 Dis(B,E)满足第四种情况，Dis(B,E) = minDis(B,A) + minDis(E,A) = 2 + (2+1.5)= 5.52.4 计算相似度通过2.3得到两个概念之间的语义距离之后，需要构造合理的相似度函数，将语义距离 转化成相似度。

16、相似度函数需要满足的几个主要特性9，如下所示：(1) 当语义距离为0时，相似度为1。即当两个概念相同时，相似度为1。(2) 此函数随语义距离的增加而减小。即语义距离大的概念间的相似度小于语义距离小 的概念间的相似度。(3) 函数的输出必须保证在0,1区间内。 符合以上三个主要特性的相似度函数有很多，如：SF1=1/(distance+1); SF2=1/(distance2+1); SF3=1/edistance. 这三个相似度函数的区别在于，它们随distance增加时的下降速度不同。 SF1采用倒数下降，这实际上是一种线性下降，即distance=1时，SF1=1/2，distance=2

17、时，SF1=1/3； SF2采用平方下降，这种下降速度比SF1线性下降要快，而且随distance增加下降更快； SF3 采用指数下降，这是三种相似度函数中下降速度最快的一种，当distance=2 时，SF3=1/e2=0.14，即当distance到达2时，相似度就已经小于15%，而且这种下降趋势会随distance增加更加快。由于后两个函数的下降速度过快，因此我们选取类SF1的相似度函数，并将其修正为 SF=1/( k * distance+1) (K1), k的取值决定了语义距离对相似度影响程度的大小，该参数的具体 取值需要通过实验来确定。3实验及结果分析以图二所示的本体为基础，对于概

18、念 C 和其它概念之间的相似度，通过本算法使用不 同参数得出的结果如表一所示。表 1 C 和其它概念之间的相似度ABCDEFGHM=3,Factor=0.30.6250.4545510.454550.689660.470590.454550.54795M=3,Factor=0.20.714290.5555610.555560.769230.571430.555560.6456M=2,Factor=0.30.6250.4545510.454550.689660.571430.454550.54795M=2,Factor=0.20.714290.5555610.555560.769230.6666

19、70.555560.64516由于不存在精确的尺度来衡量两个概念之间绝对的相似度，一方面只能通过领域专家来判断计算结果是否正确，另一方面计算相似度的目的是为了得出其它概念和某个概念之间的 匹配顺序以取得最佳匹配，因此可以分别从上述两方面考察相似度算法的合理性，并选取合 适的参数。根据图一的本体，领域专家对于概念 C ，给出的其它概念匹配顺序为 C,E,A,H,F,D,B,G， 即首先是概念本身，其次是父子节点，其次是较近的属性节点，其次是兄弟节点（该排序可 能因具体的应用领域而有所不同，不同的专家对整个顺序也可能会有不同的意见，但最佳匹 配的前几位的顺序是基本一致的。）在表一中，虽然参数不同，

20、但是根据相似度得出的匹配顺序是基本一致的，唯一的差别 在于当 m 取不同的值时，C 和 F 之间的相似度所处的排名略有不同（图三），这是因为 C 和 F 之间存在直接的二元关系，而 m 的取值决定了这个二元关系的权重，因此直接会影响到 相似度，根据专家的结果，H 应该排名在 F 之前，因此 S(C,H)应大于 S(C,F)，故取 m=3 更 接近专家的意见。在 m 值一定的情况下，参数 factor 对相似度的影响非常细微（图四），不 会改变整体的匹配顺序，关键在于取哪个值会使得相似度结果更符合直观的取值。父子关系 之间的相似度最低应该在 0.70.8 之间，因此 factor 取值 0.2

21、更为合理。通过大量的比较之 后，本算法选取 m=3，factor=0.2 作为建议参数，对其进行细微的修正如 m=0.28 或 factor=0.22 将不会对结果产生本质影响，但对于其它的情况如 m=4 或者 factor = 0.1， 由于它们将导致 相似度值不在符合直观的范围内（实验数据也说明了这点，鉴于篇幅不再一一列出），故不 建议对参数进行大于 0.1 的修正。图 3 相似度(factor = 0.2)图 4 相似度（m =3）4. 总结本文提出了本体概念之间相似度计算的方法，本算法不仅考虑了概念之间的继承关系和 二元关系，也考虑了深度对相似度的影响，并通过实验数据得到了算法中合理的

22、推荐使用参 数。利用本算法可以计算某个参照概念和备选概念之间的相似度并进行排序以获得最佳匹配 顺序，在语义 web 服务匹配中，如果服务接口是由单个本体概念构成则可以直接应用本算 法，如果是多个概念组成的集合则可以先将本算法应用到概念集合的匹配中，再根据概念集 合的相似度进行匹配。如何基于本算法构建概念集合的相似度算法是本文的下一步研究方 向。参考文献1 Tim Berners2lee, J Hendler, O Lissala. The SemanticWebJ. Si2 mantific American, 2001, 284 (5): 342432 Eric Miller, Ralph

23、Swick, Dan Brickley. Resource Description Framework (RDF) EB/OL. http: /www. w3. org/RDF3 W3C. OWL Web Ontology Language Guide EB/ OL . 2004. http :/ / www. w3. org/ TR/ owl - guide.4 M Paolucci, T Kawamura, TR Payne, K Sycara ：“Semantic Matching of Web Services Capabilities”Proceedings of the 1st I

24、nternational Semantic Web Conference , 20025 Stefan Tang：“MATCHING OF WEB SERVICE SPECIFICATIONS USING DAML-S DESCRIPTIONS“March 18th, 20046 YASSER GANJISAFFAR, HASSAN ABOLHASSANI, MAHMOOD NESHATI, and MOHSEN JAMALI ：“A Similarity Measure for OWL-S Annotated Web Services”; Proceedings of the 2006 IE

25、EE/WIC/ACM International Conference on Web Intelligence (WI 2006 Main Conference Proceedings)(WI06)7 Jeffrey Hau ， William Lee ， John Darlington ： “A Semantic Similarity Measure for Semantic WebServices”.WWW2005, May 1014, 2005, Chiba, Japan.8 Li Kuang, Jian Wu, Shuiguang Deng, Ying Li, Wei Shi, Zha

26、ohui Wu. “Exploring Semantic Technologies inService Matchmaking”, Proceedings of the Third European Conference on Web Services (ECOWS05)9 Sycara, K., Widoff, S., Klusch, M., Lu, J.: Larks: Dynamic matchmaking among heterogeneous software agents in cyberspace. Autonomous Agents and Multi-Agent System

27、s 5 (2002) 173-203An Approach for Measuring Similarity Degree between Ontology Concepts in Semantic Web Services Matchmaking Liu Qian，Shuang Kai，Chen WeiState Key Laboratory of Networking & Switching Technology，Beijing University of Posts &Telecommunications，Beijing （100875）AbstractSimilarity degree

28、 measuring based on ontology is the key to automated matchmaking of semantic web services. In this paper we explore the determination of semantic similarity between two ontologyconceptsfromseveralaspects:propertyrelationship,inheritancerelationshipespecially multi-inheritance among concepts, and the

29、 impact of the concepts depth to similarity degree. Wedefined a weight distribution approach to measure the semantic distance of two concepts, according towhich we present a math formula to compute the similarity degree. Experimental evaluation demonstrates that the proposed algorithm outperforms traditional similarity measures and accords with field experts anticipated results.Keywords：Semantic Web Services，Matchmaking，Similarity Degree