基于权重标准化SimRank方法的查询扩展技术研究

马云龙，林 原，林鸿飞

(大连理工大学 信息检索研究室，辽宁 大连 116024)

1 引言

当前，通用搜索引擎主要是通过查询关键词匹配的方法进行检索。其存在的不足是： 用户进行检索时输入的有限词语往往不能准确且完全地表达其检索的真正意图，进而导致搜索引擎返回大量的不相关文档。为此，需要找到一种有效的方法对用户输入的查询进行纠正及补充，即查询扩展技术。

查询扩展过程需要从特定的语料资源中挖掘各词项与原始查询之间的某种关联属性，进而选择较好的词项作为扩展词。查询扩展技术的两个关键之处在于扩展资源的选取以及词项间关联属性的挖掘。在扩展词资源方面，大规模真实的搜索引擎日志通常包含了用户的原始查询、浏览页面、点击链接以及对应的时间等非常丰富且有价值的信息，作为扩展资源，其质量相比于传统的伪相关文档更具有优势。同时，在真实的搜索引擎日志中，也包含了大量的噪声数据，因此，需要有效地挖掘词项关联属性以求更好地筛选出与原始查询相关的扩展词项。本文采用基于图结构的相似度算法SimRank应用于适当的词项关系图上，全面有效地挖掘词项间的相似度及语义关联，从而减少噪音影响，提高筛选质量。

本文后续内容将按如下方式组织： 第2节介绍基于搜索引擎日志及加权SimRank方法的查询扩展技术研究的相关工作；第3节说明查询点击图与词项关系图的构造和处理方法；第4节阐述权重标准化SimRank算法及其优化方法；第5节展示实验设计、结果及分析；最后，本文在第6节进行总结。

2 相关工作

查询扩展技术早在 20 世纪 70 年代就已经被提出，作为解决表达差异的一种有效方法，能在一定程度上弥补用户表达与相关文档之间的差别，提高检索效果。 按照用户交互方式的不同可将其分为显式反馈和隐式反馈两种。显式反馈以相关反馈(relevance feedback)方法为主[1]，指用户主动向系统提供自己的兴趣偏好或对系统返回的结果进行相关性评价，系统根据这些反馈生成新的查询。隐式反馈的查询扩展方法基本上可以分为全局分析、局部分析[1]和外部数据分析[2-3]三大类。全局分析是较早出现的具有实际应用价值的查询扩展方法，其基本思想是对全部文档中的词项进行相关性分析，计算每对词项间的关联程度。当需要查询扩展时，根据预先计算的相关关系，将与原查询用词关联程度最高的词项加入原查询以生成新的查询，常见的方法包括 LSI(Latent Semantic Indexing)、LDA(Latent Dirichlet Allocation)和相似性词典等。目前流行的局部分析方法主要是伪相关反馈(Pseudo Relevance Feedback)，它是在相关反馈的基础上发展起来的，其基本思想是利用初次检索得到的与原查询最相关的 N篇文章(伪相关文档集)作为扩展词项的来源。隐式反馈方式的查询扩展方法通过分析用户与系统正常的交互行为来推测用户检索意图，不需用户做额外的相关性评价。由于通常情况下用户不愿花费额外的精力进行主动反馈，所以隐式反馈方式逐渐成为查询扩展技术研究中的重点。

近些年，随着一些商业通用搜索引擎的部分查询日志被公开，对查询日志的研究工作被大规模地展开。一种普遍的观点认为，在现实中用户与搜索引擎的交互，并不仅仅是搜索引擎向用户提供合适信息的过程，与此同时用户在点击相应页面链接的过程中也对搜索结果进行了高质量的相关性反馈，这些内容都以搜索引擎日志(Query Logs)的形式被记录和保存，其中包含了用户的原始查询、浏览页面、点击链接以及对应的时间等非常丰富且有价值的信息[4]。有一部分学者在伪相关反馈的基础上对查询扩展方法进行了改进，使其能够利用查询日志中的信息挖掘合适的扩展词项[2，4]。而更多的研究则关注于通过对查询日志的分析来优化查询推荐[5-7]，其中文献[6]的方法利用了查询点击图(Query-Click Graph)，文献[5]和[7]的方法利用了查询迁移图(Query-Flow Graph)。

3 查询点击图与词项关系图

3.1 查询点击图

