基于用户意图识别的查询推荐研究

罗 成，刘奕群，张 敏，马少平，茹立云，张 阔

(智能技术与系统国家重点实验室；清华信息科学与技术国家实验室(筹)；清华大学 计算机系，北京，100084)

1 引言

过去的20年中，World Wide Web(以下简称Web)在全球化范围内获得了长足的发展。Web上的信息以传统网页、媒体文件(图片、音频、视频)、社区论坛、邮件列表、微博和博客等多种形式呈现，从数量上呈现了爆炸的趋势。面对如此规模庞大的Web信息，传统的检索方法已经无法满足人们的信息需求，给人们的生活和工作带来了无法想象的困难。

搜索引擎是指自动从Web上搜集信息，经过一定的整理以后，提供给用户进行查询的系统[1]。它的出现在一定程度上解决了针对海量信息检索和浏览的问题。在短短的20年里，搜索引擎相关的技术进步显著，同时极大地改变了人们获取信息的方式。

现有的用户和搜索引擎的交互过程一般如下：

• 用户分析自身的信息需求，概括查询意图。

• 用户进一步试图用一些关键字描述查询意图，并提交给搜索引擎。这一过程受限于用户自身的水平，可能发生信息丢失。

• 搜索引擎将根据用户提交的关键词查找索引，将查找结果按照相关性排序后返回给用户。

在依赖关键词进行检索的搜索引擎框架中，经常无法返回满足用户意图的相关结果。这一方面是因为Web上的信息量非常巨大，另外一方面是用户提交的查询意图通常非常短，所包含的信息量很少。有研究者对某中文搜索引擎大量的查询日志进行了统计，发现长度不超过3个词的查询数量占总查询数量的93.15%，平均长度仅为1.85个词[2]。这就使得搜索引擎很难准确地识别用户的具体查询意图，进而提供让用户满意的结果。如何帮助用户更准确地描述自己的信息需求，或者帮助搜索引擎更充分地理解用户的查询意图，成为搜索引擎重要且关键的技术之一。

在近年来的相关研究中，查询推荐相关技术成为解决这一问题的有效手段之一。在用户提交查询后，搜索引擎除了返回相关结果之外，还返回一个相关查询列表供用户选择，可以帮助用户更准确、更快捷地描述自己的查询意图，增加用户和搜索引擎再次交互的可能。目前几乎所有的商用搜索引擎都会在搜索结果页为用户提供查询推荐，并且这一方式也被用户所认同，据统计，有15.36%的用户查询会话中都包含对查询推荐结果的点击[3]。

由此可见，查询推荐相关的技术的研究，具有重要的研究价值和应用前景，吸引了当前学术界和工业界的广泛关注。然而，现有的商业搜索引擎中，大多从查询文本本身出发，对其进行同义改写和替换，或是选择和原查询文本类似的热门查询作为推荐，并没有关注原查询中潜在的用户意图。如果给出的查询推荐可以更准确地描述用户意图，搜索引擎就有可能有针对地调整自己的检索策略，把质量更高的页面放在相对靠前的位置。作者从用户意图识别的角度，就如何给出更加切合用户信息需求的查询推荐进行了一些研究，构建了一个完整的查询推荐流程。

2 相关研究综述

查询推荐方法吸引工业界和学术界关注已经有超过10年的时间，形成了一系列的研究成果，可以将其分为查询层次和词项层次的查询推荐方法。

查询层次的查询推荐方法通常将查询看成一个整体，和其他查询进行某种意义下的相似性度量，将最相似的结果作为查询推荐。其优点在于综合考虑了原查询的全部信息，给出的推荐更加可靠。经常用到的方法有查询流图(Query-Flow Graph)[4]，二部图上的随机漫步(Random Walk)[5]等。Zhang等人提出了一种将查询流图上的转移和文本相关性结合的一种查询推荐方法[6]。在查询流图上作者认为从一个节点到另外一个节点的转移可能以一个固定的比例衰减。两个查询间的相似性以所有会话中一个节点到另外一个节点的所有道路的权重加和来表示。Mei等人在2008年提出的一种在大规模的“查询-链接”二部图上基于Hitting Time进行查询推荐的方法[7]。Hitting Time可以直观理解为二部图上从一个查询顶点跳转到另外一个查询顶点的点击时间。如果将和用户查询相关的个性化信息一起放入二部图中，还可以做个性化的推荐。查询层次的方法缺陷是通常要求原查询和给出的推荐必须在之前的用户日志中出现过，很难对所有的查询都给出推荐。

