（计算机应用技术专业论文）中文文本分类系统的研究与实现.pdf

中文摘要 随着信息技术的发展，文本资料的数量呈几何级增长，如何在众多的资料中 快速准确的找到人们需要的信息，成为当前信息处理领域一个委待解决的闯题。 基于人工智能的文本分类技术能够根据文本的语义内容，自动将文本划分到预定 义的类别体系中，从而一定程度上解决了上述难题。 本文对中文文本分类的关键技术进行了研究和探讨，如中文分词、特征项选 择、特征项权重计算及常用的文本分类算法等。在特征选择方面，本文分析了互 信息、信息增益、c h i 统计等常用的特征选择方法，指出由于这些方法的侧重点 不同，有可能导致同一特征项在不同的特征选择方法中重要性程度相差很大。为 了削弱单个特征选择方法的缺陷，本文使用多个特征选择方法的组合来进行特征 项的选择，并实现了类中心分类法来验证不同的特征选择方法组合对分类精度的 影响，实验结果表明，两种特征选择方法的组合( t w o c o m b i n e ) 较单个特征选 择方法( o n e - m e t h o d ) 和多个特征选择方法的组合( m o r e c o m b i n e ) 性能最佳。 通过对性能较好的组合特征选择方法的分析可以发现，它们均是基于c h i ( z 2 ) 统计的。传统的权重算法，如t f i d f ( t e r mf r e q u e n c ya n di n v e r s ed o c i a r n e n t f r e q u e n c y ) 、基于熵概念的粳重等都是在全部文档集合的焦度考虑特征项的重要 性，不能体现特征项在不同类别中的重要程度差异。针对这一问题，本文提出使 用反映特征项与类别相关程度的互信息来修正t f i d f 的改进权重算法，并实现 了类中心狙k n n ( k n e a r e s tn e i g h b o r s ) 两种分类算法验证改进权重算法的优越 性，实验结果表明改进的权重算法在两种分类方法上都不同程度的提高了分类的 精度。 关键词：文本分类；中文分词；特征项权重；特征选择 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h ea m o u n to ft e x t si n c r e a s e s e x p l o s i v e l y h o wt of i n dt h er e q u i r e di n f o r m a t i o nf r o mm a s s i v ei n f o r m a t i o nq u i c k l y a n dc o r r e c t l y , b e c o m ea l li m p o r t a n tp r o b l e mi nt h ei n f o r m a t i o np r o c e s s i n gf i e l d t e x t c l a s s i f i c a t i o n ，t h ea u t o m a t e da s s i g n i n go fn a t u r a ll a n g u a g et e x t s t o p r e d e f i n e d c a t e g o r i e sb a s e do nt h e i rc o n t e n t s ，i sap a t ht os o l v i n gt h ep r o b l e ma b o v e n ek e yt e c h n i q u eo fc h i n e s et e x tc l a s s i f i c a t i o n ，i n c l u d i n gc h i n e s es e g m e n t a t i o n ， f e a t u r es e l e c t i o n ，f e a t u r ew e i g h ta n dc l a s s i f i c a t i o nm e t h o d si sd i s c u s s e d t h ew i d e l y u s e df e a t u r es e l e c t i o nm e t h o d s ，s u c ha sm u t u a li n f o r m a t i o n ，i n f o r m a t i o n g a i n ， c h i s t a t i s t i ca n ds oo n ，a r eb a s e do nd i f f e r e n tr u l e s ，t h e ym a ys c o r et h es a m ef e a t u r e v e r yd i f f e r e n t l y i no r d e rt oo v e r c o m em es h o r t a g eo fs i n g l em e t h o d ，t h i sp a p e r c o n s i d e r st h ec o m b i n a t i o n so ft w oo rm o r ef e a t u r es e l e c t i o nm e t h o d s e x p e r i m e n t r e s u l t ss h o wt h a tt h ec o m b i n a t i o no ft w om e t h o d si sb e t t e rt h a nt h a to fs i n g l em e t h o d a n dt h ec o m b i n a t i o no ft h r e eo rm o r em e t h o d s a l s o ，t h ec o m b i n a t i o no ff e a t u r e s e l e c t i o nm e t h o d s w h i c hp e r f o r mw e l la r ea l lb a s e do nc h i s t a t i s t i c 1 1 1 et r a d i t i o n a l f e a t u r ew e i g h tm e t h o d s ( s u c ha st f i d f , t h ew e i g h tb a s e do ne n t r o p y ) j u s tc o n s i d e r t h ei m p o r t a n c eo ff e a t u r e so nt h ew h o l et e x tc o l l e c t i o n t h e yc a nn o tr e f l e c tt h e i m p o r t a n c ed i f f e r e n c e so fo n ef e a t u r ei nd i f f e r e n tt e x tc a t e g o r i e s a g a i n s tt h i sp r o b l e m ， t h i sp a p e rp r e s e n t sa l li m p r o v e dm e t h o d ，w h i c hu s e st h em u t u a li n f o r m a t i o nt or e f l e c t t h ec o r r e l a t i o nb e t w e e nf e a t u r e sa n dt e x tc a t e g o r i e s t h e n ，t h i sp a p e rr e a l i z e st h e r o c c h i oa n dk n nc l a s s i f i c a t i o nm e t h o d s ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e m o d i f i e dw e i g h tm e t h o dc a n a c t u a l l yi m p r o v et h ec l a s s i f i c a t i o np e r f o r m a n c e k e yw o r d s ：t e x tc l a s s i f i c a t i o n ，c h i n e s es e g m e n t a t i o n ，f e a t u r ew e i g h t ，f e a t u r e s e l e c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王搿丽 签字目期： 年月日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 + ，向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 土祈回 一 导师签名：) i 可乙腾 导师签名： i l 尘照 签字日期：年月 日签字日期：年月 日 第一章绪论 第一章绪论 1 1 文本分类的研究背景和意义 随着信息技术的发展及互联网的普及和应用，各种电子形式的文本文档以指 数级的数量增长，尤其是科技期刊的电子化和数字图书馆的发展极大地丰富了网 络知识资源。如何在众多的资料中快速准确的找到人们需要的信息，成为当前的 一个研究热点。 基于人工智能的文本分类技术是数据挖掘领域中重要任务之一，它能够根据 文本的语义内容，将文本划分到预定义的类别体系中，为信息检索提供更高效的 搜索策略和更准确的查询结果。其中，高效性在于用户可以首先确定查询的可能 类别，以减小需要进一步匹配的文本数量。有效性在于相似的文本很可能与相同 的查询相关。这样，检索的查全率和准确率都得到了提高。 文本分类的传统做法是对网上信息进行人工分类，并加以组织和整理，为人 们提供一种相对有效的信息获取手段。但是，这种人工分类的做法存在着许多弊 端：一是耗费大量的人力、物力，二是存在分类结果不一致的现象，即使分类人 的语言素质很高，对于不同的人，其分类结果仍然不尽相同。甚至同一个人，在 不同时间做分类也可能会有不同的结果。 网络信息资源的快速增长，一方面增加了对快速、自动的文本分类方法的需 求，另一方面也为基于机器学习的文本分类方法准备了充分的资源。相对于人工 分类，基于机器学习的文本自动分类系统具有以下特点【l 】： 1 高效率、高速度。自动分类的效率将是人工分类的百倍甚至千倍，从而 大量的节约人力。 2 较高的准确度。消除了人为错误产生的可能。 3 良好的自适应性。可快速适应文本的更新及类别设置的变化，适应不同 环境及需求。 现在，文本分类几乎是所有基于内容的文本管理学科的基石，是处理和组织 大规模文本信息的关键技术，并广泛应用于信息抽取、信息检索、问答系统等文 本处理和信息检索的各个领域，可以说研究文本分类有着广泛的商业前景和应用 价值。因此，如何提高文本分类的性能及效率成为当前亟待解决的问题。 第一章绪论 1 2 文本分类的研究现状 1 2 1 文本分类在国外的发展 国外对于文本分类的研究开始较早。2 0 世纪5 0 年代，h p l u h n 2 提出词频 统计思想并主要用于自动分类。1 9 6 0 年，m a r o n 发表有关自动分类的第一篇论 文【3 】。1 9 6 4 年，m o s t e l l e r 和w a l l a c e l 4 考虑单词、句子长度、功能词的频率和词 汇差异等特征项，开创了文本分类的新阶段。s a l t o n 等人在6 0 年代末提出向量 空间模型【5 1 ，并逐渐成为处理文本分类领域大规模语料库较好的表示模型之一。 从2 0 世纪6 0 年代直到8 0 年代末期，大多数实用的自动文本分类系统都是 基于知识工程的人工智能系统，即由专业人员编写一些分类规则来指导分类。其 典型应用为卡内基集团为路透社开发的c o n s t r u e 系统1 6 j 。虽然该方法取得了较好 的分类效果，然而该方法的分类规则制定困难，推广性差，如果分类器被转到完 全不同的领域，专业人员必须重新编写分类规则，从而很难大规模推广应用。9 0 年代以后，基于机器学习的自动文本分类技术开始取代基于知识工程的方法，并 成为文本分类的主流技术。该技术通过学习人工标注的文本集自动构建分类器， 并在新文本到来时作为一个规则决定新文本的类别。这种系统进行正确分类的能 力几乎可以与人类专家相媲美，因而完全取代了文本分类专家系统，成为信息系 统学科最重要的研究领域之一。目前，自动文本分类技术己经成为机器学习技术 和信息检索技术的交汇点和结合点，成为所有基于内容的自动文本管理技术的重 要基础。 近年来，几乎所有重要的机器学习算法在自动文本分类领域都得到了广泛应 用，如：k n n 7 - 8 、朴素贝叶斯 9 - 1 0 】、决策树1 1 】、神经网络 1 2 】、支持向量机 1 3 - 1 4 】、 最大熵【1 5 】等，这些分类算法大多是基于向量空间模型的。基于向量空问模型的算 法作为一种简单、有效的算法，在信息分类中引起广泛关注，并且取得了很好的 成果，其中使用范围最广的是k n n 算法。国外的文本自动分类研究已经从最初 的可行性基础研究经历了实验性研究进入实用阶段，在邮件分类、电子会议、信 息过滤等方面取得了越来越广泛的应用。 1 2 2 文本分类在国内的发展 和国外的发展状况相比，国内的分类技术发展相对滞后。一方面因为国内起 步较晚，另一方面则由于国内的文本分类主要针对中文文本。由于中文和英文的 巨大差异，英语文本是已充分分隔开的词串，而汉语文本是连续字串，句子中各 词语间没有固有的分隔符( 空格) ，国外的技术并不能完全适应于中国的信息资 第一章绪论 源，为此中囡的学者在英文文本分类研究的基础上，结合中文文本的特定知识， 形成了中文文本自动分类研究体系。 吴军、吴立德、黄萱菁【16 l 等进行了汉语语料自动分类的研究，他们以词为特 征项构成特镊向量，以频度作为词的权重，利用一些分类算法构造分类器，取得 了定的效果。然而，中文分诩技术的发展还不是很完善，命名实体识别、歧义 分析等仍是罔前中文分词的难点【1 7 】，分词的准确率一定程度上还影响着文本分类 系统的性能。另外，臻翡国内尚无标准熊震于文本分类的中文语料库，各个研究 者分头收集自己的训练文本集，并在此基础上开展研究，因此系统的性能可比性 不强。同时，由于财力人力有限，中文语料库的规模普遍不大。 1 3 本文的主要工作及组织结构 本文以向量空间模型为基础，对中文文本分类的若干技术如：中文分词、特 征项权重计算、特征项选择、分类算法等进霉亍了深入的分析与探讨，并提出了一 些改进方法，通过实验进行了验证。 文本分类中的一个主要的问题是离维的向量空间，为了提高分类效率，许多 文本分类系统都引入了特征选择方法，将那些对分类贡献不大，或者起干扰作用 的特征词过滤，来压缩向量空间维数。常用的特征选择算法都是针对某一标准来 淘汰特征，选择上有壁偏重，有可能将某些对分类有重要贡献的特征过滤撵或是 引入某些对分类贡献不大的特征，如互信息偏重于低频词等。本文尝试将多种不 同的特征选择方法组合，一定程度上抑制了单一选择方法的缺陷。实验证明，组 合的特征选择方法比单一的特征选择方法对于分类有更好的效果。 在向量空间模型中，特征项对分类所起到的作用大小并不相同，因此，必须 针辩它们对分类所起的作用大小赋予不同的权重。本文分析了传统的权重算法， 发现t f i d f 和基于熵概念的权重等都是在全部文档集合的角度考虑特征项的重 要性，不能体现特征项在不同类别中的重要程度差异，针对这一闯题，本文提出 使用反映特征项与类别相关程度的互信息来修正t f i d f 的改进权重算法。 本文的组织结构如下： 第一章绪论 首先介绍了文本分类的研究背景、意义，讨论了国内外的研究现状，然后对 本文的研究内容和组织结构徽了篱要分绣。 第二章文本分类的相关技术研究 篙单介绍了文本分类的相关技术，包括中文分词、特征顼选择、特征项权重 以及常用的文本分类算法等。在特征选择方面，分析了单个特征选择算法的不足， 第一牵绪论 并介绍了使用多个特征选择方法的组合选取特征的过程。在特征赋权方面，分析 了传统疆i d f 和基予熵概念的权重算法的不足，提出剩用互信息m i 计算特征 项与各类别的相关度，并以此修正t f i d f 的改进权重算法t f i d f m i 。 第三章文本分类系统的实现 介绍了本文实现的中文文本分类系统的结构和系统流程，并针对各功能模块 的具体实现作了详细介绍。 第四章文本分类系统结果分析 根据第二、三章的理论知识，实现了类中心和k n n 两种分类算法，实验比 较了t f i d f - m i 算法与传统权重算法斡性能优劣。在类中心分类法的基础上， 针对不同的特征选择方法组合形式，实验比较了它们的分类性能，得出在分类性 能上两个特征选择方法的组合( t w o c o m b i n e ) 最佳，且以多个特征选择方法对 特征项评分的最小值作为特征项最后分值的方法( l r ) 要优于_ 以平均值作为最 后分值的方法( a r ) 。 第五章总结和震望 对全文工作进行了总结，并介绍了进一步的研究方向。 第二章中文文本分类的相关技术研究 2 1 中文分词 第二章中文文本分类的相关技术研究 词是自然语言中最小的语义单位，而汉语文本是连续的汉字串，词与词之间 没有明确的分隔标记，因此自动识别词边界，将汉字串切分为正确的词串的汉语 分词问题成为中文信息处理中的重要问题之一。现有的分词算法可分为三大类： 基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法 1 8 - 1 9 】。 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与词 典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。按照扫描方向 的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配 的情况，可以分为最大匹配和最小匹配；常用的几种机械分词方法有：正向最大 匹配法、逆向最大匹配法、最少切分( 使每一句中切出的词数最少) 法。机械分 词方法简单，易于实现。但是由于自然语言丰富的表达方式，汉语句法构成的复 杂性，新词汇的不断涌现，使得机械分词法面临着很多问题。如：一词多义问题、 歧义切分问题和未登录词识别问题，仅用机械分词方法都不能够很好地解决，这 些问题直接影响了分词的准确率。 。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各 种其它的语言信息来进一步提高切分的准确率。一种方法是改进扫描方式，称为 特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的 词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少 匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息 对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整， 从而提高了切分的准确率。 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其 基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处 理歧义现象。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识 的复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理 解的分词系统还处在试验阶段。 3 基于统计的分词方法 第二章中文文本分类的相关技术研究 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好 的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的甄现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程 度高于某一个阈值时，便可认为此字组构成了一个词。这种方法不需要分词词典， 也叫做无词典分词。这种方法的局限性在于，会经常抽出些共现频度高、但并 不是词的常用字组，例如“这一、“之一 、“有的”、“我的、“许多豹静， 等，并且对常用词的识别精度差，时空开销大。实际应用时一般将基于词典的和 基于统计的分词方法结合使用，既可以发挥匹配分词切分速度快、效率高的特点， 又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词 过程中，有两大难题一直没有完全突破。 1 歧义识别 歧义切分现象是自动分词中不可避免的现象，对歧义切分字段嬲处理畿力， 是评价汉语囟动分词系统性能的标准之一。分词歧义分为组合歧义和交叉歧义两 种。 a 交叉型歧义，在字段a b c 中，这里a 、b 、c 分别代表有一个或多个汉 字组成的字串。a 、a b 、b c 、c 分别都是词表中的词，则称该字段为交 叉型歧义字段。如：“中国人，“中圈入”两种切分练采。据统计， 交叉歧义字段占全部歧义字段的8 5 以上。由于没有人的知识去理解， 计算机很难知道到底哪个方案正确渊。所以这也是分词系统所要重点解 决的问题。 b 。组合型歧义，在字段a b c 中，a 、b 、a b 分别都是词表中的词，则称 该字段为组合登歧义字段。如：“他其有非凡的才能和“只有 他才能举起这个重物”。 如果交叉歧义和缀合歧义计算机都麓解决的话，在歧义中还有一个难题，是 真歧义。真歧义是说给出一句话，由人去判断也不知道哪个应该是词，哪个应该 不是词。例如：“乒乓球拍卖完了”，可以切分成“乒乓球拍卖完了”，也可切， 分成“乒乓球拍卖完了，如果没有上下文其他的句子，恐怕谁也不知道“拍 卖”在这里算不算一个词。 2 未登录词识别【2 1 - 2 2 由于不存在绝对宪备的词典，虽然一般词典都能覆盖大部分词语，但仍有一 部分词语不能穷尽的收录于系统词典中，这些词谮称为未登录词或新词。常见躲 未登录词有以下几类： 第二章中文文本分类的相关技术研究 a 专有名词，包括人名、地名、机构名、外国译名、时间词等； b 重叠词，如“平平安安”，“研究研究 ； c 派生词，如“一次性用品”中的“一次性”； d 领域相关的术语，如“互联网”、“聚氯乙烯”等； 举例来说：人们可以很容易理解句子“王军虎去广州了”中，“王军虎”是 个词，因为是一个人的名字，但要是让计算机去识别就团难了。如果把“王军虎” 做为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的人 名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存 在问题，例如：在句子“王军虎头虎脑的”中，按字典切分，把“王军虎”切分 成一个词显然是不合适的。 一方面语言的不断发展和变化，新词会不断的出现，另一方面因为词的衍生 现象非常普遍，也没必要把所有的衍生词都收入词典中，所以一个鲁棒的分词系 统必须具备识别这些未登录词的能力。迄今为止出现了很多识别未登录词的方 法，包括规则的方法和统计的方法。统计显示，人名和地名，特别是中文人名和 地名，是未登录词的重要来源，因此，若能解决人名和地名的问题，绝大多数的 未登录词问题就能迎刃而解。 2 2 特征项选择 特征项是文本中的语言单位，对于中文来说可以是字、词、短语，甚至可以 是句子或者段落。特征项也可以是概念。概念是词组的语义抽象。通常特征项的 选择是由系统设计的目的、精度、存储空间的大小等各个方面具体的要求所确定。 选出的特征项越具有代表性，语言层次越高，所包含的有用信息就越多，但是分 析的代价就会越大。词是文本中最小的语义单位，在文本中出现的频率呈现出一 定的统计规律，随着中文分词算法的不断改进，分词的精度得到了很大的提高。 所以人们通常选择词作为文本的特征项。但是选用词或者词组作为文本的特征 项，一个主要的困难就是高维的特征空间。一般来说，中等规模文本分类问题所 对应的文本特征空间就高达几万维、甚至十几万维，其维数远远超出用于分类器 训练的文本文档的个数。如果直接在这样一个高维特征空间上进行分类器的训练 和分类，很可能带来两个棘手的问题：一是很多在低维空问具有良好性能的统计 分类算法在计算上变得不可行；二是在训练样本个数一定的前提下，过多的特征 使得样本统计特性的估计变得非常困难，从而降低统计分类器的推广能力或泛化 能力，呈现所谓的“过学习 或“过训练”的现象。 要避免出现“过学习”的情况，用于统计分类器训练的训练样本个数必须随 第二章中文文本分类的相关技术研究 着特征维数的增长而呈指数增长，从而造成人们所说的“维数灾难( c u r s eo f d i m e n s i o n a l i t y ) 。为了避免“过学习”或“过训练，同时也为了提高分类器的 训练和分类效率，必须在分类器的训练之前，把特征维数压缩到与训练样本个数 相适应的地步。因此，如何降低原始特征维数，成为统计模式识别的一个重要研 究课题。作为消除特征向量中可能存在的数据噪声以及改善分类器性能的基本手 段，特征抽取和特征选择方法在自动文本分类领域得到越来越广泛的运用。 特征抽取与特征选择是一类文本集共性的归纳过程。传统的特征抽取算法通 过线性变换降低特征维数，例如主成分分析( p c a ) 口引、线性判别式分析( l d a ) 口制、 潜在语义索引【2 5 】等。特征选择则直接从特征项集合中选择部分特征来表示文档向 量。虽然特征抽取算法对降低特征维数非常有效，然而文本集合的高维性经常使 一些特征抽取算法的计算复杂度过高而降低文本分类的效率，而特征选择算法则 无此问题，因此往往比特征抽取更能很好地应用于文本分类系统。 目前对文本特征进行特征子集选择的算法一般是构造一个评价函数对特征 集中的所有特征进行评估，这样每个特征项都得到一个评估分值，然后对全部的 特征项按照其分值的大小进行排序，选取前个特征作为结果，其中是一个人 为预定的整数。一般认为评估分高的特征项是表现文章的主干，对文章的理解和 表示起关键作用，而评估分低的特征项对文章内容的贡献很小，去掉这些特征项 将不影响文档意思的表达和分类的结果。常用的特征评分函数有【2 6 。2 9 】：特征频度、 文档频数、互信息法、期望交叉熵、信息增益和c h i 统计等，其关键是找出体现 类别的关键特征。 2 2 1 常用特征选择方法 1 特征频度 特征频度指训练集中特征f 出现的次数。这是最简单的特征选择方法。一般 来说，特征项在文本集中出现次数越多，对文本分类的贡献越大。由于原始特征 集中绝大部分是低频特征，因此，设定词频阈值对过滤低频特征非常有效，可以 获得很大的降维度。对高频特征而言，当它们均匀分布在所有文本中时，对分类 的作用很小，基于特征频度的特征选择方法将不能很好的识别它们。因此，特征 频度方法主要用在文本标引时直接删除某些低频特征。 2 基于文档频数的特征选择 文档频数是训练集中含有特征项t 的文档数。该方法把所有在文档集中出现 的词作为候选特征项，从中去除那些包含特征项的文档数小于某个既定阈值的特 征。其理论假设为稀有词条或者对分类作用不大，或者是噪声，可以被删除。文 档频数方法在计算量上比其它特征选择方法小很多，实际运用中的效果也比较 第二章巾文文本分类的相关技术研究 好。但如果莱一稀有词条主要出现于采类文本中，且对此类的贡献较大，则此方 法很可能会把这些显著特征错误地过滤捧。文献【3 0 通过实验表甓，用特征频度 和文档频数的组合进行特征选择可以得到更好的降维效果。 3 互信息( m 1 ) 互信息是统计学和信息论中一个重要的概念，它用来度量两个统计量之问相 互依赖的程度，在文本分类系统中互信息衡量的是特征和类别之间的统计关联程 度。关联程度越高，置信息越大，反之亦然。特征f 和类别0 之间的互信患定义 如下： 榔一瑚。g 而p ( t 丽, c j ) 函g 等 缘1 ) 其中，p ( t i c j ) 为在0 中出现的概率，p o ) 为特征项f 出现的概率。实际计 算中公式可近似为： m ( t , c j ) = l o g 丽酉ax 币n 面 2 _ 2 ) 式中n 为训练集中的总文档数；a 为属于类别勺，并且包含特征词f 的文档； 宴代表包含特征词，但不属于类别0 盼文档；e 代表属于类别勺，但不包含特 征词t 的文档。 包含k 个类别的文档集合上，特征项t 的互信息有如下两种计算形式： 雠) = 驴k 川。g 掣 p ) 撇) = 蝴加g 等 ( 2 _ 4 ) 跌公式( 2 1 ) 可以看出，当特征的p ( t l c i ) 馕相等时，稀有谲滗普通词的分值 要高。若特征项t 和类别c ，相互独立，则m l ( t ，c ，) 为零。p ( f ) 越小而p ( tc ，) 越大 的情况下，特征项t 提供给类别c ，的信慧量越大，这个特征项越能代表这一类。 反之，p ( f ) 越大而p ( tic ，) 越小，则可能得到负的互信息值，这种情况下，特征 项对分类的意义同样很大，因此，常采用公式( 2 - 5 ) 计算特征项的互信息值， 把舔来那些熬有较大的负互信息值的特征顼也纳入到特征子集中束。 m z ( t ) ：圭最。) | l o g= 最o ) | l o g ( 2 _ 5 ) m i 评估函数没有考虑单词发生的频率，在不同特征项的条件概率相同时， 低频词比高频词的m 1 分值高，鄹此种情况下低频调易被选入特征予集中。 4 期望交叉熵( c e ) 第二章中文文本分类的相关技术研究 期望交叉熵与信息增益类似，也是一种基于概率的方法，但是不同于信息增 益对特征项属性的计算，期望交叉熵只计算出现在文本中的特征项。特征项的期 望交叉熵( c r o s se n t r o p y ) 定义如下： c e ( 泸蝶灿m g 篱 协6 ， 其中p ( c ，if ) 表示文本中出现特征项t 时，文本属于c ，的概率。如果特征项和 类别强相关，也就是p ( c jf ) 大，且相应的类别出现概率p ( c ，) 又小的话，则说明 该特征项对分类的影响很大，其对应的期望交叉熵值就大。期望交叉熵反映了文 本类别的概率分布，以及在出现了某个特征项的条件下，文本类别的概率分布之 间的距离。特征项的期望交叉熵越大，对文本类别分布的影响也越大。 5 信息增益( i g ) 信息增益( i n f o r m a t i o ng a i n ，i g ) 是信息论中的一个概念，表示了某个特征 项的存在与否对类别预测的影响。对于特征项t 和文档类别c ，i g 考察c ，中出现 和不出现t 的文档频数来衡量t 对于c ，的信息增益。特征项的信息增益度越大， 对分类的贡献率也就越大。设c 。，c ：c 。为预定义的类别集合，一个特征的信息 增益度定义如下： i g ( t , c j 驯州。g 等柳两1 0 9 等 ( 2 - 7 ) i g ( f ) ：一kp ( c ，) l 。g p ( c j ) + 尸o ) 圭p ( 勺if ) 】。g p ( c it ) + 尸( ；) kp ( 勺l ；) l 。g p ( 勺it ) ( 2 8 ) 其中p ( c ，) 为c ，类文档出现的概率；p ( c ，it ) 为包含特征词t ，并且属于c ，类文档 的概率；p ( c ，i f ) 为不包含特征词t ，并且属于c ，类文档的概率； 6 基于c h i ( x 2 ) 统计的特征选择 c h i 定义了特征项f 和类别c ，之间的相关性，并假设f 和c ，之间符合一阶自由 度的z 2 分布，特征项对于某类的c h i 统计值越高，它与该类之问的相关性越大。 定义如下： 以户盟案崭铲像9 ， 其中p ( f ，c ，) 为特征项f 和类别c ，同时出现的概率，尸( f ，弓) 为特征项硝姐类别 0 都不出现的概率，p ( t ，c j ) 为特征项f 不出现类别c ，出现的概率，p ( t ，弓) 为特 征项f 出现类别c ，不出现的概率，r 为训练集中的文本数。上式可表达为： 第二章中文文本分类的相关技术研究 z ：；) ： 丝! ( 丝兰旦z _ 一 ( 2 一l o ) z 。( 乙c ，) 2 百琵河而葛瓦万爵而 旺一 式中代表全体训练文档；彳代表属于类别c ，并且包含特征词t 的文档； b 代表包含特征词t ，但不属于类别c ，的文档；c 代表属于类别c ，但不包含特 征词t 的文档；d 代表即不属于类别c ；，又不包含特征词t 的文档。对一个特征 项，它的c h i 度量值有如下两种定义形式： k z 2 ( f ) = p ( c ，) z 2 ( f ，c ，) ( 2 11 ) j = l z 2 ( f ) = m a x ；：lz 2 ( f ，c ，) ( 2 一1 2 ) 7 文本证据权 这是一种较新的评估函数，它衡量类的概率和给定特征时类的条件概率之问 的差别。当计算出来的函数值小时，说明词条对分类的影响小，应该被去除。文 本证据权计算公式如下： we(t,cj)=p(t)llog丽p(cj1 t ) ( 1 - p ( c j ) ) l m m ， 愀嘉州睇p 鸱( c j ) ( 1 t ) 叫( 1 - p 叫( c j 功) ) i 协 其中k 为文本类别数。 2 2 2 组合特征选择方法 目前常用的特征选择算法，如：t f 、d f 、互信息、期望交叉熵、信息增益、 c h i 统计等都是从某一角度衡量特征词对分类的贡献，各有偏重。 特征频度方法认为特征项在文本集中出现的次数越多，对文本分类的贡献越 大。然而对于均匀分布在所有文本中的高频特征而言，它们对分类的作用很小， 如果单一使用特征频度的方法将不能很好的识别它们。 文档频数算法假设稀有词条或者对分类作用不大，或者是噪声，可以被删除。 但是如果某稀有词条主要出现于一类文本中，此时稀有词条对该类文档的表征能 力是比较强的，但文档频数算法很可能把这种类型的显著特征错误地过滤掉。 对于互信息来说，互信息表示特征项与类型之间的相关程度。当特征的出现 只依赖于某一类型时，特征与该类型的互信息很大；当特征与类型相互独立时， 互信息为0 ；当特征很少在该类型文本中出现时，它们之问的互信息为负数，即 第二章中文文本分类的相关技术研究 负相关。由互信息公式( 2 1 ) 可以看出，对于频度小的特征，l o g p ( t ) 的变化比 l o g p ( tc ，) 快，是互信息中的主要部分，这使得低频特征具有较大的互信息，容 易引起过度拟和问题。另外，在计算特征项互信息值的过程中，互信息给许多特 征项的估值是完全一样的【2 9 】，在实际文本分类中，经过互信息估值的特征可能有 好几千个甚至上万个之多，这样在特征选择排序时就只能随机地删除那些估值与 前面的相同却不幸排在后面的特征，造成大量有用信息的损失。 信息增益表示了某一特征项的存在与否对类别预测的影响，定义为考虑某一 特征项在文本中出现前后的信息熵之差。某个特征项的信息增益值越大，贡献越 大，对分类也越重要。信息增益方法的不足之处在于它考虑了特征未发生的情况。 虽然某个特征不出现也可能对判断文本类别有贡献，但这种贡献往往远小于考虑 特征不出现情况所带来的干扰【3 0 1 。特别是在类分布和特征值分布高度不平衡的条 件下，绝大多数类都是负类，绝大多数特征都不出现。即p ( f ) 尸( f ) ，此时信息 增益大的特征，主要是公式中代表单词不出现的部分大，而非代表单词出现的部 分大，即此时的函数值由不出现的特征决定，因此信息增益的效果会大大降低。 另外信息增益和c h i 属于贪婪算法，在特征集本身就很少时，这两种特征选择算 法的性能不佳。 由于各个评价函数考虑的侧重点不同，各种方法选出的前个特征项也就不 尽相同。对于某一特征项来说，有可能在一个特征选择方法中取得较小分数，而 在另一个特征选择方法中获得较高的分数，即出现各个评价函数对同一个特征项 的评估分相差很大的情况。为了避免单个特征选择算法的弊端，本文考虑将常用 的特征选择方法进行组合，试图通过多个特征选择方法的联合使用来削弱单个特 征选择方法的缺陷。其基本思想就是综合多个特征选择算法对特征项的评分作为 该特征项的最后分数，然后按分数大小排序特征项，选取特征集合。至于如何综 合多个特征选择算法对特征项的评分，有多种方法可以参考，如：各分数的最大 值、最小值、平均值等都可以用作该特征项的最后评分。本系统实现了使用各特 征选择方法对特征项评分的平均值和最小值来定义特征项最终分值的两种方法， 并进行分类实验，比较它们对分类性能的影响。假设候选特征项集合为 t = t ，t 2 , t ，t 。) ，其中刀为文本集中所有候选特征项的个数，有m 个特征选择方 法，第f 个特征选择方法对候选特征集合的分值向量为：w ，；( 。，w i ：，w i ，w 加) ， 则组合特征选择方法的过程为： 1 标准化分值向量 令m = m a x ( w ，l ，2 ，嵋3 ，w i n ) ，i = 1 , 2 ，m 。 w i = 土，标准化后取值为0 1 之间 w i m a x 第二章中文文本分类的相关技术研究 2 若取平均值作为特征项的分值，则最后的分值向量为： w 2 ( 二l 善m ，去善9 - , 9 去善) ( 2 - 1 5 ) 若取最小值作为特征项的分值，则鳓( j = 1 , 2 ，n ) 个特征项的分值为 w i 嗵，2m m c w u ，w 2 j ，) 最后的分值向量为： w = ( w m 缸l ，n 2 ，) ( 2 - 1 6 ) 3 选择w 中分值最大的特征项作为文本集的特征集合。 2 3 特征项权重 2 3 1 传统的权重算法 在向量空间模型中，每个文本都是用一个特征向量来表示，通过比较两个向 量之问的距离来确定两个文本是否属于同一类；而向量中的每一个分量由特征项 对文本的区分度来赋值，即特征项的权重。因此，每个特征项的权重对于能否最 大程度的反映出文本的实际差异有很大的作用。常用的特征权重算法有：布尔函 数、t f i d f 函数、基于熵概念的权重等。 1 布尔权重 布尔权重是一种最简单的赋权方法，只有0 和1 两种取值。如果特征项出现次 数为0 ，则其权重为0 ，如果特征项出现次数大于0 ，则其权重为1 。 表达公式为： )= w ，较好的体现了这一点。 2 4 文本分类算法 文本分类算法就是一个建立从文本属性到文本类别空间的映射过程。现有的 分类方法主要是基于统计理论和机器学习方法的。常用的分类算法有类中心分类 法、贝叶斯算法、k n n 算法和支持向量机算法等，下面分别对各种文本分类算 法加以论述。 1 类中心分类法 类中心分类法是基于向量空间模型和最小距离的方法。最早由h u l l 根据信息 检索中用于计算查询与文档之问关联程度的r o c c h i o 公式改造而成。该方法的分 类思路十分简单，首先将文本表示为向量空间中的特征向量，根据算术平均值为 每类文本集生成一个代表该类的中心向量，然后在新文本来到时，确定新文本的 向量，计算该向量与每类中心向量间的距离( 相似度) ，最后将新文本归到与其 距离最近的类。 第二章中文文本分类的相关技术研究 类中心分类法的分类机制篱单，在训练和分类阶段的计算量相对较小，运行 速度尤其是分类速度较快，经常被用于对分类时间要求较高的应用之中，并成为 和其他分类方法比较的基准。 2 k n n 算法 k n n 算法是模式识别中广泛使用的分类方法，它的基本思路【7 1 是：给定篇 待分类文本，首先生成它的特征向量，然后在训练文本集中找出与该文本距离最 近( 最相似) 的爱篇文本，根据这趸篇文本所属的类别判定待分类文本的类别。 k n n 算法有分类机制简单的优点，但存在的问题是，需要将所有样本存入 计算机中，每次决策都要计算待识别样本与全部训练样本之间的距离来进行比 较，因此计算新文档时存储量和计算量都较大。另一个重要的闯题是参数鬈的选 择，如果苁值选择过小，不能充分体现待分类文本的特点，藤如果必值选择过 大，则一些和待分类文本实际上并不相似的文本亦被包含进来，造成噪声增加而 导致分类效果的降低。目前趸值的确定没有很好的方法，一般采用先定一个初始 僮，然后根据实验测试的结果调整x 值。 3 朴素贝叶斯分类法 朴素贝叶斯( n a i v eb a y e s ，n b ) 算法最一种概率方法，其基本思想是利用单 蠢霉帮类之闻的联合概率，通过对训练数据的学习，估计新文本属于每类的概率， 并将新文本分到最可能的分类。该方法的朴素部分在于它的单词的独立性假设， 即不同单词在给定类别下的条件概率分布是互相独立的。该假设使得n b 分类器 不需要计算萃词之阅的联合分布概率，使得其速度远快于那些非朴素贝时舞分类 器。 设新文本d 的特征向量w = ( w 1 ，w 2 ，) ，共有k 个不同的类别q ，c ：，q ， 分类器在已知w 的情况下，预测d 属于后验概率最大的那个类别。也就是说，分 类器将未知类别的样本d 归属到类别致当且仅当： 以g | 蝴 p ( c ，| 砷对于1 j m ，j i 也就是p ( c ，1w ) 最大。其中的类别c i 就称为最大后验概率的类别。由贝叶斯 公式可得： p ( c ，1w ) ；p ( w ic 1 ) p ( c , ) ( 2 2 2 ) 一 p ( w ) 由于p ( w ) 对于所有类别均是相同的，因此只需要p ( wic i ) 尸( 岛) 取最大