基于流形排序的查询推荐方法

朱小飞，郭嘉丰，程学旗，杜 攀

(1. 中国科学院 计算技术研究所, 北京 100190;2. 中国科学院 研究生院, 北京 100049; 3. 重庆理工大学 数理学院，重庆 400054)

1 引文

目前，互联网上存储了大量的信息，搜索引擎已经成为用户访问这些信息最有效的途径。用户通过输入想要查询的关键字到搜索引擎，然后搜索引擎返回搜索结果供用户使用。然而，构造一个合适的查询并不是一件轻松的事情，一方面因为查询通常比较短[1](1～2个词)并且存在歧义性[2](例如java，apple等)，另一方面，由于用户对所查询的内容不熟悉，使得自身对要查询什么内容不清楚，例如用户输入harry potter，他可能是对名字叫harry potter的一款游戏感兴趣，或者对同名的电影感兴趣，也可能对同名的小说感兴趣。如何帮助用户更好的找到需要的信息已经成为一个至关重要的问题。

查询推荐通过向用户推荐相关的查询，以帮助用户构造更有效的查询，目前已经成为一个十分重要的研究方向。一些著名的搜索引擎公司(如Google和Yahoo)开始为用户提供查询推荐系统，以帮助用户更方便地找到所需要的信息。

传统的查询推荐方法主要关注于向用户推荐相关的查询，通过度量候选查询与用户所提交查询的相关程度，对候选查询进行排序，并推荐最相关的前k个查询给用户。这种方法可以有效地帮助用户构造更恰当的查询，但同时也存在一些问题：(1) 相关性度量问题。传统查询推荐方法通常在欧式空间上计算查询之间的相似性，但由于查询日志中的查询具有高维稀疏性，传统的相似度度量方法往往不能很好的反应用户查询之间的相关性。例如，在基于关键词来度量查询之间的相似性时，由于两个相关的查询(如“national basketball association”和“nba”)之间没有相同的查询关键词，从而被认为是不相关；或者在基于用户点击的URL来计算查询之间的相似性时，两个相关的查询因为没有点击相同的URL(因用户结果点击的稀疏性)，会导致其被认为不相关。(2)冗余性问题。由于仅关注候选查询与源查询的相关性，使得传统的推荐方法所推荐的查询存在较大的冗余性(推荐的查询之间的差异性小)，例如当用户输入查询“abc”时，系统可能会同时向用户推荐“abc television”和“abc tv”，而这两个查询其实是表达了相同的意思。

为了避免传统查询推荐方法中存在的问题，已有研究人员提出一些解决方法，例如Mei等人[3]基于随机游走(random walk)提出了通过计算各候选查询到源查询的游走时间(hitting time)来进行查询推荐(文中使用Hitting-time Ranking来表示)，该方法可以有效地推荐长尾(long tail)的查询给用户，以降低查询推荐的冗余性。然而通过这种方法获得的长尾查询往往不常见，相关性也无法得到保证，因此会影响到推荐的有效性和实用性。

针对已有查询推荐方法的不足，我们提出了一种基于流形排序的查询推荐方法(文中使用Manifold Ranking来表示)。通过把用户查询建模在流形结构上，我们可以利用查询数据内在流形结构来获得查询之间的相关性，从而有效避免传统方法的相关性度量问题。此外，基于查询的流形结构，我们使用流形排序算法来对候选查询进行排序和推荐，由于各查询的排序得分不再仅来自于源查询，同时也来自于其邻居查询，从而使得那些结构上与源查询相近并且具有代表性的查询(那些具有较多邻居结点的查询)获得更大的排序得分。由此可见，和Hitting-time Ranking不同，Manifold Ranking是通过提升那些结构上具有代表性的查询来减小查询推荐的冗余性。

我们使用了一个大规模商业搜索引擎用户查询日志来进行实验，该查询日志包括约1 500万条用户查询记录。我们将Manifold Ranking与两种基准方法：基于传统的相似性排序算法(Naïve Ranking)和Hitting-time Ranking进行比较，并通过一个自动评价机制来对各方法所推荐查询的相关性和差异性进行评价。实验结果表明，Manifold Ranking方法在保持较高相关性的条件下，明显地提高了查询推荐的差异性，在整体上要优于Naïve Ranking和Hitting-time Ranking方法。

本文的组织结构如下：第2节介绍相关的研究工作，基于Manifold Ranking的查询推荐方法将在第3节进行讨论，第4节给出了实验结果及其评价，结论将在最后一节给出。

2 相关工作

