论文研究-基于本体和二部图的网格服务发现算法研究.pdf

所需积分/C币:5 2019-09-11 12:47:18 543KB .PDF
17
收藏 收藏
举报

为了提高网格服务发现的查全率、查准率和效率,论文设计了一个基于本体和二部图的网格服务发现算法OGSDA-BG。该算法把请求服务和发布服务的属性集分别作为二部图顶点集,所有匹配属性之间的连线为边,边权是属性匹配度,把问题转换为二部图的最优完全匹配。实验结果表明该算法的查全率和查准率较以前的算法提高了10%~50%,尽管服务发现的效率降低10%左右,但是在可接受范围之内。
102008,44(1) Computer Engineering and Applications计算机工程与应用 低,只有20%,这是因为本组的贪心算法不从候选列表中删除 函数 Search()调用了另外一个计算完全匹配的函数Com-属性。 pleteMatch(),根据输入的请求服务的属性集P和发布服务的 第2组:本组的贪心算法从候选列表中删除属性。用本体 属性集P,该函数构建一个部图,并调用匈牙利算法求出该构建了6个请求服务,由于要在415个发布服务中搜索6个请 二部图的一个最优完全匹配 求服务,就会有6×415=2490个匹配。理想情况下,所有的6个 CompleteMatch(PR, P) 请求服务都能找到相应的发布服务。实际结果如下所示:贪心 算法和 OGSDA-BG算法的查准率都是100%, OGSDA-BG算 G=new Empty Graph(Vo+VI, E) 法匹配了所有6个请求服务,贪心法产生了3个错误否定,导 FP2,V←P4 ← 致其查全率只有50%。 Initialize(w,,w,, w,, w,); 3.3服务发现的效率 or(i=0: i<lV,l:i++) 服务发现的效率是指服务发现的时间开销,也就是服务发 for(=0:<V1;j+) 现的速度。为了评估 OGSDA-BG算法的服务发现效率,本文注 switch( Degree(pAi,PR ) 册了15000个服务,并把它的服务发现效率与贪心算法进行 了比较,如图3所示。 case Exact: w(pu, Pri )=w,; E=EUc(p, PRi ); break; 00 case Plugin: u(pu, PR)=w,; E=EUe(pAi,PR); break 500 case Subsume: w(PAi, PR )=w3; E=EUe(pu, PRi);break ≤400 case Intersection: w(p, PR: )=w; E=EUe(p,PR); break; 3 压300 default: break 0 200 150 贪心算法 Graph G=Hungarian Match(G); 50 OGSDA-BG算法 if(G'==null return( Fail) 50100150200250300350400450 else return( max( Degree (p, PR: ))) 发布服务数量 图3服务匹配的开销 图3显示了本次实验中2个算法的搜索时间。二部图算法 3实验分析 的搜索时间比贪心算法高出10%左右,在可以接受范围之内。 3.1实验环境 者的搜索时间都是线性的,这是因为两个算法的时间复杂度 实验所用计算机的基本硬件环境为:PⅢ2.6GCPU,512M都是O(V) 内存。计算机中安装了 Microsoft windows xp professional操 作系统、Pmog200aer推理机。系统中装载了9个本体,4结束语 共3697个属性,415个发布服务。在上述环境下,对 OGSDA 论文利用二部图的特性,设计了一个网格服务发现算法 BG算法和文献[3中提出的贪心匹配算法进行了2组测试.两 OGSDA-BG。该算法把请求服务和发布服务的属性集分别作为 个算法的匹配度计算都是采用函数 Degree() 二部图顶点集,所有匹配属性之间的连线为边,边权是属性匹 32实验结果分析 配度,把问题转换为二部图的最优完全匹配。实验结果表明该 服务发现的准确度包括两个方面:查准率和査全率。而影算法的查全率和查准率较以前的算法都有较明显的提高,尽管 响二者的主要因素就是错误的肯定和错误的否定是影响服务服务发现的效率降低了一些,但在可接受范围之内。 发现准确度的两个主要因素,错误的肯定导致查准率降低,而(收稿日期:2007年9月 错误的否定导致查全率降低。 表4是采用两种算法进行服务发现的准确度对比。 参考文献: 表4服务发现准确度评佔表 [1] Universal description, discovery and integration(UDDIEB/OLJ[2007- 匹配结果 07-21.http://www.uddi.org/ 算法 匹配度 [2 OWL-S: semantic markup for Web services EB/OL.[2007-07-211 精确插拔包含兼容不匹配 查准率查全率 http://www.w3.org/submission/owl-st 第1组贪心算法100413320%100 [3] Paolucci M, Kawamura T, Payne TSemantic matching of web service capabilities[ C)/Proceedings of Ist International Semantic Web Con- 贪心算法 302487100%50% ference(Is WC2002) Berlin, 2002: 333-34 第2组 OGSDA-BG 0 02484100%100% [4] Asratian A S, Denley T, Haggkvist R Bipartite graphs and their app- lications[M]. Cambridge: Cambridge University Press, 1998 第1组:本组测试是要在1380个属性中找出1个精确匹 5 Hsieh Ai-Jia, Ho Chin-Wen, Fan Kuo-Chin. An extension of the 配。实验数据表明:贪心算法和 OGSDA-BG算法的查全率都是 bipartite weighted matching problem Pattern Recognition Letters 100%,而贪心算法产生了4个错误肯定,导致其查准率大大降 1995,16(4):347-353.

...展开详情
试读 3P 论文研究-基于本体和二部图的网格服务发现算法研究.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于本体和二部图的网格服务发现算法研究.pdf 5积分/C币 立即下载
1/3
论文研究-基于本体和二部图的网格服务发现算法研究.pdf第1页

试读结束, 可继续阅读

5积分/C币 立即下载