（计算机软件与理论专业论文）web服务语义相似性度量方法研究.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ho ns e m a n t i cs i m i l a r i t ym e a s u r i n g m e t h o df o r 胎bse r v i c e s c a n d i d a t e ：l o n gy u s u p e r v i s o r ：a s s o c i a t ep r o f x i ex i a o q i n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro f e n g i n e e r i n g s p e c i a l i t y ：c o m p u t e rs o f t w a r ea n dt h e o r y d a t eo fs u b m i s s i o n ：d e c e m b e r , 2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y l r 1 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：扮耳 一v 日期：加，d 年3 月，f 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数 据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编 本学位论文，可以公布论文的全部内容。同时本人保证毕业后结 合学位论文研究课题再撰写的论文一律注明作者第一署名单位 为哈尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文彻在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：龙荨 日期：加d 年3 月，f 日 导师( 签字) ：确押秀亳 锄l o 年弓月i 箩日 哈尔滨t 程大学硕十学位论文 摘要 面向服务计算已经成为一种新的计算范型，尤其是服务组装成为一种重 要的软件开发方式。语义网络是未来网络的一个核心技术，它可以表达更加 复杂的概念及其之间的相互关系。w e b 也从信息共享平台转化为服务集 成的平台。现在，w e b 服务大量分散地存储在互联网上，服务组装通过 组合网络上各种w e b 服务所提供的各种各样的功能得到所需的服务。服 务搜索就是为了在网络中发现所需要的可用的好的w e b 服务，以便进行进一 步的服务组装。而w e b 服务的相似性度量方法是服务搜索的一个重要的关键 技术。 本文首先对现有的w e b 服务语义相似性的不同的计算方法进行了分析， 给出了它们的优缺点。然后基于距离模型和信息量模型，提出了一个w e b 服 务语义分类描述模型( s c d m 4 w s ) ，扩展了w e b 服务描述中的语义信息， 为w e b 服务的语义相似性度量提供了语义基础。并给了语义区分精度的定义。 其次，在s c d m 4 w s 模型基础之上提出了一种增强语义区分精度的w e b 服务语义相似性度量方法s s m m w s 。该方法综合地考虑了距离、深度和密 度等影响语义相似性的因素：克服了距离模型中不能区分具有不同密度的兄 弟节点的问题，克服了信息量模型中不能区分具有不同深度的节点的问题， 克服了融合两种模型的方法中对文本集统计时花费大量时间和存储空问的问 题。 另外，又将t a g 技术引入到服务语义相似性的计算中，提出了一种基于 t a g 的度量w 曲服务之间相似性的计算方法s s m m w s t 。该方法利用t a g 标 注来计算w e b 服务之间的语义相似度，进一步提高了w e b 服务语义相似性 的计算精度。 最后，设计和实现实验，验证了上述提出方法的正确性和可行性。采用 德国人工智能研究中心提供的数据集进行实验，将本文所提出的方法与r o y 方法、r e s n i k 方法、c o s i n e ( c o s ) 方法、 e x t e n d e dj a c c a r d ( e j ) 方法以及实验 数据集所提供的标准答案进行了实验对比分析和讨论。实验结果验证了本文 所提出的方法的可行性和效率。 关健词：w e b 服务；语义相似性；度量方法；服务搜索 哈尔滨下程大学硕十学位论文 a b s t r a c t s e r v i c eo r i e n t e dc o m p u t i n gh a sb e e nan e wc o m p u t i n gp a r a d i g m ，s e r v i c e c o m p o s i t i o nb e c o m e s a ni m p o r t a n ts o f t w a r ed e v e l o p m e n tm e t h o d s e m a n t i cw b b i so n eo ft h ec o r et e c h n o l o g i e si nf u t u r en e t w o r k s ，i tp r e s e n t sm o r ec o m p l e x c o n c e p ba n dr e l a t i o n s w e bh a sb e e nt r a n s l a t e df r o map l a t f o r mo fi n f o r m a t i o n s h a r i n gt o s e r v i c e i n t e g r a t i o np l a t f o r m n o w , 既6s e r v i c e s a r e a r c h i v i n g d i s p e r s e d l ya r o u n dt h ei n t e r n e t n l ev a r i o u sc o m p l e xs e r v i c er e q u i s i t ec a nb em e t b ys e r v i c ec o m p o s i t i o n ，t h a ti st os a y , b yc o m b i n i n ga l lk i n d so fs i m p l ew e b s e r v i c e sf r o mw e b s e r v i c ed i s c o v e r yi st of i n dau s a b l er e q u i s i t ew e bs e r v i c e f r o mw e bf o rs e r v i c ec o m p o s i t i o n s o n ei m p o r t a n ta n dc r i t i c a lt e c h n o l o g yi n s e r v i c ed i s c o v e r yi st h es i m i l a r i t ym e a s u r e m e n tm e t h o df o rw e bs e r v i c e t l l i st h e s i sa n a l y z e st h ed i f f e r e n tc o m p u t a t i o n a lm e t h o d so fe x i s t i n gw | e b s e r v i c es e m a n t i cs i m i l a r i t ya n dt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e m b a s e d o nt h ed i s t a n c em o d e la n di n f o r m a t i o nc o n t e n tm o d e l t h i st h e s i sp u t sf o r w a r da s e m a n t i cc a t e g o r yd e s c r i p t i o nm o d e lf o rw e bs e r v i c e ( s c d m 4 w s ) a n de x t e n d s t h es e m a n t i ci n f o r m a t i o ni nt h ew e bs e r v i c e sd e s c r i p t i o n w h i c hb u i l ds e m a n t i c f o u n d m i o nf o rs i m i l a r i 哆m e a s u r e m e n to fw e bs e r v i c e f u r t h e r m o r e ，i tg i v e sa d e f i n i t i o no ft h ec o n c e p to ft h es e m a n t i cd i s t i n g u i s ha c c u r a c y s e c o n d l y , b a s e d o ns c d m 4 w sm o d e l ，t h i st h e s i s b r i n g sf o r w a r da m e a s u r e m e n tm e t h o ds s m m w so fw e bs e m a n t i c ss i m i l a r i t yw h i c hc a na r g u m e n t t h es e m a n t i cd i s t i n g u i s ha c c u r a c y t l l i sm e t h o dc o n s i d e r ss y n t h e t i c a l l yv a r i o u s f a c t o r si n c l u d i n gd i s t a n c e ，d e p t ha n dd e n s i t yw h i c ha f f e c ts e m a n t i cs i m i l 撕饥 t l l i sm e t h o dc a nd i s t i n g u i s hd i f f e r e n td e n s i t yo fb r o t h e rn o d e sw e l li nt h ed i s t a n c e m o d e l ；i tc a l ld i s t i n g u i s hd i f f e r e n td e p t ho fn o d e sw e l li nt h ei n f o r m a t i o n m o d e l ；a n di ta v o i d st h et i m e - c o n s u m i n ga n ds p a c e c o n s u m i n gp r o b l e m sr e s u l t i n g f r o mt h et e x td a t as e ts t a t i s t i cp r o c e s s e s t h i r d l y , t h i st h e s i sa d o p t st h et a gt e c h n o l o g yi ns e r v i c es e m a n t i cs i m i l a r i t y c a l c u l a t i o n ，a n dp u t s f o r w a r das e m a n t i c s i m i l a r i t ym e a s u r i n g m e t h o d s s m m w s tb a s e do nt a g sf o rw e bs e r v i c e s t h em e t h o du s e st h et a gs e m a n t i c i n f o r m a t i o nt oc o m p u t es e m a n t i cs i m i l a r i t yo fw e bs e r v i c e s t h u st h i s f u r t h e r i m p r o v e st h ec a l c u l a t i o na c c u r a c yo f 娓bs e r v i c es e m a n t i cs i m i l a r i t y f i n a l l y , st h e s i sd e s i g n sa n da c h i e v e st h ee x p e r i m e n t s a n dv e r i f i e st h e f e a s i b i l i t ya n da c c u r a c yo ft h ea b o v em e t h o d w 色a d o p t e dt h ed a t as e t sw h i c hi s p r o v i d e db yg e r m a nr e s e a r c hc e n t e rf o ra r t i f i c i a li n t e l l i g e n c et oe x p e r i m e n t w ec o m p a r et h er o ym e t h o d ，r e s n i k m e t h o d ，c o s i n e ( c o s ) m e t h o d ，e x t e n d e d 哈尔滨t 程大学硕+ 学位论文 j a c c a r d ( e j ) m e t h o dw i t ht h em e t h o dp r e s e n t e di nt h i st h e s i sa n da n a l y z ea n d d i s c u s st h ee x p e r i m e n t a lr e s u l t s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o do ft h e t h e s i si sf e a s i b l ea n de 瓶c i e n t k e yw o r d s ：w e bs e r v i c e ；s e m a n t i cs i m i l a r i t y ；m e a s u r i n gm e t h o d ；s e r v i c es e a r c h r l p ， 哈尔滨下程大学硕+ 学位论文 目录 第1 章绪论1 1 1 引言l 1 2 研究背景及意义1 1 3 语义相似性度量方法3 1 3 1 基于距离的方法3 1 3 2 基于信息量的方法。5 1 3 3 融合距离模型和信息量模型的方法6 1 3 4 基于图论的方法6 1 3 5 基于社会标签的方法7 1 3 6 目前算法的比较及存在的问题7 1 4 论文的主要工作9 1 4 1 研究内容9 1 4 2 本文的贡献9 1 5 论文的组织结构1 0 第2 章w e b 服务语义分类描述模型1 1 2 1 引言1 1 2 2 研究背景1 2 2 2 1 语义和语义学相关概念1 2 2 2 2w o r d n e t 知识库1 4 2 2 3 语义层次结构1 6 2 2 4t a g 技术现状1 7 2 3w e b 服务的语义分类描述模型1 9 2 - 3 1 领域本体d c 1 9 2 3 2w e b 服务的语义分类描述模型( s c d m 4 w s ) 2 2 2 3 3w e b 服务语义区分精度。2 4 2 4 和其他模型的比较一2 5 2 5 本章小节2 6 第3 章增强区分精度的w e b 服务语义相似性度量方法2 7 3 1 引言2 7 哈尔滨下程大学硕十学位论文 3 2 增强语义区分精度的w e b 服务语义相似性度量方法( s s m m w s ) 2 8 3 2 1 相关概念。2 8 3 2 2 计算公式3 1 3 2 3 度量方法的理论证明。3 7 3 2 4 方法特点3 8 3 3 基于t a g 技术的w e b 服务语义相似性度量方法( s s m m w s t ) 3 9 3 3 1 基本思想一4 0 3 3 2 计算方法4 2 3 3 3 和其它方法的比较4 7 3 4 融合s s m m w s 和s s m m w s t 的方法( s s m e r g e ) 4 8 3 5 本章小节4 9 第4 章实验与分析5 0 4 1 实验环境5 0 4 2 数据来源和数据集5 0 4 3 实验设计5 5 4 4 结果集5 5 4 5 评估方法与实验结果分析7 2 4 5 1m a p ( m e a na v e r a g ep r e c i s i o n ) 7 2 4 5 2i mm a p 曲线一7 2 4 5 3 实验结果分析7 2 4 6 本章小节7 9 结论8 0 参考文献8 2 攻读硕士学位期间发表的论文和取得的科研成果8 9 致 射9 0 - r 、 哈尔滨t 程大学硕十学位论文 1 1 引言 第1 章绪论 语义w e b 技术的出现为w e b 服务的描述提供了增加语义层次内容的良 好方法，也推动了w r e b 服务的自动化和智能化搜索。目前，基于语义的w e b 服务匹配和发现也逐步成为w e b 服务的主要研究领域之一，而w e b 服务的 语义相似性的度量方法研究又是w e b 服务匹配和发现的关键技术之一。 相似性度量在相似性科学的研究中占据着十分重要的地位。相似性的研 究主要包括结构相似性研究和语义相似性研究。在以往的有关相似性的研究 中，人们更加关注对结构相似性的研究。但是目前，人们也开始更加关注对 语义相似性的研究了。语义相似性的研究在哲学、心理学、语言学和人工智 能等研究领域中，开始的较早，而最初研究的目的是消除词义的歧义、信息 检索、自动索引和词汇的抽取【i 】。目前，相似性的研究也逐渐被引入计算机 科学之中，尤其是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 服务之间的相似性。 1 2 研究背景及意义 近年来，网络走进人们的日益生活，为人们的生活、学习和工作带来了 巨大地变化。互联网提供了非常多的功能丰富种类繁多的w e b 服务以满足不 同人群的需要。例如，一个人要出去旅游，那么他的需求可能有：将要旅行 的这一段时间当地的天气情况是怎么样的；目前都有什么旅行社提供他所要 想要得到的旅行业务；采用什么样的交通工具；如何订购车票或机票；旅行 一 - 1 l i 哈尔滨t 程大学硕士学位论文 目的地的宾馆预定；当地采用何种货币，汇率是多少等等。这些需求概括起 来可以表达为需要以下的服务：天气预报服务，旅行社服务，有关银行的服 务，有关交通的服务和有关宾馆的服务等等。可见，一个看似简单的旅行需 求就可能需要众多不同的服务。满足上述需求的服务可能大量地存在于互联 网上，并且是时时更新的，例如有的服务可能上一秒还能使用，但下一秒就 不能使用了。想要靠人手工地加以识别这些服务并组装起来返回给用户几乎 是难以实现的，其中可能还需要随时将不可用的服务替换为可用的服务。这 就迫切需要一种由计算机自动识别和实现的方法来满足用户的服务需求。而 且，不仅要满足用户的需求，还要尽可能的快速，因为漫长的等待时间也是 让人难以接受的。 基于语义的w 曲服务的搜索和自动组装技术为实现上述的需求提供了 一种解决方案。而w e b 服务的语义相似性的度量又是实现基于语义的w e b 服务的搜索和自动组装的一个关键技术。目前现有的度量方法大多是以所提 供的需求的词的拼写为依据的，这样就无法区分该词的具体的语义，从而使 得在处理具有多个意思的词的时候可能会出现不准确的现象。例如， a p p l e 这个词它到底表示一种水果还是一种计算机的品牌昵? 在一个w e b 服务的组 装过程中，一个关于显示a p p l e 计算机价格的w 曲服务不可用了，那么就应 该再找一个也是有关显示a p p l e 计算机价格的w e b 服务来代替那个已经不可 用的w e b 服务。但若不考虑w e b 服务描述中所包含的语义信息就有可能错 误地将一个有关a p p l e 水果价格的w e b 服务去替换原来的有关a p p l e 计算机 价格的w e b 服务。在计算w e b 服务之间的相似性的过程中，若考虑了a p p i e 的各种语义信息，在w e b 服务搜索和组装时就可以有效的避免上述问题。 德国柏林洪堡大学的a x e lm a r t e n s 将p e t f i n e t 引入到w e b 服务的研究之 中，用工作流模块来描述w e b 服务，应用于w e b 服务组合方面的研究【2 1 。土 耳其博阿齐奇大学的m u r a ts e n s o y 等人用上下文本体来描述w e b 服务，将 w e b 服务分为服务需求和服务评级两个属性，然后再对这两个属性进行细分， 应用于服务的选择【3 j 。美国乔治亚大学的o u n d h a k a rs 将w e b 服务映射为一 个模板，计算模板之间的相似性作为w e b 服务之间的相似性，应用于w e b 服务的搜索1 4 j 。复旦大学的张亮等人将c c s 引入到w e b 服务的研究之中，认 为w e b 服务就是就是进程，因而用进程来描述w e b 服务，应用于w e b 之间 2 哈尔滨1 ：稃大学硕士学位论文 消息传递的研究p j 。株洲工学院计算机系的李建设等人，将w e b 服务定义为 一个二元组 s l ，o p ，其中s l 为服务层，o p 为操作层，应用于w e b 服务的 相似性的研究之中【6 j 。在上述的研究中，分别将这些描述w e b 服务的模型应 用于不同的有关w e b 服务的研究之中，但在计算和匹配的过程中，只是简单 地匹配，并没有将相关的语义信息参与到计算中。 综上，现有的w e b 服务描述模型只是较少的体现了w e b 服务的语义， 并且在w e b 服务的搜索和组装过程中，对w e b 服务之间的相似性的度量方 法上在考虑语义方面显得不足。本论文的主要目的就是要研究一种针对语义 w e b 服务搜索和组装的语义相似性度量方法，为服务的搜索和组装提供语义 上的支持，从而为满足用户提出的复杂性需求得到满足提供保证，为最终实 现自动地、高效地、智能化地服务组装提供技术上的支持。 1 3 语义相似性度量方法 目前，相似性研究中提出的度量语义关联性、语义相似性和语义距离的 算法和方法有很多，大体上可以分为以下五种类型：基于距离的方法、基于 信息量的方法、融合距离和信息量两种模型的方法、基于图论的方法和基于 社会标签的方法。 1 3 1 基于距离的方法 基于网络距离的语义相似性计算方法就是根据领域本体概念在层次结构 树中的位置来计算概念之间的语义相似性。概念之间的最短路径越短，语义 相似性越强 7 1 。 利物浦大学的r o yr a d a 等人第一次提出用距离来度量两个概念之间的 语义相似性，并给出了具体的度量方法：在一个i s a 的语义概念层次结构中， 若概念a 和b 分别由节点a 和b 来表示，则概念a 和b 之间的语义距离为 链接a 与b 之间的边的最少个数【8 j 。也就是说概念之间的语义距离越短，则 概念之间的相似性越强。虽然这种边计数的方法很直观，但是，在概念层次 结构树中，处于较深层次的节点之间的相似性要比处于较浅层次节点之间的 3 哈尔滨t 程大学硕十学何论文 相似性更强。r o y 方法并未体现出概念层次结构中的这种性质。另外，这种 方法默认概念树中所有的链接节点的边的权重都是一样的，这显然与实际不 相符合。 都柏林城市大学的r i c h a r d s o n 等人改进了r o y 方法 9 1 。提出增加边的权 重的方法。他们指出如果链接节点的边处于较深的层次，则边的权重应该减 少。但没有考虑节点密度对相似性的影响。 美国宾西法尼亚大学的m a r t h ap a l m e r 等人也对r o yr a d a 等人的方法做 了改进【l o j 。先将某一领域内的词建立一个概念集合，组织成一个层次结构， 进而，计算在某一个领域的概念之间的相似性。度量相似性时，使用了两个 概念之间的最低的共同祖先概念的深度。根据他们给出的相似性计算公式可 以看到，随着两个概念之间的最低的共同祖先概念的深度的增加，两个概念 之间的距离减少。这在一定程度上也避免了r o yr a d a 等人的方法存在的问 题。但也没有考虑节点密度对相似性的影响。 加拿大多伦多大学的g r a e m eh i r s t 和d a v i ds t o n g e 提出了语义关联性 的度量方法，并给出相应计算两个概念节点之间的权重计算公式f l l 】。他们认 为如果两个概念由一条路径链接，链接的路径小于不变常数，并且链接的方 向不会经常改变，就认为这两个概念是相关的。这种方法是利用同一路径中 边的链接方向可能不相同这一性质来计算的。这种链接方向可以是水平、向 下和向上。他们虽然认识到了链接节点之间的边的重要性并不是完全相同的， 也采取了措施进行了改进，但是并没有体现出在层次结构树中处于较深层次 的节点之间的相似性要强于较高层次节点之间的相似性这一性质。 曼彻斯特城市大学的y u h u al i 等人也提出了一个度量语义相似性的方法 1 2 1 。他们考虑了概念密度因素对语义相似性的影响，将影响语义相似性的因 素：路径长度，深度，密度等看作是独立的函数，并将这些因素看作是相似 性函数的自变量。但在计算概念密度的过程中，采用的是统计文本集( b r o w n 文本集i l 驯) 的方法。这样就必然会因为存储这个文本集而占用了大量的空间 ( 5 0 0 个文本簟每一个文本不少于2 0 0 0 个词木假设平均一个词含有6 个字母， 结果不少于5 7 2 g ) ，统计这么大的一个文本集中每一个词的频率，用时之大 可想而知。 上述的基于网络距离模型的语义相似性的计算方法各有侧重，但都没有 4 哈尔滨t 程大学硕十学位论文 同时考虑距离、层次和密度对语义相似性度量的影响，即使y u h u al i 等人也 考虑了这三个因素对语义相似性的影响，但是分开考虑的，并没有将这三个 因素统一来考虑，这一点是必要的，因为这三个因素是互相影响的。因而设 计一个综合考虑距离、深度和密度的w e b 服务语义相似性的计算方法是本课 题研究内容之一。 1 3 2 基于信息量的方法 基于信息量的方法就是根据概念所含有的信息量来计算概念之间的语义 相似性r 丌。概念越抽象，越具有一般性，其信息量越少。概念之间共享的信 息量越多，则概念之间的语义相似性就越强，概念之间共享的信息量越少， 则概念之间的语义相似性越弱。 美国宾西法尼亚大学的r c s n i k 给出了计算概念信息量的公式，认为两个 概念之间的相似性可以通过他们共享的信息的多少来判断，而两个概念共享 的信息量近似等于包含它们的最近祖先的信息量f l 钔。计算的方法是基于在一 个特定的文本集中概念出现的概率来计算的。从信息量计算公式可以看出， 在概念层次结构中概念所处的层次越浅，概念之间的相似性越弱；概念所处 的层次越深，概念之间的相似性越强这一性质，这在一定程度上解决了r o y r a d a 提出的方法的不足。但是这种方法存在的问题在于，任何具有相同的最 近共同祖先的两对概念，算出的是完全相同的语义相似性值。这显然是与客 观实际情况不符合的。 上述的方法是基于信息量的，而信息量又是基于概率统计的方法。在统 计的过程中只是计算词出现的频率，并没有考虑词的语义，这就将具有相同 拼写不同的语义的词( 多义词) 也统计在内，造成统计量被夸大，也会将具 有相同语义的不同拼写的词没统计在内，造成统计量被缩小，所统计出来的 信息量是不准确的。因而统计方法的设计将是这种基于信息论模型的语义相 似性计算方法的主要影响因素之一。设计一个较为完善的统计方法并应用于 基于信息论模型的语义相似性计算方法有一定的现实意义，本研究也将对此 进行讨论分析。 5 哈尔滨 _ 程大学硕十学位论文 1 3 3 融合距离模型和信息量模型的方法 这种度量方法提出的目的是要利用距离模型和信息量模型两种方法的优 势并避免其不足。 加拿大滑铁卢大学的j a yj j i a n g 等人鉴于上述两种方法存在的不足，提 出了一种改进的方法【1 5 1 。利用信息论模型的方法计算概念的信息量，并给出 了相邻的概念节点之间的链接边的强度。利用距离方法中的层次结构来计算 概念之间的链接边的权重，并给出了计算链接边的权重的计算公式。 他们按照r o yr a d a 等人提出的最短距离的方法，将两个概念之间的最短 距离中的边的权重进行求和，作为概念之间的语义距离。这个方法全面地考 虑了层次深度、概念密度、链接边的权重和信息量，弥补了上述两种方法所 分别具有的不足。但是，这种方法在计算信息量的时候还是延用统计文本集 的方法，因此统计文本集方法存在的不足仍然无法避免。再者，在计算链接 边的权重的时候，有两个参数q 和b ，但选定它们的值有一定的难度，不同 的选定值将直接影响最终的计算结果。 加拿大曼尼托巴大学的d e k a n gl i n 提出在计算语义相似性不但要考虑概 念之间所共享的信息量，也要考虑概念之间差异信息量【1 6 1 。两个概念的语义 相似度为最近祖先概念中共享的信息量除以两个概念的不共享的信息量的 和。这样就避免了文献 1 4 】中的不足。 北京邮电大学的白东伟等人也提出了一种计算语义距离的方法，也是先 计算链接边的权重，再用最短距离公式来计算概念之间的距离【l7 1 。他们的方 法虽然计算简便，但它没有将节点的深度这一重要的因素加以考虑，进而无 法区分同一层次中不同的密度的子节点。 1 3 4 基于图论的方法 美国印第安那大学信息学院计算机科学系的a n ag m a g u i t m a n 将图论引 入到语义相似性的计算之中，并给出了计算方法【i 引。将概念节点利用它们之 间的关系建立为一种图的结构，将节点之间的链接边看作是一个边的集合， 从总体上考虑了三种概念之间的链接关系。但其计算的中心思想是与基于信 息量的方法是一致的，并没有质的改变，只是理论上更加严谨，信息量模型 本身所固有的缺点并没有解决。 6 哈尔滨j 翻犟大学硕十学位论文 j m i i i i i | i 1 3 5 基于社会标签的方法 德国达姆施塔特理工大学的f l e h m a n n 等人提出用三元组的形式进行 概念的形式化的分析【1 9 1 。用( u ，r ，t ) 来表示用户u ，用标签t 来标注资源r 。美 国印第安纳大学的b e n j a m i nm a r k i n e s 等人用四种聚合的方法( 映射方法、分 布式方法、宏聚合方法和协同聚合方法) 【2 0 1 。将三元组( u ，r t ) 的三维维度成功 的降低为二维( r ，t ) 在此基础之上，进行资源或者t a g 的相似性的计算。但是， 由此带来的缺陷便是用户u 的信息必然有所缺失，进而资源或者t a g 的相似 性计算也会有所偏差。另外b e n j a m i nm a r k i n e s 等人利用四种聚合的方法分别 给出了t a g 和资源的相似性计算方法，其主要的思想是用t a g 来计算资源的 相似性，用资源计算t a g 的相似性。并指出采用协同聚合方法是进行相似度 计算的一种较好的方法。 1 3 6 目前算法的比较及存在的问题 表1 1 给出了上述五种计算语义相似性的法的比较结果。 表1 1 五种计算语义相似性的方法的比较 方法类别直观性理论性层次结综合考虑距离、文本集使用语义区 构依赖深度和密度分精度 基于距离强强强是 否 弱 基于信息比较强强弱否是比较强 量 融合距离比较强强 比较强 是是强 和信息量 基于图论弱 强 强否是比较强 基于社会强 弱 弱否否比较强 标签 7 哈尔滨t 程大学硕十学何论文 从表1 1 中容易看出，五种方法各有利有弊。基于距离的方法虽然多个 方面的表现都很好，但它过于依赖概念的层次结构。另外，该方法还有一个 致命的缺陷，就是它无法区分具有相同深度但密度不同的不同概念节点。基 于信息量的方法也有很多优点，但它没有综合考虑影响语义相似性的非常重 要的三个因素：距离、深度和密度，而且也无法避免地具有统计文本集过程 本身所固有的缺陷。融合距离模型和信息量模型的方法由于同时采用了两种 方法的优点，所以缺陷不是很明显，但如上所述，它仍然具有采用信息量模 型的统计文本集方法所固有的缺点。基于图论的方法，它的创新之处在于， 将图论的理论引入到了语义相似性计算方法的研究之中，在理论上有新的发 展，但其核心思想与基于信息论的方法很相似。基于社会标签的方法，虽然 没有使用文本集，也不依赖于概念层次结构，因此容易计算，计算量也较少， 但在计算时会丢失一部分信息。再者，由于用户在对资源打标注的时候，具 有很大的随意性，也不一定每一个用户对资源所打的标注就一定是正确的， 有的用户可能对资源打的标注与该资源毫无关系。因此，这种基于t a g 技术 的计算相似度的方法可能出现不准确性。 最理想的计算语义相似度的方法是直观性要很好，又具有一定的理论依 据，最好是不过分依赖层次概念的结构，又充分体现距离、深度和密度的影 响，并不使用文本集，还可以区分具有不同深度的概念节点、具有相同深度 且不同密度的兄弟概念节点和具有不同深度且不同密度的概念节点。这在技 术上实现还是比较困难的。本研究的目的就是希望可以将上述五种计算方法 的缺陷尽量的加以弥补，并充分的利用它们的有利的一面。从表1 1 中可以 看出，较好的方法是融合距离模型和信息量模型的方法。所以本研究就主要 基于这一方法加以改进，提出一种增强语义区分精度的w e b 服务语义相似性 度量方法，能够实现在继承原有的基于融合距离和信息量两种方法的优点基 础之上，不再使用文本集，并且实现能够区分具有不同深度的概念节点、具 有相同深度且不同密度的兄弟概念节点和具有不同深度且不同密度的概念节 点。 8 哈尔滨t 程大学硕十学位论文 1 4 论文的主要工作 1 4 1 研究内容 本文研究的具体内容如下： 1 研究w e b 服务的语义分类描述模型，为w e b 服务语义相似性的度量提 供基础。 2 在上述w e b 服务的语义分类描述模型基础上，提出一种增强语义区分 精度的w e b 服务语义相似性度量方法。针对w e b 服务语义信息来源的不同 方面，分别研究了计算w e b 服务相似度的s s m m w s 和s s m m w s t 方法。 综合考虑距离、深度及密度等因素对语义相似性的影响，给出了相关概念的 定义，给出了具体的语义相似性计算方法和公式，并给出方法的数学证明。 3 进行实验以验证本文所提出的w e b 服务语义相似性度量方法。包括实 验数据的获取、实验设计、实验实现以及实验结果的分析和讨论，并给出相 应的评估方法。 1 4 2 本文的贡献 本文的贡献主要包括： 1 建立了一种扩展语义标注的w e b 服务语义分类描述模型 ( s c d m 4 w s ) 。该模型在现有w 曲服务描述模型基础之上采用t a g 技术扩 展了w e b 服务描述的语义信息，为w e b 服务的语义相似性度量提供了语义 基础。并给出了w e b 服务语义相似性度量中的语义区分精度概念的定义。 2 在s c d m 4 w s 模型基础上，提出了一种增强语义区分精度的w e b 服务 语义相似性度量方法( s s m e r g e ) ，包括处理不同来源语义信息的s s m m w s 和s s m m w s t 方法，给出了相似性度量公式和综合计算公式。该方法融合了 距离和信息论的方法，弥补了距离模型和信息量模型的固有缺点，并综合考 虑了距离、深度、层次和密度等因素，并将这三个因素融合在了一起，解决 了其它的方法中不能区分兄弟节点的问题；解决了其他方法中不能区分具有 9 哈尔滨t 程大学硕十学位论文 不同深度、具有不同密度的节点的问题。 3 将s s m e r g e 方法和其他的语义相似性度量方法进行了比较分析，并设 计和实现了相关实验来验证方法的正确性和可行性，给出了实验结果的分析、 评价和讨论。 1 5 论文的组织结构 本文的组织结构安排如下： 第l 章绪论简单的介绍了该课题的研究背景和现实的意义，介绍并分 析了现有的国内外计算语义相似性的计算方法及它们的优缺点，并指出了目 前的有关相似度计算方法存在的主要问题，进而在此基础上介绍了本文的主 要研究内容。 第2 章w e b 服务语义分类描述模型本章介绍了相关的概念并给出了 w 曲服务语义分类描述模型的具体描述和建模方法。 第3 章增强区分精度的w e b 服务语义相似性度量方法本章详细介绍 了计算语义相似性的方法，针对语义信息的不同来源分别给出了具体的计算 方法及综合计算公式，并给出了数学上的证明，还阐述了该方法的特点。 第4 章实验与分析本章介绍了实验所采用数据集和具体的评估方法， 与其它方法进行了对比分析和实验结果的讨论，验证了本文所提出的方法的 可行性和有效性。 结论总结本文研究结论、不足之处和未来的工作方向。 l o 哈尔滨t 程大学硕+ 学位论文 第2 章w e b 服务语义分类描述模型 建立w e b 服务的语义相似性描述模型是计算w e b 服务的语义相似性的前 提和基础工作，模型建立的恰当与否直接影响到最终相似性计算结果的好坏。 本章详细描述了本文所采用的w e b 服务语义分类模型的建立方法和过程。 2 1 引言 互联网上存在的信息过于庞大，因此人们在w e b 上进行信息搜索、调用 和表示等方面都存在着极大的困难。为了能够使得计算机可以自动的识别和 有效处理互联网上各种复杂多样的海量信息，并在识别和处理互联网上各种 信息的基础之上可以更好地利用这些信息，互联网的创始人t