查询推荐方法的一般思路为: 通过相关模型来计算候选查询与原查询的关系权值, 在此基础上, 利用相关推荐方法生成候选查询推荐。衡量查询间相关关系的方法是查询推荐中的重要部分。计算原查询与候选查询关系权值的一般方法, 如下所示:

(1)

其中, r(q',q) 表示查询q'与原查询之间的关系值。θ(q',q)表示利用函数θ计算查询q'与原查询q之间的相关关系, λ表示函数θ的权值。 表示若有多个函数用于衡量q'与q之间关系时, 则各函数之间需进行线性加权, 各权值λ之和为1。在一般查询间关系模型中, Session中共现互信息^[4]是计算 θ(q',q)权值的常用方法。

利用查询共现信息来衡量查询间关系的研究大多基于如下假设: 同一Session中的查询描述相同的用户任务。而一些研究者发现同一Session的查询可能表达不同的用户任务: 如Lucchese等^[16]通过对AOL查询日志分析发现, 约74%的查询位于多任务Session中; Liao等^[17]通过分析一商业搜索引擎的查询日志发现, 约30%的Session中包含多任务; Jones等^[15]通过对Yahoo搜索引擎日志分析发现, 约17%的 Session中存在着用户任务交叉现象。于是, 基于共现信息生成的候选查询推荐容易偏离原查询的用户任务。本文查询推荐的目标是根据用户提交的查询来生成与原查询用户任务相同的候选查询, 拟从查询间时间距离、查询表达式与查询之间语义关系来衡量查询间的用户任务相似度。

(1) 查询间时间距离

笔者假设, 对于查询q与q'来说, 若两查询之间时间距离越小(即在同一Session中, 两查询之间距离越近), 二者表达同一用户任务的可能性越大。设 S={q₁, q₂,q₃...q_t-1,q,q_t+1...} 表示某一Session的查询集合, 该集合包含原查询q, 且该集合中查询按照提交时间先后进行排列, 其中, q₁的提交时间早于q₂的提交时间, q₂的提交时间早于q₃的提交时间。由以上假设可知, q_t+1与q_t-1表示与原查询q的相邻查询, 因此, 这两个查询包含的用户任务更可能与查询 q的用户任务相似。本文利用公式(2)中decay(i,j,S)计算在某Session S中原查询q与查询q'之间的距离权值。

decay(i,j,S)=β^|j-i| (2)

其中, j表示查询q'在S中的排序, i表示查询q在S中的排序, β表示衰减系数^[6], 本文将其值设定为0.8。

公式(3)表示当q与q'共现于多个同一Session中时, 两查询间的时间距离权值T(q,q')为各Session中距离权值 decay(i,j,S)的平均值。T(q,q')值越大, 则两查询描述同一用户任务的可能性越大。

(3)

(2) 查询间表达式相似性

在大多数情况下, 用户常用表达式相似的查询来描述同一查询任务^[16]。本文假设, 若两查询间共有查询词越多, 二者描述同一用户任务的可能性越大。考虑到查询中某些词拼写错误以及词的前缀后缀现象会影响到这种相似性的计算, 本文综合利用文献[16]提出的计算字符串之间相似度的Di-gram Jaccard距离以及标准化编辑距离来计算两查询之间相似性, 如下所示:

(4)

其中, u_jac表示两查询之间的Di-gram Jaccard距离值, u_levenstein表示两查询之间编辑距离值^[16]。因 u_jac值与u_levenstein值之和不小于1, 为使得查询间相似性与查询间距离成反比关系, 且计算而得的查询表达式相似度值小于1, 笔者利用 来衡量查询之间表达式相似性。 u_expression(q,q')值越大, 表明两查询之间的表达式相似性越大, 描述同一用户任务的可能性越大。

(3) 查询间语义相似性

考虑到表达式不同的两查询也可能包含同一用户任务, 本文也尝试利用查询间语义相似度来衡量查询间的用户任务相似度^[3]。一般来说, 衡量查询之间语义相似性方法大致分为从大数据集中扩展查询与直接采用语义资源两类方法, 因后一类方法相对前一类方简单且易实现, 本文尝试借助语义资源Wikipedia(即ClueWeb 09 Category B^[18]中的Wikipedia数据集)来计算查询间语义相似性。一般情况下, Wikipedia中的每个网页描述某一概念, 则该网页中所出现的词都与该概念相关。根据文献[3]的思想, 本文将查询词t的向量表示为:

其中, W表示数据集中所包含的网页数目。c_i表示词t在第i个网页中的权值, 其值是由tf-idf原理计算得出。

公式(5)表示查询q的向量为各个查询词(非停用词)向量之和。

(5)

本文利用余弦值来计算两查询向量之间的相似度, 如下所示:

(6)

本文在计算r(q',q)(即查询q'是查询q的候选查询概率)时, 利用三个θ函数来衡量查询之间相关关系, 即综合考虑查询之间时间距离﹑查询间表达式相似性以及查询之间语义相似性三方面, 其计算方法分别参见公式(3)﹑公式(4)与公式(6), 这个三函数的权值分别为λ₁﹑λ₂与λ₃, 且三者之和为1。

首先构建图G=(V, E), 节点V由查询词及其所点击文档构成, E所包含的边集合有: 查询之间相关关系以及查询与文档之间的点击关系。本文将每个节点当作一个马尔科夫状态。查询之间转移概率, 如下所示:

(7)

其中, P(q|q')表示查询与查询之间的转移概率, r_C(q',q)表示查询q'与查询q的相关关系, 表示与q共现同一Session中的所有不同查询q''与原查询q间的r_C(q'',q)之和。 ε表示从查询状态转移到文档状态的概率, 其参数调节过程参见5.2节。

笔者在计算查询与文档之间转移概率时, 首先将URL加以区别对待, 即若一个URL被多个查询点击, 则该URL具有模糊性, 反之, 表明该URL具有专指性。查询转移到专指性URL的概率应大于模糊类URL。本文利用文献^[19]提出的 iqf衡量URL对查询的区分度(与文档的idf思想相似), 公式如下所示:

(8)

(9)

其中, n(d_j)表示点击了文档d_j的查询频次之和, |Q|表示查询日志中总查询数。 cfiqf表示点击频次与iqf的乘积, c_ij表示查询q_i点击文档d_j的次数。

则文献[19]中query-url之间的转移概率公式如下所示:

(10)

其中, 表示查询d_i所点击文档的cfiqf权值之和。

公式(11)表示文档状态是一个吸收状态(即自转移状态), 即转移到自身的概率为1, 而转移到查询状态的概率为0。根据马尔科夫吸收链的性质: 当状态转移到文档状态后, 则会一直停留在此状态; 从每一个非吸收状态出发, 有限次转移后能以正的概率到达某个吸收状态。

(11)

基于如下假设: 用户所点击文档能描述用户的信息需求, 则点击同一文档的两查询可能具有相似用户任务^[20], 本文根据每个查询所点击文档分布来对查询构建向量。以图1为例, 图中节点由查询 q₁、q₂与q₃以及被点击文档节点d₁、d₂与d₃构成。其中, 查询与点击文档的实线边表示点击关系, 而虚线边表示经过随机游走后, 查询能到达该文档状态。本文为查询构建向量的特点在于不只是考虑某查询点击的文档, 而是查询到文档的整个路径, 即经过随机游走该查询可能到达的文档状态, 如查询q₂虽与文档状态d₁与q₃无直接点击关系, 但经随机游走后, 能到达这两状态。本文采用KL距离来计算向量之间相似度以此来排序与原查询相关的查询, 生成候选查询推荐。

图1

	Figure Option ViewDownloadNew Window
	图1 经随机游走后的查询与文档间关系

本文采用AOL^[21]查询日志作为数据集, 其时间跨度为2006年3月1日到5月31日, 其格式如图2所示, 从左到右分别表示用户ID﹑查询表达式﹑用户点击时间﹑被点击URL在结果列表中的排序﹑点击的URL地址。因原始数据集中包含许多噪音, 本实验首先对其进行清理: 如剔除包含色情词查询﹑只包含网页地址的查询等。笔者通过“15分钟划分法”^[13]识别Session边界。

图2

	Figure Option ViewDownloadNew Window
	图2 AOL数据集格式

本文随机抽取200个不同查询作为原查询。考虑到某些参数会影响到实验的最终效果, 参数调节是本文的重要部分。图3表示公式(7)中随机游走参数ε取不同值时, 所构建图模型中90%的查询节点达到吸收状态时所需要的随机游走步数。可知, 当ε取值为0.6时, 所需的随机游走步数最少, 则ε的最优值为0.6。

图3

	Figure Option ViewDownloadNew Window
	图3 随机游走参数ε取值与随机游走步数之间关系

在此基础上, 本文进行了4组不同的实验:

(1) 利用共现互信息计算公式(1)中θ(q',q)值, 并利用文献[6]中构图方法(图模型中只包含查询节点, 即只考虑查询间关系)来实现查询推荐(标记为“Baseline1”);]]>

(2) 利用共现互信息计算公式(1)中θ(q',q)值, 并利用本文构图方法来实现查询推荐(标记为“Baseline2”);

(3) 基于用户级别计算公式(1)中θ(q',q)值, 并利用文献[6]中构图方法实现查询推荐 (标记为“Baseline 3”);

(4) 基于用户任务级别计算公式(1)中θ(q',q)值, 并利用本文中构图方法来实现查询推荐(标记为“Our Work ”)。

据笔者所知, 目前尚未有公认的查询推荐公共评测语料, 人工评测是当前主要方法。本文选取三位专家对实验结果进行评测, 对于每个原查询, 三位专家分别判断每个结果的相关度, 本文中相关度的标注是基于二值判断即“相关”与“不相关”两类。另外利用Cohen kappa(κ)^[22]来获取评测者两两之间同意对方评测结果的概率, 平均值为0.68, 说明了三位专家之间同意对方评测结果的概率较高。对于少量不一致的标注结果, 标注者将根据评价标准协商后给出最终一致性结果。本文采用P@N(Precision at N)以及Recip_Rank指标来对推荐结果进行评测。其中, P@N表示前N个推荐结果中相关查询所占的比例, Recip_Rank表示返回第一个相关查询的能力。

另考虑到“Our Work”与“Baseline3”两实验从用户任务级别计算查询间相似性时, 三函数(分别参见公式(3)﹑公式(4)与公式(6))权值λ₁﹑λ₂与λ₃的不同取值会影响到的最终效果。在这两组实验中, 本文将200个原查询平均分为两份, 其中一份的100个原查询作为训练集, 获得三参数的最优解; 而将另外一部分的100个原查询作为测试集, 即在训练集中获得最优参数解的基础上, 获得实验的最终实验效果。其中, “Baseline3”最终实验结果的P@3﹑P@5﹑P@10与Recip_Rank值分别为0.47﹑0.54﹑0.67与0.68; “Our Work”最终实验结果的 P@3﹑P@5﹑P@10与Recip_Rank值分别为0.50、0.60、0.72与0.73。

表1

表1

表1 实验结果评测表 评测指标 相关方法 P@3 P@5 P@10 Recip_Rank Baseline1 0.40 0.52 0.60 0.62 Baseline2 0.42 0.53 0.60 0.63 Baseline3 0.47 0.54 0.67 0.68 Our Work 0.50 0.60 0.72 0.73

表1 实验结果评测表

表1是4组实验的评测结果。从评测指标值可知, “Baseline 3”方法优于“Baseline 1”方法, “Our Work”方法优于“Baseline2”方法, 从这两组对比数据可以说明, 基于用户任务级别衡量查询之间相关关系可进一步提高查询推荐的效果。另也可知, “Baseline 2”方法优于“Baseline1”方法, “Our Work”方法优于“Baseline 3”方法, 从这两组对比数据中可知, 本文构图方法优于文献[6]中构图方法(图模型中只包含查询节点, 即只考虑查询间关系), 即在构建图模型时, 考虑查询与文档之间点击关系可进一步提高查询推荐的最终效果。

另考虑到查询的不同属性会影响到最终的查询推荐效果。表2表示将查询按照稀有性和模糊性进行分类后, 利用本文推荐方法后的各类别查询的评测结果。其中, 查询稀有性判断方法参见文献[23],查询的模糊性判断方法参见文献[24]。

表1

表1

表1 不同属性查询的实验评测结果 评价项 P@3 P@5 P@10 Recip_Rank 稀有性 稀有查询 非稀有查询 0.42 0.58 0.49 0.71 0.64 0.80 0.64 0.82 模糊性 模糊性查询 非模糊性查询 0.43 0.57 0.52 0.68 0.63 0.81 0.67 0.79

表1 不同属性查询的实验评测结果

可知, 非稀有查询的实验效果优于稀有查询的实验效果, 非模糊性查询的实验效果优于模糊性查询的实验效果, 其主要原因在于: 因用户提交稀有查询的频次较少, 此类查询中所包含的Session信息较少, 相对非稀有查询来说, 此类查询较难从Session中推荐与之相关的候选查询; 又因用户提交模糊性查询时, 自身对该查询的意图不明确, 常常构造与之无关的查询, 相对非模糊性查询来说, 同一Session中包含更多噪声查询, 其最终查询推荐的效果较低。所以, 如何提高稀有查询和模糊查询的推荐效果是后续一项重要研究工作。