基于加权SimRank的中文查询推荐研究

李亚楠,许 晟,王 斌

(1.中国科学院计算技术研究所,北京100190;2.中国科学院研究生院,北京100049)

1 引言

目前搜索引擎采用的主要交互方式是用户自主输入查询,检索系统根据输入的查询提供检索结果。但是,很多时候用户难以精确表达其意图。研究表明,用户输入的查询通常较短[1],只有25%的查询能清晰表达用户的意图[2]。为了帮助用户完善查询,查询推荐(Query Suggestion)被广泛用于向用户推荐若干与用户输入查询相关的查询,其既方便了用户构造查询,也帮助搜索引擎更准确地定位到用户的检索意图。在搜索引擎中广泛使用的“相关搜索”就属于查询推荐技术的一个实际应用。此外,查询推荐所用的相关技术不仅局限于搜索引擎,也广泛运用在计算广告、电子商务中的商品推荐等应用中,具有广泛的应用价值。

查询推荐的目的在于向用户推荐与其输入查询相关的其他查询。目前,查询推荐主要通过查询间的共有属性直接计算查询间的相关度,例如查询共同出现在同一搜索过程的次数[3-4]、查询共有的点击URL数[5-6]、查询间的文本相似度[7-8]等。尽管这些方法在一些查询上取得了好的推荐结果,然而由于用户查询具有多样性(查询日志中往往包含几千万甚至上亿不同的查询)、稀疏性(多数查询出现次数很少,可利用属性信息很有限)、歧义性(一些属性特征具有歧义,例如“汽车引擎”和“搜索引擎”都包含特征词“引擎”,意义却不相关),很多时候,直接根据属性特征计算查询间相关度无法给出有效的推荐结果。

很多查询之间存在隐含或间接联系,两个不能直接匹配的相关查询往往有着相同或相似的相关查询。例如“李彦宏”与“李开复”均与“搜索引擎公司”有关因而两者相似。基于这一简单思想,本文将查询映射到一个查询关系图中,图中节点表示查询,边表示查询中某种直接联系。而后,根据结构相似度算法并针对查询推荐应用问题,提出加权Sim Rank(简称WSimRank)计算图中查询(节点)间相似度。对查询对(qi,qj)间的相似度S(qi,qj),WSim Rank根据查询qi和查询qj各自邻居查询之间的相似度计算S(qi,qj)。WSim Rank综合利用了多个查询的相关属性特征信息计算两个查询间相似度,因此一定程度上克服了查询的多样性、稀疏性和歧义性带来的问题。

在大规模真实搜索引擎日志上,我们实现了几种近年来提出的查询推荐方法并将它们与基于Sim Rank和WSimRank的方法对比。实验结果表明,WSim Rank在查询推荐覆盖率、相关性等各项评价指标上均优于其他方法,其MAP接近0.9。

本文的主要贡献在于：

◦有别于以往方法直接计算查询间相似度,本文基于查询间直接属性关联建立起一个查询关系图,将查询推荐问题转化成一个有向带权图上的节点相似度问题,利用查询间直接联系挖掘出相关查询间的间接联系。

◦本文引入一个通用的基于图结构的相似度算法——SimRank——来解决查询推荐问题,并对它进行改造得到WSimRank算法,它在计算上收敛,并且大幅提高了推荐查询的相关性,相对于Sim-Rank,WSim Rank使得MAP提高了42.2%。

◦针对WSimRank在实际使用中面临的运行效率问题提出优化措施,将其计算过程转化成一个状态层次图的搜索遍历求和问题,并采用动态规划思想和剪枝策略优化了运行空间和时间,同时提高了结果精度和运行效率。

本文内容将按如下方式组织：第2节介绍查询推荐的相关工作;第3节说明查询关系图的构造;第4节给出Sim Rank算法;第5节阐述WSim Rank及其优化方法;第6节展示实验结果和分析;最后,本文在第7节进行总结。

2 相关工作

根据文献[4],查询推荐技术根据推荐内容的来源分为两类：基于文档的方法和基于日志的方法。基于文档的方法从文档中抽取查询相关词并构造推荐查询。基于日志的方法从搜索引擎查询日志中查找与当前用户查询相关的其他查询作为推荐。

