Corresponding author: ZHANG Bin, professor, E-mail: zhangbin@mail.neu.edu.cn
搜索引擎使人们能从丰富的信息资源海洋中快速找到所需信息,但存在词典匹配问题[1].查询扩展技术是解决这一问题的有效方法.目前,查询扩展技术根据扩展词的来源和提取方法不同可分为基于全局分析[2]、基于局部分析[3]、基于用户查询日志[4]和基于语义资料[5],实验结果表明,在一定的条件下,这些方法可以提高查询质量,改善搜索性能.
前人研究结果表明,当搜索日志中存在大量关联查询时,基于用户查询日志的查询扩展方法能够提高查询质量,但是基于用户查询日志的查询扩展存在两个影响查询扩展效果的问题.首先,数据稀疏问题,导致基于搜索日志进行查询扩展的方法无法提取有效的相关查询词,致使查询扩展性能不佳.其次,数据时效性问题,导致扩展出的查询词没有反映当前文档集的真实状态;搜索日志和当前文档集的时效性关联度不够,出现找不到新文档的现象,影响查询性能.
本文针对数据稀疏问题和时效性问题,提出了基于搜索日志与局部上下文的查询扩展方法.该方法合并基于搜索日志提取的候选扩展词和结合时效性改进的局部上下文查询扩展方法抽取的候选扩展词,通过判断候选扩展词的查询性能,提取查询性能高的M个扩展词,加入到原查询中构成最终的查询.实验结果表明,本文的查询扩展方法有效地解决了存在的数据稀疏问题和时效性问题,提高了查询性能.
1 基于搜索日志与局部上下文的查询扩展方法近几年,越来越多的学者对查询扩展方法进行了研究.文献[6]分别基于搜索日志和组合方法进行了研究,提出了相应的查询扩展方法,提高了查询性能.但当搜索日志存在数据稀疏和时效性问题时,提取的扩展词较少或很旧,将会很大地影响查询扩展的质量.在用户查询词较少时会出现查询扩展效果不佳,在搜索日志过旧时,会遗漏新的文档信息,尤其对新闻类的信息检索影响更明显.针对这一问题,本文提出了基于搜索日志与局部上下文的查询扩展方法(query expansion method based on search log and local context QEMSLLC),从局部文档集提取查询候选扩展词来弥补基于用户日志候选扩展词较少和时效性不强的缺陷,提高查询效能.
1.1 QEMSLLC的基本思想本文方法的基本思想:依据用户输入的查询词,利用用户日志挖掘的查询扩展方法获得候选扩展词集.如果存在数据稀疏问题,导致扩展词数量很少时,继续判断是否存在时效性问题,若存在,则利用处理时效性问题的局部上下文查询扩展方法来选取扩展词,若不存在,则通过不处理时效性问题的局部上下文查询扩展方法选取扩展词,合并两个候选扩展词集,计算扩展词权重,并依据扩展词选取规则提取扩展词作为最后的扩展词集.如果不存在数据稀疏问题,但搜索日志数据很旧,时效性差,即存在数据时效性问题时,利用处理时效性问题局部上下文查询扩展方法来选取扩展词,合并两个候选扩展词集,计算词项时效价值度和权重,并依据扩展词选取规则提取扩展词作为最后的扩展词集.QEMSLLC的总体流程如图 1所示.
在本文方法的总体流程中有3个关键问题需要解决:一是如何判断是否存在数据稀疏问题;二是如何判断是否具有数据时效性问题;三是两个扩展词集如何有效合并问题.在本文查询扩展方法中采用了基于用户日志挖掘的方法、局部上下文分析的查询扩展方法[7]和查询性能预测方法[8],这些方法为本文的研究工作提供了基础.同时依据以下思想,分别解决上述3个问题.
1) 对于数据稀疏的判断问题.如果词汇在搜索日志中出现较少,则无法直接从搜索日志中获取有价值的信息实现查询扩展.此时,单纯基于搜索日志的查询扩展方法便无法取得高质量的结果.针对此类搜索请求,考虑从局部上下文中提取相关概念,补充从稀疏的搜索日志中选取的扩展词,实现查询扩展.由于词汇的出现情况为连续值,以固定阈值的方式判断词汇出现是否稀疏的方法并不科学合理,因此考虑定义比例函数f(x),其中x为词汇在搜索日志中出现的次数.以此为基础,融合分别从搜索日志和局部上下文提取的扩展词结果集,实现对具有稀疏性词汇的有效查询扩展.
2) 对于时效性的判断问题.搜索日志具有时效性.在用户查询后出现的新的相关文档包含时效性更强的相关扩展词,而基于用户日志的查询扩展方法无法获得这些扩展词,进而降低查询性能.为获取时效性强的扩展词,提出词项时效价值度来衡量候选扩展词的时效性强弱,词项时效价值度值越大,词项的时效性越强,反之越低.融合分别从搜索日志和局部上下文提取的扩展词结果集,实现对具有时效性词汇的有效查询扩展.
3) 对于扩展词集的合并问题.为从基于搜索日志提取的候选扩展词集和基于局部上下文提取的候选扩展词集中提取查询性能高的扩展词,根据扩展词判定规则,通过计算扩展词的查询性能,从大到小选取具有高查询性能的前m个扩展词,作为最终扩展词.
1.2 数据稀疏和时效性问题判定规则 1.2.1 数据稀疏性问题判定规则如果查询词在搜索日志中出现次数比较少,则一定无法扩展出好结果,因此可以用局部上下文选取扩展词进行补充.
因此,假设使用跳跃函数
并以查询词出现次数x=5为标准判断是否稀疏,那么,稀疏性可以定义为f(x)×日志+(1-f(x))×文档.
其意思是如果x>5,就全用基于搜索日志的扩展词集,否则就用基于搜索日志和局部上下文的两种扩展词集.接下来,考虑一个光滑的函数
f(x)=1/(1+e-(x-5)) ,
其意思是,当查询词出现5次的时候,这个概念既是稀疏的,又是不稀疏的,因此当x<5时就倾向于稀疏,x>5时就倾向于不稀疏.此时进一步定义为f(x)×日志+(1-f(x))×文档.
这是第二次定义,唯一的改变是修改了f(x)的形式.因此,可以令Q为搜索日志中的查询词集,q为查询,x为q在Q中出现的次数,比例函数f(x) = 1/(1+e-(x-α)),当f(x)< 0.5时,称为搜索日志对q是稀疏的,α为阈值.
1.2.2 数据时效性问题判定规则文档的创建时间离当前系统时间越近,文档的时效性越强,文档中的词项时效价值越高,反之越低.在搜索日志之后出现与查询词相关的仅包含新概念的文档,这时搜索日志会存在时效性问题.因此,可以定义搜索日志对查询词存在时效性问题.
令Q为搜索日志中的查询词集,q为查询,td为q在Q中出现的最后时间,t′d为与q相关的新文档出现的最新时间,当t′d>td时,称为搜索日志对q存在时效性问题.
同理可以定义词项时效价值度,利用以e为底,文档的时间属性与当前系统时间的比值为幂的指数函数来度量词项的时效价值,即词项时效价值度(timeliness):
其中:d表示词项t所在的文档最后修改时间;s表示当前系统时间.词项t与查询Q的相关度可以用增加词项时效价值度的改进局部上下文分析的相关度公式来计算,即
1.3 基于扩展词权重计算的候选集合并方法定义扩展词权重:对来源于搜索日志里的候选扩展词集T和文档集的候选扩展词集T′,设λ∈(0,1)为权重调节因子.当扩展词t在词集T和T′中同时出现时,加大其权重值,当扩展词t仅在词集T中出现时,降低其权重值,当扩展词t仅在词集T′中出现时,保持其权重值.即
则最终扩展词权重为两个候选扩展词词集的合并规则:
1) 当搜索日志存在稀疏问题时,若不存在时效性问题,则利用式(3)计算候选扩展词集T和T′中的扩展词权重,若存在,则利用式(4)计算候选扩展词集T和T′中的扩展词权重,选择权重值大的前m个词作为最终扩展词加入初始查询.
2) 在搜索日志存在时效性问题时,可以利用式(4)计算候选扩展词集T和T′中的扩展词权重,选择结果值最大的前m个词作为最终扩展词加入初始查询.
本文查询扩展方法与其他基于用户查询日志的查询扩展方法最大的不同是,解决了搜索日志存在数据稀疏或时效性问题时,查询扩展质量不高问题.针对搜索日志查询词数据稀疏问题,通过搜索日志扩展后的查询搜索到相关文档,依据局部上下文的相关度计算提取候选扩展词补充扩展词.针对搜索日志的时效性问题,通过选择查询后的新文档,依据局部上下文的相关度和词项时效价值度计算提取时效性强的扩展词.然后通过计算扩展词的查询性能选取查询性能高的词作为最终扩展词.
2 实验与分析本文实验采用标准的MAP,Prec@10,Prec@20指标,对比分析查询扩展方法的查询性能.实验的基线(baseline)是没用任何查询扩展方法的向量空间模型系统搜索结果.在实验后,可在全部的查询集合上,综合对比分析基准系统结果(baseline) 、基于用户日志挖掘取得的结果( QE on log)以及基于搜索日志与局部上下文查询扩展后的结果(QEMSLLC).
本文实验采用了Sogou搜索引擎提供的2012年的用户搜索日志.为避免影响实验效果,保证实验结果客观实用,在实验时将系统时间调整为2012年,并且不选择用户搜索日志截止时间以后的文档作为局部上下文查询扩展方法中的文档.
在实验中,使用与用户初始查询相关的前50篇文档作为提取查询扩展词的来源.选择前20个与用户初始查询关联度最高的词为最终查询扩展词.λ=0.6,α=20.
使用“方太”、“闹钟”、“卤菜”、“山吉树”、“紫檀木”、“山语城”、“美丽人生”7个用户查询词作为测试用查询,当搜索日志存在数据稀疏问题时,查询扩展性能对比结果见表 1.
使用“最新电影”、“美国总统”、“流行歌曲”、“年终总结”、“马年运势”、“足球世界杯”、“元旦祝福语”7个用户查询词作为测试用查询,当搜索日志存在数据时效性问题时,查询扩展性能对比结果见表 2.
从表 1,表 2中可以看出,查询扩展比没有查询扩展提高了搜索性能.当搜索日志存在数据稀疏问题时,本文方法比基于搜索日志的查询扩展方法提高了搜索性能,其中MAP提高了8.8%.当搜索日志存在数据时效性问题时,本文方法比基于搜索日志的查询扩展方法提高了搜索性能,其中MAP高出4.6%.
3 结论本文提出的基于搜索日志与局部上下文的查询扩展方法有效地解决了基于用户查询日志的查询扩展方法存在的数据稀疏和时效性问题.实验结果表明本文方法虽然查询执行平均时间稍长,但在可接受范围内,并取得了很好的查询效果,提高了查询性能.
[1] | Furnas G W,Landauer T K,Gomez L M ,et al.The vocabulary problem in human-system communication[J].Communication of ACM,1987,30(11):964-971.(1) |
[2] | Runkler T A,Bezdek J C.Automatic keyword extraction with relational clustering and Levenshtein distances[J].Institute of Electrical and Electronics Engineers, 2002,9(2):636-640.(1) |
[3] | Buckley C,Salton G,Allan J,et al.Automatic query expansion using SMART[C]//Proceedings of the 3rd Text Retrieval Conference.Gaithersburg:Comell University,1994:69-80.(1) |
[4] | Cui H,Wen J R,Nie J Y,et al.Probabilistic query expansion using query logs[C]// Proceedings of the 11th International Conference on World Wide Web.New York,2002:325-332.(1) |
[5] | Fang H.A re-examination of query expansion using lexical resources[C]//Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics.Clumbusohio,2008:139-147.(1) |
[6] | Pal D,Mitra M,Datta K.Query expansion using term distribution and term association[J].The Computing Research Repository,2013,21(3):1-19.(1) |
[7] | Xu J X,Croft W B.Improving the effectiveness of information retrieval with local context analysis[J].ACM Transactions on Information Systems,2000,18(1):79-112.(1) |
[8] | He B,Ounis I.Inferring query performance using pre-retrieval predictors[C] //The 11th International Conference on String Processing and Information Retrieval.Padova,2004:43-54.(1) |