【毕业学位论文】（Word原稿）基于网页的信息系统的一种预处理过程-计算机网络技术

北京大学 网络与分布式系统实验室硕士学位论文 北京大学硕士研究生学位论文 题目：基于网页的信息系统的一种预处理过程 姓 名：张志刚 学 号： 10108137 院 系：计算机科学技术系 专 业：计算机软件与理论 研究方向：计算机网络与分布式系统 导 师：李晓明 教授 2004 年 5 月 北京大学 网络与分布式系统实验室硕士学位论文 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 北京大学 网络与分布式系统实验室硕士学位论文 摘要 随 着 迅速发展， 的信息越来越丰富。 用方便、信息丰富，人们越来越多的使用 寻找需要的信息。为了更好的使用的信息，人们也不断的追求能够有效组织和利用网上信息的技术和系统。然而， 的信息存在很多问题：网页内的噪音内容多、 近似网页量大以及缺乏必要的元数据信息，这些问题严重影响了 息系统的服务质量。 针对 息系统的共性需求，本文提出了一个预处理框架及相应的方法。该预处理框架包括了三个预处理工作：网页净化、近似网页删除和网页元数据提取。通过预处理过程，原始网页 集中的近似网页被删除，而保留下来的网页被净化并转化为一个统一的结构化模型（称之为 该模型中提供了各个领域需求较多的元数据和内容数据， 它包括网页标识、 网页类型、内容类别、 标题、 关键词、摘要、正文、相关链接等元素。本文提出的预处理方法的一个重要优点是它不需要除原始网页以外的其他信息，而这些额外信息是该领域中其他方法所必须的；另一个优点是将 息系统的共性需求放到一个过程中一次性提取出来，可以避免相同中间过程的重复执行，从而提高信息提取效率。 本文中提出的预处理框架和方法已经应用到了“天 网”搜索引擎和网页自动分类系统中。通过使用预处理后应用系统质量的提高，验证了该预处理方法的有效性。不难看出，通过这样一个预处理过程，可以在任何一个网页集上（包括 建一个组织良好的、净化的、更易使用的信息层。 关键词： 万维网 , 数据预处理，数据净化，近似网页识别，元数据提取 北京大学 网络与分布式系统实验室硕士学位论文 of of eb eb to of ebs of In to eb eb eb in eb as in eb eb in of on of eb of eb eb of in In we a to of eb eb a of of of is no is to of in of 京大学 网络与分布式系统实验室硕士学位论文 of Its to a we up a on of eb eb 京大学 网络与分布式系统实验室硕士学位论文 目 录 第 1 章 引言 . 1 究背景 . 1 文研究内容 . 2 文贡献 . 3 文组织 . 3 第 2 章 相关研究 . 4 索引擎 . 4 页自动分类 . 7 息提取 . 9 数据提取 . 10 第 3 章 息系统面临的问题及共性需求 . 12 第 4 章 预处理方法与技术 . 14 处理框架及结果描述 . 14 处理框架 . 14 处理结果描述 . 14 页表示 . 15 页标签树表示 . 16 页量化表示 . 19 页净化 . 24 页类型判断 . 24 题网页净化 . 25 录网页净化 . 25 片网页净化 . 26 页净化时空效率分析 . 26 似网页的发现 . 27 似网页发现算法 . 27 能分析 . 29 页元数据提取 . 29 页元数据提取流程描述 . 30 北京大学 网络与分布式系统实验室硕士学位论文 文提取 . 30 键词提取 . 30 容类别判断 . 31 题提取 . 32 要提取 . 32 题相关超链提取 . 33 章小结 . 35 第 5 章 应用与评测 . 36 页净化在网页自动分类系 统中的应用与评测 . 36 用 . 36 测标准 . 37 测结果与分析 . 37 似网页消除在搜索引擎中的应用与评测 . 38 验设计 . 38 测标准 . 39 测结果与分析 . 40 页元数据在搜索引擎的索引过程中的应用与评测 . 41 索效率评测 . 41 索精度评测 . 42 章小结 . 44 第 6 章 总结与展望 . 45 结 . 45 望 . 45 参考资料 . 47 作者就读期间参加的科研项目和发表的论文 . 51 致谢 . 52 北京大学 网络与分布式系统实验室硕士学位论文 1 第 1章 引言 究背景 万维网（ 记为 因特网上最成功的应用，起源于 1989 年欧洲粒子物理研究室 最初计划是由 物理学家 1989 年 3 月提出的，第一个基于文本原型于18 个月后运行。 1991 年 12 月在德克萨斯州的 1 超文本会议上进行了一次演示，次年继续发 展，并于 1993 年 2 月，随着第一个图形界面发布而达到了其发展的高峰 1995 年 4 月， 网上的流量超过了 其它服务的流量，成为 的第一大应用服务。到 1997 年 12 月，网上大约有 3 亿 2000 万网页 根据 000 年的数据库数据表明，网页数目已经超过了 10 亿。 002 年 4 月索引网页表明，网页数已经超过 20 亿 而在 2004 年 4 月， 索引擎索引网页数已经超过 42 亿。 随 着 迅速扩展， 的信息也飞速膨胀。这一方面使得 一方面也使得其中绝大多数的信息对于绝大多数的用户是没有意义的，而且对于一个用户而言，极小部分的有用信息也淹没在无用信息中很难被找到。为了更好的使用 的信息，人们不断的追求能够有效组织和利用网上信息的技术和系统，包括搜索引擎、网页自动分类、信息提取以及主题搜索，等等。我们通常把以网页为处理对象的系统称为 基于网页的信息系统 ，为表达简单，本文中我们称其为 在相关的技术中，一方面涉及到对网页内容的分析，另一 方面也涉及到对网页间链接关系的分析。其最终目的是通过对 信息的有效组织来方便用户对所需信息的获取。 在内容分析的过程中传统信息检索领域的技术自然的会被引用进来。但 网页与传统的文档相比有着自己的特点： 一、 有用信息通常伴随着大量的“噪音”内容，而噪音内容正是 页与传统文档的一个主要区别。根据噪音内容的粒度大小， 网络与分布式系统实验室硕士学位论文 2 上的噪音内容可以被分为两类 全局噪音 ： 全局噪音 是指 具有较大粒度的噪音内容，它通常包含镜像网站、重复网页。 局部噪音 ： 局部噪音 是指 页内 与网页主题内容无关的噪音内容，比如：广告、导航条以及版权声明等内容。 二、 网页缺乏必要的元数据信息。而元数据在信息管理过程中有着重要的作用。 三、 文本信息大多数是以 页的形式存在的， 定义了一套标签来描述网页中内容的布局和显示方式，因而，网页中的标签信息隐含了网页内容的重要性信息以及相关性信息。 信息的这些特点使得传统信息检索领域中的技术已经不能满足各种 息系统的要求。针对 页的不足给各种 息系统带来的问题，各个领域都有一套具体的解决方法。但并没有一 个较为通用的预处理框架及相应的方法。通过分析可以看到，这些问题都是源自 信息本身的不足，因而各种 息系统的需求是有共性的。这意味着我们有必要也有可能建立一个较为通用的预处理框架并给出相应的方法，从而方便大多数 息系统的需求。本文中的研究工作就是在这样一个背景下展开的。 文研究内容 本文中的研究围绕以下几个方面展开： 分析 网页的特点以及其不足对 应用系统造成的影响，从而发现 各种应用系统的共性需求。 针对 应用系统的共性需求，给出一个较为通用的预处理框架和相应的方 法，从而满足大多数 息系统的需求。 将提出的预处理框架中的方法应用到实际系统中，包括：搜索引擎和网页自动分类系统。 通过对应用的效果评测和一系列实验，发现方法中的不足，继续改进方法。 北京大学 网络与分布式系统实验室硕士学位论文 3 文贡献 基于对 网页的特点和 息系统共性需求的分析，提出一个较为通用的预处理框架，包括：网页净化、近似网页发现和元数据提取。 提出一个新的网页内容净化方法，该方法的一个重要优点是它不需要除原始网页以外的其他信息（例如： 网页模板 ），而这些额外信息是该领域中其他方法所必须的。 在参考了 C和 ，提出了一个包含元数据和内容数据的网页表示模型（称为该模型包含这样几项信息元素： 网页标识 、 网页类型 、 内容类别 、 标题 、 关键词 、 摘要 、 正文 、 相关链接 。并给出了该模型中元素的自动提取方法。（ ） 将本文中提出的方法应用到实际的系统中：搜 索引擎和网页自动分类系统，通过对原有系统质量的提高，验证了方法的有效性和实用性。 通过本文中提出的方法，一方面能够自动去除 噪音网页以及网页内与网页主题内容无关的噪音内容，另一方面也能自动的从网页中提取相关的元数据，从而使我们看到了在原始 搭建一个噪音小、描述清晰、更易于处理和利用的网页信息平台。 文组织 本文后面是这样组织的，第 2 章是相关领域的研究；第 3 章讨论 4 章讲述预处理过程的框架和其中的方法；第 5 章介绍本文中提出方法的应用以及实验和实验结果分析；第 6章是对本文的总结和对未来工作的展望。 北京大学 网络与分布式系统实验室硕士学位论文 4 第 2章 相关研究 索引擎 搜索引擎是 信息检索的典型系统，它的作用是帮助人们快速准确的在 找到所需的信息。根据搜索引擎基于的技术原理，可以分为三个类型： 基于机器人（ 搜索引擎 这种搜索引擎利用一个称为 程序以某种策略自动的将 的网页搜集起来，并由一个索引器为搜集到的网页建立索引。当用户通过服务提交查询请求时，由检索器从索引库中检索出相关的文档返回给用户。该类搜索引擎的优点是提供服务的信息量大、无需人工参与；缺点是返回的信息过多，包 括很多与查询无关的信息。 目录式搜索引擎（ 这种搜索引擎以人工或半自动方式搜集信息。由人工来访问其中的网站，并对该网站撰写一段描述，并根据网站中的信息将网站加入到一个预先定义好的分类体系下。用户访问时，通过该分类体系不断按照自己关心的类别向下找，可以找到自己关心的网站。该搜索引擎的优点是用户找到的结果较为准确；缺点是需要大量人工介入、信息量少。 元搜索引擎（ 元搜索引擎是建立在其他独立搜索引擎之上的搜索引擎。当用户提交一 个查询，元搜索引擎将查询项做一定处理后，提交给多个独立的搜索引擎，并将所有的查询结果集中起来处理后返回给用户。 本节中，我们将重点介绍基于 搜索引擎，并探讨 息中的噪音内容对搜索引擎中某些环节的影响。下图是一个搜索引擎通用的结构图。 北京大学 网络与分布式系统实验室硕士学位论文 5 图表 1 搜索引擎通用结构图 基于 搜索引擎通常包含以下四个步骤： 网页抓取：发现、搜集 的网页信息。 网页消重：消除搜集到的网页中重复或近似重复的网页。 建立索引：对搜集到的 息 建立索引库。 提供检索服务：根据用户输入的查询项，在索引库中检索出文档。 下面详细讨论网页消重和建立索引。 网页消重是指将搜集到的网页中重复网页去掉的过程，在消重后的网页集上建索引再提供服务可以保证用户查询时不会出现大量内容重复的网页，同时节省建立索引的时间以及检索的时间。 三种比较常用的重复网页判断方法，其中 使用。这些重复网页发现算法都是基于相同的想法：为每张网页计算一组指纹（ 如果两张网页中相同的指纹数量 超过一个阈值，这两张网页就被认为是互为重复的网页。然而，大量的重复网页并不是对原始网页的简单拷贝，而是将要转载的主题内容放在不同的模板中形成的。我们把这种近似的重复网页以及完全相同的重复网页统称为 近似网页 。由于模板中的内容绝大多数是与主题内容无关的，因此模板中的内容就会干扰近似网页识别程序对近似情况的判断，从而导致错误消重。常见的错误消重有北京大学 网络与分布式系统实验室硕士学位论文 6 以下两种情况： 情况 1：相同的内容，由于放在了不同的模板中导致应该被消掉但实际上被消重程序判断为非近似网页而保留。 情况 2：不同的内容，由于放在了相同的模 板中导致不应该被消掉但实际上被消重程序判断为近似网页而消掉。 对于完全相同的近似网页，消重算法是容易识别的，因而，如何识别主题内容相同但模板不同的情况是消重算法面临的问题。 在索引过程中，索引器为搜集到的文档建立了一个（或若干个）索引文件，索引文件是用来在检索时对查询词与文档进行匹配的，从而找到与查询词相关的文档。为了合理的对检索到的文档排序，研究人员提出了 法，这两个算法通过分析 的链接结构来计算网页的重要性。正如 附录所讲述 的，由于广告等噪音内容通常伴随着超链出现， 法得到的排序通常偏向于广告网页。另外，如果不去除原始网页中的噪音内容，检索系统必然对噪音内容也建立索引，从而导致仅仅因为查询词在某张网页的噪音内容中出现，而把该网页作为结果返回，而网页的主题内容可能和这个查询词完全无关。可以看出，噪音内容不仅使索引结构的规模变大，而且还导致了检索准确性的下降。针对这个问题， 提出了一个去除网页中噪音内容的方法，该方法首先依据 标签构造网页的标签树，从而依据 标签将一张网页规划为相 互嵌套的内容块；而后，对于使用同一个模板作出的网页集，利用基于信息熵的方法找出在该网页集中多次出现的内容，作为冗余内容，而在该网页集中出现较少的内容块就是有效信息块。实验证明该方法是有效的，但该方法必须局限在基于同一个模板的网页集，而 的网页模板不计其数，该方法显然不够通用。 也提出了一个噪音内容判断方法，该方法必须针对某一个网站，通过对网站建立一棵特殊的标签树的方法，自动发现网站中网页内的噪音内容。但这种方法的局限在于，它只能以网站为单位进行处理。实际上，任意一张网页，人是比较容易区别 其中的噪音内容和主题内容的。这说明我们有可能追求自动识别一张网页中的主题内容和噪音内容而不需要依赖于一个网页集合；这样就可以使去除网北京大学 网络与分布式系统实验室硕士学位论文 7 页噪音内容的方法更加通用和独立。 页自动分类 网页自动分类是指用计算机程序来自动确定网页与预先定义类别之间的隶属关系 从总体上，分类器的整个工作周期可以分成训练过程和分类过程。 训练过程是指为预先确定的分类体系中的每个类别人工挑选一定量的样本（我们称这个样本集合为训练集），目的在于通过每个类别内的样本来最大程度地体现每个类的特征并区别不同类之间的特征。 在训练 过程中，训练集实例经过分词和特征选取处理后被表示成向量形式。在 该特征向量集 上，统计不同类别内的词的分布，形成类别与词之间的一个加权映射。这个映射关系将是后续分类过程的依据。另外， 校验集是训练集的一部分，通过应用相应的阈值策略来预先确定每个类别的截尾阈值。截尾阈值的作用在于，在分类过程中，每个网页都会被赋予一些候选类，以及该网页与每个候选类的类属关系权值，那么候选类中，类属关系权值大于对应类截尾阈值的类别将被保留下来作为该网页的分类结果。在分类过程中，一个待分类的中文网页表示成向量形式后，应用分类算法同训练过 程得到的类别模式逐一比较，得到候选类别列表，然后同训练过程中得到的每个类别的阈值相比较，保留大于阈值的类别，并作为该网页的分类结果。 在这两个过程中，包含以下几个关键技术： 训练集整理：从上述的介绍可以知道，训练集是分类器的一个重要分类依据，训练集的质量直接影响到后续分类的质量。 特征项选取：在训练的过程中，对每个类别内文档中包含的词项进行取舍，选取那些能够明确体现一个类别特征并有很强区分能力的词项，而去掉那些区分能力弱，模糊不同类别间特征边界的词项。同时，特征项选取还有降低向量空间维度的作用，从而提高分类 系统的效率。 人们已经研究了多种特征选取方法，如：文档频率（ 信息增益（ 互信息（ 开方拟和检验（ 2术语强度（ 等。 北京大学 网络与分布式系统实验室硕士学位论文 8 分类算法：通过比较给定网页的特征向量与每个类别内特征项的分布，确定网页与类别的隶属关系。常用的分类算法有以下几种： 法、 算法、基于 分类算法、决策树（ 法、 法，等等。 训练集 预处理 分类算法参数调整测试特征选取 分类结果 截尾算法I n d e p e n d e n c y B i n a r y 分类 M - a r y 分类图表 2 实现中文网页自动分类的一般过程 待分类中文网页向量表示预处理训练集实例预处理特征选取算法分类算法校验集 测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程 分类过程图表 3 中文网页分类器的工作原理图 由于噪音内容与主题内容无关，因此，噪音内容对上述的几个关键技术都造成了不同程度的影响。在训练过程中，训练集中的噪音内容会导致各个类别的特征变得模糊，甚至造成噪 音中的关键词成为类别的重要特征项。在分类过程中，待分类网页中的噪音内容则会导致该网页类别不明确，甚至网页的分类结果被大量的噪音内容所误导，因而影响了网页自动分类的效果。 提出了通过去掉网页中的噪音特征项来提高网页分类质量的方法。这两个方法中，作者着重考虑如何从训练集中选取有代表性的特征项而去掉噪音的特征项，而没有考虑先去掉训练集网页中的噪音内容，而后在网页的主题内容中选取特征项。 北京大学 网络与分布式系统实验室硕士学位论文 9 息提取 信息提取是从文本中提取用户感预先定义好的某些类型的信息（定义、实体、关系）并以结构化的形式返回提 取结果的过程 它与信息检索的区别在于：信息检索是在一个文档集合中找到与查询词相关的文档子集；而信息提取是在文档内部提取出预先定义的某些类型的信息。信息提取的结果通常自动导入数据库中，在这些数据之上可以作许多应用层次上的分析，例如：趋势分析；也可以直接在 提供服务，例如：当前市场上某类商品价格表。 信息提取研究的目标是建立具有如下功能的系统： 1、 从无结构或半结构化的文档中自动发现有用信息，并将其中相关的信息联系起来。 2、 能够在只做简单修改的情况下方便的应用到不同的领域。 3、 性能要满 足用户的需求。 一个信息提取系统通常分为三个自过程： 1、 从每个文档内提取有用信息。 2、 如果一个完整的记录内容分布在不同文档中，则需要将不同文档中提取的相关信息连接为一个完整的记录。 3、 将用户需要的信息按照一定格式输出。 针对 页的信息提取，较早的方法是：针对某一类具体网页，人工提取该类网页的内容组织模式。然后，信息提取系统根据该模式从属于该类的网页中提取相应的内容 但这些方法有一个共同的局限性，那就是需要人工提取内容组织模式，这对于内容组织风格繁多的说显然是不适用的。因此，在 ，作者提出了 5 条启发式规则，综合利用这 5 条规则系统可以自动地发现网页中各个主题信息块（ 边界。 出了一种基于视觉相似性来自动分析网页语义结构的方法，该方法首先比较 页内容的视觉相似性，然后使用一个模式发现算法来确定这些视觉相似的内容最有可能的组织模式，最后按照该模式将内容重新组合。 在网页信息提取过程中，自动识别网页模式以及按照一定模式从网页北京大学 网络与分布式系统实验室硕士学位论文 10 中提取信息都是很费时的，时间开销主要取决于网页中标签结构的复杂性以及提取出的模式的复杂性。传统的方法必须要从整个网页中提取模式，而 不是只针对主题内容提取。由于主题内容的结构是相对简单的，因此直接从主题内容中提取模式或信息可以大大节省时间开销。综上，在净化后的网页上作信息提取不仅可以排除噪音信息对信息提取的干扰，提高信息提取的准确性，而且可以使得网页中的结构简单化，提高信息提取的效率。 数据提取 元数据是指面向应用的、能被计算机所理解和处理的、描述 档特征的数据 长期以来，元数据在数据库领域和图书馆领域扮演着重要角色。随着 研究与应用的发展，单纯的网页内容已经不能满足需求，网页元数据得到越来越广泛的使用。在 息检索领域，单纯依赖关键词匹配的检索手段过于单一。内容类别、摘要等元数据信息的合理使用，不仅使用户可以从不同的角度进行查询，而且也使得查询的准确性得到提高。而主题搜索、个性化信息服务以及数字图书馆也都强烈的依赖资源的元数据信息。因此，准确且高效的提取必要的元数据是 各个研究领域面临的重要问题。 一个得到广泛应用的网络资源元数据标准，它提供了一个描述网络信息资源的元素集合。 在元数据提取领域，关键词提取是一个比较活跃的分支。在关键词提取的各种方法中，基于统计的方法被广泛的 接受并被证明是有效的。 式通常被用来量化一个词项的重要性。但 页中有着丰富的标签信息，如果将这些有用信息与传统的公式结合起来，将会提高关键词提取的准确性。在传统的摘要提取方法中，摘要是通过选取权值较高的句子形成的，而句子的权值则是由它所包含的关键词的权值决定的。除此之外，一些启发式规则也起到了重要的作用，比如出现“综上所述”、“本文论述了”等短语的句子通常有总结全文的功能。但基于启发式规则的方法过于机械。 在本文中，我们首先对净化后的网页按照标签结构进行语义分段。在分段的基础上，我们在 每段内按照句子的权值选取重要句子。通过这种方北京大学 网络与分布式系统实验室硕士学位论文 11 法，可以保证自动生成的摘要能够覆盖整篇网页的内容，而不会被几个权值很高的关键词所引导。 北京大学 网络与分布式系统实验室硕士学位论文 12 第 3章 目前， 息系统通常面临以下两个问题： 一、 有用信息通常伴随着大量的“噪音”内容，而噪音内容正是 页与传统文档的一个主要区别。根据噪音内容的粒度大小， 全局噪音 ： 全局噪音 是指 具有较大粒度的噪音内容，它通常包含镜像网站以及近似网页。 全局噪音 内容不仅影响了 信息检索系统（比如搜索引擎）的网页搜集、索引和检索结果排序的质量，也使得 局部噪音 ： 局部噪音 是指 页内与网页主题内容无关的噪音内容，比如：广告、导航条以及版权声明等内容。 局部噪音 使得应用程序很难确切得到网页的主题内容，因此它严重的影响了基于网页内容的应用程序。同时， 局部噪音 很多情况下是伴随着超链出现的，因此， 局部噪音 也对基于网页间链接关系的应用程序造成影响。 虽然噪音内容在某些应用程序中是有用的，但对于大多数的 息系统而言，它们是有害的。 二、随着 研究与应用的发展，单纯的网页内容已经不能满足需求，网页元数据得到越来越广泛的使用。在 息检索领域，单纯依赖关键词匹配的检索手段过于单一，内容类别、摘要等元数据信息的合理使用，不仅使用户可以从不同的角度进行查询，而且也使得查询的准确性得到提高。而主题搜索、个性化以及数字图书馆也都强烈的依赖资源的元数据信息。但网页的元数据信息在网页中并没有被明确的表示出来。因此，准确且高效的提取必要的元数据是 各个研究领域面临的重要问题。 通过对各个领域工作及研究成果的分析，我们发现不同领域的工作存在两个共性： 1、工作结果的共性。 虽然各个领域所做的工作都是为了解决网页复杂化给本领域带来的问题，但各个领域的工作结果中有着共同的部分。譬如，各个领域都需要去北京大学 网络与分布式系统实验室硕士学位论文 13 除原始网页中的噪音内容，然后在净化后的网页上进行后续工作；很多领域都需要获取网页的元数据信息。即净化的网页和元数据是它们都需要的结果。 2、 工作过程的共性。 在获得不同结果的过程中存在着共同的中间环节。譬如：网页分类、摘要的提取以及关键词的选取都需要对文档进行分词操作。而这些中间环节有时是整个工作中效率上的瓶颈。 这些共性启示我们有可能通过归纳不同应 用需求中的通用元素， 并作为一个模型一次性提取出来，从而对多种应用提供一个统一的支持。可以想象， 这样做既便于提高所需信息的质量，又最大限度地避免重复工作带来的时间开销，从而在信息量和复杂性这两个相互制约的因素之间找到一个合理的折衷点。 北京大学 网络与分布式系统实验室硕士学位论文 14 第 4章 预处理方法与技术 处理框架及结果描述 处理框架 本文中提出的预处理框架包括三部分：网页净化（局部噪音清除）、近似网页消除（全局噪