基于文档的方法包括伪相关反馈[10]、隐性语义索引(Latent Semantic Index)[11]等从文档中寻找查询相关词的方法。传统的基于文档的查询扩展和查询重构方法也可以用于查询推荐。这些方法几乎可以处理各种查询,即便对于罕见查询,只要能找到其相关的文档,也同样可以处理,但是找出查询相关文档本身又是一个问题,会引入不相关文档从而降低准确度。此外,有研究工作[12]采用词典(例如WordNet)、人工编辑语料(如 Wikipedia、Open Directory Pro ject)或其他资源产生查询相关词进行查询推荐。这类方法推荐结果往往比较准确,但是难以处理那些尚未编辑的新出现词语,而新词却在用户搜索中占很大比例。

即便基于文档的方法发现了查询相关词,如何用这些相关词构造出符合用户习惯的查询依然是个问题。而搜索引擎日志本身就包含了大量构造完整的查询,并且从中可以挖掘出查询间的各种联系,因此近几年的查询推荐主要采用基于日志的方法。根据所用的查询属性,基于日志的方法主要分为三类：基于查询内容的方法[7-8]、基于点击 URL的方法[5-6]、基于Session的方法[3-4,13]。基于查询内容的方法利用查询间的文本相似度计算查询相关度,查询文本可以包括查询所对应用户点击结果的锚文本、摘要等信息。基于点击URL的方法利用两查询上相同或相似的点击URL作为特征计算两查询间的相关度。基于Session的方法根据两查询在同一搜索过程(Session)中共现的次数计算相关度。基于这些特征,多类算法被用于进行查询推荐,包括传统的IR模型[5,8]、数据挖掘方法[3]、机器学习[13]、基于查询—点击URL二分图的图算法[6]、以及基于规则的方法[4]。

结构相似度利用对象所处的图或树的结构计算对象间相似度。近年来,结构相似度已经成为数据库模式匹配、协同过滤、链接分析等领域的热门研究方向。Antonellis等人[14]提出一种基于改进Sim-Rank的广告搜索方法。不同于上述算法实验中用到的网页、论文引用等数据,查询间没有显式的链接关系。因此,本文首先引入查询关系图表示不同查询间的联系,进而构造适合查询关系图的结构相似度算法WSim RAnk衡量查询间的相关度。

3 查询关系图

查询关系图 Gq=是一个有向图,Vq={v}是节点集合,每个节点v表示一个查询,Eq={e}是边集合,边e=(v→w)表示查询v到查询w的某种关联。边权重 ω(v→w)的大小反映了查询v到查询w之间联系的强弱;若边e不存在,ω(v→w)=0。查询关系图中的边可以根据查询内容、点击 URL、Session等查询属性构造。实验表明：基于查询内容建立起的查询图连通分支很多,而分支内的子图又往往完全连通,几乎没有可挖掘的间接联系;点击URL在检索结果不理想时很稀疏,因而对需要推荐的困难查询反而难以处理。本文采用基于Session的方法,从Session中挖掘查询之间的关系。

Session具有两个基本性质：(1)同一Session中的查询具有很高的相似性。Session是同一用户为了某一特定搜索意图进行的一系列活动,因而同一个Session中的查询都是语义相关的。(2)Session中的前后查询具有“跳转性”。不同用户重构的查询是不同的,所以这种前后查询跳转不是确定的,而是带有某种概率。跳转到某个查询的概率越大,说明这个查询相对于前一个查询越相关、越完善。具体地,查询关系图基于以下步骤构造：

(1)对搜索引擎查询日志进行Session划分,本文采用文献[15]中的方法。

(2)对于Session中出现的每一个查询,在查询关系图中增加一个节点。

(3)对于Session中的每个查询,建立从它到随后两个重构查询的有向边,边的初始权重设置为1,若边已建立,权重加1。

(4)对每个节点的入边权重归一化,即对节点v,使得 ∑iω(i→v)=1。边权重 ω(v →w)可以看作查询v到查询w的跳转概率。

4 基于SimRank的查询相似度

建立查询关系图后,原先孤立地计算两个查询之间的相似度的问题被转化成在查询关系图上计算节点之间的相似度问题。Sim Rank[9]利用图的结构信息计算对象间的相似度：一个节点与自身的相似度最高,相同或相似节点的邻居节点也相似。也就是说,节点间的相似性可以沿着边传递到他们的邻居间。从另一方面看,节点的相似性依赖于邻居节点的相似性,节点间的相似度可以由邻居节点间相似度递归计算。

