基于日志和知网的查询推荐

〔摘 要〕考虑到传统的基于日志的查询推荐算法受到数据稀疏问题的影响,本文在分析查询日志的基础上,构建查询词与点击URL之间的双向图,计算查询词与候选词之间的相似度.然后基于知网计算查询词与候选词之间的相似度,考虑词性和同义词因素对相似度的影响.最后将两个相似度分别赋予权重计算查询词与推荐词的相关度.实验结果表明,该方法不易受数据稀疏问题的影响,稳定性较好.

〔关 键 词〕查询日志；查询推荐；双向图

DOI：10.3969/j.issn.1008-0821.2013.10.015

〔中图分类号〕TP391.1〔文献标识码〕A〔文章编号〕1008-0821（2013）10-0065-05

随着互联网和基础设施的快速发展,搜索引擎已成为人们获取信息的重要来源.根据中国互联网络信息中心2012年7月19日发布的《第30次中国互联网络发展状况统计报告》中显示[1],截至2012年6月底,中国网民数量达到5.38亿,搜索引擎的使用率为79.7%.有学者研究表明,用户输入的查询通常只有两三个词[2],并且对所要检索的内容知之甚少,所以用户很难明确的表达自己的查询意图.查询推荐技术是向用户推荐若干个与用户输入相关的查询,能帮助用户生成更加符合其搜索意图的查询推荐词,引导用户的搜索行为,优化搜索结果.

本文在已有的查询推荐研究基础上,从两个方面对查询词和候选词进行相似度计算.文章的结构如下：第一节介绍查询推荐相关研究现状；第二节分别基于双向图和知网计算查询词和候选词的相似度；第三节介绍整个查询推荐算法的流程；第四节进行实验验证和评价；第五节做总结分析.

1相关研究

早在上世纪90年代,信息检索研究者就开展了一些查询推荐相关研究[3],查询推荐技术在检索和浏览过程中的确能提高检索的质量和效率.根据所依赖的数据源大致可以分为两大类：一是基于文档的推荐方法；二是基于用户查询日志的推荐方法[4].

基于文档的推荐方法主要通过处理包含查询词的文档来分析查询,从查询相关文档或人工编辑语料中找出与查询词相关的词或短语,然后利用这些相关词或短语构建推荐查询.有学者利用查询相关文档扩充查询以解决查询短的问题[5],也有学者利用伪相关文档检索查询相关词[6].

基于日志的方法依靠分析搜索引擎查询日志来寻找出现过的相似查询,并根据一定算法排序后择优推荐给用户.查询日志中记录了用户完整的搜索点击行为,基于查询日志的推荐方法逐渐成为近年来常用的方法.有学者认为在同一session内出现的查询有可能语义相近,利用相关的相似度算法来度量查询间的相关性[7].有学者提出一种基于查询共有相同点击URL数的查询推荐方法[8],在此基础上,有学者基于查询点击双向图提出了改进的SimRank相似度算法度量查询相关性[9-10].有学者基于一个大规模商业搜索引擎查询日志,利用查询数据内在的全局流行度来获得查询之间的相关性,并提出了一种基于流行度排序的查询推荐方法[11].也有学者研究查询日志中用户ID与点击URL之间的联系,提出基于主题与用户偏好分析的查询推荐方法[12].

基于日志的方法根据搜索历史推荐查询词,相对于基于文档的方法更符合用户查询特点.但是查询词在日志中的出现频率呈指数分布,大多数查询词在日志中出现次数不多,这使得基于日志的方法面临严重的数据稀疏问题.

考虑到日志中数据稀疏问题,本文将从两个方面对查询词和候选词进行相似度计算.首先基于构建的双向图计算查询词与候选词之间的相似度,然后利用中科院的分词系统对查询词进行分词处理,基于知网计算查询词与候选词的相似度,最终得到查询词与候选词的相关度,相关度满足条件的候选词即为推荐词.

2基于日志和知网的查询推荐算法

2.1基于双向图的相似度计算

查询日志的丰富与否直接影响候选查询集合的质量,因此要获得较好推荐的效果必须有丰富的查询日志.这里我们采用搜狗搜索引擎公开的查询日志库.日志的基本格式如表1：表1查询日志基本格式