查询点击图又被称为查询文档图[4]，记为GQC={VQC,EQC}。它是一个加权有向二部图，对于给定的查询集合Q以及地址集合U，其节点集合VQC={vq,vu}=Q∩U，即一部分节点表示不同的查询，另一部分节点表示用户所点击的不同地址(URL)。边集合为EQC={equ}⊆Q×U，即每一条边equ均由某一查询节点出发到某一地址节点结束，表示用户键入该查询进行检索并在搜索引擎返回的结果列表中点击了相应的地址。边权重ω(equ)记录了相应查询和地址对在查询日志中的共现次数，一定程度反映了特定节点对的关联程度。

具体地，查询点击图通过以下步骤进行构造：

(1) 对搜索引擎查询日志进行去噪处理和词项过滤，采用本文第5.1节中的方法。

(2) 对于查询日志中新出现的每一个查询，在查询点击图中增加一个查询节点。

(3) 对于查询日志中新出现的每一个地址，在查询点击图中增加一个地址节点。

(4) 对于每个查询节点，建立从它到所有相关点击地址节点的有向边，边的初始权重设置为1，若边已存在，权重加1。

3.2 词项关系图

词项关系图，记为GT={VT,ET}，是一个加权有向图。节点集合为VT={vt}，其中每个节点vt表示一个词项。边集合为ET={et}，其中每条边et均由某一词项节点出发到另一词项节点结束，表示两词项在搜索日志中有直接关联。边权重ω(et)的大小反映了两词项直接关联的强弱，若边et不存在，则另ω(et)=0。

词项关系图可以通过对查询点击图进行两次图结构转换而得到。

3.2.1 查询节点替换

由查询日志直接构建的查询点击图虽然能够完整地记录查询日志中查询与地址及其之间关系，然而对于查询扩展这一以词项为处理单元的任务来说，其查询节点包含的信息粒度过大，不利于挖掘词项间的关联。因此需要将其细化，具体步骤如下：

(1) 对于查询点击图中的每一个查询节点，将该查询节点使用其对应查询所包含的各词项节点代替。

(2) 若对应词项节点不存在则增加该节点。

(3) 将所有与查询节点关联的边逐一复制给相应的各词项节点。

(4) 删除该查询节点及与其关联的所有边。

至此形成由词项节点、地址节点及它们之间加权边所构成的词项—地址关系图。

3.2.2 地址节点消除

由于查询扩展技术的特定性质，词项—地址关系图中的地址节点是不必要的，并且其存在势必会给处理过程增加额外的消耗。因此本文通过如下步骤将地址节点消除：

(1) 对于每一个词项节点对(vt1,vt2)和每一个地址节点vu，若vt1与vt2均指向vu， 则建立由vt1到vt2以及由vt2到vt1的边，边上权重均初始化为c(vt1,vt2,vu)，若边已存在，则将其上权重加c(vt1,vt2,vu)。

(2) 删除所有地址节点及与其关联的所有边。

其中对于任意词项节点vt1和vt2(vt1≠vt2)和任意地址节点vu，c(vt1,vt2,vu)表示vt1与vt2经由vu所产生的点击通量[8]，由如下公式计算得到：

c(vt1,vt2,vu)=min(ω(vt1→vu),ω(vt2→vu))

(1)

综上所述，经过这些步骤可以快速的将查询点击关系图转换为词项关系图，并且该转换有诸多现实意义： (1)词项关系图更利于以查询扩展为目的较全面和直接地发掘查询日志中各词项间的关联；(2)可以避免由查询日志数据直接构造词项关系图所需要的复杂逻辑；(3)相比查询和地址数量，词项数量更小，进而词项关系图所需存储数据量更小，结构也更简单；(4)对于SimRank算法而言，对于节点同质的图结构处理更加高效，也更利于进行优化。

4 权重标准化SimRank与查询扩展

4.1 SimRank

构造词项关系图后，原先孤立地计算两个查询词项之间共现度或翻译概率的问题就被转化成为在词项关系图上计算两词项节点之间相似度的问题。Glen和Jennifer提出的SimRank方法[1]能利用有向图的结构信息计算图中任意两节点对象的相似度，其基本思想是： 如果两对象a和b同时分别与另外两对象c和d关联，且c与d是相似的，则a与b也是相似的；并且任意节点与其自身拥有最大相似度1。也就是说，节点间的相似性依赖于邻节点的相似性，节点间的相似度可以由邻居节点间的相似度递归计算。

针对本文而言，对词项关系图GT={VT,ET}中任意词项节点vt，定义I(vt)表示vt的入边源节点集合，Ii(vt)表示该集合中第i个入边源节点，|I(vt)|为vt的入度总和。令Sim(va,vb)表示节点va和节点vb的SimRank相似度。根据SimRank的基本思想，该相似度的标准计算公式如下：