词项层次的查询推荐通常把查询视为一个词的序列，然后对其中的元素进行替换、改写或者重组织等操作。经常用到的模型有词项转移图[8]、概念模式[9]等。词项层次的查询推荐优点在于几乎可以为任何查询给出推荐。Song等人提出了一种在不同的话题分类下基于词项转移图的查询推荐方法[8]。作者挖掘了用户查询行为中对查询中的词项进行修改的行为，在不同的分类话题下建立词项转移图，迭代计算每一个顶点的PageRank值。对于一个给定的查询，首先对其进行话题分类，根据其类别标签在相应的短语图上计算每一个词的最佳推荐，经过排序和过滤给出最终的推荐查询。概念模式是将用户给出的查询转换成一个概念模板，所谓概念，可以理解为一个类别。Cao等人提出了一种将查询概念模式和概念后缀树结合的内容敏感查询推荐框架[9]。概念模式树的每一个节点是一个概念，叶子节点对应着一个按照热门程度排序的后缀短语列表。当用户提交查询时，找到和其查询对应的概念模式，在概念后缀树上从根节点出发，找到叶子节点上最热门的词附在原查询后作为最终的查询推荐。词项层次的方法不足之处在于某一个词项可能只代表原查询含义的一部分，添加或者替换的词项可能和原查询无关。

从用户意图识别的角度出发，也有一些相关的工作。Liu等人在2011年提出了基于摘要点击模型进行用户意图挖掘的方法[3]，基于摘要点击信息对商业搜索引擎给出的查询推荐进行重新排序，从体现用户意图的角度取得了提高。Liu等人的尝试仅从摘要点击的角度挖掘优化商业搜索引擎提供的查询推荐结果，并没有构建完整的查询推荐流程。Sadikov 等人提出了一种结合文档点击和session共现特征，根据用户意图进行查询修改行为的聚类方法[10]。这样的聚类可以侧面描述用户的潜在意图，但是通常用户在搜索过程中遇到不满意的结果大多放弃搜索，因此用户修改查询的数据相对稀疏，该方法很难对大量的查询给出查询推荐。Mei等人利用Hitting Time进行查询推荐的方法[7]，可以加入用户的个人信息，在一定程度上可以进行用户信息需求的细化，也是一种间接的利用用户意图进行查询推荐的技术。

在已有的工作中，研究者大多关注查询之间的相似程度、利用文本、用户点击等特征进行推荐，并没有充分理解用户的真实查询意图，往往无法给出更加清晰表述信息需求的推荐结果。

论文工作的创新之处在于利用二部图上随机漫步方法产生规模较大的候选集合，结合摘要点击信息充分地考虑用户意图，并采用机器学习方法对其中可能的噪声进行识别，从而提升查询推荐的性能，协助用户更好地完成信息获取任务。

3 数据集合

3.1 用户行为数据

为了实现对大规模用户行为进行分析，给出查询推荐，我们在某商业搜索引擎公司的协助下收集了2012年的部分用户搜索引擎点击数据，总的规模为19.39亿条，选取的时间跨度在1个月之内。

3.2 测试查询数据构建

测试查询集合选取NTCIR的INTENT-1 和INTENT-2测试集，合并去重后共包含198个互不相同的查询。

针对查询意图的分类，Broder等人提出了导航类、信息类和事务类的分类标准[11]。我们将本文选取的测试查询集合和Broder等人抽样统计的结果进行了比较。

图1 本文查询数据集合分布

由图1，我们选取的查询集合与Broder等人的统计结果趋势基本一致，其中的比例差异可能是由于中英文用户使用搜索引擎的习惯差异导致，总体而言，可以认为是实际网络环境的可靠近似。