如表1所示,每一条检索记录由访问时间（t）,用户ID（u）,查询词（q）,用户点击的URL（l）,该URL在返回结果中的排名（r）和该URL点击的顺序组成（o）.因此,一条检索记录可由〈t,u,q,l,r,o〉表示.在这里我们只考虑查询词和用户点击的URL两个因素,利用〈q,l〉构造查询词和点击URL的双向图.其中,查询词集合Q等于{q1,q2等qn}表示日志中出现过的查询词的集合,URL集合L等于{l1,l2等ln}表示日志中用户点击过的URL的集合.查询词结点qi到URL结点urlj的边eij由某一查询词节点出发到某一URL节点结束,表示用户输入该查询进行检索并在返回的结果中点击了相应的URL.边的权重wij是查询日志中eij出现的次数,一定程度反映了节点对之间的关联程度.边的集合E等于{eijqi∈Q,urlj∈L}表示了日志中所有的点击行为集合.

查询词与点击URL双向图如图1所示：

1图1查询词与点击URL双向图1

在对双向图的观察中发现,有些边的权重值偏小.考虑到用户使用搜索引擎的一些无意识的随机点击行为会增加一些噪音数据.我们设定阈值m等于4对边噪音数据进行过滤,删除权重小于m的边,再删除双向图中孤立的查询词节点和URL节点,减小双向图的复杂度.

在查询词推荐的研究中发现,查询日志中两个查询词有相近的语义关系,将有较多的点击URL共现.基于此检测设本文使用双向图的URL结点集合来定义查询词,对于查询词节点集合Q与URL节点集合L,第i个查询词节点（qi）的特征向量为i：

i[j]等于wij1∑θijw2ij1eij存在

01eij不存在（1）

其中wij表示第i个查询词到第j个URL的边的权重.那么,对于查询词queryi和候选词queryj的相似度可以采用余弦距离计算：

Simquery（queryi,queryj）等于i×j1i×j（2）

2.2基于知网的相似度计算

《知网》是我国著名机器翻译专家董振东先生创建的一个知识系统.在《知网》的结构中,词是用概念来描述的,一个词可以表达为几个概念,而概念则用义原来描述,义原是用于描述一个概念的最小意义单位.

2.2.1词性因素

我们认为在推荐的候选词中,含有越多原查询中权重值大的词语,其与查询词的相似度就越高.例如查询词“华山风景”,华山作为惟一的专有名词,出现的频率较低,应具有更高的权重.在推荐的候选词中,“华山简介”就应该比“泰山风景”相似度更高.

首先利用中科院的分词系统对查询词进行分词处理,对于查询词query,经过分词处理,得到关 键 词集合query等于{t1,t2等tn}（n为查询词q中含有的关 键 词个数）.根据关 键 词被标注的词性,赋予关 键 词不同的权重.

weight（t）等于1.0t为专有名词

0.8t为普通名词

0.6t为动词

0.4t为形容词

0.2其它（3）

关 键 词词性对候选词的相似度的影响计算如下：

Simetymology（queryi,queryj）等于∑n1i等于1weight（ti）ifti∈queryj（4）

其中,queryj为推荐候选词,ti为查询词queryi所含的关 键 词,n为关 键 词个数.weight（ti）是查询词中第i个关 键 词的权重.

2.2.2同义词因素

我们认为同义词因素对查询推荐效果也存在同样的影响.如查询词“华山图片”就应该和“华山照片”、“华山风景”等在语义上有较大的相似度.在这里我们利用知网来计算查询词与候选词之间的相似度[13].

检测设词语K1有n个概念S1i,S12等S1n,K2有m个概念S21,S22等S2m,本文中定义词语K1和K2的相似度是其所有概念之间相似度的最大值：

Sim（K1,K2）等于Max（Sim（S1i,S2j））（5）

其中,0

用于描述概念的义原分为基本义原、关系义原和关系符号义原.概念间的相似度计算表示为：

Sim（S1,S2）等于∑31i等于1βi∏i1j等于1Simj（P1,P2）（6）

其中,Simj（P1,P2）分别表示3种描述义原的相似度,βi是可调节的参数,且有β1+β2+β3等于1,β1≥β2≥β3,1≤i,j≤3.

义原之间的相似度一般依据义原的层次结构来计算,本文基于两个节点之间的路径长度来计算：

Sim（P1,P2）等于α1α+distance（P1,P2）（7）

其中,P1和P2表示两个义原,distance（P1,P2）是P1和P2在义原层次体系中的最短路径,α是一个可调节的参数.

同义词对候选词的相似度的影响计算如下：

Simtongyici（queryi,queryj）等于∑n1i等于1∑m1j等于1weight（ti）Sim（ti,kj）（8）

其中,m,n分别为候选词和查询词中关 键 词的个数.Sim（ti,kj）为查询词中第i个关 键 词与候选词中第j个关 键 词的相似度.