其中，常数C为取值范围由0到1的实数，表示相似度在沿有向边传递过程中的衰减系数。

4.2 权重标准化SimRank

通过在词项关系图上应用SimRank算法，能够综合考虑任意查询词项对之间的所有路径，进而可以挖掘出各词项间的深层关联。同时，由于SimRank具有对稀疏数据公平对待的特性，更加适用于搜索引擎查询日志这种信息非常稀疏的数据类型。

然而，对于本文研究的问题而言，基础的SimRank算法仍然存在一个主要问题： SimRank算法在计算节点间相似度的过程中仅利用了有向图的结构信息，而没有考虑到有向边上的权重信息。在词项关系图中，边上权重体现了两词项在查询日志中总的点击通量情况，点击通量越大的查询词项间关联程度越高，所表达的语义也更接近，在查询扩展的候选词项中理应给予更多的考虑，而这些在基础SimRank方法的计算过程中均未考虑。

为此本文对SimRank算法进行了改进，以适合在词项关系图上的查询词项相似度计算。首先，对词项关系图中每个节点的入边权重进行标准化，使之对于任意节点vt均满足以下关系：

(3)

进而将标准化后的边权重融入基础SimRank算法，记为权重标准化SimRank算法(Weight Normalized SimRank，简称WNS)，其计算公式如下：

其中，ω(va→vb)表示由va节点到vb节点的有向边上的权重，其他符号与基础SimRank公式中同义。

4.3 性能优化

SimRank和WNS算法均是以图结构为基础的算法，因此对图中节点对进行一次遍历计算需要耗费大量的计算时间，加之其计算过程需要进行多次迭代以得到收敛后的稳定相似度，因此该算法的时间复杂度为Ο(kn2d2)(k表示迭代次数，d表示节点的平均入度)。当n的规模很大时，算法的性能很差，这也是本文方法在实现过程中所遇到的主要问题，为此本文分别使用了静态剪枝和限制传播半径两种方法对WNS算法进行了性能优化。

4.3.1 静态剪枝

从算法的时间复杂度中不难看出，有向图中节点的平均入度对实际时间消耗有较大影响，因此如果能减少计算图中节点的平均入度，则会相应地提高算法效率。为此，本文对词项关系图进行了静态剪枝操作。

首先，对于图中每一个节点，只保留其入边集合中点击量最大的dm条边，删除其余入边；如果节点入边数不足dm条，则全部保留；然后，再对所有保留的入边上的权重进行标准化。

静态剪枝会损失原词项关系图中的一部分信息，但是由公式(2)和公式(5)不难看出，入边权重很小的邻节点相似度对当前计算的节点对的相似度贡献很小，又因为SimRank是一种收敛速度较快的迭代算法[9]，所以，在一般情况下，能够较快的找到一个数值较小的dm使得所需的最终相似度数值几乎没有损失，对此本文实验部分将会给出进一步说明。

4.3.2 限制传播半径

G. Jeh和J. Widom[9]提出了一种通过限制SimRank计算过程中的相似度传播半径r，以提高算法效率的优化方法。在最坏情况下，每次迭代中需要计算n2个节点对的相似度，当n的规模很大时效率很差。“假设两节点相距很远，则它们的邻节点集合只会有很少量的重叠，因此根据SimRank的算法思想，像这样相距很远的节点间相似度必然会远低于相距较近节点”[9]。所以在本文的方法中我们也限制了WNS计算过程中的相似度传播半径，即若两节点va与vb间距离超过r，则记WNS(va,vb)=0。

通过这种方式，SimRank计算的时间复杂度可以降至接近Ο(knd2)，同时由此产生的误差可忽略不计[9]。

4.4 查询扩展

查询扩展技术的基本思想是选择与原始查询同义或有强语义关联的词项作为扩展词项加入查询中。本文中采用的查询扩展策略具体步骤如下：

(1) 对于原始查询中每一个词项t，若其在词项关系图中有对应节点vt，则将与vt间WNS相似度非0的所有节点所对应的词项加入候选集。

(2) 在候选集中选择相似度最高的K个节点作为扩展词加入原始查询中。

(3) 利用扩展后的查询进行检索。

其中，K为正整数，表示扩展词数。下文中将该方法简记为WNSE。

5 实验

5.1 实验数据与评测指标

5.1.1 搜索引擎查询日志

