【毕业学位论文】（Word原稿）中文网页自动分类技术研究及其在搜索引擎中的应用-计算机网络与分布式系统博士论文

北京大学博士研究生学位论文 题目： 中文网页自动分类技术研究 及其在搜索引擎中的应用 姓 名： 学 号： 10008826 院 系：计算机科学技术系 专 业：计算机软件与理论 研究方向：计算机网络与分布式系统 导 师：李晓明 教授 2003 年 5 月 A on in of y I 2003 声 明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者授权，不得将本论文转借他人并复印、抄录、拍照、或以任何方式传播。否则，引起有碍作者著作权益之问题，将可能承担法律责任。 北京大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其它个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 2003 年 6 月 8 日 摘 要 i 摘 要 为了能够 有效地组织和分析海量的 息资源，帮助用户迅速地 获取其所需要的知识和信息， 人们希望能够按照其内容实现对网页的自动分类。 迅猛发展为文档自动分类技术提供了一个前所未有的实验环境和应用平台，同时也带来了新的挑战，需要在传统的技术基础之上，开展针对 页特性的研究工作。 本文对中文 网页自动分类技术这一具有重要理论意义和广阔应用前景的课题进行了研究和探索 ,主要的研究成果有 ： 影响分类器性能的关键因素的定量分析 针对影响分类器性能的两个基本指标（分类质量和分类效率）及其相互关系，本文 从系统的角度出发，综合地考虑了影响分类器性能的各种关键因素，并且通过 定量地分析这些因素，提出了一种新的中文网页分类器的设计方案。实验结果表明，应用该方案设计实现的中文网页分类器不仅具有较高的分类质量，而且同时具有较高的分类效率，满足了处理大规模中文网页的要求。 中文网页内“噪音”的自动清除 同普通文档相比，网页的设计比较随意，通常都包含大量“噪音”，这些“噪音”影响了网页分类的质量。为此 ，本文提出了一种自动从中文网页中自动清除“噪音”的方法。该方法通过利用中文网页的结构信息和内容信息，并结合中文网页自动分类技术，实现了自动从中文网页中自动清除“噪音”。实验结果表明，该方法不仅可以有效地从中文网页中自动清除“噪音”，而且，还可以有效地改进中文网页分类器的分类质量。 从搜索引擎日志中学习新词 针对直接从专业语料库中学习新词所面临的困难，本文提出了一种从搜索引擎日志中学习新词的方法。同传统的方法相比，该方法具有学习效率和准确率高、不受领域的局限、实现简单、易于推广等优点。该方法的基本思想是， 根据用户查询词的长度分布特性和频度分布特性以及分词系统的先验知识，从所有汉字组合模式中尽可能地排除无效的组合模式，从而提高了学习新词的效率和准确性。实验结果表明，该方法不仅可以有效摘 要 地从搜索引擎日志中学习新词，为新词的自动学习提供了一种新的思路，而且，通过不断扩大分词字典的规模，还可以有效地改进网页分类质量。 应用中文网页的自动分类技术，在“自动式”搜索引擎“天网”系统中同时提供目录导航服务 为了提高搜索引擎的查准率，帮助用户快速地定位其感兴趣的网页，本文应用中文网页自动分类技术，在“自动式”搜索引擎系统 中实现了目录导航服务。这种同时具有目录导航功能的“自动式”搜索引擎系统，不仅能够维护大规模的网页，而且具有较高的查准率。 关键词： 搜索引擎， 掘，中文网页自动分类，定量分析，噪音清除，新词学习， 目录导航 o eb to it to eb by eb an an a on at eb is to eb is a in in of as of of on a eb by of of by of eb eb at of eb an to eb of eb eb eb eb at in an of as by of is to as as to of of a eb by of To in eb o of eb eb to in of eb 目 录 v 目 录 摘 要 . i . 录 . v 图表索引 . 1 章 绪论 . 1 究背景 . 1 文网页自动分类技术概述 . 2 档自动分类算法的分类 . 2 现中文网页自动分类的一般过程 . 4 文网页自动分类的关键技术 . 6 现中文网页自动分类面临的主要问题 . 15 文的主要工作 . 16 文的主要研究内容 . 16 文的创新之处 . 18 文的组织结构 . 19 第 2 章 影响分类器性能的关键因素的定量分析 . 21 言 . 21 响分类器性能的关键因素的定量分析 . 22 验设置 . 22 练样本 . 22 征选取 . 27 类算法 . 28 值策略 . 33 个中文网页分类器的设计方案 . 34 关研究 . 35 章小结 . 36 第 3 章 中文网页内噪音的自动清除 . 38 目 录 言 . 38 音清除算法 . 39 验结果及其分析 . 41 验设置 . 41 验结果 . 41 关研究 . 43 章小结 . 44 第 4 章 从搜索引擎日志中学习新词 . 45 言 . 45 种从搜索引擎日志中学习新词的方法 . 47 本思想 . 47 户查询词的分布特性分析 . 49 合模式的提取 . 52 选词的筛选 . 54 法分析 . 55 验结果及其分析 . 56 词学习方法质量的测试 . 56 词学习方法效率的测试 . 58 词字典的规模对分类质量的影响 . 59 关研究 . 60 章小结 . 61 第 5 章 中文网页自动分类技术在搜索引擎中的应用 . 62 言 . 62 天网”目录导航服务 . 64 天网”目录导航服务的体系结构 . 64 天网”目录的运行实例 . 65 关研究 . 67 章小结 . 68 第 6 章 总结与展望 . 69 文的总结 . 69 一步的研究工作 . 71 目 录 参考文献 . 73 附录 “天网”中文网页分类目录（ ） . 80 博士生期间录用和提交的论文 . 87 致 谢 . 88 图表索引 图表索引 图 1档自动分类算法的分类 . 3 图 1现中文网页自动分类的一般过程 . 5 图 1文网页分类器的工作原理图 . 5 图 2 一个网页实例集收集和整理工具 . 24 图 2个中文网页分类体系 . 25 图 2随样本数的变化 . 26 图 2随样本数的变化 . 26 图 2比较（ . 27 图 2比较（ . 28 图 2-7 类结果的比较 . 29 图 2-8 k 的取值对分类器质量的影响（ . 30 图 2-9 k 的取值对分类器质量的影响（ . 30 图 2式距离法与欧式距离法对 12 个不同 类别的分类情况 . 31 图 2于层次模型的 基本 比较 . 32 图 2 值策略的比较 . 33 图 2方案同基本 比较 . 35 图 3个网页的 代码 图 3棵典型的标签树 . 40 图 3理前的网页 . 42 图 3用 法处理后的网页 . 42 图 3R 算法对中文网页分类质量的影响 . 43 图 4搜索引擎日志中学习新词的一般步骤 . 48 图 4天网”搜索引擎的用户查询日志举例 . 48 图 4户查询词的长度分布图 . 50 图 4户查询词的频度分布图 . 51 图 4种从搜索引擎日志中提取汉字组合模式的算法 . 53 图 4词学习方法的 学全率 曲线图 . 57 图 4搜索引擎日志中自动学习得到的新词的举例 . 58 图表索引 图 4词学习方法的时间复杂度 . 59 图 5天网”目录的体系结构 . 65 图 5天网”目录导航服务系统的用户查询界面 . 66 表 1息检索系统的评价标准 . 13 表 2本集中类别及实例数量的分布情况表 . 23 表 2-2 法的分类质量和分类效率比较 . 28 表 2式距离与兰式距离的比较 . 31 表 2于层次模型的 基本 比较 . 32 表 2 值策略的比较 . 33 表 2个中文网页分类器的设计方案 . 34 表 2用新方案设计的分类器的性能 . 34 表 3用的 签及其相应的权重 . 39 表 4典的规模对分类质量的影响 . 60 第 1 章 绪 论 1 第 1 章 绪论 究背景 因特网的飞速发展为人们提供了一个可以跨越时间和空间的界限来共享和发布信息的平台。作为因特网上最成功的应用，万维网（ 记为 短短十几年中获得了举世瞩目的成就，为人们的学习和生活带来了巨大的便利。一方面，人们可以通过 获取所需要的信息和服务：通过电子商务，足不出户就能够购买到所需要的商品；通过远程教育，可以接受来自世界各地著名学府的教育或培训；通过浏览新闻站点，可以及时地了解到国内外的新闻焦点。另一方面，人们还可以通过 共享和发布各种信息：企业通过创建主页来展示和宣传自己的产品；科研机构通过网页来交流最新的研究成果；个人用户也通过创建个人主页来结识更多的朋友，所有这些都导致了 网页量的迅速膨胀。到 2003年 4 月， 索引擎索引的网页数已经超过 30亿 根据“天网”搜索引擎 周利民 97在中文网页的收集工作中统计得到的数据，到 2003 年 4 月，中国拥有的网页数已经超过了一亿，而且还将在相当长的一段时间内快速地增长。 拥有海量网页信息的 像一本无所不包的百科全书。由于没有“主编”，人们可以随心所欲地向这本书提交任何信息，这样就导致了这本书在内容组织上的极端混乱。尽管它包含着极大的信息资源，但是真正有用的信息却相对匮乏。面对规模如此庞大的信息海洋，试图通过浏览 往花费大量的精力却所获甚少。因此，在 户和 息资源之间出现了巨大的鸿沟：一方面， 一方面，用户却无法有效地获取这些信息和知识。因此，为了能够 有效地组织和分析海量的 助 户方便地获取其需要的信息和知识，人们希望能够按照其内容实现对网页的自动分类。 事实上，网页自动分类技术在面向主第 1 章 绪 论 2 题的搜索引擎 个性化搜索引擎 搜索引擎的目录导航服务 息过滤 息的主动推送服务 数字图书馆等领域得到了 广泛地应用， 已经成为 息检索领域中的研究热点。由于本文处理的对象主要是 的中文网页资源，因此本文将对中文 网页自动分类技术这一具有重要理论意义和广阔应用前景的课题进行研究和探索。 文网页自动分类技术概述 在 现之前，人们已研究过许多普通文档分类的方法，形成了各种 文档自动分类（ 术 随着海量网页信息的涌现， 术的处理对象从普通文档扩展到网页信息，自然地， 术成了实现网页自动分类技术的基础。 所谓文档自动分类就 是 用 计 算 机 程 序 来 确 定 文 档 和 预 先 定 义 类 别 之 间 的 隶 属 关 系 中文网页自动分类技术涉及到 息检索、自然语言处理、机器学习等多个领域。下面，本节首先将简要地回顾一下文档自动分类算法的分类，接着归纳了实现中文网页自动分类的一般过程，并根据这个一般过程来设计中文网页分类器的基本框架，随后重点介绍了与本文研究工作相关的基本概念和关键技术，最后针对中文网页资源较普通文本相比所具有的特性，对实现中文网页自动分类过程中存在的主要问题进行了分析。 档自动分类算法的分类 目前，已有的主要文档自动分 类算法可以分为三类： 词匹配法。词匹配法又可以分为简单词匹配法和基于同义词的词匹配法两种。简单词匹配法是最简单、最直观的文档分类算法，它根据文档和类名中共同出现的词决定文档属于哪些类。很显然，这种算法的分类规则过于简单，分类效果也很差。基于同义词的词匹配法是对简单词匹配法的改进，它先定义一张同义词表，然后根据文档和类名以及类的描述中共同出现的词（含同义词）决定文档属于哪些类。这种分类算法扩大了词的第 1 章 绪 论 3 匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍然很机械，而且同义词表的构成是静态的，对文档 的上下文不敏感，无法正确处理文档中其具体含义依赖于上下文的词，分类的准确度也很低。 基于知识工程的方法。基于知识工程的文档分类方法，需要知识工程师手工地编制大量的推理规则，这些规则通常面向具体的领域，当处理不同领域的分类问题时，需要不同领域的专家制定不同的推理规则，而且分类质量严重依赖于推理规则的质量。因此，在实际的分类系统中较少使用基于知识工程的学习法。 统计学习法。统计学习法和词匹配法在分类机制上有着本质的不同。它的基本思路是先收集一些与待分类文档同处一个领域的文档作为训练集，并由专家进行人工分 类，保证分类的准确性，然后分析这些已经分好类的文档，从中挖掘关键词和类之间的联系，最后再利用这些学到的知识对文档分类，而不是机械地按词进行匹配。因此，这种方法通常忽略文档的语言学结构，而用关键词来表示文档，通过有指导的机器学习来训练分类器，最后利用训练过的分类器来对待分类的文档进行分类。这种基于统计的经验学习法由于具有较好的理论基础、简单的实现机制、以及较好的文档分类质量等优点，目前实用的分类系统基本上都是采用这种分类方法。 文档自动分类算法词匹配法 知识工程法统计学习法B 档自动分类算 法的分类 本文介绍的文档分类算法都属于统计学习法。根据分类结果的不同，基于统计学习法的分类系统在整体上可以被分为两类：独立二元（ 类系统和 m 元（ 类系统。 所谓独立二元 分类，就是给定一篇文档，分类系统对每一个类都独立地判断这篇文档第 1 章 绪 论 4 是否属于该类：要么属于，要么不属于，而不存在其它的结果，并且在分类过程中，不同类别之间互不影响。所谓 m 元分类就是 给定一篇文档，系统计算这篇文档与所有预先定义的类的相似度，并按这篇文档和各个候选类的相似度排序，最后输出候选类列表。 文档 分类算法示意图如图 1示，本文将在第 介绍其中几个典型的分类算法。 现中文网页自动分类的一般过程 在应用基于案例的有指导的机器学习方法实现中文网页自动分类的过程中有一个基本的假设：文档的内容与其中所包含的词之间有着必然的联系，同一类的文档之间总存在多个共同的词，而不同类的文档所包含的词之间差异很大。因此，分类器的 训练过程 可以看作是在已知文档类别的情况下，统计不同类别内的词的分布，即在预先定义的类别集合 C（ C= , , 与词项集合 T（ T= , , 的幂集之间建立一种加权的映射关系，形成一种向量表示 ；相应的，分类器的 分类过程 ，可以看作在 已知一篇文档内所包含词的分布（用一个向量表示）情况下，和在训练中形成的每个类别的向量表示进行对比， 来确定该文档与类别之间的隶属关系。 根据对文档分类过程实质的分析，下面给出中文网页自动分类的一般过程。同普通英文文档相比，中文网页信息具有自身的特性： 中文网页的内容使用中文书写，不像英文单词之间存在自然的形态间隔，因此为了对中文网页进行 有效地处理，首先 需要进行分词处理，而且分词的效果将显著地影响分 类效果。 网页使用超文本设计。它包含大量的 签和超链接，有可能利用这些信息来改进分类的质量。比如包含在标题 标签内的内容通常要比出现在网页正文 标签内的内容要重要的多。在 相邻的网页通常具有相关或相同的主题，因此网页之间的超链信息也可以给本文一些启发。 网页通常包含大量的“噪音”。同普通文本相比，网页的设计比较随意，通常包含各类广告，设计人员的注释以及版权申明等无关信息。有时同一个网页甚至会包含多个不同的主题。在进行分类之前，需要自动清第 1 章 绪 论 5 除这些“噪音”，否则这些“噪 音”会降低分类质量。因此，需要对中文网页进行预处理后，才能应用相应的文档自动分类算法实现分类。 结合中文网页的特性，图 1出了实现中文网页自动分类的一般过程。其中：预处理过程主要包括中文分词以及网页内“噪音”清除等处理；基于二元分类算法的分类器，可以把分类结果直接作为待分类网页的类别结果，而基于 m 元分类算法的分类器，还需要对该分类结果进行进一步的筛选后，才能作为待分类网页的类别结果。 训练集 预处理 分类算法参数调整测试特征选取 分类结果 截尾算法I n d e p e n d e n c y B i n a r y 分类 M - a r y 分类图 1现中文网页自动分类的一般过程 待分类中文网页向量表示预处理训练集实例预处理特征选取算法分类算法校验集 测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程 分类过程图 1文网页分类器的工作原理图 根据图 1示的实现中文网页分类的一般过程，本文设计了中文网页分类器的基本框架，其工作原理如图 1示。从总体上，分类器的整个工作周期可以分成训练过程和分类过程。在训练过程中，训练集实例经过中文分词和特征选取处理后被表示成向量形式。该特征向量集用来描述类别模式，在分类过程中使用。校验集是训练集的一部分，通过应用相应的阈值策略来预先确定每个类别的截尾阈值。在分类过程中，一个待分类第 1 章 绪 论 6 的中文网页经过中文分词并表示成向量后，应用分类算 法同训练过程得到的类别模式逐一比较，得到候选类别列表，然后同训练过程中得到的每个类别的阈值相比较，保留大于阈值的类别，并作为该网页的分类结果。 从图 1以看出，构建一个分类器的关键因素包括：预处理、训练集、特征选取算法、分类算法和阈值策略等。本文的第 2 致第 4 章将逐一定量地分析这些因素对分类器性能的影响。 文网页自动分类的关键技术 从图 1示的中文网页分类器的工作原理图可以看出， 为了实现中文网页的自动分类，通常需要关注训练分类器使用的训练样本集、特征选取算法、分类算法、阈值策略、分类系统 的性能评价值指标等方面的问题。下面将分别介绍。 训练样本集 为了评价各种 文档自动分类 算法的