查询日志作为一种用户产生的数据，是众多用户在使用搜索引擎进行查询操作时的日志记录，其包含大量有价值的信息，被称为“大众智慧”(wisdom of crowds)[4]。近年来，许多研究工作开始使用查询日志中的click-through data来挖掘查询之间的语义相关关系，这种相关关系可以被用来进行查询推荐。例如，Beeferman等人[5]通过对query-URL二部图上使用凝聚聚类算法来发现相关查询；Wen等人[6]同时考虑使用click-through data和查询及文档的内容信息来确定相似查询。Li等人[7]提出了一个两阶段的查询推荐方法：发现阶段和排序阶段。在发现阶段，使用基于query-URL向量来计算查询之间的相似度；在排序阶段，使用层次凝聚聚类算法来对相似查询进行排序。Baeza-Yates等人[8]基于query-URL二部图定义了3种连边类型：identical cover，strict complete cover和partial cover，并以此计算查询间的语义关系。以上研究工作共同的特点是仅关注于推荐相关的查询。Mei等人[3]在query-URL二部图上使用随机游走方法，依据各候选查询到源查询的游走时间来对查询进行排序，可以有效的推荐长尾的查询，但是其缺点在于：由于推荐长尾的查询可能与源查询相关程度不高，降低了查询推荐的相关性。

Manifold Ranking是由Zhou等人[9-10]首先提出，与传统的欧式空间上直接计算查询之间的相似性不同，该方法通过利用大规模数据内在的全局流形结构来计算排序得分。直观的解释为：首先构造一个带权网络，并且分配给源节点一个正的得分，其他待排序节点的得分设为0，然后每一个节点将其自身得分传播到邻居节点直到整个网络达到平衡状态。除源节点外的所有节点按照最终得分大小进行排序(得分越大，排序越靠前)。目前Manifold Ranking已经被用来对图像或文档摘要进行排序，并取得很好的效果。例如，He等人[11]基于Manifold Ranking进行图像排序，其利用所有数据之间的关系，来测量输入查询与所有图片的相关性。Wan[12]等人使用Manifold Ranking来进行主题相关的多文档摘要，通过利用文档中所有句子相关性以及句子与主题的相关性，并基于贪心算法来实现有差异的文档摘要。

3 我们的工作

在这一部分的内容中，我们详细描述了如何使用click-through data来构造查询的流形结构，然后在此基础上使用Manifold Ranking方法来进行查询推荐的过程。

3.1 基本概念

给定一组查询χ={x0,x1,…,xn}⊂m，第一个查询x0表示源查询，其他查询xi(1≤i≤n)为候选查询。令d:χ×χ→表示χ上的一个度量，其中d(xi,xj)表示查询xi和xj的距离(如欧式距离)。f:χ→为排序函数，其为每一个查询xi(0≤i≤n)计算一个排序得分fi，这里我们可以将f看成是一个向量f=[f0,f1,…,fn]T。同时，定义向量y=[y0,y1,…,yn]T，其中y0=1(x0是源查询)，yi=0(1≤i≤n)。

3.2 构造查询的流形结构

图1 query-URL二部图

(1)

wij=e-d(xi,xj)2/2σ2

(2)

令wii=0。此外，若带权网络中边所对应的两个查询不是互为k近邻 (k=50)，则删除此边，以保持带权网络的稀疏性。至此，我们得到了一个查询带权网络(即查询流形结构)，其可以用一个仿射矩阵W=[wij]来描述。Manifold Ranking 算法如下：

1. Compute the pair-wise similarity valueswijbetween queriesiandj, and then construct a weighted network. The affinity matrixWis defined byW=[wij].

2. Symmetrically normalizeWbyS=D-1/2WD-1/2, in whichDis the diagonal matrix with (i,i)-element equal to the sum of thei-th row ofW.

3. Iteratef(t+1)=αSf(t)+(1-α)yuntil convergence, whereαis a parameter in [0,1), started withf(0)=0.

3.3 Manifold Ranking 方法

基于以上定义的查询流形结构，我们使用流形排序算法来进行查询排序和推荐。首先，我们对W进行对称规范化：S=D-1/2WD-1/2，其中D为对角矩阵，其对角元素分别为W各行元素之和。然后，按照下面的迭代公式：

f(t+1)=αSf(t)+(1-α)y

(3)

迭代至f收敛。其中，α用来控制来自于先验的得分和来自于结构上相邻的结点得分对最终排序得分的贡献，α值越大表示来自于相邻的节点得分贡献所占比例越大(α∈[0,1))。

Manifold Ranking的过程可以形象地描述为：首先构造一个带权网络，网络中每一个节点对应于一个查询；初始化时，给源查询赋以一个正的排序得分，其余候选查询的排序得分为0；网络中所有的节点将其得分传播给与其相邻的节点，当网络达到全局平衡状态时，传播过程停止；所有候选查询的得分将被用来对候选查询进行排序，并将排序最前的k个候选查询推荐给用户。Manifold Ranking算法的详细过程，文献[9]中证明了f最终会收敛到:

