基于语义的Web服务匹配算法研究

摘要:针对基于推理的OWL-S/UDDI匹配算法在同一级结果间不能进一步区分匹配度导致查全率和查准率不高的问题,提出了一种基于本体概念相似度计算的服务匹配算法,该算法分别按服务的基本描述、功能和非功能(QoS)三个层次进行匹配,提高了服务匹配效率。

关键词:语义;Web服务;OWL-S;服务匹配

中图分类号:TP393 文献标识码:A 文章编号:1009-3044(2009)15-3989-04

Research on Web Service Matching Algorithm Based on Semantic

PENG Bo

(Computer Center,Anhui Medical University,Hefei 230032,China)

Abstract: The OWL-S/UDDI matching algorithm based on reasoning cannot differentiate the matching degree on the same results level,thus causing inaccuracy and incompleteness.According this shortcoming of reserch, this paper proposes a Web service matching algorithm based on similarity computing of ontology concept.The algorithm has three levels:the basic description matching,the function matching ,and the non-function matching(QoS).This algorithm can improves the efficiency of services matching.

Key words: semantic;Web service;OWL-S;service matching

1 引言

面向服务体系结构(SOA)是网络环境下分布式应用系统的概念模型,在这个模型中松散耦合的系统组件在网络上被描述、和调用。实现SOA的主要方式是基于WSDL/UDDI的Web服务技术,Web服务的关键是服务的发现,基于语法级的服务描述语言和基于关键字的服务匹配算法导致了服务查准率低。语义Web服务综合了语义网技术和Web服务技术的优点,通过扩展UDDI,加入领域本体库,为每个注册服务添加语义信息等技术能够为Web服务的自动发现、执行、解释和自动组合提供有效支持。

本文首先介绍了基于推理的OWL-S/UDDI语义Web服务匹配算法,针对其同一级匹配结果间不能进一步区分的问题,提出了一种基于本体概念相似度计算的语义Web服务分级匹配算法。

2 相关技术概述

2.1 本体

目前较为公认的本体定义是Rudi Stuger于1998年提出的:“本体是共享概念的明确的、形式化的规范描述[1]”。通俗地讲,本体是为了让计算机对现实世界某一领域中的概念及概念间的关系有明确、一致的理解而进行的形式化、规范化的描述。本体的优点在于它能指导人们对某一领域的知识达到一致的认识和理解,并使用计算机进行描述和逻辑推理,从而达到语义Web的目标。

2.2 Web服务描述语言

实现语义Web服务的关键步骤是对Web服务进行语义描述。OWL-S是一种描述Web服务的本体语言,其前身是DAML-S,它为Web服务提供了核心的标记语言结构,用于精确描述Web服务的属性和能力,这些描述能被计算机无二义性的解释理解,从而实现服务的自动发现、执行和组合。这个描述至少包括三个方面语义:ServiceProfile提供服务的抽象描述,如服务实体、服务可以实现的功能,以及服务的性能参数等;ServiceModel描述Web服务如何执行,包括服务执行的先后顺序、过程流程等;ServiceGrounding描述了如何调用Web服务,描述具体的绑定信息,例如服务地址、通信协议及消息格式等。

2.3 OWL-S ServiceProfile

OWL-S Profile描述服务的三个基本方面:服务提供者的信息、服务的功能和服务的其他特征。ServiceProfile第一组属性描述Web服务提供实体,包括提供者名称(ServiceName) 、描述文本(textDescription)和联系信息(ContactInformation)。 ServiceProfile第二组属性描述服务功能,这是最本质的部分,表达了服务性能的两个方面:一是从信息流角度:输入信息Inputs和输出信息Outputs;二是从状态流角度:服务所需的前置条件Precondition以及服务执行后的结果Effect。ServiceProfile第三组属性描述服务的其他特征,包括服务分类ServiceCategory和服务等级QualityRating(提供服务质量信息)等。

