（计算机应用技术专业论文）个性化搜索引擎推荐算法研究.pdf

硕一i ：学位论文 摘要 随着i n t e r n e t 和网络信息技术的迅猛发展，网络资源呈指数急剧增长，传统 的通用搜索引擎的查询结果只依赖于查询关键词，而实际上，即便相同的查询词， 不同的用户查询目的可能不同，所希望的返回结果也会因人而异。针对这种情况， 人们迫切需要一种针对个人特点提供更加精确查询结果的搜索工具，以用户为中 心的个性化搜索引擎便应运而生。 本文首先全面了解了实现个性化搜索引擎的基本理论和研究现状，并对现有 各种个性化推荐技术进行性能对比分析，为以后的研究提供了理论基础。 接着，本文研究了推荐领域最重要的协同过滤算法，基于用户推荐的协同过 滤可以为用户发现新的潜在感兴趣的资源，但是具有稀疏性等缺点；基于项目推 荐的协同过滤在某种程度上可以解决稀疏性，而且简单有效，但是只能发现和用 户已有兴趣相似的信息。针对这些问题，本文提出了一种基于单值分解的集影响 协作过滤推荐算法，利用单值分解和增大影响集来提高协同过滤的推荐质量，解 决稀疏性问题，改善推荐系统的性能。 然而在应用了改进的协同过滤推荐算法的推荐系统中，除了已经解决的稀疏 性问题，还存在着冷开始新项目问题、扩展性问题以及用户潜在兴趣难以挖掘等， 本文在前面研究的基础上，提出了一种个性化推荐融合算法，在优秀的基于用户 协同过滤推荐思想基础上，结合现有矩阵技术，扩展影响集，利用基于项目协同 过滤以及基于内容过滤，解决了稀疏问题、扩展性问题、冷开始和用户潜在兴趣 难以挖掘等问题，提高了推荐系统的推荐质量。并在此基础上，提出了一种策略 预测用户评分，解决了由于用户对资源苛刻程度不同，而导致评分相差较大的问 题。 最后，分析研究了开源全文检索工具l u c e n e ，并在该平台上加入了个性化搜 索模块，分别对改进的协作过滤推荐算法和个性化推荐融合算法进行了仿真实验。 实验结果表明：改进的协作过滤推荐算法比传统的协同过滤算法的推荐质量高， 而在冷开始状况下，个性化推荐融合算法比改进的协作过滤推荐算法推荐质量高， 预测评分更加与实际评分相接近，搜索结果更加符合用户需求，提高了个性化搜 索引擎的服务质量。 关键词：搜索引擎；个性化；协同过滤；融合推荐 a bs t r a c t w i t ht h er a p i d d e v e l o p m e n to ft h ei n t e r n e ta n dt h en e t w o r k si n f o r m a t i o n t e c h n o l o g y ，n e t w o r kr e s o u r c e si n c r e a s ee x p o n e n t i a l l y , t h er e s u l t so ft h et r a d i t i o n a l s e a r c he n g i n eo n l yd e p e n do nt h eq u e r yk e y w o r d s ，i nf a c t ，e v e ni ft h es a m eq u e r y k e y w o r d s ，t h ep u r p o s eo fd i f f e r e n tu s e rm a yb ed i f f e r e n t i nv i e wo ft h i ss i t u a t i o n 。 p e o p l en e e das p e c i a ls e a r c he n g i n et op r o v i d ep e r s o n a l i z e ds e a r c he n g i n es e r v i c e s w h i c hc a nr e t u r np r e c i s er e s u l t sf o rt h e i ro w n f e a t u r e s ，a n dau s e r c e n t r i cp e r s o n a l i z e d s e a r c he n g i n ew a s p r o p o s e d t h i st h e s i si n t r o d u c e dt h eb a s i ct h e o r ya n ds t a t e o f - a r to fp e r s o n a l i z e ds e a r c h e n g i n e ，a n dm a d ep e r f o r m a n c ee v a l u a t i o na n dc o m p a r i s o no nt h ee x s i t i n gt e c h n o l o g y f o rp e r s o n a l i z e dr e c o m m e n d a t i o n t h e s e t h e o r i e sp r o v i d e df o u n d a t i o ns t o n eo f r e s e a r c h e sb e h i n d t h e n ，t h et h e s i sr e s e a r c h e do nt h em o s ti m p o r t a n tc o l l a b o r a t i v ef i l t e r i n g a l g o r i t h m si nt h ef i e l do fr e c o m m e n d a t i o n ，u s e r b a s e dc o l l a b o r a t i v ef i l t e r i n gc a n r e c o m m e n dn e wi n t e r e s t e dp o t e n t i a lr e s o u r c e sf o ru s e r s ，b u ti th a ss o m es h o r t a g e s ， s u c ha ss p a r s e ；p r o j e c t b a s e dc o l l a b o r a t i v ef i l t e r i n gc a ns o l v et h ep r o b l e mo fs p a r s i t y , a n di ti ss i m p l ea n de f f e c t i v e ，b u to n l yt h es i m i l a ri n f o r m a t i o nc a nb ef o u n d t os o l v e t h e s ep r o b l e m s ，a ni m p r o v e d a l g o r i t h mf o rc o l l a b o r a t i v ef i l t e r i n ga l g o r i t h m sw a s p r o p o s e d ，i m p r o v e dt h eq u a l i t yo fc o l l a b o r a t i v ef i l t e r i n gr e c o m m e n d a t i o ns y s t e mb y s i n g l ev a l u ed e c o m p o s i t i o na n di n c r e a s e i n gt h ei m p a c tc o l l e c t i o n ，a n di m p r o v e dt h e p e r f o r m a n c eo ft h es y s t e m h o w e v e r , i nt h er e c o m m e n d a t i o ns y s t e mb a s e do nt h ea l g o r i t h mo fi m p r o v e d c o l l a b o r a t i v ef i l t e r i n g ，t h ep r o b l e m so fc o l d t o s t a r t ，e x p a n s i b i l i t yw e r es t i l lb a dt o t h ep e r s o n a l i z e dr e c o m m e n d a t i o ns y s t e m ，w h e nt h e s y s t e mb e g a nt or u n ，t h e r e c o m m e n d e ds e r v i c e sw a sd i f f i c u l tt o i m p l e m e n t i nt h i ss e c t i o n ap e r s o n a l i z e d f u s i o n a l g o r i t h mw a sp r o p o s e d ，b a s e do nt h ee x c e l l e n tu s e r b e s dc o l l a b o r a t i v e f i l t e r i n g ，i tc o m b i n e dw i t ht h ec o n t e n t b a s e dr e c o m m e n d a t i o na n dt h ep r o j e c t b a s e d c o l l a b o r a t i v ef i l t e r i n gt os o l v et h ep r o b l e m so f s p a r s e ，s c a l a b i l i t y ，c o l d t o s t a r ta n dt h e d i f f i c u l t yt om i n ep o t e n t i a li n t e r e s tw i t hm a t r i xt e c h n o l o g ya n de x t e n d i n gi n f l u e n c e s e t s ，i m p r o v e dt h eq u a l i t yo ft h er e c o m m e n d a t i o ns y s t e m a n do nt h i sb a s i s ，a s t r a t e g yw a sp r o p o s e dt op r e d i c tt h eu s e r ss c o r et os o l v et h ep r o b l e mo ft h eg r e a t d i f f e r e n c eo fs c o r ec a u s e db yd i f f e r e n ts t r i c t l yl e v e l so fu s e r s f i n a l l y ，t h et h e s i sa n a l y s i s dt h eo p e n s o u r c ef u l l t e x ts e a r c ht o o l sl u c e n e a d d e d i i i 硕上学位论文 t h ep e r s o n a l i z e ds e a r c hm o d u l e st ot h ep l a t f o r m ，a n dm a d ea l g o r i t h ms i m u l a t i o no n t h ei m p r o v e dc o l l a b o r a t i v e f i l t e r i n ga l g o r i t h m sa n dt h ef u s i o n o fp e r s o n a l i z e d r e c o m m e n d a t i o na l g o r i t h m s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ：t h eq u a l i t yo f i m p r o v e d c o l l a b o r a t i v ef i l t e r i n ga l g o r i t h mi sb e t t e rt h a nt h et r a d i t i o n a lc o l l a b o r a t i v e f i l t e r i n gr e c o m m e n d a t i o na l g o r i t h m s ，a n do nt h ec o n d i t i o n so ft h ec o l d t o - s t a r t ，t h e q u a l i t yo fp e r s o n a l i z e dr e c o m m e n d a t i o n sf u s i o na l g o r i t h mi sb e t t e rt h a nt h ei m p r o v e d c o l l a b o r a t i v e f i l t e r i n ga l g o r i t h m ，t h ep r e d i c t i o n m e e tt h eu s e r sa c t u a ls c o r e m o r e ，s e a r c hr e s u l t sw e r em o r ei n l i n ew i t hu s e rn e e d s ，i m p r o v e dt h eq u a l i t yo f p e r s o n a l i z e ds e a r c he n g i n es e r v i c e k e yw o r d s ： s e a r c h e n g i n e ；p e r s o n a l i z e d ； c o l l a b o r a t i v e f i l t e r i n g ； f u s i o n r e c o m m e n d a t i o n i v 个性化搜索引擎推荐算法研究 插图索引 图1 1 通过搜索引擎查询示例l 图2 1 搜索引擎架构“7 图2 2 用户兴趣模型1 4 图3 1 单值分解矩阵变换2 4 图3 2 不同的口值的m a e 比较”2 8 图3 3 本文算法与协同算法的m a e 比较一2 8 图4 1 系统架构“3 5 图5 1l u c e n e 的处理步骤3 8 图5 2 个性化搜索引擎推荐系统模块4 0 图5 3 本文算法4 与协同算法以及优化协同算法的m a e 比较4 4 图5 4 不同数据集的m a e 比较一4 5 硕上学位论文 表 表 表 表 附表索引 2 o 3 5 2 4 4 4 析问 具分时 一 工果的发结耗阵开索消矩统检所源系擎据资的引数户要索组用主搜每 1 l 2 ，r 、 3 5 5 5 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特另t l ；h l ：l 以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 筒、华 1 日期：研年易月z ，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 阿、竿 导师签名：多乱漶 l ，、v ” 日期：加夕年6 月一日 日期：年月日 硕上学位论文 第1 章绪论 1 1 研究背景和意义 随着网络技术的飞速发展，w e b 信息量的增加，网络资源急剧膨胀【l 】，用户 在茫茫网海中找寻需要的信息，就象大海捞针一样，而应运而生的搜索引擎在互 联网中搜集信息，并对信息理解、提取、组织和处理，为用户提供检索服务。 以g o o g l e 、b a i d u 代表的这类搜索引擎已为人们所熟知。具有基于关键字， 通用性等特点。然而对于一个查询动辄返回几十万、甚至几百万篇文档，用户不 得不花费大量的时间和精力在结果中筛选。对于不同兴趣，背景的用户如何提供 更高效率更专业的服务，使得个性化搜索引擎技术【2 】成为目前的研究热点之一。 个性化搜索引擎就是针对用户的不同需求时，根据用户背景和其用户群喜好 主动为用户推荐满足用户潜在兴趣的资源。如图1 1 所示，如果b o b 喜欢去关于 探险的地方去旅游，而l i l y 则喜欢去浪漫的地方旅游，则两者的需求不同，而现 有的搜索引擎在输入相同关键字“旅游时，返回的结果是没有区别的，其只能 对于用户的查询关键词与资源通过某些方式进行匹配，而不能判断这些资源是否 真的合乎用户的兴趣，没有考虑用户的背景、兴趣、行为风格。而我们的研究则 是针对需求的不同，为用户提供不同的更专业的服务。 图1 1 通过搜索引擎查询示例 个性化搜索引擎出现了，它的出现，为满足用户的这种需求带来了希望，它 建立用户模型，分析用户兴趣，并自动将它认为对用户有用、用户感兴趣的资源 提交给用户，且具有不断学习、适应信息更新和用户兴趣动态变化的能力，从而 提供个性化的服务。在日益开放的信息服务市场环境里，用户不断动态变化的信 息需求正成为信息系统不断发展的动力，而“以用户为中心 这一服务理念早已 经深入到各个行业的每个角落。 个性化搜索引擎是通过个性化推荐技术来实现的，个性化推荐系统也因为最 l ，q 鼬 个性化搜索引擎推荐算法研究 能完美体现“以用户为中心服务理念而越来越被各界所关注【2 1 。著名的个性化推 荐系统如美国斯坦福大学数字图书馆项目的f a b 系统、美国明尼苏达大学计算机 科学与工程系开发的推荐u s e n e t 的g r o u p l e n 系统、可以预测用户对网页喜好程 度并进行推荐的s i t e s e e r 系统、印地安那州大学计算机信息科学学院和图书情报 科学学院一起研制开发的s i f t e r 个性化推荐系统等。这些系统的研制开发为信 息服务提供了具有创新能力的先决条件。 现有的推荐【3 ，4 1 大都采用基于规则的，基于项目推荐、基于用户推荐的协同推 荐以及基于内容推荐等。项目推荐简单、有效，但是只能发现和用户已有兴趣相 似的信息，用户推荐可以为用户发现新的潜在感兴趣的资源，但是具有稀疏性和 扩展性等缺点。本文是在考虑如何综合利用现有技术，提高推荐系统的推荐质量， 为搜索引擎用户提供更好的、更符合用户需求的服务而展开讨论和研究的。 1 2 研究内容 个性化搜索引擎的核心是个性化推荐技术，而现有推荐系统普遍存在稀疏性 问题，扩展性问题，新项目问题，用户潜在兴趣难以挖掘的等一系列问题。 本文主要研究内容是：利用现有各种推荐思想，综合矩阵、最近邻等技术， 解决现有推荐中存在的一系列问题，提高推荐质量，向用户提供高质量的个性化 的检索服务。 课题的具体研究主要包含以下几个方面： ( 1 ) 基于查询词的通用搜索引擎设计 基于查询关键词的通用搜索引擎是个性化搜索引擎的基础，它分为互联网资 源获取模块，资源分析模块，分词模块，建立索引文件模块，用户查找模块。 ( 2 ) 个性化推荐设计 通过设计出一种算法来解决推荐系统中存在的稀疏性问题，扩展性问题，新 项目问题，用户潜在兴趣难以挖掘的问题，在系统中利用各种推荐技术，综合矩 阵运算等技术，提高推荐系统服务质量。 ( 3 ) 个性化搜索引擎系统集成 在基于查询关键字和个性化推荐设计的基础上，向用户推出真实意义上的个 性化搜索引擎服务。会考虑到基于查询词的搜索结果与个性化推荐所得结果各占 权重。 本文的研究属于第二方面。 1 3 主要工作 本文介绍了当前的搜索引擎和个性化技术的研究进展，分析归纳了各种个性 2 硕：i ：学位论文 化推荐算法的基本思想和算法性能，为提高个性化服务质量进行了深入研究。本 文工作的目标是通过设计出一种推荐算法来解决系统中存在稀疏性问题，扩展性 问题，新项目问题，用户潜在兴趣难以挖掘的问题，以及设计出一种策略预测用 户评分，最后在l u c e n e 平台上进行实验和性能分析验证两种算法的有效性。 本文的主要工作如下： ( 1 ) 对个性化搜索引擎中的搜索引擎和个性化推荐的现有思想和算法进行具 体研究，并分析了其算法性能的优劣、以及适用情况。 ( 2 ) 提出一种基于s v d 影响集的协作过滤推荐算法。协同推荐分为基于项目 推荐的协同推荐、基于用户推荐的协同推荐。现有的推荐大都采用这两种方式， 项目推荐简单、有效，但是只能发现和用户已有兴趣相似的信息，用户推荐可以 为用户发现新的潜在感兴趣的资源，但是具有稀疏性和扩展性等缺点。此改进的 协同过滤是在考虑如何综合优化这两种协同推荐而展开研究和讨论的。 ( 3 ) 提出一种个性化推荐融合算法。基于内容的推荐存在以下不足之处：信息 挖掘不全面、推荐的内容有限、缺乏用户反馈。这样不利于挖掘用户潜在的兴趣。 而传统的协同过滤推荐的效果相当显著，但是冷开始和稀疏问题影响着系统的运 行，融合推荐就是为了研究和实现如何综合利用基于内容推荐和协同推荐的两者 的优点，进而来为推荐系统服务，提高推荐系统的质量。 ( 4 ) 提出一种调和项目预测评分的策略。由于用户对资源的苛刻程度不同，即 使用户兴趣相投，但是也可能出现对项目的平均评分相差很大的情况，针对这样 的情况，提出一种预测评分的机制，解决这类问题。 ( 5 ) 研究开源全文搜索平台l u c e n e ，并对以上算法进行仿真实验。 1 4 组织结构 本文的结构如下： 第一章介绍了个性化搜索引擎研究的背景意义、课题来源和研究内容，并给 出了论文的结构安排。 第二章介绍了搜索引擎和个性化推荐技术的概念、原理，以及基础研究、关 键技术等。为后文的研究工作提供了理论基础。 第三章在解决用户矩阵稀疏性、扩展性问题基础上，提出了协同过滤优化的 模型，并进行了实验验证。 第四章引入了融合思想，重点讨论了如何利用现有推荐技术融合，并实现了 融合推荐的算法模型，在理论上解决了现有推荐系统稀疏性问题，扩展性问题， 新项目问题，用户潜在兴趣难以挖掘等。 第五章基于第三章、第四章的研究成果，从实际情况出发，建立原型系统， 解决了现有推荐系统存在的一系列问题，以及避免了通常由于算法优化而会引起 3 个性化搜索引擎推荐算法研究 的时间损失，并构造实验，实验结果表明，上述研究有效提高了推荐系统的推荐 质量和可靠性。 最后是对本文的总结及对今后工作的展望。 4 硕士学位论文 第2 章搜索引擎和个性化 随着网络技术的应用与发展，网络资源飞速膨胀，互连网已经成为信息的重 要来源。简单通用的搜索引擎已经不在适合人们不断变化的需求，人们需要一个 能根据特定用户不断变化的兴趣需求自动推荐资源给人们。为了满足人们的这些 需求，我们分两部分来介绍：搜索引擎与个性化推荐技术。 2 1 搜索引擎 中国互联网络发展状况统计调查【l l 的统计结果表明，中国网络规模继续呈现 持续快速发展的趋势。截至2 0 0 8 年底，中国网页总数超过1 6 0 亿个，较2 0 0 7 年 增长9 0 。中国网民规模达到2 9 8 亿人，较2 0 0 7 年增长4 1 9 ，中国网民规模 已跃居世界第一位。 如何快速、准确、方便地从如此庞大的信息资源中获取自己需要的信息，是 互联网用户面临的一个重要问题。 在这样的背景下，搜索引擎技术迅速发展，成为最热门技术之一。不过，搜 索引擎从其出现开始，就一直是一种高门槛的技术，他的发展包括学术权威的众 多先进思想和设计，其涉及到学科包括自然语言处理，信息检索、数据库、数据 挖掘、分布式处理、人工智能，离散数学，排列组合，编译原理等多个领域的理 论和技术，因而具有综合性和挑战性。因此，设计一个性能良好并且使用性能强 大搜索引擎并非易事。 搜索引擎以一定的策略在互联网中搜集，对信息进行理解、提取、组织和处 理，并为用户提供检索服务，从而起到信息发现的目的，互联网用户使用网络 获取信息过程中，搜索引擎也成为必不可少的工具。 2 1 1 搜索引擎的概念 搜索引擎( s e a r c he n g i n e ) 是通过一些技术对互联网上的信息资源进行整理， 并以一定的规律组织起来，在用户输入查询后，返回匹配资源的系统。 2 1 2 搜索引擎的发展现状 搜索引擎1 2 】自1 9 9 4 年初，第一代真正基于w w w 的搜索引擎l y c o s 诞生。第 一代搜索引擎以人工分类的目录分类为主，代表厂商是y a h o o 。其特点是把网站 放在各种目录下进行聚类。但随着网络应用技术的发展，用户更希望对内容进行 查找，于是就出现了关键词查询的搜索引擎，即第二代搜索引擎。 个性化搜索引擎推荐算法研究 最有代表性的是g o o g l e ，它使用关键词进行网页搜索，内容可以覆盖互联网 大部分的网页内容。与第一代搜索引擎相比，第二代搜索引擎在收录范围、更新 频率、检索能力、查全率、查准率、响应时间、结果输出、用户负担等性能方面 均有了很大地提高，但仍然存在不少局限性，比如信息丢失、返回过多无用信息 等等。在这种背景下，出现了第三代搜索引擎。中搜( h t t p ：w w w z h o n g s o u c o r n ) 就是第三代搜索引擎的典型代表。它是在第二代搜索引擎基础上通过其领先的文 本分析及集合技术优化搜索结果，实现了人工智能和搜索引擎技术的进一步结合。 毫无疑问，随着搜索技术的不断发展，未来第三代搜索引擎的功能会得到不断地 加强，能够为用户提供更快、更准、更方便的查询。 据n e t r a t i n g s 的最新数据显示，2 0 0 5 年12 月份全球6 5 个搜索引擎的搜索 总量达5 0 多亿次，其中8 0 以上的搜索量来自三大搜索引擎g o o g l e 、y a h o o 和 m s n ，g o o g l e 己经占据美国在线搜索市场的一半份额；2 0 0 5 年百度公司的成功 上市创造了中文搜索引擎的神话；2 0 0 5 年1 1 月1 7 日g o o g l e 公司的股价一度超 过4 0 0 美元。这一切都说明搜索引擎已经成为互联网的第四桶金。 从19 9 4 年起，因特网在中国开始蓬勃发展，到19 9 7 年国内开始发展面向中 文信息检索的中文搜索引擎。由于中文信息处理较英文信息更为复杂，中文搜索 引擎的研制也是最近几年才兴起，但其发展却十分迅速。据“中文导航及搜索引擎 指南”统计，目前国内较完备的搜索引擎有1 3 1 个，中文繁体搜索引擎2 1 4 个，这 些还不包括一些开展信息服务的图书馆等其他信息服务网站。其中，用户常用的 搜索引擎有g o o g l e 、百度、新浪、搜狐、雅虎中文、天网、网易等。近年来国外 一些网络企业也开始瞄准中国互联网这一潜在的巨大市场，先后推出了一些中文 版的搜索引擎 我国对中文搜索引擎的研究工作已经全面展开，涉及的领域相当广泛，但专 业性、针对性强的研究成果还不是很多，在很多方面暴露出以下不足： ( 1 ) 语言理解能力不强，不能满足用户个性化的需求 当前急需解决的问题是根据用户仅有的几个输入词以及用户背景，来猜测用 户要查什么，即：在现有通用搜索引擎的基础上，理解用户的需求和查询的兴趣， 以及其认识的背景，使结果更加符合用户需求。 ( 2 ) 查询精度不高 目前搜索引擎动辄返回百万条结果，查询结果精确方面不够理想。用户通常 为大量的与查询无关的返回结果所困扰。 ( 3 ) 中文分词 中文信息处理较英文信息更为复杂，英文有天然的空格来切词，而中文没有， 要得到更精确的返回结果，则首先必须提高中文分词的精确度。 ( 4 ) 处理动态网页能力弱 6 硕上学位论文 目前许多搜索引擎的查找对象仅仅为静态页面，搜索引擎的搜索范围应扩大 到动态页面。 ( 5 ) 网页覆盖面有限 据权威统计，目前搜索页面最多的搜索引擎也只能达到信息量的4 0 左右。 2 1 3 搜索引擎原理 在用户输入查询关键词时，搜索引擎搜索的实际上是预先处理好的资源索引 文件。 搜索引擎工作原理，可以看做三步：从互联网上抓取网页_ 建立索引数据库 一在索引数据库中搜索。 利用s p i d e r 程序从互联网上收集网页，搜索引擎抓到网页后，还要做大量的 预处理工作，然后由分析索引器对收集回来的网页进行分析，提取相关网页信息， 然后用这些相关信息建立网页索引数据库。在索引数据库中搜索，当用户输入关 键词搜索后，由搜索程序从网页索引中找到符合该关键词的所有相关网页。 互联网虽然只有一个，但各搜索引擎的能力或针对领域不同，所以抓取的网 页各不相同，排序算法也各不相同。大型搜索引擎的数据量达到几千t 甚至几万 t 。但即使最大的搜索引擎建立的索引数据库，也只能占到互联网上普通网页的 不到3 0 ，不同搜索引擎之间的数据重叠率一般在7 0 以下。除了一些被称为信 息孤岛的网页，互联网上有更大量的网页，是搜索引擎无法抓取到的。 2 1 3 1 搜索描述语言 一个搜索引擎由搜索器、索引器、检索器和用户接口四部分组成【引，如图2 2 所示。 图2 1 搜索引擎架构 ( 1 ) 搜索器 通常是通过一个叫s p i d e r 的程序工具，在互联网中爬行搜集信息。它通常用 7 个r 丰化搜索引擎推荐算法研究 来尽可能多、快地搜集各种类型的信息，因为互联网上的信息更新很快，所以要 定期更新旧信息，避免死连接和无效连接。目前有两种搜集信息的方法： 一种方法从一个起始u r l 集合开始，可以是以队列的逻辑方式存储，顺着这 些u r l 中的超链接，以宽度优先、深度优先或启发方式循环地在互联网中搜集信 息。这些起始u r l 常常是一些非常流行的、包含很多链接的站点( 如网易、新浪 等) 。 另一种将w e b 空间按照域名、i p 地址或国家域名划分，每个搜索器负责一个 子空间的进行搜索。 搜索器搜集的信息类型多种多样，包括h t m l 、t x t 、p d f 、x m l 、w o r d 、p p t 、 多媒体信息等。 搜索器的实现常常用分布式、并行计算技术，以提高信息发现和更新的速度。 ( 2 ) 索引器 索引器的功能是对搜索器所搜索的信息进行处理，从中抽取出文档索引特征 项，用于表示文档以及生成文档的索引。 索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关，如 作者名、地址、更新时间、编码、长度、链接流行度等等；内容索引项是用来反 映文档语意内容的，如关键词及其权重等。内容索引项可以分为单字索引项和多 字索引项( 或称短语索引项) 两种。单字索引项对于英文来讲是英语单词，因为 单词之间有天然的分隔符( 空格) ，比较容易提取：而对于中文等连续书写的亚洲 或其它语言，则必须进行词语的切分。 在搜索引擎中，一般要给单字索引项或多字索引项赋予一个权值，以表示该 索引项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有统 计法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。 索引表一般使用某种形式的倒排表( i n v e r s i o nl i s t ) ，即由单字索引项或多字 索引项查找相应的文档。索引表也要记录索引项在文档中出现的位置，以便检索 器计算索引项之间的位置关系，而确定关键词与文档的关系。 索引器一般使用集中式索引算法或分布式索引算法。当数据量很大时，必须 实现即时索引( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息资源急剧增加的速度。一 个搜索引擎的性能在很大程度上取决于索引的质量。 ( 3 ) 检索器 检索器的功能是根据用户的查询关键词在索引库中查找出相关的文档，进行 文档与查询关键词的相关度计算，对将要输出的结果进行排序。 ( 4 ) 用户接口 用户接口的作用是输入用户查询关键词、显示查询结果、提供用户反馈机制。 用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查询 8 硕十学位论文 关键词的文本框；复杂接口让用户对查询进行限制，如逻辑运算( 与、或、非) 、 相近关系、域名范围( 如e d u 、t o m ) 、出现位置( 如标题、内容) 等等。目前一 些公司和机构正在考虑制定查询选项的标准。 2 1 3 2 现有搜索技术分析 ( 1 ) 查询以主关键字为主。而没有考虑语义或词语关系。以孤立的关键字表示 文档时，就割裂了原始文档的逻辑语义，可以用自然语言接口来解决这个问题。 在自然语言中，有很多方法可以表达一个询问的概念。 ( 2 ) 查询结果的选择主要根据文章中是否有关键字。而单独使用词语不能确定 页面内容，业常会导致检索结果的准确性不高。在选择结果时，判断用户的意图， 根据用户的需求，检索满足要求的页面。用户在查询时常常是由模糊到准确，用 户的连续查询行为常常反映出他的实际查询需要。应该允许用户进行二次查询。 ( 3 ) 结果的表现形式过于简单，往往是以列表的形式，并以某种优先级排序。 由此用户常常不能对结果进行进一步分类或聚类，如是应用还是理论，或是某个 领域。 2 1 3 3 搜索引擎评价标准 一般来说，搜索引擎的评价标准主要有收录范围、检索功能、结果显示、检 索效率、用户接口几个方面。 ( 1 ) 收录范围 每种搜索引擎都有特定的收录对象。若是专题型搜索引擎，它会侧重于某个 方面或领域：若是综合型的搜索引擎，则它检索到的信息比较全面。 ( 2 ) 检索功能 全文搜索引擎所提供的检索功能虽略有不同，但大致包含布尔逻辑、词组查 询、相近检索、限制字段等功能，或进一步提供相似性反馈信息、关键词检索、 自然语句输入等较先进功能。目录式搜索引擎则是一步一步地由间单到详细访问 目录，使结果更加详尽。 ( 3 ) 结果显示 查询结果的输出方式也是评价的重点之一，因为输出方式不好业会阻碍浏览 的效果。系统根据资源与查询关键词的相关性来排序，最相关的资料就会排在前 面，有些系统允许使用者自定义资料显示的数量，可节省结果计算时间，另外显 示资料的详细程度也会影响资料的参考价值。 ( 4 ) 检索效率 在评价检索效率时可从查全率、查准率及反应时间等方面考虑。查全率是检 出的相关文献量与系统文献库中相关文献总量的比率。查准率是指所检出的相关 文献占所有检出文献的比率。查全率和查准率是衡量检索系统检索效果的两个最 9 个性化搜索引擎推荐算法研究 重要的指标，两者结合使用能反映一个检索系统的基本检索效果。 ( 5 ) 用户接口 用户接口的设计也是一个相当重要的因素，如果用户接口设计不良，即使查 询功能再多、再好，也可能无法吸引大量用户使用。 2 1 4 搜索引擎分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎( m e t a s e a r c he n g i n e ) ，其他还有集合式搜索引擎、门户搜索引擎、免费链接列表等。 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、 f a s t a l l t h e w 曲、a l t a v i s t a 、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 、 中搜等，它们都是从互联网上搜集网站信息而建立索引数据库，检索与用户查询 条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是真 正的搜索引擎。 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅 是按目录分类的网站链接列表而已。用户完全可以不用进行关键词( k e y w o r d s ) 查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表性的y a h o o 雅虎。 其他著名的还有o p e nd i r e c t o r yp r o j e c t 、l o o k s m a r t 、a b o u t 等。国内的搜狐、新 浪、网易搜索也都属于这一类。 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将 结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等( 元搜 索引擎列表) ，中文元搜索引擎中具代表性的有搜星。 2 1 5 搜索引擎的发展趋势 搜索引擎已成为一个新的研究领域。它要用到信息检索、人工智能、计算机 网络、分布式处理、数据库、数据挖掘、自然语言处理等诸多领域的理论和技术， 具有很强的综合性和挑战性。又由于搜索引擎有很好的经济价值，所以引起了世 界各国计算机科学界和信息产业界的高度关注，并出现了很多值得注意的动向【引。 注重信息查询结果的精度，用户在搜索引擎上进行查询时，并不很关注返回 结果的数量，而是看结果是否符合自己的需求，越靠前的结果是否越能够与需求 相吻合。而传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在如此 大量的结果中筛选。为了解决返回结果太多的问题，目前出现了几种方法： ( 1 ) 通过各种方法获得用户没有在查询语句中表达出来的真正意图，包括跟踪 用户行为，分析用户模型，让用户告诉搜索引擎哪些文档和自己的需求相关，哪 些不相关，通过多次交互逐步求精，进一步筛选出更符合用户需求的结果。 ( 2 ) 用正文分类( t e x tc a t e g o r i z a t i o n ) 技术将结果分类，用户可以只浏览自己感 1 0 硕十学位论文 兴趣的类别。 ( 3 ) 是进行站点聚类或内容聚类，减少信息总量。 个性化服务使用获得的领域模型( 如w e b 知识、信息处理、与用户兴趣相关 的信息资源) 、用户模型( 如用户背景、兴趣、动作行为、风格) 知识进行信息搜集、 索引、过滤，并自动地将搜索引擎认为用户会感兴趣的、对用户有用的信息递交 给用户。其具有不断学习、适应用户兴趣动态变化的能力，从而提供个性化的服 务。 搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有 千秋。但当系统数量级规模到达一定程度( 如网页数达到亿级) 时，必然要采用分 布式方法，提高系统性能。搜索引擎除了用户接口外，都可以进行分布式处理运 行：网络蜘蛛可以在多台机器上进行信息搜集，以提高资源更新的速度；索引器 可以在不同的机器上建立索引；检索器可以在不同的机器上进行并行检索，以提 高检索的速度。 交叉语言信息检索是指用户用一种语言提交查询，搜索引擎可以在多种语言 的索引数据库中进行信息检索，返回多种语言的文档。返回结果可以用用户提交 使用的那种语言显示。这对于经济全球化的今天，无疑具有很重要的意义。 2 2 个性化搜索引擎 个性化搜索引擎是知识经济发展的客观必然要求。知识经济下的竞争是知识 和知识创新能力的竞争。在这个日益开放的信息服务市场环境里，用户不断动态 变化的信息需求正成为信息系统不断求新发展的动力，而“以用户为中心这一 服务理念早已经深入到各个行业的每个角落。 个性化推荐系统【3 】也因为最能完美体现这一服务理念而越来越被各界所关 注。个性化推荐系统涉及到许多的技术，如用户建模技术、推荐技术、用户隐私 保护技术等。 2 2 1 用户建模 个性化推荐系统的基础和核心是用户模型【2 1 ，个性化推荐系统的主旨目标是 为用户提供满足其个性化需求的服务，所以首要的任务是把特定用户的个性信息 需求表达清楚，用户模型则是进行形式化描述用户需求的最好方法。 用户模型问题是指与使用系统有关的用户信息的组织。主要涉及到两个方面： 一是模型获取的方式；二是用户及其需求的特征表达，也就是说用户的个性特征 及其需求的个性化特点的描述。研究模型的获取方式可以验证用户参与对系统产 生怎样的影响以及系统今后如何进行改进以减少用户投入。用户的个性化信息需 求表达则因人而异，这主要是因为这些个性化信息的表达还要受用户的教育程度、 个性化搜索引擎推荐算法研究 所从事的专业领域、对计算机技术掌握的程度及个人特征( 如年龄、性别甚至亲属 朋友的情况) 等的影响。 2 2 1 1 用户描述 用户描述( u s e rp r o f i l e ) t 3 】是为了对个性化系统的用户进行研究，发觉用户的 背景兴趣和浏览习惯，描述用户特征，而展开的跟踪用户的一系列动作和行为。 在收集用户的信息之前，首先需分析用户愿意提供什么信息，用户一般都很 注意个人信息的保密性，w w w c y b e r d i a l o g u e c o r n 的调查显示，8 0 的用户愿意向 w 曲站点提供自己的姓名、性别、年龄、教育背景和兴趣，但大多数用户不愿意 提供私有、敏感的信息，比如个人收入和信用卡号等，该公司另一项调查显示， 2 8 的用户愿意w e b 站点向其他w e b 站点共享自己的信息。 在制定用户描述文件之前，需考虑下面几个问题： ( 1 ) 了解用户，并衡量描述用户的工作是否到位，是否描述出真实用户特性? ( 2 ) 是否有现成标准? 现有标准是否完善? ( 3 ) 收集什么样的数据，收集的数据用于何种目的? 用户是否愿意提供此数据? ( 4 ) 如何收集数据? ( 5 ) 如何组织收集的数据? ( 6 ) 用户信息能否自适应地更新?