（计算机应用技术专业论文）基于类信息的潜在语义多类文本分类模型研究.pdf

基于勋d 的b t 客户端的设计与实现 摘要 在如今的网络应用中，文件的下载是重要的功能之一。传统的下载方式一 般是文件由服务器端传送到客户端，由于用户都是从一台服务器下载，而服务器 所提供的带宽是有限的。当用户数过多时，相应的下载速度就下降了。 p 2 p 技术的诞生，彻底打破了传统的文件下载的观念。目前基于b t 协议的 文件下载软件风靡全球，它采用的就是p 2 p 技术。像b i t c o m e t 、b i t s d 试t 等，文 件的下载速度反而随着用户数的增加而得到提高。但b t 客户端软件也有很多缺 点，比如我们必须隔一段时间重新从服务器上获取用户的信息，一旦服务器当机 或是突然被我们的网络服务商屏蔽掉，我们就不能得到新加入的用户的信息了。 下载的速度就会受到影响。 本人在深入分析b t 软件源码基础上，结合当前应用很广的基于异域运算的 勋d 算法，开发出了d 硒n g 系统。该系统能在t f a c k e f 服务器当机的情况下，仍 能获取新加入的下载同一文件的b t 客户端的地址，以实现更快的文件下载速度。 关键字：p 2 p ；b t 协议；b e n c o d i n g 编码：d h t ；勋d 算法 基于妇d 的b t 客户端的设计与实现 a b s t r a c t n o w a d a y s ， f i l e d o w n l o a d i n g i sa n i m p o r t a n tf u n c t i o ni nn e t w o r k a p p l i c a t i o n i nt r a d i t i o n a lw a yo f d o w n l o a d i n g ， f i l e sa r eg e n e r a l l y t r a n s m i t t e df r o mt h es e r v e re n dt ot h ec l i e n t a 1 1u s e r sd o w n l o a df i l e s f r o mo n es e r v e r ，b u tt h eb a n d w i d t hi sl i m i t e d i ft h en u m b e ro fu s e ri s e x c e s s i v e ， t h ed o w n l o a d i n gs p e e dw i l ld r o p t h ei n v e n t i o no fp 2 pt e c h n 0 1 0 9 yb r o k et h et r a d i t i o n a lc o n c e p to f f i l e d o w n l o a d i n gt h o r o u g h l y a tp r e s e n t ，t h ed o w n l o a d i n gs o f t w a r eb a s e d o nt h eb tp r o t o c o li sa 1 1t h er a g ei nt h ew h 0 1 ew o r l d ，w h i c ha d o p t st h e p 2 pt e c h n o l o g y l i k eb i t c o m e t ，b i t s p i r i ta n do t h e r s ，t h ef i l e d o w n l o a d i n g s p e e du pa l o n gw i t ht h ei n c r e a s i n gu s e r s n u m b e r h o w e v e r ，t h eb tc l i e n t s o f t w a r ea l s oh a ss o m es h o r t c o m i n g s f o ri n s t a n c e ，w eh a v et oo b t a i nt h e u s e r s i n f o r m a t i o nf r o mt h es e r v e ra f r e s ha tr e g u l a ri n t e r v a l s 0 n c et h e s e r v e rc r a s h e so ri ss u d d e n l ys c r e e n e db yt h en e t w o r kd e a l e r ， w ec a n t g e tt h ei n f o r m a t i o no fl a t e l y j o i n i n gu s e r s a n dt h es p e e do fd o w n l o a d i n g w i l lb ei n f l u e n c e d b a s e do nt h o r o u g ha n a l y z i n gs o u r c ec o d eo fb ts o f t w a r e ， w ec o m b i n e t h ec u r r e n tw i d e l ya p p l i e di ( a dt e c h n i q u e ，a n dd e v e l o pd k i n gs y s t e m i t c a r r i e so u tt h a tt h eb tc l i e n tc a no b t a i nn e wd e e ri n f o r l i l a t i o nw i t h o u t d e p e n d i n go nt h es e r v e rw i t ha r c h i v i n gt h ef a s t e rf i l e d o w n l o a d i n gs p e e d k e yw o r d s ：p 2 p ：b tp r o t 0 _ c o l ；b e n c o d i n g ；d h t ；k a d i i 表格 2 1 项和类c 构成的列联表1 2 4 个类的e c c 编码+ o n e - a g 龇n 8 t r e s t 编码表 o n e - a g a l n 8 t 0 n e 编码表 m p l c 模型在龇u t e r s - 2 1 5 了8 上特征维数下的微平均和宏平均指标 m p l c 模型在复旦分类文档集特征维数下的微平均和宏平均指标 各模型在龇u t e r s - 2 1 5 7 8 上前1 0 类性能比较 各模型在r e u t e r s - 2 1 5 7 8 上前1 0 类性能比较 各模型在复旦文档集上的性能比较 各模型在复旦文档集上的性能比较 毖勰丝 必蛐骢的柏 l 2 3 l 2 3 3 4 4 3 3 3 5 5 5 5 5 5 2 1 文本分类系统流程图 插图 3 1 0 n e - a g a l 蹦t r e 8 t 合成分类器示意图2 3 3 2 0 n e - a g a i n 8 t o n e 合成分类器示意图2 4 3 3 d d g a 分类器示意图2 5 4 1 潜在语义结构关系图3 7 5 1 m p l c 在r e u t e r - 2 1 5 7 8 前1 0 个类微平均和宏平均指标分布图，4 5 5 2 m p l c 在r e u t e r - 2 1 5 7 8 其余8 0 个类微平均和宏平均指标分布图4 5 5 3 m p l c 在复旦文档集前1 0 个类微平均和宏平均指标分布图4 7 54 m p l c 在复且文档集其余1 0 个类微平均和宏平均指标分布图4 7 第一章引言 1 1 研究背景 人类进入2 1 世纪以来，信息技术的发展日新月异，同时产生的各种信息呈 爆炸式的增长。尤其是i n t e r n e t 的普及。使得它成为全球最庞大，最丰富的信息 资源库。如何从这些海量的信息之中快速、准确的检索到所需的信息，是当前 计算机研究的热点问题。文本分类技术在信息检索、数据过滤、数据挖掘等方 面有着极为重要的地位。作为一种有效的信息处理方法，分类技术将各类信息 按照一定的分类体系进行分类整理，大大的提高了用户搜索信息的效率。 自动分类技术是在手工分类技术的基础上发展起来的。传统手工分类技 术已不适应对实时和大量的i n t e r n e t 信息进行处理。其弊端体现在既耗费大量 的人力、物力和精力又不能保持分类的性能和效率。而自动分类技术作为知识 的组织工具，它能提供更为高效的搜索策略和更为精确的查询结果。早在2 0 世 纪5 0 年代末，h l l u h n 在这领域进行了开创性的研究。m a m n 于1 9 6 0 年发表了 第一篇关于自动分类的论文”随后，这方面的研究工作开始不断的深入。我国 的文本分类研究开始于上世纪8 0 年代，一些大学、图书馆和文献工作单位开展 了档案、文献或图书的辅助或自动分类研究，陆续研究出了一些处理中文信息 的自动分类系统。 、 自动文本分类的过程如下：预先定义好文本的类别，根据相关的专家经验 为每一个类别提供一批训练样本。分类系统根据这些训练样本学习分类知识， 然后根据学习到的分类知识将待分文档分类到每一个类中。分类问题可以进行 如下形式化。 定义1 1 给定文档集合9 和管类集，文本分类就是在文档集合毋和2 饥之间建 立一个映射莎。 箩：9 ，酽 ( 1 1 ) 一个已被分类的文本可以表示为一个关系对( d 妒) ，妒2 曾。 1 管为幂集 基于类信息的潜在语义多类文本分类模型研究 经过多年的前人研究，已经有越来越多的统计分类方法、机器学习方法、数 据挖掘技术等应用到文本自动分类领域中，如：回归模型、最近邻分类器、规则 学习算法、相关反馈技术、专家投票分类法等等9 1 。这些自动分类算法虽然可以 不用人工进行干预，但是其精度已经达到了与人工分类相当的水平。 1 2 本文工作和论文组织 目前已知的自动分类算法处理的大多数都是二元分类问题。即把2 留限制为 单子集对于多类分类问题，将其分解为多个二元分类问题。这种方法可以较好 的解决多类分类问题。但是，化多类为两类分类的方法的不足之处也很明显： 1 二元分类组合多类分类需要训练多个二元分类器，对于训练样本很大时。 训练难度很大。测试时需要经过多个分类器的预测，计算复杂度高。 2 忽略文档多类属性，割裂类与类之间的关系可能会导致分类精度的降低。 基于目前多类算法的不足之处，我们提出了一个新的基于潜在语义的多类 分类算法，能比较理想的解决以上这些问题。本文的主要工作如下： 1 - 详细的阐述了基于潜在语义的分了算法的原理，并且将其应用与多类文本 分类系统中。 2 利用偏最小二乘回归简化该分类模型，并在r e u t e r 8 和复旦中文文档集上 进行试验并分析试验结果。 3 与目前性能比较好的分类算法进行比较，表明新模型的性能比较优异。 本文的具体安排如下： 第一章：引言。简单的介绍本文的研究背景以及本文的工作。 第二章：文本分类综述。介绍了文本分类的基本概念、分类的流程、应用邻 域以及发展前景。同时详细介绍了文本分类中使用的技术，主要有文本的预处 理、文本的项权重计算方法以及常用的维数约简方法、维数提取方法及其性能 的比较。最后介绍了经典文本分类算法的原理。 第三章：多类文本分类简介。介绍目前最为常用的几种将二元分类算法组 合多类文本分类方法。并分析各种方法的优劣。 2 第一章引言 第四章：基于类信息的潜在语义多类分类模型。介绍如果将潜在语义模型 用于文本分类，及其过程。 第五章：实验。给出了本文的实验过程与实验结果。 第六章：总结与展望。对全文工作进行了总结并提出下一步的工作展望。 3 第二章文本分类概述 如前所述，文本分类实际上是寻找从9 到2 曾的一个映射，即分类器。然而计 算机目前所具备语言理解能力尚不足以处理原始的文本信息，因此训练一个分 类器需要经过一系列的预处理过程，然后抽取信息，用文档的特征表示成为分 类器能够处理的形式进行训练。一个文本分类过程如图2l 表示。 图2 1 ：文本分类系统流程图 整个过程可以分为如下几个步骤： 1 文本预处理：处理文本信息的最初步骤。包括分词( 中文切词) ，去停词， 词干化。对于中文来说，分词是最具有挑战性的难题。目前中文分词的方 法有基于词典的方法、基于自然语言处理的方法和基于统计的方法 2 文本的表示：为了能让计算机处理文本信息，我们将这些文档集组织成为 机器能够理解的格式。 3 维数约减：文本预处理过程中产生的众多文档特征，然而，太多的特征不 仅不能提高分类的效率反而会导致“维数灾难”，使得计算复杂度增加和 泛化能力下降。 4 训练分类器：目前成熟的分类器有很多，比如k m r ，批韧eb 州e s ，s f 等 等，我们将逐一介绍一下这些分类方法。 霪l 基于类信息的潜在语义多类文本分类模型研究 5 评价指标：为了判定分类器的好坏，必须要有衡量分类器性能的指标。这 些指标包括f 1 ，m a r c o f l ，m i c r 0 f l 等等。 下面将就上面几个方面分别进行介绍。 2 1 预处理过程 在计算机还不能够完全拥有智能化的阶段，我们的文本分类系统还不能直 接处理原始文本信息，所以我们要对其进行预处理。这些步骤包括分词，去停 词，词干花。 2 1 1 1 分词 用字母表示的语言，其分词有种天然的优势，即他们的分词是显而易见的， 他们被空格或者标点分开。但是对于某些象形文字如中、日、韩的文字却没有 这样优势。因此分词显得尤为重要。由于中文表达能力的丰富多样，分词技术 一直受到人们的重视，涌现了很多方法。现在的中文分词系统分为三大种类： 6 1 基于词表的分词一最大匹配( m m ) ：这是一种有着广泛应用的机械分词方 法，该方法依据一个分词词表和一个基本的切分评估原则，即“长词优先” 原则，来进行分词。这种评估原则虽然在大多数情况下是合理的，但也会 引发一些切分错误。 2 基于统计的分词：这种方法首先切分出与词表匹配的所有可能的词，这种 切分方法称为“全切分”，运用统计语言模型和决策算法决定最优的切分 结果。这种方法的优点是可以发现所有的切分歧义，但是解决歧义的方法 很大程度上取决于统计语言模型的精度和决策算法。需要大量的标注语 料，并且分词速度也因搜索空问的增大而有所缓慢。 3 基于规则和基于统计相结合：这种方法首先运用最大匹配作为一种初步切 分，再对切分的边界处进行歧义探测，发现歧义。再运用统计和规则结合 的方法来判别正确的切分，运用不同的规则解决人名、地名、机构名识别， 运用词法结构规则来生成复合词和衍生词。目前这种方法可以解决汉语中 最常见的歧义类型：单字交集型歧义。并对人名、地名、机构名、后缀、动 词形容词重叠、衍生词等词法结构进行识别的处理，基本解决了分词所 第二章文本分类概述 面临的最关键的问题。而且由于优秀的辞典结构和算法设计，分词速度非 常快。 中文分词面临的最大问题歧义词和新词“。前者要解决自然语言理解的闯 题，根据上下文环境，在不同切分结果中选择最优解：后者要解决词典中未收录 词( 如人名、地名、机构名等) 的识别。虽然可以在机械匹配的基础上通过规则 的方法来求解上述两个问题，然而规则方法很难穷尽真实文本的各种现象。目 前比较主流的方法是通过对真实文本的概率统计来。 目前，国内有多家单位进行了中文分词方面的研究；其中包括清华大学、北 京大学、中科院计算所、微软研究院、东北大学和哈工大等多家研究机构。他们 在这方面的研究取得了一定的成果，并开发出了一些较为成熟的中文分词系统。 经过比较，本文实验的中文分词处理部分，采用了分词效果比较好的中科院计 算所开源项目“汉语词法分析系统i c t c l a s “。 2 1 2 去停用词 分词结束后，并不是所有分出来的词都是有用的。有这样一些词，它们在 文章中出现的频率很高或者很低，对于文本分类的贡献不大，这样的称为停用 词。比如英文中的冠词、介词：a ，t h e ，i s 等等，中文中的“的”，“啊”，“了”等 等，它们在文章中出现的频率非常的高。另外一些就是出现频率极低的一些词， 比如作者自己刨造的一些组合词。这些词并不能帮助我们提高分类的精度，反 而增加了我们处理的负担。因此需要把他们去掉 2 1 3 词干化 词干化是针对词有变化的语言而进行的处理，比如英语中有前缀和后缀， 时态和语态的变化。这些变化可以将一个词变化为很多不同的词，虽然其代表 的实际意义只有一个。这样就增加了特征的个数。为了减少这样的损失，我们 进行词干化处理。词干化处理常常采用基于自动机的规则方法，即将词形变化 的规律总结成规则，然后通过自动机的方法对词形进行转换。转换的过程当中 可使用或者不使用词典。但是，要做一个百分之百正确的词干化处理也是非常 困难的，需要用到词性分析、句法分析甚至语义分析的信息。好在，文本分类任 务对词干化处理的要求不是很高，利用不同词干化处理算法的分类结果相差不 大。 7 基于类信息的潜在语义多类文本分类模型研究 目前使用最广泛的词干化处理算法是m a r t i np o r t e r 提出的p 0 r t e rs t e m - m e r 算法蝌，本文采用的也是这一词干化处理算法。 2 2 文档表示 为了让计算机能够处理预处理完后的信息，我们必须找到一种文档的表示 方法，让计算机接受。从文本蕴涵信息的角度看，一个文本可以由特征项的权 重和及其相互之间的关系表示。权重信息可以由向量表示，而要表示出特征项 之间的关系就必须使用带指针的结构，比如图、树等。然而信息检索和文本聚 类分类处理要求定义一种距离函数，以表示文本之间的相似程度。如果使用复 杂的树、图结构表示文本的话，很难定义一种合理的距离函数表达两棵树或图 很相似。而使用向量来表示文本，则不会遇到这种困难，数学中有很多种定义距 离的方式可以使用，比如欧式距离、相关系数等。正因为存在以上的困难，所以 我们不得不舍弃不好利用的顺序信息，只使用特征项的权重向量来表示文本。 目前，在文本分类中，人们最常用向量来表示文本，即使用向量空间模 型( v s m ) ”一。在v s m 中，把文本看作是由一组正交词条( t ，如，k ) 所张成的 向量空间，每个文本可看成为空间中的一个点( 向量) ：y ( d ) = ( 叫1 ，劬，) ， 其中毗为词条t 4 的权值，表示该词条在文本中的重要程度。这样如果有m 个文 本，则可以构成一个二维的m n 阶矩阵g ，其中第。行代表第。个文本，第7 列代 表舅钉个词条( 或特征) ，g ，则代表第j 个词条在第i 个文本中所具有的权值。 下面我们介绍几种比较有代表性的权重计算方法。 8 2 2 1 布尔权重( b o o l e a nw b i g h t i n g ) 项在文档中出现权重就为1 ，否则就为o ，即 = ：慧如 2 2 2 词频垄权重( 】 e r m 胁q u e n c e ) 2 2 2 1 玎权重 项在文档中的权重就是项在文档中出现的频率，即 n 培= 七 ( 2 1 ) ( 2 2 ) 第二章文本分类概述 2 2 2 2 玎t d ，权重 综合考虑玎与。影的影响，权重公式为： 咄l o g ( 爱) ( 2 3 ) 2 2 2 3 蜘权重 不仅考虑玎、t 彤的影响，也考虑文档长度的影响，权重公式为： n 墙= 扎1 0 9 ( 差) 压甄西研 ( 2 4 ) 2 2 2 4 f t c 权重 f c 与啦的差异在于利用频数的对数代替频数，减弱了频数对权重的影响。 一。舻；塑堕兰! ：竺些耋!( 2 5 ) 吼萨面荪菰鬲雨意蓊 2 5 本文试验所采用的权重方法是z t c 权重。 2 3 维数约简 构成文本特征项的数目往往非常大，这会给分类带来如下问题： 1 计算复杂度高，维数灾难。 2 导致过度拟合，泛化能力降低。 3 容易带入噪音，影响分类性能。 所以必须采取措施降低维数，简化原始的特征集。目前，维数约简的方法包括 特征选择和特征重构。 特征选择又叫独立评估法，在特征选择时一般都是利用某种评价函数独立地对 每个原始特征项进行评分，然后按分值的高低将它们排序，从中选取若干 个分值最高的特征项，以达到减少总特征数的目的。 9 基于类信息的潜在语义多类文本分类模型研究 特征重构也叫综合评估法。其基本思想是利用映射( 或变换) 的方法把原始项 集映射到较低维的空间中，映射后的特征叫二次特征，他们是原始特征的 某种组合( 通常是线性组合) 。所谓特征重构在广义上就是指一种变换。 若y 是测量空间，x 是特征空间，则变换a ：x y 就称为特征提取器。 我们将介绍几种常用的特征选择方法： 2 3 1 文档频数( d o c u m e n tn e q u e n c e ) 这是最简单的一种评价函数，文档频数d f ( 。) 是指在所有的训练文本中出 现了项t 。的文本数由于这种方法考虑的因素太少，仅考虑了词频，所以现在很 少被采用，目前用得更多的是以下几种基于信息论的评价函数。 2 3 2 信息增益( i n f o r m a t i o ng a i n ) 信息增益是决策树技术中经常采用的一种选择最佳节点的方法。它利用的 是信息论中熵( e h t 聊) 的概念。在信息论中，熵是对事物不确定性的一种度量。 设s 是s 个文本构成的训练集合。g ： c 1 ，c 2 ，) 为类别集合。设s ，是s 中属于 类岛的文本数，则一个文本关于其类别的熵( 即期望不确定度) 为： n m 渤_ 。) = 一n l 0 9 2 。) ( 2 6 ) # 1 其中，鼽是任意样本属于类c 的概率，该概率可以用s s 来估计。 设根据项t 是否在文本种出现，可把样本集分为两类，一类a 是在其中出现 了的文本t 另一类口是t 没有在其中出现的文本。则a 类重的文本关于其类别的 熵为： n e ( t ) = 一p ( c l 0 9 2 p ( c i l t ) ( 2 7 ) i = 1 其中，p 也i t ) 表示当t 出现在文本中时，文本属于类g 的概率，可用a 中属于 类岛的文本数与a 中所有文本数的比值来估计。与之类似，b 类中的文本关于其 类别的熵为： n e ( 刁= 一p ( c iid l 。9 2 p ( q i 刁 ( 2 8 ) = l 1 0 墨三童壅奎坌耋塑堕 其中，p h l ) 表示当t 没有出现在文本中时，文本属于类c i 的概率，可用日中 属于类岛的文本数与b 中所有文本数的比值来估计。 因此，如果训练文本集按项t 来划分的话，文本关于其类别熵将变为： j ( t ) = p ( ) e ( t ) + p ( d 。e ( 刁 r 29 1 = 一p ( t ) ：1 p ( c l l t ) l 0 9 2 p ( c i i t ) 一p ( 刁：。p ( c 1 1 0 l 0 9 2 p ( q l d 、 其中p ( t ) 为项在文本中出现的概率，可以用陋l s 来估计，p ( 刁为项t 不在 文本中出现的概率，可以用i b l s 来估计一般情况下，此时的熵将比原来的 熵，( 8 “8 z ，s 。) 更小，即这个项给我们提供了一定的信息，使得分类时的不确 定程度降低了。它提供的信息量的多少可以用信息增益来表示： 坩o 三翁兰+ 文稿妊州t ) 轫( 峒，唱。错( 2 l o )= p o ) 墨l p ( c i l ) l 0 9 2 ：鬟警+ p ( t ) ：1 p ( c l f o l q 9 2 蛩潜 、7 信息增益的不足之处在于，它考虑了项未出现的情况，即( 2 1 0 ) 右边的后半 部分。虽然某个项不出现也可能对判断文本类别有贡献，但实验证明，这种贡 献往往远远小于它所带来的干扰，特别是在类分布和项分布高度不平衡的情况 下。对某一类来说，绝大多数项都是“不出现”的。即p ( 乃p ( ) ，此时信息增 益的主要部分是信息增益公式中后一部分( 代表项不出现的情况) ，而不是前 一部分( 代表项出现的情况) ，这时信息增益的效果就会大大降低了。中给出在 实验中，原始玎0 够法的分类精度为7 3 ，用信息增益进行特征选择后精度提高 到8 2 ，但在处理上述“高度不平衡”数据集时，精度下降到7 5 。 2 3 3互信息( m u t u a li n f o r m a t i o n ) 项t 和类c 之间的互信息定义如下： 订( ，c ) = l 0 9 2 p ( 亡i c ) 一l 0 9 2 p ( 亡) = l 0 9 2 错 ( 2 1 1 ) = 1 0 9 2 耥 对于一个项t 和一个类c ，我们可以构造一个双向列联表( 如表2 1 ) ， 其中a 为项t 在文本中出现并且该文本属于类c 的文本数，b 为项t 在文本中 出现但该文本不属于类c 的文本数，g 为项t 在文本中没有出现但该文本属于 类c 的文本数，d 为项在文本中没有出现而该文本也不属于类c 的文本数。 基于类信息的潜在语义多类文本分类模型研究 表2 1 ：项和类c 构成的列联表 c c 卜 ab fed 设为训练文本的总数，则我们可以用下面的式子来近似表示项t 和类c 之 问的互信息： 埘 c ) “l o g ：万高卷丽 ( 2 1 2 ) 通常采用平均互信息或最大互信息作为项t 的评价函数： 埘( t ) = p ( c 1 ) 埘( t ，c ) ( 2 1 3 ) 埘赢( t ) = 曾 懈( t ，c 1 ) ( 2 1 4 ) 互信息的缺点在于：它没有考虑项出现的频率，在很大程度上会受到项的边缘 分布的影响，由前面的式子可知，在条件概率相同的情况下，稀有词将获得更高 的互信息量，从而造成了互信息评价函数常倾向于选择稀有单词。因此这种方 法不适舍于对那些出现频率差别很大的项进行比较评估 2 3 4 妒统计量( x 2s t a t i s t i c ) 与互信息类似，我们可以画出项和类c 的双向分类列联表。x 2 统计量则可 以根据此表检验项t 和类c 之间是独立无关的还是具有显著的连带关系，我们感 兴趣的是那些与各个类有强关联的项。令a 为训练文本集中项t 和类c 同时出现 的次数；曰为项t 出现而类c 不出现的次数：e 为项t 不出现而类c 出现的次数；d 为 项t 和类c 都没有出现的次数；为训练文本集中的样本总数。则： 娥纠= 两高第蒜( 2 1 5 ) 如果t 和c 之间是独立的，则x 2 统计量的值将为0 。对于训练文本集中的每一个类。 计算出每个项与该类之间的x 2 统计量的值。根据这些值可以求出以下两种评 分： x ( t ) = p ( q ) x 2 ( t ，q ) ( 2 1 6 ) 第二章文本分类概述 x ：。( ) = r r 马耳p ( 岛) x 2 ( 亡，g )( 2 1 7 ) t ；1 对于x 2 统计量要注意两点： 1 当a 一0 ，b 一时，它不能过滤掉不合适的项。 2 当a 一0 ，b 一0 时，它对低频词不公平，即容易删除本该保留的项。 2 3 5 特征重构 特征是将原有的特征集t 加以联系和转化以构建新特征集r 的过程，一 般l r i i t | ，因而可达到降维的效果；特征重构解决的问题是由于一词多义、多 词一义的现象大量存在于文本信息中，导致文本的原始项可能不是文档内容表 示的最佳维度。特征重构试图通过重构新的特征来解决上述问题。方法有项聚 类( ，工h mc l u s t e r i n g ) 和潜在语义索引( l s i ) 等 项聚类项聚类将在语义方面具有高度关联性的项分组，从而该分组的表示将 代替这些项成为向量空间中的维度。项聚类有别于特征选择，因为前者 试图阐述项之间意义方面的关联性，而后者则主要着眼于不提供信息的 项。l e w i 8 提出了相互近邻聚类算法，该算法根据某种计算相似度的度量 计算两项之间的相似度而产生聚类。 潜在语义索引潜在语义索引基于这样的假设，即在整个文档中项的使用模式 存在隐性结构，该结构可以通过统计方法进行评估。潜在语义索引使用与 特征向量分解以及因子分析紧密关联的奇异值分解( s v d ) 技术我们将在 第4 章详细阐述该思想。 2 4 经典文本分类算法 文本分类经过几十年的研究发展，目前已经有有很多种成熟的算法，其中 比较著名的有：k 算法，r _ 0 c c h i o 算法，肌扬eb n g e 5 算法，决策树算法。神经网 络算法，支持向量机算法。 下面简要介绍一下这些经典的分类算法： 1 3 基于类信息的潜在语义多类文本分类模型研究 2 4 1k n n 分类算法1 “1 4 基于实例的分类算法中最基本的是删算法。直观地理解，所谓的j c 近邻， 就是考察和待分类文本最相似的七篇文本，根据这篇文本的类别来判断待分类 文本的类别值。相似值的判定可以使用欧拉距离，或是余弦相似度等。而最相 似的_ | 篇文本按其和待分类文本的相似度高低对类别值予以加权平均，从而预 测待分类文本的类别值。在女近邻分类器中。参数七的取值非常重要，值选取过 小，不能充分体现待分类文本的特点，而如果值选取过大，则会造成噪声增加， 导致一些和待分类文本实际上并不相似的文本亦被包含进来，使得分类精度降 低。利用自近邻分类器进行分类，文本向量z 属于类别c | 的权值( gi z ) 由下式计 算，权值越高，则认为文本向量z 属于类别c t 的概率越高： 耳 w 7 ( c i l z ) = ：s 2 m ( z ，z i ) p ( c i l z 女)( 2 1 8 ) 七= l 其中，成m 函数是向量之间的余弦相似度；。1 ，石2 ，巩是训练集中和z 余弦相 似度最大的个文本向量i 而p h f k ) 当钆属于类别c 。时为1 ，否则为0 。 由上述过程可见，七近邻法没有离线训练阶段，所有的计算都是在线进行 的。因此这种方法的实时性不好，计算的时间复杂性是0 伍t ) ，其中l 是待分 类文本向量中非。的分量个数，而n 是训练集的文本数量。 2 4 2 r d c c h i o 算法”“1 这是一种基于向量空间模型和最小距离的方法，其优点是实现简单，计算 速度快。计算步骤是：将文本表示为向量空间中的高维向量，按照训练集中正例 的向量赋予正权值，反例的向量赋予负权值，相加平均以计算每一类别的中心。 对于属于测试集的文本，计算它到每一个类别中心的相似度，将此文本归类于 与其相似度最大的类别。由其计算过程可见，如果对那些类间距离比较大而类 内距离比较小的类别分布情况，最小距离分类器能达到较好的分类精度，而对 于那些达不到这种“良好分布”的类别分布情况，最小距离分类器方法效果比 较差。由于其计算简单、迅速，所以常常用这种方法的结果作为其他分类方法 的比较标准。其分类以及评价过程可以表示如下： 1 求取类中心，对于第a 类，其类中心向量g e 眦e n 的计算公式为： 1 墨 g e 胁巩= 素：d o ( 2 1 9 ) ”j j 1 4 篁三童塞查坌耋壁 其中，l 是第g 类中文本的数目，而d o 是类别为a 的第j 个文本向量。 2 对待分类文本d d 岛进行分类，其类标签工n 6 e 屯按照下式计算： 三曲e z 。= n r 9 m o s 。m ( g e n e q ，d o 岛)( 2 2 0 ) 其中，相似度s z m 的计算通常采用余弦相似度，即两个向量的点积除以两 个向量长度的乘积。 2 4 3n a 譬v eb a y e s 算法卅 假定每个实倒d 可由其属性值的合取来描述，即d = ( 叫1 ，训2 ，) ，则贝叶 斯方法的目标是在给定d 的情况下，得到最可能的目标值a ，： ( k a p = 盘r 9 m 口z “c 尸他lt j 。，缸j 2 ，叫n ) ( 2 2 1 ) 根据贝叶斯公式，有： p2 哪。咄e 。哗赫慧产 ( 2 2 2 ) = 珊曾m 口z c f c p ( 伽l ，埘2 ，叫ni 岛) p ( c 1 ) 、 在上式中，估计p 他) 的值比较容易，只要计算每个岛在训练样本集中出现的频 率就可以得到。但要估计每一个p ( 1 ，叫z ，t j 。l 臼) 项的值则比较困难，因为 所有这些项的数量等于所有可能实例( ”l ，”。，”。) 的数量乘以所有可能类 别c i 的数量。而为了获得合理的估计，实例空间中每个实例必须出现多次，因 此需要非常大的训练集合。 朴素贝叶斯分类器基于这样一个基本假定，即假定实例中各属性值之间是 互相条件独立。即： p ( 叫1 ， 2 ，训。lc i ) = p ( 屿ic i ) ( 2 2 3 ) ， 把它代入( 22 2 ) ，即得到朴素贝叶斯公式： c k 日= 口r g m k e g p ( 包) p ( 2 码l 勺) ( 2 2 4 ) j 其中，c 。表示朴素贝叶斯分类器输出的目标类别值。从上式可以看出，在朴素 贝叶斯分类器中，须从训练数据中估计的不同p ( 屿lc j ) 项的数量只是不同属性 基于类信息的潜在语义多类文本分类模型研究 值数量乘以不同类别值数量。这比要估计所有的p ( l ，奶，ic 1 ) 项所需的 量要小得多。 概括地说，朴素贝叶斯方法根据它们在训练样本集中的频率估计不同 的p 他) 和p ( 屿ic 1 ) 项。这些估计对应了待学习的假设。然后该假设使用上式来 分类新实例。只要条件独立性假定能够满足，朴素贝叶斯分类0 k b 等于c k p 。 2 4 4 决策树算法呻”1 “ 决策树算法是一种逼近离散值目标函数的方法，在这种方法中分类器被表 示为一棵决策树。学习到的分类器能被表示为多个矿琥e 扎的规则。它是通过把 实例从根结点排列到某个叶子结点来分类实例，叶子结点即为实例所属类别。 树上的每一个结点说明了对实例的某个属性的测试，并且该结点的每个后继分 支对应于该属性的一个可能值。分类方法就是从决策树的根结点开始，测试这 个结点指定的属性，然后按照给定实例的该属性值对应的树枝往下移动。这个 过程在以新结点为根的子树上重复 多度拟合是决策树需要解决的一个难题，有几种途径可被用来避免决策树 学习中的过度拟合： 1 及早停止树增长，在i d 3 算法完美分类训练数据之前就停止树增长。 2 后修剪法( p 0 8 t _ p r u n e ) ，即允许树过度拟合数据，然后对这个树进行后修 剪。 q u i n l a 于1 9 9 3 年出版的书中进一步详细描述了决策树，并提供了c 4 5 算法。 2 4 5 神经霸络圳 人工神经网络的研究是受到生物学的启发，它模拟生物的学习系统，由相 互连接的神经元组成的异常复杂的网络。每个单元有一定数量的输入，并产生 单一实值输出。 一种应用广泛的训练多层网络的方法为反向传播算法，它的原理是基于误 差的梯度下降准则。其算法如下： 对于训练样例中的每个饵西，童是网络输出向量，穗! 目标输出值 1 6 第二章文本分类概述 1 把实例商俞入网络，计算网络中每个单元u 的输出仉。使误差沿网络反向传 播。 2 对于网络的每个输出单元计算它的误差项乳 以一d k ( 1 一d k ) ( “一o k )( 2 2 5 ) 3 对于网络的每个隐藏单元危，计算他的误差项以 以一o h ( 1 一o ) 以 ( 2 2 6 ) k 讲句妇 4 更新每个网络权值屿。 。一屿。+ 屿。 ( 2 2 7 ) 反向传播算法最令人感兴趣的特征是他能创造出网络输入中没有明确出现的特 征。神经网络的优点是度于训练数据中的错误健壮性很好，并也已被成功的应 用于很多领域如视觉分析，语音识别和机器人控制。其缺点是计算复杂度高。 2 4 。6支持向量机4 “”1 支持向量机( s u p p o r tv e c t o rm a c h i n e 8 ，s v m ) 方法是由v v a 巾n i k 与其领导 的贝尔实验室的小组一起开发出来的一种机器学习技术。它在多种分类问题 表现出优异的推广性能。其基本思想是基于统计学习理论的结构风险最小化。 如果给出两类线性可分样本，在给出线性分类面的时候，人们直观的趋向于将 分类面取在离两类的样本点都距离较远的地方，因为感觉上这种做法比较保 险。v a p n i k 从数学理论上给出了这种做法的理论依据，并推导出了这种方法风 险性能的衡量，以及一整套求解的步骤。目前这一套理论还有较多值得继续发 展和推敲的地方 在线性可分的情况下，可以假设线性分类面的形式为： 9 0 ) = u 甄+ 6 = 0 将判别函数归一化，使得两类所有样本都满足k ( z ) l = 1 。即 仉【( u 乱) + 6 】一1 o ，i = 1 ，2 ，n ( 2 2 8 ) ( 2 2 9 ) 1 7 基于类信息的潜在语义多类文本分类模型研究 其中。玑= 士i ，是样本的类别标记；甄是相应的样本。也就是使得离分类面最 近的样本成立1 9 ( 嚣) l = 1 ，这样样本的分类间隔就等于2 川u 设计的目标就是 要使得这个间隔值最小。据此可以定义l a 擎矗n g e 函数： l ( u ，6 ，口) = ；( u ，u ) 一m 玑【( “，- 甄) + 6 一1 ( 2 3 0 ) 一 t = 1 其中o 0 为l a g r a n g e 乘数，对u 和6 求偏微分并令其为0 ，原问题转换成为如下 对偶问题：在约束条件 玑吼= o ，吼o ，t = 1 ，2 ，竹 ( 2 3 1 ) t 篁1 下对吼求解下列函数的最大值： nn q ( 旬= n 。一；吼玑始( n ) i = 1 j = l ( 2 3 2 ) 如果酊为最优解，那么 n 矿= ：o 池甄( 2 3 3 ) i = l 对于线性不可分的情况，可以引入松弛因子，在求最优解的限制条件中加入对 松弛因子的惩罚函数。值得指出的是，最终判别函数只包括与支持向量的内积 的求和，所以识别时计算复杂性只取决于支持向量的个数。 由于具有较好的泛化性能，支持向量机被用于多个模式识别领域。在文本 分类方面亦有多种研究试验结果。在多个实验结果中，s v m 均取得了较原有多 种分类方法更高的分类精度。 除了以上这些方法以外。还有许多近年来涌现的许多新的算法，如基于潜 在语义的文本分类算法【2 1 ”1 ，基于最大熵算法。3 “1 ，基于模糊一粗糙集算法等 等“。 2 5 评价指标 因为文本分类从根本上说是一个映射过程，所以评估文本分类系统的标 志是映射的准确程度和映射的速度。映射的速度取决于映射规则的复杂程度， 而评估映射准确程度的参照物是通过专家思考判断后对文本的分类结果( 这 第二章文本分类概述 里假设人工分类完全正确并且排除个人思维差异的因素) ，与人工分类结果 越相近。分类的准确程度就越高。评估文本分类系统主要有两个指标：准确 率( p r e c i s i o n ) 和召回率( r e c a l l ) 。 假设有m 篇文本d l ，d 2 ，n 。分别属于n 个类别c 1 ，c 2 ，中。分别由专 家和自动分类程序对全部文本进行分类。对类别g ，其召回率r l 、准确率只公式 分别为： 且= 瓮 ( 2 只= 甏 ( 2 3 5 ) 其中坛是m 篇文本中专家认为属于c i 类的文本数； k 是m 篇文本中分类器预测 为c l 类的文本数：吼是专家和程序都认为属于c i 类的文本数，即被正确分类的 文本数。 准确率和召回率反映了分类质量的两个不同方面，两者必须综合考虑，不 可偏废，因此，存在一种新的评估指标一f 1 测试值，对类别c l ，其数学公式如 下： f 1 l = 黼 ( 2 3 6 ) 另外还有微平均和宏平均两种计算准确率、召回率和f 值的方法。微平均 和宏平均是评测系统整体性能的两种方法有m 冗、m p 和m f l 表示微平均中的 微观召回率、微观准确率和微观f 1 值，则分类系统的微平均计算公式如下： m r = 鼢 ( 2 s z ) 一敲 ( 2 3 8 ) 棚= 躺 ( 2 s 。) m 虬+ m 只】 用m r 、m p 和m f l 表示宏平均中的宏观召回率、宏观准确率和宏观f 1 值， 则分类系统的宏平均计算公式如下： m r = 砉r ( 2 - 如) 薹王耋焦星塑堂垄亘墨查耋皇奎坌鲞塑型堡塞 m p = 去只 ( 2 4 1 ) 。t = 1 心= 黼 ( 2 4 2 ) 微平均f 1 平等考虑每一个文档，因而它的值将主要受常见类的影响：而宏平 均f l 平等对待每一个类别，因此它的得分主要受稀有类的影响。 第三章多类文本分类 3 1 多类文本分类问题 我们前面定义1 1 中对于2 管未作限制。根据2 管的不同，分类的模式可以分为 以下两大类： 二元分类问题，即属于或不属于问题，当酽为单元素集合。 多类分类问题，属于个类中的某一个或几个类( 多标签) ，可以拆分成二 元分类问题，当2 留为多元素集合。 上一章我们介绍的分类算法大都是二元分类算法。但是在现实世界中的许 多任务中，我们需要进行多类分类。例如：医学诊断上需要确定病人得了某几种 病中得哪一种；数字识别中，要确认0 至9 中得具体数字；语音识别系统要辨认出 语音单元属于哪个音符。而在文本分类方面，有大量的文本属于多个类别，例 如综述性的文档，交叉学科文章等等。所以我们现在的