全局分析和本体技术相结合的查询扩展算法

创新者：张 磊

全局分析和本体技术相结合的查询扩展算法

创新者：张 磊

查询扩展可以弥补用户初始查询请求语义信息不明晰的缺陷，提高搜索性能。首先，对用户查询模式进行分析，根据查询模式的不同特点给出相应的查询扩展方法与策略，然后，提出一种全局分析和本体技术相结合的查询扩展算法，有效解决各类查询模式的查询扩展问题。仿真实验的结果表明，该算法的综合性能比全局分析的查询扩展算法的综合性能提高了12.9％，比基于本体技术的查询扩展算法的综合性能提高了9.8％。

研究发现，两个人使用相同词汇描述同一事物的概率小于20％。必须对用户查询请求进行改进处理，以提高检索性能。查询扩展QE（Query Expansion）是在初始查询的基础上加入与用户检索词相关联的新词，生成更准确的查询请求，弥补用户查询信息不足的缺陷，改善信息检索的性能。查询扩展对短查询尤为有效，因为查询越短，查询本身表达的信息就越模糊。常用的查询扩展技术有全局分析、局部分析、基于关联规则的方法以及基于本体的方法等。

全局分析对全部文档中的词或词组进行相关分析，计算每对词或词组间的关联程度，将词或词组按共同发生的频率先行聚类，其后根据词或词组的不同集合对查询进行扩展。全局分析需要对整个文献集进行处理，过程复杂，计算量大。局部分析较好地解决了全局分析的缺陷。局部分析利用初次检索得到的与查询最相关的top-k篇文章作为扩展用词的来源，而非全部文档。常用的局部分析技术有局部聚类、用户相关反馈（如用户日志、历史查询信息等）和局部上下文分析等。局部分析依赖初次检索文档的质量，当初检文档与原查询相关度不高时，会把大量无关词加入到查询中，降低查询性能。

基于关联规则的查询扩展则是通过数据挖掘技术挖掘词间关联规则，将关联规则的结论作为扩展用词的来源。该方法虽然在一定程度上克服了全局分析和局部分析的不足，但是查询扩展的效果受词间关联规则质量影响较大。

基于本体的查询扩展利用本体中的同义词和特定的子类进行扩展，收到了很好的效果。查询扩展中常用的本体有两类，一类是通用的词汇本体，如WordNet、HowNet等。这类本体在各个领域广泛使用，缺乏专业领域的词汇间的语义联系，扩展性能不稳定；另一类是领域本体，这类本体针对特定领域，本体概念所表达的语义信息明确，对该领域内的查询请求进行语义扩展非常有效。

全局分析、局部分析和基于关联规则的查询扩展在关键词匹配层次上进行的查询扩展，难以充分表达和扩展用户查询的语义信息，不能从根本上消除用户查询意图与检索结果之间的语义偏差问题。基于本体的查询扩展忽略了用户查询关键词存在多样性，查询词汇可能位于本体之外这一事实，假设查询词汇都来源于本体。一旦假设不成理，如何找到与查询词汇语义相关的本体概念就变得非常关键。

本文首先对用户查询模式进行分析，针对不同查询模式的特点给出不同的查询扩展方法与策略，然后提出一种全局分析和本体技术相结合的查询扩展方法，该方法在兼顾二者优点的同时避开各自的缺点。

用户查询模式分析

分析发现，用户查询请求往往遵循一些典型模式。针对查询模式的不同特点，可以采用不同的方法进行扩展处理。

（1）C模式查询

C模式即概念词汇模式（Concept Word Model）。此模式的查询词汇由本体概念组成，能够根据本体概念判断查询语义，获知用户查询意图。在此模式下，可以利用本体概念中的父子和同义等关系进行扩展，准确表达用户的查询目的，提高搜索性能。本文对C模式查询采用三种扩展方式，即同义替换、概念泛化和概念细化。

1）同义替换。本体概念的同义关系表示概念表达的语义信息相同，可以替换使用。这种利用概念间的同义关系进行扩展的方式叫同义替换。比如，用户输入了“计算机”这一本体概念，可以将具有同义关系的“电脑”概念作为语义扩展的目标。

2）概念泛化。本体中的某些概念可能同时出现在多个概念分支下面。比如，ACM本体（http：∥www.acm. org/about/class/1998）中，“Fault Tolerance”位于“B.1 Microprogramming”、“B.4 Data Communication”和“D.4 Operating System”等多个概念分支下面。概念泛化的基本思想是确定概念所属分支，将分支上的父概念和概念本身组合起来表达查询的具体语义。比如，将“Fault Tolerance”与其父概念“B.1 Microprogramming”组合起来后，表达的语义比单个“Fault Tolerance”更为精确。概念泛化可以通过自然语言理解及上下文分析等技术实现，也可以通过用户交互实现。

3）概念细化。概念细化的基本思想是将子概念与概念本身组合起来表达查询的具体语义。比如，概念“C.2.3 Network Operations”分支下面有子概念“NetworkManagement”和“Network Monitoring”。将“C.2.3 Network Operations”与其子概念“Network Management”或“Network Monitoring”组合起来后，表达的语义比单个“C.2.3 Network Operations”更为精确。在概念细化过程中，可以将分支上的全部子概念作为细化对象，也可以通过用户交互选择其中某一个或几个子概念作为细化对象。

