（计算机应用技术专业论文）上下文相关的查询推荐算法研究.pdf

河南大学硕士研究生学位论文 摘要 随着互联网的快速发展，搜索已成为当前最重要的网络基础应用之。但是， 目前的搜索结果并不能让人足够满意。对搜索引擎来说，如何通过用户提交的查 询关键字，返回满足用户需求的搜索结果，是判断搜索性能的关键指标。目前搜 索引擎公司和研究人员通过多种方式试图理解用户的搜索目的，生成查询推荐是 满足用户意图中很重要的一环。在实际应用中，查询推荐表现为搜索引擎提供的 “相关搜索 。 传统的生成查询推荐的方法主要通过语义分析、文档内容分析、锚文本研究 来产生推荐；近期的方法主要是通过挖掘搜索日志来生成查询推荐。一是利用在 同一个s e s s i o n 中邻近的或同时发生的查询作为彼此的推荐。这种方法能够有效的 提供有意义的查询推荐，但仅考察用户刚提交的查询，没有充分的考虑上下文序 列。另一种是上下文相关方法，通过预测后缀树模型来生成查询推荐，但在查询 s e s s i o n 划分方面存在粒度过大的问题。 提高查询推荐的准确性可以提升用户的搜索体验，在个性化搜索、提高用户 忠诚度、精准广告投放等方面有很广应用前景。本文具体做了以下方面的工作： 1 s e s s i o n 划分研究。为了生成查询推荐，首先需要对搜索日志中的s e s s i o n 进行划分。有两个问题需要解决：一是选取划分方法，这决定了如何自动划分 s e s s i o n 。本文根据对所采用的搜索日志进行分析，采用了一种时间间隔法。二是在 同一个s e s s i o n 中，如何利用已经提交的查询，对用户的下一个查询进行判断和预 测。 2 改进序列生成模型。v m m 模型是n g r a m 算法的扩展，考虑了用户的上下 文信息，也能很好的解决可变长的上下文输入问题。但在v m m 模型的建立过程 中，预测后缀树的生长率参数s 要根据经验得到。占值过大，就会丢失上下文信息； 占值过小，就会出现训练集数据过分拟合。本文通过训练多个不同边界的v m m 模 第1 i 页河南大学硕士研究生学位论文 型，建立了扩展的v m m 模型- e v m m 。得到更准确的占值，解决了上下文信 息丢失和训练集数据过分拟合的问题。 3 实验验证。生成查询推荐分为训练和测试两步。在训练阶段，对搜索日志 的s e s s i o n 做出准确的划分，然后生成扩展的序列查询预测模型；在测试阶段，根据 输入的序列得到概率最大的前n 个查询推荐。 本文改进了查询推荐算法，并在搜索日志上进行比较和实验验证。结果表明， 本算法能很好的从搜索日志中建立推荐模型，在测试集中具有更好的准确度和覆 盖率，并具有较低的时间和空间复杂度。 关键词：查询推荐；搜索目的；上下文序列；搜索日志。 河南大学硕士研究生学位论文第1 i i 页 a b s t r a c t w i t hr a p i dd e v e l o p m e n t ，w e bs e a r c hh a sb e c o m eo n eo ft h em o s ti m p o r t a n t a p p l i c a t i o n so ft h ei n t e r a c t h o w e v e r , p e o p l ea r en o ts a t i s f y i n g 、拥n 1t h ec u r r e n ts e a r c h r e s u l t s a st os e a r c he n g i n e s ，h o wt oa c c u r a t e l yg r a s pt h eu s e r ss e a r c hi n t e n ta n dr e t u r n t h e ms a t i s f a c t o r ys e a r c hr e s u l t st om e e tt h e i rn e e d si sak e yi n d i c a t o rt oj u d g es e a r c h p e r f o r m a n c e c u r r e n t l y , s e a r c he n g i n ec o m p a n i e sa n dr e s e a r c h e r st r yt ou n d e r s t a n d u s e r s 。s e a r c hi n t e n ti nm a n yw a y s ，g e n e r a t i n gq u e r yr e c o m m e n d a t i o ni sa v e r yi m p o r t a n t p a r t i np r a c t i c e ，t h eq u e r yr e c o m m e n d a t i o np e r f o r m sa st h e ”r e l a t e ds e a r c h e s ” t h et r a d i t i o n a lm e t h o do f g e n e r a t i n gq u e r yr e c o m m e n d a t i o np r i m a r i l yb ys e m a n t i c a n a l y z i n g ，d o c u m e n tc o n t e n ta n a l y z i n ga n da n c h o rt e x ts t u d y i n g s o m er e c e n tw o r kh a s u s e ds e a r c he n g i n el o g sf o rq u e r yr e c o m m e n d a t i o n o n em e t h o du s e dq u e r i e st h a ta r e a d j a c e n to rc o - o c c u ri nt h es a m eq u e r ys e s s i o n sa sc a n d i d a t e sf o rr e c o m m e n d a t i o n i t c a ne f f e c t i v e l yp r o v i d eam e a n i n g f u lr e c o m m e n d a t i o n , b u to n l ye x a m i n eq u e r yi s s u e d j u s tn o w , t h ec o n t e x tq u e r ys e q u e n c e i sn o ts u f f i c i e n t l yc o n s i d e r e d a n o t h e ri s c o n t e x t - a w a r em e t h o d b yu s i n gp s tm o d e lt op r o v i d er e c o m m e n d a t i o n ，b u ti th a v et h e g r a n u l a r i t yo v e r s i z e dp r o b l e mi ns e s s i o nd i v i s i o n i m p r o v i n gt h eq u e r yr e c o m m e n d a t i o na c c u r a c y c a l l p r o m o t et h eu s e r s s e a r c h e x p e r i e n c e i ta l s oh a sav e r yb r o a da p p l i c a t i o np r o s p e c t si np e r s o n a l i z e ds e a r c h ， i n c r e a s i n gu s e rl o y a l t y , a c c u r a t e l ya d v e r t i s i n ga n ds oo n t h ec o n t r i b u t i o n so ft h i sp a p e r a r es u m m a r i z e db e l o w ： 1 s t u d y i n gs e s s i o nd i v i s i o n i no r d e rt og e n e r a t et h eq u e r yr e c o m m e n d a t i o n y o u n e e dt od i v i d es e s s i o ni ns e a r c hl o g s t h e r ea l et w oi s s u e st h a tn e e dt ob ea d d r e s s e d f i r s t , s e l e c td i v i s i o nm e t h o d ，w h i c hd e t e r m i n e sh o wt oa u t o m a t i cd i v i d es e s s i o n b y a n a l y z i n gt h ec h o s e ns e a r c hl o g ，w eu s ea t i m ei n t e r v a la p p r o a c h s e c o n d ，i nt h es a m e s e s s i o n , h o wt oj u d g ea n dp r e d i c t i o nt h eu s e r sn e x tq u e r yu s i n gs u b m i t t e dq u e r y c o n t e x t 2 i m p r o v es e q u e n c eg e n e r a t i o nm o d e l v m mm o d e l i sa l le x t e n s i o no ft h en - g r a m 第页河南大学硕士研究生学位论文 a l g o r i t h m ，w h i c hc o n s i d e r su s e r sc o n t e x ti n f o r m a t i o na n dc a na l s ob eag o o ds o l u t i o nt o v a r i a b l el e n g t hc o n t e x t b u ti nt h i sm o d e l ，t h ep s tl e a r n i n ga l g o r i t h mp a r a m e t e r sa r e o p t i m i z e di ne x p e r i e n c e i ft h ev a l u eo fp a r a m e t e rs i st o ol a r g e ，c o n t e x ti n f o r m a t i o n m a yl o s e ；i fs i st o os m a l l ，d a t ao ft r a i n i n gs e tm a yo v e rf i t b yt r a i n i n gv a r i o u s b o u n d e dv m mm o d e l ，w eb u i l de x t e n d e dv m mm o d e 卜- e v m m ，a n dg e tm o r e a c c u r a t ev a l u e ，a d d r e s s e st h ec o n t e x ti n f o r m a t i o nl o s sa n dt r a i n i n gs e td a t ao v e rf i t t i n g p r o b l e m s 3 e x p e r i m e n t q u e r yr e c o m m e n d a t i o n c o n s i s t so f t w op h a s e s ：t r a i n i n ga n dt e s t i n g i nt h et r a i n i n gp h a s e ，w et r e a te a c hs e s s i o nf r o mt h es e a r c hl o gd a t aa sas e q u e n c eo f q u e r i e sa n db u i l dap r o b a b i l i s t i cp r e d i c t i o nm o d e l i nt h et e s t i n gp h a s e ，w ef e e dt h e o b s e r v e dq u e r yc o n t e x tf r o mau s e rt ot h ep r e d i c t i o nm o d e la n ds u g g e s tt h et o pn q u e r i e s 、析mt h eh i g h e s tp r e d i c t i o ns c o r e sa sq u e r yr e c o m m e n d a t i o n s i nt h i s p a p e rw ei m p r o v et h ea l g o r i t h mo fg e n e r a t i n gq u e r yr e c o m m e n d a t i o n , c o n d u c ta ne m p i r i c a ls t u d ya n dc o m p a r et h e mi ns e a r c hl o g s t h er e s u l t ss h o wt h a to u r a p p r o a c hc a nb u i l dw e l lp e r f o r m a n c em o d e l ，h a v eb e t t e ra c c u r a c ya n dc o v e r a g e ，a n d h a v el o wt i m ea n ds p a c ec o m p l e x i t y k e yw o r d s ：q u e r yr e c o m m e n d a t i o n ；s e a r c hi n t e n t i o n ；c o n t e x to ft h eq u e r y s e q u e n c e ；s e a r c hl o g s 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的对所研究的课题有新的见解。据我所知。除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发袁或撰 写过的研究成果。也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所徽的任何贡献均已在论文中作 了明确的说明并表示了谢意。_ 秀一未。77 、j ：? ， 学位中；又? 。学位喜羔毒茹茹蓄：蝴学位中请人( 学位论竟作者) 鍪名：望纷塑竺i 兰i ；：j # j ，。j ：j p 、i ；一3 j 。fj 一，j 。- ；。j ， ? ，。i ；? j j ： j ：、：7 ，o f 夕。| j ；j 。“。j ? 2 j ，、 j ；。，j ，。j ：曩1 ，一、“，：j 乒，：；，2 0c d 年月- “v “i , , 日 i 嘶，一，o ；：。托 ， 1 7 ， 占v ，干月 口 三? ：，每一一t 名。 ： ，：j ? ，。i ； | 、j”；。，。 ，4 又l7 一二； j ，o ，。：；? ：j ：! ：，t _一j ，? i j j j j ，。 v ，k 。t ? 7 ，+ ：j 器j - ：妻j 。，一 ，i 。： ： j i ；关于学位论文著作权使用授权书要 0pj 、0 o ii 。凌i ，i j ? ，j 一j_ t j 誊 本人经河南大学审核批准授予硕士学位。作为学位论文的作者本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 甄质文 本和电子文本) 以供公众检索、奎吼本 授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的。可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇蝙学位论文( 纸质文本和电于文本) ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 鍪名：型趟 2 0 ，口年月矽日 学位论文指导教师签名：姜乒l 2 0co 年6 月仂曰 河南大学硕士研究生学位论文第l 页 第1 章绪论 查询推荐是其他有相似搜索需求的用户所选择的查询词，根据这些查询词被 搜索的热门程度以及与当前用户所选择的查询词之间的相关性，由系统自动判断 后产生。提高搜索体验的方式之一就是提高用户查询推荐的准确性。 1 1 研究背景 随着互联网的快速发展，用户信息需求的不断提高，搜索引擎发展迅速。中 国互联网络信息中心统计1 ，截至2 0 0 9 年1 2 月底，中国网民已经达到3 8 4 亿人， 搜索引擎用户规模已达到2 8 亿人，在网民中的使用率达到7 3 3 ，超过了即时通 信，排名仅次于网络音乐和网络新闻，成为网民使用互联网的第三大应用。 网络信息量的与日俱增，海量信息丰富了人们的信息来源的同时，也给人们 获取信息造成了困扰。目前的搜索结果并不能让人足够满意。对搜索引擎来说， 如何通过用户提交的查询关键字，准确把握用户的搜索目的，返回满足用户需求 的搜索结果，是判断搜索性能的关键指标之一【1 2 捌。搜索引擎公司和研究人员通 过多种方式试图理解用户的搜索目的，生成查询推荐( q u e r yr e c o m m e n d a t i o n ) 是 满足用户意图中很重要的一环。查询推荐是其他有相似搜索需求的用户所选择的 查询词，根据这些查询词被搜索的热门程度以及与当前用户所选择的查询词之间 的相关性，由系统自动判断后产生的。通常情况下，它排布在搜索结果页的左侧 和下方，点击相关搜索词可以直接获得这些词的搜索结果。在实际应用中，查询 推荐表现为搜索引擎提供的“相关搜索 。 相关搜索土显壁f 匿垒堂堕垒 薹重塑型! g 睑堂厘垒珏蔓重；茎煎土显堂壁垒至i 蔓盏 笾蔓金亘撞幽至匿堑叁茎燧堑 墓堂塞金丑蔓直鞋堕金星邋 图1 1在百度中搜索“世博会”时返回的相关搜索 1 v c w w c n n i c n e t c n 第2 页河南大学硕士研究生学位论文 2 0 0 9 年中国搜索引擎用户行为研究报告的调查显示2 ，当一次搜索得不到理想 结果时，有7 8 2 的用户采用“更换关键词 的方法重新搜索，有7 2 的用户会用 “增加或者减少关键词的方法重新搜索；这两个方法是用户选择率最高的。6 3 2 的用户会选择从结果中再次搜索，只有1 9 7 的用户表示放弃继续搜索。因此，提 高查询推荐的准确性可以有效的改善搜索结果，凭借日趋精准化、人性化的信息 检索服务提升了网民的使用率和认同度，助推搜索引擎的快速发展，进而提高搜 索引擎的市场占有率。 查询推荐是面向用户的搜索引擎的必要成分之一。在使用搜索引擎的过程中， 常见的一个现象就是用户需要多次提交或修正查询关键字才能找到满意的结果。 提交查询推荐并不是一件容易的事，因为查询关键字通常比较短，一般情况下， 英文2 3 个诟- j t s ，中文2 - 4 个词【4 7 】。因此对用户来说，没有“标准”或“最佳”的 查询关键字。另一方面，查询词本身的二义性或具有多种含义，需要在具体的语 言环境下才能准确的判断用户的查询目的【1 4 1 。查询推荐就是帮助用户生成能更好 的满足用户搜索意图的查询关键字。 1 2 研究应用与意义 2 0 0 4 年前后，很多搜索引擎公司，如百度、g o o g l e 、y a h o o ! 等都推出了专门 针对查询推荐的“相关搜索 服务。因为通过猜测用户的搜索意图，搜索引擎可 以推荐给用户更能满足他们搜索目的的查询。一个通用的方法就是把搜索日志中 相似的查询推荐给用户【3 6 】。另一个方法就是把同一个s e s s i o n 段里的查询作为彼此 的推荐【3 引。 尽管这些方法在查询推荐方面都取得了不错的效果，但是它们没有考虑到用 户的上下文信息，未把前后输入的查询作为一个整体来考虑。例如，当用户输入 一个查询“角斗士 ，很难判断他的搜索目的，因为不知道他是对角斗士的历史、 2 w w w e n n i c n e t c n u p l o a d f i l e s d o e 2 0 0 9 9 2 1 1 0 4 1 4 8 d o e 河南大学硕士研究生学位论文第3 页 历史上有名的角斗士还是电影角斗士感兴趣。不看上下文，以前的方法会给 出很多不同的推荐，这样查询推荐的准确度就比较低。 但是，如果我们发现在“角斗士之前，用户输入了一个查询“美丽心灵 ， 那么，用户就很有可能对电影角斗士比较感兴趣；更进一步，用户还可以对 主演罗素克罗演出的其他影片也感兴趣。包含用户提交的查询序列的上下文信 息能帮助搜索引擎很好的理解用户的搜索目的。 有人认为上下文信息数据序列长度不大，就能用传统的n g r a m 算法对序列进 行预测。然而这种选择方案相对于可变长的马尔科夫模型有两个主要缺点：是 无法确定序列的个数n ，二是训练大量的n g r a m 模型在实时性要求很高的搜索中 不可行。 查询推荐是一项有用的w e b 挖掘技术，其中大量采用了对搜索日志挖掘的方 法。查询推荐在很多领域都有广泛的应用，如查询相关增强、个性化搜索系统、 移动搜索系统、在线广告精准投放和其它网络应用等。 开展该领域的研究意义在于： 1 ) 在信息处理的全球竞争中，由于历史原因，中国的信息处理和应用都同 国际先进水平有一定差距。在w e b 挖掘技术方面，虽然不能说我们同西方站在同 一起跑线上，但网络搜索、移动搜索的兴起，大家都相对出于相同的起点，因此 对于我们来说，机会还很多。 2 ) 对查询推荐的研究有很高的学术起点，需要用到数据挖掘、信息检索等 领域的知识，许多关键技术都有待进一步的研究。研究和解决该领域的问题不仅 对w e b 挖掘领域有着巨大的理论和现实意义，而且对其他相关领域也起着模范和 带头作用。 1 3 查询推荐研究的核心问题与研究现状 搜索引擎的查询推荐技术仍处于快速发展阶段，这个领域中不少问题仍然没 有得到很好的解答：( 1 ) 用何种数据模型生成查询推荐? ( 2 ) 应该使用哪些方法 第4 页河南大学硕士研究生学位论文 和算法? ( 3 ) 如何度量查询推荐的准确度和覆盖率? 1 3 1 查询推荐数据模型及存在的问题 最近的工作主要通过挖掘搜索日志，利用“大众的智慧”来生成查询推荐。 例如，f o n s e c a 13 1 ，h a n t l 6 1 ，h u a n g l l 5 1 等利用在同一个s e s s i o n 中邻接的( a d j a c e n t ) 或同时发生的( c o o c c u r ) 查询作为彼此的推荐。 查询推荐还存在如下的问题： 首先，邻接配对法( p a i r - w i s e ) 不能有效的抓住同一s e s s i o n 中有用的上下文 信息。j a s o n 等人【8 】使用“w w w d o g f i l e c o r n 搜索日志，通过分析三种主要的s e s s i o n 划分方法后得出结论，它们的查询s e s s i o n 的平均长度分别为2 8 5 ，2 3 1 ，2 3 l 。研究 表明，在很多情况下，在提交一个查询之后，用户接着输入的查询不止一个。因 此，需要一种更为通用的模型来代替邻接配对方法，因为它无法完全抓住代表用 户意图的查询上下文序列。 其次，很多不正确的s e s s i o n 划分仅能通过对前面的查询序列建模来修正。h e 等人【4 】通过对随机抽取的2 0 0 0 0 个s e s s i o n 进行人工标注，得到七种类型的s e s s i o n 模式，包括拼写错误、同义替换、概念范围扩大及缩小等。因此需要通过查询序 列来修正s e s s i o n 划分。 最后，查询词本身的二义性难以消除。上下文信息可以消减查询词的歧义， 提高查询推荐的准确性。如，当用户输入一个词”j a v a ”时，一时很难判断其目的是 ”j a v ai s l a n d ”还是”j a v al a n g u a g e ”。如果在j a v a 前输入的查询词是”i n d o n e s i a ”，则可 以断定用户对”j a v ai s l a n d ”更感兴趣。根据信息论，熵表示信息的不确定程度，熵 越低则其不确定性越低。对于给定的上下文查询序列，熵越低则其二义性越低。 例如，假设j a v a 出现了1 0 0 次，在”s u nj a v a ”中出现了6 0 次，在”j a v ai s l a n d ”中出 现了4 0 次，则其熵为o 2 9 。现在假设一个上下文序列中，j a v a 之前输入”i n d o n e s i a 9 次，s u nj a v a ”只有一次，则其熵就降低到了0 1 4 。这一结论证实了每一查询词 的概率都与其上下文序列条件相关。 河南大学硕士研究生学位论文第5 页 1 3 2 查询推荐方法架构 基于序列的查询方法有两个阶段，脱机模型训练阶段( o m i n em o d e ll e a r n i n g p h a s e ) 和联机查询推荐阶段( o n l i n eq u e r yr e c o m m e n d a t i o np h a s e ) 。在脱机模型训 练阶段，把从搜索日志中划分的s e s s i o n 作为个查询序列来训练，然后生成一个 概率预测模型；在联机查询推荐阶段，把用户输入的上下文序列提交到模型中， 生成前n 个( 例如，n = 5 ) 预测概率最高的查询作为推荐。本文用训练集代表脱 机模型训练，用测试集来代表联机查询推荐。 测试阶段的方法比较直观，问题的关键在于选取何种有效的查询序列预测模 型。我们考察了多个模型，最后把目标集中在了马尔科夫模型及其扩展上。这是 因为马尔科夫模型是通过参数方法来准确预测序列的分布，且已在复杂的序列如 自然语言处理和基因序列分析中成功应用。在马尔科夫模型及其扩展中，n g r a m 模型【1 7 】是最基础的一个。本文选取n g r a m 模型而不用更为复杂的模型，如隐马尔 科夫模型【3 2 1 ( h i d d e nm a r k o vm o d e l ，h m m ) ，最大熵马尔科夫模型1 1 跚( m a x i m u m e n t r o p ym a r k o vm o d e l ，m e m m ) ，条件随机场模型1 2 7 ( c o n d i t i o n a lr a n d o mf i e l d ， c r f ) 等，主要基于如下考虑：首先，在序列查询预测中，我们仅对用户提交的下 一个序列感兴趣，对预测或标记整个观察序列不感兴趣：其次，我们可以直接对 单个查询或查询序列建模，不需假设它们从其他未观察到的隐含状态中生成。 1 3 3 度量查询推荐的准确率和覆盖率 1 准确率。查询预测的准确率使用n d c g ( n o r m a l i z e dd i s c o u n tc u m u l a t i v e g a i n ) 3 0 】来计算。对于两个推荐序列列表，它假设排名高的列表更重要，通过比 较两个列表的相似度来计算预测准确率。 2 覆盖率。查询覆盖率是测试集中可预测的查询序列与所有查询序列的比值。 对任意给定的查询序列模型，好的查询推荐预测模型会努力做到尽可能供的覆盖 度。假设一个测试序y u q l ，q 2 ，没有在训练集中出现，则在一个3 - g r a m 模型中它 就不会被覆盖。但是，如果q 2 是训练集中有效的上下文，那么它就会被配对模型 第6 页河南大学硕士研究生学位论文 覆盖。 1 4 研究内容 v m m 算法【4 】采用预测后缀树的方法，目的也是建立可变长的马尔科夫模型， 但该算法有以下几个方面的不足：1 ) 选取s e s s i o n 的时候只考虑英文查询，因此 时间间隔过大。2 ) 进行查询预测时的v m m 算法对参数比较敏感，也不能很好 的得到针对性的模型。 针对以上不足，本文提出了相应的解决方法，提出了扩展的v m m 算法 e v m m 。该算法由以下三个阶段组成： 1 ) 数据预处理t 对搜索日志的数据进行初步分析、处理，使之成为程序能 够直接处理的数据。这些数据提供给下一阶段使用。 2 ) 数据训练阶段：对于处理后的数据，通过建立预测后缀树( p s t ) 的方法 得到训练模型。 3 ) 测试阶段t 使用测试数据对生成的模型进行检验，测试算法的性能，比 较几种算法的优劣。 概括来说，本文的主要贡献如下： 1 ) 选取一种更为合适的s e s s i o n 划分。s e s s i o n 的划分是建立查询预测模型的 前提，好的划分能建立更为准确的模型。 2 ) 提出一种扩展的混合数据模型。首先训练多个不同的v m m 模型，使其 不仅能生成多个边界的查询推荐，也能自动选取合适的边界以生成最佳的查询推 荐。 1 5 本文章节安排 本文共分为五章： 第一章为绪论。主要介绍查询推荐算法研究背景、研究现状和研究意义，并 简要说明了本文的研究内容。 河南大学硕士研究生学位论文第7 页 第二章为查询推荐相关技术概论。首先介绍搜索引擎的工作机制，其次介绍 搜索曰志，最后介绍搜索曰志中s e s s i o n 的定义与划分方法研究。 第三章为查询推荐算法研究。首先介绍早期查询推荐算法；其次介绍当前马 尔科夫模型及n g r a m 算法，讨论了上下文信息的有效性。并对各种算法的优缺点 进行了论述。 第四章描述上下文查询推荐的具体算法。首先介绍序列查询预测的基本理论， 其次介绍v m m 算法，论述了用可变长马尔科夫模型而不用其它算法的原因及优 势，描述了算法中用到的p s t 概念及具体步骤；最后针对v m m 算法的不足，给 出本文提出的对其的改进算法e v m m 。 第五章详细介绍实验数据，实验过程与结果，通过实验表明本文算法的正确 性与有效性。 第8 页河南大学硕士研究生学位论文 第2 章查询推荐相关技术概论 上一章主要讨论查询推荐的研究背景、意义及本文将要研究的具体内容。本 章首先介绍搜索引擎的基本工作原理，然后对搜索日志做详细介绍，最后对搜索 日志中s e s s i o n 的概念和划分分别做介绍，并对该研究方向的最新研究进展做具体 讨论。 2 1 搜索引擎的工作机制 本节对搜索引擎的组成和工作过程做一个简单的介绍，以便进一步了解查询 推荐的生成过程。 2 1 1 搜索引擎的工作过程 搜索引擎工作过程一般是三段式：抓取网页建立索引数据库在索引 数据库中搜索排序f 4 引。 1 抓取网页 搜索引擎利用h t m l 的特性存储大量的网页信息。这些网页信息主要通过网 络爬虫( 也叫网络蜘蛛) 在互联网上沿着各个链接自动抓取，网络爬虫沿着网页 中的u r l 爬到其它网页，并把爬过的网页搜集回来。网页抓取的工作需要考虑时 机：事先还是即时。考虑到对用户的响应时间，搜索引擎都是事先抓取。它通过 定期搜集或增量搜集的方式抓取大量网页，并保持在自己的服务器上。 2 建立索引 得到了海量的网页集合，离返回用户需求的信息还有很长的距离。搜索引擎 要对保存在服务器上的网页进行分析，提取相关网页信息。网页中的数据被保存 在索引库中以备以后的查询使用。首先提取网页中的关键词，然后对重复或转载 的网页进行消除，再对各种链接进行分析，最后对网页重要性进行判断，建立一 个倒排索引，存入索引数据库。 河南大学硕士研究生学位论文第9 页 3 在索引数据库中搜索排序 当用户向搜索引擎提交一个查询关键字后，搜索引擎首先对查询关键字进行 预处理，对于中文来说就是分词，英文不用分词。然后检查索引数据库，从中找 出和当前关键词最匹配的一系列网页的列表，返回给用户。通常情况下列表中包 含文档题目，文档内容摘要等。 分析搜索关键字 关键字转成w o r d l d 查找标引库得到d o c i d 列表 n n 遍历文档列表d o c l d 找到一篇? 立 y l - 计算文档等级 文档列表末尾? i yl - 结果按相关度排序 组织结果返回给用户 图2 - i 搜索引擎的工作流程 搜索引擎通过客户端程序接收来自用户的检索请求。用户输入的检索请求一 般是关键词或者是用逻辑符号连接的多个关键词，搜索服务器根据系统关键词字 典，把搜索关键词转化为w o r d i d ，然后在标引库( 倒排文件) 中得到d o c i d 列表， 对d o c i d 列表中的对象进行扫描并与w o r d i d 进行匹配，提取满足条件的网页，然 第1 0 页河南大学硕士研究生学位论文 后计算网页和关键词的相关度，并根据相关度的数值将前k 篇结果( 不同的搜索引 擎每页的搜索结果数不同) 返回给用户，其处理流程如图2 1 所示。 2 1 2 查询服务 搜索引擎返回给用户的，是一个和用户查询相关的结果列表【1 4 】。本节介绍搜 索引擎查询服务的过程。 建立索引数据库之后，系统关键词总体的集合和文档的集合一起构成了一个 倒排文件结构，使得一旦得到一个关键词输入，系统能迅速给出相关文档编号的 集合输出。 然而，用户通过搜索引擎看到的不是一个文档的“集合”，而是一个“列表 。 如何从集合生成一个列表，是服务子系统的主要工作。服务子系统的要求和其工 作原理主要体现在三个方面。 1 查询方式和匹配 查询方式指的是系统允许用户提交查询的形式。用一个词或者短语来直接表 达信息需求，希望网页中含有该词或者该短语中的词，是主流的搜索引擎查询模 式。这不仅是因为它的确代表了大多数的情况，还因为它比较容易实现。就英文 来说，查询是一个词的序列；就中文来说，它是包含若干个词的一段文字。中文 首先需要被“切词 ( s e g m e n t ) 或称“分词”，即把它分成一个词的序列。 2 结果排序 一旦建立了索引，搜索引擎就开始对文件进行等级评定并确定它们的相关性。 为呈现和评价搜索结果需要做两件事：一是查找包含了用户提问的网页；二是按 照相关性排定匹配网页的位置。常见的排序算法有h i l l t o p l 2 2 1 、p a g e r a n k 3 1 、词频 统计法等。p a g e r a n k 根据网站的外部链接和内部链接的数量和质量俩衡量网站的 价值。p a g e r a n k 的原理是，每个到页面的链接都是对该页面的一次投票，被链接 的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”衡 量多少人愿意将他们的网站和你的网站挂钩。p a g e r a n k 这个概念引自学术中一篇 论文的被引述的频度即被别人引述的次数越多，一般判断这篇论文的权威性 河南大学硕士研究生学位论文第1 1 页 就越高。词频统计法也就是向量空间模型采用的相似度计算方法。许多搜索引擎 都以索引项的词频和位置作为相关度的判定标准，采用前述的词频加权方法来计 算相关度。一个词在网页文档中出现的频率越高，它代表该文档主题的程度就越 大，其作为索引项的准确性也就越高，权值就越大。在与查询词匹配时，它胍代 表的文档与查询请求的相关度就越高。 3 文档摘要 搜索引擎返回的结果是一个有序的条目列表，每一个条目有三个基本的元素： 标题、网址和摘要。摘要需要从网页正文中生成。一般来讲，从一篇文字中生成 一个恰当的摘要是自然语言理解领域的一个重要课题，人们已经做了多年的工作 并取得了一些成果。常用的方法有基于文章中心段落位置法、基于与主题相关的 高频词汇的频率统计法、基于文章段义的文章框架法、对特殊领域的信息提取法、 基于语法分析和语义分析的理解分析法等。但在当前h t m l 语言框架下，网页写 作的不规范和语言理解算法的复杂性耗时太多，搜索引擎需要处理海量的信息， 难以适应其实时性要求。因此常在建立文档索引阶段后记住每个关键词在文档中 出现的位置。 查询服务返回的内容还有一些细节的支持。如拼音提示。如果用户只知道某 个词的发音，却不知道怎么写，或者嫌某个词拼写输入太麻烦，搜索引擎的“拼 音识别提示功能可以解决这个问题；错别字提示。由于汉字输入法的局限性， 用户在搜索时经常会输入一些错别字，导致搜索结果不佳。搜索引擎会给出错别 字纠正提示。错别字提示显示在搜索结果上方。如，输入“唐醋排骨 ，搜索引擎 会提示“您要找的是不是糖醋排骨”。还有英汉互译、网页快照等。这些都从 各个角度吸引用户，提高用户粘性。 2 2 搜索日志 搜索日志是记录用户和搜索引擎所有交互行为的文本列表。其中包含了大量 的数据信息，如用户的点击信息、查询词频度等【2 】。 第1 2 页河南大学硕士研究生学位论文 2 2 1 搜索日志格式 本文选用搜狗查询日志作为代表。用于分析的搜狗查询日志由一系列查询需 求组成，每个查询需求都包括如表2 1 所示条目。 表2 1 搜狗搜索日志内容 名称记录内容 q u e r y u i 也 t i m e r a n k o r d e r i d s u b m i t t e ri n f o r m a t i o n 用户提交的查询 用户点击的结果地址 用户点击发生时的日期、时间 该u r l 在返回结果中的排名 用户点击的顺序号( 这是用户点击的第几个页面) 由系统自动分配的用户标识号 浏览器信息，计算机信息 2 2 2 查询的定义 定义1 查询：用户向搜索引擎提交的查询请求。用户的一次查询过程包括向 搜索引擎提交查询关键字、点击相应的u r l ( 包括翻页) 。翻页在不同的系统中会 有一定的差别，比如有的搜索引擎把每翻一次页相当于用同一查询词的又一次查 询，系统又得到一个用户查询日志，而有的搜索引擎把翻页标记为同一次查询【4 9 】。 定义2 查询词：用户查询请求中的关键词，又称关键字。 在对搜索日志的分析中，不引起歧义的情况下，本文利用“查询 来代指“查 询词。 2 3 搜索日志中的s e s s io n 研究 搜索引擎为了准确对用户定义，得到用户更为详细的信息，常需要在搜索日 志中对用户的搜索行为进行划分。这种划分通常情况下用s e s s i o n 来表示【4 2 】。 河南大学硕士研究生学位论文第1 3 页 2 3 1 关于s e s s i o n 的定义 s e s s i o n 直接翻译成中文比较困难，常译成“会话 或“时域 。在计算机专业 术语中，s e s s i o n 是指一个终端用户与交互系统进行通信的时间间隔，通常指从注 册进入系统到注销退出系统之间所经过的时间。具体到w e b 中的s e s s i o n 指的就是 用户在浏览某个网站时，从进入网站到浏览器关闭所经过的这段时间，也就是用 户浏览这个网站所花费的时间。j a n s e n 等【8 】从上下文的角度把s e s f i o n 定义为用户 带着一个单一的搜索目的和搜索引擎一次完整的交互，它包括用户有关一个查询 的全部行为，用户提交查询以及之后翻页、在结果页面中点击的全部过程。 定义3s e s s i o n ：一个用户在一段时间里，带着一个固定的意图而进行的一系 列搜索行为的连续序列叫做一个s e s s i o n 。 一个s e s s i o n 是用户和搜索引擎一次完整的交互。为了表述的方便，在不至于 引起混淆的前提下，我们把这一系列搜索行为所对应的日志也叫做一个s e s s i o n 。 利用查询日志做研究工作的时候先做s e s s i o n 划分至少会有如下好处： 更有利于理解用户的查询意图、理解用户的搜索行为。用户的查询词通常 比较短，包含的信息比较少。且由于用户的背景差别很大，对同一个查询词，搜 索目的不尽相同，因此通过用户的单一查询词并不能准确的把握其搜索意图。而 一般情况下一个s e s s i o n 会包含多个查询词，通过对多个查询词的分析，更容易理 解用户的搜索目的。 更有利于做查询推荐、查询扩展的工作。例如，一个s e s s i o n 包含了用户输 入的查询序列，用户在搜索的过程中对查询做了多次修正，后面的查询是在前面 的基础上修改得到的。那么用户每一次修正后的查询更能代表他的搜索意图，后 面输入的查询可以作为前面查询的推荐。整个s e s s i o n 中的查询页也可以互相推荐。 利用这一特性可以来做查询推荐和查询扩展工作。 更有利于建立有效的用户模型1 4 0 ，对用户进行精准识别。就是对日志进行 分析之后，利用查询上下文来建立了用户模型。 第1 4 页河南大学硕士研究生学位论文 2 3 2 搜索日志中s e s s i o n 的划分方法 j a n s e n 等【8 ，3 4 1 对搜索引擎日志中s e s s i o n 做了大量的研究分析工作。该项目对 a o g p i l e c o m 的搜索日志进行分析，从三个方面对s e s s i o n 的划分进行了对比：a ) i p 地址，c o o k i e ：b ) i p 地址，c o o k i e 和时间限制；c ) p 地址，c o o k i e 和查询词重定 位。张磊等 4 6 1 专门研究了查询日志中的s e s s i o n 划分，并通过时间间隔法、t o p i cs h i f t 识