论文部分内容阅读
摘要：不同本体之间的交互成为语义Web的首要任务，其中本体相似度计算是本体映射的关健环节。在以往的研究中，本体相似度计算通常专注于模式及其结构的匹配。目前研究朝着进一步考虑本体内部语义信息方向努力。本文描述了语义相似度栈的各个层次，依据各个层次的语义特征对目前本体相似度方法进行分类，并对每种方法进行了详细描述。最后对现有一些主要的本体间相似度计算方法进行归纳总结。这项研究工作将为人们提出新的相似度方法或者组合的计算方法作一个参考。
关键词：方法；相似度；本体；语义Web
中图分类号：TP601文献标识码：A文章编号：1009-3044(2007)06-11609-03
1 引言
近年来，本体已经成为语义Web、人工智能、数据集成、信息检索等研究领域的热门课题。本体映射解决不同本体间的知识共享和重用问题，而本体相似度是本体映射的关键环节[1]。在本体相似度的研究中，已经有很多文献提出了多种计算方法，有的基于语言语法的相似性，有的基于本体结构的相似性，有的计算实体类的相似度，有的利用启发规则等等。目前的本体相似技术主要是针对两个异构本体间的相似性进行计算，还需要进一步考虑本体中语义关系的相似性，才能够实现更加精确的本体映射，满足基于语义Web的信息检索技术对本体相似度计算的需求。
本文首先对本体相似度的一些基本问题予以说明，并描述了语义相似度栈的各个层次。文章对目前本体相似度计算方法进行了分类，并对每种方法进行了详细描述。
2 本体及本体相似度基本概念
2.1本体
本体最初是一个哲学概念，用来描述事物的本质。在计算机科学领域，本体被定义为共享概念模型的形式化规范说明[2]。
本体简单形式化定义为：
O=(C,HC,RC,HR,I,RI,A)
本体包含以下：概念C包含于层次结构HC中。两个独立的概念之间存在关系RC。关系（属性）处于层次结构HR中。实例I是特殊化概念，由属性实例RI关联。另外，可以定义公理A用来引用其余已有的知识。描述本体的通用语言是RDFS或者OWL，它们提供不同的模型构造子，因而体现了不同复杂度。
2.2本体相似度
形式化定义本体相似度如下：
本体相似度计算是以一定的粒度为基础的，如以概念为粒度，则两个本体之间的相似度，是由两个本体内部概念之间配对相似度来决定的。两个不同本体的概念组成的概念对之间的相似度，除了与概念自身的属性有关系外，还与概念在自身的本体中所处的上下文环境有很大的关系。从本体本身来说，本体相似涉及到本体的所有概念（如类、实例、属性等）和概念之间的关系，计算本体相似度一定要以概念相似度为基础。
3 本体相似度计算方法
3.1相似度栈
参照语义Web层次图[3]，从整体上相似度计算可以看作是一个相似度栈[4]，分别为实体（Entities）、语义网络（Semantic Nets）、描述逻辑（Description Logics）、约束（Restrictions）、规则（Rules）五层。左边显示它们语义复杂度从下到上逐渐增强。右边是特殊共享的领域本体，从上到下覆盖了所有层次，可以位于相似度栈的任一层次。
图1相似度栈
相似度栈层次结构从下到上描述如下：
实体：描述实体的第一层，不需要考虑任意语义信息，基本专注于语言语法的比较。标签（labels）是实体的标识名称。
语义网络：包含许多概念的语义网络蕴含着大量背景信息，包含一些复杂的关系。一个概念是对象的通用类，它们通过特征（attributes）和属性（properties）和其它概念关联。
描述逻辑：体现了描述逻辑表示的本体复杂性，包含了原子概念的类型以及与其它原子概念的关系，主要是从构成本体的描述逻辑的语法的角度出发来考虑。
约束：本体使用约束以更精确的表达知识，如OWL本体语言[5]。在OWL语言中，有属性如：sameIndividualAs或者sameClassAs。这很明确的表明了相似性，也可以从属性衍生出新规则来决定相似性。
规则：本体中的高层。越来越影响相似度的计算，特别是在实体之间存在相似规则，这些实体将会被认为相似。
特定应用字典：可以明确定义特定应用字典用来考虑相似度。
3.2相似度计算方法
在相似度栈的各个层次中，依据各个层次的语义特征，有不同的相似度计算方法，而本体相似度的计算通常是组合了各个层次中的不同计算方法综合而成。
3.2.1相似度栈各个层次的相似度计算方法
实体层的相似度计算方法
从语法的角度[6]。通过字符串匹配以及字符串之间的编辑距离来计算相似值，没有考虑概念的语义映射关系。文献[7]中的Levenshtein distance算法计算字符串之间（后来扩展到语句）的相似度。编辑距离（Edit distance）为字符串转换所需的最小数目的单元编辑操作，包括字符的插人、删除、替换及相邻字符的调换
从词义或者自然语言的角度。在比较两个实体的时候比较两个实体是否为同义词以及词义相近程度，这通常需要借鉴与WordNet 类似的特定应用字典的帮助来完成。如文献[8][9]中基于WordNet知识库评估语义相似度
语义网络层的相似度计算方法
从本体的结构或者本体构造的图或树的角度。在实体层相似度计算基础上，参考了概念间的层次结构，如结点关系(父结点、子结点、孙子结点)、语义邻居关系等等。由于结点的层次关系中蕴涵了大量的潜在语义，在很多的相似度计算方法中都利用了这些信息。
文献[9]中采用信息理论方法评估语义相似度，通过计算包含相同子孙结点的概率值比较两个对象之间的相似度。
文献[10]采用本体距离（Ontology distance）方法，利用两个结点通过共有祖先的最短路径或者连接两个结点的共有后代的通用最短路径来计算相似性。此方法高度依赖于本体的构建，适用于同一本体内的语义相似计算。
文献[11]的映射方法中，首先计算结点本身的基距离，然后参考了语义关系，分别计算父结点、子结点、孙子结点的基距离并把它们加权平均得到一对结点的语义距离。
文献[8]中的方法不仅考虑结构中的上下位关系，而且考虑整体部分关系。但因为涉及到容易导致循环比较的问题，所以计算复杂度比较高。
描述逻辑和约束层的相似度计算方法
原子概念的类型以及与其它原子概念的关系，这主要是从构成本体的描述逻辑的语法角度出发，这些方法考虑到不同本体特殊化和形式化的不同水平。如文献[12]中M. Andrea Rodriguez和Max J.Egenhofer提出了一种利用概念定义计算概念间相似度的方法，利用同义词集、语义相邻函数和不同概念特征这3个部分相应进行匹配，比较来自不同本体的概念，得到3个相似度值S1、S2、S3，然后3个值加权平均得到两个概念的语义相似度
规则层的相似度计算方法
基于规则的方法。在本体相似计算中定义了一些启发式规则，规则的抽取来自于概念的定义和结构信息，由领域专家手工定义，如“如果两个概念的属性相同，那么这两个概念是等价的”、“如果这两个概念的子概念都相同，那么这两个概念是相似的”等等。
文献[4]中，对于一对概念ei j 和ei j 根据每条规则计算得到一个相似值Sim(ei j ,ei j)，然后用集成的方法把根据各个规则得到的相似度进行综合。这里确定每个规则的相似度的权重方法有S型函数法和基于神经网络的机器学习法。这样可以根据下面的公式计算得到一对概念ei j 和ei j 的相似度：
文献[13]中以ACM和ITTALKS两个本体为例进行映射实验时采用了启发式方法，其思想是：一个结点的子结点与另一结点映射的百分比能反映该结点与另一结点的映射关系。
还有一些典型的计算方法，可以用于相似度栈的任意层次。
统计学的方法。在本体映射过程中采用了统计学中的方法，如文献[13]采用的贝叶斯方法和GLUE系统[6]在计算概念实例的联合分布概率时的统计方法。
机器学习方法[14]。如GLUE系统通过机器学习对概念的实例进行分类，使用联合概率分布为基础计算相似性,然后采用多策略的机器学习方法来建立相似矩阵,最后利用专家给出的领域约束来半自动地创建本体之间的语义映射。这种方法基本上只利用了本体中的实例数据,因而当实例数据较多时更为有效
特征匹配方法[15]，在概念或者概念实体中使用通用和不同的特征来计算语义相似度，适合于不同本体间的语义相似计算
3.2.2不同方法的组合
实际上，为了提高相似度的精确性，本体相似度算法往往不是一个单一的方法，而是上述各种方法和技术的组合。组合的方式有两种：混合方式集成了多种标准，复合方式则合并各个独立执行的计算方法的结果。
混合方式在计算过程中采用多个标准。和多个计算方法的单独执行比较起来，可以提供更好的候选结果和更好的性能。由于仅符合一种标准的候选结果可以在早期被排除，以及在计算过程中要综合考虑多种标准，混合方式效率更高。
复合方式则把几个独立执行的匹配方法的结果合并起来。这种合并方法的能力使它比混合方法具有更大的灵活性。
下面，我们介绍一些主要的本体相似度方法。
4 相关工作介绍及其比较
Cupid方法[16]是微软研究院J.Madhavan等人实现的一个通用的模式匹配方法，该方法结合了语言和结构方面的模式匹配技术，输入的模式首先表示为一个图，然后自顶向下和自底向上相结合进行遍历该图。整个过程分为三个阶段，分别为语言相似度计算、结构相似性计算和映射生成。Cupid方法适用于数据库模式匹配。
S-Match[17]算法是基于模式的匹配系统，基于WordNet知识库，采用SAT方法，处理树型结构的映射（如等级层次或概念层次结构），分解图（树）匹配问题为结点集合匹配问题，匹配具有相似语义的概念，返回语义关系（如等价关系、包含关系）。该算法目前仅仅可以处理树型结构，虽然采用SAT方法，带有一定的语义性，但由于该方法表达性的限制，只能处理一元谓词，不能处理二元谓词，如属性、角色。
SF[18]中对输入图的结点使用字符串匹配方法，进行迭代计算，直至达到一个收敛点。该算法仅仅覆盖了部分的本体定义，而不能处理循环定义的本体。
COMA[19]也是一个合成的模式匹配工具，和Cupid相比具有更复杂的结构，而且处理过程中有可能反复运算。系统提供了匹配算法的扩展库，方法大部分基于字符串的技术和Cupid中采用的一些方法。COMA与GLUE和SF系统相比具有绝对优势。
QOM[20]采取COMA中的合成匹配算法，基于规则元素的匹配，改善了匹配算法的有效性，从而快速匹配相似元素。
Anchor-PROMPT系统[21]是本体合成和本体装配的工具，采用了复杂的敏捷机制匹配可能的元素。它是混合的装配算法，输入是两个本体（内部表示为图）及其相关词汇的关系配对集合（可以用编辑距离算法来识别），分析输入本体的内部路径，从而决定词汇在相似路径上相似位置的出现频率。最后基于频率和用户反馈决定匹配候选集。
OLA[22]充分利用了所有的元素级匹配技术，除了语义技术。OLA算法基于距离函数，所有的输入结构距离的定义转化为一组等式，这些距离都是线性的，然后寻找本体概念间的最短距离。采用了基距离算法计算不同标签及其数据类型的距离，使用固定点迭代算法直至达到一个收敛点。
表1 本体相似度算法的比较
5 总结
本体是对领域知识概念的抽象和描述，其目的是为了信息共享和软件重用，针对本体的操作如合并、比较、映射、扩展等都依赖于本体之间相似度的计算。本体相似度计算已经成为本体研究领域的重要课题。
目前已经提出的本体相似度计算方法有很多，大多数是采用多种计算标准的组合方法，可以挖掘多方面的本体信息，提高相似度的准确性。现有方法大多数是基于语言语法和模式信息，而未充分考虑本体内包含的语义信息。该文对目前本体相似度计算方法进行了分类，并对每种方法进行了详细描述。总结语义Web中知识处理的核心问题本体相似的现状，将有助于这方面的研究，为人们提出新的相似度方法或者组合的计算方法作一个参考。
参考文献：
[1]Jérome Euzenat. State of the art on current alignment techniques.IST Knowledge Web Network of Excellence FP6-507482, 12/2004, Deliverable #KWEB/2004/D2.2.3.
[2]Hendler J. Ontologies on the Semantic Web. IEEE Intelligent Systems, 2002, 17(2): pp 73-74.
[3]T. Berners-Lee, J. Hendler, O. Lassila. The Semantic Web. Scientific American, 2001, 284(5): pp 34-43.
[4]Marc Ehrig, York Sure. Ontology Mapping - An Integrated Approach. ESWS 2004, pp 76-91.
[5]OWL Web Ontology Language Reference, W3C Recommendation 10 February 2004, available at:
http://www.w3.org/TR/2004/REC-owl-ref-20040210/
[6]AnHai Doan, Jayant Madhavan, Pedro Domingos, et al. Learning to map between ontologies on the semantic web. WWW 2002, pp 662-673.
[7]I. V. Levenshtein. Binary Codes capable of correcting deletions, insertions, and reversals. Cybernetics and Control Theory, 1966, 10(8): pp 707-710.
[8]R. Richardson, A. F. Smeaton, J. Murphy. Using WordNet as knowledge base for measuring semantic similarity between words. Technical Report CA-1294, Dublin City University, School of Computer Applications, 1994.
[9]Resnik, Philip. Semantic Similarity in a Taxonomy: An Information-based Measure and its Application to Problems of Ambiguity in Natural Language, Journal of Artificial Intelligence, 1999, pp 95-130.
[10]Abraham Bernstein, Esther Kaufmann, Christoph Buerki, et al. How Similar Is It? Towards Personalized Similarity Measures in Ontologies. Wirtschaftsinformatik, 2005, pp 1347-1366.
[11]Satoshi Sekine, Kiyoshi Sudo, Takano Ogino. Statistical Matching of Two Ontologies[C]. In: Proceedings of the SIGLEX99: Standerdizing Lexical Resources, Maryland, USA, 1999, pp 69-73.
[12]M. Andrea Rodriguez, Max J. Egenhofer. Determining semantic similarity among entity classes from different ontologies. IEEE Transaction on Knowledge and Data Engineering 2003, 15(2): pp 442–456.
[13]Sushama Prasad et al. A Tool For Mapping Between Two Ontologies Using Explicit Information[C]. In: Proceedings of AAMAS 2002 Workshop on Ontologies and Agent System, 2002.
[14]AnHai D., Jayant M., Pedro D., Alon H. Ontology matching: A machine learning approach. In: Steffen S., Rudi S, eds. Handbook on Ontologies in Information Systems, Heidelberg,DE:Springer-Verlag, 2003, pp 397-416.
[15]A. Tversky. Features of Similarity. Psychological Review, 1977, 84(4): pp 327-352.
[16]Jayant Madhavan, Philip A. Bernstein, Erhard Rahm. Generic Schema Matching with Cupid. VLDB 2001, pp 49-58.
[17]Fausto Giunchiglia, Pavel Shvaiko, Mikalai Yatskevich. S-Match: an Algorithm and an Implementation of Semantic Matching. ESWS 2004, pp 61-75.
[18]Sergey Melnik, Hector Garcia-Molina, Erhard Rahm. Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching. ICDE 2002, pp 117-128.
[19]Hong Hai Do, Erhard Rahm. COMA - A System for Flexible Combination of Schema Matching Approaches. VLDB 2002, pp 610-621.
[20]Marc Ehrig, Steffen Staab. QOM - Quick Ontology Mapping. International Semantic Web Conference 2004, pp 683-697.
[21]N. F. Noy, M. A. Musen. Anchor-PROMPT: Using NonLocal Context for Semantic Matching. In: Proceedings of the Workshop on Ontologies and Information Sharing at the 17th International Joint Conference on Artificial Intelligence (IJCAI), Seattle, WA, 2001, pp 63-70.
[22]Jérome Euzenat, Petko Valtchev. Similarity-Based Ontology Alignment in OWL-Lite. ECAI, 2004, pp 333-337.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：方法；相似度；本体；语义Web
中图分类号：TP601文献标识码：A文章编号：1009-3044(2007)06-11609-03
1 引言
近年来，本体已经成为语义Web、人工智能、数据集成、信息检索等研究领域的热门课题。本体映射解决不同本体间的知识共享和重用问题，而本体相似度是本体映射的关键环节[1]。在本体相似度的研究中，已经有很多文献提出了多种计算方法，有的基于语言语法的相似性，有的基于本体结构的相似性，有的计算实体类的相似度，有的利用启发规则等等。目前的本体相似技术主要是针对两个异构本体间的相似性进行计算，还需要进一步考虑本体中语义关系的相似性，才能够实现更加精确的本体映射，满足基于语义Web的信息检索技术对本体相似度计算的需求。
本文首先对本体相似度的一些基本问题予以说明，并描述了语义相似度栈的各个层次。文章对目前本体相似度计算方法进行了分类，并对每种方法进行了详细描述。
2 本体及本体相似度基本概念
2.1本体
本体最初是一个哲学概念，用来描述事物的本质。在计算机科学领域，本体被定义为共享概念模型的形式化规范说明[2]。
本体简单形式化定义为：
O=(C,HC,RC,HR,I,RI,A)
本体包含以下：概念C包含于层次结构HC中。两个独立的概念之间存在关系RC。关系（属性）处于层次结构HR中。实例I是特殊化概念，由属性实例RI关联。另外，可以定义公理A用来引用其余已有的知识。描述本体的通用语言是RDFS或者OWL，它们提供不同的模型构造子，因而体现了不同复杂度。
2.2本体相似度
形式化定义本体相似度如下：
本体相似度计算是以一定的粒度为基础的，如以概念为粒度，则两个本体之间的相似度，是由两个本体内部概念之间配对相似度来决定的。两个不同本体的概念组成的概念对之间的相似度，除了与概念自身的属性有关系外，还与概念在自身的本体中所处的上下文环境有很大的关系。从本体本身来说，本体相似涉及到本体的所有概念（如类、实例、属性等）和概念之间的关系，计算本体相似度一定要以概念相似度为基础。
3 本体相似度计算方法
3.1相似度栈
参照语义Web层次图[3]，从整体上相似度计算可以看作是一个相似度栈[4]，分别为实体（Entities）、语义网络（Semantic Nets）、描述逻辑（Description Logics）、约束（Restrictions）、规则（Rules）五层。左边显示它们语义复杂度从下到上逐渐增强。右边是特殊共享的领域本体，从上到下覆盖了所有层次，可以位于相似度栈的任一层次。
图1相似度栈
相似度栈层次结构从下到上描述如下：
实体：描述实体的第一层，不需要考虑任意语义信息，基本专注于语言语法的比较。标签（labels）是实体的标识名称。
语义网络：包含许多概念的语义网络蕴含着大量背景信息，包含一些复杂的关系。一个概念是对象的通用类，它们通过特征（attributes）和属性（properties）和其它概念关联。
描述逻辑：体现了描述逻辑表示的本体复杂性，包含了原子概念的类型以及与其它原子概念的关系，主要是从构成本体的描述逻辑的语法的角度出发来考虑。
约束：本体使用约束以更精确的表达知识，如OWL本体语言[5]。在OWL语言中，有属性如：sameIndividualAs或者sameClassAs。这很明确的表明了相似性，也可以从属性衍生出新规则来决定相似性。
规则：本体中的高层。越来越影响相似度的计算，特别是在实体之间存在相似规则，这些实体将会被认为相似。
特定应用字典：可以明确定义特定应用字典用来考虑相似度。
3.2相似度计算方法
在相似度栈的各个层次中，依据各个层次的语义特征，有不同的相似度计算方法，而本体相似度的计算通常是组合了各个层次中的不同计算方法综合而成。
3.2.1相似度栈各个层次的相似度计算方法
实体层的相似度计算方法
从语法的角度[6]。通过字符串匹配以及字符串之间的编辑距离来计算相似值，没有考虑概念的语义映射关系。文献[7]中的Levenshtein distance算法计算字符串之间（后来扩展到语句）的相似度。编辑距离（Edit distance）为字符串转换所需的最小数目的单元编辑操作，包括字符的插人、删除、替换及相邻字符的调换
从词义或者自然语言的角度。在比较两个实体的时候比较两个实体是否为同义词以及词义相近程度，这通常需要借鉴与WordNet 类似的特定应用字典的帮助来完成。如文献[8][9]中基于WordNet知识库评估语义相似度
语义网络层的相似度计算方法
从本体的结构或者本体构造的图或树的角度。在实体层相似度计算基础上，参考了概念间的层次结构，如结点关系(父结点、子结点、孙子结点)、语义邻居关系等等。由于结点的层次关系中蕴涵了大量的潜在语义，在很多的相似度计算方法中都利用了这些信息。
文献[9]中采用信息理论方法评估语义相似度，通过计算包含相同子孙结点的概率值比较两个对象之间的相似度。
文献[10]采用本体距离（Ontology distance）方法，利用两个结点通过共有祖先的最短路径或者连接两个结点的共有后代的通用最短路径来计算相似性。此方法高度依赖于本体的构建，适用于同一本体内的语义相似计算。
文献[11]的映射方法中，首先计算结点本身的基距离，然后参考了语义关系，分别计算父结点、子结点、孙子结点的基距离并把它们加权平均得到一对结点的语义距离。
文献[8]中的方法不仅考虑结构中的上下位关系，而且考虑整体部分关系。但因为涉及到容易导致循环比较的问题，所以计算复杂度比较高。
描述逻辑和约束层的相似度计算方法
原子概念的类型以及与其它原子概念的关系，这主要是从构成本体的描述逻辑的语法角度出发，这些方法考虑到不同本体特殊化和形式化的不同水平。如文献[12]中M. Andrea Rodriguez和Max J.Egenhofer提出了一种利用概念定义计算概念间相似度的方法，利用同义词集、语义相邻函数和不同概念特征这3个部分相应进行匹配，比较来自不同本体的概念，得到3个相似度值S1、S2、S3，然后3个值加权平均得到两个概念的语义相似度
规则层的相似度计算方法
基于规则的方法。在本体相似计算中定义了一些启发式规则，规则的抽取来自于概念的定义和结构信息，由领域专家手工定义，如“如果两个概念的属性相同，那么这两个概念是等价的”、“如果这两个概念的子概念都相同，那么这两个概念是相似的”等等。
文献[4]中，对于一对概念ei j 和ei j 根据每条规则计算得到一个相似值Sim(ei j ,ei j)，然后用集成的方法把根据各个规则得到的相似度进行综合。这里确定每个规则的相似度的权重方法有S型函数法和基于神经网络的机器学习法。这样可以根据下面的公式计算得到一对概念ei j 和ei j 的相似度：
文献[13]中以ACM和ITTALKS两个本体为例进行映射实验时采用了启发式方法，其思想是：一个结点的子结点与另一结点映射的百分比能反映该结点与另一结点的映射关系。
还有一些典型的计算方法，可以用于相似度栈的任意层次。
统计学的方法。在本体映射过程中采用了统计学中的方法，如文献[13]采用的贝叶斯方法和GLUE系统[6]在计算概念实例的联合分布概率时的统计方法。
机器学习方法[14]。如GLUE系统通过机器学习对概念的实例进行分类，使用联合概率分布为基础计算相似性,然后采用多策略的机器学习方法来建立相似矩阵,最后利用专家给出的领域约束来半自动地创建本体之间的语义映射。这种方法基本上只利用了本体中的实例数据,因而当实例数据较多时更为有效
特征匹配方法[15]，在概念或者概念实体中使用通用和不同的特征来计算语义相似度，适合于不同本体间的语义相似计算
3.2.2不同方法的组合
实际上，为了提高相似度的精确性，本体相似度算法往往不是一个单一的方法，而是上述各种方法和技术的组合。组合的方式有两种：混合方式集成了多种标准，复合方式则合并各个独立执行的计算方法的结果。
混合方式在计算过程中采用多个标准。和多个计算方法的单独执行比较起来，可以提供更好的候选结果和更好的性能。由于仅符合一种标准的候选结果可以在早期被排除，以及在计算过程中要综合考虑多种标准，混合方式效率更高。
复合方式则把几个独立执行的匹配方法的结果合并起来。这种合并方法的能力使它比混合方法具有更大的灵活性。
下面，我们介绍一些主要的本体相似度方法。
4 相关工作介绍及其比较
Cupid方法[16]是微软研究院J.Madhavan等人实现的一个通用的模式匹配方法，该方法结合了语言和结构方面的模式匹配技术，输入的模式首先表示为一个图，然后自顶向下和自底向上相结合进行遍历该图。整个过程分为三个阶段，分别为语言相似度计算、结构相似性计算和映射生成。Cupid方法适用于数据库模式匹配。
S-Match[17]算法是基于模式的匹配系统，基于WordNet知识库，采用SAT方法，处理树型结构的映射（如等级层次或概念层次结构），分解图（树）匹配问题为结点集合匹配问题，匹配具有相似语义的概念，返回语义关系（如等价关系、包含关系）。该算法目前仅仅可以处理树型结构，虽然采用SAT方法，带有一定的语义性，但由于该方法表达性的限制，只能处理一元谓词，不能处理二元谓词，如属性、角色。
SF[18]中对输入图的结点使用字符串匹配方法，进行迭代计算，直至达到一个收敛点。该算法仅仅覆盖了部分的本体定义，而不能处理循环定义的本体。
COMA[19]也是一个合成的模式匹配工具，和Cupid相比具有更复杂的结构，而且处理过程中有可能反复运算。系统提供了匹配算法的扩展库，方法大部分基于字符串的技术和Cupid中采用的一些方法。COMA与GLUE和SF系统相比具有绝对优势。
QOM[20]采取COMA中的合成匹配算法，基于规则元素的匹配，改善了匹配算法的有效性，从而快速匹配相似元素。
Anchor-PROMPT系统[21]是本体合成和本体装配的工具，采用了复杂的敏捷机制匹配可能的元素。它是混合的装配算法，输入是两个本体（内部表示为图）及其相关词汇的关系配对集合（可以用编辑距离算法来识别），分析输入本体的内部路径，从而决定词汇在相似路径上相似位置的出现频率。最后基于频率和用户反馈决定匹配候选集。
OLA[22]充分利用了所有的元素级匹配技术，除了语义技术。OLA算法基于距离函数，所有的输入结构距离的定义转化为一组等式，这些距离都是线性的，然后寻找本体概念间的最短距离。采用了基距离算法计算不同标签及其数据类型的距离，使用固定点迭代算法直至达到一个收敛点。
表1 本体相似度算法的比较
5 总结
本体是对领域知识概念的抽象和描述，其目的是为了信息共享和软件重用，针对本体的操作如合并、比较、映射、扩展等都依赖于本体之间相似度的计算。本体相似度计算已经成为本体研究领域的重要课题。
目前已经提出的本体相似度计算方法有很多，大多数是采用多种计算标准的组合方法，可以挖掘多方面的本体信息，提高相似度的准确性。现有方法大多数是基于语言语法和模式信息，而未充分考虑本体内包含的语义信息。该文对目前本体相似度计算方法进行了分类，并对每种方法进行了详细描述。总结语义Web中知识处理的核心问题本体相似的现状，将有助于这方面的研究，为人们提出新的相似度方法或者组合的计算方法作一个参考。
参考文献：
[1]Jérome Euzenat. State of the art on current alignment techniques.IST Knowledge Web Network of Excellence FP6-507482, 12/2004, Deliverable #KWEB/2004/D2.2.3.
[2]Hendler J. Ontologies on the Semantic Web. IEEE Intelligent Systems, 2002, 17(2): pp 73-74.
[3]T. Berners-Lee, J. Hendler, O. Lassila. The Semantic Web. Scientific American, 2001, 284(5): pp 34-43.
[4]Marc Ehrig, York Sure. Ontology Mapping - An Integrated Approach. ESWS 2004, pp 76-91.
[5]OWL Web Ontology Language Reference, W3C Recommendation 10 February 2004, available at:
http://www.w3.org/TR/2004/REC-owl-ref-20040210/
[6]AnHai Doan, Jayant Madhavan, Pedro Domingos, et al. Learning to map between ontologies on the semantic web. WWW 2002, pp 662-673.
[7]I. V. Levenshtein. Binary Codes capable of correcting deletions, insertions, and reversals. Cybernetics and Control Theory, 1966, 10(8): pp 707-710.
[8]R. Richardson, A. F. Smeaton, J. Murphy. Using WordNet as knowledge base for measuring semantic similarity between words. Technical Report CA-1294, Dublin City University, School of Computer Applications, 1994.
[9]Resnik, Philip. Semantic Similarity in a Taxonomy: An Information-based Measure and its Application to Problems of Ambiguity in Natural Language, Journal of Artificial Intelligence, 1999, pp 95-130.
[10]Abraham Bernstein, Esther Kaufmann, Christoph Buerki, et al. How Similar Is It? Towards Personalized Similarity Measures in Ontologies. Wirtschaftsinformatik, 2005, pp 1347-1366.
[11]Satoshi Sekine, Kiyoshi Sudo, Takano Ogino. Statistical Matching of Two Ontologies[C]. In: Proceedings of the SIGLEX99: Standerdizing Lexical Resources, Maryland, USA, 1999, pp 69-73.
[12]M. Andrea Rodriguez, Max J. Egenhofer. Determining semantic similarity among entity classes from different ontologies. IEEE Transaction on Knowledge and Data Engineering 2003, 15(2): pp 442–456.
[13]Sushama Prasad et al. A Tool For Mapping Between Two Ontologies Using Explicit Information[C]. In: Proceedings of AAMAS 2002 Workshop on Ontologies and Agent System, 2002.
[14]AnHai D., Jayant M., Pedro D., Alon H. Ontology matching: A machine learning approach. In: Steffen S., Rudi S, eds. Handbook on Ontologies in Information Systems, Heidelberg,DE:Springer-Verlag, 2003, pp 397-416.
[15]A. Tversky. Features of Similarity. Psychological Review, 1977, 84(4): pp 327-352.
[16]Jayant Madhavan, Philip A. Bernstein, Erhard Rahm. Generic Schema Matching with Cupid. VLDB 2001, pp 49-58.
[17]Fausto Giunchiglia, Pavel Shvaiko, Mikalai Yatskevich. S-Match: an Algorithm and an Implementation of Semantic Matching. ESWS 2004, pp 61-75.
[18]Sergey Melnik, Hector Garcia-Molina, Erhard Rahm. Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching. ICDE 2002, pp 117-128.
[19]Hong Hai Do, Erhard Rahm. COMA - A System for Flexible Combination of Schema Matching Approaches. VLDB 2002, pp 610-621.
[20]Marc Ehrig, Steffen Staab. QOM - Quick Ontology Mapping. International Semantic Web Conference 2004, pp 683-697.
[21]N. F. Noy, M. A. Musen. Anchor-PROMPT: Using NonLocal Context for Semantic Matching. In: Proceedings of the Workshop on Ontologies and Information Sharing at the 17th International Joint Conference on Artificial Intelligence (IJCAI), Seattle, WA, 2001, pp 63-70.
[22]Jérome Euzenat, Petko Valtchev. Similarity-Based Ontology Alignment in OWL-Lite. ECAI, 2004, pp 333-337.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。