（2）O模式查询

O模式即普通词汇模式（Ordinary Word Model）。此模式的查询词汇非本体概念，而是位于本体之外的普通单词。该模式无法借助本体技术进行扩展，只能使用全局分析或局部分析等扩展技术。为了避免局部分析中的二次搜索，本文选择全局分析进行O模式查询扩展。

统计发现，普通词汇和特定的本体概念间往往有很强的相关性。比如，“QoS”词频比较高的文档资源一般和本体概念“Network Measure”有关。如果借助全局分析技术计算普通词语和本体概念间的相关性，就可以根据计算结果选择合适的本体概念作为扩展的目标。在O模式查询扩展中，词语-概念相关度计算是进行语义扩展的关键环节。

（3）混合模式查询

混合模式查询指查询词汇中同时包含C模式词汇和O模式词汇。此模式的查询词汇既有本体概念，又有位于本体之外的普通单词。对于本体概念，采用C模式处理方法进行扩展；对于普通词汇，则按照O模式处理方法进行扩展。

词语-概念相关度计算

随着语义Web和本体技术的发展，人们借助本体为越来越多的文档资源添加语义信息，把资源标注到1个或者多个本体概念下作为概念实例是最常见的操作。此时，文档资源到概念间存在所属关系，文档资源中的词语到概念也存在所属关系，这种所属关系蕴涵着词语-概念的相关关系。

如图1所示，一个词语可能存在于多个文档中，而每个文档又属于1个或多个概念类。词语与概念通过文档建立联系，可以利用词汇与概念间的共现性计算词汇-概念相关度。通过统计包含词语的文档资源所属的概念，就可以统计出这个词语对不同概念的所属程度，即是词语-概念相关度。

词语-概念相关度计算应满足下面3个基本准则。

（1）一个词语通过文档资源映射到的本体概念的个数越多，它对单个概念的相关度越低。

（2）一个词语在某一概念对应文档资源中的词频越高，它对这个概念的相关度越高。

（3）一个词语在某一个概念对应的越多文档资源中存在，它对这个概念的相关度越高。

准则1是从词语在概念空间中的分布情况来分析。一个词语与越多的概念关联，它对概念的区分性就越不明显，它与概念的相关度也就越低。

准则2是从词语在一个概念对应的文档资源中出现的频率来分析。选择词频作为统计量而不选择文档资源数量作为统计量，原因在于前者属于细粒度，区分性强，可以更准确地刻画词语对概念的相关度。

图1　词语-文档-概念关系

准则3是从词语在一个概念对应的文档资源中的分布情况来分析。词语在一个概念对应的越多文档资源中出现，说明它在这个概念中分布的越均匀，它与概念的所属关系被越多的文档承认，因而它与这个概念的相关度也就越高。

本文基于上述3个基本准则，并借鉴文献中的部分思想，给出词语-概念相关度计算公式。

定义1. 假设文档资源集为D ，共有m 个文档资源，dj（j=1，...，m）表示第j 个文档资源；本体概念集为C ，共有n 个概念，ci（i=1，...，n）表示第i 个概念，词语集为T ，共有p 个词汇，tk（i =1，...，p）表示第k 个词汇。词语tk和概念ci的相关度为

式（1）中，nk表示tk根据文档-概念关系映射到概念上的概念数目，numi表示概念ci对应的文档数目，numk，i表示概念ci对应的文档资源中出现词语tk的文档数目，表示词语tk通过文档映射到概念ci的词频统计量。

式（2）中，Di表示概念ci对应的文档集合，即Di=｛dj|dj∈D∧dj是ci的 实例｝，count （tk，dj）表示词语tk在文档资源dj中出现的次数，len（dj）表示dj的长度。

利用公式（1）可以计算词语和本体概念间的语义相关度，从而构建词语-概念相关度词典（Association Thesaurus），用于语义查询扩展。

查询扩展算法

算法1. 全局分析和本体技术相结合的查询扩展算法

输入：查询请求Q（q1，q2，…，ql）

输出：扩展后的查询请求Q′

算法描述：

1.Q′=Q ；

2.Q查询模式分析；

3.IFQ 为混合模式

图2　查询扩展算法流程图

4.查询请求Q 分组为Q1和Q2；//Q1为C模式词汇，Q2为O模式词汇

5.For Each qiIn Q1

6.C模式查询扩展；

7.End For；

8.For Each qiIn Q2

9.O模式查询扩展；

10.End For；

11.ELSE

12.IF Q为C模式

13.For EachqiIn Q

14.C模式查询扩展；

15.End For；

16.End IF

17.IF Q为O模式

18.For EachqiIn Q

19.O模式查询扩展；

20.End For；

21.End IF

22.End IF

23.扩展结果合并；

24. 返回扩展后的查询请求Q′。

全局分析和本体技术相结合的查询扩展算法流程如图2所示。