4 查询推荐候选生成

生成候选的查询推荐有多种方法。在真实的搜索引擎中，可以从文本特征、语义特征等多个角度生成推荐候选。与基于文本相似度给出的推荐候选相比，语义层面上给出的候选推荐与用户意图相关的可能性更大。从语义的角度出发，结合我们拥有的海量用户行为记录，建立查询流图[4]或者查询链接二部图[5]等都是常用的查询推荐的挖掘技术。这里我们采用二部图上的随机漫步方法进行候选查询的挖掘。基本假设是点击了相同或相似链接的查询具有一定的语义层次相关性。二部图上的随机漫步方法可以利用大量的真实的用户查询作为候选，为大量查询高效的生成候选推荐。同时，这样生成的查询推荐比较接近用户的意图；候选列表按照二部图上的转移概率排序，本身具有一定的参考意义；同时得到候选集合的规模大，之后结合用户意图信息进行重排序的空间较大。缺点是随机漫步方法可能无法为全部的查询给出推荐，我们可以通过扩大数据规模进行改善；可能带来一些噪音，但之后的重排序过程、机器学习方法噪音识别过程都可以对噪音进行有效地过滤和筛选，对整个查询推荐流程的影响不大。

4.1 “查询-链接”二部图

“查询-链接”二部图的顶点由两个互不相交的子集构成，一个子集为查询集合，包含用户提交的相关查询，另外一个集合为链接集合，为用户点击的所有链接。从查询q到链接u这条边的权重表明在用户行为数据集合中提交查询q，点击链接u的次数。

4.2 基于随机漫步的查询推荐

基于随机漫步的查询推荐过程，需要定义不同的查询节点间的转移概率。然后在“查询-链接”二部图上进行随机游走，选取到达概率最大的前若干个查询作为推荐的查询返回。

在二部图G=({V1,V2},E)上，首先定义从顶点i到相邻的顶点j的转移概率如式(1)所示。

其中，

其中wi,j为二部图上有向边(i,j)的权重；di是所有与顶点i相连的边的权重加和。

在此基础上，可以定义一个该二部图上的一个2步长的随机漫步过程：

这样，我们就对查询间的相似度给出了度量。

4.3 查询推荐结果与分析

通过“查询-链接”二部图上随机漫步的方法，对于198个查询，我们对其中的176个查询给出了推荐结果，其中161个查询的推荐结果数量多于10个。22个查询没有得到查询推荐结果，主要是这些查询比较冷门，在“查询-链接”二部图上没有相应的联通分支，这是二部图上随机漫步方法的一个局限。

表1 随机漫步方法查询推荐结果示例

分析表中的数据可以得出，对于“巨人”和“E话通”这两个查询，随机漫步方法可以给出相关的查询推荐，并且根据转移概率进行排序。但是这种方法给出的查询推荐也存在一些问题： 1)很多推荐的查询是对原查询的简单重复，比如“E话通”的推荐结果“e话通”，对于用户细化对查询意图的描述没有太大的帮助；2)查询的质量不稳定，例如，“巨人”查询推荐“juren”，和“E话通”的查询推荐“doshow”，都可以认为是一些表达模糊的低质量查询，随机漫步方法本身不能判断这种查询的质量。

针对上面的问题，一方面可以结合用户意图，对推荐列表进行重新排序，让高质量的推荐排在比较前的位置，从而提升推荐查询的质量；另外一方面可以利用机器学习的方法，训练模型，对低质量的推荐结果进行过滤。

5 基于用户意图的查询推荐

在用户和搜索引擎的单次交互中，搜索引擎很难把握用户的准确意图。通过对过去提交相同或者相似查询的用户行为进行分析，可以尽可能地接近当前用户的意图。搜索结果页上的摘要是用户进行相关性判断的依据，也隐含着迎合了用户意图的信息。

5.1 摘要点击和用户意图的关系

现有的通用搜索引擎，通常接受用户提供的一个查询词序列，返回一系列搜索结果，以标题和摘要作为主要的展现内容。

