【毕业学位论文】（Word原稿）面向主题搜集系统中搜集策略的研究与评测-计算机系网络与分布式系统

北京大学学士论文第 1 页 论 文 评 定 意见评语 : “面向主题的搜索引擎”，是我们“天网”搜索引擎下一步发展的重要方向之一。龚笔宏同学的毕业论文，是这一新方向的良好开端。 论文所涉及的工作包含了对搜索引擎技术的一般认识，通用搜索引擎和面向主题搜索引擎的对比，面向主题搜索引擎的基本工作方式，以及在各个环节中所涉及的有关算法对比与分析；而且，将上述知识和认识有效地应用到了程序设计实践中，高质量地完成了一个面向影视主题的搜索引擎系统，搜集了几十多万影视信息，在影视信息方面提供 着比“天网”通用搜索引擎更有效的服务；论文内容丰富，所涉及的工作量大，且有较强的系统性，是一篇优秀的本科毕业论文。 在毕业设计工作的过程中，龚笔宏同学态度端正，积极努力，精力集中，独立思考，表现出很强的进取精神和踏实的工作作风，为“天网”的发展做出了贡献。 老师签名 :_李晓明 _ 北京大学学士论文第 2 页 摘 要 天网 中英文搜索引擎是具有中文特色的搜索引擎 ,但是随着当前网络的不断增长 ,以及用户应用的不停变化 ,通用的搜索引擎已经不能应付各种不同的检索请求 . 面向主题 的搜集系统是针对一个主题，一类网页的搜集系统 ,也就是说只搜集整个网络的一个特定子集 . 所谓主题 ,可以用一系列例子页面来确定 ,也可以用一系列的特征词来确定 . 搜集的目标就是 与例子页面在内容上类似的页面 . 我们对目前所采用的各种面向主题的搜集 算法进行了研究 ,同时进行了初步的评估 确定了一套搜集算法 . 这套算法是基于原有的天网搜索引擎 ,而实现的 准确的进行同主题搜集 .,根据实现的结果说明面向主题搜集的优势所在 ,以及其发展的可能性 . 本文的大纲如下 : 本文首先说明了什么是通用的搜索引擎 , 什么是面向主题的搜集系统 ,以及此二者的区别 . 接着提出了几种搜集策略 , 总的来说 ,把面向主题的搜集系统分为三个部分 : 搜集例子 , 特征提取 ,根据特征进行搜集 . 对这三部分 各分析了几种策略 ,同时进行了分析 ,评估 . 然后介绍了目前我们所实现的策略 . 我们主要采用的是基于向量空间模型 , 结合天网的特点 的特征提取 . 搜集方面我们主要加入了对连接关系的考虑 ,对出度入度的考虑 , 接着对我们的工作进行了总结 ,评价了所实现的系统 ,说明面向主题比通用搜索引擎的区别 ,以及其优势 . 最后是对未来工作的展望 , 现有系统的不足以及改进 关键词：搜索引擎 ,主题 ,文本分类 ,特征提取 ,连接关系 ,信息挖掘 北京大学学士论文第 3 页 目 录 论文载要 . .目录 . .一章 面向主题的搜索引擎 4 索引擎的介绍 . . 4 1. 搜索引擎的使用 2. 搜索引擎的分类 3. 搜索引擎的未来 向主题的搜索引擎 . 6 者的区别比较 8 第二章 天网搜索引擎的介绍 . 网系统简介 网总体结构 . 第三章 搜集策略的研究和比较 . 12 述 . .定目标样本 . 13 征提取部分的几种策略 . 13 集部分的策略 . 结 .四章 我们的实现 21 统结构 21 征提取部分的实现 22 集部分的实现 24 作结果及对结果的评价 27 第五章 总结 . 28 参考文献 29 北京大学学士论文第 4 页 第一章 面向主题的搜索引擎 索引擎的介绍 1 1993 年， 出现了最早的 览器 年 出了 览器的发展促使 到迅速推广 推动着搜索引擎的发展 . 1994 年初， 出现了包括 内的第一批 索引擎，同年还成立了 后者成为了近年来最成功的商业目录。 搜索引擎能够帮助网民在浩瀚网 海中 ,找到自己所需要的内容 一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务 . 按 止 2000 年 6 月 30 日的调查表明，按 1690 万网民计算，目前使用过搜索引擎网民共有 1570 万左右。 搜 索引擎，在网民上网经常参与的活动中列第三位，有六成左右的网民将其列为经常使用的网络服务，仅次于电子邮件与浏览新闻，超过了网上聊天或网上下载或上传软件等活动 . 2. 搜索引擎的分类 按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类： 基于 搜索引擎 这种搜索引擎的特点是利用一个称为 叫做 程序自动访问 点， 搜集 站点上的网页，并根据网页中的链接进一步 搜集 其它网页，或转移到其它站点上。 集的网页 经过分析处理后 ,建立索引 ,加入数据库中。 用户查询时 ,检索数据库 ,返回结果 . 最早出现的搜索引擎就是利用 建立数据库， 搜索引擎 这个词的原义也只是指这种狭义上的基于 搜索引擎。 它的缺点： 并不能真正反映出网页的质量 , 返回信息过多，有很多无关信息 它的优点 : 信 息量大、更新及时、毋需人工干预 例子 : 如 天网 基于 目录（ 叫做 搜索引擎 以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要，并将 站点 置于事先确定的分类框架中。 当用户查询某个关键词时，搜索软件只在这些描述中进行搜索。目录 一般都是依靠一群专职编辑来建立和维护的 . 出名的商业目录用了大约一两百名编辑 来维护目录 北京大学学士论文第 5 页 它的缺点 : 需要人工介入、维护量大、信息量少、信息更新不及时 它的优点 : 信息准确、导航质量高， 例子 :如 目前 提供了目录式服务 索引擎 (也叫 “元搜索引擎 ”) 索引擎也叫做 的特点是本身并没有存放网页信息的数据库，当用户查询一个关键词时，它把用户的查询请求转换成其它搜索引擎能够接受的命令格式，并行地访问数个搜索引擎来查询这个关键词，并把这些搜索引擎返回的结果经过处理后再返回给用户。 它的缺点 : 不能够充分使用所使用搜索引擎的功能 , 擎的高级搜索功 能 它的优点 : 实现起来比较简单 , 返回结果的信息量更大、更全 例子 : 经过了多年的发展之后，现在的搜索引擎功能越来越强大，提供的服务也越来越全面，它们的目标是把自己发展成为用户首选的 口站点，而不仅仅是提供单纯的查询功能。 搜索引擎未来的发展面临着两大难题： 1)发展速度， 近几年来 速扩张，其上的站点和网页越来越多 ,再大型的搜索引擎也不可能做到真正的 一网打尽 2) 当搜索引擎的数据库越来越大时，用户查询同一个关键词所得到的结果也就越来越多， 然而成千上万的结果对用户并没有什么实际意义，用户关心的是能否迅速在开头几十个结果中找到自己需要的信息 面对着这两个难题，目前很多搜索引擎都在发生一些变化，这些变化中包含着搜索引擎未来的发展趋势。 个性化服务 使用自动获得的领域模型 ,用户模型 (如用户背景 ,兴趣 ,行为 ,风格 )等进行信息采集 ,索引 ,过滤 (包括兴趣过滤和不良信息过滤 )对用户有用的信息提交给用户 . 目录占据主导地位 北京大学学士论文第 6 页 目录与基于 搜索引擎相比更具优越性，这一点已为大多数人所接受， 在今后的发展中，目录将会占据主导地位，而基于 搜索引擎将更多地以辅助工具的面貌出现。 采用分布式体系结构提高系统规模和性能 当系统规模越来越大的时候 ,必然要采用某种分布式的方法 ,以提高系统性能 ,都可以进行分布式 :如 :以在多台机器上相互合作 ,相互分工的进行信息发现 . 特殊搜索引擎越来越多 搜索引擎的另外一个发展趋势是特殊搜索引擎越来越多，这些特殊搜索引擎只收集了某个方面的网站或网页，例如文学、医学、体育、音乐、件等等，其中的内容一般都要 比通用搜索引擎更好更精，因此很受用户的欢迎。建立特殊搜索引擎的成本要远小于通用搜索引擎，这也促进了它的发展。 也就是本文所要介绍的 面向主题的搜索引擎 . 向主题的搜索引擎 面向主题 ” 目前 ,通用的搜索引擎确实有了很多的发展 ,从技术以及硬件条件上 ,都有了很大的变化 ,但是事实上 ,即使最大的搜索引擎目前也仅能覆盖 30%网络 一般需要几个星期 ,甚至几个月 这主要是因为通用的搜索引擎的一个主要指导思想是 ”一网打尽 ”他们试图迎合每一种可能出现的查询请求 ,虽然这种讲究高覆盖率的搜索引擎是有其不可估量的价值 ,但是却往往导致了 其搜集的网页 ,在内容上过于分散 往往导致查询时 ,有很多并不相关的网页 . 因此随着网络的发展 ,我们需要一种新形式的搜集系统 . 很容易的我们想到 ,用 相关度 以及 网页质量 来过滤搜集的网页 对于一个个人来说 ,他所关心的始终只是一小部分 收藏起来 ,然后他所关心的也就是与这些例子类似的网页 . 因此通用的搜索引擎是不 适合这种目的的 基于关键字(查询是很难达到这种目的 : 将网页正确的与某个主题联系起来 我想查 唱 歌手 李小龙 , 如果用通用的搜索引擎的话 ,他很可能把拍武打片的李小龙 , 甚至是 263 的李小龙全都返回 结果会好一点 让用户很沮丧 . 北京大学学士论文第 7 页 正是因为有许多是通用的搜索引擎所无法实现 ,或实现的不好的 ,因此我们就需要有一种小巧 ,精致的搜索系统 面向主题 ” 面向主题 就是只针 对一类主题 ,一类网页 , 例如文学、医学、体育、音乐、件等等 ,进行搜集 . 也就是说只搜集网络的一个子集 主题 : 也就是用户所要搜集的类型定义 也可以由一系列描述类型特征的特征词来确定 . 相对与通用的搜集系统而言 ,它更为小巧 但是 其中的内容一般都要比 通用的 搜索引擎更好更精，因此很受用户的欢迎。建立 面向主题的搜集系统 的成本要远小于 通用的 搜索引擎，这也促进了它的发展 . 它所涉及的主要技术 有 :信息挖掘 ,文本分类 ,文本提取 ,网络搜集 ,入度出度 等等 先有用户确定一系列的样本网页 ,来确定所搜集的主题 , 然后进行特征提取 , 分析样本网页 ,提取特征信息 ,之后再搜集过程中 ,根据这些特征信息 ,对每一个搜集的网页 ,都赋予一定的相关度 就说明 与主题越相似 . 目前国内的面向主题的搜集系统还出于起步阶段 ,尚没有很成熟的系统 也就是分类的搜索 ) 一般都是采用人工分类的形式 只要面向主题的搜集 算法足够好 ,在很大程度上可以代替这种人工分类的 方法 . 好的 ”面向主题搜集系统 这也就涉及到面向主题的 评价指标的问题 速度快 所谓速度快 ,不是指一台机器每天能搜集多少网页 ,而是说能够在尽可能快的时间能覆盖大面积的网络 如果说通用的搜索引擎需要 10 天来覆盖 30%的网络 ,那么 面向主题只需要 3 天就能够覆盖 30%的网络 . 聚集度高 也就是搜集到的网页 ,必须是高度相关的 , 不允许将主题外的搜集进来 , 覆盖完全 也就是说覆盖尽可能大的网络 ,保证每一个属于主题内的网页被搜集也就是 (完全性 ),而第二点 是保证 , 每一个被搜集的 都是主题内 北京大学学士论文第 8 页 者的区别比较 对于通用的搜索引擎和面向主题的搜索引擎 ,二者之间是有差别的 ,面向的需求不同 ,各有千秋 ,或是有了通用的就不要面向主题了 . 面向主题的搜索引擎 (下简称为 主题 ) 与通用的搜索引擎 (下简称为 通用 )有一下几点区别 : 目的不同 通用 : 搜集尽可能多的网页 , 一网打尽 主题 : 搜集某一领域内的网页 . 兵贵在精 面对需求不同 通用 : 各种 各样的检索请求 主题 领域内部的检索请求 策略不同 通用 : 面对各种不同的网页 ,一视同仁 ,同样处理 主题 :对于各种不同类的网页 ,区分对待 表 1二者的区别 通用的搜索引擎 面向主题的搜索引擎 数据量大 : 这是因为它搜集所有的网页 数据量小 : 这是因为它只搜集部分网页 ,其余的都抛弃了 更新慢 : 因为其数据量太大 ,更新一次往往要数周 ,甚至上月 更新快 : 因为数据量小 ,能够迅速更新 ,周期只要数天即可 . 博而不精 : 数据量大 ,但是太过 分散 ,没有重点 精而不博 : 数据量小 , 集中 ,但是只限于本领域 数据不完全 : 这里指的是相对与它的搜集目标而言 ,最多覆盖网络的 30数据较完全 : 相对与它的搜集目标 ,因为本来该领域范围内的网页就少 ,就可能搜集的较完全 硬件需求高 : 通用的往往需要上 G 的内存 ,上百台的机器才能使得搜集成一定规模 硬件需求低 : 目前我们的搜索引擎仅用了一台机器进行搜集 . 北京大学学士论文第 9 页 问题 : 如我们搜 游泳 方面的信息 游泳 , 和用面向主题的搜集 系统搜集 游泳 领域 , 结果有区别马 ? 答案 : 当然有区别 , 1) 用面向主题 , 我们可能搜集出 网页中不出现 游泳 ,但是确实与游泳的相关的网页 , 如讲述泳镜之类的网页 2)只要例子网页选择的好 , 面向主题所搜集的大部分都是与游泳相关度高的 ,而通用搜索引擎就做不到这一点 3) 也就是面向主题的搜集系统所搜集的相关网页必然多于 通用所检索得到 . 因此 ,我们可以看出 ,在网络蓬勃发展的今天 ,发展面向主题的搜索引擎是很有必要的 . 北京大学学士论文第 10 页 第二章 天网搜索引擎的介绍 网系统简介 因为我们所实现的面向主题的搜索引擎 ,是基于天网搜索引擎之上完成 天网中英文搜索引擎是主要针对中国 丰富的信息资源而开发的具有中文特色的搜索引擎。天网属于基于 搜索引擎范畴，主要采取了基于服务器模式具有导向功能的搜索和提供文本摘要的方式。在实现中，天网使用了中文自动识别和中文编码自动转换技术、根据中文的语言特点和表达习惯对中文信息进行词语切分和词类标注技术以及基于词 的大型、高效的信息索引数据库和快速准确的检索技术等先进的中文信息处理和索引技术，从而大大提高了中文信息的理解程度和发现、检索效率，同时也提高了汉语的查准率。 目前 天网由若干 主控 (导向控制下，使用具有高度智能性和适应性的信息发现算法搜索网页，提取关键词及摘要，形成原始数据库，然后在此基础上建立索引数据库。 来自前端的用户信息，传给检索服务器，经过查询优化，产生结果回送用户。 天网搜索引擎的检索是基于词汇的，克服了中文分词的困难，同时具有中英文词汇自动学习 的能力。 它侧重于中文信息的发现，向全世界的中文用户提供准确、有效的网络中文信息。 天网搜索引擎具有以下技术特征： 信息收集符合 相关协议和标准。 实用、高效的信息分析方法 高度智能性和适应性的信息发现方法 中文信息处理技术 可伸缩的分布式结构 基于词的大型、高效的信息索引数据库和快速、准确的检索方法 智能化、多功能的用户检索接口 天网搜索引擎目前访问量以及搜集网页数已经达到了千万 天网 由于采用了可伸缩的分布式结构、查询 引数据库和检 索数据库分开等先进、有效的技术，使得系统占用资源少、信息收集速度快、用户查询响应时间快（系统对 上的查询可在 1 秒钟之内作出响应）、查准率和查全率较高，基本达到了实用化程度。 北京大学学士论文第 11 页 网的总体结构 本系统主要由 息存取和分析子系统 ( 息搜集控制子系统 (资源索引数据库 (信息检索子系统 (管理和监控子系统 (几个部分组成 系统的结构图如下 : 档 存取分析子系统 搜集控制子系统 信息检索子系统 务器 资源索引数据库 览器 览器 2网的总体结构 理和监控子系统 存取分析子系统 北京大学学士论文第 12 页 第三章 搜集策略的介绍和比较 述 主题搜索的实现多种多样 ,但是如果把它们的框架去出来 ,都是大同小异 a) 确立例子网页 也就是由用户选择例子网页 ( 来确定系统所要搜集的主题 与主题相关性越强 ,最后搜集的效果越好 . 因为我们的整个系统的目标就是搜集 尽可能多的与例子网页尽可能相似的网页 若各自在内容上相关性不强 ,将会导致所提取的特征信息不具有代表性 ,是的搜集失败 . 因此用户应该慎重选择 例子网页 . b) 提取特征信息 其实是一个文本提取的过程 ,也就是 (有些系统如 (实现的系统 ,)把这一部分称为 它的目的 :根据 例子网页 ,用一系列的特征词 ,以及特征词权值来描述该主题 根据特征词 ,特征词权值而展开 . 特征词 :就是一个关键词 他能够标志主题的特征 标志了该特征词于该主题的相关程度 . 权值越高 ,说明该特征促于主题越相关 ,越 能够代表该主题的特征 . 因此特征词 ,以及其权值的选择 决定了系统搜集 的好坏 . c) 信息采集 其实是一个文本分类的过程 对网络中的网页进行筛选 系统运行前的准备工作 它的目的是根据前一步所确定的特征信息 ,搜集网页 尽可能于例子网页相关度高的网页 . 性能指标 :我们可以用以下两个性能指标来衡量搜集系统的好坏 : 北京大学学士论文第 13 页 召回率 (检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检索系统（搜索引擎）的查全率； 精度 (检索出的相关文档数与检索出的文档总数的比率，衡量的是检索系统（搜索引擎）的查准率。 对于一个检索系统来讲，召回率和精度不可能两全其美：召回率高时，精度低，精度高时，召回率低。 下面我们将分别对这三步骤中的策略进行详细介绍 . 定例子网页 确定例子网页 ,由用户确定几个主题典型的 用来配置系统 1. 几个 应该是同一个站点的 , 2. 几个 容应该于主题密切相关 3. 几个 好文字较多 ,这样文本提取的效果会较好 . 4. 几个 该是该主题中典型的网页 . 用户应该认真选择 征提取部分的几种策略 目的 : 根据 例子网页 ,用一系列的特征词 ,以及特征词权值来描述该主题 集应该 : 能体现例子网页所包含的内容 (完全性 ) 这是容易做到的 有了这一点我们就可以确定那些网页与目标相关 能体现例子网页所不包含的内容 (区分性 ) 这是难于实现的 但是因为目前并没 有一个很好的算法能够实现这一点 ,因此我们只能确定这个网页相关 ,并不能确定这个网页于主题不相关 下面将介绍两种用于特征提取的算法 : 1) 基于统计的算法 2) 支持向量机 ( 北京大学学士论文第 14 页 于统计的算法 每个网页 ,都会有一个 ,甚至不只一个主题 网页有的就只有 词 因此我们的算法就是把想办法把主题和这些词联系起来 . 顾名思义 ,基于统计的算法也就是 计其中出现过的关键词，建立关键词词典 ,根据每个词在网页中的出现次数 ,出现位置来计 算它的权值 ,最后 ,由这些信息 , 综合多个网页 , 来确定该主题的特征词 ,以及特征词的权值 . 答案 : 当然不是 . 类比与图象压缩处理中所提到的 ,经常出现的 ,所包含的信息量就越少 在网页中越常出现的 , 所包含的信息量就越少 ,比如基本上每个网页都会有 联系我们 这样的字眼 , 但是这种字眼对描述主题是没有任何作用的 . 这也就说明了 词频高的未必代表主题 . 也就是说 ,一个特征在文档中出现的次数越多 , 权 值越高 , 越多文档都出现了这个特征 ,则这个特征反而信息量小 ,权值越低 . 因此我们可以构造 权值评价函数 问题 : 将词频高的作为特征 词 ? 特征词的权值应该 : 正比 于 在文档内出现的频率 反比 于 出现了该特征的文档数 北京大学学士论文第 15 页 nk 01.0(lo g*)()g (其中 特征项 i 中的出项频数 ,N 表示全部文档的总数 ,征项的文档数 . 基于统计的算法 ,实现起来简单 ,思想直接 ,易懂 ,但是它存在很大毛病 ,就是对高频词的处理 ,词频太高 ,有可能是忽略词 ,或是无意义的词 ,词频太低 ,也就不具有代表性 这里的一个权衡就是很关键的 . 持向量机 (支持向量机 (一种机器学习的方法 通过训练文本 ,以自动寻找出那些对分类有较好区分能力的支持向量 ,由此构造出的分类器可以最大化类与类的间隔 假设训练文本为 ),(ii . 其中 , 也就是是一个 m 维的向量 . 1. 其中 表示 ,否则就是一个反面例子 . 法先执行了一个映射 , 从 m 维到 n 维空间的映射 ,通常 ,n 大大于 m.,这样 训练向量就被映射到一个 更高纬度的空间中 )( 这个超平面经过优化之后 ,保证 正面例子 和反面例子之间的 距离最大 .系数 W 可以写成 )(x 的线性组合 . W= 而这些i可以用一下的 二次方程解得 : 基于统计算法的评估 北京大学学士论文第 16 页 ( )= 1)()(21 而对于这些i还必须满足一下的约定 01Ni 同时 i 0 由此可以确定了 超平面 ,确定了 分类器 一种很复杂的算法 ,具体情况情参见参考文献 11 有较好的推广新能和较高的分类准确率 经被用于孤立的手写体识别 ,语音识别 ,人脸识别 其算法复杂 ,对于网页分类这种大规模的数据集而言 ,训练例子往往要很多 ,才能够找一个好的分类器 要的训练时间也太长 ,计算也太复杂 . 集 部分的策略 目的 :在运行中利用前一步得到的特征值信息 ,进行网页的搜集 . 搜集到尽可能于例子网页相似的网页 , 尽可能于例子网页相关度高的网页 下面我们将介绍两个搜集时的策略 1) 向量空间模型 2) 接关系的考虑 量空间模型 目标表示是指以一定的特征项 (即关键词 ,特征词 )来表示目标网页信息 ,目标表示的模型有很多种 ,常用的有 布尔逻辑型 ,向量空间型 ,概率型等 . 在 ,将例子网页经过特征提取之后 , 看作是由一组特征项 ( ., 构成 ,对于每一个特征项 ,根据其在网页中的重要程度 赋以一定的权值 所以例子网页可以写成用 (,(, ., 法 的评估 北京大学学士论文第 17 页 (n), 来表示 . 而所有待分类的网页都可以写成 ( ,其中 . 这样我们就构造一个 n 维坐标系 ,以特征项为其坐标轴 ,(w1, 其对应的坐标值 D(t1,t2, , 假设 例子网页的特征向量为 W,那么检验网页 D 和例子的相关程度 ,就装化为向量空间中 两个向量的夹角来度量 相似程度越高 相似度 (D,W)=,W)=其实就是计算两个向量之间夹角的余弦 ,这个值越大 ,角度越小 ,相似程度越高 , 还有些算法 ,也构架向量空间模型 ,但是并不采用上面的公式 ,而是采用一个函数 ,来对这两个向量进行计算 , 通过计算结果来判断相关程度 . 如 :最简单的线性函数 F(X)= D*W = jj 结果高的就认为相关程度高 . 据我所知 , 向量空间模型是比较形象的一种建模方式 ,实现起来也比较容易 . 但是有一个很大的缺陷 就是向量空间模型最初的提出主要是针对文本分类 于普通的文本 相比 ,档中有着很明显的标志符 ,结构信息更加的明显 ,对象的属性更加的丰富 将会遗漏了很多 有用的信息 . 向量空间模型的评估 北京大学学士论文第 18 页 接关系的考虑 (s 就是超链接文本 ,网络上的信息就是有许多的连接而组合在一起的 . 因此 ,我们在研究 档之间的关系时 ,这些连接就是一个很好的信息源 ,能够提供给我们许多有效的信息 . 所有对这些连接关系的研究都是基于一下两个假设的 : 两个 间存在连接 这两个 含相关的内容 许多网页都指向同一个网页 这个网页是很重要的 用图来表示 ,如下图 .(其中 A B 表示有一个从 A 到 B 的连接 ) 图 3说明假设 1 图 3明假设 2 但是 ,我们可以很容易的看出这个假设其实并不是完全正确 两个网页之间 存在连接 ,并不一定表示二者之间存在相关性 是 ,门户网站与各种各样的网页之间都存在连接 ,但是并不表示他们之间在内容上又相关性 下面介绍一种利用链接关系的算法 s 和 权威程度 ( 一个具有高权威程度的网页 ,就很有可能具有相关的内容 一个具有高中心程度的网页 ,就很有可能拥有指向相关页的连接 . 档 A 档 B A 于 B 相关 档 档 C C 是一个重要的页面 北京大学学士论文第 19 页 换句话说 ,也就是 , 一个网页拥有 许多指向其他相关页的连接 ,它的 高 . 而一个网页被许多 相关页所指向 , 它的 越高 . 更进一步说 ,一个网页如果拥有许多指向那些 的网页的连接 ,那么他的 当然就越高 一个 果被许多 指向 ,他的也就越高 . 在具体实现中 ,我们要注意几个问题 , 1. 在同一个主机中的网页 ,往往有一些互相之间的连接 ,比如什么 回到主页 之类的连接 , 但是这 种连接 是作者自己加入的 ,并不能又什么导航性 值的时候 ,这种连接应该不加以考虑 . 2. 在计算 ,时候 ,往往能以完全计算 ,算 ,只是一个出度 .而 涉及到入度 ,网海茫茫 ,入度 是无法完全计算的 如果入度已经达到了上限 ,就不再计算了 . 因此我们可以知道在具体实现的过程 ,我们只需要统计网页的入度 ,出度 , 根据入度出度统计网页的 ,以及 不断 被修改的 . 出度高的 , 往往 比较高 ,入度高的往往 高 . 这种算法充分考虑了超文本的特征 ,能够充分挖掘了链接所包含的信息 ,对发掘相关性有很大的帮助 . 但是 ,这种算法也有很大的弊病 . 1) 因为同一个主机上的一系列网页往往是同一个作者 ,那么他往往可能使得这一系列网页都指向一个他认为重要的页面 ,这样会大幅度 提高 该页面的 相关页 相关页 相关页 相关页 . . . . 关页 相关页 相关页 相关页 . . . . s 评估 北京大学学士论文第 20 页 2) 这种算法会导致 , 网页的 循环增大 . 比如说 , 网页 A 有一 个连接指向 网页 B 那么 B 的 增大 A 的 增大 而 A 的 增大 又会导致 B 的 增大 这样循环增大 ,将是导致算法一无是处 必须采用一定的策略来避免这一点 . 3) 不相关的节点 :这就是前面所提到过的假设其实并不完全成立 . 有些网页上往往会有一些连接是指向不相关的页面 ,这样的计算将会导致偏差 结 这一章我 们主要是介绍了 用于面向主题搜索的各种算法 1. 确定例子网页 2. 进行特征提取 3. 信息采集 在特征提取部分我介绍了两种算法 : 基于统计的算法 :也就是统计词频 ,经过一定的公式计算 其权值 ,取出 特定的作为特征项 . 支持向量机的算法 . 通过学习算法 ,自动寻找对分