（计算机应用技术专业论文）基于粗糙集和支持向量机的文本分类方法研究.pdf

摘要 摘要 本文首先对文本分类的发展现状及存在问题进行了系统性阐述，按文本分 类的流程对文本分类相关技术进行了介绍和探讨，重点分析和研究了文本表示、 特征选择技术以及文本分类算法等文本分类关键技术。 本文较为系统地总结和研究了粗糙集和支持向量机的基本原理。并分别就 属性约简算法、支持向量机训练和分类算法等问题加以讨论。 为了更好地提高文本分类准确率，降低支持向量机分类算法的运行时间， 针对文本经过预处理和文本表示后高维稀疏性的特点，本文在研究和分析了一 些粗糙集属性约简算法及其存在的问题的基础上，提出了一种改进的基于属性 重要度函数的属性约筒算法，并将该算法和相关已有算法进行了对比分析，从 理论上证明了该改进算法的有效性，算法的时间复杂性优于同类算法。 结合粗糙集和支持向量机的各自优点，提出了基于粗糙集与支持向量机相 结合的文本分类方法，在对文本进行特征选择后，利用改进后的粗糙集属性约 简算法，对特征选择后的特征向量空间进行约简，进一步降低特征向量空间的 维数，减少冗余属性对分类效果的影响，缩短支持向量机的训练时间，并据此 设计和实现了一个结合粗糙集理论和支持向量机技术的文本分类实验系统，对 比了降维前后分类效果，探讨了惩罚因子c 的选择对分类结果的影响。实验结 果表明，在文本特征向量空间的维数大于2 5 0 0 维情况下，采用粗糙集和支持向 量机相结合的文本分类方法取得了较好的分类效果。从而从实践上证明了本文 提出的改进约简算法在高维情况下是有效的。 最后，对本文取得的成果以及不足进行了总结，并对下一步的研究工作进 行了展望。 关键词：文本分类；特征选择；粗糙集：支持向量机；属性约简 a b s t r a c t a b s t r a c t t h ep r e s e n ts i t u a t i o no ft e x tc l a s s i f i c a t i o na n dt h ee x i s t i n gp r o b l e m sw e r ef i r s t s y s t e m a t i c a l l ye l a b o r a t e d ；t h er e l e v a n tt e c h n o l o g i e so ft h et e x tc l a s s i f i c a t i o nw e r e i n t r o d u c e da n de x p l o r e da c c o r d i n gt ot h ec l a s s i f i c a t i o nf l o w t h ek e yt e c h n o l o g i e s ， t e x tr e p r e s e n t a t i o n ，f e a t u r es e l e c t i o na n dt e x tc l a s s i f i c a t i o na l g o r i t h m s ，e t c ，w e r e s e l e c t i v ea n a l y z e da n di n v e s t i g a t e d n l ep r i n c i p l e so fr o u g hs e tt h e o r y , s u p p o av e c t o rm a c h i n e ( s v m ) w e r e s y s t e m a t i c a l l ys u m m a r i z e da n di n v e s t i g a t e d a t t r i b u t er e d u c t i o na l g o r i t h m s ，s v m t r a i n i n ga n dc l a s s i f i c a t i o na l g o r i t h m sw e r ed i s c u s s e dr e s p e c t i v e l y i no r d e rt or a i s et h ea c c u r a c yr a t eo ft e x tc l a s s i f i c a t i o na n dd e c r e a s er u n n i n g t i m eo fs v mc l a s s i f i c a t i o n a l g o r i t h m ，a i m e d t ot h ec h a r a c t e r i s t i c so fh i g h d i m e n s i o n a l i t ya n ds p a r s i t ya f t e rt e x tr e p r e s e n t a t i o n ，a ni m p r o v e da t t r i b u t er e d u c t i o n a l g o r i t h mb a s e do na t t r i b u t es i g n i f i c a n c ef u n c t i o nw a sp r o p o s e da f t e ri n v e s t i g a t e da n d a n a l y z e dt h ew e a kp o i n t so ft h es o m ee x i s t i n ga t t r i b u t er e d u c t i o na l g o r i t h m s ，i t s f e a s i b i l i t ya n dl o w e rt i m ec o m p l e x i t yo ft h ei m p r o v e da l g o r i t h m sw e r et h e o r e t i c a l l y p r o v e db yt h ec o m p a r a t i v ea n a l y s i sb e t w e e nt h ei m p r o v e do n ea n do t h e r s ak i n do ft e x tc l a s s i f i c a t i o nm e t h o dc o m b i n e dw i t l lt h em e r i t so fr o u g hs e ta n d s v mt h e o i e sw a sp r o p o s e d t h ei m p r o v e da t t r i b u t er e d u c t i o na l g o r i t h mw a su t i l i z e d t of u r t h e rr e d u c et h ed i m e n s i o no ft e x tf e a t u r ei t e m sa f t e rf e a t u r es e l e c t i o n ，d e c r e a s e d t h e i n f l u e n c e so ft h er e d u n d a n c ya t t r i b u t e s ，s h o r t e nt h et r a i n i n gt i m eo fs v m a l g o r i t h m ，a n dh e r e b yat e x tc l a s s i f i c a t i o ns y s t e mc o m b i n e dw i t hr o u g h s e ta n ds v m w a sd e s i g n e da n di m p l e m e n t e d ，t h ec l a s s i f i c a t i o ne f f e c t sb e f o r ea n da f t e ru s i i l g i m p r o v e da t t r i b u t er e d u c t i o na l g o r i t h mw e r ec o m p a r e d ，e x p l o r e dt h es e l e c t i o no f p e n a l t yp a r a m e t e rc t oa f f e c tt h ec l a s s i f i c a t i o nr e s u l t t h ee x p e r i m e n t a lr e s u l ts h o w n t h a tb e t t e rc l a s s i f i c a t i o ne f f e c t sc c o u l db e a c q u i r e db ya d o p t i n g t h em i x e d c l a s s i f i c a t i o nm e t h o dw h e nt h ed i m e n s i o no ft h et e x tf e a t u r es p a c ew a sl a r g e rt h a n 2 5 0 0 ，s ot h ei m p r o v e da t t r i b u t ea l g o r i t h mw a si m p r o v ei np r a c t i c eu n d e rt h eh i 曲 d i m e n s i o ns i t u a t i o n f i n a l l y , t h ea c h i e v e m e n t sa n di n s u f f i c i e n tp o i n t so ft h ea r t i c l ew e r ec o n c l u d e d ， t h en e x tr e s e a r c hw a sl o o k e da h e a d k e y w o r d s ：t e x tc l a s s i f i c a t i o n ；f e a t u r es e l e c t i o n ；r o u g hs e t ；s u p p o r tv e c t o r m a c h i n e ；a t t r i b u t e sr e d u c t i o n i l 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：配琢穿签字日期：溯，年，砂月砷日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：夏像匆喈导师签名：眵殳p 旁杉仅 签字日期：加矿年7 1 月哆e l 第l 章引言 第1 章引言 本章将首先介绍本文的选题依据及研究意义，然后介绍文本的国内外发展 和研究状况，并就文本高维问题的研究情况作了简单介绍，最后阐述了本文的 研究工作以及论文的组织结构。 1 1 选题背景与研究意义 事物总是伴随着矛盾而发展的。以电子文档为代表的i n t e m e t 信息数量的迅 速增长，一方面为我们获取有效的、廉价的、丰富的和可靠的数据资源提供了 便利；但另一方面也使得人们面临着如何从海量信息中提取自己所需信息的重 大任务。“信息丰富而知识贫乏成为二十一世纪信息化社会不可避免出现的现 象之一。如何利用计算机对信息进行行之有效的辨识和加工处理，为用户最大 程度地提供适当的智力支持和帮助，提高信息的使用效率，是一个十分有意义 的研究课题。 文本自动分类是近些年以来信息应用领域中一个被广为关注的课题，它是 一种基于内容的有指导的自动信息管理核心技术，旨在根据一些已经分配好的、 具有预先定义类标签的训练文档集合，来帮助用户对i n t e m e t 上的积累的大量杂 乱无章的未知文档分配这些类标签，从而使得未知文档便于加以辨识和分类。 由于使用向量空间模型将文本表示成向量形式后，文本具有高维的特性。 在众多特征项中，往往存在许多冗余特征项。它们的存在一方面增加了存储空 间，另一方面使分类器具有较高的计算复杂度，分类算法的泛化能力降低，出 现所谓“过学习”现象。如何对高维文本特征空间进行有效的降维处理，删除 冗余特征项，最大限度地保留对分类起重要贡献的特征项，将在很大程度上方 便地为用户提供了更高的查询效率、更准确的查询结果。因此研究自动文本降 维问题具有较大实用价值和广阔的应用前景。 1 2 文本分类关键技术综述 早期的文本分类主要是通过经过严格训练的专业人员手工对文档进行分 第1 章引言 类，其工作强度之大，成本之高可象而知。互联网上大量电子文本的出现，众 多新的分类需求开始纷纷被提出。例如，通过信息过滤，只将用户需要的文献 类别提供给用户；根据用户的阅读兴趣，为用户提供个性化服务；在远程大型 联机信息检索服务中，大量文献需要经常更新。为了缩短检索的响应时间，文 档数据库中的文献也需要分类存放。这些都离不开对文档进行分类，使得传统 的人工文本分类技术开始力不从心，从而促使人们开始对文本自动分类的研究。 1 2 1 文本分类问题概述 文本分类是文本挖掘重要的组成部分，它是指在给定的分类体系下，根据 一定的算法对建立在预定义的训练集的内容或属性得到分类判别规则，将大量 新的未标明类别的文本，划分到一个或多个已知类别或相似文档集合中去的过 程。其目的在于对文本集进行有序地组织，把相以的、相关的文本有效地组织 在一起。这种形式的分类是一种有指导的学习过程，其实质是一个从未知领域 向已知领域映射的过程。由于一篇文本往往可以同时属于多个类别，因此这种 映射可以是一一对应的，也可以是一对多的。 从数学角度可以将文本分类的过程描述如下：存在一个映射f d _ c ，其 中d = d l ，d 2 ，d m ) 可以是个有限集，也可以是个无限集，表示所有待分类文本集， c = c l ，c 2 ，c a ) 必须是有限集，表示在给定分类体系下所有文本类别的集合。确 定文本分类的映射规则f 是文本分类的关键，它根据已经有训练集的样本信息得 到分类规则，建立相应的判别公式和判别规则。当遇到新的待分类文本后，根 据所得文本分类的映射判别规则，以确定该文本所属类别。 1 2 2 文本分类的流程 文本分类是一个有指导的学习过程。一个完整的文本分类过程主要包括训 练和分类两个阶段，其中文本预处理及文本表示。即将文本集表示成能被计 算机处理的形式；特征提取。即根据一定的策略，选择文档中重要程度较大 的特征项组成文本特征向量空间；根据预处理后的训练集构建并训练文本分 类器，得到分类模型，并根据该模型将未知待分类文本映射到已知类别中。这 三个步骤贯穿其中。上述具体过程如图1 1 所示： 2 第1 章引言 训练阶段分类阶段 图1 1 文本分类流程图 1 2 3 文本分类的关键技术及难点 中文文本分类的关键技术主要包括文本预处理、文本表示、特征选择、分 类算法等关键问题，它们将最终影响分类算法的结果，下面分别进行阐述。 1 2 3 1 文本预处理 由于不同的文本集的格式及编码格式不统一，不能直接被计算机处理。因 此，必须经过一定的处理。文本预处理是文本分类后续步骤的基础，主要是去 除语料库中的噪音信息、剔除文档中所有与分类任务无关的内容、规范文本格 式，使其符合分类模型的输入要求，并对训练和测试文本集进行分词和参数统 计的工作。 文本预处理主要包括去除文档中的格式标记、过滤非法字符、分词以及去 除停词表中的停用词等步骤，其中常见的中文分词基本算法【1 】有：( 1 ) 基于词典与 规则匹配法。基于词典与规则的方法应用词典匹配，汉语词法或其它汉语语言 知识进行分词，这类方法简单、分词效率较高，但对词典的完备性、规则的一 致性等要求比较高。匹配策略有：最大匹配法、最小匹配法、逆向匹配法、增 字或减字匹配法、双向扫描法。( 2 ) 标志法。如切分标志法、统计标引法。( 3 ) 词 第1 章引言 频统计法。基于统计的分词方法将汉语基于字和词的统计信息，完备性较差。( 4 ) 语义语用法。如后缀分词法。目前使用最多的是基于词库的分词方法。中国科 学院开发i c t c l a s3 0 是目前使用最广泛的中文分词软件之一。 经过上述步骤得到了所有训练文本集的原始特征集。 1 2 3 2 文本表示( t e x tr e p r e s e n t a t i o n ) 由于预处理后的文本是半结构甚至是没有结构的，为了能让计算机能够对 文本进行分类，就必须将文本表示成计算机能够处理的形式。 s a l t o n 提出的向量空间模型( v s m ) 有效地解决了非结构化文本数据的处理 问题。在空间向量模型中，语料库中所有的文本被统一转换成向量形式，从而 便于计算机处理。向量空间模型示意图如图1 2 所示。 ，秽趋。，w ：) 图1 2 向量空间模型示意图 向量空间模型主要涉及以下几个概念： 文档( d o c u m e n t ) 。通常是指一篇文章； 特征项( t e r m ) 。所谓特征项是一个语义单位，通常是从文档中选择出来 的能代表文档内容的关键词。理论上，文本特征项可由字、词或短语组成。但 是大量实验表明，选取词作为特征项要优于字和短语，因为它更能够代表文档。 权莺( w e i g h t ) ，假设共有1 1 1 个文档、n 个不同的项，那么文档d = t l ，t 2 t n ) 。 为了标识特征项t k ( 1 k ) 在文本中的重要程度，特征项“常被赋予一定的 权重w k ，它反映了特征项在某类文本区别于其它类文本的重要性。 4 第1 章引言 t it 2t 3t d i- l l- 1 2 - i n d 2 d 3 - - d - 图1 3 向量空间模型中的文本表示形式 由词或短语组成的文本是可以被看作是由一组正交特征矢量所形成的向量 空间，每个文档d 被看作是向量空间中的一点，v ( d ) = ( t l ，w 0 ，( t 2 ，w 2 ) ，( t n ，w n ) ) 表示为向量空间中的一个文本的特征向量。其中v ( d ) 表示特征向量，t i i 表示特征 项，w n 表示某特征项t n 的权重，特征项权重充分反映了该特征项标识文本内容 的共享程度以及区分不同文本能力。 确定特征项的权重是文本表示的关键。在向量空间模型中，由于t f i d f 函 数具有简单直观、处理速度快等优点，因此它是目前使用较多的权重计算函数 之一。它的数学表达式为：w t i i = t f i jxl 0 9 2 ( n i d f i ) ，其中t f i j 称为词语频率， 表示特征词i 在文档j 中出现次数；i d f i 称为倒排文档频率，表示文档集中包含 特征词t i 的文档数。从数学表达式可以看出权重w t i j 和t f i i 成正比，和i d f i 成 反比。图1 3 所示的是文本在向量空间模型中的表示形式。 为了减少文本长度对特征项权值的影响，一般将t f i d f 权重归一化至区间 o ，1 】中，公式如下： 耽 ， 一寥! 巧_ * l o g ：( _ ) 其中分母为归一化因子，它是各分量平方和的根。 上述公式表示如果权值w t i j 越大表示特征词在文档中出现词数越多、越集 中，那么越重要。而如果一个特征词在多篇文章中同时出现，那么这个特征词 5 第1 章引言 也不重要。特别地，若特征词在所有文档中都出现，即d f i = n ，则w t i j = o 。换 句话说，尽管特征词出现次数很多，但如果其分布比较均匀，则说明它的区分 类别能力比较弱。最终那些具有较高出现频率并且在文档集合中较少的文档中 出现的特征项具有较高的权重。 使用向量空间模型表示文本后，文本被表示成一个为稀疏矩阵a = ( a i i ) m 。， 矩阵中的大部分的元素为零值。为了缩减存储空间，降低系统开销，只保留矩 阵中a i i o 的元素。 尽管向量空间模型没有考虑特征项之间顺序，并假设所有特征项都满足两 两正交，不考虑特征项之间的相关性，而该假设一般只适用于基于文本主题的 分类，并且可能会造成文本结构和语义信息的损失【2 1 。但是，由于向量空间模型 方法可以使文本的表示和处理形式化，通过引入各种成熟的统计方法进行定量 分析，在更大程度上利用了文本中蕴含的语义信息，具有很好的可操作性，并 与具体的应用领域无关，因此该模型是目前使用最多的文本表示模型之一。 1 2 3 3 特征空间降维的主要方法一特征选择 1 ) 文本特征空间降维的必要性 文本分类所需的训练文本集必须包含足够的特征信息，以便通过训练算法 得到分类器。理论上说，一个训练文本集应该要能够包含所有能够反映数据之 间的关系的特征项，否则将会影响分类器的构建及分类的效果。然而现实面临 的问题是，由于经过文本表示后的文本特征向量空间一般会达到几千维至几十 万维。样本和特征项数量的增加，一方面为知识发现提供了更加丰富的信息， 同时也带来了巨大的挑战。 由于在文本特征向量空间中，特征项对分类的贡献是不尽相同，而且这样 的样本分布往往十分稀疏：比如，在整个文档集中，尽管有些特征项数目很多， 但是它在文本分类时所起的作用却很小；而有些特征项虽然只占全部特征项的 - 4 , 部分，但是对文本的分类来说却能十分有效。在样本量一定的情况下，无 论对于哪种已有分类算法，大量对分类贡献较小的特征词的存在，都将会造成 分类器的算法的时间复杂度随着特征空间维数的增加而呈迅速增长，引起“过 学习 问题，造成分类器性能下降。而且，许多在低维空间行之有效的特征选 择算法都难以适用于高维空间。 所以从上面的论述可以看到，高维稀疏性己成为文本分类中的主要瓶颈之 一。因此在分类算法的训练阶段对文本进行分类前对文本特征向量进行行之有 6 第1 章引言 效的降维操作，已成为决定文本分类效率的重要因素之一。 2 ) 维度约简的定义 维度约简【3 j 的定义是：假设 x 。) 笔cr d 是d 维空间中一个包含n 个数据的 集合，且其来自于( 或近似来自于) 维数为d ( d d ) 的某一数据流形的采样。降维的 目标即为寻求数据流形合适的低维坐标描述。从这个意义上说，降维问题由以 下四部分组成： ( 1 ) 高维数据空间qd ，它通常为r d 的某一子集； ( 2 ) 降维空f 日- j ( 或称低维表示空间) qd ，通常为的某一子集； ( 3 ) 降维映射f ：q d q d ；x - - - y - = f ( x ) ，称y 为x 的降维表示： ( 4 ) 重构映射f 一：qd q d ；y x = f d ( y ) 。 维度约简的意义并不仅仅是使缩小向量的维数，而是通过一定的方法区别 特征项的分类贡献能力，过滤那些对分类贡献不大的特征词，只保留有限个数 且对分类作用较大的特征词来组成一个更为优化的特征项集。 3 ) 特征选择主要方法 般来说，一个有效的文本特征集应该具备两个特点：完整性，即文本 特征集要能够体现或者代表文档的内容：区分性，指可将目标文档同其他文 档区分开来，即从候选文本特征集中选择既能够保持或者改善学习性能，又不 包含冗余属性的文本的特征。这是对文本特征选择的要求。 文本特征选择和文本特征抽取1 4 1 是文本分类领域常用的两种特征空间降维 方法，是文本分类的基础。 和特征抽取不同的是，特征选择不考虑特征词之间的语义关系，不改变原 始特征空间的性质，只是从原始特征空间中选择了指定数目、且能很好反映词 条与各类之间的相关程度的重要特征，组成一个新的低维空间。 文本评估函数是一种常用的特征选择方法。它通过构造一个特征评估函数， 独立地对文本特征集中的每个特征项进行评估，然后按照评估分数的大小对所 有的特征进行排序，选择预定数目得分最高的特征项组成特征子集。 。下面介绍五种较为常用的文本特征选择评估函数【5 】，它们分别是： 文档频率( d o c u m e n tf r e q u e n c yd f ) 特征项出现的频率是最简单的文本特征选择方法，它是指在训练集合中出 现该特征项的文档数，具有相对于训练语料规模的线性计算复杂度。因此该方 法能够比较容易地被用于大规模语料统计中。它的公式可以表示为： 7 第l 章引言 d f ( t ) = 出现特征t 的文档数 该方法是基于如下基本假设：权重低于某个阈值的特征项是低频词，它不 含或含有较少的类别信息。如果将这样的特征项从原始特征空间中移除，不但 能够降低特征空间的维数，而且还有可能提高分类的精度。 但是在一些信息抽取研究表明，某些d f 值低的特征项相对于d f 值高的特 征项具有较多的信息量，如果只是笼统地将它们完全移除，可能会造成分类精 度的损失。因此，该方法在实际应用中常被作为评判其它评估函数的基准。 互信息( m u t u a li n f o r m a t i o n ) 互信息是信息论中的概念，用于度量一个消息中两个信号之间的相互依赖 程度。在文本特征选择中，互信息度量的是特征项和类别的共现关系：如果特 征项对于类别的互信息越大，那么它们之间的共现概率也越大。从原始特征空 间中移除低于特定阈值的特征项，仅保留高于阈值的特征项。 互信息的计算公式为：m i ( t ，c ，) = l o g 等箬掣。其中p ( t ，e i ) y g 特征项t 出现在类 r t t ， 别c i 中的概率，p ( t ，c ) 为特征项w 在所有文档中的出现概率。该方法考虑了每个特 征项在其所属类别文档中出现的概率和它在整个文档集中出现的概率的比值，作 为它对该类的分类贡献。若特征w 与分类c i 相互独立，则m i ( t ，c i ) = 0 。 在实际应用中常使用近似计算公式：m l ( t , c i ) = l 。g 乙再i a 聂x 乙n 再面，其中 n 表示训练集中包含的总文档数，a 为t 与c i 同时出现的次数，b 为t 出现c 不出现的次数，c 为c i 出现而t 不出现的次数。 信息增益( i n f o r m a t i o ng a i n ) 信息增益方法是机器学习领域应用较为广泛的特征选择方法。它通过特征 在文本中是否出现的情况来推算该特征项所携带有的信息量。特征项的信息增 益可以用下面的公式计算为： 取f ) = - e ，讹) l o 龇) + 荆讹it ) l o g p ( c ，if ) + p ( ，) 讹it ) l o g p ( c ，it ) ， 其中p ( c i ) 表示类别c i 出现的概率，p ( t ) 表示特征项t 出现的概率，p ( c i l t ) 表示 特征项t 在属于类别c i 的文档出现的概率，p ( c ，ir ) 表示特征项在不属于类别c i 的文档出现的概率。 期望交叉熵( c r o s se n t r o p y ) 8 第1 章引言 期望交叉熵的公式为：c e ( t ) = p ( qi ，) l o g ( 裂) 。其中p ( c ，lf ) 表示文 j = i1 o f ， 档包含特征项t 时属于c i 类的条件概率，p ( c ，) 表示类文档c i 在样本集中出现的 概率。如果p ( c ，i f ) 越大，且相应的类别出现概率p ( c 。) 越小，则说明该特征项对 分类的影响大，相应的期望交叉熵越大。期望交叉熵反映了文本类别的概率分 布和在出现了某个特定词的条件下文本类别的概率分布之间的距离。特征项w 的交叉熵越大，对文本类别分布的影响也越大。和信息增益方法相比，期望交 叉熵并没有考虑特征不出现的情况。 z ：分布统计( c h i ) 假设特征项t 和文档类别c 之间满足具有一阶自由度的z 2 分布，n 表示 训练集中包含的总文档数，a 为t 与c i 同时出现的次数；b 为t 出现而c i 不出现 的次数，c 为c i 出现而t 不出现的次数，d 表示是既不属于c i 也不包含的特征项 t 的频数。n ，a ，b ，c ，d 满足n = a + b + c + d 且a d b c ：t 与c i 相互独立，那 么t 对c i 的z 2 分布值是z 2 ( ，c ) = n x ( a d b c ) 2 ( 彳+ c ) ( b + d ) ( 彳+ b ) ( ) 。 在处理多类( 设类别 数位m ) 问题时，分别计算t 对于每个类别的c h i 值，然后利用公式 磊缸= m2 ( f ，q ) 来计算特征项对整个语料的值分别进行检验。z 2 分布_ , a x z tc h i 统计方法反映了特征项t 和文档类别c 之间的相关程度：若特征项t 对某类c i 的 z 2 统计值越高，则说明它与该类的相关性越大，其重要度越大。 经过文本特征选择后，大量噪音和无用特征项被剔除，特征集规模得以减 小，为后续步骤做好准备。 1 2 3 4 几种经典的文本分类算法的介绍 文本分类算法是典型的有指导的学习过程，它常分为训练和分类两个阶段： 训练阶段： ( 1 ) 首先确定文本类别集合c = c l ，c 2 ，c k ，c m ，这些类别可以是层次 式的，也可以是并列式的； ( 2 ) 选择适量具有代表性的文本，给出训练文档集合t = t l ，t 2 ， ，t 1 1 ) ； ( 3 ) 对于t 中的每个训练文档t i ，确定其所属的类别c i ； ( 4 ) 选择训练文档t j 的特征，得到特征向量v ( s j ) ； ( 5 ) 统计t 中所有文档的特征向量v ( s j ) ，以此确定代表c 中每个类别的 9 第1 章引言 特征向量v ( g ) ； 分类阶段： 对于测试文档集合t d l ，”，d k ，d r ) 中的每个待分类的文档d k ，计算其 特征向量v ( d k ) 与每个v ( c 0 之间的相似度s i m ( d k ，c i ) 。只要d k 与这些类别之间的 相似度超过某个预定的阈值，则选取相似度最大的一个类别作为文档d k 的类别。 有时也可以为d k 指定多个类别。如果d k 与所有类别的相似度均低于阈值，那么 通常将该文档放在一边，由用户来做最终决定；对于那些根据算法判定所得类 别与预定义类别不匹配的文档而言，这是合理的，也是必须的。如果这种情况 经常发生，则说明与定义的类别不合理，需要进行修改，然后重新进行上述训 练与分类过程。 接下来对几种目前较为成熟的文本分类算法作一总结： 1 ) 朴素贝叶斯算法( n a i v eb a y e s ) 朴素贝叶斯分类算法1 6 是一种最常用的有指导意义的方法之一，它以贝叶斯 理论为基础，是种在已知先验概率与条件概率的情况下的模式识别方法。朴 素贝叶斯分类算法基于下面的假设：在给定的文本类语境下，文本的特征词对 给定类的影响独立于其它属性。 假设类别集为c ，样本及为a ，那么根据贝叶斯定理： 尸( c = ql4 = q ，4 = a k ) = ! 塾叁盂i 竺乏三等xp ( c = q ) c - ， 其中p ( c = c i ) 称为先验概率。 根据假设条件，若属性对分类的影响是独立于其他属性，则 尸( 彳i 2 a l ，a k 2 a lc 2 q ) = i - p ( a i = a i ) ( 2 ) 。 将( 2 ) 代入( 1 ) 得朴素贝叶斯分类器输出的目标值为： 肚a 诬r g ( m a x p ( c 弘锄，小) = 鬻c ( m a x 业掣筹型 c i e ca ，i a f = 口；i 它表示若未知样本属于的某一个类别的概率值具有最大值，那么该样本就属于这 个类。 2 ) k 近邻分类算法( kn e a r e s tn e i g h b o r s ) c o v e r 和h a r t 于1 9 6 8 年提出的k 近邻分类算法【7 1 是最著名的模式识别统计 学方法之一，很早就被用于文本分类研究，而且是取得分类效果较好的文本分 1 0 第1 章引言 类算法之一。 k n n 分类模型的原理如下：首先计算待分类测试样本与已知类别训练样本 之间的相似度( 常用两向量问的夹角的余弦值来衡量) ，找到相似度与待分类 样本数据最近的k 个邻居( 样本点) 。然后再根据这些邻居所属的类别来判断 待分类样本数据的类别：若待分类样本数据的k 个邻居都属于一个类别，那么 待分类样本也属于这个类别；否则，再对每一个候选类别进行评分，按照相似 度高低对类别予以加权平均，从而确定待分类样本数据所属的的类别。 士 i 己w 诗xw j k w ( c ，ix ) = s ( x ，坼) 尸( c 。lx k ) ，其中s ( x ，以) - c o s ( x ，坼) = 了等彳一 扣1 ( 以) ( 哌) yi t l k = l 表示向量x 和x k 之间的相似度；x l ，x 2 ，是训练集中和x 相似度最大的k 个文本向量；而p ( c i i x k ) 当x k 属于类别c i 时为l ，否则为0 。 由于k n n 算法不需要构建分类模型，所有有关分类的计算都是在对新样本 数据分类的时候进行，因此当数据量比较小时，k n n 算法的训练过程较快，而 且可以随时添加或更新训练文本来调整训练速度。其时间复杂度是o ( l 宰n ) 。但 是当数据集特征属性比较多、规模比较大时，k n n 算法的时间复杂度较高，分 类效果不理想。 3 ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 支持向量机理论【8 , 9 , 1 0 1 ( s u p p o r tv e c t o rm a c h i n e ss v m ) 是由v a p n i k 于19 9 5 年 首先提出一种基于结构风险最小化原则的统计学习理论，最初用于解决二分类 模式识别问题。它的解决思想是在向量空间中找到一个决策面( d e c i s i o ns u r f a c e ) ， 这个决策面能“最好 地分割两个分类中的数据点。已有实验【l l 】研究表明，s v m 和k n n 是目前两种分类效果比较好的分类算法。根据实际情况，已提出的常见 s v m 改进算法有c s v m 、v s v m 及f s v m 等。本文将在第三章对支持向量机理 论进行进一步的介绍与阐述。 4 ) 决策树( d e c i s i o nt r e e ) 决策树【1 2 】是一种常用的基于信息论理论提出的一种数据分类技术，具有易 于理解、执行数度和分类准确率比较高的特点。决策树的建立算法有多种，其 中包括：由h u n t 等【1 3 1 提出的c l s 算法；由q u i l a n 提出的基于信息增益的启发 式算法i d 3 t 1 4 1 以及同样是基于信息增益，意在解决连续属性分类的c 4 5 算法1 1 5 】； 第1 章引言 基于g i n i 系数的c a r t 算法【1 6 】；针对大样本集的可伸缩s l i q 算法【1 7 】；能够解 决了主存容量的限制，并能够处理其它任何算法都不适用的超大规模训练样本 集的可并行化s p r i n t 算法【1 8 】；b e l l 实验室的r a j e vr e s t o g i 等提出将建树和剪 枝集成到一起的p b u l i c 算法【”】等。 1 3 文本分类的研究现状 1 3 1 国外文本分类的研究现状 国外对文本自动分类研究开展得比较早，始于2 0 世纪5 0 年代。美国i b m 公司的工程师h e l u h n 在这个领域就进行了开创性的研究，首先提出了基于词 频统计思想的文本自动分类方法。在2 0 世纪9 0 年代以前，文本分类的工作主 要是由某一领域的专家和知识工程师完成，根据他们手工编写分类推理规则， 将未知文档划分到某一已知给定的类别中去。 自互联网时代诞生来，以电子文档为表现形式的信息数量急剧增加。在这 种情况下，基于机器学习的文本分类方法逐渐成为目前文本分类的主流技术。 这种方法不再需要大量的领域专家，而且随着训练文本数量的增加，机器学习 的效果也会不断提高，从而将人们从繁琐的脑力劳动中解放出来。 经过几十年的不断发展，目前国外的文本分类研究已从实验性阶段进入到 了实用化阶段，一些文本分类研究成果已被广泛应用于邮件分类、电子会议、 信息过滤等方面。其中应用比较成功的是美国麻省理工学院为白宫开发的邮件 分类系统以及c a r n e g i e 集团为路透社开发的c o n s t r u e 系统等。当前国外对文本 分类研究的研究现状【2 0 】有： 1 ) 向量空间模型( v s m ) 的研究不断完善 自上世纪6 0 年代哈佛大学的g e r a r ds a l t o n 首先提出以来，向量空间模型已 广泛应用于文本分类、信息检索等诸多领域。在较为常见的文本分类方法，如 神经网络( n e u r a ln e t ) 、k 邻近算法( k n n ) 、最大熵算法( m a x i m u me n t r o p y ) 、 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 等几乎都采用了向量空间模型。因此可以 说向量空间模型成为最简洁、行之有效的文本表示模型之一。 2 ) 语料测试库标准化 语料测试库是文本分类的基石，例如r e u t e r s 2 1 5 7 8 语料库就是常见的标准 西文测试语料库之一，它是由2 1 5 8 篇文章以及1 3 5 个类别组成。测试语料库的 1 2 第1 章引言 标准化为极大地促进了英文文本分类研究。 3 ) 对不同的文本分类算法进行了较为系统的对比研究 目前，国外一些大学已经对较为常见的文本分类算法，比如神经网络( n e u r a l n e t ) 、k 邻近算法( k n n ) 、最大熵算法( m a x i m u me n t r o p y ) 、支持向量机( s u p p o r t v e c t o rm a c h i n e ) 等都做了较为系统的对比研列1 1 】。将各种文本分类算法相结合， 取长补短，并将结合后的算法应用到文本分类当中，亦成为目前的研究方向之一。 4 ) 文本分类技术应用于特定的信息服务中 个性化服务研究逐渐成为近些年来国外众多学者的研究热点之一。通过对 用户感兴趣的文章进行分类，从而主动为用户推送个性化服务。文本分类的效 果将直接影响个性化服务的质量。 1 3 2 国内文本分类的研究现状 国内对于文本自动分类的研究起步较晚，侯汉清教授是国内这一领域的先 驱，他于1 9 8 1 年首次对计算机在文本分类工作中应用做了十分有意的探讨和阐 述工作。之后，国内许多研究机构陆续开展了文本自动分类系统的研究。其中 比较有代表性的有：上海交通大学研制的基于神经网络算法的中文自动分类系 统、清华大学的自动分类系统等。目前，已建立了较为系统的中文文本中文测 试集【2 l 】，比如，北京大学建立的人民日报语料库、清华大学建立的现代汉语语 料库等。中文文本表示的研究重点已逐渐从借鉴英文文本表示方法转向利用中 文本身的一些特征，以便更好地表示文本样本上来，从而为将目前已经比较成 熟的英文文本分类方法应用到中文文本分类方法中去成为可能；中文分词方面 已从简单的查词典的方法发展到基于统计语言模型的分词方法，这促进了中文 分词技术的发展。 、 然而，目前国内的文本分类研究还存在一些的问题1 4 亟待解决： 中文分词是影响中文文本分类的重要的因素之一，它是一项非常复杂的 工作，其速度和准确率与分类结果密切相关。随着新词汇的不断涌现，对分词 理论的创新和词典的构造都提出了新的要求。 目前还没有发现“最佳 针对中文文本分类的组织特点的分类算法，需 要结合特定的特征选择算法。在使用不同分类算法时，如何选择最佳的特征选 择方法将是一个值得深入研究的问题； 目前虽然已建立了较为系统的中文文本测试集，但尚未建立起统一的中 1 3 第1 章引言 文分类语料体系。如前所述，尽管我国一些高校已建立了一些中文文本分类语 料体系，但是这些语料库的建立缺乏统一的制定标准，而且大多数是非开放性 的，从长远看这不利于中文文本分类技术的发展。 目前存在多种成熟的文本分类算法，大部分分类系统都是应用某一种分 类算法，分类性能受到了限制，如何寻找“通用文本分类算法是摆在广大研 究者面前的一项课题。 1 3 3 文本高维问题研究现状 正如前对文本降维必要性的阐述，文本高维问题已成为文本分类技术发展 的瓶颈之一。目前已有许多学者从事文本特征向量空间降维的工作。 a n d r e a sk o n i g1 2 2 】比较了特征选择和特征抽取各自的特点，并就将两者相结 合应用于文本特征降维的潜在优势作了重点阐述。g a u r a vj a i n 等【2 3 】提出了一种 基于概念的有指导的降维方法，结合多种分类方法的分类器，并将其应用于 r e u t e r s2 1 5 7 8 文本集分类中，实验结果表明采用这种降维方法能取得较好的分 类效果。刘海峰【2 4 2 5 】利用散度差准则分别对文本特征降维问题进行了研究，其中 文献 2 4 】中提出了一种基于散度差的准则的特征降维原理和方法，并从理论上对 该方法相关步骤进行了有效性论证；文献【2 5 】讨论了一种基于散度差准则与c