f*=β(I-αS)-1y

(4)

其中β=1-α，虽然可以直接使用(4)式来计算f*，但是由于涉及到计算逆矩阵(I-αS)-1，当数据规模较大时，需要的计算开销很大，因此与大多数研究工作[10-11]一样，我们这里选择使用迭代方式来计算f*。

此外，为了减小计算开销同时又不影响算法的有效性，我们从源查询出发使用广度优先搜索构造一个子图，直到子图中的查询节点达到预先指定的数目。子图的每一个节点(除源查询节点外)可以看成是源查询的一个候选查询，那些不在子图中的节点，由于离源查询节点足够远，以至于不可能被推荐给用户，将这部分节点去除，不会影响实际查询推荐的效果，但可以有效的减小算法计算开销。

4 实验结果及评价

4.1 数据集

我们使用一个商业搜索引擎的查询日志作为数据集，该查询日志记录了2006年5月1日至2006年5月31日期间的1 500万条查询。对于每一个查询，日志中记录其相应的信息，包括查询ID，查询词本身，所点击的URL，URL的位置信息，时间戳，用户Session ID，URL在结果页面中的排序，以及返回的结果数目。我们对查询日志进行预处理：只保留英文查询，并用空格替代查询中的标点符号，不执行词干还原和去除停用词的操作。为了减小噪音数据带来的影响，对于每个查询要求用户的点击次数不能小于3次。表1是所获得的query-URL二部图的统计信息。

表1 query-URL二部图的统计信息

4.2 评价指标

评价查询推荐是一件十分困难的事情，因为对于一个查询来说并不存在某种标准的推荐结果。为了使评价结果更为客观合理，这里我们采用了一种自动评价的策略。该策略使用开放式分类目录搜索系统ODP (the Open Directory Project)和Google的检索结果作为评价数据资源，对查询推荐结果的相关性和差异性进行评价。ODP是目前最大的人工编制的分类检索系统，已经被一些研究人员用来作为评价数据，例如Baykan等人[13]使用ODP作为URL主题类别信息来评价分类结果，Baeza-Yates等人[8]使用其评价查询的语义相关性。

4.2.1 相关性指标

对于ODP中的两个类别ci和cj，我们定义其相关度为类别的相同前缀长度与类别最大长度的商，形式化的表示为s(ci,cj)=|l(ci,cj)|/max{|ci|,|cj|}，其中|l(ci,cj)|为类别ci和cj相同前缀长度，|c|为类别c的长度。举例来讲，两个目录“Arts/Television/News” 和“Arts/Television/Stations/North_America/United_States”的相关度为2/5。因为其相同前缀为“Arts/Television/”，长度为2，而最大类别为“Arts/Television/Stations/North_America/United_States”，长度为5。

对于每个查询，在抓取Google Directory中前k个ODP目录作为该查询对应的类别集合，设C和C′分别为查询q和q′所对应的ODP类别集合，类似于文献[8]，我们用类别集合C与C′之间最相似的两个类别的相关度来衡量查询q和q′相关性。形式化表示为:

(5)

因此，对于给定的源查询q，其推荐查询结果的相关性指标定义为：所有推荐查询与q的平均相关性，形式化表示为:

(6)

其中S为源查询q的推荐查询集合，|S|为推荐查询集合中查询数目。

4.2.2 差异性指标

对于每个查询q，我们抓取Google前k个搜索结果的URL，作为查询q对应的URL集合。查询q和q′的差异度可以定义为：查询q和q′的URL集合中相异的URL的数目所占的比例，形式化表示为：d(q,q′)=1-|o(q,q′)|/k，其中|o(q,q′)|是查询q和q′的URL集合中相同URL的数目。因此，对于给定的源查询q，其推荐查询结果的差异性指标定义为：所有推荐查询两两之间的平均差异度，形式化表示为:

(7)

其中S为源查询q的推荐查询集合，|S|为推荐查询集合中查询数目。

4.3 实验结果及分析

我们随机抽取了150个查询作为测试样本，类似于文献[14]，我们要求这些查询的各自总的URL点击次数介于700至15 000次之间，这样做的目的是为了避免选择那些过于频繁出现的查询(例如www, car, book等查询，因为对其进行推荐没有实质意义)和过于不频繁出现的查询(查询日志中不存在可以推荐的查询)。其他参数设置为：算法迭代的次数设置为30, α=0.99, σ=1.25。