本文将ServiceProfile作为广告在服务注册中心,并利用ServiceProfile的信息进行服务匹配。同时,服务请求也将ServiceProfile作为表达服务查询条件的语言,从而使服务匹配能够更加方便。

3 基于语义的Web服务匹配算法

3.1 基于推理的OWL-S/UDDI服务匹配算法

基于推理的服务匹配是利用本体概念间的包含关系来判断服务的请求方和方的匹配程度。Massimo Paolucci等于2002年首先提出了一种基于DAML-S的服务匹配算法[2],利用DAML-S的Service Profile对服务的输入、输出、前提、效果(IOPE)进行匹配。该方法定义了四种匹配程度(以输出匹配为例,设outR为请求者的一个输出,outA为服务者的一个输出):

1) Exact: 当outR与outA相同或outR是outA的直接子类(subClassOf)时,结果为Exact。

2) Plug-In:如果outA包含outR,也就是说outA可能完全满足outR。

3) Subsume:如果outR包含outA,即outA能部分满足outR但不是完全满足。

4) Fail:在outR和outA之间没有任何包含关系,匹配失败。

随后,LeiLi等人对上述四种匹配类型进行了补充,在Subsume和Fail之间添加了Intersection,即outR与outA的交集是可满足的(outR∩outA≠Φ,但outR不包含outA),说明outA有可能满足outR的部分功能。从上述介绍可以看出,基于推理的OWL-S/UDDI服务匹配方法将服务间的匹配程度分为5个等级:Exact Plug-In Subsume Intersection Fail,但在同一等级内部无法进一步区分匹配度。

3.2 Web服务描述模型

在介绍匹配算法之前,先创建服务描述模型,将服务描述为:WS=.其中S是基本描述,是服务的公共属性,包括服务分类、服务名称,文本描述等。F是服务功能描述,即服务功能包括输入与输出,前提与结果等。NF是非功能的属性描述,如服务质量(QoS)。

3.3 Web服务匹配算法的分级匹配过程

算法的基本原理:服务请求者先提供一个OWL-S文档,对其所需服务进行描述。在预处理阶段,通过服务分类匹配(可通过属性ServiceCategory来判断)去掉不属于请求服务分类的注册服务,将分类符合的服务放入候选集中,首先进行基本描述匹配,经由基本描述匹配筛选的候选服务再参与功能匹配,合格的服务再进一步参与QoS非功能属性的匹配。下面详细介绍各部分的匹配过程。

3.3.1 基本描述的匹配

服务的名称和文本描述是已经在Web服务本体中的概念实体、概念属性以及概念间的关系,所以其计算的基础是概念间语义相似度。对于本体库中概念以及概念间上下位关系(subClassOf)形成的概念树,可用2个不同节点之间的距离来衡量节点概念间的相似度。因服务匹配的要求,定义概念树中节点的距离如下:

定义1概念树定义为一棵有向树,对于树中的每一条有向边,如果Vi是Vj的父节点,Vj是Vi的子节点,则Vi包含Vj。

定义2对于概念树中的任意2个节点Vi,Vj的距离distance(Vi,Vj),定义为:

1) 如果Vi与Vj为树中相同节点,则distance(Vi,Vj)=0

2) 如果从节点Vi没有路径到达Vj,且从节点Vi也没有路径到达Vj,则distance(Vi,Vj)=∞

3) 如果从节点Vi有路径到达Vj,则distance(Vi,Vj)为从Vi到达Vj的路径的长度。

4) 如果从节点Vj反方向有路径到达Vi,则distance(Vi,Vj)为Vj从到达Vi的路径长度的负数。

定义3概念树中2个节点所表示的概念相似度函数定义如下,设结点Vi表示的概念为Cvi,结点Vj表示的概念为Cvj。

其中AS是广告服务,RS是请求服务,Simsn(AS,RS)是服务名称的相似度,Simtd(AS,RS)是文本描述的相似度。SimBasic(AS,RS)的结果是0到1之间的实数值。其中wi是用户自定义的权值。

