《语义相似性测度方法研究综述_黄世国》由会员分享，可在线阅读，更多相关《语义相似性测度方法研究综述_黄世国（3页珍藏版）》请在金锄头文库上搜索。
1、第 25卷第 2期 计算机应用与软件Vol125No. 2 2008年 2月 Computer Applications and Soft wareFeb . 2008语义相似性测度方法研究综述黄世国1 , 2耿国华21(西北大学信息科学与技术学院 陕西 西安 710069)2(福建农林大学计算机与信息学院 福建 福州 350002)收稿日期: 2006- 04- 25 。国家自然科学基金 ( 60573179)。黄世国, 讲师, 主研领域: 智能信息处理等。摘 要 语义相似性测度是信息检索中的关键技术。回顾了基于距离的、 基于信息内容的、 综合了距离和信息内容的、 基于图的语义相似性测度算法
2、, 认为基于图的语义相似性测度算法是今后研究的方向。关键词 语义相似性 基于树 基于图THE SURVEY ON SEMANTIC SIM ILARITY METRICHuang Shiguo1, 2Geng Guohua21(College of Infor mation Science and Technology, Northwest University, Xip an 710069, Shaanxi, China)2(College of Computer and Infor mation, FujianAgriculture and Forestry University, Fuz
3、hou 350002, Fujian, China)Abstract Se mantic si m ilaritymetric is a key technique in infor mation retrieva.l The algorithms of se mantic si m ilarity metric based on dis -tance , infor mation content , the combination ofdistance and infor mation content , and graph are revie wed, and it is pointed
4、out that graph-based se mantic si milaritymetric algorithm is the trend in future research .K eywords Se mantic si milarity Tree -based Graph -based0 引 言语义相似性测度多年来一直是自然语言处理和信息检索研 究的重要组成部分, 是计算语言学和人工智能应用中亟待解决 的问题。特别是近几十年来 Internet技术的高速发展, 网络上出 现了大量共享的文献资料, 如何使用户高效且准确地找到所需的信息是基于 WEB信息检索的研究热点。该研究涉及到两个
5、方面: 一是如何发现相关的 WEB; 二是存在相关 WEB情况下如何进行排序。上述问题的解决途径是找到比较好的 WEB间语 义相似性测度算法。传统的相似性测度往往以手工的方式进 行。这种方法费时费力且效率不高, 无法解决网页快速增长、 内容不同一性的问题。因此, 需要有语义相似性的自动测度算法。 目前语义相似性的自动测度算法主要分为两类: 一是基于 树的语义相似性测度算法, 二是基于图的语义相似性测度算法。1 基于树的语义相似性研究基于树的语义相似性计算一般适用于/ is -a0的体系结构, 这类算法大体上分为两种: 一是基于距离的语义相似性测度; 二 是基于信息内容的语义相似性测度。1 .
6、1 基于距离的语义相似性测度1. 1. 1 边作为距离 如果树状语义网中所有的边即树的分支是等长的, 那么边 的数目可以作为距离的测度。假定要确定词 w1和 w2之间的语义相似性, 在语义网中词是与 / is -a0树状结构中的概念相对应的, 可以在该语义网中首先找到包含待比较词的那些概念。在此情况下, w1和 w2之间的语义相似性可以用连接这两个概念之间的最短路径来表示 1。例如, 图 1是取自 W ordnet本体中的一小部分2。 boy和 girl之间的最短路径是 boy -male -person-fe male -gir, l最小路径长度为 4。而 teacher和 boy之间的最小
7、路 径长度为 6。因此, girl比 teacher在语义上更接近于 boy 。该测度算法在医学语义网中获得了很好的测度结果。但是在一般的 语义网中如 W ordnet , 则较难获得很好的结果。如图 1中 ani mal和 boy的最小路径长度也为 4, 因此就得出了一个错误的结论, 即 ani mal比 teacher在语义上更接近于 boy 。其原因在于自然语言的分类中边不是等长的, 随着深度的增加, 边的长度变小。图 1 树状语义知识库38 计算机应用与软件2008年1. 1. 2 其它类型的距离在 Wordnet 、 Roget等诸多自然语言本体中, 边是不等长的, 因此最小路径长度
8、测度算法不再适用。为此, 许多学者对基于边的相似性测度方法进行修改, 引进了亚层次密度、 层次深度、 连接类型、 结点信息内容等多种相似性测度的参量。Agirre和 R igau等将亚层次密度作为相似性度量的标准, 认 为当树状语义网的层次较为完整或者层次中词汇的分布规律基本上反映了自然语言中词汇的分布规律时, 密度较高的层次的 词汇间相似性要比密度较稀疏的层次的词汇间相似性要大一些 3。但这种算法的不足之处在于假设的条件与实际情况不符合, 并且密度有过度泛化的风险。层次深度也经常作为语义相似性测度的标准, 但基于层次的相似性算法对于 W ordNet中的 / is -a0结构比较适用。但由于
9、 Roget类型的层次是相对较平且一致的, 基于层次深度的语义相似性将不再适用。 在 WordN et中引入连接类型是显然的, 其连接类型主要包括/ is-a0和/ has part0。根据不同的类型需要选择不同的测度方 法。对于 Roget , 其连接类型则要复杂得多, 在此情况下较难确定语义相似性测度的算法。 由于上述的每个参量均有其不足之处, 一些学者在算法中综合考虑了这几个不同的参量。 Sussna根据亚层次密度、 层次 深度和连接类型对边进行加权。M c Hale使用了介入词的数目。介入词的数目忽略了层次结构, 把层次当成了一个平面型的文 件 5。该算法假设: 词汇的排序必须是正确的
10、; 所有词汇均被表示或者在层次中均匀分布。这与实际情况不符。1 . 2 基于信息内容的语义相似性测度概念的信息内容等于出现这一概念实例的概率, 该概率是使用 Bro wn词典中每个词出现的相对频率来代替的。Resnik仅使用概念的信息内容进行语义相似性测度, 并将其结果与边计 数算法以及人类的判断水平作比较。Resnik定义两个概念间的相似性为层次中包含了待比较的概念的最大信息内容。其计算 过程如下 6:Step 1 计算每个词出现的相对频率: p( c) = Freq( c) /N Step 2 计算每个概念的信息量: IC( c) = log- 1p( c) , p( c)是概率。越普通的
11、词, 其信息量越小。1 . 3 综合了距离和信息内容的语义相似性测度R ichardson和 Smearon 使 用 了 密 度、层 次 深 度 和 信 息 内容 3。Jiang和 Conrath不仅使用信息量, 而且使用边计数、 局部密 度、 概念深度和连接类型进行语义相似性测度的算法 4, 以参数 A 和 B 来优化公式, 该参数用于控制概念深度和密度对边权 重计算的影响。如果 A = 0和 B= 1 , 那么概念 c1和 c2之间的语义相似性简化为:D ist( c1, c2) = IC( c1) + IC ( c2) - 2 IC (LS( c1, c2) ), 其中 LC( c1,
12、c2)表示包含 c1和 c2的最近的父概念。LiYuhua等将概念 c1和 c2的语义相似性作为路径长度、 层次深度和局部语义密度的函数 7, 即:s(c1, c2) = f( l, h, d)( 1)其中 l是 c1和 c2间的最短路径, h是概念的层次深度, d是 c1和 c2的局部语义密度。路径长度和深度根据词汇语义网计算, 而局部语义密度则 根据文集来计算。假设式 ( 1)可写成三个独立的函数, 即:s( c1, c2) = f(f1( l), f2(h), f3(d) )( 2) f1、 f2、 f3分别是路径长度、 层次深度和局部语义密度的传递函数。 假定路径长度和层次深度是独立的
13、, 那么式 ( 2)在特定的情形下将变为基于边的方法。式 ( 2)的取值范围为 0, + ), 但语义相似性的取值为 0, 1, 当两个概念语义完全相似时赋值为 1, 完全不相似时赋值为 0, 因此将信息转换成语义相似性 是一个非线性的关系。路径长度可以分成如下三种情形进行计算: 一是 c1和 c2是 相同的概念, 有相同的含义, 其语义路径长度为 0 ; 二是 c1和 c2不是相同的概念, 但包含一个或多个相同的词汇, 共享了部分相 同的特征, 将 c1和 c2间的路径长度为 1; 三是 c1和 c2不是相同的概念, 也不包含相同的词汇, 则其路径长度为 f1( l) = e- Al, 其
14、中 a是常数, f1( l)是 l的单调递减函数。层次深度是通过计算词汇树状语义网的顶点开始一直到该 概念的层次数。多义词最短路径是由层次深度推导出来的。一般来说树状结构中高层的词汇是比低层更一般的概念, 具有更 少的语义相似性。因此计算 s( c1, c2)时需要缩小高层概念的语义相似性, 放大低层概念的语义相似性, 同样语义相似性取值区 间为 0, 1。令 f2(h)是深度 h的递增函数, 则为了满足上述条件,f2(h) = ( eB h- e- Bh) ( eBh+ e- B h)( 3)其中 B是平滑因子, 当 B y 时, 层次深度没有意义。局部语义密度无法从树状语义网中获得, 需要
15、通过文集进 行计算。局部语义密度测度的一种方法是计算概念信息内容。设在文集中出现概念 c的实例的概率是 p( c), 那么概念 c的信 息内容为:IC( c) = - log p( c)( 4) 对于概念 c1和 c2, 语义相似性测度通过计算最大信息内容得到: si m (c1, c2) =max cI sub( c1, c2) - log p( c) 其中 sub( c1, c2)是包含概念 c1和 c2的概念集。 词 w1和 w2之间的语义相似性定义为:wsim(w1, w2) = max c1, c2 sim( c1, c2) 其中 c1和 c2分别是 w1和 w2可能具有的概念。因此
16、, 局部语义密度定义为 wsim(w1, w2), 其传递函数为:f3(wsi m ) =eK #w sim (w1,w2)- e- K # wsi m (w1, w2) eK #w sim (w1,w2)+ e- K # wsi m (w1, w2)其中 K 0, 当 K y 时, 词的信息内容没有意义。最后, 通过计算式 ( 2)得到词间的语义相似性。2 基于图的语义相似性研究目前对树状结构的语义网中概念的语义相似性测度进行了 大量研究8, 但是对基于图的语义网中概念的语义相似性测度的研究成果却很少。其主要原因在于基于图的语义网中既包含 了树状结构又包含了非树状结构。M aguitman提出了基于图的语义相似性测度算法 9。基于图的本体是结点表示概念的图。每个结点包含代表文档的对象。一个本体图既有/ is-a0的树状成分, 又具有其它类型连接 的非树状成分。举例来说, ODP本体是一个有向图 G = (V, E),第 2期 黄世国等: 语义相似性测度方法研究综述39