对查询关系图Gq=中任一节点(查询)v,I(v)表示v的入边邻居节点集合,Ii(v)表示第i个入边相邻节点。令Sim(a,b)表示节点a和节点b的Sim Rank相似度。根据前面所述的Sim-Rank 思想,则 ：如果 a=b,Sim(a,b)=1;否则

这里C(0

让我们来看一个例子,有两个Session,从查询“in formation retrieval”开始 ,分别结束于“CCIR”和“SIGIR”：

Session1：information retrieval→信息检索→CCIR Session2 ：inform ation retrieval→IR→SIGIR

“信息检索”和“IR”都有共同的入边相邻节点“information retrieval” ,因此 ,根据 SimRank,“信息检索”和“IR”相关。同样,因为“CCIR”和“SIGIR”的入边相邻节点“信息检索”和“IR”相似,因此“CCIR”和“SIGIR”也相似。尽管“信息检索”和“IR”、“CCIR”和“SIGIR”没有出现在同一Session中,SimRank仍然可以挖掘出它们间的相似性。实质上,“CCIR”和“SIGIR”相似是因为它们可以共同回溯到同一查询“information retrieval”。这种相遇的路线越多,两个查询就越相关,其SimRank相似度也就越高。

5 加权SimRank查询推荐

SimRank可以挖掘出查询间的深层联系,并综合考虑了一对查询间可以相遇的所有对称路径,这种计算相似度的策略适用于查询这种属性信息稀缺的对象。但是,Sim Rank算法在计算查询相似度上仍然存在两个问题：

◦Sim Rank算法仅仅利用了图的结构信息,没有考虑边权重信息。边权重体现了查询间的跳转概率,权重高的查询间关系更紧密,应该在推荐中给予更多考虑,而原始的SimRank算法却一视同仁,这影响了计算结果的准确性。

◦Sim Rank中两节点是否相邻对它们间相似度没有影响。在上个例子中“information retrieval”和“信息检索”的相似度计算为0。这是不合理的,查询关系图中具有直接关联的查询才会直接相连,这些查询往往非常相关。

因此需要改进SimRank算法以适合查询关系图上的查询相似度计算。首先,将权重信息融入公式;其次,修改公式保证相邻查询肯定相似。这个改造后的算法被称做加权SimRank(Weighted Sim-Rank,简称WSim Rank),公式如下：

与原始Sim Rank公式不同,WSim Rank保证查询关系图上有连边的节点对的相似度大于等于边权重。这样所有具有直接连边的查询的相似度都不为0了。可以迭代求解 WSimRank值,首先初始化如下：

利用数学归纳法,可以证明WSim Rank算法具有与Sim Rank算法相同的性质：唯一性、对称性和有界性。同样,WSim Rank的迭代算法具有收敛性。容易看出,在迭代过程中WSim k(a,b)单调非减,由于边权重事先做了归一化,则

所以WSim′k(a,b)≤1,因而 WSim k(a,b)≤1。根据单调有界收敛准则,迭代过程一定收敛。

5.1 性能优化

在Sim Rank和WSim Rank算法的每次迭代过程中,要暂存每次迭代的中间结果,因此空间复杂度为O(n2),其中n为图中节点个数。Sim Rank和WSim Rank算法的时间复杂度是O(kn4),其中k表示迭代次数。即便采用稀疏矩阵存储查询关系图,时间复杂度仍为O(kn2d2)(d表示节点的平均入度)。当n的规模很大时,会遭遇到性能瓶颈。真实搜索引擎中的查询总数往往至少数以百万计,我们必须对WSim Rank算法进行优化。

关于Sim Rank优化,前人提出一些方法,文献[9]提出限制传播半径来减少计算量;文献[16]采用蒙特卡洛方法得到近似解;文献[14]通过变化公式来优化计算。但是这些方法都没有结合计算机实现给出具体的实用性优化算法,本文把Sim Rank和WSim Rank的迭代计算过程转化成一个层次状态图中路径和的计算问题并给出优化方法。结合Sim Rank和WSim Rank,可以发现查询关系图中的每个节点在不同时刻具有四种不同的状态：

◦起始节点：计算中作为某个相似度节点对(a,b)的左节点a,

◦起始邻居：计算中作为某个相似度节点对(a,b)左节点a的入边节点I(a),

◦终止邻居：计算中作为某个相似度节点对(a,b)右节点b的入边节点I(b),

◦终止节点：计算中作为某个相似度节点对(a,b)的右节点b。

把查询图的每个节点分裂成四个状态,建立起所有状态间的联系,就构成了一个图,称之WSim-Rank计算图(简称计算图,图1)。计算图实际上反应了WSim Rank的计算过程。

图1 计算图

对于计算图中某一起始节点a,定义其可达节点b为：节点b属于终止状态集合且a到b之间存在至少一条路径。只有起始节点才具有可达节点,只有终止节点才能作为可达节点。起始节点与其任一可达节点构成一可达节点对。非可达节点对间的相似度肯定为0,因此不需要计算。定义可达路径为可达节点对间的一条路径,其权值为路径中各边权重的乘积。由此,WSim(a,b)的计算过程转化为：遍历计算图中节点a到节点b间的解有可达路径,并将这些可达路径权值累加的过程。

5.1.1 计算优化

从计算图中可以发现许多可达路径之间共享子路径。采用动态规划思想,将子路径的权值作为中间计算结果保存起来,下次计算直接利用,能大大减少重复计算。下面举例说明,在图1中黑色边表示从a到e和a到 f的四条路径：a→b→d→e,a→c→d→e,a→b→d→f,a→c→d→f,这四条路径的权值在计算路径和S(a,e)和S(a,f)时都必须计算出来,由于每条路径做2次乘法计算,那么一共需要8次乘法计算和4次累加计算。而S(a,e)=S(a,d)×ω(e,d),S(a,f)=S(a,d)×ω(f,d),它们都需要使用子路径权值S(a,d),计算S(a,d)需要2次乘法和1次加法计算,保存S(a,d)之后,一共仅需4次乘法和1次加法。

5.1.2 剪枝优化

如果能减少计算图中边的数量,那么将降低复杂度。剪枝的策略有两种,一种是静态剪枝,在计算前修剪,主要是修剪原始查询关系图,例如我们可以去除查询关系图中权重很低的边,或者去除像“百度”、“Google”这样连边多却不能体现搜索意图的查询;另一种是动态剪枝,在运行时修剪,主要是删去计算过程中相似度较低的节点对。在每次计算中预先删掉一些值较小且不会对最终结果有较大影响的中间结果,就能在接下来的计算中减少相当多的计算量。本文使用简单的启发函数f：

5.1.3 复杂度分析

设计算图中起始邻居状态节点的平均出边数为l,查询关系图中每个节点的平均出边数为d。使用压缩矩阵存储查询关系图需O(n+nd)空间,存储结果图需要O(n+nl)空间,另外需要O(n)存储中间结果,空间复杂度为O(n+n(d+l))。计算所有节点的子路径中间结果需要O(n)×O(d)×O(l)=O(nd l)时间,利用中间结果计算相似度需要O(d)+O(n)=O(nd),于是迭代一次的时间复杂度是O(nd l)+O(nd)=O(nd l),迭代k遍的时间复杂度是O(k)×O(nd l)=O(knd l)。由于查询关系图非常稀疏,d<

6 实验

6.1 实验数据和评价方法

为了验证加权Sim Rank,我们在真实搜索引擎查询日志上开展了一系列实验。实验数据基于新浪爱问搜索2006年9月到11月初的部分查询日志,这部分日志包含近两亿条记录。我们从中抽取了93 862个不同的高频查询构建查询关系图,本文选取了五种不同的方法进行对比：1)关联规则挖掘[3],用ARMSim表示;2)把所有查询用其对应点击URL的向量表示,以向量余弦夹角计算查询间相似度,以URLSim表示;3)Huang和Jian发表的查询推荐方法[4],也是基于Session的方法,记做Jian-Sim;4)原始 Sim Rank[9],以 Naïve Sim Rank 表示;5)加权Sim Rank,记做 Weighted Sim Rank。