为了验证本文方法的有效性，实验在真实的搜索引擎查询日志上开展，所使用的查询日志数据为AOL(American Online)公司面向学术研究公开的旗下搜索引擎由2006年3月1日00:00:00至2006年5月31日23:59:59期间的全部搜索日志，包含了657 426个独立用户的总共36 389 567条记录，格式为“用户 查询 时间 [点击序号 地址]”[10]。其中共有10 154 742个不同查询以及19 442 629次用户点击。

5.1.2 检索文档集与原始查询

本文实验使用TREC评测所提供的公开文档集GOV2作为检索文档集，共包含文档25 205 179个，其中大部分为政府部门曾公开发表的英文新闻文章；同时实验中我们使用了TREC公开的701至850号Topic作为原始查询集合。

5.1.3 评价方法

本文实验评测部分使用TREC提供的公开相关文档标注结果以及标准评测程序。为了同时从不同角度考察本文方法的有效性，本文采用了P@10、P@20和MAP三项指标对实验结果进行评价。

5.2 实验设计

首先，我们对AOL搜索引擎查询日志进行去噪处理，将诸如“fidelity.com”的网址导航查询和类似“wu 20v 20-----”的无语义信息查询以及包含成人词汇的查询过滤后，按前文所述方法构造了查询点击图。图中共有查询节点4 605 412个，地址节点2 316 342个。在此基础上构造词项关系图，图中共有词项节点413 013个。

接着，对词项关系图进行静态剪枝，我们对不同的最大节点入度dm取值进行了简单的对比试验，在用WNS进行5次迭代后的结果中抽取3个词项节点对的相似度进行观察，发现当dm取值范围在100至900时，其相似度变化如表1所示。

可以看出，当dm取值500以上时，dm数值的增加对最终相似度的影响甚微，所以在实际实验中，我们设置dm为500。

之后，我们在得到的词项关系图上使用WNS方法进行词项间相似度的计算，由于一般情况下当C在0.5到0.9之间变化时，相似度关系的变化很小[7]，所以实际实验中我们将C设置为经验值0.8[9]。类似的，将相似度传播半径r和迭代次数k均按经验值设置为 2和5[9]。

表1 不同dm取值时的WNS相似度

最后，使用本文在4.4节所述的查询扩展方法，在Indri检索工具中利用结构化查询语句“#weight”和“#combine”进行检索，并按照是否将WNS相似度作为扩展词项的权重加入最终查询而分为WNSE-Weighted以及WNSE-Unweighted两种方法，分别进行有效性验证，最终查询形式如公式(6)。

#weight(λQori(1.0-λ)Qexp)

(6)

其中λ为取值0到1间的实数，表示原始查询权重；Qori表示原始查询；Qexp表示扩展词。

作为有效性验证的对比实验，我们分别选择了两种较成熟且被广泛用于对比的方法： (1)查询似然模型，并使用以经验值1 500为参数的Dirichlet平滑方法，记为LM-Dir，该方法同时也为其他查询扩展方法的基础检索方法；(2)基于伪相关文档的Lavrenko查询扩展方法[11]，记为RM方法。

5.3 实验结果

通过观察实验所得到的3种查询扩展方法在GOV2数据集上的性能变化情况(图1)， 可以发现

图1 K=30时各扩展方法的性能变化曲线

当扩展词数K=30时，RM方法在λ取值约0.6时MAP指标分值最高；本文提出的WNSE-Weighted和WNSE-Unweighted方法分别在λ取值0.9和 0.8 时效果最好。表2、表3和表4分别给出了上文所述4种方法在λ参数取最优情况时的P@10、P@20 和MAP评价指标分值。

表2 4种方法检索结果MAP分值

表3 4种方法检索结果P@10分值

表4 4种方法检索结果P@20分值

从各表中不难看出，本文提出的WNSE-Weighted和WNSE-Unweighted方法，在MAP评价指标上与传统RM方法性能相当，并且大多数情况下分值略高于后者；而在P@10和P@20评价指标上相对RM方法均有较大幅度提高；实验中涉及的各查询扩展方法在三项评价指标上均相对于基础检索方法LM-Dir有很大幅度的提高；WNSE-Weighted方法效果略优于WNSE-Unweighted方法，且相比更加稳定。为了更直观的反映实验结果，图2给出了各评价指标的分值变化曲线。

从图中可以得出与上文相同的结论，与此同时我们还发现WNSE方法在扩展规模较小(K取值20至40)时效果较好，而RM方法在扩展规模较大时效果更优。其意义将在5.4节中进行讨论。

图2 4种方法检索结果的MAP、P@10和P@20分值变化曲线

5.4 实验结果分析