w1+ w2=1,0≤wi≤1,i=1,2

基本描述匹配算法描述:

BasicDescriptionMatch(RS,AS,Reasoner reasoner)

{

Int BasicMatch=0;

Ucandidates=Ф;//候选子集初始为空

BasicMatch=reasoner.SimBasic(RS,AS);//由推理机计算SimBasic

for (int i=0;ASФ;i++){

if BasicMatch>Num1 //Num1是用户设定的匹配阈值

ADD(Ucandidates,ASi);//将符合条件的AS加入候选集中

endif

}

}

3.3.2 服务功能的匹配

在这个阶段,使用基于WordNet和HowNet通过语义相似度的计算方法来计算请求服务与广告服务的匹配相似度。

WordNet是一个以同义词集合为单位来组织信息的语义词典,是基于英文的词汇语义网络系统。它为英语词语相似度的计算提供了便利。目前基于WordNet的相似度计算方法很多,如res、lin和jcn等方法使用WordNet中的上下位关系计算相似度;hso、lesk和vector等方法使用WordNet中包括上下位关系的所有关系计算相似度[3]。

为了在使用WordNet中所有信息关系的同时充分使用上下位关系,本文在计算英文信息的相似度时选择两个典型的方法:lin和lesk,其中对方法lin进行改进,再分别计算得到概念相似度Slin和Slesk,然后取Slin和Slesk的加权和作为英文概念最终的相似度值。

方法Lin是利用概率的方法计算两个概念的相似度。

在寻找词义Cvi和Cvj的共同上位词时,通过路径的方法,设定了一个系数αl/2。其中α是一个介于0和1之间的常数,用来调整随层次加深,相似度随之递减的程度, 表示在某个同义词层次结构中,寻找词义Cvi和Cvj的共同上位词的最大路径。由于Cvi和Cvj两个词义,故乘以1/2。

HowNet是一个用以揭示概念与概念之间以及概念所具有属性之间的关系的常识知识库,是目前最完善的汉语语义知识词典。本文设汉语概念的语义相似度为Sch,使用刘群[4]等人提出的基于HowNet的语义相似度计算方法可得到汉语概念相似度值。最后对英文概念相似度值和汉语概念相似度值加权平均得到公式(4):

其中μi是用户自定义的权值。μ1+μ2+μ3=1,0≤μi≤1,i=1,2,3

设Ains表示广告服务输入参数的集合,Rins表示请求服务输入参数的集合,Aous表示广告服务输出参数的集合,Rous表示请求服务输出参数的集合,Aprs表示广告服务的前提条件参数的集合,Rprs表示请求服务前提条件参数的集合,Aes表示广告服务影响参数的集合,Res表示请求服务结果影响参数的集合。在这里需注意的是这四个参数都是本体中的概念而不是原子数据类型。基于公式(4),函数SimIOPE(AS,RS)可计算服务的功能性特征(IOPE)的匹配度,其参数是广告服务(AS)和请求服务(RS),其结果是0至1之间的实数值。

服务功能的相似度计算公式如下:

其中α1、α2、α3、α4分别是输入集、输出集、前提条件集、结果影响集的权值,

α1+α2+α3+α4=1,0≤αi≤1,i=1,2,3,4. 权值可由用户决定,如果用户没有对权值的要求,则可采用默认的平均权值,即视这四个方面同等重要。

功能匹配算法描述:

由于PR和IO的匹配算法相似,在这里只对IO匹配加以说明。

ParametersMatch(RS,AS,Reasoner reasoner)