在93 862个查询中,我们随机抽取了200个查询作为测试查询。并采用Poo ling的方法构建了评价集。具体而言,对每种方法返回的排名最前的10个推荐结果,使用文献[13]中的标准进行手工标注,这样共标注了约8 000个查询对作为评价集;每一对查询相关与否,均有3名学生进行标注,标注过程中,可以参考查询在搜索引擎中的返回结果;对于少量不一致的标注结果,标注者根据评价标准协商后最终给出一致结果。基于评价集,定义召回率(Reca ll)和准确率(Precision)：

此外,还有平均结果数(所有测试查询的平均返回结果数)、覆盖率(能给出推荐结果的查询在所有测试查询中的比例)。

6.2 实验结果和分析

图2和表1给出了各种方法的各项评价指标得分,其中,ARMSim[3]中关联规则参数 support和con fidence分别为2和 10%,Sim Rank和Weighted Sim Rank的衰减系数C均设为0.8,各自迭代计算5次,其他方法参数按照它们论文中的值进行设置,实验表明以上参数设置为在此语料集上的最佳参数设置方式。

图2 各种方法查询推荐结果的precision-recall曲线和NDCG曲线对比结果

表1 各种方法查询推荐结果评价值

从P-R曲线图上看到,Weighted SimRank的曲线大大超过其余所有方法的,取得最好效果。关联规则挖掘和原始Sim Rank性能相似,但是关联规则曲线在Recall<0.3时更陡,随着召回率增加下降明显,说明简单地统计频率信息会带来很多杂质。URLSim和JianSim效果最差,这主要是由于召回率偏低,结果稀疏导致的。Weighted Sim Rank算法之所以在召回率和正确率均有不同程度的提高,是引入图结构表示查询关系,并通过迭代计算挖掘出了更多的隐含关系,这在一定程度上保证了高召回率。

