（计算机应用技术专业论文）web挖掘在搜索引擎个性化中的应用研究.pdf

w e b 挖掘在搜索引擎个性化中的应用研究 摘要 随着i n t e m e t 的发展与普及，网上信息量的急剧膨胀，w e b 己成为人们获取信 息的一个重要途径，使得搜索引擎成为辅助网络信息检索的重要工具。w e b 挖掘为 实现个性化信息检索提供了技术支持，利用用户兴趣向用户提供个性化服务已经成 为w e b 应用领域的一个研究热点。本文针对w e b 挖掘在搜索引擎个性化中的应用 进行研究，主要工作如下： 首先，本文阐述了搜索引擎现状及存在的问题，提出了个性化搜索引擎的重要 意义。分析了搜索引擎工作原理、组织结构及各部分功能，并对向量空间模型进行 了详细的研究。 其次，论文介绍了w e b 挖掘的定义、任务及与信息检索的关系，研究了w e b 挖掘技术及w e b 内容挖掘、结构挖掘和使用挖掘在搜索引擎中的应用。详细讨论了 基于用户浏览行为获取用户兴趣的方法，提出了对向量空间模型( v s m ) 改进方法， 研究了用v s m 构建初始的用户兴趣模型，然后根据用户浏览行为自动学习用户兴 趣并对其模型进行更新及个性化信息过滤等关键技术。另外，针对大量同义词的存 在，为了提高检索覆盖率，建立同义词词典，以扩充检索词来对查询语句进行优化。 最后，在上述研究的基础上，设计了一个基于w e b 挖掘的个性化搜索引擎模型 p s e ，给出了各模块的功能及实现方法，从理论上分析该个性化搜索引擎具有灵活 的检索方式和个性化的查询结果等特点。论文结尾，对本文所做的工作进行了总结 并对个性化信息检索的发展进行了探讨。 关键词：信息检索；搜索引擎；空间向量模型；w e b 挖掘；用户兴趣；个性化 a p p l i c a t i o n so fw e bm i n i n gi np e r s o n a l i z e ds e a r c he n g i n e a b s t r a c t w i t ht h ed e v e l o p m e n ta n dp o p u l a r i t yo fi n t e r n e t ，w e bh a sb e c o m ea l li m p o r t a n tw a y o fg e t t i n gi n f o r m a t i o n b e c a u s eo ft h er a p i de x p a n s i o no fo n l i n ei n f o r m a t i o n ，s ep l a y sa v e r yi m p o r t a n tr o l e i ns e a r c h i n gn e t w o r ki n f o r m a t i o n w e bm i n i n gp r o v i d e st e c h n i c a l s u p p o r tf o rp e r s o n a l i z e di n f o r m a t i o ns e a r c h p e r s o n a l i z e ds e r v i c eo r i e n t e dt o w a r d su s e r p r o f i l e s h a sb e c o m eah o ti s s u eo fr e s e a r c hi nw e bt e c h n o l o g i e s r e s e a r c h i n go n a p p l i c a t i o n so fw e bm i n i n gi np e r s o n a l i z e ds e a r c he n g i n e ，t h em a i nt a s k sf o rt h i s d i s s e r t a t i o na r ea sf o l l o w i n g ： f i r s t l y ，t h i sd i s s e r t a t i o na n a l y z e st h ec u r r e n ts t a t u sa n dp r o b l e m so fs e ，p o i n t so u t t h es i g n i f i c a n c eo fs t u d y i n gp e r s o n a l i z e di n f o r m a t i o nr e t r i e v a l i ta n a l y s i z e st h ew o r k i n g p r i n c i p l e ，t h eo r g a n i z a t i o ns t r u c t u r ea n df u n c t i o n so fs e d e t a i l e ds t u d i e sa r ea l s om a d eo n t h es p a c ev e c t o rm o d e l ( v s m ) s e c o n d l y ，t h i sd i s s e r t a t i o ni n t r o d u c e st h ed e f i n i t i o na n dt a s k so fw e bm i n i n g ，s t u d i e s a n da n a l y z e st h er e l a t i o nb e t w e e nw e b m i n i n ga n dt r a d i t i o n a li n f o r m a t i o nr e t r i e v a la n dt h e a p p l i c a t i o n so fw e bm i n i n gi ns e i ti n t r o d u c e si nd e t a i lt h em e t h o d so fa c c e s s i n gu s e r s i n t e r e s t sb a s e do nu s e r sb r o w s i n gb e h a v i o ro nw e b t h i sd i s s e r t a t i o np r o v i d e sam e t h o do f i m p r o v i n gv s m i ts t u d i e st h ek e yt e c h n o l o g i e sw h i c ha i mt ou s ev s m t oe s t a b l i s hi n i t i a l b s e ri n t e r e s tm o d e l s ，a n dt h e na u t o m a t i c a l l yu n d e r s t a n da n dl e a r nt h ei n t e r e s to fu s e r sb a s e d o nt h em i n i n gb e h a v i o r so fu s e r s ；a n dt h e nr e n e wt h em o d e l sw i mf i l t e r e dp e r s o n a l i z e d i n f o r m a t i o n i na d d i t i o n ，d u et ot h ee x i s t e n c eo ft h el a r g en u m b e ro fs y n o n y m sa n di no r d e r t oi m p r o v er e t r i e v a lc o v e r a g e ，i ti sr e c o m m e n d e dt oe s t a b l i s hs y n o y m s d i c t o n a r yt oe x p a n d t h es e a r c ha n do p t i m i z et h eq u e r y f i n a l l y , b a s e do nt h e a b o v es t u d i e s ，t h i sd i s s e r t a t i o nd e s i g n sap e r s o n a l i z e d i n f o r m a t i o nr e t r i e v a lp s eb a s e do nw e bm i n i n g ，a n dd e s c r i b e si nd e t a i lt h ef u n c t i o n sa n d r e a l i z a t i o no fr e l a t e dm o d u l e s i tc a r r i e so u ts t u d yf r o mat h e a t e t i c a lp r o s p e c t i v ea b o u tt h e f a c tt h a tt h ep e r s o n a l i z e ds eh a st h ec h a r a c t e r i s t i c ss u c ha sf l e x b i l es e a r c h i n gm e t h o d sa n d p e r s o n a l i z e dr e t r i e v a lr e s u l t se t c a tt h ee n do ft h i sd i s s e r t a t i o n ，t h ea u t h o rs u m m a r i z e st h e w o r kt h a th a sb e e nd o n ea n de x p l o r e st h e d e v e l o p m e n tp o t e n t i a l 。o fp e r s o n a l i z e d i n f o r m a t i o nr e t r i e v a l k e y w o r d s ：i r ；s e ；v s m ；w e bm i n i n g ：u s e ri n t e r e s t ；p e r s o n a l i z e d i i 插图清单 图2 1 搜索引擎系统结构8 图2 2 文档v s m 及相似度s i m ( d 。，d 2 ) 1 3 图3 1w e b 的逻辑结构1 5 图3 2w e b 挖掘的分类1 6 图3 3 基于超链相关度的排序2 l 图3 4 结果的联机聚类2 1 图3 5 相关度反馈2 4 图5 1 个性化搜索引擎模型3 7 图5 2 获取用户浏览信息流程图4 1 图5 3 个性化搜索用户注册( 1 ) 4 4 图5 4 个性化搜索用户注册( 2 ) 4 5 图5 5 个性化搜索引擎查询接口4 5 图5 6 个性化搜索结果示例4 6 v i 表格清单 表4 1 服务器日志一般格式2 8 表4 2 用户操作方式对应权值设置2 9 表5 1 用户浏览行为库4 2 表5 2 关键词库4 2 v u 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得 金月曼王些太堂或其他教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 学位论文作者签名：张身易签字日期：力谚年，月多同 学位论文版权使用授权书 本学位论文作者完全了解金月巴王些太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权佥壁王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：锄老b 签字同期：印9 年，月，6 日 学位论文作者毕业后去向： 工作单位：山缘停蚀定哕叛黼p 通讯地址：弘觜海确印缘- 钆球饧“弓 导师虢周】纫砑 签字同期：彩年产月7 7 同 电话：幽多，2 7 芗，l ；口 邮编：z ，口多， 致谢 本人在硕士研究生课程学习和撰写学位论文的过程中，自始至终得到了我的导 师周国祥教授的悉心指导，无论从课程学习、论文选题，还是到收集资料、论文成 稿、修改到最后定稿，都倾注了周老师大量的心血，由衷感谢周老师在学业指导及 各方面所给予我的关心以及从言传身教中学到的为人品质和道德情操，老师广博的 学识、严谨的治学态度、忘我的工作精神、诲人不倦的教育情怀和对事业的忠诚， 令我永生难忘，终身受益，并激励我勇往直前。在这里，谨向周老师致以最衷心的 感谢和崇高的敬意! 同时，我要感谢合肥工业大学的领导和老师，感谢参加评审答辩的老师，感谢 我单位( 山东信息职业技术学院) 的领导和同事及所有教育帮助过我的老师，他们 的教诲为本文的研究提供了理论基础，并创造了许多条件和学习机会，在我课程学 习和论文撰写期间，给予了我大力支持和帮助。 再次感谢所有帮助过我的领导和老师! i l l 张艳 2 0 0 8 年5 月 第一章绪论 1 1 引言 i n t e m e t 已成为当今人们发布和获取信息的主要渠道之一，i n t e m e t 上流通的 信息也在呈爆炸性增长，据c n n i c 报告【1 1 ，截至2 0 0 5 年1 2 月3 1 日，全国网 页数量约为2 4 亿，全国网页总字节数约为6 4 t b ，w e b 上的数据正以每天新增 一百万个页面的速度增长。w i e b 已经成为人们生活、工作、娱乐等必不可少的 工具。2 0 0 7 年7 月1 8 日中国互联网信息中心c n n i c 发布第2 0 次中国互联网 络发展状况统计报告【2 】，报告显示，截至2 0 0 7 年6 月3 0 日，我国网民人数达 到1 6 2 亿，半年来平均每分种就增加近1 0 0 网民，互联网的普及率达到了1 2 3 。 我国网站数量达到1 3 1 万个。报告还显示，互联网的获取信息、娱乐和沟通功 能被普遍使用，网络新闻和搜索引擎的网民使用比例已达7 6 3 。6 9 8 的网民 都使用实时通信功能，5 5 4 的网民使用电子邮件。网络音乐使用率已经超过 6 8 5 ，玩过网络游戏的网民也已经达到4 7 o 。1 5 的网民通过网络找工作， 2 5 5 的网民使用网络购物，3 9 的人进行网上旅行预订。已有1 5 的网民开始 使用网上银行和网上炒股，我国网上炒股的比例已与互联网普及率高的美国相 当。中国网民平均每周上网小时数是1 8 6 小时，与历史数据相比，中国网民的 上网时间仍在逐年提高，比2 0 0 6 年1 2 月的1 6 9 小时提高了近2 个小时。 1 2 信息检索系统现状与存在问题 为了有效地获得自己需要的信息，i n t e m e t 上的信息检索系统搜索引擎 ( s e a r c he n g i n e ) 成为人们必不可少的帮手。搜索引擎为用户提供了友好而高 效的w e b 信息访问接口，在网络资源定位、准确查询w e b 信息中起到了相当重 要的作用。c n n i c 发布2 0 0 6 年中国搜索引擎市场调查报告 3 1 ，报告显示：页面 搜索、地址栏搜索和工具条搜索成为当前用户搜索信息的三大搜索方式。其中， 使用页面搜索的比例占7 6 7 ，仍然占据绝对主导地位。4 4 7 1 的网民经常使 用( 每天多次使用) 搜索引擎，可见近半数网民高度依赖搜索引擎提供的服务。 另外，每天使用一次搜索引擎的用户也占到1 7 2 ，这意味着每日使用搜索引 擎用户数高达6 1 9 1 。由此可见，网民的搜索依赖性呈现增强趋势。自2 0 0 0 年以来，搜索引擎用户的年度增加速度基本稳定在1 2 左右，而进入2 0 0 6 年后， 搜索引擎用户的增速开始放缓降到1 1 3 2 ，截至2 0 0 7 年9 月，2 0 0 7 年的搜索 引擎新增用户数是7 7 。c n n i c 预计，搜索引擎用户增速在2 0 0 7 年仍将保持 微量下调的趋势。在用户首选的搜索引擎中，百度首选市场份额，达到了7 4 5 ， 占到了用户首选搜索引擎市场的7 成以上。g o o g l e 的首选市场份额是1 4 3 。 搜索引擎在一定程度上满足了用户的需求，但由于搜索引擎使用的信息检 索技术智能水平的限制，以及对自然语言理解的制约，搜索结果重视的是返回 的数量而不是质量，在结果文档的组织和分类上也有所欠缺。国外多次调查结 果显示，约有7 1 的人对搜索的结果感到不同程度的失望。 目前i n t e m e t 上的搜索引擎可分为两大类：一类是按关键词进行内容检索的 搜索引擎，另一类是分类搜索引擎，这两类搜索引擎的功能是互相借鉴和渗透 的。 按照信息搜集方法和提供的服务方式的不同，搜索引擎系统可以分为以下 四类【4 1 ： ( 1 ) 基于关键词查询的搜索引擎 w e b 上的网页通过超链建立链接，这种链接结构可以看作是一个有向图， 每个网页就是图中的一个结点，一个超链则是一条有向边。基于关键词检索的 搜索引擎，例如g o o g l e 、百度等，就是利用一种软件( 称为r o b o t ，s p i d e r ，c r a w l e r 或w a n d e r ) 按照某种搜索算法，循着超链接遍历整个w e b ，并取回访问的每个 文档，这些文档及它们的位置信息存于搜索引擎的索引系统内。索引系统从文 档中提取一些有代表意义的信息，将它们保存在数据库中。当用户输入关键字 进行查询时，搜索引擎检索数据库以查找匹配的文档，将结果返回给用户。它 的代表是a l t a v i s t a 5 1 ，n o r t h e r nl i g h t l 6 ，g o o g l e ，i n f o s e e k 7 1 、百度等。 ( 2 ) 基于目录的搜索引擎 基于目录的搜索引擎，例如讪o o 【引、o p e n d i r e c t o r y 9 1 、s n a p 1 0 】等，与基于 关键词检索搜索引擎工作方式不同，它并不使用r o b o t 下载w e b 文档，而是由 人工收集或者由w e b 站点的作者主动提交；目录一般也不对文档内容进行自动 分析和建立索引，而是由人工对w e b 站点和文档进行评价、分类并给出简要描 述，经过上述处理的w r e b 信息资源按照主题分类并以树状的形式加以组织，从 树的根节点逐层向下列出了从一般到特殊的分类及各级子类，而叶节点则包含 指向w e b 信息资源的链接。用户可以通过浏览目录中的分类来查找w e b 信息。 当目录中包含太多的分类和超链接时，目录本身也变得不便于浏览。为此，目 录通常也提供检索功能以方便用户。需要说明的是，目录提供的是对分类以及 w e b 信息描述的索引，这与搜索引擎提供对文档内容的全文索引是不同的。 关键词查询搜索引擎和目录搜索引擎两种w e b 信息检索系统各有所长。通 常，由于关键词查询搜索引擎具有庞大的全文索引数据库，适用于检索难以查 找的信息或者一些比较模糊的主题；而目录搜索引擎有助于逐步缩小主题或者 查找某个主题的常见的、质量较高的信息。由于这两种系统彼此互补，因此一 2 些将两者结合起来的混合系统也开始出现。例如l o o k s m a r t 1 1 】等。现有的一些 著名的搜索引擎和目录也呈现出逐渐融合的趋势。例如y a h o o 在目录检索服务 的基础之上，已经开始使用i n k t o m i i 垃】的w e b 全文索引数据库提供与搜索引擎 类似的w e b 信息全文检索服务。因此，常把这两种搜索引擎统称为搜索引擎。 ( 3 ) 元搜索引擎 虽然各个搜索引擎为了在竞争中获胜而不断地增加其索引的w e b 页面数 目，但是却跟不上w e b 发展的速度。w e b 的覆盖面有限，根据s t e v el a w r e n c e 的报告【l 孔，目前任何搜索引擎索引的部分不超过整个w e b 的3 0 ，随着有效检 索信息数量的增加，同时带来了负面影响，即减少了查询潜在信息的机会。因 此，用户经常需要使用多个搜索引擎检索以提高查全率。但是，各个搜索引擎 的用户接口是异构的，有其特定且复杂的界面和查询方法，这给用户同时使用 多个系统带来了不便，一些研究人员面对这种状况而开发了元搜索引擎，例如， m e t a c r a w l e r 1 4 1 ，s a v v y s e a r c h b5 1 ，i n q u i r u s t l 6 】等。 元搜索引擎的基本设计思想可以总结如下： 对用户查询请求进行预处理，分别将其转换为若干个底层搜索引擎以处 理的格式。 向各个搜索引擎发送查询请求，并等返回检索结果。例如，m e t a c r a w l e r 同时向g o o g l e ，y a h o o ，m s ns e a r c h ，a s k ，l o o k s m a r t ，a l t a v i s t a 等9 个主要 搜索发送查询请求。 对检索结果进行后处理，包括：组合各个搜索引擎返回的检索结果，消 除重复项，对结果进行相关性排序等。有些搜索引擎在必要时还通过下载的w e b 文档来实现一些搜索引擎不支持的查询，或者对文档进一步地分析以提高信息 检索的精度。 向用户返回经过组合和处理后的检索结果 上述思想虽然简单，但是效果比较明显，对于设计人员而言，不需要建立 和维护庞大的索引数据库，也不需要使用复杂的检索机制；对于用户而言，元 搜索引擎提供了一个能够同时查询多个搜索引擎的集成界面，将各个搜索引擎 的位置、接口等细节屏蔽了起来，同时提高了查全率和查准率。 目前这些搜索引擎仍然存在以下四个主要问题： 搜索引擎一般都采用关键词检索方式，用户在提出检索请求制定检索策 略时，常常很难简单地用关键词或其间的逻辑组合来准确地表达真正需要的信 息内容，表达困难导致检索困难。 搜索引擎面对的是形形色色的用户，这些用户的信息需求、知识背景、 兴趣各不相同，而基于关键词的搜索，无法得到个性化的搜索结果。 搜索引擎返回的检索结果有成千上万条，其中含有大量重复、冗余信息， 查准率低；由于索引数据库存储量有限，导致查全率不高。 无自主学习能力。用户的反馈信息不能及时地调整检索策略，而且用户 每次都是从头开始的检索，不能从原来的查询结果中做进一步的提炼，降低了 检索的效率。单个用户的检索结果也不能被其他相同需要的用户共享。 ( 4 ) 信息检索a g e n t 为了实现信息检索的智能化，人们将人工智能技术引入到信息检索中，已 经研究出了各种智能信息检索方法，提出了许多智能型检索系统模型，主要分 为两大类：一类是基于机器学习的大范围的信息检索系统，另一类就是智能化 的用户个性化信息检索系统。 a g e n t 技术是一种分布式计算环境下软件智能化技术，是人工智能和网络技 术相结合的产物，它提供了一种在分布式异构环境下智能化应用、实现智能化 协调的全新的技术模式。 目前a g e n t 在研究领域尚没有一个统一的定义，我们可以这样理解：a g e n t 是为达到某个特定的目标，在对外部环境的相互作用的基础上，通过对环境状 态的认识以及和其它a g e n t 的协作，自动地推进问题解决的处理单位。 信息检索a g e n t 与搜索引擎等系统的区别在于它具有以下特征： 可适应性。它能够在用户日常的检索、浏览等行为中学习用户兴趣，对 用户的需求推理，为每个用户建立个性化的p r o f i l e 。 主动性。能够主动地根据用户的兴趣需求从w e b 上检索相应信息，甚 至能够监控信息源的变化，及时地报告给用户。这些工作不需要用户参与，而 由a g e n t 利用自身的控制机制、知识等进行任务的规划、问题求解。 协作性。信息检索a g e n t 之间可以共享和交流信息，实现协作式信息检 索。 移动性。信息检索a g e n t 能够移动到远程服务器上，并在服务器上进行 信息检索，以避免将信息下载到客户端。在服务器上信息量很多，客户与服务 器之间没有持久、稳定的网络连接，或者客户机的处理能力不够时，移动a g e n t 十分有用。 在上述4 个特征中，前3 个是信息检索a g e n t 一般都具有的。但是由于缺 乏一个广为接受的、安全的基础运行环境，移动性目前仍处于实验阶段。 在信息检索领域中，对a g e n t 的研究取得了十分丰富的成果。例如， c a m e g i e m e l l o n 大学开发的w e b w a t c h e r 、w a s h i n g t o n 大学开发的s h o p b o t 、 4 s t a l l d f o r d 大学开发的f a b 等。这些信息检索a g e n t 是一些智能化的程序，它们 能够学习用户的需求，并利用搜索引擎等系统提供的现有服务来检索用户所需 的信息。 基于信息检索a g e n t 的搜索引擎有以下两种： 智能或知识搜索引擎。智能搜索引擎是根据目前搜索引擎的发展趋势， 除提供传统的全网快速检索、相关度排序等功能外，还提供角色登记、智能化 信息过滤和推送等功能，为用户提供了一个真正个性化、智能化的网络工具。 智能搜索引擎服务器端由多台分布式服务器组成，查询信息响应时间小于1 秒， 查全率指标相对较高，查准率接近人工分类的搜索引擎的准确率。客户端通过 专用浏览器或插件，自动识别用户兴趣，通过智能搜索引擎按用户兴趣搜索、 过滤、推送信息，并可实现网上兴趣和理解的能力。一般搜索引擎缺乏知识能 力和理解能力，对要检索的信息仅仅采用机械的关键词匹配来实现。智能搜索 引擎能将目前基于关键词层面检索提高到基于知识( 或概念) 层面。 智能检索利用分词词典、同义词典、同音词典改善检索效果，进一步还可 在知识层面或者说概念层面上辅助查询，通过主题词典、上下位词典、相关同 级词典，形成一个知识体系或概念网络，给予用户智能知识提示，最终帮助用 户获得最佳的检索效果。另外，智能检索还包括歧义信息和检索处理，通过歧 义知识描述库、全文索引、用户检索上下文分析以及用户相关性反馈等技术结 合处理，高效、准确地反馈给用户最需要的信息。知识检索的主要理论依据是 本体论。 个性化搜索引擎。此类搜索引擎最重要的特征是具有学习功能，能够在 信息交互中获得用户信息，包括用户的兴趣、爱好和思维方式。在此前提下， 系统可主动、定期地为用户查找信息，并根据用户搜索信息的变化调整“知识 库”中通用字和关键词，使之能够有效地适用专门领域的信息搜索。系统的本 地信息库可以对搜索到的信息进行分类存储和管理，并具有与其它系统的协作 功能，扩展灵活，维护方便。目前此类搜索引擎在搜索引擎中所占比例很小， 但其发展代表着网络信息资源检索的一个方向，已得到业界的重视，其主要代 表为a g e n t ( w w w a g e n t c o r n ) 1 3 本论文的研究内容、拟解决的关键问题及创新之处 搜索引擎缺乏知识处理能力和理解能力，对要检索的信息仅仅采用机械的 关键词匹配来实现。把信息检索从目前基于关键词层面提高到基于知识( 或概 念) 层面，是解决问题的根本和关键。为了解决w e b 信息检索中存在的各种问 题，1 9 9 6 年e t z i o n i 提出了w 曲挖掘( w 曲m i n i n g ) 的概念【1 7 】：在已知数据样 5 本的基础上，通过归纳学习、机器学习、统计分析等方法得到数据对象间的内 在特性，据此采用信息过滤技术在网络中提取用户感兴趣的信息或者更高层次 的知识和规律，简单地说，就是使用数据挖掘技术自动地从w e b 文档和服务器 中发现和提取信息和知识的技术。 1 3 1 本论文研究的内容 本论文旨在利用w e b 挖掘技术提高搜索引擎的查全率和查准率，为用户提 供个性化的信息服务。在w e b 信息检索中，通过对用户查询请求及访问w e b 的 行为、访问频度、访问内容等浏览信息进行挖掘，提取出用户的特征，获取用 户访问w e b 的模式，建立用户兴趣模型，对返回结果进行个性化过滤，提高查 询精度，满足用户个性化需求，是新一代搜索引擎要解决的关键问题。 本论文主要研究以下内容： ( 1 ) 介绍w e b 挖掘技术，分析w e b 挖掘与信息检索的关系，研究w e b 挖掘 在信息检索中的应用。 ( 2 ) 研究个性化信息检索关键技术，分析研究了对检索结果进行排序、聚类、 相关反馈等处理技术。提出基于用户浏览行为建立和更新用户兴趣模型的方法， 给出个性化信息过滤算法。 ( 3 ) 基于w e b 挖掘的个性化搜索引擎设计，利用w e b 挖掘技术及智能a g e n t 实现个性化的信息检索系统，并对相关的功能模块进行详细的说明，对系统性 能进行分析。 1 3 2 本文拟解决的问题 ( 1 ) 如何准确收集用户访问行为、访问频度、访问内容等浏览信息； ( 2 ) 如何正确度量和表达用户的浏览兴趣； ( 3 ) 如何建立、更新用户兴趣模型及同义词词典； ( 4 ) 利用同义词词典对检索词进行优化，利用用户兴趣模型对检索结果进行 优化过滤。 1 3 3 本论文创新之处 通过收集用户访问内容、时间及频度等浏览信息，利用w e b 挖掘技术对浏 览内容及浏览行为进行挖掘，准确度量用户兴趣；利用w e b 挖掘技术对向量空 间模型v s m 进行改进，提高向量空间模型的准确率。利用同义词词典对查询关 键词进行优化，提高搜索引擎的查全率。 1 4 小结 本章论述了信息检索技术在w e b 上获取信息的重要性，详细地分析了w e b 上四类信息检索工具基于关键词的搜索引擎、基于目录的搜索引擎、元搜 6 索引擎及信息检索a g e n t 的特点及现状，指出w e b 挖掘技术可以实现个性化信 息检索服务，在此基础上给出了本论文研究的主要内容。 7 第二章w e b 信息检索技术概述 2 1 搜索引擎工作原理 自从第一个w e b 搜索引擎w w w w ( w o r l dw i d ew e bw o r m ) 在c o l o r a d o 大学开 发成功以来，w e b 上的搜索引擎已发展到上千个。w e b 信息检索系统一般是两层的 c s ( c l i e n t s e r v e r ) 模式。虽然各个搜索引擎的具体实现不太相同，但一般包含五个基 本部分：r o b o t 、分析器、索引器、检索器和用户接口，服务器端主要包括r o b o t 、分 析器、索引器、检索器和索引数据库。其系统结构如图2 1 所示。 一r n h n t l l 一一 用每1 吣 用 检 士竺固一 索 分e 竺八葡 户 索 引 一 析 l 页面圹 接 器 器 器 叫塑竺r 耐 口 寿占挫眼复婴泄 图2 1 搜索引擎系统结构 2 1 1r o b o t r o b o t 采用广度优先( 或深度优先) 的策略，对w e b 进行遍历并下载文档，系统 中维护一个超链接队列( 或者堆栈) ，其中包括一些起始u r l 。r o b o t 从这些u r l 出 发，下载相应的页面，并从中抽取出新的超链接加入队列( 或者堆栈) 中。上述过程 不断重复直到队列( 或堆栈) 为空。 这些起始u r l 可以是任意的u r l ，但常常是一些非常流行、包含很多超链接的 站点( 如y a h o o ) 。为了提高效率，搜索引擎中可能会有多个r o b o t 进程同时遍历不同 的w e b 子空间。将w e b 空间按照域名、i p 地址或国家域名划分，每个搜索器负责一 个子空间的穷尽搜索。 r o b o t 搜集的信息类型多种多样，包括h t m l 、x m l 、n e w s g r o u p 文章、f t p 文件、 字处理文档、多媒体信息等。 r o b o t 的实现常常用分布式、并行计算技术，以提高信息发现和更新的速度。商 业搜索引擎的信息发现可以达到每天几百万网页。 目前，大多数r o b o t 不能够访问基于框架的w e b 页面、需要访问权限的w e b 页 面以及动态生成w e b 页面( 页面本身并不存在w e b 服务器上，而是由服务器根据用 户提交的h t m l 表单生成的页面) 。 8 2 1 2 分析器 分析器对r o b o t 下载的文档进行分析提供给索引器使用。文档分析技术一般包括： 分词、过滤和转换等，这些技术往往与具体的语言以及系统的索引模型密切相关。在 分词时，大部分系统从全文中抽取词条，而有些系统仅从文档的某些部分( 例如t i t l e ， h e a d e r 等) 中抽取。词条的类型也多种，包括字、词或者短语等。这些工作主要包括 英文文档的s t e m m i n g 处理和中文文档的词条切分。其中s t e m m i n g 处理是指从英文单 词的多种形式中提取出其基本词干的过程。英文单词在具体使用时，可以有现在时、 过去时等多种形式，还有的单词，有名词、形容词、副词等多种形式，但它们的词干 是相同的，因此在进行词频统计时应该作为相同的词处理，一般实现的方法是建立单 词前缀、后缀和特殊形式表，用匹配方式实现；中文同英文不同，句子中各词条间没 有固有的分隔符( 空格) ，进行中文文档的词频统计前，首先需要对中文文档进行分 词处理，中文文本的分词就是在中文文本的各词条间加入分隔符，将中文文本连续的 字流形式转化为离散的词流形式。中文文本的分词方法有很多，各种方法适用的情况 也不同，网络信息挖掘对分词处理要求有较高的实时性，但对分词的准确度不太敏感， 容许一定的分词错误率，因此可以采用较为简单的基于词典的正向匹配、逐词遍历分 词方法。 分词处理后通常要使用禁用词表( s t o pl i s t ) 来过滤掉如“a ，“t h e ，“a n d 或 中文中的“的”、“地 、“得 、“和”等虽然出现的频率都很高，但没有索引价值的虚 词，并且这些词也要从查询请求过滤掉。 2 1 3 索引器 索引器将文档表示为一种便于检索的方法并存储在索引数据库中。索引的质量是 w e b 信息检索系统成功的关键因素之一。一个好的索引模型应该易于实现和维护，检 索速度快，空间需求低。搜索引擎普遍借鉴了传统信息检索中的索引模型，包括倒排 文档、矢量空间模型、概率模型等。 索引器的功能是理解r o b o t 所搜索的信息，从中抽取出索引项，用于表示文档以 及生成文档库的索引表。 索引项有客观索引项和内容索引项两种。客观索引项与文档的语义内容无关，如 作者名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等等；内容索 引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可以 分为单索引项和多索引项( 或称短语索引项) 两种。单索引项对于英文来讲是英语单 词，比较容易提取，因为单词之间有天然的分隔符( 空格) ；对于中文等连续书写的 语言，必须进行词语的切分。在搜索引擎中，一般要给单索引项赋一个权值，以表示 该索引项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计 9 法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。 索引数据库一般使用某种形式的倒排表( i n v e r s i o n l i s t ) 。倒排索引是一种索引结 构，它包含两个索引表：文档表和词表。文档表由一组文档记录组成，词表由一组词 记录组成。通过这种组织，可以很容易地回答类似查询“找出与给定词集相关的所有 文档”，或“找出与指定文档相关的所有的词 等。文档的全文索引用文档中的经过 分析器处理后的每个词作为关键词。 由索引项查找相应的文档，索引表也可能要记录索引项在文档中出现的位置，以 便检索器计算索引项之间的相邻或接近关系( p r o x i m i t y ) 。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现 即时索引( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息量急剧增加的速度。索引算法对索 引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。 2 1 4 检索器 检索器从索引数据库中找出与用户查询请求相关的文档。首先采用与分析、索引 文档相似的方法来处理用户查询请求。 检索器一般有两种检索方法： ( 1 ) 基于关键字的检索。在基于关键字的信息检索系统中，文档被看成字符串， 可用一组关键字加以识别。用户提供一个关键字或一组由关键字构成的表达式，由关 键字进行查询。这样，用户可以找出包含关键字的全部文档。 在基于关键字的信息检索系统中，还要考虑“同义词”问题。可以采用同义词的 方法解决这个问题，对每个词都定义一些同义词。 基于关键字的信息检索系统还有一个难题，就是“多义词 问题，即同一个关键 字，在不同的上下文中可能有不同的含义。遗憾的是，目前这种基于上下文确定关键 字含义的检索系统还不成熟。 ( 2 ) 基于内容相似性的检索。某些信息检索系统允许基于相似性的检索。这时， 用户可给系统一个文档a ，然后要求系统找出与a “相似 的文档。两个文档的相似 性可以自定义，如根据一组共同的关键词作为相似性。然后按照某种方法来计算用户 查询与索引数据库中每个文档之间的相关度。此类检索的输出应当基于相关度，其中 相关度的度量是根据关键词的近似性、关键词的出现频率等。如果与a 相似的文档非 常多，系统可以只给用户其中几个，并且允许用户从中选择最相关的那些文档，然后 根据选出的文档和文档a 的相似性开始一个新的检索。最后，将相关度大于阈值的所 有文档按照相关度递减的顺序排列，并返回用户。然而，搜索引擎的相关度判断并不 一定与用户的需求完全相等。 检索器使用的算法主要有布尔模型、矢量空间模型、概率模型等。 1 0 2 。1 5 用户接口 用户接口为用户提供可视化的查询输入和结果输出界面。在查询输入界面中，用 户按照搜索引擎的查询语法指定待检索词条及各种简单或高级检索条件。在输出界面 中，搜索引擎将检索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要 和超链等信息。由于检索结果中相关文档和不相关文档相互混杂，用户需要逐个浏览 以找出所需文档。 w e b 信息是动态变化的，旧的页面不断被更新( 内容改变、位置移动等) 和删除， 新的页面不断出现。因此，r o b o t 、分析器和索引器模块每隔一定时间要重复运行以 更新索引数据库。搜索引擎的索引更新周期通常为几周或几个月，索引数据库越大， 更新也越困难。 2 2 搜索引擎检索效果主要性能指标 衡量信息检索系统检索效果的主要指标有两个，分别是查全率( r e c a l l ) 和查准率 ( p r e c i s i o n ) 。在对传统的信息获取系统进行评测时，通常是预先选定一个文档集合( 比 如经常使用的t e x tr e t r i e v a lc o n f e r e n c e 评测文档集1 8 1 ) 和一个检索条件集，这个文档 集中的文档和这些检索条件之间的相关情况是己知的，然后使用信息检索系统根据这 些检索条件对文档集中的文档进行检索，根据检索结果的情况来分析该系统的检索效 率。 ( 1 ) 查全率 查全率是指信息检索系统检索到的相关文档占被检索文档集中所有相关文档的 比重，可以用下面的公式计算：i k c a l l = p r a i i 。其中r 是搜索到的相关文档数，鼬i 是 被检索文档集中所有的相关文档数量。一个系统的查全率越高，则说明它发现相关文 档的能力越强。 ( 2 ) 查准率 查准率是指信息检索系统检索到的所有文档中相关文档所占的比率，可以用如下 公式计算：r p 僦i s i o 。= 如。其中r 是搜索到的相关文档数，d 是检索到的文档数。一 个系统的准确率越高，则其检索到的信息噪声越低。 2 3 向量空间模型v s m 在搜索引擎中，最主要采用的一种技术是向量空间模型，每个文档和用户查询分 别被表示为一个范化矢量，然后按照某种方法来计算用户查询与索引数据库中每个文 档之间的相关度，最后按相关度的大小输出。 ( 1 ) 文档d ( d o c u m e n t ) 文档泛指文档或文档中的一个片段( 如文档中的标题、摘要、正文等) 。 ( 2 ) 特征项t ( t e r m ) 特征项是指出现在文档中能够代表文档性质的基本语言单位( 如字、词等) ，也 就是通常所指的检索词，这样一个文档d 可以表示为d ( t 1 ，t 2 ，t n ) ，其中n 代表特征项的数目。 ( 3 ) 特征项权重w k ( t e r mw e i g h t ) 特征项权重指特征项t n 能够代表文档d 能力的大小，体现了特征项在文档中的重 要程度。这样文档d 的向量可以表示为d ( w l ，w 2 ，w n ) ，其中w l ，w 2 ，w n 分别代表文档d 特征项t l ，t 2 ，t i l 的特征项权重。 页面关键词t i 在文档d 中的权重w i 有多种计算方法，最常用的有布尔值、词频 和t f i d f 三种方法。现分别描述如下： 布尔值算法 就是以单词t i 在文档d 中的出现或不出现作为其权重w i ，即若单词t i 在文档d 中出现，则w i = l ，否则w j = o 。 词频算法( t e r