我们不难看出，在用户点击某条结果之前，并不能看到这条结果所链接到的页面的具体内容，只能看到结果的标题、摘要、链接地址和时间。

图2 搜索结果呈现方式示例

Liu等人在相关工作中提出以下两个假设[3]：

相关性的间接判定假设： 认为搜索引擎用户在点击结果之前，标题和摘要是用户判断相关性的最主要依据。

用户的群体智慧假设： 虽然单个用户的点击行为不足以判断查询和结果间的相关性，但是大量用户的点击行为为相关关系提供了可靠反馈。

在此基础上我们可以进一步假定，在某个查询的结果中，被较多用户点击的结果，其标题和摘要反映用户意图的可能性较大；在同一条结果的标题和摘要中，出现较多的词对用户的相关性判定发挥更重要的作用。将标题和摘要切分成词，不同的词在标题和摘要中对用户的吸引程度不同，可如果可以将其量化成一个权重，就可以对推荐的查询从满足用户意图的角度进行评价，对候选查询推荐重新排序。

5.2 摘要中词权重的计算

结合上述的两点假定，我们提出了一种利用词频和点击分布计算词得分的方法，同时考虑到了摘要和标题的重要性差异，假定标题在用户进行相关性判定时更重要一些。

对于一个查询Q，摘要中每一个词t的权重按照式(4)算出：

其中N表示从结果页上解析出的查询结果的数量。TF表示该词在标题和摘要总的词频，CDi表示第i条摘要在用户行为数据中的点击分布，既考虑到了单个搜索结果中，不同词的词频和权重不同，又考虑到了用户的点击偏好。为了解决词项出现的边际效应，对词频取对数，这也是文本检索中的常见的做法。

进一步的，需要考虑用户在浏览搜索结果中，对标题与摘要的信任程度可能不同，对摘要和标题的信息进行区分和整合：

实验中经过多次尝试，当λ=1.2时效果较好。

利用上面的产生式，我们为每一个查询都计算出了一个词权重列表，随机抽取了50个查询进行统计，平均每一个查询得到的有效词项个数为47.2个。

5.3 利用词权重列表进行重排序

得到词权重列表以后，我们可以对随机漫步方法给出的查询推荐列表进行重新排序。

对于一个查询Q，可以得到一个与其相关的词权重列表D，对于一个查询推荐QR，我们可以计算其得分，这里采用了线性加和的方法：

即查询推荐QR的得分等于所有在QR中出现且不在Q中出现的词权重之和，得分越高，意味着QR包含了越多权重不为0的词，或者包含了权重越高的词。按照查询推荐命中的词项得分进行重排序。

在表2的结果示例中，存在一些噪声，例如，查询“坐上火车去拉萨”中的“伤感唯美歌曲”、“拉萨歌曲”、“坐上火车+去拉萨歌曲”，和查询“貔貅”中的“开光方法”、“开光”、“pixiujiage”和“淘宝网”等。出现这种噪声的可能是：

1. 用户的点击较为稀疏，计算出的词项得分偶然性较大；

2. 查询为拼音或链接，可读性较差，并不能描述用户的信息需求；

表2 基于用户意图重排序推荐结果示例

3. 查询中包含错别字，不能很好的获得结果。

综合以上，如果可以采用机器学习的方法对候选列表进行过滤和筛选，可以进一步提高其质量。

6 基于分类的查询推荐过滤算法

对于一个给定的查询，利用“查询-链接”二部图上的随机漫步方法挖掘出的查询推荐中，很有可能包含一些低质量的结果，利用摘要点击信息依然无法对查询的质量进行甄别。如果可以构建一个分类器，对查询推荐的质量进行分类，结合前面的候选查询生成算法，就可以自动生成查询推荐。

6.1 特征抽取

对于样本中的每一个查询，我们抽取了10个特征：

特征1： 提交过该查询的独立用户数；

特征2： 查询结果中，被用户点击过的独立目标地址数；

特征3： 总共被查询的次数；

特征4： 推荐查询对原查询的覆盖率，即原查询中的字符在推荐查询中出现的比例；

特征5： 推荐查询和原查询的长度比值；