MAP和P@N的结果与P-R曲线稍有不同,关联规则挖掘在各项指标上都优于原始SimRank,这揭示了原始 SimRank算法的一个很重要的缺陷——没有结合权重信息。而Weighted Sim Rank在各类指标上都远远优于其他方法。这里平均结果个数统计的是整个测试查询集上所有查询的平均返回结果数目(对Sim Rank和Wsim Rank,相似度小于0.1的结果不予推荐),可以看到非迭代的方法都遭遇到稀疏性问题,前10个仅能返回不到6个结果,而SimRank类的方法均接近10个。在测试集上的覆盖率指标显示Weighted Sim Rank所有查询均有正确返回结果,关联规则挖掘次之。而基于URL的方法覆盖率和召回率都很低,这可能与实验语料有关。

6.2 加权SimRank的参数和性能

衰减系数C是Weighted Sim Rank中唯一的参数,实验结果表明C的选取对实验结果影响不大。当C在0.5到0.9间变化时,M AP的变化区间为(0.88,0.89),其他各项指标的变化幅度也小于5%。性能优化对于Weighted Sim Rank是必须的,在拥有一块2.4GH z CPU及8G DDR内存的机器环境下,包含93 862个节点的查询关系图可在1小时内完成5次迭代,实验表明迭代5次的结果已经非常接近最优值,而不加优化的运行时间估计需要数月。

6.3 例子

为了更好地理解加权SimRank给出的查询推荐结果。这里给出一个具体的例子①各搜索引擎相关搜索的返回结果均为2009年5月间取得的结果。,在日志中有一个查询词是“讯腾 qq”,因为“讯腾”没有与“QQ”相关的含义,很明显用户的本意是想搜索“腾讯qq”,但是输入错误变成“讯腾qq”。我们发现目前主流的搜索引擎的推荐结果竟然都包含“讯腾”二字,而我们的结果给出了用户真正想要的推荐“腾讯qq”。这也说明我们的方法能挖掘出查询间的语义联系。

7 总结

查询推荐是现代检索系统的重要组成部分,是搜索引擎与用户交互的途径之一。本文给出一种将查询关系用图模型表示的方法,并引入结构相似度算法——Sim Rank——来计算图中查询之间的相似度,这样能综合利用传统信息检索算法和查询间全局信息进行推荐。同时,改进Sim Rank变成加权Sim Rank。基于真实搜索引擎日志的实验验证了该算法的有效性：加权Sim Rank在查询推荐各项指标上比其他方法都有很大提高。

