（计算机应用技术专业论文）基于搜索日志的用户行为研究及应用.pdf

北京邮电大学博卜学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 申请学位论 本人签名： 处，本人承担一切相关责任。 日期：丝：盖：2 ：三垒 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在 校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关 部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后遵守此规定) 非保密论文 本人签名： 导师签名： 于保密范围，适用本授权书。 日期：笙垄：z ：! 查 一 日期：塑量：三：堑 北京邮电大学博_ 上学位论文 捅要 搜索引擎的出现，成为互联网发展史上又一个重要的里程碑。越来越多的互联网用 户开始选择搜索引擎作为其获得网络资源的首选工具。但是搜索引擎的表现并不总是尽 如人意，很多时候当用户输入一个查询，搜索引擎返回成千上万个搜索结果，然而很少 有用户愿意浏览三页以上的搜索结果。此外，由于用户的水平存在较大差异，不少用户 构造的查询并不能完全表达其搜索意图。对搜索日志的挖掘能够有效的解决这一系列问 题。本文着眼于搜索日志的分析和应用，主要对用户搜索行为模型、搜索行为分类、网 页排序算法的优化、异常搜索行为的检测等问题进行研究，论文工作主要包括以下几个 方面： ( 1 ) 对搜索日志进行基本分析，包括搜索日志各个属性及其相互之间的关系，发现了 大规模中文搜索引擎用户的一些基本搜索特征。首次引入了中文分词算法，使关于查询 词的分析结果更接近中文搜索引擎实际情况。首次分析了网页u r l 深度和被点击次数的 关系，并根据对不同时期搜索日志的分析，发现了中文搜索引擎用户的搜索行为变化趋 势。 ( 2 ) 分别从抽象和具体的角度对用户的搜索行为进行了分类。首次从搜索日志中提取 用户搜索行为模型，并从抽象的角度概括用户搜索行为的各种表现形式。通过网页分类 的相似性及网页向量的相似性对模型进行了校正。为基于搜索行为的相关研究提供了基 础。引入了历史查询分析，并计算了历史查询的影响因子。 ( 3 ) 提出了一种基于预定义类别的搜索分类算法，将基于朴素贝叶斯理论的网页分类 技术和用户搜索日志相结合，使搜索分类能够体现用户的搜索意图，并且克服了因查询 词过短以及词语多义性导致的分类误差将实时搜索历史应用于搜索分类，提高了分类 的准确率。 ( 4 ) 提出了一种网页排序优化算法。该算法在原有网页排序结果的基础上，结合用户 搜索日志，采用混合频繁模式树算法，能够有效发现搜索事务的关联规则，并对查询词 进行扩展。选择对原排序结果的前n 个网页进行优化排序，既保证了搜索结果的相关性和 覆盖率，同时使排序结果更能够体现用户的搜索需求。此外，将用户搜索行为模型应用 于网页排序优化算法，通过计算历史查询词的影响因子，使排序结果能够实时体现用户 搜索意图。 ( 5 ) 分析了异常搜索行为潜在的安全威胁，并根据不同异常搜索行为的特征对其进行 了分类，包括基于内容的异常搜索及基于流量的异常搜索。提出了一个异常搜索行为检 测框架，并采用优化的决策树算法对不同异常搜索行为进行检测。 关键词：搜索引擎、数据挖掘、搜索同志、搜索分类、网页排序、搜索行为模型、异常 搜索行为检测 北京邮电大学博士学位论文 a b s t r a c t t h ew o r l dw i d ea p p l i c a t i o no fs e a r c he n g i n ec a l lb eam i l e s t o n eo ft h ee v o l u t i o no f i n t e r n e t m o r ea n dm o r ep e o p l ea r ew i l l i n gt oc h o o s es e a r c he n g i n e 嬲t h ep r i m a r yt o o lf o r h u n t i n gr e s o u r c e sf r o mi n t e m 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 s n o t a l w a y s s a t i s f a c t o r y m o s tt i m es e a r c he n g i n ew i l lr e t u r nt h o u s a n d so fr e l a t e dw e bp a g e sw h e nw ei n p u t aq u e r y u n f o r t u n a t e l y , f e wp a g e sa r eu s 舒- u la n df e wp e o p l ew o u l dl i k et ov i e wt h er e s u l t so v e r 3r e s u l tp a g e s b e s i d e s ，勰f o rt h ed i f f e r e n c eo fk n o w l e d g eb a c k g r o u n d ，t h e r ea r eq u i t es o m e p e o p l ew h o c a l ln o tc r e a t et h eh i g hq u a l i t yq 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 d a t a m i m n go nq u e r yl o gm i g h tb eh e l p f u lt os o l v et h e s ep r o b l e m s t h i sp a p e rf o c u s e do nt h e a n a l y s i sa n da p p l i c a t i o no fq u e r yl o g , i n c l u d i n gt h es e a r c hb e h a v i o rm o d e l ，q u e r yc l a s s i f i c a t i o n , s e a r c hr e s u l tr a n k i n go p t i m i z a t i o n , a n da n o m a l ys e a r c hd e t e c t i o n t h em a i nc o n t r i b u t i o n so f t h i sp a p e ra r e 舔f o l l o w i n g ： ( 1 ) f r o mt h eb a s ea n a l y s i so fq u e r yl o g , i n c l u d i n gt h ea t t r i b u t e so fas e a r c ha n dt h e r e l a t i o n sa m o n gt h e m ，t h es e a r c h i n gc h a r a c t e r i s t i c so ft h eb s e r sf r o mal a r g es c a l ec h i n e s e s e a r c he n g i n ew e r ed e s c r i b e d t h ec h i n e s ew o r d ss e g m e n t a t i o na l g o r i t h mw a si n t r o d u c e dt o t h eq u e r yl o gm i n i n gm a k i n gt h ea n a l y s i sr e s u l tm o r ee x a c t l y t h er e l a t i o nb e t w e e nt h ed e p t h o faw e bp a g eu r la n dt h ev i s i t e df r e q u e n c yw a sd i s c o v e r e d ，a sw e l l 私t h es e a r c hv a r i a t i o n v e n d sb yc o m p a r i n gt h eq u e r yl o g sr e c o r d e di nd i f f e r e n tp e r i o d s ( 2 ) t h es e a r c hb e h a v i o rw a sc l a s s i f i e df r o ma b s t r a c ta n ds p e c i f i cp e r s p e c t i v e as e a r c h b e h a v i o rm o d e lw a sp r e s e n t e d , w h i c hw a sc r u c i a lf o r t h es e a r c hb e h a v i o rr e l a t e dr e s e a r c h t h e s e a r c hh i s t o r yw a sa l s ot a k e ni n t oa c c o u n t , a n dt h ei m p a c tf a c t o ro fe a c hq u e r yw o r d sw a s c a l c u l a t e d ( 3 ) aq u e r yc l a s s i f i c a t i o na l g o r i t h mw a sd e s c r i b e dw h i c hc a nc l a s s i f yt h eq u e r i e si n t o s o m ep r e d e f i n e dt a x o n o m i e s t h ea l g o r i t h mw a gb a s e do nn a i v eb a y e s i a nn e t w o r k ，m a k i n g t h ec l a s s i f i c a t i o nr e f l e c t i n gt h eu s e 培s e a r c hi n t e n t t h em i s c l a s s i f i c a t i o nc a u s e db yt h ef e w w o r dn u m b e ro fa l li n p u tq u e r ya n dt h em u l t i m e a n i n g so faw o r d 啪b er e d u c e d n 地 c l a s s i f i c a t i o na c c u r a c yc a nb ei m p r o v e db yu s i n gt h eq u e r yh i s t o r y ( 4 ) a no p t i m i z a t i o no ft h er e s u l tp a g er a n k i n ga l g o r i t h mw a sp r e s e n t e d t h ea l g o r i t h m u t i l i z e dah y b r i df r e q u e n tp a t t e r nt r e et or e s t o r et h eq u e r i e s ，a n do p t i m i z e dt h es o r t i n go ff i r s t 刀 o r i g i n a ls e a r c hr e s u l t s t h i sc a ne n s u r et h er e l a t i v i t ya n dt h ec o v e r a g eo ft h es e a r c hr e s u l t ，嬲 w e l l 嬲r e f l e c t i n gt h es e a r c hi n t e n to f t h es e a r c he n g i n eu s e r s ( 5 ) t h ea n o m a l ys e a r c hb e h a v i o rw h i c h 锄b ea u x i l i a r yf o rm a l i c i o u si n t e n d i n gw a sd e s c r i b e d a n a n o m a l ys e a r c ht y p ed e f i n i t i o nw a sd e s c r i b e di n c l u d i n gt h ec o n t e n tb a s e da n o m a l ys e a r c ha n dt h et r a f f i c b a s e da n o m a l ys e a r c h a na n o m a l ys e a r c hd e t e c t i o nf r a m e w o r kw a sp r o p o s e da n da no p t i m i z e dd e c i s i o nt r e e a l g o r i t h mw a su t i l i z e dt od e t e c tt h ea n o m a l ys e a r c hb e h a v i o r 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 , q u e r yl o gq u e r yc l a s s i f i c a t i o n ，p a g es o r t i n g , s e a r c hb e h a v i o rm o d e l ，a n o m a l ys e a r c hd e t e c t i o n 4 北京邮电大学博上学位论文 第一章绪论 1 1 研究工作的背景和意义 在过去的几年中，随着互联网的高速发展，搜索引擎的作用与同俱增，越来 越多的互联网用户开始选择搜索引擎作为其获得网络资源的首选工具。但是，搜 索引擎的表现并不总是尽如人意。很多时候，当用户输入一个查询词，搜索引擎 会返回成千上万个搜索结果，而其中只有很少一部分甚至没有网页是符合用户需 求的。如何理解用户的搜索意图，找出符合用户需求的网页，并将最相关的网页 置于搜索结果的前列，这成为众多学者研究的重要课题。 总体而言，针对上述问题的研究已经取得了一些进展。例如通过基于自然语 言的处理技术来理解用户的搜索意图，通过建立垂直搜索引擎确保所有的搜索结 果都是和查询相关的，以及通过对原有网页排序算法的改进将最符合用户需求的 网页置于前几页，等等。但是，这些研究并不能从根本上解决问题。至少，今天 的搜索引擎和几年前相比并没有太大的差异，最令人印象深刻的只是其收录的网 页数量确实明显增多，但这并不完全归功于搜索引擎。 对搜索日志的研究，为提高搜索引擎质量提供了一个新的思路。由于搜索日 志详细记录了每个用户的搜索行为，因此对搜索日志的挖掘能够最直接的发现用 户搜索规律和搜索意图。关于搜索日志的研究，主要可以从以下几个方面展开： 1 ) 基于搜索日志的基本研究：搜索日志记录的信息包括用户i d 、搜索时间、 提交的查询、用户点击的u r l 、该u 眦搜索结果的中排名、用户点击 的顺序号。通过对这些信息的统计分析，以及发掘这些信息间的相互关 系，可以发现一些最基本的搜索行为特征。这些特征为研究用户的行为 模型、评价搜索引擎的性能、改进搜索引擎的算法等提供了最直接的支 持。 2 ) 用户行为模型：如果希望提高搜索引擎质量以满足用户的搜索需求，则 首先需要理解用户的搜索需求。搜索日志所记录的用户搜索历史是用户 需求的直接体现。所谓万事皆因果，用户发起搜索、点击某个u r l 、修 改查询、终止查询，都是有原因的，即搜索行为背后所隐含的用户需求。 分析用户行为特征，并为之建立模型，可以将各种表面现象进行归纳描 述，揭示用户的搜索意图。此外，用户行为模型可以为搜索引擎的其他 相关算法研究提供参考。 3 ) 搜索分类或聚类算法研究：由于互联网页规模过于庞大并且网页更新速 度很快，采用基于内容发现相似网页的算法代价太高。但是，通过搜索 同志可以快速发现查询相关的相似网页。此外，通过分类或聚类算法对 搜索日志进行数据挖掘，还可以有效发现那些语义无关但是搜索相关的 查询词，这些查询词表达了相同的搜索意图。对搜索进行分类或聚类， 熬寒酸嗽大学簿士学绽论文 发现相关或相似的查询词，用于扩展用户查询，可以改善当前因用户输 入的查询过短、以及词语多义性导致搜索准确度不高的现状。荠且，对 搜索进行分类，可以更准确的掌握用户搜索兴趣点，为搜索结果排序算 法的改进提供参考。 4 ) 搜索结果蓑 序算法的改进：鬓前主流的搜索萼l 擎爨页摊序算法都是基于 网页内容的，或者可以认为是基于网页中包含的超链接关系。在某种程 度上，这些算法反映了网页作者们的意图，而不是用户的搜索意图。这 些算法的缺点造成了嚣前搜索弓l 擎普遍存在的问题，譬如缀多人为了提 高网页排名而刻意调整网页内容结构，使网页链接的入度或出度很高， 但网页本身质量却很低；搜索结果中存在大量的镜像甚至完全相同的网 页，并且占据了搜索结果前三页位置，恧大多数用户只愿意浏览前三燹 结果。结合搜索因志改进网页排序算法，可以使搜索结果真正反映用户 搜索意图。只有被用户经常访问的网页才是高质量的网页，解决了因人 为刻意构造的网页影响搜索结果排穿的问题。 5 ) 异常搜索行为检测：这方面的研究将成为未来搜索引擎研究领域的一个 新的热点。由于搜索引擎的应用网益广泛，许多问题也随之产生，其中 包括搜索行为带来的潜在威胁。虽然搜索弓 擎本身荠不对互联网构成威 胁，却无意中成为了助纣为虐的工具。通过搜索引擎可以迅速发现互联 网中可能具有安全漏洞的服务器，帮助黑客们找到攻击目标，缩短了入 侵行为的奏效周期。嚣此，在这类问题还没有爆发时采取有效解决办法 做到防患于未然是非常有必要的。由予大部分带有潜在安全威胁的搜索 行为具有明照的特征，因此可以通过对搜索日志进行挖掘，建立这些异 常搜索行为的模式，能够有效检测异常搜索行为。 需要说明的是，搜索闷志挖掘与普通文本数据挖掘并不相同，因为搜索同志 是具有一定结构性的文本数据，每一条记录的各个属性都有明确定义。对搜索r 志的挖掘必须源于搜索弓l 擎，服务予搜索譬l 擎，具有明确的露的性和现实性。当 然，一些基本的数据挖掘算法是通用的，例如分类、聚类、关联规则等等，只是 在将这些算法具体应用于搜索网志挖掘的时候，可能需要根据搜索同志的特点做 相应的改进。 1 2 主要研究工作 本文作者在博士研究生期闻，作为主要研发人员和组织人员参加了多个数据 挖掘和搜索引擎的项毽，包括有： 1 ) “电信网络安全防御研究 ( 国家2 4 2 信息安全计划，项目编号： 2 0 0 5 a 1 3 ) ： 2 “下一代黄页搜索弓| 擎挣( 企业合作项目，合作方：中国露通有限公司 山西省分公词) ： 北京邮电大学博士学位论文 3 ) “七号信令网数据挖掘 ( 企业合作项目，合作方：中创信测科技股份 有限公司) ： 本论文是在这些项目的支持下完成的。概括起来，作者在攻读博士学位期间 的研究工作主要包括以下几个方面： 1 ) 对搜索引擎进行全面深入的学习和研究，包括搜索引擎的工作原理和体 系结构，网页信息的搜集与存储，收集信息的预处理，信息的查询与结果呈现， 网页的索引技术，搜索结果的排序算法，中文网页分类技术，等等。 2 ) 作为“下一代黄页搜索引擎 项目负责人，采用著名搜索引擎开源计划 ( l u c e n e ) ，为某运营商开发结合电信增值业务的搜索引擎系统。通过对用户需 求进行分析，设计了搜索引擎系统的框架，提出了将搜索引擎与电信业务捆绑的 应用模式，使互联网应用服务和电信应用服务完美结合。 3 ) 对搜索引擎系统记录的用户搜索日志进行了研究，发现了用户搜索的规 律和兴趣点，分析了用户搜索行为的变化过程，分别从抽象和具体的角度理解和 鉴别用户搜索意图，并提出了一个用户搜索行为模型。 4 ) 分析了用户输入的查询与点击的搜索结果之间的关系，结合数据挖掘算 法提出了搜索分类的算法，并利用用户的搜索历史改进网页排序算法，引入了一 种新的手段评价网页排序算法的有效性。 5 ) 对电信网的安全现状进行了分析，通过对信令数据进行挖掘，建立了电 信网安全防御框架，建立了电信用户正常行为和异常行为模型，有效的应用于电 信网入侵检测系统中。 6 ) 将入侵检测系统的概念和搜索引擎系统结合，通过分析异常搜索行为的 特征建立异常搜索的规则，能够有效检测可能带来潜在威胁的异常搜索行为。 1 3 论文的结构和主要内容 本文主要对搜索引擎的用户搜索日志进行分析，发现用户搜索行为特征，并 将这些特征运用于搜索引擎的改善，包括搜索行为模型的建立、搜索的分类、网 页排序算法的改进、异常搜索行为检测，等。 本文共分七章，各部分内容简单介绍如下： 第一章：绪论。 第二章：基于搜索r 志的用户行为分析。首先介绍了搜索日志的研究现状， 然后分别从用户输入的查询词、用户点击的u r l 、以及基于s e s s i o n 的搜索规律这 三个方面进行详细的统计分析。观察了中文搜索引擎用户所采用的搜索语言、查 询的长度、查询词频分布、高级搜索方式的使用情况、查询词的修改情况等；分 析了u r l 的点击分布情况，并发现了u i u 目录深度和点击频率之白j 的关系；分析 了用户搜索的时间规律。 北京邮电大学博j ：学位论文 第三章：用户搜索行为模型。首先介绍了用户搜索行为的研究现状，接着分 别从抽象和具体的角度对搜索行为进行分类。通过对搜索日志的分析，发现用户 查询的修改规律以及u r l 的点击情况，并首次从搜索日志的角度提出了用户搜索 行为模型，能够有效概括用户的各种搜索行为及记录用户的完整搜索历史。该模 型为后续研究提供了基础。 第四章：基于用户反馈的搜索分类。首先介绍了搜索分类问题的研究现状， 分析了这些方法存在的优缺点。结合用户搜索反馈，提出了一种基于预定义网页 类别的搜索分类算法n b q c 。该算法将网页分类技术和用户搜索历史有效结合， 建立朴素贝叶斯搜索分类器。本章还提出了一种基于实时搜索反馈的搜索分类算 法，克服了用户输入查询过短导致分类误差较大的弊端。 第五章：结合混合频繁模式树和用户反馈的网页排序算法。首先介绍了网页 排序算法的研究现状，包括当前主流搜索引擎所采用的算法以及相关的改进算 法。然后结合用户搜索日志提出了一种基于混合频繁模式树的改进排序算法。该 算法在原有p a g e r a n k 算法的基础上，只对部分搜索结果进行优化排序，既考虑了 用户只浏览前几页搜索结果的特点，又兼顾了网页排序的查全率和执行效率。此 外，还结合用户搜索行为模型，将实时搜索反馈应用于网页排序。本章最后通过 实验证明了算法的有效性。 第六章：异常搜索行为检测。本章针对近年出现的搜索引擎引发的安全问题 提出思考，并列举了高级搜索方式可能导致的潜在安全威胁。本章对异常搜索行 为进行了分类，并提出了异常搜索行为检测框架。采用改进了的决策树算法对异 常搜索行为进行分析，发现了异常搜索行为特征，并应用于异常搜索行为检测。 第七章：结束语。总结了论文的工作，提出了今后需要进一步研究的内容。 1 4 论文研究的创新点 本文的主要创新点可以归纳如下： 1 ) 首次通过分析搜索日志完整的提出了用户搜索行为模型，高度概括了各 种具体搜索行为，并从抽象的角度去理解用户的搜索行为。该模型的提出为进一 步研究搜索行为提供了基础。 2 ) 提出了基于朴素贝叶斯理论的搜索分类算法，将网页分类技术和搜索日 志有效结合并应用于搜索分类。根据网页文档的特点提出了一种属性重要性计算 方法，选择关键属性作为搜索分类器的训练特征属性，降低了计算复杂度。 3 ) 在原有网页排序算法的基础上，根据用户输入的查询与点击的u r l 之问 的映射关系，提出了一种局部优化排序算法，体现了用户的搜索意图，并且不影 响搜索结果的查全率。 4 ) 首次提出了异常搜索行为检测框架。根据异常搜索行为的特点进行分类， 北京邮电大学博i 上学位论文 并根据不同的异常搜索类别建立不同的搜索行为检测模型，能够有效的检测异常 搜索行为。 北京邮电人学博士学位论文 第二章基于搜索日志的用户行为分析 2 1 前言 随着互联网信息的急剧膨胀，搜索引擎已经成为互联网用户必不可少的助 手。大部分搜索引擎都详细记录了用户搜索的完整过程，包括用户的来源、搜索 时间、输入的查询、点击的u r l 等。对搜索日志的分析深入的研究用户搜索行 为特点，可以发掘用户的搜索规律，揭示用户的搜索意图，为提高搜索引擎的质 量提供了参考。 2 1 1 国外搜索日志研究现状 国外对搜索日志的研究始于二十世纪九十年代。包括e x i t e 、l y c o s 、i n k t o m i 等许多著名搜索引擎的出现，引起了诸多互联网用户以及专家学者的注意。随着 互联网的蓬勃发展以及g o o g l e 获得的巨大成功，搜索引擎正式成为互联网发展史 的一个罩程碑。关于搜索引擎的各种研究也不断涌现，其中包括对搜索同志的研 究。 对搜索同志的研究主要包括两个方向：基本研究和扩展研究。其中，基本研 究从搜索同志本身进行分析，发现用户的搜索行为规律和特点。扩展研究主要是 在搜索日志研究的基础上，通过对f 1 志中某一方面的挖掘得到相关的知识，并将 这些知识运用于搜索引擎的改善。 2 1 1 1 基本研究 s i l v e r s t e i n 等人【2 】首次对大规模商业搜索引擎的搜索同志进行分析，发现了 英文搜索引擎用户的一些搜索规律，比如查询的长度、每个s e s s i o n 的搜索次数、 查询词的修改方式、查询词的组合出现频率等。j 趾s e n a 等人 1 2 】在文献 2 】的基础 上比较系统的对搜索r 志进行分析，包括不同查询的数量及其所占的比例，查询 词的修改方式及其所占比例，查询长度的分布，网页浏览数的分布，高级搜索方 式的使用情况，等等。他们统计了一些热门查询词，以及不同搜索类别所占的百 分比；分析了词频分布曲线，并发现该分布曲线和z i p 份布相似。他们还发现很 多用户采用了不j 下确的高级搜索方式，查询词拼写错误的比例也很高。r i c a r d o 等人【1 3 同样发现了词频分布曲线符合z i p 盼布，并据此提出了高速缓存的设计 思路，计算了搜索执行时间和存储容量之间的关系。 l a u 1 5 1 等人将用户的搜索行为分成包括n e w 、g e n e r a l i z a t i o n 、s p e c i a l i z a t i o n 等在内的七个类型；并将搜索意图分成多个类别，例如时事、天气、健康信息、 产品和服务等。通过分析搜索同志，统计了各种搜索类别、各种搜索意图分别占 全部搜索的比例，各种搜索类别、搜索意图的平均搜索长度。此外还分析了不同 类别搜索的持续时间，后续搜索类别的概率等。 北京邮电大学博上学位论文 2 1 1 2 扩展研究 在基于搜索日志的扩展研究中，很多学者希望通过结合用户搜索反馈来提高 搜索引擎的质量，例如发现相关搜索、扩展用户的查询、改善搜索结果排序算法 等。文献 1 8 ，1 9 ，2 0 通过分析搜索日志中查询词和点击u r l 的映射关系，发现 相似查询，用于向用户推荐查询关键词或者扩展查询。 j o a c h i m s 1 7 通过分析用户点击的网页顺序，采用支持向量机( s v m ) 算法 对搜索结果排序提出改进。s h c n 等人 2 1 】通过分析用户的搜索历史，用于改善搜 索结果排序算法。 此外还包括其他一些针对搜索日志的扩展研究。z h a o 等人 16 】通过分析搜索 日志，发现搜索流量的周期性规律，并对搜索日志中的查询和对应点击的u r l 建立无向有权连通图，采用图论的相关算法检测特殊事件的发生。 大多数用户，甚至包括很多专家学者以及搜索引擎开发人员，都认为高级搜 索方式( 例如a n d ，o r 等) 能够有助于改变搜索范围，提高搜索结果的质量。 但是e a s t m a n 等人【1 4 】通过大量试验并与搜索日志进行对比分析，发现高级搜索 方式的作用并不像大家想象的那么乐观。他们主要对“a n d 、“o r ”、“m u s t a p p e a r 以及“p h r a s e ”四种高级方式进行观察，发现采取高级搜索方式确 实影响了搜索的范围( c o v e r a g e ) ，但是搜索结果的相关度( r e l e v a n c e ) 并没有 显著增高。 2 1 2 国内搜索日志研究现状 国内搜索引擎日志的研究起步相对较晚，因此大多数研究参考了国外类似研 究方法。如文献 3 、5 、7 、8 、9 、1 0 、1 1 】等，重点分析了中文搜索引擎用户的 行为特点，包括查询的长度、词频分布、u r l 点击分布、高级搜索方式使用情况 等等。中文搜索引擎用户的搜索行为特点基本和英文用户相似，但是也存在一些 差异。例如中文用户的查询长度相对比较短，高级搜索方式所占的比例明显较低 等。 随着国内商业搜索引擎得到广泛应用，对搜索日志的扩展研究也日益增多。 l i u 等人【l 】结合文献 2 2 、2 3 关于搜索的分类定义，通过对搜索同志进行分析发 现不同类型搜索的特征，例如导航类( n a v i g a t i o n a l ) 搜索比信息类( i n f o r m a t i o n a l ) 搜索的点击次数少，并且对应点击网页的排序值较小。王建勇等人 7 】分析了相 邻n 项查询词的偏差，发现用户查询项分布过程具有自相似性，并以此提出高速 缓存替换策略。此外他们还分析了网页被访问次数与网页的镜像数，网页的入度， 以及网页目录的深度之间的关系。 2 1 3 本章研究出发点 目前针对中文搜索引擎同志的研究，很少有从中、英文语言的差异以及中、 北京邮 【1 人学博上学位论文 英文搜索引擎用户的搜索习惯差异的角度进行分析，国外对搜索日志分析的结论 并不一定适合中文搜索引擎用户。国内关于搜索日志的研究，总体可以分为两个 阶段。第一阶段主要以北京大学“天网 搜索引擎提供的日志为研究对象，并部 分参考了国外研究方法，产生了一批中文搜索引擎日志分析成果。但是“天网 的用户群规模与目前主流商业搜索引擎相比不可同日而语。随着“百度 等商业 搜索引擎的成功，“天网”渐渐淡出了人们的视线。但是，商业搜索引擎出于商 业机密等因素的考虑，很少将搜索日志及研究成果公开。第二阶段始于s o g o u 实验室公开其搜索日志，供公众进行科学研究，其后产生了一些新的研究成果 【l 】【3 】【8 】。 本文选择s o g o u 商业搜索引擎提供的最新搜索日志，结合以前的研究成果， 分别从用户的搜索时间、输入的查询词、点击的次数、点击的u r l 排序号等方面， 进行详细分析。本文还从中英文语言差异的角度出发，引入中文分词算法，更深 入的分析中文搜索引擎用户的搜索规律。 通过本章对搜索日志的全面分析，有助于用户搜索行为模型的建立，搜索分 类问题的研究，搜索结果排序算法的改进，以及对异常搜索行为的检测。 2 2 数据对象及相关工具介绍 2 2 1 搜索日志 本文选择s o g o u 搜索引擎提供的2 0 0 6 年8 月搜索同志进行分析。该日志已经 对原始数据进行了清理，去除了无效搜索，得到有效搜索记录为2 1 3 6 2 4 6 2 条。 本文基于搜索时间的日志分析还选择了s o g o u 提供的2 0 0 7 年3 月的搜索日 志。和2 0 0 6 年8 月的搜索日志相比，2 0 0 7 年3 月的搜索日志规模更大，并且记录日 期较新，更能体现当前用户的搜索规律。更重要的是，2 0 0 7 年3 月的搜索日志增 加了“搜索时间这个属性，有利于发掘更多的潜在规律。 s o g o u 提供的搜索日志为纯文本文件，数据格式为：搜索时间t 用户i d t 查 询词1 t 该u r l 在返回结果中的排名t 用户点击的顺序号t 用户点击的u r l 。其中， 用户i d 是根据用户使用浏览器访问搜索引擎时的c o o k i e d 言息自动赋值，即同一次 使用浏览器输入的不同查询对应同一个用户i d 。 需要说明的是，本文中对“查询( q u e r y ) ”和“搜索( s e a r c h ) 一并没有作明 确区分，国内外研究文献中也没有对这两个术语明确定义，通常都表示用户的搜 索行为。细微的差别在于“查询 更偏重于用户输入的查询词，而“搜索 偏重 于搜索行为，但是很多时候这两者可以相互替代 2 2 2 分词工具 本文的中文分词部分实验采用中国科学院计算技术研究所丌发的基于多层 北京邮电人学博士学位论文 隐马尔科夫模型的汉语词法分析系统i c t c l a s ( i n s t i t u t eo fc o m p u t i n g t e c h n o l o g y ，c h i n e s el e x i c a la n a l y s i ss y s t e m ) 。该系统提供开源分词模块，能够 对中文语句进行有效分词。 分词采用的词典包括三部分：一是中国科学院计算技术研究所提供的 d i c t i o n a r yf r e eb u i l d 0 7 0 5 。第二部分是由s o g o u 提供的基于互联网语料环境的 高频词库v 1 0 ，该词库涵盖了中文互联网l 亿页面以上出现的1 5 万条高频词。第 三部分是本文对2 0 0 6 年8 月s o g o u 搜索引擎用户输入的查询词进行分析，选择添 加了部分高频的查询词。 2 3 搜索日志基本分析 2 3 1 基于查询词的分析 2 3 1 1 查询语言的分析 通过对搜索日志的统计，得至u 2 0 0 6 年8 月总计查询次数为2 1 3 6 2 4 6 2 。其中： 纯英文字符查询次数为2 0 6 4 1 5 5 ，占总体的9 7 ；中英文混合查询次数为1 8 2 3 0 7 7 ， 占总体的8 5 ；少量非常规字符，如日文、不合法字符，所占的比例可以忽略不 计；其余全部为中文查询，约占总体的8 1 8 。可见，目前中文搜索引擎的用户 主要还是采用中文查询词进行搜索。采用英文和数字的查询中，很多是某些名称 的缩写。例如，和2 0 0 6 年8 月的搜索同志相比，2 0 0 7 年3 月的搜索日志中包含了很 多股票代码查询，这些代码全部由数字表示。此外，诸如“m p 3 一、“q q 、“a c d s e e 等，以及直接输入网址的查询，都是采用英文字母或数字作为查询串。 2 3 1 2 查询词长度的分析 为区分分词前后用户查询词的表示方式，本文定义用户原始输入的搜索关键 词为“查询串，一个查询串由一个或多个“短语 组成，相邻两个短语之间由 空格隔开。短语经过分词后形成“词”组，一个短语可以分词成一个或多个词。 由于中英文天然的差异，导致对中、英文搜索引擎搜索r 志的分析产生不同 的结果。英文的句子由多个单词组成，两个单词之间由空格隔开。中文句法和英 文完全不同，单词之间没有空格。并且，虽然中文搜索引擎用户可以在输入查询 词的时候用空格隔开，但是对查询同志的分析显示，很少有用户愿意将一个短语 彻底的“解剖成词组后输入。从表2 1 中的数据可以看出，2 0 0 6 年8 月约9 0 左 右用户只输入一个短语进行查询，很少有人输入4 个以上的短语。用户的平均查 询短语数为1 1 4 ，这显然与 2 】中的平均值2 3 5 相差比较大。 考虑到中文和英文的句子成分( 如主语、谓语等) 以及词性( 名词、动词等) 存在着共同点，因此我们猜测如果对中文查询短语进行分词，然后再进行分析所 北京邮电火学博士学位论文 得的结果可能更接近英文搜索引擎日志的分析结果。于是我们采用第2 2 2 中的词 典以及分词算法，对2 0 0 6 年8 月l 同的查询串进行分词处理，得到表2 1 右侧数据。 用户的平均查询词数为2 2 7 ，与【2 】中的值基本相符。 分词前查询短语统计 分词后查询词统计 统计项 0 8 0 10 3 0 1 统计项 0 8 0 10 3 0 1 一个短语比例9 0 8 4 7 一个词比例3 6 3 1 1 8 9 两个短语比例7 5 1 1 8 两个词比例3 0 5 6 2 4 8 l 三个短语比例1 7 2 8 三个词比例1 5 9 5 2 8 3 8 四个短语以上比例0 8 6 四个词比例1 0 0 2 2 0 9 5 平均短语数 1 1 41 2 五个以上比例 7 1 7 1 3 9 7 最多短语数 3 4 94 l 平均词数 2 2 73 1 标准差 0 5 7o 5 5标准差2 1 12 2 6 表2 - 1 ：8 月1 日与3 月1 日查询短语分词前后对比 此外，我们将0 6 年8 月的日志和0 7 年3 月的日志进行对比，发现一些有意义的 信息。0 6 年8 月的平均输入字符长度约l0 ，而0 7 年3 月平均输入字符长度约12 。我 们估计随着互联网用户水平的提高，其构造查询串的能力也在增长。用户开始愿 意构造一些复杂的查询来反映其搜索意图。于是我们进一步对比二者的短语数 量，发现用户输入的短语数量确实在上升。只输入一个短语的查询比例在下降， 而输入多个短语的查询比例在上升。我们再对查询串进行分词处理，发现查询串 中包含的单词数量也显著增加，见表2 1 。 2 3 1 3 查询词频分析 我们对用户输入的查询短语出现的频率进行分析，得到图2 1 所示的结果， 其中横轴表示查询短语被搜索的频率，纵轴表示不同频率的查询短语占全部查询 短语的比例。在对查询短语进行分词之前，超过4 0 的短语只被搜索过一次，超 过9 0 的短语被搜索的次数小于l o 。由于8 月l 同的查询短语的频率分布曲线和当 月的分布曲线基本吻合，因此我们选择该日的搜索日志进行分词处理。分词之后， 曲线相对平缓一些，有相当一部分比例的词被搜索的次数超过1 0 0 。此外，我们 还选择对0 7 年3 月1 日的搜索同志进行分词处理，同样观察不同出现频率的查询词 所占的总查询词比例，其分布曲线基本和0 6 年8 月1 日分词后的曲线吻合。这说明 半年以来用户输入的查询词汇分布没有发生明显变化，但是只出现一次的查询词 所占的比例有所降低，高频查询词的比例略有上升。 北京邮电大学博：j ：学位论文 123455 - 1 01 0 - 5 05 0 - 1 0 0 1 0 0 - 5 0 05 0 0 + t e r m w o r df r e q u e n c y 图2 - 1 ：词频与其所占查询总体的比例关系 o oo 1 o 2 o 3o 4o 5o 6o 7 o 80 91 p e r c e n t a g eo ft e r m s w o r d s 图2 2 ：查询词与点击关系 此外我们还将每个查询短语被搜索的次数进行降序排列，分析y = fp ，的曲 x = l 线。其中x 为查询短语的离散序列，p ，为查询短语x 被搜索的次数占总搜索数的 比例。图2 2 表明在分词之前，约2 0 的短语约占了8 0 的搜索量，这和 5 】中的 数据基本相符。但是当我们对查询短语进行分词后，发现用户的搜索热点比预期 的还要集中，1 0 的词约占了8 5 的搜索量。我们再对0 7 年3 月1 日的同志进行相 同的处理，发现其分布曲线和0 6 年8 月l 同分词后的曲线基本吻合。于是我们专门 分析了8 月1 同及当月十大热门查询词。表2 2 显示，8 月1 日十大热门查询词占当 同全部查询的2 8 2 5 ，这相对于当月十大查询词所占的4 9 的比例偏高。又如 “张木秽这个查询词，8 月l 同的搜索量占该词当月搜索量的一半以上。出现这种 现象的原因可能是由于一些突发事件的存在，如某个重要纪念同、八卦新闻等， 5 4 3 2 1 o 0 o o o o o 西；匕兽lu卫=口一曩2芑。口凸氧v。jo也 o 9 8 7 6 5 4 3 2 1 o 1 o o o o o o o o o o pjo，sei宴p9u3jeo一口9芑。功腰c8毒t 北京邮电大学博士学位论文 会导致某些词的搜索量急剧增加。这对于设计查询c a c h e 的时候具有很大的参考 价值。除了采用 5 】中建议的l l u 替换算法，一些热门查询词可以考虑设置较高 的优先级，以减少由于替换算法的缺陷带来的消耗。此外8 月1 日的十大查询词有 一半出现在当月的十大查询词中，可见热门的查询存在一定的延续性。 8 月1 _ 日十大查询词8 月十大查询词 张x x ：6 8 7 5 6陋俗：3 3 9 9 9 0 林彪：5 2 8 9 7女艺人：1 1 3 5 6 2 周恩来：4 0 8 1 8张幸：1 1 2 6 0 3 富婆：3 6 5 8 1周恩来：1 0 8 3 4 3 惊人一幕：2 7 7 0 2明星：7 7 2 1 l 村妓：2 4 8 7 0十景缎：7 0 9 4 0 明星：1 4 0 5 3林彪：6 9 7 8 9 翁美玲：1