论文部分内容阅读
[摘 要]传统的基于UDDI的Web服务查询算法对于服务提供者与服务发现者之间术语不一致的问题无能为力,为了解决这个问题,本体被引入Web 服务之中,目前已经有一些新的Web服务查询算法把本体考虑进来,但是这些算法虽然提高了查全率,却在一定程度上降低了查准率。本文主要从提高查准率和用户满意度的角度,讨论了一个基于查询弱化技术的Web服务查询算法,并把该算法和另外一个算法作了简单的比较分析,然后用一个实例验证了算法的有效性。
[关键词]本体;Web服务;语义弱化;服务发现
1 引 言
传统的基于UDDI的Web服务发现机制是基于关键词的检索技术,检索的主要依据是Web服务的名称,如果服务请求者和服务发现者使用的术语不一致,使用基于关键词的检索技术无法发现满足条件的所有Web服务。
已经有研究者提出在Web服务中引入领域本体来解决这个问题,在文[1]中,作者通过结合一个具体的试验项目METEOR-S,探讨了如何构造一个基于本体的Web服务具有良好扩展性以及系统的构架,同时在文中指出通过匹配IOPE(input,output,precondi-tion,effect)来进行Web服务发现,但是并未给出其算法细节。
文[2]、[3]讨论了基于本体的Web服务匹配算法,其主要思想是通过Web服务的IO(input,output)参数类型和本体关联,通过匹配web服务的输入输出参数类型来决定某一个Web服务是否是所要查找的Web服务,分别提出了计算匹配度的方法,可以把匹配度作为查询结果排序的依据。该算法的问题是当Web服务的IOPE是查询条件的上位类时,就认为匹配,这样降低了查准率。
文[4]、[5]从用户满意度的角度指出精确匹配是多余的,应允许非精确匹配的存在。文[4]更是通过一个语义Web服务的用例,指出在大多数情况下只需要匹配OE(output,effect)。文[5]中提出把Web服务参数依据客户的要求是强制性还是非强制性,分为软性条件(soft condition)和硬性条件(hard condition),应该对这两类条件采取不同的匹配策略。
本文在这些研究的基础上,从提高查准率和用户满意度的角度出发,提出了一个基于本体的Web服务查询弱化算法。
2 基于语义的Web服务查询弱化算法
2.1 算法思想
该算法思想是用迭代式的强制匹配来获得较高的查准率。每一次迭代过程后对于软性条件(soft condi-tion)弱化一次,所谓弱化就是用查询条件的上位概念来替代它,由于查询条件不断被弱化,Web服务被发现的可能就越来越大,这一迭代查询过程直到某一个条件被满足为止(例如,检索出的结果集包含了~定数量的Web服务,或者弱化到了一定的距离就自动返回)。算法的输入是Web服务的输入输出参数fIs(input soft),In(input hard),Os(output soft),Oh(output hard),记为集合C,对应领域本体中相应的概念。把UDDI中的每一个注册服务与集合C进行hard match,假设得到的结果集为R,如果R包含了大于阈值的Web服务,那么算法返回,否则对查询条件C进行弱化,得到查询条件C1,再用C1和每一个注册服务进行Hard match,如此往复。通过对阈值的设定,可以对Web服务的查全率和查准率都做到较好的控制。
2.2 算法描述
为了方便描述算法,先引用文[3]中的定义:
定义1 Web服务可以描述为:
WSi(Ii,Oi)
Ii是输入参数类型(与本体对应),Oi;是输出参数类型。
定义2 WSi和WSj精确匹配表示如下:
Exact(WSi,Wsi)={Iiequivalentclassof Ii l and Oiequivalentclassof Oi}
基于查询弱化的查询算法如下:
(1)设定初始弱化次数Relaxcount为Oi,查询结果集WSResult为空。
(2)把查询条件{Input condition,output conditionl与UDDI中的每一个注册Web服务的输入输出参数进行匹配,如果是精确匹配,就是定义2所指的Exact匹配,就把这一个注册Web服务加到查询结果集中。
(3)如果查询结果集WSResult包含的Web服务数量超过了一个阈值,或者查询条件fInput condition,output condition}弱化的次数(也就是Relaxcount的大小)大于某一个阈值,抑或查询条件{Input condition,output condition}中的参数都已经弱化到了对应的本体中的根节点,那么算法结束,否则转到(4)。
(4)记查询条件中的软条件{soft input condition,soft output condition}为R,计算R中的每个参数在本体中的深度(也就是其到本体根的距离),找出深度最大的参数,如果这样的参数只有一个,那么把该参数替换为其本体中的父节点,Relaxcount=Relaxcount+1,执行转到(2),否则转到(5)。
(5)计算具有最大深度的参数对应的概念在本体中的父节点的出度,找出那些具有最大父节点出度的参数,如果只有一个参数的父节点具有最大出度,那么把该参数替换为其本体中的父节点,Relaxcount=Re-laxcount+l,执行转到(2),否则转到(6)。
(6)找出具有最大深度的参数中最左边的一个,那么把其替换为其本体中的父节点,Relaxcount=Relax-count+1,执行转到(2)。
在上面的描述中,(4)到(6)是查询条件弱化的过程。对于查询条件的弱化是算法的关键,弱化策略(也即哪些参数应该优先弱化)的好坏直接决定了下一轮匹配的结果,进而决定了查全率和查准率。在本体中,根到节点的距离越大,往往表示某一个节点所代表的概念越专指。如果两个节点到根的距离是一样的,那么父节点出度大的概念的专指度大。如果其父节点的出度也相同,那么认为这两个节点的专指度是一样的。进行查询条件弱化时,我们总是先把最专指的条件进行弱化,也就是往树根的方向走,这样的弱化顺序带来的语义损失最小,因而可以带来最好的查全率和查准率的平衡。
假设有图l所示的本体,包含3个本体Hotel、Lo-cation、Food,假设有一个用户需要来到某一个城市,需要使用该市的宾馆预定服务,输入的有餐饮类型以及宾馆的位置,输出是宾馆名称。假设用户想要预定市中心某个位置附近能提供中国菜的某一宾馆,那么查询Web服务时就转换为接受参数类型fcenter,chinese-food},以此作为Web服务查找的条件。假设该市的预定服务可能有以下几个:
{Bookl{location,Food),Book2{City,Chinesefood},Book3{city food}}
假设所有的条件都是soft condition。下列表格演示了算法的执行过程:
结 论
由上可见,该算法能够完成设计目标,即完成基于语义的匹配,而且算法产生的结果是按语义损失由小到大排序的,因而总是最前面的结果满足用户的查询需求。该算法和文[2]中提出的算法相比较,其执行效率要低一些,因为可能要进行反复查询,但是提供了更高的准确度,因为算法执行的过程是从最符合查询要求的结果开始过渡到不那么符合条件的检索结果,也就是说该算法提供了web服务的排序机制,同时还可以通过控制阈值对算法的执行次数以及结果集大小进行控制。该算法还有改进的余地,通过一定的手段,可以减少查询弱化的次数,例如每次向上弱化条件时,可以弱化两层,或同时弱化两个节点,另外弱化的顺序还有进一步改进的余地,特别是一个已经弱化过的节点,如果和一个没有弱化过的节点的深度一样的话,那么它应该在没有弱化过的节点之后弱化,这样带来的语义损失要小一些,可以提供更高的查询精度。
[关键词]本体;Web服务;语义弱化;服务发现
1 引 言
传统的基于UDDI的Web服务发现机制是基于关键词的检索技术,检索的主要依据是Web服务的名称,如果服务请求者和服务发现者使用的术语不一致,使用基于关键词的检索技术无法发现满足条件的所有Web服务。
已经有研究者提出在Web服务中引入领域本体来解决这个问题,在文[1]中,作者通过结合一个具体的试验项目METEOR-S,探讨了如何构造一个基于本体的Web服务具有良好扩展性以及系统的构架,同时在文中指出通过匹配IOPE(input,output,precondi-tion,effect)来进行Web服务发现,但是并未给出其算法细节。
文[2]、[3]讨论了基于本体的Web服务匹配算法,其主要思想是通过Web服务的IO(input,output)参数类型和本体关联,通过匹配web服务的输入输出参数类型来决定某一个Web服务是否是所要查找的Web服务,分别提出了计算匹配度的方法,可以把匹配度作为查询结果排序的依据。该算法的问题是当Web服务的IOPE是查询条件的上位类时,就认为匹配,这样降低了查准率。
文[4]、[5]从用户满意度的角度指出精确匹配是多余的,应允许非精确匹配的存在。文[4]更是通过一个语义Web服务的用例,指出在大多数情况下只需要匹配OE(output,effect)。文[5]中提出把Web服务参数依据客户的要求是强制性还是非强制性,分为软性条件(soft condition)和硬性条件(hard condition),应该对这两类条件采取不同的匹配策略。
本文在这些研究的基础上,从提高查准率和用户满意度的角度出发,提出了一个基于本体的Web服务查询弱化算法。
2 基于语义的Web服务查询弱化算法
2.1 算法思想
该算法思想是用迭代式的强制匹配来获得较高的查准率。每一次迭代过程后对于软性条件(soft condi-tion)弱化一次,所谓弱化就是用查询条件的上位概念来替代它,由于查询条件不断被弱化,Web服务被发现的可能就越来越大,这一迭代查询过程直到某一个条件被满足为止(例如,检索出的结果集包含了~定数量的Web服务,或者弱化到了一定的距离就自动返回)。算法的输入是Web服务的输入输出参数fIs(input soft),In(input hard),Os(output soft),Oh(output hard),记为集合C,对应领域本体中相应的概念。把UDDI中的每一个注册服务与集合C进行hard match,假设得到的结果集为R,如果R包含了大于阈值的Web服务,那么算法返回,否则对查询条件C进行弱化,得到查询条件C1,再用C1和每一个注册服务进行Hard match,如此往复。通过对阈值的设定,可以对Web服务的查全率和查准率都做到较好的控制。
2.2 算法描述
为了方便描述算法,先引用文[3]中的定义:
定义1 Web服务可以描述为:
WSi(Ii,Oi)
Ii是输入参数类型(与本体对应),Oi;是输出参数类型。
定义2 WSi和WSj精确匹配表示如下:
Exact(WSi,Wsi)={Iiequivalentclassof Ii l and Oiequivalentclassof Oi}
基于查询弱化的查询算法如下:
(1)设定初始弱化次数Relaxcount为Oi,查询结果集WSResult为空。
(2)把查询条件{Input condition,output conditionl与UDDI中的每一个注册Web服务的输入输出参数进行匹配,如果是精确匹配,就是定义2所指的Exact匹配,就把这一个注册Web服务加到查询结果集中。
(3)如果查询结果集WSResult包含的Web服务数量超过了一个阈值,或者查询条件fInput condition,output condition}弱化的次数(也就是Relaxcount的大小)大于某一个阈值,抑或查询条件{Input condition,output condition}中的参数都已经弱化到了对应的本体中的根节点,那么算法结束,否则转到(4)。
(4)记查询条件中的软条件{soft input condition,soft output condition}为R,计算R中的每个参数在本体中的深度(也就是其到本体根的距离),找出深度最大的参数,如果这样的参数只有一个,那么把该参数替换为其本体中的父节点,Relaxcount=Relaxcount+1,执行转到(2),否则转到(5)。
(5)计算具有最大深度的参数对应的概念在本体中的父节点的出度,找出那些具有最大父节点出度的参数,如果只有一个参数的父节点具有最大出度,那么把该参数替换为其本体中的父节点,Relaxcount=Re-laxcount+l,执行转到(2),否则转到(6)。
(6)找出具有最大深度的参数中最左边的一个,那么把其替换为其本体中的父节点,Relaxcount=Relax-count+1,执行转到(2)。
在上面的描述中,(4)到(6)是查询条件弱化的过程。对于查询条件的弱化是算法的关键,弱化策略(也即哪些参数应该优先弱化)的好坏直接决定了下一轮匹配的结果,进而决定了查全率和查准率。在本体中,根到节点的距离越大,往往表示某一个节点所代表的概念越专指。如果两个节点到根的距离是一样的,那么父节点出度大的概念的专指度大。如果其父节点的出度也相同,那么认为这两个节点的专指度是一样的。进行查询条件弱化时,我们总是先把最专指的条件进行弱化,也就是往树根的方向走,这样的弱化顺序带来的语义损失最小,因而可以带来最好的查全率和查准率的平衡。
假设有图l所示的本体,包含3个本体Hotel、Lo-cation、Food,假设有一个用户需要来到某一个城市,需要使用该市的宾馆预定服务,输入的有餐饮类型以及宾馆的位置,输出是宾馆名称。假设用户想要预定市中心某个位置附近能提供中国菜的某一宾馆,那么查询Web服务时就转换为接受参数类型fcenter,chinese-food},以此作为Web服务查找的条件。假设该市的预定服务可能有以下几个:
{Bookl{location,Food),Book2{City,Chinesefood},Book3{city food}}
假设所有的条件都是soft condition。下列表格演示了算法的执行过程:
结 论
由上可见,该算法能够完成设计目标,即完成基于语义的匹配,而且算法产生的结果是按语义损失由小到大排序的,因而总是最前面的结果满足用户的查询需求。该算法和文[2]中提出的算法相比较,其执行效率要低一些,因为可能要进行反复查询,但是提供了更高的准确度,因为算法执行的过程是从最符合查询要求的结果开始过渡到不那么符合条件的检索结果,也就是说该算法提供了web服务的排序机制,同时还可以通过控制阈值对算法的执行次数以及结果集大小进行控制。该算法还有改进的余地,通过一定的手段,可以减少查询弱化的次数,例如每次向上弱化条件时,可以弱化两层,或同时弱化两个节点,另外弱化的顺序还有进一步改进的余地,特别是一个已经弱化过的节点,如果和一个没有弱化过的节点的深度一样的话,那么它应该在没有弱化过的节点之后弱化,这样带来的语义损失要小一些,可以提供更高的查询精度。