基于概念间边权重的概念相似性计算方法.doc

基于概念间边权重的概念相似性计算方法文章编号:1001-9081(2012)01-0202-04 doi:10.3724/sp.j.1087.2012.00202摘 要: 介绍了传统的基于距离的相似度计算方法，针对其在距离计算中包含语义信息不充足的现状，提出了一种改进的使用wordnet的基于概念之间边的权重的相似性度量方法。该方法综合考虑了概念在词库中所处层次的深度和密度，即概念的语义丰富程度，设计了一种通用的概念语义相似性计算方法，该方法简化了传统语义相似性算法，并解决了语义相似性计算领域的相关问题。实验结果表明，所提方法在rubenstein数据集上与人工判断有着0.9109的相关性，与其他经典的相似性计算方法相比有着更高的准确性。关键词: 概念相似度计算；wordnet；边权重；语义信息中图分类号: tp393.08 文献标志码:aabstract: the traditional distance-based similarity calculation method was described. concerning that the method of distance calculation does not contain sufficient semantic information, this paper proposed an improved method which used wordnet and edge weighting information between the concepts to measure the similarity. it considered the level of depth and density of concepts in corpus, i.e. the semantic richness of concept. using this method, the authors can solve the semantic similarity calculation issues and make the calculation of similarity among concepts easy. the experimental results show that, the proposed method has a 0.9109 correlation with the benchmark data set-rubenstein concept pairs. compared with the classical method, the proposed method has higher accuracy.key words: concept similarity calculation; wordnet; edge weight; semantic information0 引言词与词之间的相似性研究多年来一直是自然语言处理和信息检索的一部分，是正确理解文本内容的关键，在计算机语言学和人工智能及应用中语义相似性问题都比较普遍，比如词义消歧、文档分类或聚类、词语拼写纠错、自动翻译、本体学习和信息检索等。语义相似性是比较词语之间的匹配程度也可以理解成分类学上的接近程度，比如两个概念含有共同的父概念，那么它们的相似性就比较高。但是词语之间的互联不仅仅是这种分类上的父子关系还有很多语义上的关联，这样本文引入了语义相关性的概念，语义相关性是概念之间通过某种联系而产生关联，本文用方法识别出这种关联使这种关联能被计算理解这样就达到了使用语义信息。在概念之间进行语义相关的计算都是在已经存在并建好的知识库中进行的，比如wordnet1,wordnet是由普林斯顿大学认知语言实验室开发的一个词库。在近几十年间很多语义相似性的算法被提出，这些方法主要可以分为以下几类：1）基于距离度量的相似性算法；2）基于信息量的相似性算法；3）基于向量空间的相似性算法；4）综合以上几种方法的计算方法。文献2提出一种计算词之间的最短路径的算法，通过这个最短路径来衡量两个概念之间的相似性；wu等3引入最小共同父概念来表示两个概念的共性的多少；leacock等4提出的算法都是从路径长度以及概念的深度上考虑概念之间的相似性；li等5则以非线性函数的形式对最短路径和最小共同父概念组合进行计算；al-mubaid等6提出了一种结合最短路径长度和最小上层父概念深度的基于簇的方法，它为每一个层次上分支结构到根节点的部分定义一个簇，使得低层次上的概念对的相似度比高层次上的相似性高；lin等7提出的基于信息量的计算方法，考虑了两个概念间在知识库中的共享信息和两个概念分别带有语义信息的比率。本文提出一种基于wordnet1并采用概念之间边的权重的相似性算法，概念之间的边的权重能反映概念在词库中的语义关系，一个概念越靠近叶子节点、含有的子概念越少，就说明含有的语义信息就越丰富8-9。在计算语义相似性时，两个概念距离越短则它们之间的相似性就越高2。本文在已有的距离相似性算法的基础上引入概念之间边的权重，去衡量概念在层次树中的语义丰富性，通过rubenstein原始数据集10进行实验，表明该方法在计算语义相似性问题上较其他一些算法和人工判断有更高的一致性。1 距离度量相似性算法假设词语组成的结构是一种像树形一样的层次结构，每个节点代表一个词语或概念，rada2是指代文献2吧？原来指文献1？请明确。证明了在连通不同的两个概念c1和c2之间的最短边数是衡量这两个概念之间距离的尺度。对于两个词语w1和w2之间的距离的度量可按以下三条规则进行度量2：1)w1和w2是同一是“同一”?还是“统一”？请明确。个概念，则它们之间的距离为0；2)w1和w2不是同一概念但是它们所属的词义中包含有相同的词的时候则它们的距离为1；3)w1和w2既不属于同一概念也没有在所属词义中包含相同的词则计算它们之间的最短路径的距离。基于距离的相似性算法最大的优点是它们计算词语之间的相似性只基于某种词库或某一本体，这样就对不同领域有更好的适应性。但是该方法最大的问题，就是太过依赖词库或本体的完整程度、均匀性和覆盖面11，如果词库不完整或是没有覆盖足够多知识，就容易导致计算结果不正确或不符合程序的要求。而且，这种方法在计算距离的时候是根据词库的分类来计算，这容易忽略其他因素对距离度量的影响，而且这种分类关系不能作为语义相似性的度量12。2 基于概念间边权重的相似性计算方法充分利用距离相似性算法的优势，针对上述方法存在的缺点，本文改进了li等的方法5，采用给边加上一定权重的方式来改进算法，因为在不加权重以前边的默认权重都为1，由于没有完全考虑到概念节点所处的位置对语义相似性的影响，容易导致计算结果不精确。概念节点间边权重的影响因素很多，包括节点所处词库网络的密度、节点在词库网络中的深度、连接节点之间链接的类型和连接边的强度13，文献8的结果表明连接节点之间链接的类型和连接边的强度对相似性计算的影响不大，所以在此基础上本文主要考虑前两种因素对概念间边权重的影响。2.1 边的权重计算在考虑概念所在层次深度和概念含有的子概念的个数情况下，计算出来的边权与路径的长度只存在较小的偏差，但是这样却能体现边权信息对词语准确度的影响，实验结果也显示出用此方法计算出来的边权信息能较大程度地拟合人工判断的结果。例如boy和person与boy和animal两对概念在词库中的距离是相同的都是4，可是显然前者的相似性更高，在引入本文方法后boy和person的距离为1.20，boy和animal的距离为1.93，可以很好地区分两者之间的相似性。首先是概念所处位置的密度，本文采用了概念的子节点个数与所有节点的个数的比重来衡量概念的密度。一个概念所含有的子概念个数越多说明这个概念越抽象，则该概念所连的边的权重应该要取小一些的值14；相反如果概念的子概念个数很少，则说明该概念是一个很具体的概念，所以对它所连接的边应该赋予高一些的权限。由式（1）表示了概念所处的位置的密度因子对权重的影响：density(c1,c2)=1ln(hypo(c)+1)ln(maxwn)（1）请补充对数log的底？若没有，请说明原因。其中：c的取值是在c1和c2中取层次比较低的那个进行计算；hypo(c)表示概念c的子孙节点的个数，并且不考虑重复的概念节点；maxwn表示整个词库中的词语的个数，本文采用的是wordnet中所有名词的个数。概念的深度因子对概念所连边的影响也很重要，本文在考虑深度因子的时候主要是针对其在词库中所处的层次的高低，越低的层次上的概念因为概念比较具体所以对其边所赋的权也就越大；相反在高层则概念的权相对较小，这两处表达的意思相同，是否表达错误，请核实。由式（2）来表示深度因子：depth(c1,c2)=ln(maxdepth(c1),depth(c2)ln d（2）log的底是多少，请补充。其中：depth(c)表示概念c在词库中的深度；d表示整个词库的深度，在wordnet中词库的最大深度为16。在考虑了深度因子和密度因子对概念之间边的权重的影响之后，本文可以把两部分结合起来计算概念之间的权重，如式（3）所示：weight(c1,c2)=tdensity(c1,c2)+(1t)depth(c1,c2)（3）其中t的取值范围在0,1。当t=0时只考虑了概念的深度对概念之间权重的影响；t=1时则只考虑了概念的密度对概念之间权重的影响。2.2 改进的相似性计算方法本文的相似性计算公式仍采用文献5的公式原型，在路径的计算上考虑上文的概念之间的边权重信息。通过计算最短路径上概念之间边的权重，综合路径上概念的密度和深度等因素的影响，使得源概念对之间的语义相似性计算更加精确。sim(c1,c2)=eaw1,w2path(c1,c2)lcs(c1,c2)weight(w1,w2)eblcs(c1,c2)eblcs(c1,c2)eblcs(c1,c2)+eblcs(c1,c2)(4)式(4)中，对于blcs(c1,c2)未予交代，是否有必要补充说明一下，请核实。“blcs(c1,c2)”其中：path(c1,c2)表示连接c1和c2取不同的词义的时候描述的最短路径上的概念；lcs(c1,c2)指的是概念c1和c2的最近公共祖先概念节点；weight(w1,w2)则表示词义概念w1和w2之间的边的权重，且a0,b0。2.3 语义相似性计算算法描述输入 两个概念a和b。输出 两个概念之间的语义相似性。第一步 找出概念a和概念b在词库wordnet中所处的位置。第二步 判断概念a和概念b是否是相同概念，相同则跳转到第五步，如果多义词中包含有相同的概念词语做一标记。第三步 计算概念a和概念b之间的语义距离，取其多义词中最短路径作为两个概念之间的路径，记为path(a,b)，并保存两个概念相交的概念节点记为lcs。第四步 遍历path(a,b)中相邻的两个概念节点，按式（1）和式（2）计算两个概念的密度density和深度depth，然后把density和depth代入式（3）计算边的权重并累加到weight变量中。第五步 如果是相同概念则其weight等于0，lcs等于两个概念中任意一个，如果是两个概念中含有相同概念词汇则weight等于1；否则weight取第四步计算出来的结果。第六步 计算lcs在词库中所处层次h，然后把h和weight代入式（4）计算出概念a和b之间的相似性。3 实验结果与分析本文的实验通过计算出来的结果之间的相关系数来衡量算法的性能，相关系数是变量之间相关程度的指标，用r表示，r的取值范围为-1,1。|r|值越大，误差就越小，变量之间的线性相关程度越高；|r|值越接近0，误差就越大，变量之间的线性相关程度越低。本文采用皮（尔生）氏积矩相关系数来计算两个结果之间的相关性，计算公式如式(5)所示：rxy=ni=1(xi)(yi)ni=1(xi)2ni=1(yi)2(5)其中：指的是数列x的平均值，则指的是数列y的平均值，xi表示x数列中的第i个数，yi表示y数列中的第i个数。3.1 实验方案本文的相似性计算采用rubenstein数据集10，并利用wordnet2.0作为实验的词库，实验过程中首先实现了前文提到的距离相似度算法，为了进行比较，对文献7的基于信息量的相似性度量算法与本文提出的方法进行了比较，如表23所示。3.2 概念间的语义相似性计算根据上述边权算法和相似性算法，并基于wordnet词库丰富的词语来进行相似性计算。在实验中，深度和密度对概念相似性影响相当，所以取两项的权重因子t=0.5，经过多次尝试，可以验证在a=0.3,b=0.4，取定的情况下相似性算法与人工判断最接近，相关度为0.9109。表1列出了rubenstein和m&c进行的实验做出的结果以及各项词语的指标，其中length值的是概念对的最小距离长度，depth指的是概念对的最小上层父概念的在整个词库中所处的层次。本文的实验是基于rubenstein10所做的实验结果即rg rating，并以此来估计算法的性能。表1中的mc rating表示的是miller and charles（m&c）进行的人工实验结果，m&c数据集是rubenstein的一个子集，两者的相关度为0.9715。表1中的rg rating表示什么，是否需要交代一下，请核实。实验过程分为两个阶段：边权计算和概念间的相似性计算。本文使用m&c选取的30对概念，这些概念都进行了人工打分，打分区间在0,4。很多研究者都只采用了这30对词组而忽略其他词组来进行研究，大量的实验表明furnace和stove存在意义上的相似可是两者语义距离却很远导致其不是很好的测试数据8，所以本文不考虑这组数据并选取了m&c数据集的其中27组作为本文的实验数据集。表2列出了本文方法与前述方法的计算结果，由表2数据可以发现本文方法与li方法5比较接近且本文方法与人工判断的数据拟合得比较好。本文的方法是在文献5的基础上的改进，不同的方法对相似度的判断都有不同的结果和准确性，在rada等2刚提出距离相似度度量的时候，他的方法在当时是较准确的，随着技术的不断创新和存储结构的不断优化新的方法不断提出，计算结果的准确性也越来越高。li提出的假设，把resnik16对m&c数据集的测试出来的相关系数作为相似性算法研究的上界，也即0.95835。表3列出了各种方法与人工结果的相关系数，本文方法与人工结果有较高的相关性。4 结语本文在li等5提出的非线性方程相似度计算方法的基础上，改进了其中距离度量的标准，采用了基于边权信息的计算方法。传统的基于距离的度量方法，因为没有考虑到概念所处位置的语义信息，所以在距离相同的时候概念的相似度会惊人地相似，而考虑了概念所处位置的语义信息后则把概念的这些语义相关性充分地体现了出来。本文的实验结果与rubenstein源数据集的相关系数为0.9109，表明该方法与人工判断的数据有较好的相关性。但是算法还有很大的提升空间，正如li所说的，当真正的非线性函数被发现，则算法的性能会有很大的提升。由于本文的方法只考虑了一部分信息，一个概念的语义信息还有很多比如连接类型和连接强度等因素，这些信息都会影响相似性判断的准确性，所以在以后的研究过程中需要加入更多的语义相关信息使相似判断更加准确。参考文献:1fellbaum c. wordnet: an electronic lexical database m. cambridge, ma: mit press, 1998.2rada r, mili h, bichnell e, et al. development and application of a metric on semantic nets j. ieee transactions on systems, man, and cybernetics, 1989, 9(1): 17-30.3wu z, palmer m. verb semantics and lexical selection c/ proceedings of the 32nd annual meeting of the association for computational linguistics. stroudsburg: association for computational linguistics, 1994: 133-138.4leacock c, chodorow m. combining local context and wordnet similarity for word sense identification m/ wordnet: an electronic lexical database. cambridge, ma: mit press, 1998: 265-283.5li y, bandar z a, mclean d. an approach for measuring se-mantic similarity between words using multiple information sources j. ieee transactions on knowledge and data engineering, 2003, 15(4): 871-882.6al-mubaid h, nguyen h a. a cluster-based approach for semantic similarity in the biomedical domain c/ proceedings of the ieee engineering in medicine and biology society. new york: ieee press, 2006: 2713-2717.7lin d. an information-theoretic definition of similarity c/ proceedings of the 15th international conference on machine learning. san francisco: morgan kaufmann, 1998: 296-304.8jiang j, conrath d. semantic similarity based on corpus statistics and lexical taxonomy c/ proceedings of the international conference on research in computational linguistics. cambridge, ma: mit press, 1997: 19-33.9seco n, veale t, hayes j. an intrinsic information content metric for semantic similarity in wordnet c/ proceedings of the 16th european conference on artificial intelligence. amsterdam: ios press, 2004: 1089-1090.10rubenstein h, goodenough j b. contextual correlates of synonymy j. communications of the acm, 1965, 8(10): 627-633.11cimiano p. ontology learning and population from text: algo-rithms, evaluation and applications m. new york: springer-verlag, 2006.12bollegala d, matsuo y, lshizuka m. websim: a web-based semantic similarity measure c/ proceedings of the 21st annual conference of the japanese society for artificial intelligence. berlin: springer-verlag, 2007: 757-