（计算机软件与理论专业论文）基于聚类的个性化搜索引擎研究与设计.pdf

摘要 近年来随着w e b 的迅猛发展，i n t e m e t 上存在大量的信息资源，如何从中快速准确 的获取有价值的信息一直以来是一个迫切需要解决的问题。 本文介绍了搜索引擎的发展史及相关技术，并对个性化的元搜索引擎技术进行了 深入探讨。在传统搜索引擎的基础上，采用基于关键短语的聚类技术，对用户的搜索 结果进行聚类，同时跟踪用户浏览行为，结合用户信息分析模块，通过反复训练，分 析用户对那类信息感兴趣，并提取出用户兴趣爱好特征项，从而在聚类及用户的搜索 结果排序中起到指导作用。文中分析了个性化元搜索引擎的系统构成，并设计了一个 元搜索引擎系统c p s ，详细介绍了每个模块的功能，同时讨论了在个性化元搜索引擎技 术中建立用户兴趣模型的方法，最后展望了它的发展前景。 关键词：关键短语聚类算法个性化模块 元搜索引擎 a b s t r a c t a tp r e s e n t ，w i t ht h er a p i dd e v e l o p m e n to fw e b ，t h e r ea r eal o to fi n t e r n e ti n f o r m a t i o n r e s o u r c e s ，h o wf a s ta n da c c u r a t ea c c e s st ov a l u a b l ei n f o r m a t i o nh a sa l w a y sb e e nap r e s s i n g n e e dt ob ea d d r e s s e d t h i sa r t i c l ed e s c r i b e st h eh i s t o r yo ft h ed e v e l o p m e n to fs e a r c he n 西n e sa n dr e l a t e d t e c h n o l o g i e s ，a n df o rp e r s o n a l i z e dm e t as e a r c he n g i n et e c h n o l o g yf o ri n d e p t hd i s c u s s i o n s t h r o u g hb a s e do nt h ek e yp h r a s eo ft h ec l u s t e r i n gt e c h n o l o g yt ot h eu s e r ss e a r c hr e s u l t s c l u s t e r i n g ，a tt h es a m et i m e ，t ot r a c k u s e rb r o w s i n gb e h a v i o r , c o m b i n e dw i t hu s e r i n f o r m a t i o na n a l y s i sm o d u l e ，r e p e a t e d l y , t h r o u g ht r a i n i n g ，a n a l y s i so ft h eu s e r si n t e r e s t e di n t h ek i n do fi n f o r m a t i o na n de x t r a c tt h ec h a r a c t e r i s t i c so ft h eu s e ri n t e r e s t s ，i no r d e rt oc l u s t e r a n dt h eu s e r ss e a r c hr e s u l t si no r d e rt op l a yt h eg u i d i n gr o l e o nt h eb a s i so ft h et r a d i t i o n a l s e a r c he n g i n e t h ea r t i c l ea n a l y z e dt h ep e r s o n a l i z e dm e t a - s e a r c he n g i n ec o n s t i t u t e sas y s t e m ， a n dd e s i g n e dam e t as e a r c he n g i n ec p ss y s t e m ，d e t a i l so ft h ef u n c t i o n so fe a c hm o d u l e ，a t t h es a m et i m ed i s c u s s e dt h ep e r s o n a l i z e dm e t as e a r c he n g i n et e c h n o l o g yt oc r e a t eu s e r i n t e r e s ti nt h em o d e l t h el a s to fi t so u t l o o kf o rd e v e l o p m e n t k e yw o r d s ：k e yp h r a s e m e t as e a r c he n g i n e c l u s t e r i n ga l g o r i t h m p e r s o n a l i z e dm o d u l e l i 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，基于聚类的个性化搜索引擎研究与 设计是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经 注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 作者签名：奎亟! ! ! 童年旦月旦r 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权 使用规定”，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学 位论文全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文 的复印件和电子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复 制手段保存和汇编学位论文。 作者签名： 銮巫兰! ! ! 年盟月且日 指导导师签名：年卫月旦日 4 1 第一章绪论 1 1 研究背景 1 1 1 互联网搜索引擎发展与现状 1 9 9 0 年，加拿大麦吉尔大学( u n i v e r s i t yo f m c g i l l ) 计算机学院的师生开发出 a r c h i e 。当时，万维网( w o r l dw i d ew 曲) 还没有出现，人们通过f 1 p 来共享交流资源。 a r c h i e 能定期搜集并分析f 1 甲服务器上的文件名信息，提供查找分别在各个f 限主机 中的文件。用户必须输入精确的文件名进行搜索，a r c h i e 告诉用户哪个f t p 服务器能 下载该文件。虽然a r c h i e 搜集的信息资源不是网页( h t m l 文件) ，但和搜索引擎的基 本工作方式是一样的：自动搜集信息资源、建立索引、提供检索服务。所以，a r c h i e 被公认为现代搜索引擎的鼻祖。 1 9 9 3 年m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r ，这是第一个利用h t m l 网 页之间的链接关系来检测万维网规模的“机器人( r o b o t ) ”程序1 1 1 。开始，它仅仅用 来统计互联网上的服务器数量，后来也能够捕获网址( u r l ) 。 1 9 9 4 年4 月，斯坦福大学( s t a n f o r du n i v e r s i t y ) 的两名博士生，美籍华人j e r r y y a n g ( 杨致远) 和d a v i df i l o 共同创办了y a h o o 。随着访问量和收录链接数的增长，y a h o o 目录开始支持简单的数据库搜索。因为y a h o o ! 的数据是手工输入的，所以不能真正被 归为搜索引擎，事实上只是一个可搜索的目录。 1 9 9 4 年初，华盛顿大学( u n i v e r s i t yo fw a s h i n g t o n ) 的学生b r i a np i n k e r t o n 开始 了他的小项目w e bc r a w l e r 。1 9 9 4 年4 月2 0 日，w e bc r a w l e r 正式亮相时仅包含来自 6 0 0 0 个服务器的内容。w e b c r a w l e r 是互联网上第一个支持搜索文件全部文字的全文搜 索引擎，在它之前，用户只能通过u r l 和摘要搜索，摘要一般来自人工评论或程序自 动取正文的前1 0 0 个字。 1 9 9 4 年7 月，卡内基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 的m i c h a e lm a u l d i n 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，创建了l y c o s 。除了相关性排序外， l y c o s 还提供了前缀匹配和字符相近限制，l y c o s 第一个在搜索结果中使用了网页自动 摘要，而最大的优势还是它远胜过其它搜索引擎的数据量。 1 9 9 5 年，一种新的搜索引擎形式出现了元搜索引擎 ( a m e t as e a r c he n g i n er o u n d u p ) 。用户只需提交一次搜索请求，由元搜索引擎负责转 换处理，提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回的所有查 询结果，集中起来处理后再返回给用户1 2 1 。 1 9 9 5 年1 2 月，d e c 的正式发布a l t a v i s t a 。a l t a v i s t a 是第一个支持自然语言搜索 的搜索引擎，第一个实现高级搜索语法的搜索引擎( 如a n d ，o r ，n o t 等) 。用户可 以用a l t a v i s t a 搜索新闻组( n e w s g r o u p s ) 的内容并从互联网上获得文章，还可以搜索 图片名称中的文字、搜索t i t l e s 、搜索j a v aa p p l e t s 、搜索a c t i v e xo b j e c t s 。a l t a v i s t a 也 2 声称是第一。个支持用户自己向网页索引片提交或删除u r l 的搜索引擎，并能在2 4 小 时内上线。a l t a v i s t a 最有趣的新功能之一，是搜索有链接指向某个u r l 的所有网站。 在面向用户的界面上，a l t a v i s t a 也作了大量革新。它在搜索框区域下放了“t i p s ”以帮 助用户更好的表达搜索式，这些小t j p 经常更新，这样，在搜索过几次以后，用户会看 到很多他们可能从来不知道的的有趣功能。这系列功能，逐渐被其它搜索引擎广泛采 用。1 9 9 7 年，a l t a v i s t a 发布了一个图形演示系统l i v e t o p i c s ，帮助用户从成千上万的 搜索结果中找到想要的。 1 9 9 7 年8 月，n o r t h e m l i g h t 搜索引擎正式现身。它曾是拥有最大数据库的搜索引 擎之一，它没有s t o pw o r d s ，它有出色的c u r r e n tn e w s 、7 ，1 0 0 多出版物组成的 s p e c i a lc o l l e c t i o n 、良好的高级搜索语法，第一个支持对搜索结果进行简单的自动分类。 1 9 9 8 年1 0 月之前，g o o g l e 只是斯坦福大学( s t a n f o r du n i v e r s i t y ) 的一个小项目 b a c k r u b 。1 9 9 5 年博士生l a r r yp a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月1 5 日注 册了g o o g l e c o m 的域名，1 9 9 7 年底，在s e r g e yb r i n 和s c o t t h a s s a n 、a l a ns t e r e m b e r g 的共同参与下，b a c h r u b 开始提供d e m o 。1 9 9 9 年2 月，g o o g l e 完成了从a l p h a 版到 b e t a 版的蜕变。g o o g l e 公司则把1 9 9 8 年9 月2 7 日认作自己的生日。g o o g l e 以网页级 别( p a g e r a n k ) 为基础，判断网页的重要性，使得搜索结果的相关性大大增强b 。 2 0 0 0 年1 月，两位北大校友，超链分析专利发明人、前i n f o s e e k 资深工程师李彦 宏与好友徐勇( 加州伯克利分校博士后) 在北京中关村创立了百度( b a i d u ) 公司。2 0 0 1 年8 月发布b a i d u c o m 搜索引擎b e t a 版( 此前b a i d u 只为其它门户网站搜狐新浪t o m 等提供搜索引擎) ，2 0 0 1 年1 0 月2 2 日正式发布b a i d u 搜索引擎，专注于中文搜索。 1 9 9 4 年左右，万维网( w o r l dw i d ew e b ，简记为w w w 或w e b ) 出现。它的开放 性( o p e n n e s s ) 和其上信息广泛的可访问性( a c c e s s i b i l i t y ) 极大地鼓励了人们创作的积 极性。万维网具有规模大，内容不稳定的特点。我国互联网在近1 0 多年罩取得了长足 的发展。据c n n i c 统计，1 9 9 7 1 0 3 1 我国网民数为6 3 万。截至2 0 0 8 年6 月底，我 国网民数量达到了2 5 3 亿，首次大幅度超过美国，跃居世界第一位。统计表明，中国 网站数量持续增长，共有1 9 1 9 万个，年增长率为4 6 3 ；随着网站的增多，内容的丰 富，人们上网查阅资料已经不在拘泥于几家门户类网站的浏览，方便快捷的找到想要 查找的信息变的越发的重要，因特网的迅猛发展、w e b 信息的增加，用户要在信息海 洋里查找信息，就像大海捞针一样，搜索引擎技术恰好解决了这一难题，它可以为用 户提供信息检索服务。面对如此海量的数据和如此异构的信息，用户要在里面寻找信 息，必然会“大海捞针”无功而返。搜索引擎正是为了解决这个“迷航”问题而出现 的技术。搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、 组织和处理，并为用户提供检索服务，从而起到信息导航的目的。其方便快捷全面的 信息查找功能使其很快得到众多网民的青睐，并迅速的发展起来。如今搜索引擎已经 变成最大的网络媒体，现在，搜索引擎对网络的影响同益增强，其占报纸、杂志和电 视新闻网站搜索流量的3 0 。，随着中国互联网发展的同趋成熟，以及计算机的普及， 人民对搜索引擎的依赖越来越强，尤其足在当今网络资源丰富，网络需求量的年代， 搜索技术尤为关键。由于互联网已经成为人们学习工作和生活中小可缺少的平台，几 乎每一个上网的人都会使用搜索引擎，搜索引擎实际上就是在用户和互联网资源这两 者之间建立起一个联系，将用户真正想要的内容呈现给用户，同时用户不想要的内容 不呈现给用户。随着网民的网络行为同益个性化和生活化，下一代搜索引擎的发展趋 势必将是智能化的、个性化的。 1 1 2 搜索引擎未来动向 搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、 计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域 的理论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用户，有很好的 经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究、 开发十分活跃，并出现了很多值得注意的动向。 ( 1 ) 提高信息查询结果的精度，提高检索的有效性。用户在搜索引擎上进行信息 查询时，并不十分关注返回结果的多少，而是看结果是否和自己的需求吻合。对于一 个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在结果中筛选“1 。 解决查询结果过多的现象目前出现了几种方法：一是通过各种方法获得用户没有在查 询语句中表达出来的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型； 使用相关度反馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关( 及其相关的 程度) ，哪些不相关，通过多次交互逐步求精。二是用正文分类( t e x tc a t e g o r i z a t i o n ) 技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。 三是进行站点类聚或内容类聚，减少信息的总量。 ( 2 ) 基于智能代理的信息过滤和个性化服务。信息智能代理是另外一种利用互联 网信息的机制。它使用自动获得的领域模型( 如w e b 知识、信息处理、与用户兴趣相 关的信息资源、领域组织结构) 、用户模型( 如用户背景、兴趣、行为、风格) 知识进 行信息搜集、索引、过滤( 包括兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、 对用户有用的信息提交给用户。智能代理具有不断学习、适应信息和用户兴趣动态变 化的能力，从而提供个性化的服务。智能代理可以在用户端进行，也可以在服务器端 运行吲。 ( 3 ) 采用分布式体系结构提高系统规模和性能。搜索引擎的实现可以采用集中式 体系结构和分布式体系结构，两种方法各有千秋。但当系统规模到达一定程度( 如网 页数达到亿级) 时，必然要采用某种分布式方法，以提高系统性能。搜索引擎的各个 组成部分，除了用户接口之外，都可以进行分布：搜索器可以在多台机器上相互合作、 相互分工进行信息发现，以提高信息发现和更新速度；索引器可以将索引分布在不同 的机器上，以减小索引对机器的要求；检索器可以在不同的机器上进行文档的并行检 索，以提高检索的速度和性能。 ( 4 ) 重视交叉语言检索的研究和丌发。交叉语言信息检索是指用户用母语提交查 4 询，搜索引擎在多种语言的数据库中进行信息检索，返回能够回答用户问题的所有语 言的文档。如果再加上机器翻译，返回结果可以用母语显示。该技术目前还处于初步 研究阶段，主要的困难在于语言之间在表达方式和语义对应上的不确定性。但对于经 济全球化、互联网跨越国界的今天，无疑具有很重要的意义。 ( 5 ) 社会化搜索引擎的研究和开发。社会化搜索是随着最近几年来的w e b 2 0 概 念发展起来的搜索技术，目前还没有一个比较统一的定义。它的最简单的定义就是基 于人的搜索，其目的是通过搜索引擎的众多用户的集体智慧获取和改善搜索结果6 1 。 用户对网络的信息体验是从分类检索体验开始的，第一代搜索引擎呈现给用户的 是“千人一面 的分类体系和网页内容。人们在经过了初始短暂的兴奋后，很快就对 这样的信息访问方式不满意了。第二代的搜索引擎是以关键字作为表达查询的主要手 段的，以按相关度大小排列的文献列表为展示方式。为了克服千人一面的不足，人们 还引进了一些个性化的技术，包括对查询输入的修正，查询结果的聚类等。但是，到 目前为止，查询输入的主要方式还是关键字，查询输出的主要也还是文本列表。如何 为用户的学习和工作营造一个个性化的信息空间，是未来搜索引擎应该追求的方向， 这里包括如何表达信息需求，如何展示、浏览搜索结构，如何对个性化的信息需求建 立模型等等。从这种意义上讲，下一代搜索引擎将是个性化的。 1 2 研究目的与重要意义 w w w 应用的快速发展，使之已经成为一个巨大的海量信息空间，其间的信息种 类也伴随着应用领域的拓展而更加丰富。w w w 上每天都有新页面的产生，现有的页 面在不停地被更新，页面与页面之间的联系也趋于紧密和复杂。面对如此庞杂的信息 资源，如果仅仅采用浏览器，获取有价值的信息是困难和低效的。搜索引擎以一定的 策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提 供检索服务，从而起到信息导航的目的。w e b 搜索引擎的出现，为人们从w w w 获取 信息发挥了重要的作用，但是，随着信息量的急剧增加和基于w w w 的新的应用模式 的出现，现有的w e b 搜索引擎也面临着新的挑战。个性化服务通过收集和分析用户信 息来学习用户的兴趣和行为，从而实现主动推荐的目的个性化服务技术能充分提高站 点的服务质量和访问效率，从而吸引更多的访问者。本文所提出的基于聚类的个性化搜 索模型可以在很大程度上提高用户搜索的精度，更准确、更快速的提供用户想要查找 的信息，增强了用户的搜索体验。 1 3 课题研究的主要内容 ( 1 ) 对现有聚类，分类算法的研究及其相关指标体系确定。从对现有的主要聚类， 分类算法的分析和研究入手，系统综合地分析影响搜索结果精度的各相关因素及其优 缺点，分析现有的聚类，分类算法。并研究其结合个人信息的模型及方法。 ( 2 ) 基于关键短语的聚类算法和模型设计。通过对用户个人信息的分析结合现有 5 的聚类算法提出一种改进的聚类算法，构建基于关键短语的聚类算法和模型，对算法和 模型进行自学习和训练，使模型适合实际情况。 ( 3 ) 对改进后的搜索引擎系统进行实证研究。以一定数量的搜索结果为基础，对 比其他相关算法，对改进后的搜索引擎系统进行实证对比研究。 ( 4 ) 提出一种用户兴趣模型的建立方法。通过用户兴趣模型的建立更好的实现搜 搜引擎的个性化，方便用户快速、准确的查找。同时用户兴趣模型的建立也为聚类算 法提供了很好的参考依据，作为聚类算法的重要参考指标，用户兴趣模型的建立使聚 类算法的结果更加精确。本文的用户兴趣模型更新算法在原有算法的基础上还采用结 合聚类结果进行分析的方法，使用户兴趣模型的更新更加准确。 1 4 本章小结 本章主要介绍了搜索引擎的发展历史和未来发展趋势，并对本论文的研究目的， 意义和内容做了整体的概述。 6 第二章w e b 搜索引擎的介绍及基本原理和相关技术 2 1 搜索引擎的分类 目前，搜索引擎技术按信息标引的方式可以分为目录式搜索引擎、机器人搜索引 擎和混合式搜索引擎；按查询方式可分为浏览式搜索引擎、关键词搜索引擎、全文搜 索引擎、智能搜索引擎；按语种又分为单语种搜索引擎、多语种搜索引擎和跨语言搜 索引擎等。 2 1 1 目录式搜索引擎 目录式搜索引擎( d i r e c t o r ys e a r c he n g i n e ) 是最早出现的基于w w w 的搜索引擎， 以雅虎为代表，我国的搜狐也属于目录式搜索引擎。 目录式搜索引擎由分类专家将网络信息按照主题分成若干个大类，每个大类再分为 若干个小类，依次细分，形成了一个可浏览式等级主题索引式搜索引擎，一般的搜索 引擎分类体系有五六层，有的甚至十几层。 目录式搜索引擎主要通过人工发现信息，依靠编目员的知识进行甄别和分类。由于 目录式搜索引擎的信息分类和信息搜集有人的参与，因此其搜索的准确度是相当高的， 但由于人工信息搜集速度较慢，不能及时地对网上信息进行实际监控，其查全率并不 是很好，是一种网站级搜索引擎。 2 1 2 机器人搜索引擎 机器人搜索引擎通常有三大模块：信息采集、信息处理、信息查询。信息采集一 般指爬行器或网络蜘蛛，是通过一个u r l 列表进行网页的自动分析与采集。起初的u r l 并不多，随着信息采集量的增加，也就是分析到网页有新的链接，就会把新的u r l 添 加到u r l 列表，以便采集8 1 。 机器人搜索引擎使用多线程并发搜索技术，主要完成文档访问代理、路径选择引 擎和访问控制引擎。基于机器人搜索引擎的w e b 页搜索模块主要由u r l 服务器、爬行 器、存储器、u r l 解析器四大功能部件和资源库、锚库、链接库三大数据资源构成， 另外还要借助标引器的一个辅助功能。 具体过程是，u r l 服务器发送要去抓取的u r l ，爬行器根据u r l 抓取w e b 页并 送给存储器，存储器压缩w e b 页并存入数据资源库，然后由标引器分析每个w e b 页 的所有链接并把相关的重要信息存储在锚库文件中。u r l 解析器读锚库文件并解析 u r l ，然后依次转成d o c l d 。再把锚库中文本变成顺排索引，送入索引库。 2 1 3 元搜索引擎 元搜索引擎，也叫集搜索引擎，是指在统一的的用户查询界面与信息反馈的形式 下，共享多个搜索引擎的资源库为用户提供信息服务的系统。元搜索引擎是对搜索引 擎进行搜索的搜索引擎阳- 。 元搜索与一般搜索引擎的最大不同在于它可以没有自己的资源库和机器人，它充 7 当一个中间代理的角色，接受用户的查询请求，将请求翻译成相应搜索引擎的查询语 法。在向各个搜索引擎发送查询请求并获得反馈之后，首先进行综合相关度排序，然 后将整理抽取之后的查询结果返回给用户。元搜索引擎查全率高、搜索范围更多更大， 查准率也并不低。 元搜索引擎包括w e b 服务器、结果数据库、检索式处理、w e b 处理接口、结果生 成等几个部分，其中用户通过w e b 服务器访问元搜索引擎，而元搜索引擎则通过w e b 处理接口访问其它外部的搜索引擎。其系统结构如下图2 1 所示。 图2 1元搜索引擎系统结构图 用户通过w w w 服务访问元搜索引擎，向w e b 服务器提交检索式。当w e b 服务 器收到查询请求时，先访问结果数据库，查看近期是否有相同的检索，如果有则直接 返回保存的结果，完成查询；如果没有相同的检索，就分析检索式并转化成与所要查 找各搜索引擎相应的检索式格式，然后送至w e b 处理接口模块。 w e b 处理接口通过并行的方式同时查询多个搜索引擎，把所有的结果集中到一起。 根据各搜索引擎的重要性，以及所得结果的相关度，对结果进行抽取并排序，生成最 终结果返回给用户。同时，把结果存到自己的数据库里，以备下次查询参考使用。 2 1 4 跨语言搜索引擎 跨语言综合搜索引擎是在一般的搜索引擎基础上加了两个功能：不同语言提问之 间的翻译和不同搜索引擎检索结果的集成。跨语言搜索引擎有两种情况，一种是架构 在单一搜索引擎的基础上，另一种是架构在多搜索引擎的基础上。 目前研究最多的是跨语言文本检索和跨语言语音检索。跨语言检索主要涉及信息 检索和机器翻译两个领域的知识，但又不是这两种技术的简单融合。跨语言检索系统 的检索功能，可以利用现有的检索系统来实现，也可以重新构造新的检索系统或检索 功能模块来实现。 8 跨语言搜索引擎的工作过程如下：用户向系统提交检索词，形成一个源语言的搜 索式，系统对搜索式进行语言识别，识别出语种后，就对进行提问式的词法分析和结 构分析，然后把这个分析过的搜索式翻译成各种语言的搜索式，最后把这一系列的搜 索式提交给系统进行检索就可以了。 检索结果是含有多个语种的页面。如果使用多搜索引擎，转换成不同语言搜索式 时还需要注意各种搜索引擎搜索式表达方法的不同。例如，新浪网搜索中文信息的结 果比较好，那么就把提问词是中文的搜索式转换成新浪网的搜索式；雅虎对英文信息 的搜索结果比较好，那么就向雅虎提交提问词是英文的搜索式。 关于多语种搜索有这样几种情况：检索词为不同语种，检索结果也不同，这种情 况是不经过翻译的i 对搜索引擎来讲是不区分的。比如在g o o g l e 里输入“知识发现 k n o w l e d g e ，选择所有语种，那么只要网页罩既有“知识发现”又有“k n o w l e d g e 就 可以检索出来，不管该页面是中文的，还是英文或者是日文的，搜索引擎并不识别检 索词的语种，这不是真正的跨语言搜索引擎。第二种情况是，检索词为同一语种，检 索结果为不同语种。 2 2 检索结果深加工 用户在使用搜索引擎进行信息搜索时，有时并不十分关注返回结果的多少，而是 看检索结果是符合自己的需求。对于一次普通查询，传统的搜索引擎动辄几十万、几 百万篇文档，这样的搜索结果是没有多大意义的。 解决检索结果过多过杂的问题，目前有多种方法t l o l 。一是通过各种方法获得用户 没有在检索式表达出来的真正目的，包括智能代理跟踪用户检索行为，分析用户操作 模型，使用相关反馈机制，确定文档和用户需求的相关性，提高检索的精度。二是用 文本分类技术，将结果分类，使用可视化技术显示分类结构，用户只浏览自己感兴趣 的类别。三是进行站点聚类或内容聚类，减少信息的总量，从而有利于从大量返回结 果中找到用户所需要的信息。 2 2 1 提供个性化服务 为了实现个性化服务，需要获取用户兴趣信息。获取用户的兴趣信息，有两种方 法。在训练阶段，用信息论的观点对关键词分类并表示其特征程度( 关键词按贡献率 分为积极特征词、消极特征词和零特征词) ，然后定义标题的特征程度，并对各类特征 词进行统计。 在测试阶段，应用兴趣描述文件( 通常以x m l 文件格式存储) ，动态获取用户的 兴趣从而把用户感兴趣的页面提供给用户。这种方法避免了用户描述兴趣的困难。用 户很难描述兴趣，但可以判断一篇文章是否符合需要。 另一种方法是可以根据用户的书签文件以及每次检索输入的关键词、用户的反映 来动态更新用户的兴趣。通过分析用户行为的意图，获取用户感兴趣的相关信息及感 兴趣的感性程度。另外，用户输入的关键词也作为积极特征词来动态更新用户兴趣文 9 件。 2 2 2 基于智畿搜索 搜索引擎的智能化方向发展是毫无疑问的。智能搜索引擎( s m a r t h u n t e r ) 是根据 目前搜索引擎的发展趋势，除提供传统的全网快速检索、相关度排序等功能外，还提 供用户角色登记、用户兴趣自动识别、内容的语义理解、智能化信息过滤和推送等功 能，为用户提供一个真正个性化、智能化的网络信息搜集工具。如下图2 2 所示。 智能搜索引擎利用神经网络、决策树、关联规则、范例推理、模糊聚类、粗糙集、 隐马尔科夫模型等技术实现分布式并行检索，以数据挖掘与知识发现为主要手段，加 上自然语言理解技术，对检索结果进行进一步的分析，滤掉与用户需求不相关或弱相 关的信息，从而提高系统性能和检索的精度与效果。 2 3 全文搜索的工作原理 全文搜索引擎的“网络机器人 或“网络蜘蛛”是一种网络上的软件，它遍历 w 曲空间，能够扫描一定i p 地址范围内的网站，并沿着网络上的链接从一个网页到另 一个网页，从一个网站到另一个网站采集网页资料n 。它为保证采集的资料最新，还 会回访已抓取过的网页。网络机器人或网络蜘蛛采集的网页，还要有其它程序进行分 析，根据一定的相关度算法进行大量的计算建立网页索引，才能添加到索引数据库中。 我们平时看到的全文搜索引擎，实际上只是一个搜索引擎系统的检索界面，当你输入 关键词进行查询时，搜索引擎会从庞大的数据库中找到符合该关键词的所有相关网页 的索引，并按一定的排名规则呈现给我们。不同的搜索引擎，网页索引数据库不同， 排名规则也不尽相同，所以，当我们以同一关键词用不同的搜索引擎查询时，搜索结 果也就不尽相同。 1 0 搜索引擎并不真正搜索互联网，它搜索的实际上是预先整理好的网页索引数据库。 真正意义上的搜索引擎，通常指的是收集了因特网上几千万到几十亿个网页并对例页 中的每一个词( 即关键词) 进行索引，建立索引数据库的全文搜索引擎。当用户查找 某个关键词的时候，所有在页面内容巾包含了该关键词的网页都将作为搜索结果被搜 出来。在经过复杂的算法进行排序后，这些结果将按照与搜索关键词的相关度高低， 依次排列。 现在的搜索引擎己普遍使用超链分析技术，除了分析索引网页本身的内容，还分 析索引所有指向该网页的链接的u r l 、a n c h o r t e x t 、甚至链接周围的文字。所以，有 时候，即使某个网页a 中并没有某个词比如“恶魔撒旦，但如果有别的网页b 用链 接“恶魔撒旦”指向这个网页a ，那么用户搜索“恶魔撒旦 时也能找到网页a 。而 且，如果有越多网页( c 、d 、e 、f ) 用名为“恶魔撒旦 的链接指向这个网页a ， 或者给出这个链接的源网页( b 、c 、d 、e 、f ) 越优秀，那么网页a 在用户搜索 “恶魔撒旦”时也会被认为更相关，排序也会越靠前。 搜索引擎的原理，可以看做三步：从互联网上抓取网页一建立索引数据库_ 在索 引数据库中搜索排序。 ( 1 ) 从互联网上抓取网页。利用能够从互联网上自动收集网页的s p i d e r 系统程序， 自动访问互联网，并沿着任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬 过的所有网页收集回来。 ( 2 ) 建立索引数据库。由分析索引系统程序对收集回来的网页进行分析，提取相 关网页信息( 包括网页所在u r l 、编码类型、页面内容包含的关键词、关键词位置、 生成时间、大小、与其它网页的链接关系等) ，根据一定的相关度算法进行大量复杂计 算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度( 或重要性) ，然 后用这些相关信息建立网页索引数据库。 ( 3 ) 在索引数据库中搜索排序。当用户输入关键词搜索后，由搜索系统程序从网 页索引数据库中找到符合该关键词的所有相关网页。因为所有相关网页针对该关键词 的相关度早已算好，所以只需按照现成的相关度数值排序，相关度越高，排名越靠前。 最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回 给用户。一般搜索引擎的系统架构如图2 3 所示。 图2 3 一般搜索引擎的系统架构图 其中包括负面搜集器、索引器、检索器、索引文件等部分，下面对其中的主要部 分的功能实现进行了介绍。 ( 1 ) 搜集器。搜集器的功能是在瓦联网中漫游，发现并搜集信息，它搜集的信息 类型多种多样，包括h t m l 页面、x m l 文档、n e w s g r o u p 文章、f 1 p 文件、字处理文 档、多媒体信息等。搜索器是一个计算机程序，其实现常常采用分布式和并行处理技 术，以提高信息发现和更新的效率。商业搜索引擎的搜集器每天可以搜集几百万甚至 更多的网页。搜索器一般要不停地运行，要尽可能多、尽可能快地搜集互联网上的各 种类型的新信息。因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧 信息，以避免死链接和无效链接。另外，因为w e b 信息是动态变化的，因此搜集器、 分析器和索引器要定期更新数据库，更新周期通常约为几周甚至几个月。索引数据库 越大，更新也越困难。 ( 2 ) 分析器。对搜集器搜集来的网页信息或者下载的文档一般要首先进行分析， 以用于建立索引，文档分析技术一般包括：分词( 有些仅从文档某些部分抽词，如 a l t a v i s t a ) 、过滤( 使用停用词表s t o p l i s t ) 、转换( 有些对词条进行单复数转换、词缀去 除、同义词转换等工作) ，这些技术往往与具体的语言以及系统的索引模型密切相关。 ( 3 ) 索引器。索引器的功能是对搜索器所搜索的信息进行分析处理，从中抽取出 索引项，用于表示文档以及生成文档库的索引表。索引项有元数据索引项和内容索引 项两种：元数据索引项与文档的语意内容无关，如作者名、u r l 、更新时问、编码、长 度、链接流行度等等：。内容索引项是用来反映文档内容的，如关键词及其权重、短语、 单字等等。内容索引项可以分为单索引项和多索引项( 或称短语索引项) 两种。单索 引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符( 空格) ； 对于中文等连续书写的语言，必须进行词语的切分。在搜索引擎中，一般要给单索引 项赋予一个权值，以表示该索引项对文档的区分度，同时用来计算查询结果的相关度。 使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方法有统计法、概 率法和语言学法。 ( 4 ) 检索器。检索器的功能是根据用户的查询在索引库中快速检出文档，进行文 档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机 制。检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型等 多种，可以查询到文本信息中的任意字词，无论出现在标题还是正文中。 2 4 元搜索引擎的工作原理 元搜索引擎是建立在已有的搜索引擎服务之上的一种搜索引擎，它利用下层多个 搜索引擎提供的服务向上提供统一的检索服务，自身不采集文档，也没有索引，只是 维护它所管理的搜索引擎的参数信息，如每个引擎的查询参数，引擎的内容表示。当 一个查询到来时，元搜索引擎自身并不处理，而是按照各个成员引擎的查询格式作相 应的转换之后再分发到各个成员引擎，有关成员引擎的参数信息可以帮助元搜索引擎 1 2 进行引擎的选择和协调，各个成员引擎返回结果之后，元引擎进行结果合并形成全局 按权重排序的序列输出给用户。之所以要开发元搜索引擎，毛要的理由是： ( 1 ) w e b 数据量太大，而且增长迅猛，单个引擎的容量，处理能力难以扩展到很 大的规模，所以每个引擎只能包含一部分w e b 文档。元搜索能够分散处理负载，增加 检索的范围。 ( 2 ) 元搜索具有较好的扩展性，可以加入多个成员引擎。它使得各个成员引擎规 模变小，性能更好，这样成员引擎的检索响应时间短，还可以使得检索的内容保持最 新。 ( 3 ) 有些w e b 站点的内容不能用数据采集器抓取，只有用该站点提供的a p i 访问。 ( 4 ) 检索更有效，用户为了找到满意的检索结果可能访问多个搜索引擎，直到找 到结果位置，而元搜索引擎可以帮助用户自动完成这个任务。 一个基本的元搜索引擎的结构表示如下图2 4 所示： 图2 4一个基本的元搜索引擎的结构 2 5 本章小结 本章介绍了w e b 搜索引擎基本原理和技术，介绍了全文搜索引擎，全文搜索引擎 一般由信息采集、索引、搜索三个部分组成，本章给出了全文搜索引擎的一般框架， 并对几个主要部分进行了详细介绍，同时对元搜索引擎的相关原理和技术也做了介绍。 第三章个性化分析模块的设计 3 1 搜索引擎个性化系统的介绍和相关技术 i n t e r n e t 上网页的爆炸式地增长，虽然通用搜索引擎给人们提供了信息检索的手段， 但是随着信息越来越多，搜索引擎返回给用户的信息量也越来越大，其中跟用户无关的 垃圾信息也越来越多。如何根据不同的用户兴趣过滤掉不相关的信息，从而返回给用户 最有用的信息，就是个性化查询研究的内容。到目前为止，已经提出了许多技术来解决 w e b 搜索个性化的问题。 3 1 1 个性化定义 能够满足用户的个体信息需求，即通过观察和分析用户的搜索行为，从中识别用户 的信息需求偏好，并且能够根据用户对搜索结果评价，自觉地调整搜索策略，使得对于 同一检索请求，不同用户能够得到最贴近的自己需要的信息n 盯。 个性化信息服务是针对用户提出的检索要求，根据用户的兴趣在海量信息库中筛 选提供符合用户的信息。个性化信息服务主要包括两个方面的含义：一是信息服务方式 的个性化，即根据个人的爱好或特色进行服务：二是信息服务内容的个性化，即让人们 从个人的职业、兴趣等方面获得信息。 3 1 2 个性化信息服务的实现方法 在个性化信息服务中，有关用户建模技术的研究已经成为个性化服务研究的关键 技术。用户模型并不是对用户个体的一般性描述，而是具有一种面向算法的、具有特 定数据结构的、形式化的用户描述：在个性化信息服务中，主要有三种用户模型的表 示方式：主题表示法，以用户感兴趣的主题表示用户模型，如m y y a h o o ；关键词表示 法，以用户感兴趣的关键词表示用户模型，如w e b w a t c h e r ；基于空间向量模型的表示 法，用关键词向量空间中的向量来表示用户模型的方法，如w e b m a t e 等等。目前，个 性化信息服务中主要有三种用户建模技术“钉：手工定制建模，即由用户自行输入或选 择的建模方法，此方法完全依赖于用户并且无法准确反映用户兴趣；其次是示例建模， 即由用户提供与兴趣相关或无关的示例来建立模型，此方法需要用户在浏览过程中标 注页面以得到示例，干扰了用户的正常浏览；第三种是自动建模，即根据用户的浏览 行为自动建立模型，改进了示例建模技术，不会造成对用户的于扰。但总的来说，在 个性化搜索引擎中，用户建模技术还处于起步阶段，尚未形成完整的技术体系。 文章将个性化信息服务中的手工定制建模技术与自动建模技术相结合，利用基于 空间向量模型的表示方法，提出了一种用户模型智能调整算法，通过用户的浏览行为， 得到用户的兴趣，从而建立更为详细、准确的用户模型。模拟实验表明，该结构和算 法能够有效地提高检索结果的准确度，并且具有良好的可适应性。 3 1 3 用户模型的研究现状 在个性化信息服务研究的早期，建模技术并没有得到应有的重视，大量的研究集 1 4 中在实现个性化信息服务的具体技术上，如信息推荐技术、信息检索技术、文木聚类 技术等。随着个性化信息服务的发展和研究的深入，研究者逐渐意识到个性化信息服 务的关键还在于用户兴趣模型的可计算描述“钉。所以，近年来，有关用户建模技术的 研究开始作为个性化信息服务的基础技术来进行研究。 总的来说，用户建模技术的研究还处于起步阶段，还没形成成熟的技术体系，各 种用户模型离实用还有距离，还有许多关键技术尚待解决。 3 2 用户兴趣模型的建模方法 本文采用用户手工定制和自动建模技术相结合的用户兴趣模型的建模方法。建模 涉及到两个过程，一是用户兴趣模型的建立和初始化，二是用户兴趣模型的更新。 3 2 1 用户兴趣模型的表示 用户模型的表示决定了模型反映用户真实信息的能力和可计算能力，也在一定程 度上限制了建模方法和模型更新算法的选取，同时也是决定算法简繁优劣的重要因素 之一。用户模型的表示目前还没有一个统一的标准，常见的表示方法有以下几种： ( 1 ) 关键词表示法。关键词表示法就是用一组关键词列表来表示用户的兴趣，这 组关键词由用户一开始就提供，因此更像是用户的目标而不是兴趣。 ( 2 ) 加权关键词表示法。加权关键词表示法是指将用户感兴趣的信息以关键词的 形式表示，并通过赋予权重表示用户对该关键词表征的信息感兴趣的程度。这种表示 方法和文档向量空间( v s m ) 表示方法相同1 。 ( 3 ) 主题表示法。主题表示法是指以用户感兴趣的信息的主题来表示用户模型的 方法。如用户对体育和财经感兴趣，则可将用户模