（计算机软件与理论专业论文）搜索引擎日志挖掘技术研究.pdf

中文摘要 中文摘要 搜索引擎的出现，成为互联网发展史上一个重要的里程碑，它能帮助人们从 浩瀚的网络中筛选所需信息，所以搜索引擎成为人们获取网络信息的首选工具。 但是搜索引擎的表现并不总是尽如人意，很多时候搜索引擎用户输入一个查询词， 搜索引擎返回成成千上万的查询结果，但是仅有部分信息是有用的并且很少用户 愿意浏览两页以上的搜索结果。此外，由于语言的多样性和用户对查询内容的理 解程度不同，不少用户输入的查询词并不能准确地表达其查询意图。 对搜索引擎日志的挖掘能够有效的解决这一系列问题。本文着眼于搜索引擎 日志的分析和应用，主要对搜索引擎用户行为分析、关键词生成和查询扩展等问 题进行研究，论文工作主要包括以下两个方面： 关键词生成：本文首先提出了基于搜索引擎日志的关键词生成算法p k g 算 法。该算作利用搜索引擎日志中的关键词和点击网址建立一个双向图，并且考虑 用户点击网址的顺序和网址的排名因素。然后在真实搜索引擎日志上实现了p k g 算法并做了大量的实验。实验结果表明，p k g 算法生成的关键词能够代表企业客 户的需求，在运行时间上也有明显优势。 查询扩展：本文提出了基于搜索引擎日志的查询扩展算法，并考虑了会话、 用户点击网址的顺序和网址的排名因素，而其它算法都没有考虑用户点击网址的 顺序和网址的排名因素，并做了大量实验，实验结果表明，既能满足用户的需求， 又在总体平均精度和查询平均精度上有所提高。 关键词：搜索引擎，数据挖掘，关键词生成，查询扩展 a b s t r a c t a b s t r a c t t h ee m e r g e n c eo fs e a r c he n g i n eh a sb e c o m ea l li m p o r t a n tm i l e s t o n ei nt h eh i s t o r y o ft h ed e v e l o p m e n to ft h ei n t e r n e t w h e np e o p l eu s es e a r c he n g i n e ，s e a r c he n g i n ec a l l h e l pp e o p l ef i l t e rt h ei n f o r m a t i o nw h i c ht 1 1 e yd on o tn e e d ，s om o r ea n dm o r ep e o p l ea r e w i l l i n gt oc h o o s es e a r c he n g i n ea st h ep r i m a r yt o o lf o rh u n t i n gr e s o u r c e sf r o mi n t e r n e t b u tt h ep e r f o r m a n c eo fs e a r c he n g i n ei sn o ta l w a y ss a t i s f a c t o r y w h e naq u e r y s u b m i t t e dt oas e a r c he n g i n e ，m o s tt i m et h es e a r c he n g i n ew i l lr e t u r nh u n d r e d sa n d t h o u s a n d so fr e l a t e dw e bp a g e s u n f o r t u n a t e l y , f e wp a g e sa r eu s e f u la n df e wu s e r sa r e w i l l i n gt ov i e wm o r et h a nt w op a g e so fs e a r c hr e s u l t s b e s i d e s ，a sf o rt h ea m b i g u i t yt h a t a r i s ei nm a n yt e r m so fal a n g u a g e ，t h eq u e r i e ss u b m i t t e dw h i c ha r ev e r ys h o r ta n ds h o r t q u e r i e sa r em o r el i k e l y t ob ea m b i g u o u s ，t h e r ea r eq u i t es o m ep e o p l ew h oc a nn o t f o r m u l a t ee f f e c t i v eq u e r i e st h a te x p r e s st h es e a r c hi n t e n tc l e a r l y s o m e t i m e s ，u s e r sm a y h a v el i t t l ek n o w l e d g ea b o u tt h ei n f o r m a t i o nt h e ya r es e a r c h i n g ，a n dw o r s t ，t h e yc o u l d n o te v e nb ec e r t a i na b o u tw h a tt os e a r c hf o r d a t em i n i n go ns e a r c he n g i n eq u e r yl o gm i g h tb ea ne f f e c t i v es o l u t i o nt ot h e s e p r o b l e m s t h i sp a p e rf o c u s e do nt h ea n a l y s i sa n da p p l i c a t i o no f s e a r c he n g i n eq u e r yl o g ， i n c l u d i n ga n a l y s i so fu s e rb e h a v i o r , k e y w o r dg e n e r a t i o na n dq u e r ye x p a n s i o n t h em a i n c o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w i n g ： k e y w o r dg e n e r a t i o n ：t h i sp a p e ra d d r e s s e st h ep r o b l e m b ym a k i n gu s eo ft h eq u e r y l o g so fs e a r c he n g i n e ，b u i l d i n gab i p a r t i t eg r a p hb e t w e e nq u e r i e sa n dt h ec l i c k e du r l s w ea l s ot a k ea c c o u n to fu s e r s c l i c k e do r d e ra n dr a n ko ft h eu r lw h i c ha r ei g n o r e db y t h ee x i s t i n ga l g o r i t h m s w ep e r f o r me x p e r i m e n t sw i t hr e a lq u e r yl o g s o u re x p e r i m e n t r e s u l t sp r o v et h a tk e y w o r d sg e n e r a t e db yp k ga r ea b l et os a t i s f yt h en e e d so fe n t e r p r i s e u s e r s ，c o m p a r e d 淅t l la r w , p k g i ss p e e d y q u e r ye x p a n s i o n ：t h i sp a p e rp r o p o s e saq u e r ye x p a n s i o na l g o r i t h mb a s e do nq u e r y i i i 黑龙江大学硕士学位论文 l o g so fs e a r c he n g i n e t h ea l g o r i t h mn o to n l yc o n s i d e r ss e s s i o n ，b u ta l s ot a k e sa c c o u n t o fu s e r s c l i c k e do r d e ra n dr a n ko ft h eu r lw h i c ha r ei g n o r e db yt h e e x i s t i n g a l g o r i t h m s w ep e r f o r me x p e r i m e n t sw i t hr e a lq u e r yl o g s t h er e s u l t ss t r a t i f yt h en e e d s o fu s e r s ，a n dt h e q u a l i t yo ft h eo v e r a l la v e r a g ep r e c i s i o na n dp e rq u e r ya v e r a g e p r e c i s i o nh a si m p r o v e d k e y w o r d s ：s e a r c he n g i n e ，d a t am i n i n g ，k e y w o r dg e n e r a t i o n ，q u e r ye x p a n s i o n i v 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人 已经发表或撰写过的研究成果，也不包含为获得墨垄江盔堂或其他教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所作的任何贡献均已 在论文中作了明确地说明并表示谢意。 学位论文作者签名： 签字日嘲年6 月( o 日 学位论文版权使用授权书 本学位论文作者完全了解墨蕴堑丕堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权墨蕉婆盔堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 薹耋兰差三一b 导师签名：幸勃p 夕 导师签名：霄彩， 签字嘎购岛钌月f d 日 l 电话： 邮编： 澳 轹阳 套茚 懿年 ， 作瞄、 文蔓谳嘲 第1 章绪论 第1 章绪论 1 1 课题研究的背景和意义 随着网络和互联网的飞速发展，搜索引擎已经成为人们获取网络信息的主要 途径。目前搜索引擎已经成为除e m a i l 外( 我国是除即时通讯外) ，人们使用最多的 网络服务系统。 在用户提交一个查询后，如果用户点击了返回结果页面的某个u r l ，一般表 示用户对u r l 的一个认可，并且在多数情况下不被认可的u r l 就不会被点击。 搜索引擎会在搜索引擎日志中记录用户输入的查询词和点击的u r l 。 搜索引擎日志记录了用户和搜索引擎交互的信息。通过搜索引擎日志挖掘， 可以发现用户的行为规律、用户如何使用w e b 搜索引擎、用户在w e b 上查找什 么样的信息、整体或单个用户的查询具有什么样的特征与规律等。并且通过搜索 引擎日志挖掘，可以收集统计信息，进而来改进网页的权重定义和返回结果的排 序，从而提高相关排序的性能。 目前搜索引擎主要以用户输入的查询关键词进行检索，然后把与用户输入关 键词相关的文档返回给用户，但返回的结果页面往往不能令用户满意。分析其原 因，可归结为两方面：( 1 ) 语言本身的原因( 某些词歧义，即一词多义) 。例如， “j a g u a r ，它既可以表示“汽车j a g u a r ，还可以表示“动物j a g u a r 。( 2 ) 用 户不知如何组织查询关键词来描述自己所想要查询的内容，最糟糕的情况是用户 自己都不知道自己所想要查询的内容。例如，用户输入查询“下载”，而没有指出 其想下载的具体内容。 为了解决上述问题，各搜索引擎都推出了查询推荐功能。查询推荐受到越来 越多用户的欢迎。查询推荐在帮助用户查找到所需信息的同时，也提高了搜索引 擎的点击率。 各搜索引擎的查询推荐功能都是基于查询扩展的，基本能将查询相关的查询 词推荐给用户，但很少能将语义相关的推荐给用户，所以有时无法满足用户的需 黑龙江大学硕十学位论文 求。 查询扩展是本课题研究的一个主要问题。通过对大量搜索引擎日志的研究， 从中挖掘出相关查询和语义相似的查询。 目前，搜索引擎广告是搜索引擎盈利的重要模式，而关键词生成是搜索引擎 广告的关键。关键词生成即生成满足特定企业客户需求的关键词集合。 关键词生成对搜索引擎服务商和企业客户都具有重要意义：对搜索引擎服务 商而言，为企业客户提供大量相关的关键词集合，能够吸引大量的中小型企业， 从而得到可观的收入；对企业客户而言，通过购买合适的关键词，能够提高企业 网站的访问率，从而得到巨大的品牌效应。 关键词生成时本文研究的另一个主要问题。通过搜索引擎日志挖掘，能够生 成满足企业用户需求的关键词集合。 综上，对搜索引擎日志挖掘技术的研究具有重要的实际意义。 1 2 国内外研究现状 目前搜索引擎日志挖掘主要可分为三个方面：( 1 ) 用户行为分析( 2 ) 查询扩展的 研究( 3 ) 关键词生成。 ( 1 ) 用户行为分析 用户行为分析是搜索引擎日志挖掘最先研究的方向。早在1 9 9 9 年，c r m g s i l v e r s t e i n 等就开始对搜索引擎日志进行研究，分析用户行为，通过分析发现传 统信息检索技术己不适应w e b 信息检索1 1 。但其没有从时间的角度对用户行为进 行分析【2 ，3 1 。s e t e v e nm b e i t z e l 等从时间的角度分析了用户的行为，通过分析发现 每天同一时刻用户的查询频率分布比较固定，并且在每天的查询高峰期，用户输 入的查询词最多，且查询集合比较稳定【4 1 。 j a i m et e e v a n 等发现用户在使用搜索引擎查询时，重复查询( r e p e a tq u e r i e s ) 是 普遍存在的，并且改变查询返回结果的排序会延长用户重复查询的点击时f n q t s , 6 1 。 m a r ks a n d e r s o n 等分析了重复查询时用户行为【7 1 。 中文网络数据环境与英文的有较大的差异，除了数据上的，还有用户群体的 2 第1 覃绪论 文化、语言习惯等差异，这些都造成了中文搜索引擎用户行为上的特异性，所以 有些研究者就对中文搜索引擎的用户行为进行独立的分析研究8 , 9 1 。 基于北大天网搜索引擎日志，王建勇等分析得出：用户查询的分布具有明显 的局部性，用户查询关键词非常集中，据此设计了系统的查询缓存，并比较了 f i f o ，l r u 及带衰减的l f u 三种c a c h e 替换策略f 1 0 1 。王继民等从用户查询类型 与数量，查询中包含中英文字符串的情况，用户到达时间，用户点击u r l 等方面 进行用户行为分析1 1 ，1 2 1 。余慧佳等基于搜狗日志对用户行为进行分析f 1 3 】，对查询 关键词和点击顺序等都进行了分析。 ( 2 ) 查询扩展的研究 目前，查询扩展的研究主要考虑如下三个方面因素：用户输入的查询关键词 1 4 - 1 9 ；用户点击对应查询的u r l f l 9 2 1 】；用户查询时间【2 2 】。 r i c a r d ob a e z a y a t e s 等提出了基于向量空间的查询词聚类的方法，该方法主 要考虑了用户输入的查询关键词和对应查询u r l 的页面内容，根据聚类的结果进 行查询推荐和w e b 页面重排序 1 , 2 3 , 2 4 。z h i y o n gz h a n g 等在r i c a r d ob a e z a y a t e s 的 基础上考虑了会话( s e s s i o n ) ，并考虑了会话内查询关键词之间的距离，从而进行 查询推荐【2 5 1 。 q i a n k u nz h a o 等提出了基于时间的语义相似性研究的方法。由于在同一时间 间隔内用户的查询具有一定的相似性，根据这种相似性进行语义相似性研究瞄】。 r i c a r d ob a e z a - y a t e s 提出了基于图的语义相似性研究的方法。用户在查询时， 由于文化背景等的原因，使用不同的查询关键词，但用户可能点击相同的u r l ， 这样这两个词之间就用一定的语义相似性【2 6 1 ，由此进行相似性研究。 x i a o d o n gs h i 等使用了基于关联规则的查询扩展，该方法考虑了会话和字之 间的匹配( 中文日志) ，然后使用关联规则的方法进行查询扩展【2 7 1 。 崔航等提出了一种基于用户查询日志的查询扩展统计模型 2 8 1 ；将用户查询中 使用的词或短语与文档中出现的相应词或短语以条件概率的形式连接，利用贝叶 斯公式挑选出文档中与该查询关联最紧密的查询词，以达到扩展优化的目的。 王继民等提出了一种利用搜索引擎日志发现相近w e b 查询的新方法。对一个 黑龙江大学硕士学位论文 l i 给定的查询，从日志中抽取候选查询的一些量化指标，如查询关键词被查询的次 数等建立一个发现有较好反馈结果的相近查询的回归模型 2 9 1 。 吴京慧等提出了一种基于用户查询日志的查询扩展模型，该模型根据用户查 询日志进行聚类，对一个新查询先计算其所属类别再进行扩展【3 0 1 。 迄今为止，进行查询扩展的研究时，都没有考虑用户点击的顺序和u r l 在返 回结果中的排名，但这两方面因素在日志挖掘中都具有重要意义，所以在进行查 询扩展时，需要考虑这两方面因素。 ( 3 ) 关键词生成 基于搜索引擎日志的关键词生成方法根据搜索引擎日志生成与企业客户相关 的关键词。搜索引擎日志记录了用户查询和点击的信息，每一条记录中都包含了 用户输入的关键词和点击的网址，这样可以认为该关键词是对应网址的一个简单 描述。 谷歌关键词工具1 3 l 】的关键词生成是挖掘用户查询日志而得到的。但在得到的 结果中，其中“与所输入字词相关的关键字”中仅得到包含输入词词干的关键词， 而没有与输入词相关而不包含输入词词干的关键词。雅虎关键词工具【3 2 1 和谷歌关 键词工具类似，仅包括含有所给查询词词干的关键词。 通过网页f 3 3 。6 1 或搜索引擎查询结梨3 刀也可以生产关键词，但这两种方法都有 相应的缺陷：由网页生成关键词的方法，工作量巨大，需要用网络蜘蛛爬下很多 网页；而由搜索引擎查询结果生成的关键词往往比较少。 a r i e lf u x m a 提出了基于日志的马尔科夫链关键词生成算法【3 8 】，根据搜索引擎 日志建立关键词和网址之间的双向图，从企业客户所给的网址出发，经过迭代， 生成所对应的关键词，此方法能生成相关的，不包含所给词词干的关键词。 此外对搜索引擎目志的挖掘还有对查询词聚类 3 9 , 4 0 和分类4 1 1 。 但目前，查询扩展和关键词生成都没有考虑搜索引擎日志中网址的排名和用 户点击的顺序。 综上，关键词生成和查询扩展都值得继续深入研究。 4 第1 章绪论 1 3 本文的研究内容与组织结构 1 3 1 本文研究内容 本文研究内容主要由如下三个方面： 1 用户行为分析 用户行为分析是查询扩展和关键词生成的基础，对用户行为进行分析能够为 查询扩展和关键词生成得到合理的实验基础。 2 关键词生成 目前，对关键词生成的研究比较少，但关键词生成是搜索引擎广告的基础， 并且目前基于搜索引擎日志的关键词生成算法，在时间效率上有很大问题。原因 有两方面，一方面生成的关键词数量比较多，另一个方面算法效率问题。 针对目前关键词生成存在的问题，本文提出关键词生成算法，并考虑用户点 击的顺序和u r l 在返回结果中的排名因素。 3 查询扩展 目前，对查询扩展的研究基本都没有考虑到用户点击的顺序和u r l 在返回结 果中的排名，而这两方面因素都包含重要意义：用户点击的顺序表示用户对该 u r l 的满意度；u r l 在返回结果中的排名表示搜索引擎认为该u r l 与用户查询 的相关度。 针对查询扩展存在的问题，本文在查询扩展研究过程中考虑用户点击的顺序、 u r l 在返回结果中的排名和会话。 1 3 2 本文组织结构 全文共分5 章，具体章节安排如下： 第1 章绪论，介绍论文的研究背景和意义，并概述了目前搜索引擎日志挖掘 的现状和不足，最后介绍了本文的研究内容与组织结构。 第2 章搜索引擎日志挖掘概述，首先介绍数据挖掘的基础知识，然后介绍搜 索引擎、搜索引擎日志的基础知识和本章小结。 黑龙江大学硕士学位论文 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i in i li i i i i i i i i i i i i i i i i i i i i i i i i i i 第3 章用户行为分析，首先介绍对搜索引擎日志的预处理，然后进行用户行 为分析，最后为本章小结。 第4 章关键词生成，首先介绍了关键词生成的基础知识，然后介绍了本无关 键词生成算法，最后为实验和本章小结。 第5 章查询扩展，首先介绍了查询扩展的基础知识，然后介绍本文查询扩展 算法，最后为实验和本章小结。 结论，给出本文研究结论、不足之处以及未来的工作方向。 6 第2 章搜索引擎日志挖掘概述 第2 章搜索引擎日志挖掘概述 搜索引擎日志挖掘是w e b 挖掘的一个主要分支，是数据挖掘技术在搜索引擎 日志上的应用。因此本章首先介绍数据挖掘的基础知识和搜索引擎的基本原理， 然后介绍搜索引擎日志的形成与结构。 2 1 数据挖掘的基础知识 数据挖掘的基础知识包括什么是数据挖掘、数据挖掘过程和数据挖掘应用和 发展趋势。 2 1 1 什么是数据挖掘 随着数据库技术、w e b 和计算机硬件的发展，数据日益膨胀，人们越来越认识 到自己“埋没”在庞大的数据中，出现了“数据丰富，而信息贫乏”的现象，不能从海 量的数据中获得自己所需的信息。如何及时、准确地从海量的数据中提取需要的 信息、并发现潜在的信息，就迫切需要一门学科来研究。因此数据挖掘就应运而 生。 数据挖掘( d a t am i n i n g ) ，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) ，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理 解的模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识 【4 2 】。数据挖掘融合了数据库技术、机器学习、统计学、信息科学和人工智能等， 是一个交叉学科。 2 1 2 数据挖掘过程 数据挖掘过程主要包括：问题定义、数据准备、数据挖掘、结果分析和知识 应用。 1 、问题定义 数据挖掘是从海量数据中挖掘出用户感兴趣的信息，所以从海量数据中发现 何种信息是数据挖掘整个过程关键的一步。只有问题定义明确，数据挖掘其他步 7 黑龙江大学硕士学位论文 骤才有意义，所以问题定义是关键。 2 、数据准备 数据准备又可分为四个子步骤：数据清理、数据集成、数据选择和数据变换。 在现实世界中，数据一般都说有噪声的、不完整的和不一致的。数据清理就 是解决这些问题，清除噪声并识别离群点，填充缺失值和纠正数据中的不一致。 在实际应用中，数据存储方式是多种多样的，数据可能存储为不同的格式， 数据存储在不同的计算机上。数据挖掘时，需要将不同格式的，不同数据源的数 据集中起来，合并在一起，存放在一个一致的数据存储中。 数据选择是从集成的数据中提取与挖掘相关的数据。 数据变换是指将选择后的数据转换或统一成适合挖掘的形式。数据变换有以 下集中形式：光滑、聚集、数据泛化、规范化和特征构造。 3 、数据挖掘 在问题定义中，明确了挖掘的任务和目的，但明确数据挖掘任务中所需的模 型类型是由数据挖掘来完成。数据挖掘中模型类型可分为：概念类描述、关联分 析、分类和预测、聚类分析、孤立点分析和演变分析。数据挖掘阶段，首先需要 明白所需的模型类型，然后选择适当的算法进行数据挖掘。 4 、结果分析和知识应用 在数据挖掘阶段后，需要对结果进行评估和分析，查看产生的结果是否达到 需求，是否存在冗余或无关的模式。如果结果不理想，需要对出现问题进行分析， 然后回退到前序阶段，重新选取数据，采用新的转换方法，设定新的参数值，甚 至修改原有算法。在不断分析和尝试中，得到理想的结果。然后将结果应用到实 际中，或给管理者提供决策，或改变营销策略等。 2 1 3 数据挖掘应用和发展趋势 从上世纪8 0 年代起，数据挖掘在理论和应用上都得到不断进步。今天，数据 挖掘应用更为广泛，应用到众多领域：金融业、零售业、电信业和生物学等。 数据、数据挖掘任务等对数据挖掘提出了许多新的挑战。数据挖掘发展趋势 8 第2 章搜索引孥日志挖掘概述 为：( 1 ) 应用探索( 2 ) 可伸缩的和交互的数据挖掘方法( 3 ) 数据库系统、数据仓库系统 和w e b 数据库系统的数据挖掘集成( 4 ) 数据挖掘语言的标准化( 5 ) 可视数据挖掘( 6 ) 挖掘复杂数据类型的新方法( 7 ) 生物数据挖掘( 8 ) 数据挖掘与软件工程( 9 ) w e b 挖掘 ( 1 0 ) 分布式数据挖掘( 11 ) 实时数据挖掘( 1 2 ) 图挖掘、链接分析和社会网络分析( 1 3 ) 多关系和多数据库数据挖掘( 1 4 ) 数据挖掘中隐私保护和信息安全等【4 3 1 。 2 2 搜索引擎的基本原理 在日常工作和学习中，搜索引擎是不可或缺的工具，所以了解搜索引擎基本 原理是十分必要的，能对日常搜索应用和网站提交推广起到重要作用。搜索引擎 基本原理包括：搜索引擎架构、搜索引擎分类和搜索引擎发展趋势。 2 2 1 搜索引擎架构 虽然搜索引擎有不同的架构，但搜索引擎总体由三部分组成：信息搜集系统、 建立索引数据库和查询接口。 信息搜集系统主要用来搜集信息，不同的搜索引擎采用不同的方法：( 1 ) 目录 导航搜索引擎采用人工的方法，采用手工的方法发现新的网站，给每一网站一个 标记和描述，然后将其放入到对应的类目体系中；( 2 ) 全文搜索引擎是通过机器人 或网络蜘蛛自动完成的。网络蜘蛛是通过网页中的链接地址来寻找下一个网页的 入口，一般情况，从网站的主页面开始，读取页面的内容，并找出页面内的链接 地址，然后通过链接地址寻找下一页面，这样一直循环下去，直到找到网站内所 有页面为止。如果把互联网比做一个网站，那么根据这个原理，网络蜘蛛可以把 互联网所有网页都爬抓下来。 建立索引数据库主要用来将信息搜索系统搜集的信息整理，并按照一定的规 则进行编排。建立索引数据库目的是在用户查询时，搜索引擎能快速提供与用户 查询相关的信息，如果将所有信息杂乱无章地存放在一起，查询时需要将所有信 息都要扫描一次，这样再快的计算机系统也无法满足用户的需求。 搜索引擎主要是用来满足用户查询需求，所以搜索引擎一般提供了关键词查 询这样的查询接口，方便用户查询。另外，搜索引擎还可能可供了高级查询接口 9 黑龙江大学硕士学位论文 i i1 功能，比如组合查询，模糊查询等。搜索引擎的查询接口还提供搜索结果相关性 排序等关键技术的实现。 2 2 2 搜索引擎分类 搜索引擎按照工作方式不同，可分为三种：目录导航搜索引擎、全文搜索引 擎和元搜索引擎。 目录导航搜索引擎的典型代表是雅虎y a h o o t u 。从严格意义上将目录导航搜 索引擎并不是真正的搜索引擎，它仅仅是将网站按照不同目录分类而已。在查询 时，用户可以按照目录查询所需信息，按照搜索引擎的目录一层层深入，就能找 到自己所需的信息，而不一定要按照关键词查询。其优点是从目录搜索得到的结 果往往更具参考价值，信息准确，导航质量高；其缺点是需要人工介入、维护量 大、信息量少、更新不及时等。 目录导航搜索引擎可以称为第一代搜索引擎，为了解决第一代搜索引擎存在 的问题，第二代搜索引擎产生了，即全文搜索引擎。全文搜索引擎使用网络蜘蛛 按照某种策略自动地在互联网搜集和发现信息，然后使用索引器为搜集的信息建 立搜索，再由检索器根据用户的输入查询词查询索引库，并将查询结果返回给用 户。全文搜索引擎的优点是信息量大、更新及时、无需人工干预，其缺点是返回 信息过多，用户需要从中筛选。全文搜索引擎的典型代表有g o o g l e t 4 5 、a l t a v i s t a 4 6 等，国内的典型代表有百度【4 7 】、天网【4 8 1 等。 元搜索引擎没有自己的网页索引数据库，而是提供一个用户查询接口，根据 用户的查询请求，同时调用多个搜索引擎进行查询，并将所有查询结果进行汇总、 去重、筛选、组合、排序等优化处理，然后将处理后的结果以统一的格式在同一 界面提供给用户。严格意义上来讲，元搜索引擎只能算是一种用户代理，而不是 真正的搜索引擎。这类搜索引擎的代表是w e b c r a w l e r ，但在实际中应用的效果并 不理想。 2 3 搜索引擎日志的特点 搜索引擎日志记录了用户使用搜索引擎查询时点击结果的信息，为了更好的 l o 第2 章搜索引擎日志挖掘概述 理解搜索引擎日志，下面介绍搜索引擎日志的形成和结构。 2 3 1 搜索引擎日志的形成 搜索引擎是w e b 体系机构，而w 曲体系结构基本都是基于浏览器( b r o w s e 0 服务器( s e r v e r ) 模式，其工作方式采用典型的请求响应方式，主要流程如下 4 9 1 ： ( 1 ) 搜索引擎用户向搜索引擎服务器或者通过代理发出查询请求，根据h 1 m 协议，请求中包含了用户的查询词、用户的i p 地址和查询时间等一系列信息。 ( 2 ) 搜索引擎服务器收到查询请求后，根据查询请求将用户要求的信息内容结 果直接或者通过代理返回到用户。 ( 3 ) 用户从搜索引擎返回的结果中筛选自己要需要信息，并点击对应的网址， 搜索引擎服务器同时将访问信息和用户信息等记录到日志文件中。用户每点击一 个网址记录一次。 在此基础上，在搜索引擎服务器端形成了搜索引擎日志，记录了用户和搜索引 擎交互的信息。 2 3 2 搜索引擎日志结构分析 出于商业目的和保护用户隐私的目的 3 6 , 5 0 ，开放搜索引擎日志的搜索引擎很 少。目前，可以得到的搜索引擎日志有搜狗日志刚和a o l 日志【5 2 1 。 表2 1 搜狗搜索引擎日志内容 t a b l e2 1t h ec o n t e n to fs o g o us e a r c he n g i n eq u e r yl o g 名称记录内容 t i m e i d q u e r y r a n k o r d e r u r l 用户点击网址的时间 系统自动分配的用户标示号 用户提交的查询词 用户点击网址在返回结果的排名 用户点击网址的顺序号 用户点击的网址 搜狗搜索引擎日志内容见表2 1 。 黑龙江大学硕士学位论文 搜狗日志片段如表2 2 ： 表2 - 2 搜狗日志片段 t a b l e2 - 2al i t t l ef r a g m e n tf r o ms o g o us e a r c he n g i n eq u e r yl o g 记录 日志 10 0 ：1 2 ：4 2 2 0 3 9 8 8 2 5 1 7 9 7 0 1 5 8 【a z m 网址大全】21w w w a z m 8 o r e , 20 0 ：12 ：4 515 0 0 17 8 2 3 7 2 9 8 7 9 1 【电影】73w w w b n b 8 8 c o r n 第一条日志记录表示：用户2 0 3 9 8 8 2 5 1 7 9 7 0 1 5 8 查询“a z i n 网址大全”，在 0 0 ：1 2 ：4 2 时刻点击了网址w w w a z m 8 o r g ，该网址在返回结果的排名是2 ，用户在 所有点击结果中第一个点击了该网址。 a o l 日志内容如表2 3 ： 表2 3 a o l 搜索引擎日志内容 t a b l e2 - 3t h ec o n t e n to f a o ls e a r c he n g i n eq u e r yl o g 名称记录内容 a n o n i d q u e r y q u e r y t i m e i t e m r a n k c l i c k l 瓜i ， 用户匿名标识号 用户提交的查询词 用户查询时间 用户点击网址在返回结果的排名 用户点击的网址 a o l 日志片段如表2 4 。 第一条日志记录表示用户1 0 2 0 在2 0 0 6 0 4 1 81 2 ：1 8 ：1 8 时刻查询了 w w w s a c s a n d s t o m ”，但用户没有点击返回结果，第二、三条日志记录表示用户 1 0 2 0 在2 0 0 6 0 4 1 81 2 ：4 3 ：4 6 查询了“s l o tm a c h i n et i p s ”并点击了网址 h t t p ：w w w s l o t a d v i s o r c o m ”，该网址在返回结果的排名是第一名，和网址 h u p ：w w w 1 i c e n s e d 4 f u n c o r n ”，该网址在返回结果的排名是第十一名。 第2 章搜索引擎日志挖掘概述 表2 4 a o l 日志片段 t a b l e2 - 4al i t t l ef r a g m e n tf r o ma o ls e a r c he n g i n eq u e r yl o g 记录日志 l1 0 2 0w w w s a c s a n d s t o m2 0 0 6 - 0 4 1 81 2 ：1 8 ：1 8 210 2 0s l o tm a c h i n et i p s2 0 0 6 0 4 1812 ：4 3 ：4 61h t t p ：w w w s l o t a d v i s o r e o m 310 2 0s l o tm a c h i n et i p s2 0 0 6 - 0 4 1812 ：4 3 ：4 61 1h t t p ：w w w 1 i c e n s e d 4 f u n c o m 从上面可以看出各搜索引擎日志格式各不相同：其组织和内容形式各异，但 都包含基本信息：用户标示、用户查询词，用户点击网址、用户点击网址时间等。 2 4 本章小结 本章介绍了搜索引擎日志挖掘的基础知识：数据挖掘的基础知识和搜索引擎 的基本原理，然后介绍了搜索引擎日志的形成和搜索引擎日志的结构。 搜索引擎日志挖掘基础知识是以后章节的基础，以后章节将对搜索引擎日志 挖掘进行深入的介绍。 1 3 第3 章用户行为分析 第3 章用户行为分析 随着互联网信息的不断增长，搜索引擎成为互联网用户必不可少的工具。搜 索引擎用户使用搜索引擎时，首先由用户输入查询关键词，然后搜索引擎按照用 户输入的关键词与预存的网页数据库按照特定的规则进行匹配，按照一定的算法 输出网页的集合。但是这种简单的匹配有时不能满足搜索引擎用户的需求。 通过对互联网用户使用搜索引擎的行为进行分析，一方面可以提高搜索质量， 满足用户的需求，另一方可以改善和提高搜索引擎的性能，提高搜索引擎的知名 度和扩大其市场份额。 3 1 搜索引擎日志预处理 本文采用搜狗搜索引擎2 0 0 7 年3 月份共3 1 天的日志，该日志的存储为文本 文件，为了方便对数据进行处理和对用户行为进行分析，本文首先将文本日志导 入到o r a c l e 数据库中，在导入过程中，做了如下的处理：去除查询关键词为空 的点击记录、去除无点击的查询关键词的记录、去除长度超过1 5 0 的查询关键词 的点击记录和去除长度超过2 0 0 的u r l 网址的点击记录。 3 2 用户行为分析 预处理后，该日志共4 4 4 1 0 9 0 0 条点击记录、共1 4 9 7 6 3 7 5 条不同的u r l 网址、 共8 1 6 6 1 6 9 个不同的用户和4 5 7 9 8 0 5 个不同的查询关键词，如表3 1 ： 表3 - 1 搜狗搜索引擎日志统计结果 t a b l e3 - 1t h es t a t i s t i c so fs o g o us e a r c he n g i n eq u e r yl o g 名称数目 点击记录4 4 4 1 0 9 0 0 不同的也网址 14 9 7 6 3 7 5 不同的用户 8 1 6 6 1 6 9 不同的查询 4 5 7 9 8 0 5 黑龙江大学硕七学位论文 从表3 - 1 中可知，平均每个u r l 网址被点击3 次、平均每个用户点击6 条记 录、平均每个查询关键词点击1 0 条记录、平均每个用户点击2 条不同的u r l 网 址、平均每个查询关键词点击3 条不同u r l 网址和平均每个用户有两个不同的查 询关键词。 3 2 1 查询关键词分析 查询关键词反映了搜索引擎用户使用搜索引擎的方式和语言组织情况，通过 对查询关键词分析，能很好理解用户行为，从而有助于改善和提高搜索引擎质量。 3 2 1 1 查询关键词长度 查询关键词长度指搜索引擎用户使用搜索引擎查询输入的查询关键词的长 度。中文是指汉字的个数，英文是指单词的个数。统计结果如图3 1 ： 。 j 。t ? 嘤j7 _ 。 “? j ? ；j ：鼍譬? ”弩嘲鼢霹璁 ， ，w 。 甍 。l i秀 i 一j b t 诩戋t 诩长度 图3 - 1 查询词长度及所占比例 f i g u r e3 - 1t h ep e r c e n ta m o n gt h ed i f f e r e n tl e n g t h so fq u e r y 从图3 1 可知：其中查询关键词长度最多为4 ，占总查询关键词的1 6 7 ；长 度在2 到1 4 之间的查询关键词，占总查询关键词的9 4 7 ；长度在4 到8 之间的 查询关键词，占总查询关键词的6 6 5 ；平均查询长度为7 。这说明中文在语言 组织和意思表达上2 到1 4 个字基本能表达清楚其含义，表达含义时4 到8 个字用 得最多，搜索引擎在中文语言处理上需要特别注意处理长度为2 到1 4 的查询关键 词。在实验数据分析过程中，发现部分查询关键词长度超过10 0 ，例如：查询词 1 6 第3 章用户行为分析 “ e m b e d + s r c = ”h t t p ：w w w t u d o u c o m v h i 6 w t 0 8 g - t c ”，还有其他形式的查询词，不过可以发现，关键词长度过长的查询词，不是 网址，就是搜索引擎用户粘贴的一部分内容，这可能是用户需要查询的内容，也 可能是用户不知如何使用搜索引擎。 3 2 1 2 查询关键词词数 查询关键词词数是指查询关键词有几个词组成。中文是指词语的个数，英文 是指单词的个数。中文的词语和英文的单词都以空格或“+ 分割。图3 2 为查询 关键词词数与所占比例的示意图。 移5 m 珊铹秒叼曩，弩i ”掣。“? 嘞弘i 祥：“? 一飞翟 ，。 ，1 ； ! 。i ； 、 f 一 、 ；i ；、3 ；i 毽。，i ：t 。jj ? ，、2 ；。二。j j ：? j 一- j j i 。ji 。t 瀛 置诲黄词词t 图3 - 2 查询关键词词数与所占比例的示意图 f i g u r e3 - 2t h ep e r c e n to f t h en u m b e ro f d i f f e r e n tq u e r i e s 从图3 2 中可知查询关键词词数最多为1 ，占总查询词的9 6 9 左右。经过分 析可知，平均查询关键词词数为1 0 5 ，该结果与文献【5 3 1 中的英文查询关键词词数 的2 3 5 相差较大，但与文献【5 4 】中的中文查询关键词词数的1 1 4 接近，这说明中 文与英文在词语组织和意思表达上有较大的差别，中文仅需一个词就能表达一定 的含义，而英文需要两个甚至更多。在分析过程中，发现出现查询关键词词数很 多的格式是这样的“a + t a l e + o f + s u r v i v a l + l o s t + f r e e ”，可知出现查询关键词词数多的 查询基本是英文查询。这与中英文差异有关，因为在英文中以空格来分割单词， 1 7 黑龙江大学硕士学位论文 而中文以词语而非空格来分割。 3 2 1 3 查询关键词的语种 查询关键词语种是指搜索引擎用户使用何种语言组织查询关键词，在处理过 程中忽略了少量非法字符，得到查询关键词语种有中文，英文，中英文混合，分 析各语种查询关键词数量得到图3 3 。 图3 3 查询关键词的语种数量不慈图 f i g u r e3 - 3t h en u m b e ro f d i f f e r e n tl a n g u a g e so f q u e r i e s 查询关键词中即有中文、英文甚至中英文混合，但从图3 3 中可知英文组织 查询关键词仅是- d , 部分，仅有1 0 左右，中英