（计算机软件与理论专业论文）基于个性化服务匹配度的服务发现机制研究.pdf

摘要 摘要 服务发现是以w e b 服务作为数据源的信息集成系统中不可或缺的一部分，其 目的是从大量备选服务中，筛选出可以满足特定的用户查询需求的服务。u d d i 是商用服务发现解决方案的实际标准，模式匹配问题是学术研究领域研究的主要 方向。现有的服务发现技术有两个主要缺点：一是大部分服务发现技术基于精确 的关键词匹配，无法处理关键词的不一致性；二是未考虑用户的个性化信息，无 法有效利用用户使用服务发现的历史记录。 本文在研究现有服务发现技术的技术上，提出了基于个性化服务匹配度的服 务发现机制，解决了服务发现中的服务匹配和用户个性化信息的利用问题。本文 提出了基于个性化服务匹配度的服务发现机制的发现流程，分析了模式层面上的 服务匹配问题，提出了基于相似度传播思想的服务模式匹配度的概念及计算方法。 本文还分析了用户个性化信息的概念，提出了利用个性化信息修正服务发现的方 法。 文章最后描述了服务发现方法的实现，利用一个实例对服务发现结果的质量 进行了评估，分析了用户个性化信息对服务发现结果的影响。评估结果表明文中 提出的服务发现机制可以达到较高的服务发现质量，同时较好地体现了不同用户 对服务选择的不同偏爱。 关键词：服务发现模式匹配个性化信息信息集成 a b s t r a c t a b s t r a c t s e r v i c ed i s c o v e r yi sac r u c i a lc o m p o n e n ti ni n f o r m a t i o ni n t e g r a t i o ns y s t e m sw h i c h u s ew e bs e r v i c e sa si t si n f o r m a t i o ns o u r c e s t h ep u r p o s eo fs e r v i c ed i s c o v e r yi st of i n d s e r v i c e st h a tc a nm e e tt h eq u e r yr e q u i r e m e n tb yc e r t a i ni k s e ra m o n gt h el a r g ea m o u n t s e r v i c e sr e g i s t e r e di ns y s t e m u d d ii st h es t a n d a r do fb u s i n e s ss e r v i c ed i s c o v e r y s o l u t i o n s ，a n da c a d e m i cr e s e a r c h e r sf o c u so nt h ea s p e c to fs c h e m am a t c h i n g t h e r ea r e t w ob i gd i s a d v a n t a g e so fc u r r e n ts e r v i c e sd i s c o v e r yt e c h n o l o g i e s f i r s t ，m o s ts e r v i c e s d i s c o v e r yt e c h n o l o g i e sa r eb a s e di nt h ea c c u r a t em a t c ho ft h ek e y w o r d s ，s oi tc a n n o t h a n d l ew i t ht h ed i s a g r e e m e n to ft h ek e y w o r d s s e c o n d ，t h ep e r s o n a l i z e di n f o r m a t i o no f t h eu s c l sa r en o tu s e db ys e r v i c e sd i s c o v e r y , s ot h eh i s t o r yo fh o wt h eu s e r sd i ds e r v i c e s d i s c o v e r yc a n n o tb eu t i l i z e de f f e c t i v e l y s e r v i c ed i s c o v e r y b a s e do np e r s o n a l i z e ds e r v i c em a t c h m a k i n gd e g r e ei sb r o u g h t f o r w a r di nt h i sp a p e ri no r d e rt os o l v et h ep r o b l e m so fm a t c h - m a k i n go fs e r v i c e sa n d u s eo f p e r s o n a l i z e di n f o r m a t i o n t h es e r v i c ed i s c o v e r ym e c h a n i s mb a s e do nt h ec o n c e p t o fp e r s o n a l i z e ds e r v i c em a t c h m a k i n gd e g r e ei ss u m m a r i z e d ，t h es e r v i c e sm a t c h i n g p r o b l e mo ns c h e m al e v e li sa n a l y z e d ，a n dt h ec o n c e p ta n dw a yf o rc a l c u l a t i o no f s c h e m am a t c h m a k i n gd e g r e ei sb r o u g h tf o r w a r d t h e n ，t h ec o n c e p to fp e r s o n a l i z e d i n f o r m a t i o ni si n t r o d u c e d ，a n dr e s e a r c hi sm a d eo nt h eu t i l i z a t i o no fp e r s o n a l i z e d i n f o r m a t i o nt oi m p r o v es e r v i c ed i s c o v e r y a tt h ee n do ft h i sp a p e r , t h ei m p l e m e n t a t i o no ft h es e r v i c ed i s c o v e r ym e c h a n i s mi s d e s c r i b e d a n da ne x a m p l ei ss h o w e dt oe v a l u a t et h eq u a l i t yo ft h er e s u l t t h er e s u l t s h o w st h a tt h es e r v i c ed i s c o v e r ym e c h a n i s mi n t r o d u c e di nt h i sp a p e rc a ng e tar e l a t i v e l y 1 1 i g hs e r v i c ed i s c o v e r yq u a l i t y ；t h ed i f f e r e n tc h o i c e so fs e r v i c e sm a d eb yd i f f e r e n tu s e r s a r ea l s os h o w e di nt h er e s u l t k e y w o r d ： s e r v i c ed i s c o v e r ys c h e m am a t c h i n g p e r s o n a l i z e di n f o r m a t i o n i n f o r m a t i o ni n t e g r a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特l l l i 以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 s a 签- s ：监日期型! ! ：! ! 兰 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名： 导师签名 卿毫 】【i11ji一 复冶竹 日期2 咀 j 肇 日期川7 - ；tm 第一章绪论 第一章绪论 1 1 引言 本节分为两部分，第一部分简要介绍了信息集成技术的三个发展阶段和实现信 息集成系统的两种主要方法。第二部分介绍了服务发现的概念和服务发现领域的 三个主要问题。 1 1 1 信息集成技术概述 在近二十多年的发展过程中，信息集成技术依次经历了三个发展阶段：单个的 联邦系统、基于组件的分布式信息集成系统、基于w e bs e r v i c e s 的信息集成系统。 单个的联邦系统是将所有数据源中的数据统一集成到一个单一的系统中。该方 法比较简单，联邦系统有统一的数据模式，不用考虑分布数据的转化和统一。其 主要缺点是实现代价较高，需要很长的开发时间和高性能的主机设备来构建这样 一个集中式的系统。 基于组件的分布式信息集成系统利用分布式的对象模型，诸如d c o m ( d i s t r i b u t e dc o m p o n e n to b j e c tm o d e l ，分布式组件对象模型) 【1 】、c o r b a ( c o m m o n o b j e c t r e q u e s t b r o k e r a r c h i t e c t u r e ，通用对象代理体系) 1 2 1 或r m i ( r e m o t e m e t h o d i n v o c a t i o n ，远程方法调用) 3 1 ，来构建信息集成系统。这种方法有效地避免了单 个联邦系统带来的开发代价大，代码难以重用的问题。但是，这类技术要求服务 客户端与系统提供的服务本身之间必须进行紧密的耦合，因此这样的系统往往十 分脆弱，不易修改。 以上两个阶段的技术针对的集成对象主要是传统的异构数据库系统，而随着互 联网的飞速发展，网络迅速成为一种重要的信息传播和交换的手段。网络上有着 及极其丰富的数据来源，如何获取网络上的有用数据并加以综合利用，构建针对 网络信息的信息集成系统，成为一个引起广泛关注的研究领域。因为w e bs e r v i c e s 具有完好封装、松散耦合、规范协议高度可集成能力等特性，因，基于w e bs e r v i c e s 的信息集成方案是构建w e b 信息集成系统较为理想的体系结构。 根据孟小峰等人的研究【4 1 ，实现信息集成系统主要有两种方法：数据仓库方法 和包装器中介器方法： 数据仓库和单个的联邦系统在概念上比较类似，其实现机制是：定期把数据从 各个数据源收集到一个“仓库”中，该“仓库”在物理上存储着所有数据源数 据的总合，用户的查询都是针对“仓库”对外提供的统一数据模式，和具体的 数据源无关。 基丁个性化服务匹配度的服务发现机制研究 数据仓库方法的优点是查询速度快，因为查询时并不需要从具体数据源获取数 据；其主要缺陷是如果数据源中包含的数据总量很大，则“仓库”的构建会占 据大量的存储空间，而且如果数据源的数据更新较为频繁，则数据源到“仓库” 的定期更新也会消耗较长的时间。 包装器中介器( w r a p p e r m e d i a t o r ) 方法也被称为“虚拟方法”。该方法并不将 各数据源的数据集中存放，而是通过包装器中介器结构满足信息集成的需求。 典型的基于包装器中介器方法的信息集成系统结构如图1 1 所示： 大台并二：嚣果爿 中介器 i t 用户嘉针对包结果f 套翟磊最 墓渊篡遵心 包装器a包装器b包装器c 的查询结果的奁询结果的奁询 结粜 苣曲壶士睦曲 图1 1 基于包装器中介器方法的信息集成系统结构图 包装器中介器方法的核心是中介模式【5 1 。信息集成系统通过中介模式将各数据 源的数据集成起来，而数据仍存储在各个数据源中，这相当于建立了一个虚拟 的“仓库”，这个被称为“中介器”的虚拟的“仓库”对用户提供一个统一的 视图，针对包装器中介器方法的查询正是基于中介器提供的统一视图。包装 器封装了各个数据源，对数据进行转换使之符合中介模式。包装器就代表了数 据源，用户不必知道每个数据源的具体信息。 基于包装器中介器方法的查询流程由如下三个步骤构成： 步骤一：中介器将基于中介模式的查询转换为针对各包装器的查询，将查询分 解到各个包装器上。 步骤二：各个包装器基于中介器传来的经过分解的查询，查询具体的数据源。 每个包装器对应一个数据源，该包装器了解如何查询该数据源。查询结束后， 各个包装器将其所对应的数据源的查询结果抽取出来，然后将查询结果传给中 第一章绪论 介器。 步骤三：中介器将各个包装器的查询结果合并，然后把合并好的结果返回给用 户。因为各个数据源查询出的结果可能会有错误，所以在合并的时候可能需要 进行处理，常见的处理是数据清洗。数据清洗的目的是修正数据源返回的结果 中包含的错误。 包装器中介器方法避免了数据仓库方法中的数据的更新问题，从而弥补了数 据仓库方法的不足。其优点是不需要和具体数据源定期同步，而且不占用额外 的存储空间；其缺点是每次处理查询时都需要进行查询的转换、从数据源抽取 数据、合并结果，查询速度较慢。 综合考虑两种方法的优缺点，利用包装器中介器方法来实现w e b 信息集成是 现在应用较多的一种方法。在包装器中介器方法中，很重要的一个步骤就是上文 步骤一描述的查询分解过程，而查询分解的一个重要前提是知晓应该把查询分解 到哪些数据源上。信息集成系统中注册了很多数据源，但并不是每个数据源都能 满足用户的查询需求。最常见的情况是：一些数据源可以满足用户一部分的查询 需求，而另一些数据源可以满足用户另一部分的查询需求。这个问题引出了服务 发现的概念，即从系统中注册的大量备选数据源中筛选合适的数据源来回答用户 的查询。 1 1 2 服务发现技术概述 服务发现是信息集成系统中的一个重要组成部分。服务发现的目标是：当用户 发起查询时，系统依据用户的查询请求， 选出能满足特定的用户查询需求的服务。 在系统中已注册的大量备选服务中，筛 服务发现的实质是数据源发现，通过筛 选能满足用户查询需求的数据源，为得到用户满意的查询结果提供前提条件。服 务发现是联系服务消费者和服务提供者的纽带，也是w e b 服务研究领域一个很重 要的课题。 服务发现技术主要涉及三个方面的内容： 备选服务的组织，即服务发现的目标所处的环境。备选服务的组织是服务发现 的预处理。在服务提供者将服务注册到信息集成系统中时，如果能按照一定的 规则将服务注册到与之对应的类别中，那么在查找时不仅能有效地提高服务发 现的速度，还能提高服务发现结果的质量。 服务的提供者和消费者对服务和用户需求的描述，即服务的建模方法。提供者 和消费者对于备选服务的描述发生在服务注册时，是在服务发现过程之前；而 4基丁- 个性化服务匹配度的服务发现机制研究 提供者和消费者对于用户需求的描述则意味着一次服务发现过程的开始。 评价服务和用户查询相似度的方法，即服务匹配算法。服务匹配衡量了一个服 务是否可以满足用户的查询需求。服务匹配的完成标志着一次服务发现过程的 结束。 以上三方面之间是紧密相联、相互影响的，解决一个方面问题所采取的方法往 往直接影响到其他内容的复杂度。其中，服务的描述方式起着重要的作用，备选 服务的组织通常都是按照服务的某个属性进行分类存放。服务的供需双方对服务 描述的差别更是直接影响到服务的匹配算法，差别越大，匹配算法需要处理的问 题就越多，反之亦然。备选服务的组织同样影响着服务的匹配过程，组织的规范 性越强、规律性越明显，意味着服务匹配要解决的问题越简单，最终服务发现的 质量和效率越高。本文重点讨论服务的描述方式和匹配算法，并不讨论备选服务 的组织方面的问题。 1 2 服务发现技术研究现状 本节从商用解决方案和学术研究两个方面对服务发现技术研究现状作以简单 介绍。 目前商用的w e b 服务发现机制可以大致分为以u d d i 1 1 】为代表的集中式发现 机制和以w s i n s p e c t i o n1 1 2 为代表的分布式发现机制两种： u d d i ( 统一描述、发现和集成，u n i v e r s a ld e s c r i p t i o n d i s c o v e r y , a n di n t e g r a t i o n ) 是现有w e b 服务发现机制中标准化程度最高的一个，它由服务注册中心和访 问中心的a p i 组成。服务注册中心是一个全局的、公共的、基于x m l 的在线 注册平台，服务提供者可以通过u d d i 来注册并宣传它们的w 曲服务。a p i 提供了用户查询中心信息的接口，用户可以通过a p i 用编程的方式对u d d i 中注册的服务信息进行查询。 在u d d i 中，服务描述采用基于x m l 格式的w s d l ( w e b 服务描述语言， w e bs e r v i c e sd e s c r i p t i o nl a n g u a g e ) ，服务匹配比较算法往往是通过比较用户查 询需求和服务这两者描述中语法的精确匹配来完成，主要是对服务的名称和有 限的服务描述进行精确匹配。这一方面导致返回了语法相同但事实完全不同的 错误结果，即影响服务发现的查准率：另一方面也导致了漏掉一些本质相近但 采用不同语法的服务，即影响服务发现的查全率。 u d d i 存在的主要问题是其采用的基于关键词匹配的机制存在着缺陷：无法对 所查询的目标进行准确描述、无法度量候选w e b 服务和查询目标的匹配程度、 无法使用语义相关的操作进行查询。 w s i n s p e c t i o n 中服务就发布在服务的交付点上，由一个w s i l ( w e bs e r v i c e s 第一章绪论 i n s p e c t i o nl a n g u a g e ，w e b 服务检查语言) 文档提供相应结点上的服务信息， 并可以在其中包含相关服务的链接。该机制可以发现未在u d d i 中心注册的服 务，也克服了以u d d i 为代表的集中式服务发现所带来的注册中心瘫痪导致服 务发现彻底失效的问题。但是，如果不知道所需要的服务在哪个结点，则需要 借助其他发现机制。 在学术研究方面，模式匹配是解决服务发现问题的最主要的方法之一。模式匹 配的目标是寻找两个或多个模式的元素之间的对应关系，若两个服务的模式之间 的元素具有很高的对应关系，则说明这两个服务的相似程度较高。文献1 13 j 对现有 的模式匹配系统进行了介绍和分类。根据匹配对象的不同，可以分为模式级别和 实例级别的匹配、元素级别的匹配和结构级别的匹配：根据匹配方法的不同，可 以分为基于语言学特征的匹配和基于约束的匹配；根据自动匹配的策略，可以分 为基于规则的匹配和基于学习器的匹配。 根据程伟等人的研究【“，模式匹配问题研究中所采用的技术主要有以下三种： 信息检索技术( i n f o r m a t i o nr e s e a r c h ，i r ) 1 1 4 l 。信息检索技术在进行模式匹配 时通常应用近似匹配、基于距离等匹配技术，消除了基于关键字的匹配的局限 性。这种匹配方法应用的前提是：相似的属性名称代表语义上的相似性。通常， 对于具有清晰规则命名的属性名称应用这种匹配方法可以得到较好的匹配效 果，词典是该方法必备的一个部分。信息检索技术一般为基于模式级别的匹配， 只考虑了模式本身的信息，而没有考虑模式所包含的数据实例的信息，因此在 处理一些命名规范的模式时效果较好。反之，在处理一些命名不规则的模式时， 由于名称产生歧义，因而效果很差。 机器学习技术【1 5 】。应用机器学习方法对已知的匹配和非匹配属性进行学习，然 后利用学习结果指导新的匹配。机器学习技术需要采集大量的训练数据，因此 匹配结果对训练数据的依赖性较高。 图论技术【1 6 1 。图论技术主要用于结构匹配，即将模式中的元素表达为树或者图 的形式，用图论的方法来计算树图中节点的相似度。图论技术的应用场合主 要为结构匹配，存在主要的问题为无法有效区分模式中具有高结构相似性但语 义不同的元素。 在学术研究领域，具有代表性的模式匹配系统主要有以下三个： c u p i d l i t 】是结合了信息检索技术和图论技术。c u p i d 在匹配过程中，采用了同 义词词典作为辅助信息源，来处理模式元素中的同义词、缩写等情况。c u p i d 使用结构匹配算法对模式进行结构匹配。 l s d i ”1 是最有代表性的基于机器学习技术的模式匹配系统，由华盛顿大学研 6 基丁个性化服务匹配度的服务发现机制研究 发。l s d 中使用多种学习器对模式元素通过训练产生各自的匹配度预测值，然 后通过一个元学习器合成学习结构，再经过领域约束检验和用户检验，得到最 终的匹配结果。有多种类型的学习器针对不同类型的元素进行学习，如名称学 习器、内容学习器、x m l 学习器等。 s k a t 【l8 】是一个基于规则的模式匹配系统。用户提供初始的匹配和非匹配关系 定义，形成表达匹配和非匹配关系的规则；然后派生出新的匹配方法，对根据 规则派生出的匹配关系进行识别操作，决定是接受还是拒绝。该系统的缺点是 对用户定义的依赖度很高。 随着信息集成技术的发展，满足用户的个性化需要成为越来越重要的一个要 求，现有的一些服务发现系统都没有考虑用户个性化信息的利用，本文针对w e b 服务发现的应用提出了一种基于w e b 服务模式匹配度的匹配评估方法，再结合用 户个性化信息，较好的完成了服务发现的工作。 1 3 研究内容和目标 本文提出了一种利用用户个性化信息修正服务发现结果的服务发现方法，主 要研究了两个方面的问题：服务匹配度的计算问题以及个性化信息的利用问题。 第一个问题是服务发现领域的主要问题之一，服务匹配度是衡量一个服务是否能 满足用户查询需求的指标。对于用户个性化信息在服务发现中的利用问题，现在 国内外研究还并不多，但是随着用户对个性化的服务发现结果的需求逐步增加， 把用户个性化信息引入服务发现过程也是有很大实际意义的。 本文提出并分析了服务发现的整体流程，并提出了个性化服务匹配度的概念。 服务匹配度是表明了该服务是否能满足用户查询的一个指标，匹配度高则代表该 服务较能满足用户查询的需要，该服务应该被列入服务发现的结果，反之hr j b 艮务 不应被列入服务发现的结果。 为了利用用户个性化信息来增强用户对服务发现结果的满意度，本文提出了 用户个性化信息的建模方法，同时提出了利用用户个性化信息来对服务发现的结 果进行修正的方法。 本文还列举了一个实例，利用具有不同历史记录的用户，基于同样的备选服 务，进行针对不同查询的服务发现，以此来检验服务发现结果的质量。从测试结 果可以看出本文提出的服务发现方法有较好的服务发现质量。 本文研究的目标是为服务发现问题提供一个比较通用的解决方案，该服务发 现机制不应该局限于w e bs e r v i c e s 形式的数据源，它可以适用于各种形式的数据 源的发现。 第一章绪论 7 1 4 论文各章节的安排 本文剩余章节的安排如下： 第二章提出了基于个性化服务匹配度的服务发现的思想，对该方法的处理流 程进行了阐述，介绍了流程中每一步骤的具体任务，并对其优点和局限性进行了 分析。 第三章给出了服务和用户查询的建模方法，目的是将服务和用户查询都转化 为标准化的模式。然后介绍了相似度传播的概念，并详细阐述了相似度的迭代计 算方法，这一部分是本文的两个重点之一。 第四章首先介绍了个性化信息的概念，简要论述了利用个性化信息对服务发 现有何帮助。然后提出了个性化信息的建模方法，并分析了引入个性化信息后新 的服务发现方法。这一部分是本文的另一个重点 第五章论述了基于个性化服务匹配度的服务发现方法的实现原理，包括服务 匹配度算法的实现，和利用个性化信息的方法。然后利用该方法进行了服务发现 的测试，并对测试结果进行了详细分析。从测试结果可以看出本文提出的服务发 现方法可以有效完成服务发现的任务。 第六章对全文进行总结并展望下一步的工作。 基丁个性化服务匹配度的服务发现机制研究 第二章基于个- 性化服务匹配度的服务发现机制 本章提出基于个性化服务匹配度的服务发现机制的思想和流程，对方法的具 体执行流程进行了介绍，分析了流程中各个步骤的功能。基于该服务发现机制的 特点，分析了方法的优点和局限。 2 1 方法流程 通过1 2 节中对服务发现技术研究现状的分析，本文提出了基于个性化服务匹 配度的服务发现机制，用于解决服务发现中存在的无法处理关键词语义模糊以及 无法体现用户差异的问题。该服务发现机制的流程如图2 1 所示： 图2 1 服务发现方法流程图 该服务发现机制通过计算用户查询需求和系统各个备选服务之间的匹配度， 筛选出能满足用户查询需求的服务集合。信息集成系统可以根据服务发现的结果， 调用那些结果中的服务，进而从满足用户查询需求的各个服务中得到用户所需要 的查询数据，最后将各个服务返回的数据合并好后返回给用户。为了提高筛选出 的服务质量，本文提出的服务发现方法还引入了用户个性化信息，通过分析每个 用户历史上使用服务发现的记录，得出不同用户使用服务发现的习惯，对服务发 现的结果进行修正。服务发现流程中的各个步骤如下： 预处理。把用户的查询请求转化为和w e b 服务模式类似的查询模式，以 第一二章基丁个性化服务匹配度的服务发现机制 9 便和已有的w e b 服务模式进行匹配。 预处理对于用户查询模式的要求是，查询模式可以被表示为三个部分：用 户信息、输入部分和输出部分。其中，用户信息包含了识别发起本次查询 的用户身份的信息( 比如用户名) ，其作用是在后续流程中确定本次查询 发起者的个性化信息。输入部分包含了用户为此次查询所提供的输入，即 用户提供的查询条件。输出部分包含了用户想从信息集成系统中获取的数 据项，即要求服务能返回的数据项。输入和输出部分将被转化为用户查询 模式，传递给后续的服务模式匹配度计算步骤。 服务模式匹配度计算。计算用户查询模式和w e b 服务模式的匹配度，该 步骤是服务发现的核心。 利用和预处理步骤类似的方式，将w e b 服务的描述转化为和用户查询模 式相类似的w e b 服务模式。这一步骤对w e b 服务的要求是，w e b 服务可 以被表示为两部分：输入部分和输出部分。输入部分包含该w e b 服务可 以接受的输入，即服务可以接受的参数。输出部分包含该w e b 服务可以 提供的输出数据项。w e b 服务模式的输入和输出部分分别和用户查询模式 的输入和输出部分对应。 该步骤主要是通过图变换的形式进行，将用户查询模式和w e b 服务模式 都转化为格式相同的图。基于用户查询模式和w e b 服务模式的图，利用 采用图论技术的模式匹配算法计算用户查询模式和w e b 服务模式中的元 素的匹配情况，依此来评估其匹配度的高低。 如果用户查询模式中的元素在w e b 服务模式中都找到了匹配对象，则该 w e b 服务的模式匹配度较高，反之，若用户查询模式中的元素并未在w e b 服务模式中找到匹配对象，则该w e b 服务的模式匹配度较低。 用户个性化信息计算。计算每个w 曲服务对发起查询的用户的个性化值。 不同的用户对系统中的各个备选w e b 服务都有一个个性化值，该值代表 了该用户对该服务的偏爱程度。个性化值越高，则代表用户以往更偏好于 选择该服务。也意味着用户此次服务发现也有较高的几率选择该服务。系 统还记录了每个服务历史上被所有用户调用的次数，代表全体用户对每个 服务的偏好。 匹配度合并。结合服务模式匹配度计算和用户个性化信息计算的结果，计 算出系统中已注册的各个w e b 服务的最终匹配度，我们称之为“个性化 服务匹配度”。个性化服务匹配度由服务模式匹配度和用户个性化信息共 同决定，衡量了该服务是否可以满足特定用户发起的特定查询需求。个性 化服务匹配度越高，则说明服务越能满足用户的查询需求，该服务被列入 服务发现的结果中的几率也越大。 0基于个性化服务匹配度的服务发现机制研究 结果过滤和返回。基于以上得出的各个服务的个性化服务匹配度的结果， 用相应的过滤器过滤出满足用户查询需求的w e b 服务集合，然后把服务 发现结果返回给信息集成系统。 在进行过滤之前，我们先对各个服务的个性化服务匹配度排序。可以采用 以下三种方法进行过滤：额定数目( 只选择个性化服务匹配度最高的若干 个服务) 、额定百分比( 只选择个性化服务匹配度最高的若干百分比的服 务) 、阈值( 只选择个性化服务匹配度高于某个值的服务) 。这三种方法可 以单独使用，也可以同时使用，以便对服务发现的结果进行更加严格的过 滤。以上提出的三种过滤器原理都比较简单，在某些情况下，为了提高服 务发现的有效性，我们也可以采用更为复杂的过滤器。例如，只选择位于 某个国家的w e b 服务的服务地理位置过滤器、只选择拥有较好服务质量 的服务质量( q u a l i t y o f s e r v i c e ，q o s ) 过滤器、只选择某些机构提供商的 服务提供商过滤器等，还可以根据安全性的要求选择具有足够安全性的 w e b 服务，而舍弃那些不够安全的服务。 需要注意的是，以上的服务模式匹配度计算和用户个性化信息的计算是要对 系统中的所有服务都进行的，在最后计算出所有服务的个性化服务匹配度后，再 根据匹配度的高低进行过滤筛选，确定最后的服务发现结果。 在上述流程中，最重要的两个步骤就是模式匹配度计算和用户个性化信息计 算，这两个问题也正是本文接下来要研究的两个重点问题。第三章会重点讨论模 式匹配度的计算方式，第四章会对用户个性化信息的利用进行研究。 析。 2 2 特点分析 本节从优点和局限两方面对基于个性化服务匹配度的服务发现机制进行分 本文提出的服务发现机制的主要优点有以下三个： 可以适应用户查询和数据源( w 曲服务) 之间的非精确匹配。因为该方法 并非采用基于关键字的匹配方法，故可以匹配名称不同但语义相同的元 素。例如，用户查询的“书名”可以和w e b 服务模式中的“图书名称” 进行匹配。 这个优点很好的克服了以往的基于关键字精确匹配的服务发现方法( 例如 u d d i ) 的缺点，因为服务的提供者不一定能保证所提供服务的关键字完 全和用户提供的关键字保持一致。 充分利用了用户的个性化信息，让服务发现的结果尽可能的适应不同的用 第二章基于个性化服务匹配度的服务发现机制 1 1 户的不同需求。通过记录用户以往进行服务发现的结果，对用户当前的服 务发现结果进行修正，使以往用户选择次数较多的服务有更大的可能被发 现出来。 可以适应不同类型的数据源。因为本文并不讨论服务发现后进行服务调用 的问题，如何调用具体的服务对本文提出的服务发现方法不会产生影响， 因此服务发现方法所发现的服务并不仅仅局限于w e b 服务数据源，只要 能抽象为本文提出的服务发现方法中规定的特定形式的模式，就都可以被 用来进行服务发现。 本文提出的服务发现机制的主要局限有如下两个。 对于使用习惯突然改变的用户，服务发现的效果会在短期内降低。因为本 方法中利用的用户个性化信息是基于用户以往的使用记录的，它假设用户 对某些服务的偏好是会长期保持的，而不会突然发生改变。如果用户对服 务的偏好突然发生改变，则服务发现的结果需要一定的时间来适应用户偏 好的改变。在最初，服务发现的结果将无法体现出用户新的使用习惯，但 随着时间的增加，发现结果会越来越符合用户新的使用习惯。 例如，一个用户以往总是喜欢查询特定电影片名的参演演员，这就使得系 统认为该用户对于那些接受电影片名作为输入而且能提供演员名作为输 出的服务较为偏爱。但如果该用户突然改变了使用习惯，开始大量地查询 特定电影片名的电影的出版日期，则在短期内系统还会认为那些可以提供 演员和出版日期的服务比那些只能提供出版日期的服务更被该用户所偏 爱。但过了一段时间以后，随着系统收集到的用户新的使用习惯的更多信 息，系统就不再会这样认为，因为用户已经不再喜欢查询参演演员。 数据源必须能够抽象为一定的模式，这一点在上述的“预处理”步骤中也 有所描述。 因为数据源的模式要与用户查询模式进行匹配，因此数据源必须能抽象为 和用户查询一致的模式。具体来说，数据源应该能被较好的抽象为输入和 输出两部分，分别代表服务能接受的输入参数和服务能返回的各个数据 项。这一点要求数据源必须可以对外提供较为规范的接口，易于以可编程 的形式被调用。 2 3 本章小结 本章介绍了基于个性化服务匹配度的服务发现方法的流程以及该流程中的每 个执行步骤。通过研究该方法的机制，说明了其优点和局限性。本文第三至五章 1 2 基丁个性化服务匹配度的服务发现机制研究 论述的服务匹配度和个性化信息的计算方法和实验证是基于该方法的流程展丌进 行研究的。 下一章我们将详细论述基于个性化服务匹配度的服务发现方法中的服务匹配 度计算方法，这是本文研究的两个重点内容之一。 第二章服务模式匹配度的计摊 第三章骚务模式匹配度的计算 本章详细论述了服务模式匹配度的计算方法，沦述了对w e b 服务和用户焱询 鹣建模方法，介绍了相似发传播的概念，并详细论述了相似度的迭代计算方法。 3 1 服务以及用户查询的建模 模式匹配的前提条体是待匹配的嬲个模式具有糟嗣的性质，因此在进行模式 逛配之藩，罄先要令爱声焱诲_ 程w e b 缀务具舂辐阕酌模式，本苗分绍对w e b 溅务 和用户查询的建模方法。 在本文提出的方法中，w e b 服务被抽象为两个部分：输入和输出。 输入帮分代表了该w e b 殿务耱嚣翡羧入蕊息，主要是对羚入戆参数豹要 求，包括参数名称、参数类型等信息。 输出部分代表了该w e b 服务能对外提供的输出信息，钒括输出数据的名 称、类型等信息。 相应的，用户查询被抽象为三个部分：用户信息、输入和输出。 用户信息部分代表了发起查询的用户的识别信息，采用凝省唯一性的用户 国豹形式，剥髑该售惠霉数谈爨发超查谗瓣蠲户，遘露麓蘧该羡息焱稳 该用户的个性化倍怠，对服务发现过程进行修正。 输入部分对应上文提到的w e b 服务的输入部分，它代袋了用户此次雀询 豹输入，即用户鼗传递绘服务发现过程的镶怠。输入部分怠含了用户输入 的参数类型、参数翡其俸蘧等信息。 输出部分对应上文提到的w e b 服务的输出部分，它代袭了用户期望得到 的数据，即用户期望从各数据源中得出的凌询结果。输出部分包含了用户 麓麓懿数据顼豹袭穆彝数撵类餐。 图3 1 描述了w e b 服务和用户查询的模型的对应关系。 豳3 1w e b 服务和用户查询模型 下面是一个图书领域的用户查询横式的例子，用x m l 格式描述。该模式的内 1 4基丁个性化服务匹配度的服务发现机制研究 容是“用户名为张三的用户想查询i s b n 为7 一1 1 5 0 9 2 0 6 的图书的书名和出版社的 信息”。 上述用户查询模式由如下三部分组成： 用户信息，即 和 之间的部分。该部分表明了发起 此次查询的用户的用户名是张三，“用户名”这个数据项的数据类型是字 符串( s t r i n g ) 类型。 输入，即 和 之间的部分。该部分表明了用户想要查询i s b n 为7 1 1 5 0 9 2 0 6 的图书的相关信息，i s b n 也为字符串类型。即用户给服务 提供的输入为字符串类型的i s b n 。 输出，即 和输出 之间的部分。该部分表明了用户想要了解图书 的书名和出版社信息，这两方面的内容也为字符串类型。即用户想从服务 中得到的输出为字符串类型的书名和出版社。 下面是一个恰好完全满足上述用户查询需求的w e b 服务的模式。该模式表明 此w e b 服务能接受的输入参数是一个字符串类型的i s b n 号，可以提供的输出数 据项是字符串类型的书名和出版社。 第二章服务模式匹配度的计算 3 2 相似度传播 相似度传播的思想由m e l n i ks 等人于文献【1 6 1 提出，该思想描述了图中相邻节 点之间的相似度的互相影响。本节先阐述了如何用图的形式来表示用户查询模式 和w e b 服务模式，接下来介绍了相似度传播的概念。 3 2 1 模式的图表示 本文所提出的服务发现方法中的模式匹配度的计算是基于图论的方法，因此 要将3 1 节论述的w e b 服务和用户查询的模式转化为图的形式，进而基于图来进 行匹配度的计算。 对于3 1 节列举的服务模式的例子，我们把它的输出部分转化为如下格式的图 3 2 ： 图3 2 服务模式的图表示 图3 2 中的椭圆形和矩形节点之间没有含义上的区别，只是为了方便区分节点 类型。其中椭圆形节点代表一个具有唯一性的节点标示符，矩形节点代表文字描 述。用户查询模式和服务模式会被分别转化为两张图，一张是输入部分，一张是 输出部分。用户查询模式中的用户个性化信息不分不需要转化为图。我们可以观 察出上图有如下特征： 图为有向图，节点之间的有向边上有各自的边名，表明了相邻节点之问的 关系。 能体现模式中对于输入输出参数约束的节点，大多是矩形节点。 同类型节点拥有相同的“类型”相邻节点，例如& 3 和& 6 都有“类型”边 指向& 4 节点。 3 2 2 相似度传播 相似度传播概念是指： 1 6基丁- 个性化服务匹配度的服务发现机制研究 相似度会沿着相似度传播图中的边从一个节点传播到所有的相邻节点。 相似度传播图的概念稍后介绍。相似度传播基于以下假设： 假设一：不会出现两个模型中同一元素名字所代表的元素具有不同含义， 即语义上不存在歧义。例如，3 1 节的用户查询模式和w e b 服务模式中的 节点“出版社”应该都代表同样的含义。 假设二：如果两个模型中的某两个节点相似度高，则其相邻节点相似度也 高。 在w e b 服务模式和用户查询模式转化为的图中，最重要的节点是输入和输出 部分的数据项名称和数据类型。例如，3 1 节列举的用户查询对所筛选出的服务的 最基本的要求，就是该服务要能够接受字符串类型的i s b n 作为输入参数，而且应 该能够输出字符串格式的书名或者出版社，最好能同时输出字符串格式的书名以 及出版社。 3 3 相似度的迭代计算方法 本节详细论述了基于图论方法的相似度的迭代计算方法，首先介绍了计算相 似度之前的准备工作：图变换。其目的是把用户查询模式和w e b 服务模式都转化 为图的形式。其次介绍了相似度迭代计算的算法，对算法中的各个步骤进行了详 细的分析。 3 3 1 图变换 在进行相似度计算之前，需要对3 1 节提出的描述w e b 服务模式和用户查询 模式的图做适当的变换。 变换分为两个步骤： 将用户查询模式和w e b 服务模式转化为节点对连接图。下面给出节点对 连接图的定义： t x 。协p 仪，) 、节点对连接图t a b = = ( x p t ) e a a l ( y p 矿) b 其中a ，b 为两个模式，三元组( x ，p ，x ) 意味着存在一条名为p 的边，其 起点为x ，终点为x 。节点对连接图中的每个节点，都是由一个模式a 中 的节点和一个模式b 中的节点组成。具体的转化方法是将两个模式中相同 名字的边相连的节点合并起来，即分别从两个模式中各取一个节点，组成 一个节点对。 第三章服务模式匹配度的计算 图3 3 两个模型的图表示 假设存在图3 3 中描述的的模型a 和b ，根据节点对连接图的定义可 知，a 和b 转化完成的节点对连接图3 4 如下： l l 1l 2 面造芦 t l 2 图3 4 节点对连接图 将节点对连接图转化为相似度传播图。 首先，在节点对连接图中，对每一条边添加一条反向的边，边名不变。对 于上图，即添加从( a l ，b 1 ) 到( a ，b ) 的l 1 边、从( a 2 ，b 1 ) 到( a ，b ) 的l 1 边、 从( a 2 ，b 1 ) ：至l j ( a l ，b 2 ) 的l 2 边、从( a 2 ，b 2 ) 至t j ( a l ，b ) 的l 2 边。添加反向边 后的图3 5 如下。 图3 5 添加反向边后的节点对连接图 基丁个性化服务匹配度的服务发现机制研究 其次，为每一条边计算权值。计算方法是观察每一个节点对的出边，若它包含 n 条同名的出边，则这些边的权值均为1 n 。例如，在上图中，节点对( a ，b l 有两条l l 出边，分别指( o ( a l ，b d 和( a 2 ，b 1 ) ，因此这两条边的权值均为1 2 = 0 5 。 添加了权值的图即为相似度传播图，每条边的权值被称为“传播系数”。由上 述传播系数的计算方法可知，每个节点对对于其每个不同名的出边得出的传播 系数总和为l ，例如，节点对( a ，b ) 和( a l ，b 1 ) 以及( a ，b ) 和( a 2 ，b 1 ) 之间的相 似度总和为1 。 图3 4 转化为的相似度传播图3 6 如下： 3 3 2 相