特征6： 推荐查询比原查询多出字母数；

特征7： 推荐查询比原查询多出数字数；

特征8： 推荐查询相当于原查询的转移概率；

特征9： 推荐查询命中的原查询摘要词项数目；

特征10： 推荐查询基于原查询的摘要词权重表的得分。

上面提取的10个特征来源于三点考虑：

• 推荐查询相关的真实用户行为(特征1、特征2和特征3)： 针对推荐候选中的一些冷门查询、包含错别字的查询等。

• 推荐查询于原查询的文本特征(特征4、特征5、特征6、特征7和特征8)： 针对候选推荐中的超链接、长串数字等不可读的情况，以及和原查询文本无关等情况。

• 推荐查询在原查询的摘要词权重表上的表现(特征9和特征10)： 针对查询对用户意图的满足情况。

实际构建数据集合时，设计了一些对照实验，具体如下：

• 不使用摘要词特征的数据集，即在上面的10个特征中，只使用特征1～特征8，不包含特征9和特征10，这样的设计是想考察有摘要词特征和无摘要特征带来的性能差异；

• 使用摘要词权重表中的前k条结果，这样设计的考虑主要是，一些查询的摘要词权重表可能非常的长，得分越低的词说明其出现频度越少，和查询词之间的相关度越低，设置这一组实验可以分析出大概用多少特征是合适的。

综合以上，我们总共构造了下面17个数据集：

• 不使用摘要词特征；

• 使用摘要词特征，其中k=1,2,3,4,5,6,7,8,9,10,20,30,40,50,100和使用所有的摘要词权重。

6.2 利用支持向量机构建分类器

支持向量机(Support Vector Machine)[12]是一种广泛使用的监督式的学习方法，广泛应用于解决小样本、非线性和高维模式识别问题。论文工作中选取支持向量机构建分类器。

7 实验

7.1 基于用户意图的查询推荐

评价指标借鉴了信息检索相关的评价指标中MAP(Mean Average Precison)和NDCG(Normalized Discounted Cumulative Gain)[13]两项指标。

MAP的计算公式如式(6)所示：

NDCG的计算公式如式(7)所示：

随机选取了176个查询中的50个，对其重排序前后的前10条结果和某商业搜索引擎结果页上呈现的查询推荐采用Pooling[14]方法进行三级手工标注，将标注为“2”的视为“好的查询标注”，将标注为“1”和“0”的视为“不好的查询标注”。在上述两个指标上进行评价，结果如图3所示。

图3 查询推荐结果比较

可以看到，加入摘要点击特征挖掘用户行为进行重排序后，在随机漫步结果与搜索引擎呈现结果两组数据上都取得了不同程度的提高。在某商业搜索引擎呈现的查询推荐数据上提高有限，主要是搜索引擎呈现数据只有9个结果，重排序的提升空间不大。

另外，我们对某搜索引擎2012年1月至3月中用户点击查询推荐的情况进行了统计，并与随机漫步和重排序后的结果列表进行了匹配，选取了匹配率50%及以上，单个查询匹配点击数20以上的62个查询，共涵盖用户点击54 424次。经过统计，用户在不同排序位置上的平均点击分布如图4所示。

图4 优化前后用户点击分布的比较

由上图可以看出，经过重排序后的列表，用户点击的分布更加集中在整个列表靠前的位置。这说明利用摘要点击的信息可以有效地挖掘用户的潜在意图。

7.2 基于分类的查询推荐过滤

实验中选取了198个查询中的70个查询，将他们的候选推荐作为样例。如果某一个查询的候选推荐超过30个，只取前30个作为样例，总共获得 2 030个样例。

对于其中的每一个查询推荐，采取和之前一致的Pooling方法进行手工三级标注。最终得到两种样例的比例为1 107∶923，基本平衡。

支持向量机选取台湾大学林智仁(Lin Chih-Jen)开发的LIBSVM[15]。

在交叉验证比为3的前提下，不加摘要点击特征得到的分类结果为Precision 0.789，Recall 0.686，F-Measure 0.640。在同样的实验设置下，加入点击特征后分类的结果如图5所示。