{

Ucandidates=Ф;//候选子集初始为空

//inputs匹配

int inMatch=0;

int inCount1=RS.getInputs().size;

int inCount2=AS.getInputs().size;

for(int i=0;i

for(int j=0;inCount1;j++){ //由推理机根据公式(5)计算相似度

inMatch=reasoner.Parametermatch(RS.getinputs(i),AS.getinputs(j));

ifinMatch>Num2 // Num2是用户设定的匹配阈值

ADD(Ucandidates,ASi);//将符合条件的AS加入候选集中

Endif

}

}

//outputs匹配

int outMatch=0;

int outCount1=RS.getOutputs().size;

int outCount2=AS.getOutputs().size;

for(int i=0;i

for(int j=0;outCount1;j++){ //由推理机根据公式(5)计算相似度

outMatch=reasoner.Parametermatch(RS.getoutputs(i),AS.getoutputs(j));

ifoutMatch>Num2 // Num2是用户设定的匹配阈值

ADD(Ucandidates,ASi);//将符合条件的AS加入候选集中

Endif

}

}

3.3.3 非功能属性QoS的匹配

功能性的匹配只满足了请求服务方静态的常规要求,这些常规要求相对固定。而如果用户想要获得高质量的Web服务,还需要用一些非功能的属性来量化其服务功能,这就是Web服务的QoS(Quality of Service),文献[5]中Joge Cardoso给出了服务质量评价模型中应包括的因素,具体包括费用(cost)、时间(time)、可靠性(reliability)。这里再增加信誉度(Credit)因素。

函数SimQoS(AS,RS)计算广告服务AS和请求服务RS的QoS相似度。可通过分别计算AS和RS的QoS中各维相似度的几何距离来计算。函数返回一个0至1之间的实数,返回值越接近1,说明AS和RS越相似。

服务质量匹配算法描述:

QoSMatch(RS,AS,Reasoner reasoner)

{

IntQoSMatch=0;

Ucandidates=Ф;//候选子集初始为空

QoSMatch=reasoner.SimQoS(RS,AS);//由推理机计算SimQoS

for (int i=0;ASФ;i++){

if BasicMatch>Num4 //Num4是用户设定的匹配阈值

ADD(Ucandidates,ASi);//将符合条件的AS加入候选集中

endif

}

}

4 算法性能分析

在评价服务匹配算法效率方面,通常用查准率和查全率来衡量一个Web服务匹配算法的好坏。查准率是指查询返回符合查询条件的Web服务数量与查询返回Web服务总数量的比率;查全率是指查询返回符合查询条件的Web服务数量与测试样本集中符合查询条件的Web服务数量的比率。查准率和查全率越高,服务匹配算法越好。为了验证本文匹配算法的有效性,设计了一个原型系统WSMS(服务匹配系统),本文选取医学诊断专家系统本体文件及100个可用于查询疾病诊疗方案的Web服务,对于本文算法和OWL-S/UDDI匹配算法进行仿真性能测试,测试结果如表1所示。

由此可见,本文算法综合考虑了服务的基本描述、服务功能和服务质量三个方面的相似度,具有较高的服务发现效率。

5 结束语

本文分析了基于推理的服务匹配算法的局限性,提出了一种基于本体概念相似度计算的服务匹配算法。实验结果表明该算法能过滤掉大多数不相关服务,缩小服务匹配范围,提高了服务匹配效率。下一步将完善算法和原型系统,考虑在语义网中存在多个异构本体情况下进一步改进服务匹配算法。

参考文献:

[1] Rudi Stuger,Richard Benjam ins V. Knowledge Engineering:Principles and Methods[J]. .Data and Knowledge Engineering 1998,25(2):161.

[2] Massimo Paolucci,Takahiro Kawamura,Terry R Payne. Semantic matching of Web services capabilities[C]. In Proceedings of the First International Semantic Web Conference(ISWC).

[3] 余晓峰.面向译文选择的双语语义词典自动构建研究[D].哈尔滨:哈尔滨工业大学,2005:30-42.

[4] 刘群,李素建.基于《知网》的词汇语义相似度计算[J].Computational Linguistics and Chinese Language Processing, 2002, 7(2):59-76.

[5] Cardoso J.Bussler C.Semantic Web Services and Processes:Semantic Composition and Quality of Service[C].On the Move to Meaningfull Internet Computer 2002.