（计算机应用技术专业论文）中文文本分类中特征选择方法的研究与实现.pdf

摘要 特征选择在整个中文文本分类过程中具有重要作用。国内现有的对于特征选择方法 的研究主要关注于各特征选择方法在类分布均匀语料集上的分类效果。本文针对中文文 本分类中一些特征选择方法在类分布不均匀语料集上，分类效果大幅下降的问题，在国 内现有研究的基础上，分析和研究了影响其分类效果的主要因素，并提出了改进方案。 在此基础上设计并实现了一个中文文本分类系统，为本文对中文文本分类的进一步研究 提供了平台。主要工作有： 1 ) 针对传统信息增益特征选择方法在类分布不均匀语料集上分类效果明显下降的 情况，分析并指出了影响信息增益特征选择方法分类效果的因素。结合国内现有研究， 在传统信息增益方法的基础上，去除了方法中特征词不出现情况对文本分类的贡献，同 时将集中度、分散度等因素加入到特征选择中。为了进一步提高分类效果，又将改进型 信息增益方法用于权重调整技术中。 2 ) 针对传统c h i 统计特征选择方法对低频词倚重大的缺点，深入分析了其对低频 词倚重大的原因。在传统c h i 特征选择方法的基础上，去除了方法中特征词与类别负相 关的情况。为了进一步对改进后的方法进行分析和研究，又将改进后的方法引入到特征 词权重调整技术中。与此同时，结合国内现有的关于c h i 统计特征选择方法的研究，将 集中度、分散度、频度等因素引入到改进后的方法中，提高了该方法的分类效果。 3 ) 为了实验和验证上述改进方法的分类效果，同时为进一步对中文文本分类的研 究提供平台，设计和开发了一个中文文本分类系统。 4 ) 为了进一步发现和探索中文文本分类中特征词权重调整方法中的问题和规律， 在已开发的中文文本分类系统上对不同分类器不同语料集上各权重调整方法的分类效 果进行了实验和总结。 关键词：文本分类，特征选择，权重调整，信息增益，c h i 统计 a b s t r a c t f e a t u r es e l e c t i o np l a y sa ni m p o r t a n tr o l ei nt h ec h i n e s et e x tc a t e g o r i z a t i o n d o m e s t i c e x i s t i n gf e a t u r es e l e c t i o nm e t h o d sm a i n l yf o c u so nt h er e s u l t so ft h ec l a s sd i s t r i b u t i o ne v e n l y c o r p u so ft h ef e a t u r es e l e c t i o nm e t h o d t h i st h e s i s ，i na l l u s i o nt ot h ep r o b l e mo ft h ee f f i c i e n c y d e c l i n i n gs i g n i f i c a n t l yo nt h ec l a s sd i s t r i b u t e du n e v e n l yc o r p u sf o rs o m ef e a t u r e ss e l e c t i o n m e t h o d si nc h i n e s et e x tc a t e g o r i z a t i o n ，b a s e do nd o m e s t i ce x i s t i n gr e s e a r c h ，a n a l y s e sa n d s t u d i e st h ef a c t o r sa f f e c t i n gt h ec l a s s i f i c a t i o ne f f e c ta n dt h ei m p r o v e dp r o g r a m sa r ep u t f o r w a r d o nt h i sb a s i s ，t h i st h e s i sd e s i g n e da n di m p l e m e n t e dac l a s s i f i c a t i o ns y s t e mf o r c h i n e s et e x tc a t e g o r i z a t i o n w o r k sa c h i e v e di nt h i sp a p e ra l ea sf o l l o w ： 1 ) i na l l u s i o nt ot h ed e c r e a s e de f f e c ts i t u a t i o ni nt r a d i t i o n a li n f o r m a t i o ng a i nf e a t u r e s e l e c t i o nm e t h o do nc l a s sd i s t r i b u t e dh e t e r o g e n e o u sc o r p u s ，t h i sp a p e ra n a l y s i sa n dp o i n t so u t t h ef a c t o r st h a ti m p a c tt h ec l a s s i f i c a t i o ne f f e c to fi n f o r m a t i o ng a i nf e a t u r es e l e c t i o nm e t h o d b a s e do nt h et r a d i t i o n a li n f o r m a t i o ng a i nm e t h o d ，w h i l er e m o v i n gt h ec o n t r i b u t i o n so ft h e t e r m sn o te x i t si nt h em e t h o da n da d d i n gc o n c e n t r a t i o n ，d i s p e r s i o nt ot h ef e a t u r es e l e c t i o n ，t h e t h e s i si m p r o v e st h ee f f e c t i v e n e s so ft e x tc l a s s i f i c a t i o n f o rf u r t h e ra n a l y s i sa n dr e s e a r c ho ft h e i m p r o v e dm e t h o d ，i nt u r nt h ei m p r o v e dm e t h o di si n t r o d u c e dt ot h et e r mw e i g h ta d j u s t m e n t t e c h n i q u e s 2 ) i na l l u s i o nt ot h ed i s a d v a n t a g eo ft h et r a d i t i o n a lc h i - s q u a r es t a t i s t i cf e a t u r es e l e c t i o n m e t h o d r e l y i n gh e a v i l y o nl o w - f r e q u e n c yw o r d s ，t h i sp a p e ra n a l y s i st h er e a s o n so ft h a t b a s e d o nt r a d i t i o n a lf e a t u r es e l e c t i o nm e t h o d ，t h i st h e s i sr e m o v e st h en e g a t i v ec o r r e l a t i o ns i t u a t i o n b e t w e e nt e r m sa n dc a t e g o r i e s f o rf u r t h e ra n a l y s i sa n dr e s e a r c ho ft h ei m p r o v e dm e t h o d ，i n t u r nt h ei m p r o v e dm e t h o di si n t r o d u c e dt ot h et e r mw e i g h ta d j u s t m e n tt e c h n i q u e s a tt h e s a m et i m e ，c o m b i n i n ge x i s t i n gd o m e s t i cc h i - s q u a r es t a t i s t i cf e a t u r es e l e c t i o nm e t h o d s ， i n t r o d u c i n gt h ec o n c e n t r a t i o n ，d i s p e r s i o n ，f r e q u e n c yi n t ot h ei m p r o v e dm e t h o d ，t h i sp a p e r i m p r o v e st h ec l a s s i f i c a t i o np e r f o r m a n c eo f t h em e t h o d 3 ) i no r d e rt ot e s ta n dv a l i d a t et h ep e r f o r m a n c eo ft h ei m p r o v e dc l a s s i f i c a t i o nm e t h o d s a n dp r o v i d eap l a t f o r mf o rf u r t h e rr e s e a r c ho nc h i n e s et e x tc l a s s i f i c a t i o n ，t h i st h e s i sd e s i g n e d a n dd e v e l o p e dac h i n e s et e x tc l a s s i f i c a t i o ns y s t e m 4 ) t of u r t h e ri d e n t i f ya n de x p l o r et h ep r o b l e m sa n dl a w so ff e a t u r ew o r d sw e i g h t a d j u s t m e n ti nc 1 1 i n 器et e x tc l a s s i f i c a t i o nm e t h o d , t h i st h e s i sm a d ee x p e r i m e n ta n dc o n c l u s i o n o nt h ec l a s s i f i c a t i o nr e s u l t so fw e i g h ta d j u s t m e n tm e t h o d 、析t l ld i f f e r e n tc l a s s i f i e r sa n dc o r p u s i nt h ed e v e l o p e dc h i n e s et e x tc l a s s i f i c a t i o ns y s t e m s k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，f e a t u r es e l e c t i o n ，w e i g h ta d j u s t m e n t ，i n f o r m a t i o ng a i n ， c h i s q u a r es t a t i s t i c 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人 允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。同时授权中国科学技术信息研究所等机构 将本学位论文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。、 学位论文作者签名：羧奠荡 指导教师签名：亩l 彦鏊与陵 7 0l o 年6 月冲日 2 卯c j 年6 月以局 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 本论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西 北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 装蜊 仍p 年6 月钟日 西北大学硕士学位论文 1 1 研究背景和意义 第一章绪论 近年来文本分类作为数字化图书馆、信息检索、信息过滤等领域的技术基础，受到 了国内外研究者的广泛关注【1 ，2 捌。自动文本分类不仅能够提高数字化图书馆在组织和管 理上的效率，而且在提高信息检索系统的性能以及信息过滤系统的过滤效能上也起着极 其重要的作用。 自动文本分类的困难来自于很多方面：一方面，选择一种适当的数据结构来表征文 本；另一方面，必须对高维的特征空间进行降维处理，以提高系统的运行效率。同时还 需要选择适当的算法进行分类，以获得更好的分类效果【4 】。国内外对于文本分类的研究， 也主要集中上述三个方面。 特征选择方法在文本分类中得到了广泛的应用，其主要用于高维特征空间的降维处 理。采用向量空间模型表示文本时，首先要对语料集中的文本进行分词、去停用词，然 后用文本预处理后的结果组成文本向量来表征文本。如果直接使用文本预处理后的初始 特征集，其中的特征词有可能是成千上万的，势必造成特征空间的维数过大，影响文本 分类的效率；并且并不是初始特征集中所有的特征词对于分类都是有用的，有的甚至会 影响分类的效果。特征选择是根据一定的规则从高维的特征空间中选取一部分对分类贡 献大的特征词作为特征子集用于之后的分类过程，从而提高了文本分类系统的时间效率 和空间效率。特征选择结果的好坏直接影响着文本分类系统的分类效果。 目前从国外文本分类技术发展来看，国内对于中文文本分类的研究还相对滞后。由 于国内对于中文文本分类的研究起步较晚，在文本分类及其相关技术的研究上与国外相 比还存在着定的差距。传统的文本分类技术，如一些传统的特征选择方法，也存在着 一些不足或者不完善的地方，需要我们进行进一步的研究与改进。因此开发一个中文文 本分类系统，并在此基础上对文本分类中一些传统的方法进行实验分析和改进，对中文 文本分类相关技术中的问题和规律进行探索和研究是很有必要和有意义的。 1 2 研究现状 国外对于文本分类的研究较早。2 0 世纪5 0 年代末，l u h n 首先将词频统计的思想应 用于文本分类中，对这一领域进行了开创性的研究5 1 。近年来，国外对于文本分类技术的 第一章绪论 研究取得了很大的进展，提出了多种特征空间降维处理方法和分类方法，同时还建立了 o h s u m e d 、r e u t e r s 等开放的分类语料库。 在权重调整技术方面，文献【6 】认为表征文档的特征词，应根据其所在句子的重要性 区分对待。对于重要句子( 如：和标题相近的句子等) 中的特征词，应赋予较高的权重。 在降维处理方法研究方面，文献【7 】分析了在不均衡语料库上各个特征选择方法的分 类效果，提出了优化的结合正相关特征词和负相关特征词的特征选择方法，其在不均衡 语料库上的分类效果要优于其它特征选择方法。文献 8 提出了一种新的特征选择方法 c m i m ，其可以选择出一套有独立鉴别能力、相互弱相关的特征词，并且将该方法应用 于文本分类中，提高了文本分类系统的分类效果。 在特征词权重调整方面，文献 9 】对传统的t f i d f 方法进行了分析和改进，将文本 分类中的一些特征选择方法与t f 相结合，用于特征词的权重调整。 在分类算法研究方面，文献 1 0 1 将基于p t r e e s 的数据结构引入到k n n 的分类算法 中，大大提高了k n n 分类器的分类的时间效率和空间效率。文献 1 1 】为了提高s v m 分 类器的性能，使用a m 特征选择方法，从而使s v m 分类器的训练时间减少了5 0 多。 文献1 1 2 对现有的几种分类算法进行了分析和比较，对于我们进行文本分类的研究具有 指导性的意义。 文献 1 3 】还对文本分类中常用的三种阈值技术进行了分析和改进。 相对于国外，国内对于文本分类的研究起步较晚。研究中主要采用基于向量空间模 型的文档相似性比较，使用的文档特征主要为词或n g r m a 。 在中文文本分类中的特征词权重调整技术上，文献【1 4 】和文献 1 5 1 对于文本分类中 特征词权重调整技术进行了研究和改进，提高了文本分类的效果。 在分类模型的研究方面，文献 1 6 】将概念推理网的概念引入到文本分类中，提出了 新的分类模型，并通过实验证明该方法具有较高的分类精度。 在分类算法研究方面，文献 1 7 】对类中心向量分类方法进行了改进，提出了一种快 速的类中心向量分类方法，提高了分类的准确率和召回率。在k n n 分类算法中，分类 效果与k 值的选取有直接关系。文献【1 8 】对传统的k n n 分类算法进行了改进，克服了 分类效果对k 值的依赖。文献 1 9 】以改进的互信息公式来选择特征，以朴素贝叶斯分类器 进行分类，对分类方法进行了改进，提出了一种高性能的两类中文文本分类方法。文献 【2 0 提出了一种利用权重调整思想对向量空间法和朴素b a y e s 分类器进行改进的文本分 类方法，并探讨了利用e m 算法进行无导师b a y e s 分类的方法。 2 西北大学硕士学位论文 由于文本分类中训练集样本分布不均匀的情况，会导致文本分类的准确率下降。文 献 2 1 1 针对此问题进行了研究，提出了针对k n n 方法的训练集样本裁剪方法。文献1 2 2 】 对基于机器学习的文本分类的研究和发展进行了综述和评论，并对研究方向进行了展 望，对国内中文文本分类的研究具有一定的指导意义。 1 3 研究内容 本文在国内对中文文本分类研究的基础上，主要针对中文文本分类中特征选择方法 及其相关技术进行了分析和研究。在对传统的信息增益特征选择方法和c h i 统计特征选 择方法进行分析和改进的基础上，设计并实现了中文文本分类系统。 本文的主要研究工作包括以下几个方面： 1 ) 训练集文本在各个类别中分布的均匀程度，对文本分类的效果是有影响的。在 类分布不均匀的语料集上，各分类器的分类效果明显下降。本文从理论上对传统的一些 特征选择方法，如信息增益和c h i 统计，进行了深入地分析和研究，指出了在类分布不 均匀语料集上影响其分类效果的主要因素。 2 ) 在理论分析的基础上，本文设计并实现了一个中文文本分类系统。该系统是本 文中所有实验和分析的基础。该系统主要包括分类器的构造、分类器分类和结果评测功 能。其中的主要模块有： 文本预处理：分词采用中科院计算所汉语语法分析系统i c t c l a s 对中文语料集中 的文档进行分词，该系统分词精度达到9 8 4 5 。在分词后进行去停用词处理。 特征选择：实现了信息增益、互信息、期望交叉熵、c h i 统计、文本证据权、改进 型信息增益、改进型c h i 统计这七种特征选择方法。 权重调整：实现了中文文本分类中常用的几种权重调整方法，如：t f i d f 、t f * 特 征选择方法值和t f i d f * 特征选择方法值。 分类器构造：实现了k n n 分类器和s v m 分类器两种分类器。 分类器分类：能够使用构造好的两种分类器对测试集中的文本进行分类。 结果评测：对中文文本分类中各种方法的分类结果进行统计和评测。 3 ) 在上述的中文文本分类系统上，首先对传统的信息增益和c h i 统计特征选择方 法在类分布均匀语料集和类分布不均匀语料集上的分类效果进行了实验。分析了影响其 各自分类效果的因素，对信息增益特征选择方法和c h i 统计特征选择方法进行了初步改 进，并通过实验验证了该方法的有效性和可行性。同时结合国内现有研究，在改进后方 3 第一章绪论 法中引入集中度、分散度等因素，提高了其在类分布不均匀语料集上的分类效果。为了 进一步提高改进后方法的分类效果，又将改进后方法引入到特征词权重调整技术中，提 高了文本分类系统的分类效果。 4 ) 在上述的中文文本分类系统上对常用特征词权重调整方法进行了实验与分析。 常用的特征词权重调整方法有t f i d f 、t f * 特征选择方法值和t f i d f * 特征选择方法值。 其中t f i d f 在文本分类中得到了广泛的应用，但其也存在不足之处。t f 搴特征选择方法 值和t f i d f * 特征选择方法值是基于熵概念的权重调整方法。本文分别在k n n 分类器和 s v m 分类器上，对不同语料集上各种特征词权重调整方法的分类效果进行了实验。主 要目的在于分析各分类器上哪种权重调整方法的分类效果最好，对实验中的问题和规律 进行探索和总结。 1 4 论文组织 第一章介绍文本分类的研究背景及研究意义，分析国内外文本分类的研究现状和研 究重点，并介绍本文主要的研究工作。 第二章介绍文本分类的相关技术，对文本分类每一个环节中用到的方法和技术进行 描述和总结，为后续章节的讨论作概念和技术上的准备。 第三章讨论对信息增益特征选择方法的改进。首先分析传统信息增益特征选择方法 存在的问题，然后结合现有技术对其进行改进，提高了分类器的分类效果。 第四章讨论对c h i 统计特征选择方法的改进。首先分析传统c h i 统计特征选择方 法对低频词的倚重大的问题，然后结合国内现有的对c h i 统计特征选择方法的研究，对 其进行改进，提高了分类器的分类效果。 第五章介绍文本分类系统的设计和实现，并在此基础上对文本分类中常用的几种特 征词权重调整方法进行了分析和实验。 第六章是总结与展望。主要是对论文的工作做全面而细致的总结，并进一步指出本 文中存在的不足之处和将来要改进的方向。 4 西北大学硕士学位论文 第二章文本分类的相关技术 文本分类在信息检索、信息过滤等领域得到了广泛地应用。中文文本分类的过程一 般包括：中文分词、去停用词、降维处理、文本表示、分类器构造、分类器分类、分类 性能评估。因为中文文本分类的各个阶段对中文文本分类系统的分类效果都有着重要影 响，因此对于中文文本分类过程中任意一个阶段的方法或算法进行研究和改进，都能够 提高中文文本分类系统的分类性能。 2 1 文本分类过程 文本分类是在给定分类体系的情况下，根据文本的内容或属性将其分到一个或多个 预定义类别的过程。国内对于中文文本分类的研究主要是基于向量空间模型。向量空间 模型中，一篇文档被表示为特征空间中的一个向量，这个向量也称为文档向量。文档向 量中每一维对应于文档中的一个特征。 对于中文文本分类，其处理过程主要包括训练阶段和测试阶段。 在训练阶段，首先对中文训练集中的每一个文档进行分词，也就是将每一个文档分 割成该文档所包含的单词。在经过分词后所形成的特征词集合中，有很多词对于文本分 类的作用不大甚至还会影响分类效果，例如常用的一些虚词等，对于这些词我们就需要 去除，这就是去停用词阶段。虽然去除了停用词，但对文档进行向量表示时，特征空间 的维数很大，大大影响了分类的时间效率和空间效率。因此就需要在向量表示前对特征 空间进行降维处理，从原有的特征空间中，挑选出对文本分类最重要或者影响最大的一 些特征词。在降维处理后，为了区分不同特征词对分类的不同作用，还需要对特征词进 行权重调整，然后进行文档的向量表示。最后用训练集中的文档向量进行分类器的构造。 具体流程如图2 1 所示。 _ i 初始特征集l l 中文分词 l 训练集文本 l 降维处理 叫分类器构造i ， 去停用词 i 、， 文本向量化 图2 - 1 文本分类的训练过程 5 第二章文本分类的相关技术 在测试阶段，我们同样需要对测试集中的文档进行中文分词和去停用词。然后用训 练时生成的特征子集对测试集文档进行向量表示，最后用已构造的分类器进行分类。具 体流程如图2 - 2 所示。 i l 中文分词 测试集文本 l- - q 文本向量化h 分类器分类 ， 去停用词 2 2 语料集 图2 - 2 文本分类的测试过程 语料集一般分为训练集和测试集两个部分。训练集文本用于分类器的构造过程，测 试集文本用于分类器的分类过程及分类效果的评价。国外对于文本分类的研究较早，并 且已经建立了多个开放的语料集，如r e u t e r s 2 1 5 7 8 和o h s u m e d 等。采用统一的语料 集就能方便地、客观地对不同方法、不同系统的分类性能进行比较和评价。 对于中文文本分类，国内目前还没有建立标准的、开放的分类语料集。一般都是研 究者自己搜集和整理语料集，进行训练和测试。因此不同方法和不同系统之间分类性能 的可比性较差。这一问题己经引起国内文本处理界的重视，并已经为这方面做着努力。 本文实验中采用了复旦大学计算机信息与技术系国际数据库中心自然语言处理小 组整理的训练和测试语料集。本文分别使用类分布均匀语料集和类分布不均匀语料集进 行实验。 a 语料集为类分布均匀的语料集，在上述语料集的计算机、艺术、经济、政治、体 育、环境六类中随机选取训练集2 0 5 2 篇文档和测试集7 0 2 篇文档。其中各类文档的选 取情况如表2 1 所示。 表2 - 1a 语料集上训练集和测试集的选取情况 计算机艺术经济政治体育环境 训练集 3 3 0 3 3 7 3 4 63 5 2 3 4 43 4 3 测试集 1 1 71 1 71 1 71 1 71 1 71 1 7 b 语料集为类分布不均匀的语料集，在上述语料集的计算机、艺术、经济、政治、 体育、环境六类中随机选取训练集2 1 1 0 篇文档和测试集6 4 6 篇文档。其中各类文档的 6 西北大学硕士学位论文 选取情况如表2 - 2 所示。 表2 - 2b 语料集上训练集和测试集的选取情况 计算机 艺术 经济 政治 体育环境 训练集 1 1 71 0 01 6 0 01 1 71 1 75 9 测试集 1 1 71 1 71 1 71 1 71 1 76 1 2 3 中文分词 从句子中划分出每个有独立意义的词被称为分词【2 3 1 。中文分词技术属于自然语言处 理的范畴，是信息过滤、信息检索等领域的重要基础。 在西方语言中，词与词之间有空格分隔，从语义的准确度和技术的复杂性上来讲都 比较简单。而对于中文文本，由于中文的词与词之间的分界比较模糊，因此要进行分词 就比较困难。中文是一种比较复杂的语言，让计算机理解中文文本是十分困难的。歧义 识别和新词发现一直以来是中文分词的两大难点。 目前对于中文分词，常用的分词方法有：正向最大匹配算法、逆向最大匹配算法、 双向最大匹配算法、最佳匹配法、设立切分标志法等。 本文采用中科院计算所汉语语法分析系统i c t c l a s 对中文语料集中的文档进行分 词，该系统分词精度达到9 8 4 5 。 2 4 去停用词 对于中文文档进行分词后，并不是所有的词对于文本分类都是有用的。一些词，如 “这，那，得，的，地”等，几乎在所有的文档中都出现，但其对于文本分类几乎没有什 么作用。如果将这些词也作为文档的特征词，势必对分类的结果造成影响。因此我们需 要去除那些在语料集文档中频繁出现，而对文本分类效果没有太大作用的词，这个过程 就是去停用词。 无论是在中文文档还是英文文档中，都存在着很多的停用词。对于文档中的停用词， 一般通过构造停用词表的方法去除。国外对于英文停用词的研究相对比较成熟，已经有 了一些比较著名的英文停用词表，如：b r o w nc o r p u s 停用词表以及v a i lr i f s b c r g e n 发表 的停用词表。国外的很多学者在现有停用词表的基础上，研究新的更合理的方法，试图 寻找更好地建立停用词表的方法或者去除停用词的方法 2 4 , 2 5 , 2 6 。 对于中文停用词的研究相对较少，目前还没有一个比较权威的停用词表。国内的研 究者一般都是自己手工建立或者采取基于统计的停用词选择方法建立自己的停用词表。 7 第二章文本分类的相关技术 文献【2 7 和【2 8 】对中文停用词表的建立进行了分析和研究，提出了高效的停用词表的选 取方法。 2 5 降维处理 在中文文本分类中，对语料集中的文本进行分词、去停用词后，所形成的特征词集 合，称之为初始特征集。在初始特征集中，特征词的个数可能是成千上万的。也就是说 经过分词，去停用词后所形成的特征空间的维数是非常大的。高维的特征空间给文本分 类的效率带来了很大的影响。如何降低特征空间的维数，提高中文文本分类的时间效率 和空间效率，也就成为文本分类中的关键问题，这也正是降维处理所要解决的问题2 9 1 。 在中文文本分类中降维处理的方法一般有两种：特征选择和特征抽取。 2 5 1 特征选择 特征选择在文本分类中得到了广泛地应用，其主要用于高维特征空间的降维处理。 在采用向量空间模型来表示文本时，首先要对语料集中的文本进行分词、去停用词，用 文本预处理后的结果组成一个文本向量来表征文本。如果直接使用分词、去停用词后的 初始特征集，由于特征空间的维数过大，势必影响中文文本分类的效率；而且并不是初 始特征集中所有的特征词对于分类都是有用的，有的甚至会影响分类的结果。特征选择 是根据一定的规则或方法从高维的特征空间中选取一部分对分类贡献大的特征词作为 特征子集用于之后的分类过程，从而提高了文本分类系统的时间效率和空间效率。特征 选择结果的好坏直接影响着中文文本分类系统的分类效果。常用的特征选择方法有：信 息增益、互信息、期望交叉熵、c h i 统计、文本证据权等。下面详细介绍本文中用到的 几种特征选择方法。 信息增益( i n f o r m a t i o no a i n ) ：表示了某一个特征词的存在与否对类别预测的影响， 一般定义为特征词在文档中出现前后的信息熵之差。其公式表示如下所示： 刖= 扣q ，w ) 1 。g 揣 ( c j ，砷g 老高) 汜d 其中p ( q ，们表示类别q 和特征词w 的联合概率，p ( 叻是特征词w 在文本中出现的 概率，p ( q ) 是c ：类文本在文本集中出现的概率，p ( q ，叻表示类别q 和不包含特征词w 的联合概率，尸( 叻表示文本中不包含特征词w 的概率，i c i 为类别总数【2 】。 8 西北大学硕士学位论文 互信息( m u t u a li n f o r m a t i o n ) ：根据单词的出现情况来衡量一个单词对某一个类的重 要程度，其在统计语言模型中被广泛采用。其公式表示如下所示： = 兰i = 1 9 x ( w ) 删。g 谢 ( 2 2 ) = 艺尸( c f ) l o g 号掣 ( 2 。2 工w ， 其中e ( w lc , ) 为词条w 在类q 中出现的条件概率，尸( q ) 和尸( w ) 的定义同上【2 1 。 期望交叉熵( e x p e c t e dc r o s se n t r o p y ) ：也称k l 距离。具体公式表示如下： = 抵i = l 讹揣 他3 ， 其中p ( q ，w ) ，p ( q ) ，p ( 计的定义同上。期望交叉熵反映了文本类别的概率和在出 现了某个特定词的条件下文本类别的概率分布之间的距离，词条w 的期望交叉熵越大， 对文本主题类分布的影响也越大【2 1 。 c h i 统计( c h i s q u a r es t a t i s t i c ) ：假设特征词w 与类别c 之间的非独立关系类似于具 有一维自由度的z 2 分布，w 对于c 的c h i 统计量可计算为： 触c ) 2 丽筹器丽 眨4 ) 其中a 表示属于类别c 的文档中包含特征词w 的文档频数，b 表示不属于类别c 的 文档中包含特征词w 的文档频数，c 表示属于类别c 的文档中不包含特征词w 的文档频 数，d 表示既不属于类别c 也不包含特征词w 的文档频数，n 表示语料中的文档总数3 1 。 文本证据权( w e i g h to fe v i d e n c eo ft e x t ) ：它衡量类的概率和给定特征时类的条件 概率之间的差别。具体公式表示如下： 唧们- p ( 聊善t c l 酬b g 器篙篇l 汜5 ) 其中p ( q ) 的定义同上，p ( qlw ) 表示文本包含词条w 时属于q 类的条件概率3 1 。 2 5 2 特征抽取 特征抽取则是根据一定的方法，从原始的初始特征集中抽取出一部分新特征词，用 于文本分类的其它过程。在中文文本分类中，经过文本预处理后所形成的初始特征集中 有很多近义词或同义词的存在，如“光阴”、“岁月”和“时光”为近义词，“北京大学”和“北 大”，“周树人”和“鲁迅”为同义词。这些同义词或近义词在文本分类中所起的作用基本相 9 第二章文本分类的相关技术 同，如果将其都作为特征集中的特征项，势必造成特征空间的冗余，对文本分类系统的 分类效果是有很大影响的。如何对这些语义相关性较强的特征词进行重构，提高文本分 类的效率，这就是特征抽取所要解决的问题。 特征选择和特征抽取方法在很多热点领域都得到了广泛地关注。相对来说，特征选 择在文本分类、信息检索等领域使用的多一些，而特征抽取在人脸识别、手写体字符识 别等领域使用的多一些【3 0 , 3 1 】。 2 6 文本表示 文本表示是文档分析和处理中的关键问题3 2 1 。文本表示也是文本分类、信息过滤、 信息检索、知识发现等领域的基础3 3 , 3 4 , 3 5 。对于中文语料集中的文本，计算机不能够直 接进行处理，因此在进行中文文本分类之前，必须要对中文语料集中的文本进行一些处 理。采取合理的方式将中文文本转化成计算机能够处理的形式，这个过程就是文本表示。 文本表示的方法一般包括：布尔模型、概率模型和向量空间模型等。以下详细介绍本文 在中文文本分类中采用的向量空间模型。 1 ) 向量空间模型 向量空间模型是由g e r a r ds a l t o n 等人在2 0 世纪6 0 年代提出的【3 6 1 ，其在文本分类、 信息检索等领域都得到了广泛的应厍j 3 7 , 3 8 , 3 9 。 在向量空间模型中，语料集中的每一篇文本被形式化为多维空间中的一个点，并以 向量的形式来描述【1 4 1 。语料集文本中的特征词，可以是文本中的句子、词、词组等，对 应于向量空间中的一个维度。文本的集合对应于分布在空间中的一组点集。特征词可以 通过其在文本中的重要程度来赋予一定的权重。特征词的权重，对应于空间中点的坐标 值。 对于文档d t ，t j ( j = 1 ，2 ，力) 为文档喀中互不相同的特征词，特征词f ，在文本d i 中的 权重记为，文本喀则可表示为3 q ： v ( d i ) 2 ( w p w 2 ，w 一) ( 2 6 ) 2 ) 特征词的权重计算 特征词的权重可以通过其在文档中的重要程度来表示。文档中对分类有着不同作用 的特征词，我们应区别对待。在个文档中，对表征文本内容贡献程度大和区分不同文 本能力强的特征词，我们应赋予较高的权重。对于分类效果作用不大或者无作用的特征 1 0 西北大学硕士学位论文 词，我们应赋予较低的权重，以减少其对文本分类效果的影响。最常用的特征加权方法 是t f i d f 方法。 t f i d f 方法是通过特征词的词频( t f ) 和反文档频率o d d 来计算特征词的权重。 对于文档或中的特征词0 其权重计算公式如下所示【1 4 】： t f i d f ( d ，t j ) = 豫( 奶) 肼( 砒) = 弘( 奶) 1 0 9 ( 热) ( 2 7 ) 其中，t f ( d i ，t ) 表示特征词0 在当前文本哆中出现的频率，l d i 是文本总数，d f ( t ) 是在所有文本中特征词。出现的频率，2 ：卯( 嘭，勺) 是反文档频率，即l 。g ( 面黔) 。 常用的特征词权重调整方法除了t f i d f 外，国内的一些学者将特征选择中的评估函 数与t f i d f 相结合，提出了新的特征词权重计算方法( 如：t f * 特征选择方法值、t f i d f * 特征选择方法值) ，提高了分类效果【1 4 1 5 1 。 3 ) 相似度计算 文本的相似度是指两个文本之间内容的相关联程度，也就是内容的相似或相近的程 度。在中文文本分类中，往往要对文本之间的相似度进行计算。如：在基于k n n 分类 算法的系统中，要将待分类文档与训练集中的文档进行相似度计算，找出k 个与待分类 文档最相似的文档，从而对其类别做出判断。在基于类中心向量分类算法的系统中，要 将待测文本与各个类的类中心向量进行相似度计算，从而将文档归入与其最相似的那个 类别中。 对于相似度计算，我们可以借助文本向量之间的某种距离来表示文本之间的相似 度。常用的度量方法有【1 2 】： 欧氏距离： r 一 d i s ( d i ，q ) = ( 吆一) 2 y 扣1 ( 2 8 ) 坛指特征词气在文档呸中的权重，n 是特征词总数。 夹角余弦值：文本的相似度可以用文本向量之间的夹角余弦来表示。其计算公式见 公式( 2 4 ) 。 第二章文本分类的相关技术 a m ( d , ，q ) = 露 ( ) k = l 指特征词气在文档d l 中的权重，n 是特征词总数。 2 7 常用分类算法 ( 2 9 ) 文本分类的方法基本上可以分为三大类。一种是基于统计的方法，如n a i v eb a y e s 、 k n n 、类中心向量、回归模型、支持向量机( s v m ) 、最大熵模型等方法；另一种是基 于连接的方法，如人工神经网络；还有一种是基于规则的方法，如决策树、关联规则等， 这些方法的主要区别在于规则获取方法。国内对于文本分类的研究主要集中在基于统计 的方法，其中k n n 、s v l v i 方法的分类正确率较高。下面就常用几种分类算法作简单介 绍。 2 7 1n a i v eb a y e s 算法 朴素贝叶斯( n a i v eb a y e s ) 分类器在机器学习领域得到了广泛地应用和研究。贝叶 斯分类器的基本思想是利用特征词和类别之间的联合概率来评估和判定一个文档属于 某个类别的概率。贝叶斯分类器假定各个特征词之间都是独立的，也就是说给定类别中 一个特征词的条件概率与这个类别中其它特征词的条件概率之间是相互独立的。由于贝 叶斯分类器不使用特征词的组合进行预测，因此其有着很高计算效率。 n a i v eb a y e s 分类算法的基本思想是：假设d l 为一任意文档，它属于文档类 c = c l ，c z ，c k ) 中的某一类c ，。根据n a i v eb a y e s 分类算法，要对文档喀进行分类，首 先通过公式( 2 5 ) ，计算出文档d i 的概率，然后通过公式( 2 6 ) 计算出文档儡出现的情况下， 其属于各个类别的条件概率，最后将文档谚归属到概率值最大的类别中【1 2 】。 k p ( z ) = p ( c j ) p ( a , j d ，、p ( c j ) e ( a , l c j ) 尸( oi 喀) = 铲 ( 2 1 0 ) ( 2 1 1 ) 根据p ( 吐ic j ) 计算方式的不同，可以将n a i v eb a y e s 方法分为泊松模型、多项式模 1 2 西北大学硕士学位论文 型、最大似然模型等。 2 7 2s v m 算法 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是一种相对较新的机器学习方 法，它是为了解决两类模式识别问题，由v a p n i k 于1 9 9 5 年提出的。该方法是基于结构 风险最小化原理，其定义了一个向量空间，问题的关键是寻求一个可以将数据点成功的 分为两类的最优决策面。为了定义最优分类，在此需要引入类间隔的概念。图2 3 和图 2 - 4 说明了这一点。为了简单起见，我们只显示了二维空间上线性可分的数据点，但是 这种方法可以被扩展到高维的空间上线性不可分的数据点。在一个线性可分的空间上的 决策面是一个超平面。图2 3 和图2 4 中的实线显示了两种可能的决策平面，每一个决 策平面都能将数据正确的分为两组。与实线相平行的虚线显示了有多少个平面能成功分 类。这些虚线之间的距离被称为分类间隔，s v m 所要寻找的最优决策平面，可以使得 训练集上数据点之间的分类间隔最大。 - - 图2 - 3 非最优决策线 o o 箸髫善( 1 b o 图2 - 4 最优决策线 图2 - 4 中虚线上的数据点也叫做支持向量。 我们用d = ( 乃，再) ) 表示i j i l 练集文档，其中y t + 1 ) 。如果文档；属于正例，其y 值 为+ l ，如果文档；属于反例，其y 值为1 。s v m 算法所要寻找的就是这样的向量一w 和b ， 其能满足如下公式： w 。五一b + 1当yl=+1(212) 1 3 。?、 第二章文本分类的相关技术 w 五一b - 1当所= 一l( 2 1 3 ) 其分类间隔等于2 i j 叫i ，使间隔最大等价于使0 卅l 最小。满足上述公式且使知叫1 2 最 小的分类面就叫做最优分类面【1 2 】。 支持向量机算法一般是针对二类分类问题的。为了使其能适应多类别的分类问题， 我们把每一个类别的分类问题看成一个独立的二类分类问题，也就是对于训练集中文 档，我们将其看为两类，即属于该类别的文档和不属于该类别的文档。因此，用支持向 量机算法对含有多个类别的语料集进行分类时，就需要构造多个分