图5 加入点击特征前后分类性能比较

对比结果我们可以看到，加入摘要点击特征后，分类器的性能在Recall和F-Measure上获得较显著的提升，分析具体结果，主要原因是对于负例(不好的推荐查询)分类Recall提升明显。

在加入摘要点击特征后，在k =9时分类器Precision最好，之后受到影响，这主要是因为摘要此权重表中越靠后的词可靠性越差，k=50之后分类器Precision获得了一定的提升，这主要是因为权重词表中靠后的词权重值非常小，此时对特征9的影响比较小，反而对特征10的影响显著，对分类器的性能造成了较大的影响。

8 结论

论文工作采用大规模“查询-链接”二部图上随机漫步的方法生成了查询推荐候选列表。在此基础上充分考虑用户的查询意图，结合用户点击摘要的信息，为每一个查询构建一个词项得分表，以此为依据进行候选列表重排序。实验证明该方法可以从迎合用户意图的角度提供更高质量的查询推荐。针对推荐列表中的噪声，进一步从用户行为、文本特征和用户意图三个角度提取特征，利用支持向量机构造分类器，对噪声进行识别和过滤，精度较高。从查询推荐候选生成、根据用户意图进行优化到利用分类器进行噪声识别，形成了一个完整的查询推荐流程。

回顾整个流程中的一些不足之处，还有很多进一步工作可以继续。

首先，可以考虑到结果页位置的偏执，采用点击模型(Click Model)优化用户意图识别过程。

其次，可以采取一些规则，对二部图上随机漫步得到的集合进行筛选和过滤，得到质量更高的候选集合。

最后，可以利用网络百科等知识，对查询推荐进行多样化处理，使得查询推荐覆盖尽量多的相关子话题。

[1] 维基百科.Web search engine[EB/OL]. [2012年6月5日]. http://en.wikipedia.org/wiki/Web_search_engine.

[2] 余慧佳, 刘奕群, 张敏, 等. 基于大规模日志分析的网络搜索引擎用户行为研究[C].第三届学生计算语言学研讨会, 中国辽宁沈阳, 2006.

[3] Liu Y, Miao J, Zhang M, et al. How do users describe their information need: Query recommendation based on snippet click model. Expert Systems with Applications, 2011,38(11):13847-13856.

[4] Boldi P, Bonchi F, Castillo C, et al. The query-flow graph: model and applications[C]//Proceedings of CIKM ’08, New York, NY, USA, 2008.

[5] Craswell N, Szummer M. Random walks on the click graph[C]//Proceedings of SIGIR ’07, New York, NY, USA, 2007.

[6] Zhang Z, Nasraoui O. Mining search engine query logs for social filtering-based query recommendation[J]. Applied Soft Computing, 2008,8(4):1326-1334.

[7] Mei Q, Zhou D, Church K. Query suggestion using hitting time[C]//Proceedings of CIKM ’08, New York, NY, USA, 2008.

[8] Song Y, Zhou D, He L. Query suggestion by constructing term-transition graphs[C]//Proceedings of WSDM ’12, New York, NY, USA, 2012.

[9] Cao H, Jiang D, Pei J, et al. Context-aware query suggestion by mining click-through and session data[C]//Proceedings of KDD ’08, New York, NY, USA, 2008.

[10] Sadikov E, Madhavan J, Wang L, et al. Clustering query refinements by user intent[C]//Proceedings of the 19th international conference on World wide web. ACM, 2010: 841-850.

[11] Broder A. A taxonomy of web search[C], 2002.

[12] Boser B E, Guyon I M, Vapnik V N. A training algorithm for optimal margin classifiers[C]//Proceedings of COLT ’92, New York, NY, USA, 1992.

[13] Rvelin K J A, Kek A L A， Inen J. Cumulated gain-based evaluation of IR techniques[J]. ACM Transactions on Information Systems (TOIS), 2002,20(4):422-446.

[14] Jones K S, van Rijsbergen C J. Information retrieval test collections[J]. Journal of documentation, 1976,32(1):59-75.

[15] Chang C C, Lin C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011,2(3):27.