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

北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 1 论 文 摘 要 本文首先介绍了 发展状况，指出 一个庞大、杂乱、瞬息万变的信息源泉，仅仅依靠网页上的超文本链用户是无法方便、快捷地找到自己所需的信息的，提供 息导航服务的搜索引擎是解决这个问题的一个途径。在介绍了传统的 搜索引擎和基于人工分类的目录式搜索引擎的特点并对它们作了比较之后，指出支持分类目录是 搜索引擎发展的趋势，而应用文档自动分类领域的研究对收集的网页自动分类，实现对分类目录的支持是一种可行的方法。然后，本文介绍了天网搜索引擎的 现状，分析了它的特点，说明要进一步发展天网系统，应当采用文档自动分类技术支持分类目录。 接下来，本文介绍了文档自动分类的意义和算法的分类，然后分别介绍了类系统和 类系统常用的算法和各个算法的特点，接着介绍了从 类系统转换到 类系统常用的三种算法以及这两种分类系统的性能评价指标，然后分析了特征项选取对分类系统的影响，介绍了常用的五种特征项选取的方法。 结合现有的天网搜索引擎，本文提出了天网系统支持分类目录的设计方 案，详细介绍了自动分类系统的实现，说明了分类系统选用的分类算法的是 法，选用的评价特征项重要性的指标是 计量，选用的转换算法是 法，然后讨论了自动分类系统在实现过程中遇到的问题以及解决的办法： 1 使用两个文件描述分类目录，用 构表示类之间的层次结构； 2 通过限制文档向量最大分量的值显著地提高了系统分类的性能指标； 3 使用稀疏矩阵在程序中表示文档向量，极大地缩短了分类响应时间，节省了占用的内存空间。在说明了分类系统使用的分类目录、训练集和测试集之后，本文给出了系统的测试 数据。 最后，本文详细介绍了将自动分类系统集成在现有的天网系统中的方法，讨论了对天网系统各个子系统的改造。 关键词： 文档自动分类、搜索引擎、 京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 2 目 录 目 录 . 2 第一章 课题研究背景 . 3 第二章 文档自动分类的主要算法和性能评价 . 6 2 1 文档自动分类的主要算法 . 6 2 1 1 算法的分类 . 6 2 1 2 文档的向量空间模型 . 7 2 1 3 类系统 . 8 2 1 4 类系统 . 10 2 2 分类系统的性能评价 . 13 2 2 1 类系统的性能评价 . 13 2 2 2 类系统的性能评价 . 15 2 3 特征项的选取 . 17 第三章 自动分类系统的实现及其在天网系统中的应用 . 21 3 1 支持分类目录的天网系统的设计 . 21 3 2 自动分类系统的实现 . 22 3 2 1 自动分类算法的选用 . 22 3 2 2 对中文的支持 . 22 3 2 3 自动分类系统的实现 . 23 3 2 4 自动分类系统的测试 . 27 3 3 现有天网系统各子系统的改造 . 31 3 3 1 收集分析子系统的改造 . 31 3 3 2 询页面和查询处理程序的改造 . 32 第四章 展望 . 33 参考书目 . 35 附录 . 36 北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 3 第一章 课题研究背景 一个由不同类型和规模的独立自主运行和管理的计算机网络组成的全球范围的计算机网络，它的前身是 1969 年美国国防部高级研究计划署组建的实验性网络 着计算机网络和通 信技术的发展，各个国家和组织的网络的不断加入， 成为一个规模巨大、自治性强、发展变化快、用户访问频繁的全球最大的国际互联网络，截至 1996 年 7 月， 连接了134346 个网络，入网的国家和地区超过 150 个，主机 1228 万台，用户人数以亿计。 是一个无穷无尽的信息源泉，它已深入到人们生产、生活的各个领域，向人们提供着巨大的并且还在不断增长的信息资源和服务，越来越多的公司、企业通过网页宣传自己，越来越多的科研机关和学校通过网页交流科研成果，越来越多的组织和个人拥有 了自己的主页，越来越多的报刊、杂志加入了 不出户而知天下事已不再是神话。据不完全统计， 1996 年 900 万，时至今日，这个数目决不会少于 4 亿。 为了让用户能够在如此庞大、杂乱、瞬息万变的信息海洋中，方便、快捷地找到自己感兴趣的信息，而不是茫然不知所措，仅靠网页上的超文本链是远远不够的，提供 息导航服务的搜索引擎（ 解决这个问题的一个途径。传统的 搜索引擎通过被称为 程序自动地在网上循着超文本 链递归地访问、收集 页，分析页面的内容，生成索引和摘要，并向用户提供 询页面，根据用户的查询请求在索引库中查找相关信息在网上的位置，最后将查询结果按照相关度排序后返回，帮助用户尽快地找到所需的信息，给用户带来了极大的便利。这类搜索引擎的代表有 于人工分类的目录式搜索引擎稍后出现，它在人工的参与下建立分类目录，对收集的网页按主题或者学科进行分类，编写摘要，用户可以沿着分类目录的层次结构，进入自己感兴趣的主题，进而找到所需的信息。这类搜索引擎的代表是 比较这两种搜索引擎， 搜索引擎自动地收集、分析和处理网页，因北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 4 而它索引的网页数多，信息量大，并且能定期重新收集网页，更新索引库的内容，向用户提供最新的导航信息，但由于它只提供基于关键词或全文的检索，用户只有确切地知道自己想查什么，自己感兴趣的网页应当含有哪些关键词时，查询的效果才比较理想，否则，返回的结果很可能和用户的实际需要相距甚远；目录式搜索引擎在对网页的分类和网页内容的理解上引进了人工干预的机制，因而在查询的准确性方面要优于 搜索引擎。它支持基于分类目录的查询， 当用户对某个领域感兴趣但并不熟悉这个领域的关键词时，这种查询方式能很好地为用户提供服务，而此时 搜索引擎则基本上无能为力。由于人工分类和摘要编写的效率低，网页更新困难，目录式搜索引擎在索引的网页的数量上受到了很大的限制，维护管理工作量大， 搜索引擎索引的网页数早以突破千万，而 还停留在百万级的水平。 信息量大是 搜索引擎的一大优点，但这也常常使得返回的查询结果成千上万，用户经常需要在一大堆不感兴趣的信息中费很大力气才能找 到自己感兴趣的网页，有时甚至还会一无所获，无功而返。如果搜索引擎能够对收集的网页按学科或者主题进行分类，用户可以选择只在自己感兴趣的领域内查询，这样就能将许多无关网页排除在返回结果之外，极大地提高查询结果的准确性，方便用户的使用。目前，支持分类目录是 搜索引擎发展的趋势， 用户基于分类目录进行查询时，系统实际上是使用目录式搜索引擎人工处理的数据提供服务。除了采用人工的方法对网页分类之外，还可以人工建立分类目录，利用人工智能领域研究的一些技术对网页自 动分类。搜索引擎大家庭中的后起之秀 采用的就是这种方法，它参照美国国会图书馆图书分类的方法，人工建立基于主题的分类目录，然后通过网上自动地收集网页，采用离线的方式，应用文档自动分类技术对网页自动分类，建立索引，向用户提供导航服务。 所谓文档自动分类 2就是指定文档和预先定义好的一些类之间的类属关系，分类的工作由计算机自动完成。从分类的准确性来看，文档人工分类要优于自动分类，但这并不说明自动分类就没有存在的价值。首先，自动分类在速度和效率上要大大优于人工分类，它 能节省大量的人力、物力和资金；其次，对于人工分类，如果分类人员的素质不够高，或者面对不熟悉的领域，分类的准确性很难保北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 5 证，在这个时候，自动分类系统可以作为人工分类的辅助工具，分类人员可以参考自动分类的结果，作出正确的判断，提高分类的准确性。 采用文档自动分类技术，对收集的网页自动分类，实现对分类目录的支持既保持了传统的 搜索引擎索引网页多、信息量大的特点，又保证了分类的效率，同时，在文档自动分类领域的研究成果保证了分类的准确性。 1994 年，我国正式加入 过几年的迅猛发展，至 1998 年底已经形成了以 大网为主干，遍布全国的互联网络，注册域名 18396 个，直连主机 台，拨号上网的计算机 63万台， 点超过 8000 个，上网用户 210 万人， 1999 年 3 月，用户人数已突破 300 万。为了方便日益增多的国内用户，促进 尤其是 中文信息的交流，增强全世界华人的凝聚力， “九五”攻关项目“计算机信息网络及其应用关键技术研究”中设立了“中文编码和分布式中英文信息发现”子专题，北京大学 网络研究室承担了该子专题的部分研究开发工作，设计开发了“天网”中英文搜索引擎（ 3。 1997 年 10 月 29 日，天网搜索引擎正式在 提供查询服务，到现在为止，天网索引的网页数超过100 万，新闻组信息 30 万条，访问人次达到一百万，点击次数突破一千万，软件世界（ 1998 年 7 月）将天网评为国内最值得关注的搜索引擎， 1998 年 12 月，天网通过了 鉴定。 天网是典型的 搜索引擎，它立足于国内，主要收集大陆和香港地区的网页，支持多种中文编码，基于词建立索引，索 引的网页数在国内的搜索引擎中名列前茅，查询的响应速度极快，是网上用户访问国内资源的强有力的导航工具，受到了广泛的好评。但是，也有一些用户抱怨天网查询的结果不够准确，有用的信息常常夹杂在一大堆无关的东西中返回，为了把它们找出来需要不断地向后翻页，很是麻烦，还有一些用户在希望天网能支持分类目录。为了适应时代发展的需要，进一步发展天网系统，提高它的性能，更好地满足用户的需求，同时借鉴 成功经验，在已有“天网”的基础上，应当采用对收集的页面自动分类的方法，实现对分类目录的支持，我的论文工 作就是围绕这个目标展开的，在对当前常用的文档自动分类算法作了认真的调查之后，选用 法实现了一个自动分类系统，并提出了在现有天网系统基础上支持分类目录的设北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 6 计方案。 第二章 文档自动分类的主要算法和性能评价 文档自动分类属于信息检索领域的研究范畴，它涉及人工智能、近世代数、概率统计等多个领域。为了推进在信息检索领域的研究，交流研究成果，评价各种算法的优劣，美国国家标准和技术研究院（ 信息访问和用户界面公司（ 息技术实验室（ 然语言处理和信息检索部（ 美国国防部高级研究计划署信息技术处共同主持召开了信息检索会议（ 至今已召开了七次。 议实际上是信息检索系统的擂台赛，一些大学包括一些公司带着自己开发的文档分类系统参加会议，由大会使用相同的训练集和测试用例对这些系统进行评测，从第三次会议开始，大会增加了西班牙文分类系统的评测，从第五次会议开始，增加了对中文分类系统的评测，和面向英文的分类系统相比，中文分类系统的起步较晚，实际上，参加 中文分类系统处理的重点还停留在中文的切词上。可以说， 在展示的文档分类系统代表了文档分类领域的最新研究成果。 在国内做这方面工作的主要有两家：一个是复旦大学计算机系，另一个是光公司，实际上，曙光公司使用的文档自动分类系统是由复旦大学计算机系开发的。 2 1 文档自动分类的主要算法 2 1 1 算法的分类 基于计算机的文档分类算法主要分以下三类：简单词匹配法，基于同义词的词匹配法和经验学习法。简单词匹配法是最简单，最直接的文档分类算法，它根据文档和类名中共同出现的词决定文档属于哪些类，很显然，这种算法的分类规则过于简单，机械，分类效果极差 。基于同义词的词匹配法是对简单词匹配法的北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 7 改进，它先定义一张同义词表（可以是机器自动生成的，也可以是手工创建的），然后根据文档和类名以及类的描述中共同出现的词（含同义词）决定文档属于哪些类。这种分类算法扩大了词的匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍然很机械，而且同义词表的构成是静态的，对文档的上下文不敏感，无法正确处理文档中其具体含义依赖于上下文的词，分类的准确度还是很低。经验学习法和词匹配法在分类机制上有着本质的不同，它的基本思路是先收集一些与待分类文档同处一个领域的文档作为训练 集（ 由专家人工进行分类，保证分类的准确性，然后分析这些已分好类的文档，从中挖掘词和类之间的语义联系，最后再利用学到的知识对文档分类，而不再是机械地按词进行匹配。经验学习法在文档分类的准确性方面要大大优于词匹配法，目前实用的分类系统都是采用这种分类方法。本文介绍的几种文档分类算法都属于经验学习法。 2 1 2 文档的向量空间模型 待分类的文档和训练集中的文档在分类和训练时用何种形式表示是一个很实际的问题。 1969 年， 出了向量空间模型 是文档表示的一个 统计模型，该模型以特征项（ 为文档表示的基本单位，特征项由字，词和短语组成。 令 D=示文档集， T=示特征项集，它由文档集 D 中的所有或部分特征项组成，文档 特征项空间中的向量 表示， 示特征项 文档 的权重， 示特征项 文档 出现的频率，称为项频， 表示文档集 D 中出现了特征项 文档的数目，称为文档频率。 量空间模型是目前最好的文档表示模型，参加 大部分文档分类系统都采用 这种模型，不同系统都着重在特征项的选取，短语的生成，查询扩展和权重评价等四个方面作文章，以提高系统的性能。 北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 8 2 1 3 类系统 根据分类结果的不同，采用经验学习法的文档分类系统又可以分成两类：类系统和 类系统。 给定一篇文档，这种分类系统对每一个类都独立地判断这篇文档是否属于该类，不同类之间互不影响。 类系统常用的分类算法如下： 策树， 4 决策树是 常用的一种归纳算法，它通过对训练数据的学习总结出一般化，普遍化，概括化的规则，然后再利用这些规则分析，解决问题。用决策树进行文档分类的基本思路是这样的：先用训练集为预先定义的每一个类构造一棵决策树，构造方法如下： 以训练集作为树的根结点，它表示所有的训练文档，将它标记为“未被检测”； 找到一个标记为“未被检测”的叶结点，如果它表示的所有文档都属于这个类，或者都不属于这个类，将这个叶 结点的标记改为“已被检测”，然后直接跳到第三步；否则，挑选当前最能区分这个结点表示的文档集中属于这个类的文档和不属于这个类的文档的特征项作为这个结点的属性值，然后以这个结点为父结点，增添两个新的叶结点，都标记为“未被检测”，父结点表示的训练文档集中含有这个特征项的所有文档用左子结点表示，所有不含有这个特征项的文档用右子结点表示； 重复第二步操作，直到所有的叶结点都被检测过了，此时，决策树就构造好了。 每个类的决策树都构造好了以后，就可以用它们进行分类。分类的方法很简单，对每 棵决策树，从它的根结点开始，判断结点的属性值（特征项）是否在待分类的文档中出现，如果出现，则沿着左子树向下走；否则沿着右子树向下，再继续判断当前结点的属性值是否在待分类的文档中出现，直到到达决策树的某个叶结点，如果这个叶结点表示的训练文档都属于这个类，则判定这篇待分类的文档也属于这个类；反之亦然。 决策树算法的构造复杂度取决于特征集的大小和决策树的内部结点数，分类复杂度取决于决策树的内部结点数。目前常用的分类系统中有两个使用决策树算北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 9 法的分类系统： 们构造的决策树的内部结点数一般控制在 200以内，这主要是因为内部结点数目越多，计算越复杂，从可计算的角度考虑，内部结点数不能太多。 简单 法 这种方法的基本思想是给定一个类和一篇文档，利用 概率公式：P(A|B)=P(B|A)*P(A)/P(B)，根据这个类对于每个特征项的条件概率计算它对于这篇文档的条件概率。 给定一个类和一篇文档，令 ， 其中 示文档中出现的第 i 个特征项， n 为文档中出现的特征项的总数。根据全概率公式，我们可以得到如下式子： P( + | = P( + ) * P( + ) / P( ； P( - | = P( - ) * P( - ) / P( ； 其中 P( = P(a1 P( + )表示待分类的文档所处的领域中的文档属于这个类的概率， P( - )表示不属于这个类的概率，在具体的计算中可以分别用训练集中属于和不属于这个类的文档所占的比例代替。 如果 P( + | P( - | ， 法就判定这篇文档属于这个类；否则就判定这篇文档不属于这个类，算法的 关键是如何计算 P( + )和P( - )。 为了使这两个概率可计算，简单 1）对于属于这个类的文档，特征项之间是独立无关的；（ 2）对于不属于这个类的文档，特征项之间也是独立无关的。于是， P()和 P()可以化简成： P()=P()*P()* *P() (1)； P()=P()*P()* *P() (2)； 对于任意一个特征项 t， P(t|+)可以近似地用特征项 于这个类的文档中出现的次数与训练集中所有属于这个类的文档中特征项出现的总次数的比值表示， P(t|-)可以近似地用特征项 们都是可计算的。简单 法利用两条假设极大地降低了计北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 10 算的复杂度，使得算法的实现成为可能，但是这两条假设缺乏严格的理论推导作为基础，无法保证它的正确性，这也在一定程度上限制了算法的性能。 神经网络 神经网络也是 常用的一种算法，它以人类的思维活动为模型。神经网络的基本单位是神经结点，它有输入，输出，阈值三个元素组成，将这些神经结点级连在一起，就形成神经网络。目前常用的文档分类系统中有两个系统采用了神经网络算法：一个是 司开发的 一个是 两个系统都为每个类建立了一个独立的神经网络，通过训练集学习从特征项映射到类的非线性关系，然后再利用学到的知识对文档进行分类。 纳算法 这种算法和决策树算法一样，也是 常用的一种算法，它在原理上和决策树算法具有相同的归纳能力。 法 法是用于文档分类的经典的向量空间模型算法，它的基本思想是使用训练集为每个类构造一个原型向量，构造方法如下：给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，所有不属于这个类的文档对应向量的分量用负数表示，然后把所有的向量加起来，得到的和向量就是这个类的原型向量，定义两个向量的相似度为这两个向量夹角的余弦，逐一计算训练集中所有文档和原型向量的相似度，然后按一 定的算法从中挑选某个相似度作为界。给定一篇文档，如果这篇文档与原型向量的相似度比界大，则这篇文档属于这个类，否则这篇文档就不属于这个类。 法的突出优点是容易实现，计算（训练和分类）特别简单，它通常用来实现衡量分类系统性能的基准系统，而实用的分类系统很少采用这种算法解决具体的分类问题。 2 1 4 类系统 给定一篇文档， 类系统对所有预先定义的类综合考虑，输出候选类北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 11 列表，给出这篇文档和各个候选类的相关度并按此排序。这种分类系统可用于人机交互环境下的计算机辅助分类，工作人员 根据系统返回的候选类列表决定文档应该属于哪些类。 下面介绍 法 这种算法实际上不属于经验学习法，它就是前面介绍的词匹配法，是一种最简单、非学习的算法。在这种算法里，待分类的文档和类名都用 型表示，定义文档和类之间的相识度为它们对应的向量的夹角余弦，逐一计算待分类文档和各个类的相识度，然后按相似度排序就得到了候选类列表。这种算法主要是用来和其他学习算法进行比较，看看采用其他算法能在多大程度上提高分类系统的性能，当两种分类算法不能直接进行比较时， 为它们的参照物。 法 5 这是一种多元线性回归算法，它通过对训练集文档的学习，构造一个多元回归模型描述特征项和类之间的线性关系。用 j 个特征项， 阵 特征项之间的关系， 矩阵 类之间的类属关系， 或 1， 表示文档 j； 表示文档 j， 出矩阵 X，使得 |E=最小，矩阵类之间的线性关系， 出矩阵 X 后，对待分类的文档 算 C=， 最近邻居算法（ 6 这种算法和 先将训练集中的文档用 后对预先定义的每一个类，将训练集中所有属于这个类的文档对应的向量求和，再除以属于这个类的文档的总数，这个步骤实际上求出属于这个 类的文档在北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 12 向量空间的几何中心（质心），并以此作为这个类的原型向量。和前面介绍的几种方法一样，这种算法也以向量夹角的余弦作为向量之间的相似度，给定一篇文档，逐一计算它和各个类的原型向量的相似度，哪个类的原型向量和它的相似度最大，它就属于哪个类。这种方法的特点和 的计算非常简单，复旦大学开发的分类系统使用的就是这种算法。 法 法可以说是从 法上衍生出来的， 法是找一个最近的邻居，而 个最近的邻居。给定一篇文 档， 是计算训练集中所有文档和这篇文档的夹角余弦即相似度，然后从中挑出与之最相关（相似度最大）的 K 篇文档，这 选类与这篇文档的相关度用这 再假设一个类只有一个中心，在这一点上它要优于 法和 法，但它的分类响应时间要长于 N 算法，计算复杂度和训练集中的文档数目成正比，不过，由于 法本身简单而且有效，所以这并不妨碍它和简单 法， 法， 法一样，是在大型应用中可以使用的分类算法。 在有些应用场合，要求分类系统明确判定给定的这篇文档属于哪些类，显然，类系统能满足这种需求，而 类系统则需要对输出的结果进行转换才能提供这种功能。常用的转换算法如下： 置截尾法 ) 设分类系统定义的候选类列表的长度为 m，系统预先根据经验定义一个结尾位置 k， k 的取值在 1 和 m 之间，对每篇待分类的文档，分类系统都返回一个长为 候选类列表的前 篇文档就属于这 不属于其他的类。这种转换算法在实现上非常简单，但它存在很严重的问题：设待分类的文档数目为 n，候选类列表的每个位置都对应 括相同的类），即使 ，也会有 法平滑地调整分类系统的性能。 北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 13 例截尾法 ) 设待分类的文档数目为 n，预先定义的类数为 m， 示训练集中属于类 据每篇待分类文档的候选类列表，系统生成每个类的候选文档列表，并按类和文档的相关度排序，对类 i，取这个类的候选文档列表中的前 n* 他的 文档则不属于这个类。在这里， 过改变它的大小，可以平滑地调整系统的性能。 法的基本思想是控制分入各个类的文档数，使它们保持训练集中各个类文档数的比例关系，这种算法最大的问题是过分依赖于这种比例关系，而没有考虑类和文档的相关度以及类在候选类列表中的位置。 优截尾法 ) 这种方法的基本思路是给定一篇待分类的文档，先计算每个类的最优截尾相关度，然后给出这篇文档的候选类列表，对于候选类列表里的每一个类，如果这篇文档和这个类的相关度大于这个类的最优截尾相关度，那么这篇文档就属于这个类，否则，这篇文档就不属于这个类。将训练集分成两部分，其中一部分仍然作为训练集，另一部分作为测试集，对每一个类，评价分类系统在这个测试集下对于这个类的分类性能，调整截尾相关度，使得系统的性能达到最优，此时截尾相关度的值就是这个类的最优截尾相关度。 上面介绍的这三种转换算法中， 次是 次是 2 2 分类系统的性能评价 2 2 1 类系统的性能评价 1 评价方法 类系统的输入是一篇待分类的文档，输出是按照相关度排序的候选类列表，给定一个阈值（ 如果这篇文档与某个候选类的相关度大于这个阈值，那北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 14 么它就属于这个类，否则它就不属于这个类），对每篇输入的文档，定义： F=候选类列表中与这篇文档的相关度大于阈值的类的数目； C=这篇文档实际所属的类的数目； 选类列表中这篇文档实际所属且与之相关度大于阈值的类的数目； 召回率 =； 精度 =； 评价 111均精度），它的计算步骤如下： 1）对每篇文档，计算它的候选类列表上每个它实际属于的类所在位置对应的召回率和精度 ； 2）将召回率划分成十个区间： 0%， 10%)， 90%， 100%)，再将第一步求出的精度按照它对应的召回率划入相应的区间，用每个区间的最大精度作为区间左界，即 0%， 90%，对应的召回率的代表精度，如果某个区间为空，就用0作为这个区间的代表精度； 3）如果 100%的召回率能达到，就用它对应的精度作为它的代表精度；如果不能达到，就用最接近 100%的召回率对应的精度代替。 4）对 0%， 100%这 11 个召回率，用每个召回率和比它大的召回率对应的代表精度的最大值代替它的代表精度； 5）计算所有测 试文档在这 11个召回率上的平均代表精度 ）计算这 11 个召回率的平均代表精度 平均值，得到的平均值就是分类系统的 11 2 评价结果 使用路透社 5个版本的新闻稿作为训练集和测试集对 6： 版本 1 版本 2 版本 本 3 版本 4 28 22 22 80 93 91 92 京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 15 复旦大学计算机系开发的分类系统用新华 社的新闻稿评测的数据如下 7： ) ) ) ) 74 83 88 90 其中 测试文档数 *100%。 假设 00%，则 11+= 2 2 2 类系统的性能评价 1 评价方法 给定一个测试集，对每一个类，可以用这样一个表来表示分类情况： 属于这个类的文档 不属于这 个类的文档 系统判定属于该类的文档 a b 系统判定不属于该类的文档 c d 令 n=a+b+c+d； 义： b/(b+d)=(b/n)/(b+d)/n)=P(不属于这个类 系统判断属于这个类 )/P(不属于这个类 )=P(系统判断属于这个类 |不属于这个类 )； 召回率 =a/(a+c)=(a/n)/(a+c)/n)=P(属于这个类 系统判定属于这个类 )/P(属于这个类 )=P(系统判定属于这个类 |属于这个类 )； 精度 =a/(a+b)=(a/n)/(a+b)/n)=P(属于这个类 系统判定属于这个类 )/P(系统判定属于这个类 )=P(属于这个类 |系统判定属于这个类 )； 评价系统的整体性能有两种常用的方法： 计算每个类的性能指标，然后求出这些指标的平均值来衡量系统的整体性能。 统计出每个类的分类情况表，然后求每个表单元对于所有的类的总和得到系统的总体分类情况表，再分别计算相应的性能指标。 有考虑每个类占的比例的不同，而是给予北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 16 相同的权值， 每篇文档给予相同的权值，考虑到了大类和小类在反映系统整体性能上的不同地位，（在整体性能上，大类是起决定作用的），因此在评价系统的整体性能上， 优于 目前常用的评价 类系统的性能的方法是综合考虑召回率和精度这两个性能指标，根据前面的分析，精度 =P(属于这个类 |系统判定属于这个类 )，召回率 =P(系统判定属于这个类 |属于这个类 )，令 P=P(属于这个类 )，利用全概率公式有： 精度 =召回 率 *P(属于这个类 )/P(系统判定属于这个类 )； P(系统判定属于这个类 )=P(属于这个类 系统判定属于这个类 )+P(不属于这个类 系统判定属于这个类 )=P(系统判定属于这个类 |属于这个类 )*P(属于这个类 )+P(系统判定属于这个类 |不属于这个类 )*P(不属于这个类 )； 精度 =P*召回率 /(P*召回率 +(1 对一个分类系统，召回率是属于这个类的文档被判定为属于这个类的概率，精度是被判定为这个类的文档确实属于这个类的概率，如果加强将一篇文档判断为属于某个类的限制条件，如提高截尾相关度 ， 回率会下降，但相应地，错误地被判定为属于这个类的文档数目也会减少， 般情况下，此时精度就会上升；类似地，减弱将一篇文档判断为属于某个的限制条件，如降低截尾相关度， 回率会上升，但相应地，错误地被判定为属于这个类的文档数目也会增加， 般情况下，此时精度就会下降。因此分类系统通常通过调整阈值和一些参数的值在精度和召回率之间进行取舍，为了获得较高的召回率，就需要牺牲系统的精度；反之亦然。如果可以通过对阈值和参数的调整使得精度和召回率的值相等，这个值就 被称为系统的 评价 档分类系统常用的性能指标之一。如果不能使得精度和召回率的值正好相等，就用最接近的精度和召回率的值的平均值来代替，这个值称作 精度和召回率的值相距甚远时，使用 一个经常用来评价系统的整体性能的指标是精度和召回率的调和平均值： (1/精度 +1/召回率 )，它的大北京大学硕士论文 文档自动分类技术及其在搜索引擎中应用的研究 17 小主要取决于召回率和精度中较小的那一个，当召回率 =精度时， 最大值。 2 评价 结果 使用路透社 5个版本的新闻稿作为训练集和测试集对一些常见的分类系统的性能评测结果如下： 版本 1 版本 2 版本 3 版本 4 80 76 75 71 观察上表中给出的性能指标，可以得出如下结论： 性能最好的分类系统， 性能也还不错，简单 然不能考虑 统）， 为衡量其它系统性