原始加权Sim Rank的时间复杂度和空间复杂度很高,在实际系统中难以实用,本文把计算过程转化成一个层次图——计算图,然后从不同角度对算法进行优化：1)采用图搜索方法而不是穷举减少计算量;2)采用动态规划思想保存中间结果减少重复计算;3)采用剪枝策略删去相似度低的节点对。将空间和时间复杂度从O(n2)和O(kn4)降低到了O(n log(n))和O(n log2(n)),大大提高了算法的效率和实用性。

表2 关于查询“讯腾 qq”的推荐示例

[1] Y.Li,S.Zhang,B.Wang,J.Li.Characteristics o f Chinese W eb Searching：A Large-Scale Analysis o f Chinese Query Logs[J].Journalof Computational Information Systems.Bethel：Binary Information Press,2008,4(3)：1127-1136.

[2] M.Strohmaier,M.K röll,C.Körner.Intentional Query Suggestion：Making User Goals More Explicit During Search[C]//WSCD'09：Proceedings o f the 2009 w orkshop on Web Search Click Data.New York,NY,USA：ACM,2009：68-74.

[3] B.M.Fonseca,Golghe,P.B.,Moura,E.S.d.,and Ziviani,N.Discovering Search Engine Related Queries Using Association Rules[J].Journal of W eb Engineering,2004,2(4)：215-227.

[4] C.-K Huang.,Chien,L.-F.,and Oyang,Y.-J.Relevant term suggestion in interactive w eb search based on contextual information in query session logs[J].Journal o f the American Society for Information Science and Technology,2003,54(7)：638-649.

[5] R.Baeza-Yates,Hurtado,C.,and Mendoza,M.Query Recommendation Using Query Logs in Search Engines[C]//In：Book Query Recommendation Using Query Logs in Search Engines,Springer Berlin/H eidelberg,2004：588-596.

[6] H.Cao,D.Jiang,J.Pei,Q.He,Z.Liao,E.Chen and H.Li,Context-aware query suggestion bym ining click-through and session data[C]//Proceeding of the 14th ACM SIGKDD international conference on Know ledge discovery and data m ining.Las Vegas,Nevada,New York,NY,USA：ACM,2008：875-883.

[7] M.Saham i and T.D.Heilman,A web-based kernel function formeasuring the similarity o f short text snippets[C]//Proceedings of the 15th international conference on World WideW eb.New York,NY,USA：ACM,2006：377-386.

[8] J.-R.Wen,J.-Y.Nie and H.-J.ZH ang,Query clustering using user logs[J].ACM Trans.Inf.Syst.,2002,20：59-81.

[9] G.Jeh and J.Widom,Sim Rank：ameasure of structural-context sim ilarity[C]//Proceedings o f the eighth ACM SIGKDD international conference on Know ledge discovery and data m ining.New York,NY,USA：ACM,2002：538-543.

[10] J.Xu,and W.B.Croft,Query expansion using local and global document analysis[C]//Proceedings of the 19th annual international ACM SIGIR conference on Research and development in in formation retrieval.New York,NY,USA：ACM,1996：4-11.

[11] S.Deerw ester,et al.Indexing by latent semantic analysis[J].JASIS,January 1999,41(6)：391-407.

[12] Y.Chen,G.-R.Xue,and Y.Yu,Advertising keyw ord suggestion based on concep t hierarchy[C]//Proceedings of the international conference on W eb search and w eb datam ining.New York,NY,USA：ACM,2008：251-260.

[13] R.Jones et al.,Generating query substitutions[C]//Proceedings of the 15th international con ference on W orld WideWeb.New York,NY,USA：ACM,2006：387-396.

[14] I.Antonellis,H.G.Mo lina and C.C.Chang,Simrank++：query rew riting through link ana lysis of the click graph[C]//Proc.VLDB Endow.2008：408-421.

[15] 张磊,李亚楠,王斌,等.网页搜索引擎查询日志的session划分研究[J].中文信息学报,2009,23(2)：54-61.

[16] D.Fogaras and B.Racz,Scaling link-based sim ilarity search[C]//Proceedings of the 14th international conference on World Wide Web.New York,NY,USA：ACM,2005：641-650.

[17] D.Lizorkin,P.Velikhov,M.Grinev and D.Turdakov,A ccuracy estimate and optim ization techniques for Sim Rank computation[C]//Proc.V LDB Endow.,2008：422-433.