2.3查询词与候选词的相关度计算

我们先利用双向图计算了查询词与候选词的相似度,然后在分词的基础上,基于知网计算了查询词与候选词之间的相似度.我们可以得到候选词与查询词的相关度计算方法：

Relation（queryi,queryj）等于γ1Simquery（queryi,queryj）+γ2Simtongyici（queryi,queryj）+γ3Simetymology（queryi,queryj）（9）

其中,γi是可调节参数,且有γ1+γ2+γ3等于1.

3查询推荐算法流程

由于搜索引擎的广泛使用,查询日志每个月新增约2000万条点击记录.随着日志的不断增长,算法需要动态支持添加新的查询词与点击日志.算法步骤如下：

步骤1：遍历双向图中查询词集合的节点query∈Q,获取与query相连的所有点击URL节点集合Lq.

步骤2：遍历query的点击URL节点集合Lq,获取Lq相连的查询词节点集合q∈Q′.

步骤3：遍历与query可能相近的查询词集合Q′,计算query与q的相关度,并根据相关度大小降序排序,选取前k个词做为与query相近的查询词,本文取k等于10.

算法流程如图2所示：

1图2查询推荐算法流程1

如图2所示该算法只需扫描一遍查询词集合,便可以挖掘出每个查询词的语义相近查询词.并且,对于新加点击行为,只需修改新加边的权重,针对该查询词重新执行算法步骤2与步骤3,获取到该词的候选词序列便可,不影响其他查询词的计算结果.

4实验结果与评价

4.1实验数据

本文采用搜狗查询日志作为数据集,该数据集记录了搜狗搜索引擎在2006年8月的所有用户查询记录,其中包含了19562507条点击行为,2898971条查询词,8018410条点击URL.根据实验中的多次尝试,我们将几个参数值设置如下：α等于1.5,β1等于0.5,β2等于0.3,β3等于0.2,γ1等于0.5,γ2等于0.3,γ3等于0.2.

4.2实验环境

实验用的系统是WindowsXP,开发环境是VisualStudio.NET,开发语言是C++,数据库环境是SQLServer2000.4.3实验结果

由于查询短语的相关性带有极高的主观性,不同的人由于背景或兴趣的不同,同一组推荐结果也会有不同的评价结果.目前这方面的研究还没有一个标准的评价标准,通常都采取随机选取查询并进行评分.我们从查询日志中随机抽取10个查询词,得到与每个查询词相关度最高的10个候选词,同时也从百度搜索引擎中获取10个候选词.

例如随机抽取的查询词为“华山照片”,按照我们的方法和百度得到的推荐词如下表所示：表2我们的方法得到的推荐词

华山的照片1华山图片1华山的图片1华山风景1华山风景照片华山天气1华山旅游1华山门票1华山攻略1华山住宿

表3百度搜索引擎得到的推荐词

华山的照片1华山医院1上海华山医院1华山一日游1华山门票华山住宿1翠华山1西安华山

山顶住宿1华山天气1华山论剑

我们请50个同学对推荐结果进行评价.根据结果的相关性从0～5分进行评分,最高分为5分,表示该推荐词与查询词十分相关,最低分为0分,表示推荐词与查询词毫不相关.当分值小于或等于1时,该推荐词与查询词不相关.评价结果图3所示：1图3查询评价效果图1

从图3中可以看出,百度的平均值为3.85,但不同的查询词得到的相关度评价波动幅度较大,说明结果受到数据稀疏的影响较大.用我们的方法得到的相关度评价的平均值为3.77,略低于3.85,但每个查询词的评价结果都在很小范围内浮动,说明我们的方法不易受数据稀疏的影响,稳定性较好,具有一定的实际价值.

我们定义集合A为推荐系统返回的10个推荐词,集合R为所有相关的推荐词,即评分大于1的推荐词.推荐词的精确度定义为：

Pre（query）等于R1A

根据以上方法,如图4所示,我们得到推荐词的精确度.从图中可以看到我们的方法得到平均精确度为7.04,与百度的方法非常接近.即平均每10个推荐词中,大约有7个与查询词相关.

1图4查询精确度

5总结

本文基于搜狗查询日志,通过构建查询词与点击URL双向图和分词处理,分别基于双向图和知网计算查询词与候选词之间的相似度.实验表明,该方法不易受数据稀疏的影响,稳定性较好.在今后的工作中,将进一步简化双向图的复杂度,减少系统的时间消耗,进一步挖掘查询日志中的相关信息,实现基于用户和主题的个性化推荐,提高检索怎么写作的效率和质量.