仿真实验

本节通过仿真实验分析查询扩展算法的性能。本体采用计算机科学领域的领域本体ACM。文档资源从ACM数据库下载（http：//porta.acm.org/portal.cfm），资源规模为19030。本文对比三种不同查询扩展算法的性能：基于全局分析的查询扩展算法、基于本体技术的查询扩展算法、全局分析和本体技术相结合的查询扩展算法。三种查询扩展算法分别简称为：全局分析、本体技术、全局分析+本体技术。

在信息检索领域，查准率（precision ）、查全率（recall ）和F值是评价系统性能的主要指标。查全率为搜索结果中符合查询条件的资源数量占总符合查询条件资源数量的比例。查准率为搜索结果中符合查询条件的资源数量占返回资源数量的比例。F 值为查全率和查准率的加权几何平均。F值将查全率和查准率结合在一起进行评价，防止出现查准率很高而查全率很低或者查全率很高而查准率很低的现象。F值反映系统的综合性能，该值越接近1越好。

搜索性能评价指标的计算公式分别为：

式（3）和（4）中，resourcerelevant为符合查询条件的总资源数量，resourceretrieval为返回资源数量，resourcerelevant∩resourceretrieval为返回结果中符合查询条件的资源数量。

仿真实验共发起了20次查询请求，其中C模式查询请求4次，O模式查询请求4次，混合模式查询请求12次，概念泛化和概念细化的层数均设定为1层。图3显示了上述三种算法20次查询请求的查全率，查询编号1至4为C模式查询请求，5至8为O模式查询请求，9至20为混合模式查询请求。从图3可以看出：前4个请求为C模式词汇，可借助本体进行查询扩展，本体技术的查全率明显优于全局分析的查全率。由于请求不包含O模式词汇，此时全局分析+本体技术的性能无法充分体现，查全率和本体技术的查全率持平；5至8为O模式查询词汇，无法借助本体进行查询扩展，全局分析的查全率明显优于本体技术的查全率。由于请求不包含C模式词汇，此时全局分析+本体技术的性能无法充分体现，查全率和全局分析的查全率持平；9至20为混合模式查询词汇，全局分析与本体技术各有优势，查全率基本持平，本体技术的查全率略高于全局分析的查全率。混合模式查询请求能充分发挥全局分析+本体技术的性能，因此查全率明显提高。在实际应用中，大多数搜索请求都为混合模式查询。

图3　三种算法的查全率

图4　三种算法的查准率

图5 三种算法的F值

图4显示了上述三种算法20次查询请求的查准率。从图4可以看出，三种算法的查准率性能表现与图3的查全率性能表现基本一致。全局分析+本体技术的查准率最高，另外两种算法次之。单独比较全局分析和本体技术两种算法发现：由于本体在精确语义表达方面的优势，使得无论是C模式查询，还是混合模式查询，本体技术的查准率都优于全局分析的查准率，而且差距比较明显。

图5显示了上述三种算法20次查询请求的F值。全局分析和本体技术相结合的查询扩展算法在兼顾二者优点的同时避开各自的缺点，因此全局分析+查询扩展的综合性能最好，比只采用全局分析的综合性能提高了12.9％，比只采用本体技术的综合性能提高了9.8％。

然后，再通过仿真实验分析概念泛化和概念细化的层数对本文提出的查询扩展性能的影响。将概念泛化和概念细化的层数分别设定为0、1、2、3、4，考察基于全局分析和本体技术的查询扩展算法的F值，结果如图6所示。0层表示不进行概念泛化或概念细化。从图6可以看出，进行1层、2层的概念细化和概念泛化可以明显提高查询扩展的性能，但是当概念泛化或概念细化的层数过多（大于2层），查询扩展的性能不但不会提高，反而下降，并且概念泛化的性能受层数影响较概念细化明显。主要原因是当概念泛化或概念细化的层数过多后，扩展出的概念与原始查询词汇的语义差距明显增大，概念泛化尤为明显。因此，在进行概念泛化，以1层为最佳，在进行概念细化时，最佳层数为1～2层。

图6　概念泛化和概念细化层数对查询扩展性能影响

结语

查询扩展可以生成更准确的查询请求，弥补用户查询信息不足的缺陷，提高搜索性能。用户查询请求往往遵循一些典型模式。本文首先对用户查询模式进行分析，根据查询模式的不同特点给出相应的查询扩展方法与策略，在此基础上，提出一种全局分析和本体技术相结合的查询扩展算法，该算法在兼顾二者优点的同时避开各自的缺点。仿真实验的结果表明，该算法的综合性能比全局分析的查询扩展算法的综合性能提高了12.9％，比基于本体技术的查询扩展算法的综合性能提高了9.8％。

全局分析和本体技术相结合的查询扩展算法的性能受多种因素影响。这些因素包括：（1）本体自身的合理性与完备性；（2）词汇-概念词典的准确度；（3）和用户交互过程中所获得信息的有效性。下一步将从这些影响因素入手，进一步提高全局分析和本体技术相结合的查询扩展算法的性能。

10.3969/j.issn.1001-8972.2015.09.024