（计算机应用技术专业论文）基于web的个性化搜索引擎的研究与设计.pdf

江苏大学硕士学位论文 摘要 随着网络信息量成爆炸式地增长，人们要在信息海洋中找寻自己需 要的信息是十分困难的。因此，随之出现的信息检索系统一搜索引 擎成为人们搜索信息的主要工具。虽然搜索引擎为用户的查询信息带来 很多方便，但是目前大多数的搜索引擎仍然存在许多缺陷，它们没有考 虑到用户的个性和兴趣，只能简单地执行用户的查询需求，只要用户使 用的关键词相同，所得到的搜索结果就相同，大大降低了搜索的准确性。 所以，如何将搜集的信息资源合理组织，如何从大量的信息中，针对用 户不同的兴趣需求，返回用户真正需要的信息，从而实现个性化搜索， 成为目前研究的重要课题。 本文针对现有搜索引擎系统存在的问题，深入研究实现个性化搜索 引擎系统的相关技术，设计并实现了个性化搜索引擎，并且主要专注于 个性化搜索引擎的网页资源的分析组织、网页的自动分类以及个性化模 型构建更新等方面来分析研究。论文的主要工作如下： ( 1 ) 对目前的搜索引擎系统进行论述分析。论述分析了目前搜索引擎 系统的发展历史、系统架构，并且分析了当前搜索系统存在的一些缺陷， 比如查询的准确性不高，不能体现用户的个性。 ( 2 ) 对个性化搜索引擎中的网页特征描述进行了研究，并且提出了一 种利用非线性函数改进特征词权重计算的方法。 ( 3 ) 网页的自动分类。研究了目前比较流行的分类算法，利用分类算 法对收集到网页信息资源进行分类，从一定程度上缩小了用户的查询范 围，提高了查询的效率。 ( 4 ) 个性化模型的构建。采用w e b 挖掘技术对存放在w e b 缓存中的历 史页面进行挖掘，获取用户的兴趣信息，利用聚类算法对用户兴趣分类 管理，并且利用最优二叉树的形式来表示用户兴趣。利用获取的用户兴 趣信息来构建个性化模型。 。 江苏大学硕士学位论文 ( 5 ) a g e n t 动态跟踪和个性化模型的更新。利用a g e n t 动态跟踪用户 的浏览行为，捕捉用户兴趣的变化，并通过“衰弱因子”、设置权重阈值、 兴趣度阈值以及时间阈值及时更新用户兴趣，不断更新模型。 ( 6 ) 利用个性化模型过滤搜索结果，返回给用户的是满足其兴趣需求 的个性化结果。这里提出了一种搜索结果过滤算法。 关键词：搜索引擎，非线性函数，网页分类，个性化模型，最优二叉树 江苏大学硕士学位论文 a b s t r a c t w l t ht h ee x p l o s l v em c r e a s eo fn 1 f o 肋a t l o ni i lw e b ，i ti sm f f i c m tt 0s e a r c ht h en e e d e d i i l f o 衄a t i o ni ni n f o 咖a t i o nm a r i n e s om es e a r c he n 酉n eh a sb e c 0 m et h em a i nt o o lf o r 枷 0 衄a t i o ns e a r c t l t h o u 曲t h es e a r c he n g i i l eb 血g sag r e a tc 0 n v e i l i e n c ef o rs e a r c h i i l g m f 0 皿a t i o n ，m e r ea r es t i l lm a n ys h o n c o m i n g si nm o s to fs e a r c he n g 面e s t h e yd on o t c o n s i d e ri n d i v i d u a l i 够觚di n t e r e s tt 0m ec o n s u m e r ，t h ei n q u i 巧b e i n ga b l et 0o i l l yc a r 巧o u t c o n s u m e rs i m p l en e e d s a sl o n g 舔t h ek e y w o r dm a tt h ec o i l s 啪e ru s e si si d e n t i c a l ，w h a t r e c 0 皿a i s s a n c er e s u l ti d e n t i c a lh 勰r e d u c e dt h e 辩a r c ht h ep r e c i s i o n t h e r e | o r c ，h o wt h e i b 衄a t i o nr e s o u r c e sc o l l e c t i i l gi so 唱柚i z e dr a t i o n a l l y ，i nh o ws e c o n d a r yl a r g e 锄。吼t0 f i i l f b m l a t i o n ，d i f 6 e r e n ts p e c i f i c a l l y f o r t h ec o n s u m e ri i l t e l e s t n e e d s ，r e t u m t 0t l l e h l f 0 皿a t i o nt h a tt t l ec o n s 啪e rn e e d sr c a l l y ，r e a l 也et h ei i n p o n a n tp r o b l e mi i l d i v i d u a t i o nt 0 s e a r c hf o r ，b e c o m i i 培t os t u d ya tp r e s e mt l l e r e b y t h ep a p e ra i l n st 0t l l ep d o b l e mo fs e a f c he n g m es y s t e m ，h 弱g o n ed e 印i n t 0 也e s y s t e m a t i cr e l e v a n c eo fs e a r c he n g i i l et e c t u l o l o g ys t u d 咖gr e a l 也a t i o ni i l d i v i d u a t i o n ，h 弱 d e s i g n e dt 0c a r r yo u ta l s oi i l d i v i d u a ls e a r c he i 画n c ，锄dm a i l l l yb ea b s o r b e di i li i l d i v i d u a l t t l e a 1 1 2 l l 舛c a lo 唱a i l 娩a t i o n s e a r c h e dm ew e bp a g er e s o u r c e so fe n g 姬e ，a u t o m a t i c c l 嬲s i f i c a t i o n 锄di i l d i v i d u a lm o d e lo fw e bp a g es c tu pr e n e w a le t c a s p e c tc o m e 柚a l 妒c a l r e s e a r c h t h em a i l lw o r ko fp a p e ri s 勰f o l l o w s ： ( 1 ) c a r r i e so nt h ee l a b o r a t i o na n a l y s i st ot h ep r e s e m a r c he n g i n es y s t e m t 1 l e 蛾毗a c yd i s c i l s s i i l gt oa n a l y z et os e a r c ht h ed e v e l o p m e n t 挝s t o r y ，s y s t e mo fe n 百n es y s t e m s t r 咖f ec u r r e n t l y ，a n da n a l y z i i 坞t 0s e 挑h i n gs o m eb l e m i s h e s0 fs y s t e me x i s t e n c ea t p r e s e m ，s e a r c hf o re x 锄p l ei s n 讪i 曲，c 觚铀o d yn o w t l l ec h a r a c t e ro fc u s t o m e r ( 2 ) t oi i l d i v i d u a t i o n ，w 曲p a g e c h a r a c t e r i s t i ci i ls e a 础l e n 百n ed e s c 曲e s m e c a l c i l l a t i v em e t h o dh a v i n gc a r r i e do u tt h ew e i 曲th a v i n gs t l l d i e d ，a n db r i i l g i i l gf o r w a r do n e k i i l do ft h ew o r dm a k i i 坞u s e0 fm en o n l i n e a rf u n c 吐o nt 0i i n p r o v et e 衄w e i 曲t i n g m e t l l o d ( 3 ) 1 1 l ea u t o m a t i cd a s s i f i c a t i o no fw e bp a g e 皿ee f f i c i e n c ys t i l d i e dc u r r e n t l ym o r e p o p m a rd a s s i f i c a t i o n 咖c u l a t ew a y ，m a d e u s eo fc l a s s i f i c a t i o nc a l c u l a t ew a yt oc a r r yo na c ：i a s s i f i c a t i o nt o w a r d sc o l l e c t i l l gaw e b p a g ei i l f o 咖a t i o nar e s 0 u r c e s ，c o n t r a c t e dt h es e a r c h s c o p e o fc i l s t o m e rf r o mt h ec e r t a i l ld e 伊e e ，r a i s e das e a r c h ( 4 ) t 1 1 ei n d i v i d u a lm o d e ls e t su p a d 叩tw r e bm i n i n gt e d l i l i q u et os a v eam e d i u m l i i s t o 哆p a g et oc a r r yo ne x c a v a t i o nt o w a r d sd 印o s i t i i l gi i lw r e bs l o w l y ，o b t a i nt l l ei i l t e r e s t m f o 册a t i o no fc u s t o m e r ，m a k eu s eo ft og a m e rat ) ，p eo fc a l c u l a t ew a yad a u s s i f i c a t i o na m 锄a g e m e n tt ot h ec u s t o m e ri i i t e r e s t ，a i l dm a k eu s co ft h ef o 册o ft w os u p e r i o rf o r kt r e e s 江苏大学硕士学位论文 t 0m e a ni i l t e r e s ti i lt l l ec 吣t o m e r 7 r h i sa n i c l eu s e st h eg a i nt h eu s e ri n t e r e s ti n f o 咖a t i o nt 0 c o n s t n 】c tt h ep e r s o n a l i z e dm o d e l ( 5 ) t h ea g e n td y n a m i cs t a t ef o l l 伽帽w i t ht h er e n e w a lo fi n d i v i d u a lm o d e l m a k i n g u s eo ft h ea g e n td y n a m i cs t a t ef o l l o w sc u s t o m e rt ob r o w s eb e h a v i o r ，c a t c h i n gt h ev a r i e t y 0 fi n t e r e s ti i lt h ec i l s t o m e r ，a n dp a s s w e a kf a c t o r i l ，e s t a _ b l i s ht h ep o w e rh e a v yv a l u e ，t h e i n t e r e s tw o r t ha l l d 劬ei i lt i m ew o r t ht 0r e n e wi n t e r e s ti nt h ec u s t o m e r ，r e n e w i n gm o d e l c o n 血u o u s l y ( 6 ) m a l 【i n gu s eo ft h ei n d i v i d u a lm o d e lp e r c o l a t i o ns e a 玎c h e sar e s u l t ，r e t u m i n gt o s a t i s f ya n di t si n t e r e s td e m a n d i i l gc h a r a c t e r i s t i cr e s u l tf o rc u s t o m e r h e r ep u tf 0 州a r dt o r e s u l tp e r c o l a t i o nc a l c u l a t ew a y k e yw o r d s ：s e a r c he n g i n e ，n o n 1 i n e a rf u n c t i o n ，w e bp a g ec l a s s i f i c a t i o n ， i i l d i v i d u a l m o d e l ，s u p e r i o rt w o f o r kt f e e s 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文 的全部内容或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密 ， 在年解密后适用本授权书。 本学位论文属于 不保密 。 学位论文作者签名：军晶谒， 指导教师签名：孝仓1 q 2 0 0 8 年6 月5 日2 0 0 8 年6 月5 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容以外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：号岛胡7 日期：2 0 0 8 年6 月5 日 江苏大学硕士学位论文 第一章绪论 1 1引言 随着网络技术的迅速发展，人们可以更加方便快捷地共享和交流信息。互联网 是为用户提供信息交换，共享而发展起来的i n t e r n e t 应用。据c n n i c 发布的第1 9 次中国互联网络发展状况统计报告显示，2 0 0 6 年底，我国的网民人数达到1 3 7 亿，全国网页数量和网页字节数分别为4 4 7 亿个和1 2 2 ，3 0 6 g b 。人们上网的主要目 的是查询信息。搜索引擎作为一项网络应用，已经成为人们查询信息的主要工具。 它可以从大量纷杂的信息中，找到与主题相关的信息，为人们查询信息提供了方便。 但是，目前的搜索引擎存在着很多的问题，它只解决了信息查询的问题，而从信息 资源覆盖面、检索精度、检索接口的易用性、可维护性等许多方面来看，其效果并 不能令人满意，而人们迫切地希望能够从w e b 上快速、有效地找到所需信息。 1 2 信息检索系统 从一些资料可知，大约在4 0 0 0 年前，人类就开始有目的地组织信息，以方便对 其的获取和使用。人类经历了从检索工具书到计算机检索再到i n t e r n e t 信息检索。 随着计算机技术的发展，很多信息检索系统应运而生。作为帮助人们查找到特定的 信息的一种工具，信息检索系统需要对信息进行正确的表示、存储和组织，并且提 供对于信息的访问方式。这里，信息的范围很广，可以是一个文本，一个网页，一 封邮件，一张图片甚至是一些虚拟信息的集合。 信息检索系统乜3 旨在检索出与查询相关的所有文档，并且将一些无用的文档过滤 掉，即返回给用户的最终信息能够充分满足用户的兴趣需求。但是，要实现这样的 检索目的，首先需要用户提供能够体现其需求含义的查询语句，其次信息检索系统 采用一种方法来解析用户的查询语句的内容，并且将文件表示成索引词条，方便信 息检索时的信息抽取，最后根据与用户查询的相关度对结果信息进行排序。 1 3in t e r n e 七信息检索系统 i n t e r n e t 信息检索属于信息检索的范畴，它所具有的多样性、灵活性远远超出 了传统的信息检索。传统的信息检索需要访问所有数据库的文件，而i n t e r n e t 搜索 可以不必访问所有文件却能完成信息搜索。随着网络时代的到来，人们可以随时随 江苏大学硕士学位论文 地通过网络浏览器访问i n t e r n e t 查找信息。然而，网络上的信息量一直成爆炸式增 长，再加上这些资料被人们的无序管理，导致i n t e r n e t 上的信息量庞大，呈现出无 结构的特点。因此，想要在信息海洋中找到有用的信息并非易事。 i n t e r n e t 信息具有以下特点： 信息量非常巨大：i n t e r n e t 上的信息量是无比巨大的，目前互联网已有超过 4 4 亿的页面存在，并且这个资料还在不停地以指数级的速度增加着。 动态性：i n t e r n e t 上的信息大部分总在动态地发生着改变。大量的研究表明， 每天有2 3 的页面在更新，平均来说，一个页面生存的半衰期大致为1 0 天左右。为 了保持最新页面，采集器必须定期充分采集同一页面。 结构的异构性：i n t e r n e t 上的信息类型十分丰富。例如，多媒体文件、图像 文件、视频文件、格式化文档等等。 页面的重复性：i n t e r n e t 上不同的网站中有许多的重复文档，这些文档在服 务器之间被多次交叉复制。据统计，大约有3 0 的页面是重复的。 高链接性：一个页面总是会包含有指向其它页面或站点的链接，而且链接变化 多端。 工n t e r n e t 上信息的特殊性，使得其信息检索方法具有独特性。主要的方法有： 基于超文本的信息查询、基于目录的信息查询和基于搜索引擎的信息查询。其中， 搜索引擎是目前人们最为常见的信息检索形式。 1 4 搜索引擎 1 4 1 搜索引擎发展历史 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆炸性 的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息 检索需求的专业搜索网站便应运而生了。 搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a 1 a ne m t a g e 发明的a r c h i e 。 虽然当时w o r l dw i d ew e b 还未出现，但网络中文件传输还是相当频繁的，而且由于 大量的文件散布在各个分散的f ，i p 主机中，查询起来非常不便，因此a l a ne m t a g e 想到了开发一个可以以文件名查找文件的系统，于是便有了a r c h i e 。而真正具有现 代意义的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e lm a u l d i n 将j o h nl e a v i t t 的 蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同年4 月，斯坦福 ( s t a n f o r d ) 大学的两名博士生，d a v i df 订。和美籍华人杨致远( g e r r yy a n g ) 共 2 江苏大学硕士学位论文 同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。从此搜索引擎 进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数百家，其检索的 信息量也与从前不可同日而语。比如g o 0 9 1 e ，其数据库中存放的网页已达3 0 亿之巨。 搜索引擎的发展是一个不断探索的过程，如今它已向第三代发展，功能也越束越 强大，下面就对第一代和第二代搜索引擎做一个简要的介绍。 1 4 1 1 第一代搜索引擎 无论是纯技术型的搜索引擎还是分类目录，都可以认为是互联网上的第一代搜索 引擎，出现于1 9 9 4 年前后，以a 1 t a v i s t a 、y a h o o 和i n f o s e e k 为代表，搜索结果的 好坏往往用反馈结果的数量来衡量，也就是说，第一代搜索引擎“求全”。 i n f o s e e k ( 堕塑：i 旦q 墨旦皇k ：曼q 婴) 1 9 9 5 年初，搜索引擎家族又添了新的成员：i n f o s e e k 。i n f o s e e k 不是以数据库 大而见长的，而是以检索的相关程度高而知名。它沿袭了雅虎和l y c o s 的概念。 i n f o s e e k 友善的用户接口和大量的附加服务使它的声望日益增加。而1 9 9 5 年1 2 月 与t s c a p e 的战略性协议，使它成为一个强势搜索引擎。1 9 9 9 年，i n f o s e e k 被 d i s n e y 所购买，d i s n e y 将其作为网站g o c o m 的搜索引擎，在技术上的革新比较 少，处于维持现状的水平，主要是做娱乐方面的索引。 a l t a v i s t a ( 盟：垒! 主垒! i 璺! 垒：璺q 里) a 1 t a v i s t a 是在1 9 9 5 年1 2 月推出的。它是第一个支持自然语言搜索的搜索引擎， a 1 t a v i s t a 是第一个实现高级搜索语法的搜索引擎( 如a n d ，o r ，n o t 等) 。用户可以 用a 1 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 也声称是第一个支持用户自己向网页索引库提交或删除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 i 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 4 1 2 第二代搜索引擎 1 9 9 8 年，第二代搜索引擎出现在互联网上，这些引擎的主要特点是使用了一系 列新技术，特别是自然语言处理技术，使得搜索更快更准确，可以用“求精”来描 3 江苏大学硕士学位论文 述。 q ) v i v i s i m o ( h 主主p ；么z i y i 璺i 堕q ：曼q 婴z ) v i v i s i m o 是一个元搜索引擎，调用多种搜索引擎，并对返回的结果自动分类， 接口友好，简单易用。尽管元搜索引擎存在着这样或那样的功能局限，但其以涵盖 较多的搜索资源，能够在尽可能短的时间内提供相对全面、准确的检索结果等诸多 优异功能受到用户的青睐，已渐成为一种不可或缺的颇具潜力的网络检索工具。 a s k j e e v e s ( 曼旦堕：璺曼k ：q q 里) 从技术上讲，a s k j e e v e s 是一个比较简单的系统，但从创意来说是相当出色的， 它是维护了问题和答案相联系的数据库。从结构上说它比较简单，因为提问后并不 是立即返回问题的答案，而是用逼近式的方法让你选择他知道的所有问题，再由用 户分类来选择答案。这点从技术上非常容易解决，但从实践来说需要大量的人力 来干预，即是问题与结果的数据库规则基本是靠入工来建立的。但由于它建立了一 套可以让人以自然语言提问的系统，很多网民喜欢这样的形式。但由于其规则库太 小，真正使用的人不是很多。 g o t o ( ! ! ! 型：g q 主q ：垦q 堡) 从本身的技术来说，g o t o c o m 使用了超链接的分析与根据用户的点击行为来分 析与重排序，搜索得到的结果相关性程度较高，而且比较符合用户的点击习惯。 g o t o c o m 允许网站的拥有者实时进行检索结果的排序，客户可以花钱购买排序的位 置，通过拍卖的形式将相关的网站放在前面，但同时明确的标出这个搜索结果是付 费的，g o t o c o m 是最先将拍卖的概念引入搜索引擎服务的网站。 龟! ) g o o g le ( 里! ! 型：g q q g ! 金：q 型) g 0 0 9 1 e 由l a r r yp a g e 和s e r g e yb r i m 设计，于1 9 9 8 年9 月发布测试版，一年 后正式开始商业运营。g 0 0 9 l e 由于对搜索引擎技术的创新而获奖无数，如美国时 代杂志评选的“1 9 9 9 年度十大网络技术”之一、个人计算机杂志授予的“最佳 技术奖”、t h en e t 授予的“最佳搜索引擎奖”等。g o 0 9 1 e 现为全球8 0 多家门户和终 点网站提供支持，客户遍及2 0 多个国家。g o o g l e 所擅长的是易用性和高相关性。 g 0 0 9 1 e 提供一系列革命性的新技术，包括完善的文本对应技术和先进的p a g er a n k 排序技术，后者可以保证重要的搜索结果排列在结果列表的前面。g 0 0 9 l e 还提供一 项很有用的服务一一“网页快照”功能，即当搜索内容站点或网页不存在时，用户 可以调用g o o g l e 事先为用户储存的大量应急网页，经g 0 0 9 l e 处理后，搜索项均用 不同颜色标明，另外还有标题信息说明其存盘时间日期，并提醒用户这只是存盘资 料。实际上g o 0 9 1 e 将检索的网页都做了一番“快照”然后放在自己的服务器上，这 4 江苏大学硕士学位论文 样做的好处是不仅下载速度极快，而且可以获得互联网上已经删除的网页。g o 0 9 1 e 已成为当前搜索准确度和用户查询相关度最好的搜索引擎4 【。 雅虎中国( 堕塑：z 尘q q ：鱼q 堕：塑) 雅虎中国网站( w w w y a h o o c o m c n ) 于1 9 9 9 年9 月正式开通，它是雅虎在全球 的第2 0 个网站。中文y a h o o 在许多人的心目中是搜索引擎的同义词，名声在外的 y a h o o 也确有其过人之处，分类目录查询就做得相当出色，无论从网站的数量还是 分类的合理性方面都可圈可点。站点目录分为1 4 个大类，每一个大类下面又分成若 干个子类，搜索十分方便。该站点连接速度快，包含范围广，资料容量大，简便易 用，是查询各种信息的好去处。雅虎中国网站为用户提供了强大的搜索功能，通过 其1 4 类简单易用、手工分类的简体中文网站目录及强大的搜索引擎，用户可以轻松 搜索到政治、经济、文化、科技、房地产、教育、艺术、娱乐、体育等各方面的信 息。 目前，虽然国内的搜索引擎在技术上与国外还有一定差距，但也有不少优秀的中 文搜索引擎。比如，百度( w w w b a i d u c o m ) 、北大天网( h t t 巳：e 乜k u e d u c n ) 、世 纪永联( w w w s o f t h o u s e c o m c n ) 等等。 1 4 2 搜索引擎的系统架构 真j 下意义上的搜索引擎，通常指的是收集了互联网上几千万到几十亿个网页并对 网页中的每一个文字( 即关键词) 进行索引，建立索引数据库的全文搜索引擎。当 用户查找某个关键词的时候，所有在页面内容中包含了该关键词的网页都将作为搜 索结果被搜出来。在经过复杂的算法进行排序后，这些结果将按照与搜索关键词的 相关度高低，依次排列。搜索引擎的系统架构拍1 如图卜1 所示： 携霭应# 杠 鬏够 戮 露溺 滋 叠一 图卜1 搜索引擎系统架构 搜索器( s p i d e r ) ：搜索器是一个计算机程序，其实现常常采用分布式和并行处 5 一 江苏大学硕士学位论文 理技术，以提高信息发现和更新的效率。在搜索器实现时，系统中维护一个超链接 队列，或者堆栈，其中包含一些起始u r l ，搜索器从这些u r l 出发，下载相应的页面， 并从中抽取出新的超链加入到队列或者堆栈中，上述过程不断重复队列直到堆栈为 空。为提高效率，搜索引擎将w e b 空间按照域名、i p 地址或国家域名进行划分，使 用多个搜索器并行工作，让每个搜索器负责一个子空间的搜索。为了便于将来扩展 服务，搜索器应能改变搜索范围。 分析器：对搜索器搜集来的网页信息或者下载的文档一般要首先进行分析，以用 于建立索引，文件分析技术一般包括：分词、过滤、转换等等。 索引器：对搜索器所搜索的信息进行分析处理，从中抽取出索引项，用于表示文 档以及生成文文件库的索引表。索引项有元资料索引项和内容索引项两种。在搜索 引擎中，一般要给单索引项赋予一个权值，以表示该索引项对文件的区分度，同时 用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语 索引项的提取方法有统计法、概率法和语言学法。 检索器：根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评 价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。检索器常用的 信息检索模型有集合理论模型、代数模型、概率模型和混合模型等多种，可以查询 到文本信息中的任意字词，无论出现在标题还是正文中。 1 4 3 搜索引擎存在的缺陷 随着互联网上的信息急剧增加，用户检索信息时更加需要搜索引擎中的搜索技 术。据统计显示，2 0 0 5 年1 2 月底，搜索引擎的用户到达率为8 9 1 ，即使用过搜索 引擎的互联网用户占所有互联网用户的8 8 2 。但是，目前i n t e r n e t 用户对于现有 的搜索引擎的满意程度并不乐观。由k e e n 所做的调查显示，人们平均每天有四个问 题需要从外界获取答案，其中3 1 的人使用搜索引擎以获取正确的信息，而在网上查 找答案的人中，半数以上都不成功。 从调查资料中不难看出，目前的搜索引擎仍然存在很多局限性。主要表现在以下 几个方面： 查询精度不高且不能根据用户兴趣返回信息。目前大多数的搜索引擎在返回 结果的精度方面不够理想，因此要加强查询结果过滤等方面的研究。根据专家评测， 目前主要的搜索引擎返回的相关结果的比率不足4 5 。 资料检索与用户的交互不够。据调查显示，用户行为信息的利用对提高检索 的准确率和召回率最有优势，尽管目前有些搜索引擎通过日志文件记录大量的用户 6 江苏大学硕士学位论文 行为信息，但并没有有效地利用这些信息建立相应的反馈机制，以指导资料检索与 用户的交互。 语义性差。目前的搜索引擎只能支持关键词的查询方式，通过这种方式来猜测 用户要找些什么，不能充分理解用户的需求。所以只有自然语言的查询更能满足用 户的需求和兴趣。 查询结果排序不合理大多数搜索引擎并没有对目录型、内容型网页分类组织， 加上检索方式本身存在缺陷。另外，排序时又过多地考虑网页的人度、镜像度等并 不能直接反映网页实际内容的因素，从而使得查询结果排序过于粗糙。 不能处理多种格式的文件。目前许多搜索引擎只能处理h t m l 格式，其它格式 的信息包括p d f 文文件、w o r d 文档、以及各种的电子邮件内容都无法查找。 1 5 本文的研究意义、研究内容及论文组织结构 由于w e b 信息具有数量庞大、重复性强、无序性的特点，搜索引擎成为目前帮助 人们搜索信息的主要工具。但是目前很多的搜索引擎系统都没有考虑到每个用户的 兴趣需求，没有考虑到用户之间的差异。搜索引擎返回给用户的搜索结果越来越多， 人们也越来越难以找到符合自己兴趣的信息。因此，如何提高搜索引擎的性能，为 用户提供更为准确的搜索信息是本文的研究的重点。 当前用户需要的是一种个性化的搜索服务，它能够根据用户的兴趣和特点进行搜 索，返回用户需要的搜索结果，它可以根据用户之间的差异，提供给用户是一种基 于用户兴趣的、智能的搜索服务。为此，本文提出了从用户和资源的角度来分析， 构建个性化的搜索引擎。该系统主要通过对于收集的w e b 资源进行有效地组织、分 类，然后利用挖掘的用户兴趣信息构建个性化模型，最终使用个性化模型来过滤搜 索结果返回给用户。其间我们通过a g e n t 来动态跟踪用户，随时感知用户兴趣的变 化，及时更新个性化模型。 本文所研究的个性化搜索引擎系统中，利用网页分类技术，使得信息搜索的定位 更为准确，缩小了搜索的范围；利用w e b 挖掘技术来挖掘用户的兴趣信息，对于用 户兴趣的存储表示，本文利用最优二叉树的形式来表示用户个性化模型。本系统的 最终目的是为用户提供符合其兴趣的更准确的搜索结果。 以提高搜索引擎系统的性能和查准率为目标的，本文研究的内容主要围绕对于信 息资源的组织，网页分类? 用户个性化模型的构建和更新、利用个性化模型过滤结 果等方面。本文对实现个性化搜索系统的各项技术进行论述，并且讨论了系统构建 问题。本文主要从下几个方面进行了研究和设计。 7 江苏大学硕士学位论文 ( 1 ) 网页的自动分类。研究了目前比较流行的分类算法，利用改进的分类算法对收 集到网页信息资源进行分类。 ( 2 ) 个性化模型的构建。采用w e b 挖掘技术对存放在w e b 缓存中的历史页面进行挖 掘，获取用户的兴趣信息，并且利用最优二叉树的形式来表示用户兴趣。从获取的 用户兴趣信息来构建个性化模型。 ( 3 ) a g e n t 动态跟踪和个性化模型的更新。利用a g e n t 动态跟踪用户的浏览行为， 捕捉用户兴趣的变化，并通过“衰弱因子”、设置权重阈值、兴趣度阈值以及时间阈 值及时更新用户兴趣，重点研究了网页自动分类以及构建索引的方法，不断更新模 型。 ( 4 ) 利用个性化模型过滤初始的搜索结果，返回给用户的是满足其兴趣需求的个性 化结果。 论文组织结构： 第一章简述了i n t e r n e t 信息检索系统，综述了搜索引擎的概念、发展历史， 系统架构和存在的缺陷，明确了本文研究的意义目的和内容。 第二章主要介绍对于实现个性化搜索引擎系统涉及的相关的背景知识。 第三章给出了基于w e b 的个性化搜索引擎系统的整体框架体系结构设计，并就 其中的主要功能模块做详细的介绍，简述了系统的运行机制。 第四章研究个性化搜索引擎中网页特征描述，介绍了相关文献的研究内容，并 且对网页特征抽取范围以及特征词权重计算作重点研究。提出了一种改进的权重计 算的方法。 第五章详细论述了个性化模型的构建过程。首先介绍了利用历史页面来挖掘出 用户兴趣信息，并且提出了根据兴趣特征进行页面聚类的算法以及用户兴趣向量的 表示法：然后参照最优二叉树的形式存储用户兴趣的思想来存储用户兴趣；随后利 用“衰弱因子 、设置的权重阈值、兴趣度阈值以及时间阈值的思想，提出模型更新 的方法；最后给出了基于用户兴趣的过滤结果的方法。 第六章前部分主要介绍了信息搜集处理模块的设计，其中讨论了网络蜘蛛 ( s p i d e r ) 收集网页信息的过程，以及分析了对于收集到的网页信息进行预处理的 必要性，简述了对数据进行分词的一般过程，并且在此基础上，着重讨论了对于存 放在原始信息库中的网页数据进行自动分类和构建索引的方法。后部分主要阐述了 结果过滤模块的设计实现，提出了利用个性化模型对搜索结果进行过滤的具体算法。 第七章通过实验测试网页分类和个性化模型。对于网页分类实验，我们利用从 网站上抓取的网页集，利用m a r c o f 1 来验证分类的效率。通过对比改进前后的分类 8 江苏大学硕士学位论文 算法的效率，体现出改进后的k n n 算法的优越性。对于个性化模型的测试，利用某 位用户6 0 天搜索的历史页面来构建个性化模型；利用设置的权重阈值、兴趣度阈值、 时间阈值以及衰弱因子，得到不同的用户兴趣，显示出用户的兴趣变化特点；将个 性化模型用于搜索结果的过滤，返回给用户的是体现其兴趣的结果。 第八章论文的总结和进一步展望。 9 江苏大学硕士学位论文 第二章相关概念介绍 2 1w e b 挖掘与in t e r n e t 个性化服务 2 1 1w e b 挖掘 w e b 挖掘是指使用数据挖掘技术在w w w 资料中发现潜在的、有用的模式或信息。 w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计学、人工 智能中的机器学习和神经网络等。w e b 挖掘作为一个完整的技术体系，在进行挖掘之 前的信息获得工r ( 工n f o r m a t i o nr e t r i e v a l ) 和信息抽取i e ( i n f o r m a t i o ne x t r a c t i o n ) 相当重要。目前，在这两方面都有相应的研究成果和具体应用，特别是在大型搜索引 擎中得到了很好的应用。根据对w e b 数据的感兴趣程度不同，w e b 挖掘一般可以分为 三类6 m ：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r e m i n i n g ) 、w e b 用法挖掘( w e bu s a g em i n i n g ) 。如图2 1 所示。 w 曲挖掘 l 内容挖掘il 结构挖掘i 使用挖掘 基于代理 的方法 智能查 询代理 信息过 滤分类 塑幽褂 习到巨 图2 1w e b 挖掘分类 w e b 内容挖掘就是从w e b 资源中发现信息或知识的过程。w e b 内容挖掘的对象包 括文本、图像、音频、视频、多媒体和其他各种类型的数据。其中针对无结构化文 本进行的w e b 挖掘被归类到基于文本的知识发现( k d t ) 领域，也称文本数据挖掘或 文本挖掘。w e b 内容挖掘一般从两个不同的观点来进行研究。从资源查找( i r ) 的观 点来看，w e b 内容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助用户过 滤信息。而从d b 的角度讲w e b 内容挖掘的任务主要是试图对w e b 上的数据进行集成、 建模，以支持对w e b 数据的复杂查询。 1 0 江苏大学硕士学位论文 w e b 结构挖掘是从w e b 组织结构和链接关系中推导信息、知识。w e b 结构挖掘的 对象是w e b 本身的超连接，即对w e b 文档的结构进行挖掘。对于给定的w e b 文档集 合，应该能够通过算法发现他们之间连接情况的有用信息，文档之间的超连接反映 了文档之间的包含、引用或者从属关系，引用文档对被引用文档的说明往往更客观、 更概括、更准确。w e b 结构挖掘在一定程度上得益于社会网络和引用分析的研究。 把网页之间的关系分为i n c o m i n g 连接和o u t g o i n g 连接，运用引用分析方法找到同 一网站内部以及不同网站之间的连接关系。此外，w e b 结构挖掘另一个尝试是在w e b 数据仓库环境下的挖掘，通过发现针对某一特定领域超链接的层次属性去探索信息 流动如何影响w e b 站点的设计。 w e b 使用挖掘是通过挖掘相关的w e b 日志记录，来发现用户访问w e b 页面的模式， 通过分析日志记录中的规律，可以识别用户的忠实度、喜好、满意度，可以发现潜 在用户，增强站点的服务竞争力。w e b 使用记录数据除了服务器的日志记录外还包括 代理服务器日志、浏览器端日志、注册信息、用户会话信息、交易信息、c o o k i e 中 的信息、用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。 2 1 2 i n t e r n e t 个性化服务 传统的i n t e r n e t 服务为用户使用i n t e r n e t 资源提供了一些可行的途径。然而， 相对于巨大、无序的i n t e r n e t 信息空间，每个用户真正感兴趣的信息非常有限，仅 仅是工n t e r n e t 信息空间的沧海一粟。显然，传统的“人找信息”的服务模式已经越 来越难以适应迅速增长的工n t e r n e t 信息资源，用户迫切需要一种能够根据用户的特 点自动组织和调整信息的服务模式，个性化服务应运而生。最早的个性化服务是以 个性化导航、过滤和推荐的服务形式出现。随着i n t e r n e t 中信息量的指数增长， i n t e r n e t 信息检索系统的检索效率日益受到关注。为不同的用户提供有针对性的检 索结果，也即个性化信息检索，成为一种新的个性化服务形式。个性化服务涉及的 技术较多，如用户建模技术，个性化推荐技术，w e b 挖掘技术，用户隐私保护技术等。 目前，个性化服务逐渐从学术研究走向实际应