综合多层信息的本体概念相似度计算方法的研究.doc

第6期赵欢等：综合多层信息的本体概念相似度计算方法的研究141综合多层信息的本体概念相似度计算方法的研究赵欢，李仁发，王家琴，张在美（湖南大学 计算机与通信学院，湖南 长沙410082）摘 要：提出了一种综合多层信息的本体概念相似度计算方法。首先从概念的单层信息出发，分别计算概念的语义、语用以及字面3个层面的相似度，在此基础上，对各层面相似度进行综合计算，得到能够更加全面的描述概念整体特征的综合相似度。实验结果表明，与基于单层信息的概念相似度计算方法相比，综合相似度计算方法能够有效提高计算精度，与人类主观判断的结果更加吻合。关键词：智能信息检索；本体；概念相似度；主观判断 中图分类号：TP391 文献标识码：A 文章编号：1000-436X(2009)06-0135-07Research on an ontology concept similarity calculation approach based on the integrated multilayer information ZHAO Huan, LI Ren-fa, WANG Jia-qin, ZHANG Zai-mei(College of Computer and Communication, Hunan University, Changsha 410082, China)Abstract: A new ontology concept similarity calculation approach based on the integrated multilayer information was proposed. The approach started from the single-layer information of concepts, calculated the semantic, pragmatic and literal similarity respectively, and then integrated these similarities according to a certain integrated method, lastly, got the integrated similarity which described concepts more entirely. Experimental result demonstrates that, comparing with the methods based on single-layer information, the integrated approach improves the precision of concept similarity calculation effectively, and the calculation results inosculate with subjective judgment more tightly.Key words: intelligent information retrieval; ontology; concept similarity; subjective judgment1 引言收稿日期：2008-04-09；修回日期：2009-04-15基金项目：湖南省科技计划重点基金资助项目（2007GK2015）Foundation Item: The Planned Science and Technology Project of Hunan Province (2007GK2015)随着网络信息技术的迅速发展，互联网已成为人们获取信息最重要的途径。而信息的积累带来了巨大潜在知识价值的同时，也引发了信息爆炸的难题。面对海量的网络数据，能否方便快捷地搜到用户感兴趣的知识依赖于信息检索领域的发展。在信息检索领域中，需要研究的内容众多，包括信息的表示、存储、查询和获取等，而准确判断用户查询式与数据库中信息之间的相似度，是提高检索效率和准确率的前提。由于万维网信息不能被机器理解和自动处理，查询结果并不令人满意。Tim Berners- Lee于2000年正式提出了语义网的概念，它是一种能理解人类语言的智能网络，用本体来描述数据的语义，形成有结构的数据，更加便于信息的组织和查找。因此，语义网中本体概念相似度的计算成为提高信息检索准确率的关键。目前计算概念间相似度的方法大多局限于利用概念单一层面的信息，如词汇语义、上下文环境、词形等，不能全面体现概念间的相似程度，若综合概念的多层信息来计算，则预期可提高概念间相似度的准确率，对提高信息检索的效率具有重要意义。2 相关研究本体在20世纪80年代被引入人工智能领域，强调用特定领域中已达成共识并经明确定义的概念集以及这些概念间的关联来表达语义，它向人们提供对知识的共同理解，并形成计算机可读的数据结构，以便于计算机智能地存储、组织和查找信息1。概念是本体结构中的主要实体，概念相似度计算是语义网中信息查询、文本匹配等的基础，用于计算概念相似度的信息包括概念本身的各层面信息，如语义、语用、字面等25。概念相似度在不同的应用领域中有不同的具体含义，如在信息整合领域，它一般指文本间的匹配程度；在基于实例的机器翻译中，主要用于衡量文本中概念的可替换程度；而在信息检索领域中，相似度则反映信息与用户查询的匹配程度，相似度越高，表明信息与用户的请求越接近。本文的工作背景即为信息检索领域。本文约定，概念相似度的取值范围在0到1之间。当相比较的2个概念完全相同时，其相似度定义为1；当2个概念完全不同时，其相似度定义为0；其情况下，其相似度在0到1之间。概念相似度计算是智能信息检索的基础。从概念本身各层面信息的角度出发，将现有计算概念相似度的方法总结为3类。1) 基于语义的概念相似度计算方法随着对信息检索智能化要求的提高和语义网的推出，利用概念语义计算相似度的研究越来越受到关注23。概念语义相似度计算方法主要有2种。一是基于义类词典或词汇分类体系进行计算。这种方法将所有同类的语义项构成一个具有概念层次的树状结构，通过计算相应结点之间的距离(概念距离)或信息熵即可获得其语义相似度。这一类义类词典和词汇分类体系资源包括Rogets Thesaurus、WordNet、知网(HowNet)、同义词词林等，这种方法效果较好，易于理解，但它依赖于比较完备的按照概念间结构层次关系组织的大型语义词典。二是基于语料库计算语义相似度。这种方法将概念的基于语料库的上下文信息作为参照依据，根据概念的语义环境相似情况以及概念本身在上下文中出现频率的统计情况获取语义相似度。主要方法包括词汇共现、词汇语义向量空间模型等6，这种方法需要大规模语料库的支持，当语料库较小时会因数据稀疏或数据噪声干扰而影响计算结果。2)基于语用的概念相似度计算方法这种方法根据概念的实际应用环境计算其相似度，可利用的环境信息有搜索引擎的返回结果、互信息等。其中PMI-IR算法7即是利用搜索引擎的返回结果进行统计分析，但搜索引擎的接入、访问速度等性能限制了方法的可行性。LC-IR算法4在PMI-IR方法基础上进行了改进，将搜索引擎与本地的小型搜索引擎结合，对检索结果中2个概念的共现频率进行统计，取得了一定成效。3)基于字面的概念相似度计算方法，即字面相似度计算主要包括基于编辑距离的计算方法5和基于相同字或词的方法8等。该类方法主要通过概念词汇的表层信息进行比较判断，由于语义的多元化，字面完全相同的2个概念，其在不同的上下文中所表示的含义却不一定相同。因此，单凭词形进行相似度计算的方法在智能信息检索过程中存在严重缺陷。以上方法分别从概念的语义、语用和字面3个层面出发，利用词汇的含义、上下文环境和词形等信息对概念相似度进行度量，虽然均可独立完成相似度的计算，但都只偏重于概念的某一单层信息，结果并不理想。而本文将基于以上相关研究，对上述3种方法进行结合，提出一种综合的本体概念相似度计算方法，使概念相似度的度量建立在基于3层信息的综合考虑之上，以达到提高计算精度的目的。3 本体概念相似度的计算3.1 语义相似度计算本文面向中文信息检索，基于义类词典知网计算本体概念的语义相似度。知网是一个以中英文词汇所代表的概念为描述对象，以解释概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。在知网中，利用一系列义原与知识描述语言来刻画概念。这些义原通过上下位关系组织成一个树状义原层次体系。文献9基于知网提出一种利用概念间距离计算概念相似度的方法。设2个概念、，其语义相似度计算公式如下(1)其中，是一个可调节的参数，表示相似度为0.5时的概念距离值，为2个概念、之间的语义距离。考虑到中文词汇中常含有复合词，不适合直接采用上述方法计算其相似度，因此本文提出采用二元分词技术，首先对复合词进行分词预处理，从而达到上述计算过程的需要。例如，复合词“研究项目”经分词预处理之后，可分解为有意义的“研究”和“项目”2个简单概念。复合词之间的相似度，可通过计算经分词之后的简单概念之间的相似度获得(一般复合词经分词预处理之后，只剩2个有意义的简单概念)。假设、为2个复合词，可分解为(按前后顺序)、，可分解为、，则其语义相似度计算为(2)若、中只有为复合词，则有 (3)同理，若只有为复合词，则有(4)其中，、分别为权重参数，且。由于中文字符串通常具有“语义重心后移”的特点10，因此令权重参数。经反复测算实验，设置经验值，。3.2 语用相似度计算所谓语用相似度是指以概念所处的应用环境为背景，若其上下文信息类似，则可由此推断概念之间具有某些相似性7。以现有信息检索系统作为应用环境，将概念提交搜索引擎后，返回的结果通常包含标题、文摘(通常为查询概念及其上下文或页面的前200300字)、统一资源定位符(URL)等信息，可以利用这些信息来计算概念间的相似度。本文利用概念提交搜索引擎返回结果的URL和2个概念同时提交搜索引擎返回结果的标题、文摘中含有查询概念的个数，计算概念间的语用相似度。将概念、分别提交搜索引擎后，在返回结果中提取URL，分别记为和。，其中，分别为、中第、条URL结果。计算、中相同URL的数目。由于2个概念同时提交搜索引擎进行检索的过程中，2概念的前后顺序会使得搜索结果有所不同，因此为提高准确率，本文提出2个概念的相对的正向和反向搜索概念。定义1 正向搜索：将概念和按照“先后”的顺序同时提交给搜索引擎进行搜索。定义2 反向搜索：将概念和按照“先后”的顺序同时提交给搜索引擎进行搜索。将正向搜索结果的标题、摘要中出现、的次数分别记为，；将反向搜索结果的标题、摘要中出现、的次数分别记为，并记，中的较小者为，中的较小者为。则、之间的语用相似度为(5)其中，、为权重参数，且。由于对2个URL完全相同的要求过于严格，且不同的URL可能反映相同的内容，因而其对语用相似度的贡献相对较小，令其参数。根据概念提交后的返回结果中标题、摘要出现在可用信息中的概率与2个URL相同概率的比值，设置经验值，。3.3 字面相似度计算本文参照GLUE系统11中的方法，将本体概念树中根结点到当前结点所有概念的名称串联起来构成当前结点的全称，通过对全称中概念名称的个数进行统计分析，计算概念的字面相似度。图1为2个本体片段的概念树状结构，其中，概念“A”的全称为“X0/ X2/ X3/ A”。假设、分别为概念、的全称，、中相同概念名称的数目为，各自包含概念名称的数目分别为、，则、之间字面相似度的计算公式如下(6)图1 本体(片断)概念树状结构示例图由于在本体概念树中，越是靠近树底层的概念，其表达的含义越具体，而越是靠近树顶层的概念，其表达的含义越模糊，因此即使2个概念的全称完全一致，其真正相似的程度也因其所处的深度不同而存在差异。而式(6)并未将此考虑在内。本文将利用权重设置的方式解决此问题，概念所处的位置越深，即距离根结点越远，令其权重越大。本文设置概念的全称中第个概念名称的权重为(7)则以为原概念，以为目标概念的二者相似度可用式(8)计算(8)其中，当中的第个概念名称在中找到相同的名称时，=1；否则=0。另外，若2个概念、在各自的本体树中所处的深度不同，则计算时会因二者在式(8)中的顺序差异而出现不同的结果值。因此，本文对其进行双向比较以达到计算结果的一致性，得到字面相似度计算方法如下：(9)计算结果与概念树的深度有关，概念树越深，其字面相似度越精确。3.4 综合相似度计算根据上述对概念的语义、语用以及字面相似度的计算，本节综合概念多层面的信息，提出概念、的综合相似度计算如式(10)所示：(10)其中，、分别为权重参数，且 。从测算实验中可知，三者对综合相似度的作用依次递减，且语义在概念比较时起绝对主导作用，因此本文根据反复测算经验赋予3个参数经验值分别为：，。在使用式(10)的算例验证中发现，如果语义相似度非常小，但字面相似度或者语用相似度比较大，将导致整体的相似度仍然比较大的不合理现象，因此需要对式(10)进行修正。由于主要部分的相似度值对于次要部分的相似度值起制约作用，如果主要部分相似度值比较低，那么次要部分的相似度对于整体相似度而言所起到的作用也会降低9。因此，本文将最终的综合相似度计算式修正如下：(11)为使式(11)计算效果达到最佳，本文进行了反复测算实验，并最终赋予参数经验值分别为：，。综合相似度计算方法考虑了概念的语义、语用、字面等多个层面的信息，对概念的描述更加详细，因此可以预期其具有更好的相似度计算精度，但与此同时，计算复杂性有所增加。从式(11)对3种相似度计算方法进行综合的过程可以看出，综合相似度计算方法的复杂度，是基于语义、语用、字面信息进行相似度计算的3种方法复杂度的乘积。4 实验结果及讨论4.1 实验结果对于概念间相似度计算结果的评价，目前还没有一个通用的标准。理想的方法是将其放在一个实际的应用系统中，通过对系统性能的影响来对不同的相似度计算方法进行评估，但这需要一个完整的系统来支持。由于基于本体的智能信息检索系统尚处于研究阶段，还未形成成熟的实际应用系统，而智能信息检索的目的是为了检索到与人类主观意识相一致的信息，因此，目前学者一般采用人类主观判断的结果作为衡量标准对相似度计算方法进行评价。由于本文的概念相似度计算方法是针对本体中的概念进行计算，且计算过程与本体结构有密切关系，因此选取了2个已经构建好的描述大学及其内部活动信息的公用本体作为测试集进行实验。其中一个来自于美国利哈伊大学网站，包含12个子结点，32个叶结点12；另一个来自于美国马里兰大学网站，包含15个子结点，37个叶结点13。2个本体均以中文表示。本文对这2个本体中叶节点概念之间进行了两两比较，分别依据本文的算法，计算其语义相似度、语用相似度、字面相似度以及综合相似度，并与主观判断的结果进行比较。其中，是通过访问20个不同学历层次的人，使其对每对概念间的相似度进行主观判断，然后取平均值获得。以每对概念的各种相似度、以及的计算结果与的绝对差值作为语义、语用、字面以及综合相似度的计算误差。由于这2个本体中的某些概念如“学院”与“杂志”之间关联度很小，其相似度计算的实际意义不大，因此本文从中选取了20对有代表性的概念，对其各种相似度计算方法的结果进行展示，以说明算法的有效性，如表1所示。为了便于更加直观地观察各种相似度计算方法的精确度，本文依据表1中的数据绘制了上述4种方法的相似度计算误差折线图，如图2所示。表12个本体中20对概念的相似度计算结果序号本体1概念本体2概念1学院部门0.1390.5540.5690.1170.1570.0180.3970.4120.0402学院大学1.0000.6070.5690.8560.8890.1110.2820.3200.0333学院学会0.2560.6410.5690.2210.2350.0210.4060.3340.0144说明书期刊0.6150.5370.6340.5170.4890.1260.0480.1450.0285说明书杂志0.6150.6910.6340.5420.5280.0870.1630.1060.0146说明书书0.6150.5500.6340.5200.4980.1170.0520.1360.0227技术报告刊物文章0.6710.7220.6670.5990.5890.0820.1330.0780.0108会议论文实践论文0.6350.6530.5590.5510.6130.0220.0400.0540.0629指南期刊0.6150.5430.6340.5180.4860.1290.0570.1480.03210指南杂志0.6150.8480.6340.5680.4980.1170.3500.1360.07011指南书0.6150.5420.6340.5180.5180.0970.0240.1160.00012软件期刊0.2860.1780.6710.2140.2190.0670.0410.4520.00513软件会议论文0.1640.3880.5690.1310.1360.0280.2520.4330.00514软件书0.2860.2690.6710.2210.1960.0900.0730.4750.02515博士后讲师0.8750.5860.7330.7530.6960.1790.1100.0370.05716博士后领导0.7220.5540.7330.6150.5850.1370.0310.1480.03017博士后院长0.6670.6520.7190.5850.5690.0980.0830.1500.01618研究研究项目0.4420.6550.8250.3910.4270.0150.2280.3980.03619研究研究兴趣0.4230.6090.8250.3690.3860.0370.2230.4390.01720毕业课程课程0.6210.6480.8530.5500.5370.0840.1110.3160.013图2 4种相似度计算方法的误差比较从表1中的计算结果和图2的误差描述可以看出，几种不同的方法对概念进行相似度计算的结果各有差异，而综合相似度计算结果误差最小，最接近于人类主观判断的结果，其次是基于语义和语用的相似度计算方法，而字面相似度计算方法的性能最差。这说明综合了多层信息的计算方法的确提高了概念相似度计算的精度。另外，为了进一步判断上述方法与人类主观判断结果的吻合程度，本文借鉴文献14的思想，利用式(12)来计算本文方法与人类主观判断结果的兼容度。(12)其中，为实验中所用的概念对数目，和分别为本文计算方法和人类主观判断第对概念的相似度，为兼容度。本文结合实验数据，计算了根据综合相似度计算方法得到的概念相似度值与人类主观判断结果的兼容度为，而基于语义、语用和字面的方法兼容度分别仅为、。由此可见，综合了多层信息的概念相似度计算方法比基于单层信息的计算方法更加有效，且可以为用户所接受。4.2 讨论从上面的实验可以看出，综合了概念多层信息的相似度计算方法比基于单层信息的计算方法具有更高的精确度，也非常接近于人类主观判断的结果，因此更加适合于应用到智能信息检索系统中，但与此同时，对多层信息的综合计算也带来了额外的复杂性，使得计算效率上受到一定影响，这是需要进一步考虑的问题。本文的实验中，基于字面的相似度计算方法效果很不理想，这主要与本文选取的实验本体有关，目前某些领域本体的构建还没有形成统一的规范，特别是在不同的本体中，很可能存在对概念的分类不一致现象，且可能使用不同名称的概念来表达相同的内容，因此使得字面相似度计算方法在计算不同本体中的概念相似度时效果很不理想。尽管如此，从实验的结果可以看出，它对综合相似度的计算提供了必要的信息做出了一定的贡献。在以后的工作中可以通过选择合适的同义词表等途径来提高字面相似度的准确率。此外，本文的计算方法对各权重参数的赋值大都以经验值为主，其更加科学的赋值方法还有待进一步研究。5 结束语在基于本体的智能信息检索领域中，概念间相似度的计算起着重要作用。本文首先分析了现有基于概念单层信息的各种相似度计算方法，指出其不足之处并进行了一定的修正，在此基础上，综合了概念在语义、语用、字面等多个层面的信息，提出了一种新的概念相似度计算方法。本文选取了2个本体进行实验，计算了其叶子结点概念之间的相似度。由实验结果可以看出，与单一利用概念的语义、语用或字面信息的计算方法相比，本文的综合概念相似度计算方法具有更好的精度。它不会因为仅利用某一单层信息存在的缺陷影响最终结果，且与人类主观判断结果吻合度较高，表明了该方法的有效性，但同时也付出了计算复杂性有所提高的代价。下一步工作将考虑如何提高方法的效率以及对权重的科学赋值问题。另外，本文的方法可在分词、词语被标注成概念的基础上，通过计算概念相似度，进一步拓展用于计算短句、长句甚至段落之间的相似度，为文本识别等应用领域提供帮助。 参考文献：1LE D N, GOH A E S. Current practices in measuring ontological concept similarityA. Procceedings of Third International Conference on Semantics, Knowledge and GridC. China, 2007.266-269.2WU C W, DAI D M, WAN Y. Ontology concept similarity in semantic queryA. Proceedings of Fifth International Conference on Fuzzy Systems and Knowledge DiscoveryC. Jinan, China, 2008. 24-28.3XIAO M, ZHONG L, XIONG Q X. Semantic similarity between concepts based on OWL ontologiesA. Proceedings of Second International Workshop on Knowledge Discovery and Data MiningC. Moscow, Russia, 2009.749-752.4WEEDS J. The reliability of a similarity measureA. Proceedings of the 5th UK Special Interest Group for Computational LinguisticsC. Leeds, 2002. 33-42.5MONGE A E, ELKAN C P. The field-matching problem: algorithm and applicationsA. Proceedings of the Second Internet Conference on Knowledge Discovery and Data MiningC. Oregon, Portland,1996. 267-270.6CROUCH C J. An approach to the automatic construction of global thesauriJ. Information Processing and Management,1990,26(5): 629- 640.7TURNEY P D. Mining the web for synonyms: PMI-IR versus LSA on TOEFLJ. Lecture Notes in Computer Science,2001,2167: 491-502.8NIRENBURG S, DOMASHNEV C, GRANNES D J. Two approaches to matching in example-based machine translationA. Proceedings of TMI-93C. Kyoto, Japan,1993. 47-57.9刘群, 李素建. 基于知网的词汇语义相似度计算A. 第三届汉语词汇语义学研讨会论文集C. 2002. 59-76.LIU Q, LI S J. Calculation of semantic similarity based on HowNetA. Proceedings of the Third Workshop on Chinese SemanticsC. 2002. 59-76.10章成志. 基于多层特征的字符串相似度计算模型J. 情报学报, 2005, 24(6): 696-701.ZHANG C Z, ZHENG C H, Passi K. A model for chinese string similarity based on multi-level featuresJ. Journal of the China Society for Scientific and Technical Information, 2005, 24(6):696-701.11DOAN A H, MADHAVAN J, DOMINGOS P. Learning to map between ontologies on the semantic WebA. Proceedings of the 11th InTernational Conference on World Wide WebC. New York, USA, 2002. 662-673.12An university ontology for benchmark testsEB/OL. http:/www. lehigh. edu/zhp2/2004/ 0401/univ-bench.owl.13An university ontology for testsEB/OL. /projects/ plus/DAML/onts/univ1.0.daml.14徐德智, 郑春卉, PASSI K. 基于SUMO的概念语义相似度研究J. 计算机应用,2006, 26(1):180-183.XU D Z, ZHENG C H, PASSI K. Concept semantic similarity research based on SUMOJ. Journal of Computer Applications, 2006, 26(1):180-183.作者简介：赵欢（1967-），女，湖南长沙人，湖南大学博士生、教授，主要研究方向为智能信息处理、语音信息处理、嵌入式系统设计等。李仁发（1957-），男，湖南宜章人，湖南大学教授、博士生导师，主要研究方向为智能信息处理、嵌入式计算、无线网络等。王家琴（1981-），女，山东烟台人，湖南大学硕士生，主要研究方向为智能信息处理。张在美（1981-），女，山东临沂人，湖南大学硕士生，主要研究方向为智能信息处理。（上接第134页）13GANESAN D, GREENSTEIN B, PERELYUBSKIY D, et al. Multi-resolution storage and search in sensor networksJ. ACM Transac