论文部分内容阅读
[摘要]排序算法的好坏很大程度上影响了搜索引擎的用户体验，尤其是近些年随着语义检索技术的发展，使其检索和排序的对象不仅仅局限于文档和网页，更包括了实体和关系等。在对现有研究与应用调研的基础上，对当前语义检索研究进行了综述，并按照排序的阶段将其分为实体排序、关系排序和本体文档排序，并详细阐述了每种排序算法的研究进展，最后指出，将用户的社会网络因素同已有的排序算法相结合，是未来语义排序的发展趋势之一。
[关键词]语义检索；检索排序；本体；关系；实体
[中图分类号]G250
[文献标识码]A
[文章编号]1008-0821（2015）02-0159-06
搜索引擎最重要的任务是搜集网络信息，提供给用户与其检索词最匹配的结果，并返回相关链接。搜索引擎在网络上抓取足够的网页已不再是困难，困难在于如何将这些网页整理出来，选择合适的排序算法，把这些结果集返回给用户。语义网技术的出现，更加加剧了这种困境。语义网的宏观结构来源于RDF模型所定义的数据之间的链接，随着RDF数据大量涌入，传统搜索引擎更加凸显出局限性，因此语义搜索引擎应运而生。由于语义检索的对象不再仅限于文档和网页，同时也包括了实体和关系等，所以在一定程度上对排序算法的要求变得更高。对于语义搜索引擎来说，一个合理的排序算法不仅可以帮助用户提高搜索效率，更是迈向可信语义网的至关重要的一步。从对现有研究与调研的基础上可以看出，目前针对本体文档的排序研究较多，已经形成了较为系统的分类排序算法体系，但针对实体和关系的排序的研究还在发展中。本文按照排序的阶段将语义检索排序分为实体排序、关系排序和文档排序，并详细阐述了每种排序算法的研究进展，供今后研究人员参考。
1 传统排序算法概述
传统搜索引擎的排序算法主要可以分为两类，分别是基于链接分析的方法和基于用户行为分析的方法，以及在此基础上进行改进的排序模型。其中基于链接分析的方法又可以分为PageRank算法、HITS算法、SALSA算法等；基于用户行为分析的方法可以分为BrownseRank和Direct Hit算法等；一些在此基础上改进的排序算法包括基于节点和边属性的排序算法、基于监督学习的排序算法等。随着语义网的发展，本体数量与日俱增，本体模型在语义网上被广泛地应用，传统的基于关键词的检索方法不能对本体中的语义关系进行很好的推理，而仅仅基于表述逻辑对本体进行检索，因而用户满意度并不高，也无法取得很好的排序结果。与此同时，一些研究将传统的排序算法应用于语义检索中，取得了一定的成果，但是由于本体结构的特殊性，目前相关研究仍在探索更加优化的排序算法，下文将详细介绍当前的研究现状和进展。
2 语义检索排序方法
当前按照排序的阶段可以将语义检索排序分为实体排序、关系排序和本体文档排序，但是这些排序方法之间是有很大交集的，并无严格的界限。
2.1实体排序
语义网中的定义/概念是为了描述现实中的实体数据，这些实体数据都将服务于资源的请求者，比如利用FOAF撰写的个人档案就是目前最常用的实体数据。语义网最初发展时，由于实体数据相对匮乏，因而并未引起足够的重视，近年来随着语义网的迅猛发展，大量类似于FOAF、RSS等实体数据的出现，加上实体排序本身就有着巨大的研究价值和商业价值，使得这个问题越来越受到研究者的关注，而且从实际的角度来讲，对于大多数一般用户而言，实体数据的检索需求更为普遍。实体排序问题的实质是对实体之间异质关联的分析方法，其排序的目的是从知识库中发现和检索与用户需求最匹配的实体对象，这种最匹配的实体对象一般称为种子实体（seed entity），排序的困难之处在于实体之间的关联异常的复杂，一些隐式关联很难被发现，推理过程不仅牵扯到描述逻辑（Description Logic）的推理规则，还需要使用语义网规则描述语言（SWRL）定义的规则，因此在对实体数据进行排序的过程中，如果想得到全面准确的排序结果，那么推理所起到的作用是不可忽略的。
W.Wei等人提出了针对特定领域的实体排序算法RareRank，其指出传统的信息检索模型主要依靠内容和链接分析评分来确定排序结果，即相关性分数（relevance）和质量分数（quality）。作者将这两种评分相结合，并在此基础上分配相应的参数来进行优化，并引入了合理搜索模型（Rational Research Model）。其首先将一个领域的知识利用有向图来表示，然后将领域本体引入到有向图中，因此该模型的排序分数整合了领域本体的相关性分数和链接分析的质量分数。这个方法实质是应用了链接分析来对实体进行排序，实证结果证明效果确实有一定改善，但是该模型的参数设置较为简单，将来还需要大量的数据集进行测试。L.Dali等人提出了Learning to Rank算法，其主要是采用查询词本身进行实体的优化排序，首先利用PageRank作为参考模型，并将其应用到RDF图中，并结合这些词的变化特点，进而获得更高的资源关联，最后计算出更好的排序结果。这种方法的本质是利用查询词自身特点的RDF图。相比一般的文本排序，该方法会产生较大的非连续性，尤其是在关联数据集（LOD）参与的情况下，很难具有较好的效果；X.Ning等提出了语义搜索排序框架RSS，这种算法一方面利用关系（relations）的异质性来确定实体的重要性，同时利用一种扩展激活算法（Extended spread activa-tion）来检索与查询词最相关的实体，因此可以边搜索边推理，并提供合适的实体排序结果。实验结果也显示出这种算法的效果。作者最后也指出，这种算法也具有一些不足，比如目前在模式图中分配边权重时无法采用机器自动分配以及跨平台可移植性效果不佳等；A.Harth等提出了语义搜索引擎SWSE，其是一种专门用来搜索实体及其相关知识的搜索引擎。SWSE的排序算法叫做ReConRank，该算法由3个阶段的实体计算构成：①ResourceRank；②ContextRank；③ReConRank。这3个阶段的计算过程都是在RDF资源图中利用改进的PageRank算法来进行的。具体来说，首先从web上抓取RDF数据，之后传递到有向图中，并利用ResourceRank算法计算排序分数；然后使用RDF数据源流信息的上下文情景语义图进一步计算ContextRank分数；最终，利用预定义规则衍生出的整合后的资源语义图进一步生成ReConRank分数，这种排序算法考虑了实体及其上下文的重要性，并具有一定的可扩展性；H.Hwang等提出了专门针对关系数据库中的排序算法ObjectRank，其主要是基于PageRank启发原则来排序实体对象，并提出了一系列指标和参数来改善结果的相关性。其中最重要的两个参数是特定指标和质量指标。特定指标是专门用来衡量与检索词最相关的实体对象；质量指标（quality metric）是用来衡量返回的实体本身的重要性的。此外还提出了两个参数，分别是“结果集中的相关实体的数量”和“查询词的权重”。作者也探索了将领域本体整合到ObjectRank算法中，来优化查询结果；C.Rocha等提出了一种混合排序算法，在传统关键词检索的基础上，结合扩展激活算法，通过图遍历进一步扩展检索与初始结果相关的更多实体，这是一种依赖特定领域来达到相关结果排序的方法。此外，该方法是通过上下文情景来描述实体之间关系的重要性的，并分配相应的权重。显而易见，这种实体排序算法对跨领域的排序并不能起到良好的效果；N.Stojanovic等提出一种利用本体中语义的排序算法。该方法结合推理过程的特点和资源内容本身，相结合来确定搜索结果的相关性和排序。其把实体间的语义关系分配两个权重，分别是“普遍性”和“用户自定义”，不仅考虑了上下文的情景，也考虑了其他的一些参数，诸如路径长度和关系的特定性等。也就是说，实体的关系特定性越高，该实体出现在其他关系中的可能性就越低。作者利用这种方法在样本数据集中进行测试，结果显示用户的满意度有所提高；R.McCreadie等利用一种扩展的投票模型来进行实体的排序，通过考虑查询词和实体在上下文的共现程度作为投票的标准，为投票模型建立一种语义关系支持。另外在投票模型之上，开发了一种基于图的技术来更进一步的增强初始投票评估效果。为了获取实体，他们利用了DBPedia建立了一个词典库，通过基于词典的方式来识别实体。他们的实验表明扩展的投票模型可以有效的处理实体排序问题；Z.wang提出了一个实体排序方法，该方法先以文档中心模型（DCM）为基础，然后计算查询术语与候选实体的距离得分。查询术语和候选实体的距离是指，在候选实体的所有相关文档中查询词和候选实体名称之间的最短距离。最后把文档中心模型得分和距离得分做线性累加。 2.2关系排序
目前语义搜索引擎的研究重点集中在如何更好地发现语义实体上，事实上语义网强调的是实体之间的关联关系，实体之间是通过关联关系结合在一起，孤立的实体本身并不包含任何语义信息。所以说，实体之间的关联关系相比实体本身更加具有研究价值，比如可以挖掘出隐藏在实体之间有价值的某种事实等。随着语义网资源的大量增长，实体之间的关联关系的个数必然会超过实体本身，因此，在这种多领域融合的语义搜索中，对关联关系搜索结果进行排序，将用户最为感兴趣的关联关系优先返回给用户，是当前急需解决的难点之一。
关联关系排序的困难之处在于，实体之间的链接异常复杂，某些隐式关联很难被发现，而且实体之间的关联反映在图模型中往往体现为一条路径，所以传统排序中链接分析无法适用。关联关系排序的实质就是对实体图中连接两个实体之间的路径进行排序。与实体排序和本体文档排序不同，语义关联关系排序是近几年才逐渐被人们关注的，相关研究还在快速发展中。
K.Anyanwu等提出了SemRank算法，这是一种语义关联关系搜索排序方法，这种方法利用“改进排序模型”（Modulative Ranking Model）来识别与用户查询词相关的上下文情景，然后推断用户兴趣，综合了各种语义信息和启发式信息。用户还可以改变检索的模式来得到涵盖某种特定情景的搜索排序结果；Y.Li等提出了以关联关系为基础的搜索引擎OntoLook，其首先进行网页的语义标注，利用概念和关系分别作为点和边进行建模，然后在图中删除一系列不相关的概念。利用这种方法，可以生成候选关系词集（CRKS），进而返回给标注数据库，最大限度上减少了无关网页的数量，优化了排序结果。这种方法主要靠个人经验和知识来识别概念关系，排除不相关概念，重构用户检索需求；B.Aleman等在利用复杂关系语义进行关系排序中进行了有益的尝试，并提出了一个以用户为中心的排序标准。作者提出了一些语义标准，比如“信任”、“包含”、“稀有度”、“关联长度”等，并利用这些标准对两个实体进行了语义关联的排序。由于这种排序方法包含了较多的参数，所以在计算排序分数权重时需要个人经验或领域专家的参与，所以并不适用于一般的用户；值得欣喜的是，国内对关联关系排序也有一定的探索研究，文坤梅提出了一种关联关系排序方法，其针对实体之间普遍存在的关联关系，以统计学、链接分析、社会网络等相关技术为基础，抽取3种影响排序的关键因素，分别是领域相关度，关联关系长度以及关联关系频度，并提出了这3种关键影响因子的计算方法，该方法综合考虑了3种因素的影响，能优先返回用户需要查询的关联关系。试验结果表明该方法能较好地将用户感兴趣的语义关联关系优先返回，并能挖掘出实体对象之间有价值的关联关系。
2.3语义/本体文档排序
语义/本体文档检索的目的是为了找到含有特定类或属性的本体文档。传统的搜索引擎无法识别本体的语义标注信息，所以在检索结果集中无法将真正符合用户需求的文档检索出来。就语义文档检索而言，结果集中应该返回的是包含与查询词最相关的实体及其关系的文档。当前用于本体文档排序的相关方法大致可以分为：基于链接分析的方法、基于结构分析的方法、基于内容分析的方法、基于概念结构分析的排序方法以及一些其他排序方法。目前本体文档排序虽然形成了较为系统的排序方法，但是还没有统一的标准，缺乏一致的衡量标准，在计算排序时要从本体链接关系、本体的模式和重要性、概念匹配的特征甚至是实体等角度进行综合考虑，同时也要结合用户的个性化需求，才能够获得需求导向的最佳的排序效果。
2.3.1基于链接分析的排序方法
L.Ding等提出了语义搜索引擎Swoogle，其使用类似于PageRank的链接分析法，作者提出了语义Web中的3种基本元素：语义Web文档（SWD）、语义Web本体（SwO）以及语义Web术语（SWT），针对不同的元素，分别给出了不同的排序算法。其中针对语义Web文档（SWD）的排序算法叫做OntoRank，在这种算法中，作者引入了3种不同的隐式链接关系，分别是引用（TM/IN）、扩展（EX）以及导人（IM）。引用表示一个本体文档引用了另一个本体文档中定义的术语；扩展表示一个本体扩展了另外一个本体；导入表示一个本体导入另外一个本体，基于这些链接关系，OntoRank采用随机冲浪模型来计算本体的重要性。本体间的连接关系不同于网页的链接，OntoRank算法引入了更加合理的模型，为实体的关系赋予不同的权重。这种算法可以检索出大量相关本体，但本体的主题对于排序结果的影响被忽略了，也就是说OntoRank只能以静态的方式评价本体的重要性，不能将用户的查询词作为影响排序结果的因素。类似于这种改进的PageRank的算法还有ontokhoj算法，在该算法中，本体间的链接关系被定义为两个本体中概念之间的引用关系，同时这种链接关系被认为是有向的而且可以传递，链接的强度随着链接距离的增加而减弱，在确定了本体的链接关系后，再采用随机冲浪模型计算每个本体的排序值即可。这种改进的PageRank算法将本体看成与网页类似的无结构数据，但本体具有其特殊性，从而导致排序结果准确度不高。
使用链接分析或其他在此基础上改进后的算法，用来计算本体文档排序的主要困难在于，本体与网页不同，本体之间缺乏显式的链接，所以采用链接分析的方法就必须要挖掘出本体之间的隐式关联。这种以OntoRank为代表的链接分析方法，由于本体主题对排序结果的影响被忽略，所以不能将其作为结果排序的因素。
2.3.2基于结构分析的方法
H.Alani等提出了AKTiveRank算法，该方法从另一个角度考虑了用户的查询，尤其是多个关键字查询对排序的影响。该算法利用了4个标准对本体的重要性进行评分，分别是类匹配标准（Class Mateh Measure）、密度标准（Density Measoxe）、语义相似度标准（Semantie Similarity Measue）和中间性标准，用户在查询时，本体文档的排序分数由这4种标准加权来计算。实证结果显示，在考虑查询的情境下，AKTiveRank算法排序结果比单一的OntoRank更加贴近实际标准。此外，一些研究侧重将Swoogle链接分析方法和AKTiveRank方法结合起来探索本体排序结果，比较有代表性的比如张志强等的研究，其将AKTiveRank中的类匹配度量、语义相似性度量以及密度度量等保留，并结合匹配类的子类及其属性，设置相应的权重，迭代计算类的重要性，最后在Swoogle链接分析的基础上计算本体的重要性的分数。相比基于链接分析方法，基于结构分析的方法考虑到了本体自身的结构特性，同时也考虑到了用户查询词对结果集的影响，但是这种方法的时间成本较大。 S.Tartir等提出了OntoQA算法，首次把实体数据的考察引入到本体评价中。该算法的创新之处在于不仅考虑本体模式的评分，同时也考虑了本体知识库的评分。该算法是对搜索到的本体文档根据其结构特征，再与用户查询词相对比，进行多方面的度量，对各个度量值进行加权计算，从而得到本体的最终排序值。这种算法对本体文档重要性的评分可以分为两个方面，分别是本体模式和本体实体。严格说来，这是一种基于模式和实体分析的排序方法。
2.3.3基于内容分析的排序方法
M.Jones等提出了一种基于内容分析的本体排序算法，这种算法不仅考虑了类标签，同时考虑了本体图以外的评论等内容。其认为在结果集中本体的重要性不仅与查询词有关，与其相关概念的匹配程度也有关，匹配越多的查询词，本体就越重要，排序时就应该排在前面。在实验中，作者利用wordnet获得查询词的上位词、下位词以及同义词，再根据结果集中与本体中类的匹配程度来计算本体的类匹配值和文本匹配值，通过两者加权进行本体文档的排序。
2.3.4基于概念结构分析的排序方法
A.Harith在研究中考虑了匹配概念在本体结构中的重要程度，充分注重了本体中匹配概念间的结构和关系，通过查询匹配，找到用户所关注的概念在本体中的位置，然后分析其结构的特征。这种算法考察了4种衡量因素：分别是类匹配度量（CMM），中心性度量（BEM），密度度量（DEM），语义相似性度量（SSM），通过对上述4种因素的加权平均得到每个本体文档的分数，然后进行排序。
2.3.5其他排序方法
OntoFetcher从概念覆盖CCW、关系覆盖PRW、相关性度量RM、连通性度量CM、关系的丰富度RR与Swoogle链接分析计算出的本体的秩几个方面进行了本体重要度的考量，从而进行排序设计，可以说是一种基于内容和链接分析相整合的排序方法；V.Sankar等人提出了一种基于OWL的本体文档排序方法，OWL中含有描述类、类公理、属性定义与约束等内部关系，可以通过对OWL中类匹配进行计算排序；徐德智等针对传统本体排序结果不准确的情况下，提出一种新的内容分析方法，首先通过构造本体的概念模型提取本体的主题词集合得到本体的主题相似度；然后通过对关键词所在的本体上下文进行分析，得到本体相对于关键词的上下文相关度；最后对二者进行加权平均得到本体文档的排序分数。实验结果表明，该方法可以有效地提高本体排序的准确性；寇燕歌等使用TF-IDF方法计算查询词与本体文档中术语的权重，通过计算夹角弦值的方法衡量二者的相似度，据此进行本体的排序；杨克特等使用TF-IDF方法计算匹配类的重要程度，再结合本体链接分析方法，提出一种面向特定领域的语义文档排序算法；T.Ahmed在分析本体链接的基础上，提出了基于HITS的本体排序方法；H.Lewen探索了用户对本体评论或用户信任度等的本体反馈信息对排序的影响；还有一些研究主要从方法的角度对本体排序因素进行了探讨，但是没有阐述具体的量化计算方法。
以上是典型的语义/本体文档排序算法，近年来一些研究开始逐步关注针对本体中某一片段甚至是个别词汇的排序。在这种元素级或粒度层级上的排序目前还在快速发展中，代表性的算法有TermRank、CARRank和TripleRank等。
TermRank是swoogle中用于术语排序的一种算法，该算法使用术语的流行度作为排序的标准，术语流行度由该术语被使用的次数、推广的量、所在语义文档上下文重要性等共同来确定；CARRank是一种利用相互增强关系迭代计算本体中概念与关系的重要性的方法。这种算法根据本体构建模型的特点进行分析，从而得到本体模型的4个特征，最后根据这些基本特征利用本体中元素的中心值来表示本体中片段的重要性；TripleRank是一种利用张量分解对语义网数据进行排序的方法。该算法中使用统计学方法获得外部语义来增强可用数据，并使用张力模型来模拟RDF图。最后使用平行因子法分析此模型，将该模型看成是可以使用HITS算法进行排序的模型。
3 总结与展望
语义检索相比传统检索的优势在于可以实现基于语义的匹配和推理，是一种知识检索，可以返回与查询词更相关的内容。本体在语义检索中处于非常重要的位置，承担着知识表达的核心任务，对语义检索的推理也起着支撑性的作用。由于语义Web对传统互联网进行了革命性的变化，使其检索和排序的对象不仅仅局限于文档和网页，更包括了实体和关系等，虽然可以通过模型变换和算法改进来优化传统的排序算法，也带来了一定的效果改善，但是由于语义Web的特殊结构，传统排序算法的思路并不能完全移植到语义Web中。本文在调研的基础上，详细阐述了当前实体排序、关系排序和本体文档排序的研究进展，可以预见的是，在将来的语义排序算法发展中，语义网中信任和信誉度的研究将越来越受到重视，将用户的社会网络因素同已有的排序算法相结合，必将是未来重要的研究方向之一。
（本文责任编辑：孙国雷）
[关键词]语义检索；检索排序；本体；关系；实体
[中图分类号]G250
[文献标识码]A
[文章编号]1008-0821（2015）02-0159-06
搜索引擎最重要的任务是搜集网络信息，提供给用户与其检索词最匹配的结果，并返回相关链接。搜索引擎在网络上抓取足够的网页已不再是困难，困难在于如何将这些网页整理出来，选择合适的排序算法，把这些结果集返回给用户。语义网技术的出现，更加加剧了这种困境。语义网的宏观结构来源于RDF模型所定义的数据之间的链接，随着RDF数据大量涌入，传统搜索引擎更加凸显出局限性，因此语义搜索引擎应运而生。由于语义检索的对象不再仅限于文档和网页，同时也包括了实体和关系等，所以在一定程度上对排序算法的要求变得更高。对于语义搜索引擎来说，一个合理的排序算法不仅可以帮助用户提高搜索效率，更是迈向可信语义网的至关重要的一步。从对现有研究与调研的基础上可以看出，目前针对本体文档的排序研究较多，已经形成了较为系统的分类排序算法体系，但针对实体和关系的排序的研究还在发展中。本文按照排序的阶段将语义检索排序分为实体排序、关系排序和文档排序，并详细阐述了每种排序算法的研究进展，供今后研究人员参考。
1 传统排序算法概述
传统搜索引擎的排序算法主要可以分为两类，分别是基于链接分析的方法和基于用户行为分析的方法，以及在此基础上进行改进的排序模型。其中基于链接分析的方法又可以分为PageRank算法、HITS算法、SALSA算法等；基于用户行为分析的方法可以分为BrownseRank和Direct Hit算法等；一些在此基础上改进的排序算法包括基于节点和边属性的排序算法、基于监督学习的排序算法等。随着语义网的发展，本体数量与日俱增，本体模型在语义网上被广泛地应用，传统的基于关键词的检索方法不能对本体中的语义关系进行很好的推理，而仅仅基于表述逻辑对本体进行检索，因而用户满意度并不高，也无法取得很好的排序结果。与此同时，一些研究将传统的排序算法应用于语义检索中，取得了一定的成果，但是由于本体结构的特殊性，目前相关研究仍在探索更加优化的排序算法，下文将详细介绍当前的研究现状和进展。
2 语义检索排序方法
当前按照排序的阶段可以将语义检索排序分为实体排序、关系排序和本体文档排序，但是这些排序方法之间是有很大交集的，并无严格的界限。
2.1实体排序
语义网中的定义/概念是为了描述现实中的实体数据，这些实体数据都将服务于资源的请求者，比如利用FOAF撰写的个人档案就是目前最常用的实体数据。语义网最初发展时，由于实体数据相对匮乏，因而并未引起足够的重视，近年来随着语义网的迅猛发展，大量类似于FOAF、RSS等实体数据的出现，加上实体排序本身就有着巨大的研究价值和商业价值，使得这个问题越来越受到研究者的关注，而且从实际的角度来讲，对于大多数一般用户而言，实体数据的检索需求更为普遍。实体排序问题的实质是对实体之间异质关联的分析方法，其排序的目的是从知识库中发现和检索与用户需求最匹配的实体对象，这种最匹配的实体对象一般称为种子实体（seed entity），排序的困难之处在于实体之间的关联异常的复杂，一些隐式关联很难被发现，推理过程不仅牵扯到描述逻辑（Description Logic）的推理规则，还需要使用语义网规则描述语言（SWRL）定义的规则，因此在对实体数据进行排序的过程中，如果想得到全面准确的排序结果，那么推理所起到的作用是不可忽略的。
W.Wei等人提出了针对特定领域的实体排序算法RareRank，其指出传统的信息检索模型主要依靠内容和链接分析评分来确定排序结果，即相关性分数（relevance）和质量分数（quality）。作者将这两种评分相结合，并在此基础上分配相应的参数来进行优化，并引入了合理搜索模型（Rational Research Model）。其首先将一个领域的知识利用有向图来表示，然后将领域本体引入到有向图中，因此该模型的排序分数整合了领域本体的相关性分数和链接分析的质量分数。这个方法实质是应用了链接分析来对实体进行排序，实证结果证明效果确实有一定改善，但是该模型的参数设置较为简单，将来还需要大量的数据集进行测试。L.Dali等人提出了Learning to Rank算法，其主要是采用查询词本身进行实体的优化排序，首先利用PageRank作为参考模型，并将其应用到RDF图中，并结合这些词的变化特点，进而获得更高的资源关联，最后计算出更好的排序结果。这种方法的本质是利用查询词自身特点的RDF图。相比一般的文本排序，该方法会产生较大的非连续性，尤其是在关联数据集（LOD）参与的情况下，很难具有较好的效果；X.Ning等提出了语义搜索排序框架RSS，这种算法一方面利用关系（relations）的异质性来确定实体的重要性，同时利用一种扩展激活算法（Extended spread activa-tion）来检索与查询词最相关的实体，因此可以边搜索边推理，并提供合适的实体排序结果。实验结果也显示出这种算法的效果。作者最后也指出，这种算法也具有一些不足，比如目前在模式图中分配边权重时无法采用机器自动分配以及跨平台可移植性效果不佳等；A.Harth等提出了语义搜索引擎SWSE，其是一种专门用来搜索实体及其相关知识的搜索引擎。SWSE的排序算法叫做ReConRank，该算法由3个阶段的实体计算构成：①ResourceRank；②ContextRank；③ReConRank。这3个阶段的计算过程都是在RDF资源图中利用改进的PageRank算法来进行的。具体来说，首先从web上抓取RDF数据，之后传递到有向图中，并利用ResourceRank算法计算排序分数；然后使用RDF数据源流信息的上下文情景语义图进一步计算ContextRank分数；最终，利用预定义规则衍生出的整合后的资源语义图进一步生成ReConRank分数，这种排序算法考虑了实体及其上下文的重要性，并具有一定的可扩展性；H.Hwang等提出了专门针对关系数据库中的排序算法ObjectRank，其主要是基于PageRank启发原则来排序实体对象，并提出了一系列指标和参数来改善结果的相关性。其中最重要的两个参数是特定指标和质量指标。特定指标是专门用来衡量与检索词最相关的实体对象；质量指标（quality metric）是用来衡量返回的实体本身的重要性的。此外还提出了两个参数，分别是“结果集中的相关实体的数量”和“查询词的权重”。作者也探索了将领域本体整合到ObjectRank算法中，来优化查询结果；C.Rocha等提出了一种混合排序算法，在传统关键词检索的基础上，结合扩展激活算法，通过图遍历进一步扩展检索与初始结果相关的更多实体，这是一种依赖特定领域来达到相关结果排序的方法。此外，该方法是通过上下文情景来描述实体之间关系的重要性的，并分配相应的权重。显而易见，这种实体排序算法对跨领域的排序并不能起到良好的效果；N.Stojanovic等提出一种利用本体中语义的排序算法。该方法结合推理过程的特点和资源内容本身，相结合来确定搜索结果的相关性和排序。其把实体间的语义关系分配两个权重，分别是“普遍性”和“用户自定义”，不仅考虑了上下文的情景，也考虑了其他的一些参数，诸如路径长度和关系的特定性等。也就是说，实体的关系特定性越高，该实体出现在其他关系中的可能性就越低。作者利用这种方法在样本数据集中进行测试，结果显示用户的满意度有所提高；R.McCreadie等利用一种扩展的投票模型来进行实体的排序，通过考虑查询词和实体在上下文的共现程度作为投票的标准，为投票模型建立一种语义关系支持。另外在投票模型之上，开发了一种基于图的技术来更进一步的增强初始投票评估效果。为了获取实体，他们利用了DBPedia建立了一个词典库，通过基于词典的方式来识别实体。他们的实验表明扩展的投票模型可以有效的处理实体排序问题；Z.wang提出了一个实体排序方法，该方法先以文档中心模型（DCM）为基础，然后计算查询术语与候选实体的距离得分。查询术语和候选实体的距离是指，在候选实体的所有相关文档中查询词和候选实体名称之间的最短距离。最后把文档中心模型得分和距离得分做线性累加。 2.2关系排序
目前语义搜索引擎的研究重点集中在如何更好地发现语义实体上，事实上语义网强调的是实体之间的关联关系，实体之间是通过关联关系结合在一起，孤立的实体本身并不包含任何语义信息。所以说，实体之间的关联关系相比实体本身更加具有研究价值，比如可以挖掘出隐藏在实体之间有价值的某种事实等。随着语义网资源的大量增长，实体之间的关联关系的个数必然会超过实体本身，因此，在这种多领域融合的语义搜索中，对关联关系搜索结果进行排序，将用户最为感兴趣的关联关系优先返回给用户，是当前急需解决的难点之一。
关联关系排序的困难之处在于，实体之间的链接异常复杂，某些隐式关联很难被发现，而且实体之间的关联反映在图模型中往往体现为一条路径，所以传统排序中链接分析无法适用。关联关系排序的实质就是对实体图中连接两个实体之间的路径进行排序。与实体排序和本体文档排序不同，语义关联关系排序是近几年才逐渐被人们关注的，相关研究还在快速发展中。
K.Anyanwu等提出了SemRank算法，这是一种语义关联关系搜索排序方法，这种方法利用“改进排序模型”（Modulative Ranking Model）来识别与用户查询词相关的上下文情景，然后推断用户兴趣，综合了各种语义信息和启发式信息。用户还可以改变检索的模式来得到涵盖某种特定情景的搜索排序结果；Y.Li等提出了以关联关系为基础的搜索引擎OntoLook，其首先进行网页的语义标注，利用概念和关系分别作为点和边进行建模，然后在图中删除一系列不相关的概念。利用这种方法，可以生成候选关系词集（CRKS），进而返回给标注数据库，最大限度上减少了无关网页的数量，优化了排序结果。这种方法主要靠个人经验和知识来识别概念关系，排除不相关概念，重构用户检索需求；B.Aleman等在利用复杂关系语义进行关系排序中进行了有益的尝试，并提出了一个以用户为中心的排序标准。作者提出了一些语义标准，比如“信任”、“包含”、“稀有度”、“关联长度”等，并利用这些标准对两个实体进行了语义关联的排序。由于这种排序方法包含了较多的参数，所以在计算排序分数权重时需要个人经验或领域专家的参与，所以并不适用于一般的用户；值得欣喜的是，国内对关联关系排序也有一定的探索研究，文坤梅提出了一种关联关系排序方法，其针对实体之间普遍存在的关联关系，以统计学、链接分析、社会网络等相关技术为基础，抽取3种影响排序的关键因素，分别是领域相关度，关联关系长度以及关联关系频度，并提出了这3种关键影响因子的计算方法，该方法综合考虑了3种因素的影响，能优先返回用户需要查询的关联关系。试验结果表明该方法能较好地将用户感兴趣的语义关联关系优先返回，并能挖掘出实体对象之间有价值的关联关系。
2.3语义/本体文档排序
语义/本体文档检索的目的是为了找到含有特定类或属性的本体文档。传统的搜索引擎无法识别本体的语义标注信息，所以在检索结果集中无法将真正符合用户需求的文档检索出来。就语义文档检索而言，结果集中应该返回的是包含与查询词最相关的实体及其关系的文档。当前用于本体文档排序的相关方法大致可以分为：基于链接分析的方法、基于结构分析的方法、基于内容分析的方法、基于概念结构分析的排序方法以及一些其他排序方法。目前本体文档排序虽然形成了较为系统的排序方法，但是还没有统一的标准，缺乏一致的衡量标准，在计算排序时要从本体链接关系、本体的模式和重要性、概念匹配的特征甚至是实体等角度进行综合考虑，同时也要结合用户的个性化需求，才能够获得需求导向的最佳的排序效果。
2.3.1基于链接分析的排序方法
L.Ding等提出了语义搜索引擎Swoogle，其使用类似于PageRank的链接分析法，作者提出了语义Web中的3种基本元素：语义Web文档（SWD）、语义Web本体（SwO）以及语义Web术语（SWT），针对不同的元素，分别给出了不同的排序算法。其中针对语义Web文档（SWD）的排序算法叫做OntoRank，在这种算法中，作者引入了3种不同的隐式链接关系，分别是引用（TM/IN）、扩展（EX）以及导人（IM）。引用表示一个本体文档引用了另一个本体文档中定义的术语；扩展表示一个本体扩展了另外一个本体；导入表示一个本体导入另外一个本体，基于这些链接关系，OntoRank采用随机冲浪模型来计算本体的重要性。本体间的连接关系不同于网页的链接，OntoRank算法引入了更加合理的模型，为实体的关系赋予不同的权重。这种算法可以检索出大量相关本体，但本体的主题对于排序结果的影响被忽略了，也就是说OntoRank只能以静态的方式评价本体的重要性，不能将用户的查询词作为影响排序结果的因素。类似于这种改进的PageRank的算法还有ontokhoj算法，在该算法中，本体间的链接关系被定义为两个本体中概念之间的引用关系，同时这种链接关系被认为是有向的而且可以传递，链接的强度随着链接距离的增加而减弱，在确定了本体的链接关系后，再采用随机冲浪模型计算每个本体的排序值即可。这种改进的PageRank算法将本体看成与网页类似的无结构数据，但本体具有其特殊性，从而导致排序结果准确度不高。
使用链接分析或其他在此基础上改进后的算法，用来计算本体文档排序的主要困难在于，本体与网页不同，本体之间缺乏显式的链接，所以采用链接分析的方法就必须要挖掘出本体之间的隐式关联。这种以OntoRank为代表的链接分析方法，由于本体主题对排序结果的影响被忽略，所以不能将其作为结果排序的因素。
2.3.2基于结构分析的方法
H.Alani等提出了AKTiveRank算法，该方法从另一个角度考虑了用户的查询，尤其是多个关键字查询对排序的影响。该算法利用了4个标准对本体的重要性进行评分，分别是类匹配标准（Class Mateh Measure）、密度标准（Density Measoxe）、语义相似度标准（Semantie Similarity Measue）和中间性标准，用户在查询时，本体文档的排序分数由这4种标准加权来计算。实证结果显示，在考虑查询的情境下，AKTiveRank算法排序结果比单一的OntoRank更加贴近实际标准。此外，一些研究侧重将Swoogle链接分析方法和AKTiveRank方法结合起来探索本体排序结果，比较有代表性的比如张志强等的研究，其将AKTiveRank中的类匹配度量、语义相似性度量以及密度度量等保留，并结合匹配类的子类及其属性，设置相应的权重，迭代计算类的重要性，最后在Swoogle链接分析的基础上计算本体的重要性的分数。相比基于链接分析方法，基于结构分析的方法考虑到了本体自身的结构特性，同时也考虑到了用户查询词对结果集的影响，但是这种方法的时间成本较大。 S.Tartir等提出了OntoQA算法，首次把实体数据的考察引入到本体评价中。该算法的创新之处在于不仅考虑本体模式的评分，同时也考虑了本体知识库的评分。该算法是对搜索到的本体文档根据其结构特征，再与用户查询词相对比，进行多方面的度量，对各个度量值进行加权计算，从而得到本体的最终排序值。这种算法对本体文档重要性的评分可以分为两个方面，分别是本体模式和本体实体。严格说来，这是一种基于模式和实体分析的排序方法。
2.3.3基于内容分析的排序方法
M.Jones等提出了一种基于内容分析的本体排序算法，这种算法不仅考虑了类标签，同时考虑了本体图以外的评论等内容。其认为在结果集中本体的重要性不仅与查询词有关，与其相关概念的匹配程度也有关，匹配越多的查询词，本体就越重要，排序时就应该排在前面。在实验中，作者利用wordnet获得查询词的上位词、下位词以及同义词，再根据结果集中与本体中类的匹配程度来计算本体的类匹配值和文本匹配值，通过两者加权进行本体文档的排序。
2.3.4基于概念结构分析的排序方法
A.Harith在研究中考虑了匹配概念在本体结构中的重要程度，充分注重了本体中匹配概念间的结构和关系，通过查询匹配，找到用户所关注的概念在本体中的位置，然后分析其结构的特征。这种算法考察了4种衡量因素：分别是类匹配度量（CMM），中心性度量（BEM），密度度量（DEM），语义相似性度量（SSM），通过对上述4种因素的加权平均得到每个本体文档的分数，然后进行排序。
2.3.5其他排序方法
OntoFetcher从概念覆盖CCW、关系覆盖PRW、相关性度量RM、连通性度量CM、关系的丰富度RR与Swoogle链接分析计算出的本体的秩几个方面进行了本体重要度的考量，从而进行排序设计，可以说是一种基于内容和链接分析相整合的排序方法；V.Sankar等人提出了一种基于OWL的本体文档排序方法，OWL中含有描述类、类公理、属性定义与约束等内部关系，可以通过对OWL中类匹配进行计算排序；徐德智等针对传统本体排序结果不准确的情况下，提出一种新的内容分析方法，首先通过构造本体的概念模型提取本体的主题词集合得到本体的主题相似度；然后通过对关键词所在的本体上下文进行分析，得到本体相对于关键词的上下文相关度；最后对二者进行加权平均得到本体文档的排序分数。实验结果表明，该方法可以有效地提高本体排序的准确性；寇燕歌等使用TF-IDF方法计算查询词与本体文档中术语的权重，通过计算夹角弦值的方法衡量二者的相似度，据此进行本体的排序；杨克特等使用TF-IDF方法计算匹配类的重要程度，再结合本体链接分析方法，提出一种面向特定领域的语义文档排序算法；T.Ahmed在分析本体链接的基础上，提出了基于HITS的本体排序方法；H.Lewen探索了用户对本体评论或用户信任度等的本体反馈信息对排序的影响；还有一些研究主要从方法的角度对本体排序因素进行了探讨，但是没有阐述具体的量化计算方法。
以上是典型的语义/本体文档排序算法，近年来一些研究开始逐步关注针对本体中某一片段甚至是个别词汇的排序。在这种元素级或粒度层级上的排序目前还在快速发展中，代表性的算法有TermRank、CARRank和TripleRank等。
TermRank是swoogle中用于术语排序的一种算法，该算法使用术语的流行度作为排序的标准，术语流行度由该术语被使用的次数、推广的量、所在语义文档上下文重要性等共同来确定；CARRank是一种利用相互增强关系迭代计算本体中概念与关系的重要性的方法。这种算法根据本体构建模型的特点进行分析，从而得到本体模型的4个特征，最后根据这些基本特征利用本体中元素的中心值来表示本体中片段的重要性；TripleRank是一种利用张量分解对语义网数据进行排序的方法。该算法中使用统计学方法获得外部语义来增强可用数据，并使用张力模型来模拟RDF图。最后使用平行因子法分析此模型，将该模型看成是可以使用HITS算法进行排序的模型。
3 总结与展望
语义检索相比传统检索的优势在于可以实现基于语义的匹配和推理，是一种知识检索，可以返回与查询词更相关的内容。本体在语义检索中处于非常重要的位置，承担着知识表达的核心任务，对语义检索的推理也起着支撑性的作用。由于语义Web对传统互联网进行了革命性的变化，使其检索和排序的对象不仅仅局限于文档和网页，更包括了实体和关系等，虽然可以通过模型变换和算法改进来优化传统的排序算法，也带来了一定的效果改善，但是由于语义Web的特殊结构，传统排序算法的思路并不能完全移植到语义Web中。本文在调研的基础上，详细阐述了当前实体排序、关系排序和本体文档排序的研究进展，可以预见的是，在将来的语义排序算法发展中，语义网中信任和信誉度的研究将越来越受到重视，将用户的社会网络因素同已有的排序算法相结合，必将是未来重要的研究方向之一。
（本文责任编辑：孙国雷）