由实验结果可以得出在最优情况下，本文设计的WNSE方法与传统RM以及基础检索LM-Dir方法相比： 在MAP指标上分别提高了1.81%和5.22%；在P@10指标上分别提高了5.44%和8.61%；在P@20指标上分别提高了3.73%和7.73%。说明WNSE查询扩展方法在AOL搜索引擎查询日志和GOV2文档集上有不错的实际检索效果。

关于WNSE方法在扩展规模较小时效果较好这一特点，也有其现实意义。众所周知在各检索框架下，查询词项的增加都会不同程度地增加检索所需时间，因此WNSE方法有助于使用较少的检索时间得到较好的检索效果。

从图2中还可以看出，WNSE方法随平均扩展度的增加各指标分值均有一定程度的波动，经过观察实验中间结果，我们发现造成波动的原因主要是所使用的查询日志中包含噪音，虽然已经经过了一些去噪处理，但仍然残存一定数量的噪音词项。在原始查询较短情况下，噪音词项的加入会一定程度上影响检索效果。然而即便如此，在处于波动低值时的检索性能也是可以容忍的。

6 总结

查询扩展技术是现代检索技术中一个重要的组成部分，能够较为有效地帮助用户与搜索引擎进行交互，从而提高检索效果。本文提出了一种将搜索引擎查询日志使用查询点击图表示，进而转化为词项关系图的图模型表示方法，同时引入了对相似度算法SimRank进行改进后的权重标准化SimRank算法，来计算图中个词项间的相似度，从而综合利用查询日志中词项间直接和潜在的信息进行查询扩展。

原始权重标准化SimRank方法在较大规模数据的应用中存在很大的时间消耗，因此本文从该角度出发，使用静态剪枝以及限制传播半径的方法对算法进行了优化，提高了算法的效率和实用性。

基于较大规模真实搜索引擎查询日志的实验验证了本文方法的有效性。利用基于词项关系图的权重标准化SimRank方法在标准TREC数据集上进行查询扩展，其效果比传统伪相关文档查询扩展在P@10评价指标上有较大幅度提高，同时在MAP指标上也有小幅提升。

同时我们也注意到，本文方法也存在一些不足之处： (1)由于查询日志数据的稀疏性和大量噪音，导致最终实验结果未达到最优；(2)由于作者精力有限，对比实验中并未涉及更多的相关方法，这也还我们在今后一段时期内进行更多的相关研究工作。

[1] J. Xu and W. Croft. Query expansion using local and global document analysis [C]//Proceedings of SIGIR. Zurich, Switzerland，1996：4-11.

[2] X. Wang, C. Zhai. Mining term association patterns from search logs for effective query reformulation [C]//Proceedings of CIKM. Napa Valley, California, USA，2008:479-488.

[3] 宋巍，张宇，刘挺，等. 基于检索历史上下文的个性化查询重构技术研究[C]//第五届全国信息检索学术会议. 上海，中国，2009:144-152.

[4] V. Dang, W. B. Croft. Query reformulation using anchor text [C]//Proceedings of WSDM. New York City, New York, USA，2010:41-50.

[5] P. Boldi, F. Bonchi and C. Castillo. Query suggestions using query-flow graphs [C]//Proceedings of WSCD. Barcelona, Spain，2009:51-58.

[6] I. Antonellis, H. G. Molina and C. C. Chang. Simrank++: Query rewriting through link analysis of the click graph [C]//proceedings of VLDB. Auckland, New Zealand，2008:408-421.

[7] 许晟，李亚楠，王斌，等. 基于加权SimRank的中文查询推荐研究[C]//第五届全国信息检索学术会议. 上海，中国，2009:242-251.

[8] D. Beeferman, A. Berger. Agglomerative clustering of a search engine query log [C]//Proceedings of SIGKDD. Boston, Massachusetts, USA，2000:407- 416.

[9] G. Jeh, J. Widom. SimRank: A measure of structural-context similarity [C]//Proceedings of SIGKDD. Edmonton, Alberta, Canada，2002:538-543.

[10] F. Diaz, D. Metzler. Improving the estimation of relevance models using large external corpora [C]//Proceedings of SIGIR. Seattle, Washington, USA，2006:154-161.

[11] V. Lavrenko, W. B. Croft. Relevance based language models [C]//Proceedings of SIGIR. New Orleans, Louisiana, United States，2001:120-127.

[12] C. Silverstein, H. Marais and M. Henzinger. Analysis of a very large web search engine query log [J]. ACM SIGIR Forum, 1999, 33(1)： 6-12.