我们将基于Manifold Ranking的查询推荐方法，与另外两种查询推荐方法(Naïve Ranking，Hitting-time Ranking)进行了实验比较，实验结果分别显示在表2和表3*注：我们没有列出推荐数目为1的差异性指标，因为差异性指标是计算推荐查询两两之间的平均差异度，当推荐数目为1时，计算出来的差异性指标没有评价意义。中。表2是对三种不同方法的相关性指标进行比较，从表2中我们可以看到Manifold Ranking与Naïve Ranking的查询推荐结果在相关性指标方面接近相同(Naïve Ranking的平均相关性指标为0.891，Manifold Ranking平均相关性指标为0.898)；而Hitting-time Ranking的查询推荐结果在相关性指标方面要明显低于前两种方法(Hitting-time的平均相关性指标只有0.859)，这主要是因为Hitting-time Ranking方法过于强调推荐长尾的查询，其计算候选查询到源查询的游走时间来作为推荐依据，而忽略了这样一个事实：候选查询到源查询的游走时间的值小，并不意味着源查询到候选查询的游走时间的值也小，这就造成推荐的查询与源查询相关性不高。表3是对三种不同方法的差异性指标(所推荐查询的冗余性越大，其差异性指标越低)进行比较，从表3中我们可以看到Manifold Ranking与Hitting-time Ranking的查询推荐结果在差异性指标方面要显著高于Naïve Ranking方法(Hitting-time Ranking与Manifold Ranking的平均差异性指标比Naïve Ranking方法分别提高了 4.9 和2.1个百分点)。从差异性指标比较的结果来讲，Hitting-time Ranking要优于Manifold Ranking的推荐结果。但是如前面分析的结果所示，Hitting-time Ranking的平均相关性指标比Naïve Ranking低了3.9个百分点，而Manifold Ranking平均相关性指标和Naïve Ranking基本相同。从查询推荐的角度来讲，我们希望所推荐的查询与源查询尽可能相关，同时所推荐的查询之间又尽可能保持差异性。考虑查询推荐的相关性与差异性，我们可以得到以下结论：Manifold Ranking其在不损失相关性的条件下，明显的提高了查询推荐的差异性，整体上要优于Naïve Ranking和Hitting-time Ranking。

表2 三种查询推荐方法(Naïve Ranking, Hitting-timeRanking,Manifold Ranking)在不同推荐数目下相关性指标的比较

表3 三种查询推荐方法(Naïve Ranking, Hitting-timeRanking,Manifold Ranking)在不同推荐数目下差异性指标的比较

5 结论

本文中，我们提出了一种基于流形排序的查询推荐方法，该方法通过利用查询数据内在全局的流形结构来进行查询推荐，避免了传统查询推荐方法在相关性度量方面和冗余性方面的不足。与现有Hitting-time Ranking相比，Manifold Ranking通过提升结构上具有代表性的查询，从而使得所推荐的查询与源查询差异性得到的提高，同时保持较高的相关性。在一个大规模商业搜索引擎查询日志上的实验结果表明，Manifold Ranking要明显优于两种基准方法(Naïve Ranking和Hitting-time Ranking)。

[1] H. Cui, J.-R. Wen, J.-Y. Nie, and et al. Probabilistic query expansion using query logs[C]//WWW ’02, 2002: 325-332.

[2] J.-R. Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine[C]//WWW ’01, 2001: 162-168.

[3] Q. Mei, D. Zhou, and K. Church. Query suggestion using hitting time[C]//CIKM ’08, 2008: 469-478.

[4] J. Surowiecki. The wisdom of crowds: why the many are smarter than the few and how collective wisdom shapes business[C]//Doubleday, Reading, MA, 2004.

[5] D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log [C]//KDD ’00, 2000: 407-416.

[6] J.-R.Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine[C]//WWW ’01, 2001: 162-168.

[7] L. Li, Z. Yang, and et al. Query-url bipartite based approach to personalized query recommendation[C]//AAAI’08, 2008: 1189-1194.

[8] R. Baeza-Yates and A. Tiberi. Extracting semantic relations from query logs[C]//KDD ’07, 2007: 76-85.

[9] D. Zhou, O. Bousquet, T. N. Lal, and et al. Learning with local and global consistency[C]//NIPS’03, 2003.

[10] D. Zhou, J. Weston, A. Gretton, and et al. Ranking on data manifolds[C]//NIPS’03, 2003.

[11] J. He, M. Li, H.-J. Zhang, and et al. Manifold-ranking based image retrieval[C]//MULTIMEDIA’04, 2004: 9-16.

[12] X. Wan, J. Yang, and J. Xiao. Manifold-ranking based topic-focused multi-document summarization[C]//IJCAI’07, 2007: 2903-2908.

[13] E. Baykan, M. Henzinger, L. Marian, and I. Weber. Purely url-based topic classification[C]//WWW ’09, 2009: 1109-1110.

[14] P. Boldi, F. Bonchi, C. Castillo, and et al. Query suggestions using query-flow graphs[C]//WSCD ’09, 2009: 56-63.