中文文本分类算法研究.pdf

《中文文本分类算法研究.pdf》由会员分享，可在线阅读，更多相关《中文文本分类算法研究.pdf（66页珍藏版）》请在三一文库上搜索。

1、V 来了时间和金钱上的巨大浪费。另外，大量有害和无用的信息也威胁着社会各个行业的 发展。如何在海量数据环境下有效地管理并快速地检索所需的数据，成为信息科学领域 迫切需要解决的问题，各种信息检索技术也孕育而生。 数据的形式是多种多样的，自然语言形式的数据是人们最为关心的数据形式之一， 作为人类思维的载体和人们交流的主要工具，它蕴含着丰富的数据量和人的主观思想。 作为语言的明文形式，自然语言文本存在着语法、语义、文字等等众多不统一因素，由 于这些特殊性，对于自然语言文本的分类过去主要由领域专家和语言专家来完成，这种 人工方法周期冗长、费用高昂、效率低下，逐渐不能适应信息爆炸时代的需求。 随着技术的

2、发展，将自然语言文档自动分类成若干主题的类别这一项工作作为一门 新兴的学科发展了起来，称为自动文本分类( A u t o m a t i cT e x tC l a s s i f i c a t i o n ) ，为简洁起见， 本文将自动文本分类简称为文本分类( T e x tC l a s s i f i c a t i o n ) 。文本分类的主要任务是在给 定的分类体系下，根据文本的内容自动地确定与文本关联的类别【l 】。文本分类技术不仅 仅解决了用户准确查找数据的需求，也在很大程度上降低了网络信息的杂乱特征。所以， 文本分类技术的出现受到了计算机和自动化领域内专家、学者和工程师们的广

3、泛重视。 从语言学角度来看，文本分类属于自然语言处理的领域；从计算机学科角度来看， 文本分类属于模式识别和机器学习的领域；从信息学角度来看，文本分类属于信息处理 的领域。进而继续推广，文本分类被认识为许多技术的基础，如搜索引擎、信息过滤、 情报分析、情感分析，等等。因此，文本分类技术有着广泛的应用前景，是一项具有较 大研究价值的关键性技术。 由于文本分类问题首先在国外被提出，中文的文本分类工作起步比较晚，而根据统 计，人类文明史上8 0 以上的知识和信息均由文本形式留存，在计算机应用方面，用于 数学计算的仅占1 0 ，用于过程控制的不足5 ，8 5 以上的应用都与文字和语言处理 相关。可以说，

4、在信息化的现代社会，语言信息的处理技术水平是衡量整个社会信息化 水平的重要标志，发展中文的文本分类，具有很强的实际意义。 l 绪论 硕士论文 1 2 国内外研究现状 1 2 1 国外研究现状 国外文本分类研究起步比较早，在上世纪5 0 年代末起就开始研究。1 9 5 7 年， H E L u l m ( I B M 公司) 在这一领域内首先提出了词频统计的思想，并将其应用于文本分 类工作，开创了文本分类的先河。1 9 6 0 年，M a r o n 等发表了题名为( O nr e l e v a n c e ， p r o b a b i l i s t i ci n d e x i n ga

5、 n di n f o r m a t i o nr e t r i e v a ) ) 的关于自动分类的第一篇论文，正式标志 着文本分类作为一个独立的研究课题出现在了世界上【2 】。此后大量的学者和研究人员在 这一领域提出了很多具有创新性的研究，总的来说，文本分类国外的技术性发展历程可 以分为两个大的阶段： ， 1 ) 6 0 年代至8 0 年代，基于知识工程技术的方法。 这种分类方法必须通过人工定义分类规则来对待分类文本进行分类，需要依赖于某 一领域的专家，花费时间和人力较多，必须对于分类领域有较为深入的了解，才能构建 出合适的分类规则。这一阶段比较典型的系统有卡耐基为路透社开发的C o

6、n s t r u e 新闻分 类系统等【3 J 。 2 ) 8 0 年代后期至今，基于机器学习的方法。 随着机器学 - - J ( M a c h i n eL e a r n i n g ) 的发展，机器学习方法为主的信息自动分类技术渐 渐取代了过去的知识工程方法，成为了文本分类的主流研究方法，这种基于机器学习的 方法可以避开专家领域，比较典型的方法有朴素贝叶斯、决策树、K 最近邻、神经网络、 支持向量机等等，这些基于机器学习的分类方法大大提高了组建文本分类系统的效率并 提高了分类精度和速度，已经成为文本分类的主流方法并且进入到了实际应用阶段。目 前普遍认为，K 最近邻方法和支持向量机方法

7、是文本分类中效果最好的方法。 近年来，文本分类的主流研究基本上围绕着文本表示方法、特征的约简、分类器融 合、分类器改进等几个方向，研究目标也越来越细化，如特征选择、分类器融合等技术 也作为单独的研究领域拥有了一大批研究学者，也涌现出了很多卓有成效的研究成果。 J o a c h i m s 提出了基于支持向量机的文本分类算法，并且证明这种方法比其他方法更适合 文本分类【4 】。H o t h o m 等结合B a g g i n g 中产生的O u t - o f - b a g 样本提出了D o u b l e - b a g g i n g 方法来进行分类【5 】。N i g a m 等使

8、用最大期望算法( E M ) 对有标记和无标记的文本进行了分 类 6 1 。S t e p h a nB l o c h d o m 等提出了基于B o o s t i n g 方法的集成学习文本分类方法【_ 7 1 。Z h o u 等提出了基于聚类改进的K N N 文本分类算法【8 l 。R o nB e k k e r m a n 等分析了而二元模型 B i g r a m s 在文本分类中失效的主要原因，并应用一元模型的簇状信息改进T - - 元模型 9 1 ， 等。在这些研究成果的推动下，文本分类的各个技术节点也已经框架化，基本可以分为 文本预处理、特征约简、表示方法、分类器、评价指

9、标等几个大的步骤。 2 硕士论文中文文本分类算法研究 1 2 2 国内研究现状 国内文本分类起步比较晚，基本上是在延续国外对英文的研究工作，相较于英文文 本分类而言，国内使用的中文在分词上面有着比较大的困难，使得对于中文文本的分类 效果在很长一段时间内都并不太好。随着中文分词技术的完善，中文文本分类逐渐摆脱 了由于中文分词而造成的限制，目前正处于高速发展阶段。 8 0 年代初，侯汉清教授首次提出了用计算机对中文文本进行自动分类的概念，并 对于国外的研究成果和目前的应用进行了系统性的探讨【l 们。在此后，大量的学者对于中 文文本分类进行了深入的研究，出现了一些经典的中文文本分类的相关方法。 在中

10、文分词方面，李庆虎等分析了分词词典机制在分词中的作用，并提出了一种双 字哈希词典机制，提高了中文分词的效率【l 。宋彦等针对基于字的分词方法效果不佳的 问题，提出了一种使用字词联合解码的分词方法【1 2 】。朱聪慧等使用无向图模型，将分词 和词性标注整合到同一框架，提高了词性标注的效果【1 3 1 。 在特征约简方面，王卫玲等考虑了特征与类别、特征与特征之间的关联情况，提出 了一种改进的基于条件互信息的特征选择算法【1 4 1 。刘海峰等为了解决文本分布倾斜对分 类的影响，提出了一种基于散度差准则的特征降维方法【l5 1 ，王培涌等结合类间集中度、 类内分散度和反文档频率提出了一种新的特征选择

11、方法【1 6 1 。翟亚利将非负矩阵分解引入 中文文本分类中，并提出了非负矩阵的初始化方法，改进了互信息特征选择算法【1 7 】。龙 鹏飞等结合蚁群算法和遗传算法提出了一种新的特征提取方法，以提高特征选择的准确 度【1 引。 在表示方法方面，张爱华等研究了分词和文本表示方法对于文本分类的影响，提供 了一些理论指导【1 9 】。何伟等提出使用张量空间模型来表示文本【2 0 1 ，胡学钢等使用词向 量空间模型来表示文本【2 l 】，都取得了一些成绩。周新栋等使用N 元语言模型来表示中 文文本，脱离了传统的词袋模式，构建了一种基于词的二元模型分类器L 2 2 1 。 在分类器方面，李荣陆等结合最大熵

12、模型提出了一种中文文本分类方法【2 3 1 。袁方等 提出了利用文本的标题、摘要、关键词、重点段落等进行渐进式K N N 分类的方法【2 4 1 。 张翔等提出先通过粗糙集进行文本特征选择，再采用A d a B o o s t 来提高分类器性能的组 合中文文本分类方法L 2 引。毛雪岷等提出了对典型类别区分词进行加权后基于语义引导与 支持向量机的中文文本分类方法【2 6 j 。张翔等以决策树算法C 4 5 作为弱分类器，使用投 票规则合成了一种新的B a g g i n g 中文文本分类算法【2 7 】。卢祖友等针对支持向量机在大规 模数据集上收敛速度慢的情况，提出了一种基于球向量机的中文文本

13、分类算法，取得了 较好的效果【2 引。 在中文文本分类理论研究轰轰烈烈展开的同时，也出现了一些效果比较好的实际应 用和产品，如新浪网开发的中文垃圾邮件分类系统，百度中文搜索引擎，清华大学的张 l 绪论 硕士论文 东礼等人开发的中文文本分类系统，哈尔滨工业大学社会计算与信息检索研究中心开发 的语言技术平台等等。 1 3 本文主要工作 本文紧密围绕中文文本分类，总结了文本分类的研究背景，国内外研究现状和文本 分类的相关技术，着重分析了特征选择方法、支持向量机理论的一些发展变化和目前存 在的问题。 在中文文本特征选择中，传统的信息增益由于没有考虑特征项在类别中的分布情 况，所以在非平衡数据集上分类效

14、果不够理想。针对信息增益在非平衡数据处理上的不 足，引入了T h e i l 熵对信息增益进行了改进，提出了一种基于T h e i l 熵的信息增益方法 T - I G ，实验证明，T - I G 在解决非平衡数据集分类上相对于传统的信息增益方法在效果上 有了较大的提高。 支持向量机参数选择缺乏理论指导，且对参数非常敏感，传统参数选择方法主要依 靠经验和试凑。针对支持向量机在参数选择上的问题，结合G r o u pL e a d e r 优化算法对支 持向量机算法进行了改进，提出了一种基于G L O A 的支持向量机算法G L O A - S V M ，实 验证明，G L O A S V M

15、算法有效地改善了支持向量机性能对于参数的随机性，与同类算 法相比有着一定的优势。 最后，构建并实现了一个中文文本分类原型系统，在系统上对T - I G 方法和 G L O A S V M 算法进行了验证。 1 4 本文内容安排 本文主要内容安排如下： 第一章绪论 阐述本文的课题背景及研究意义，对文本分类的国内外研究现状进行综述，并且介 绍了文章的主要工作和内容安排。 第二章文本分类相关技术 总结分析文本分类所用到的相关技术，如中文分词、文本表示模型、特征选择方法 等等，着重阐述常用的文本分类方法和它们的异同点。 第三章支持向量机理论 对统计学习理论进行了简单分析，详细阐述支持向量机理论，并总结

16、了支持向量机 的发展、目前的热点研究方向和目前存在的问题。 第四章基于T h e i l 熵的信息增益方法 分析目前主流的特征选择方法，在数学上总结了信息增益目前存在的问题，并结合 T h e i l 熵对传统信息增益进行改进，提出了一种基于T h e i l 熵的信息增益方法T - I G ，并给 4 硕士论文 中文文本分类算法研究 出相应的数学实现方法。 第五章基于G L O A 的支持向量机算法 设计实验证明支持向量机对于参数的敏感性，阐述G L O A 算法，针对支持向量机 对参数的敏感性提出了一种新的支持向量机算法G L O A S V M 并进行了详细的描述，设 计实验验证G L

17、O A S V M 算法在分类上的有效性。 第六章中文文本分类系统设计 在前文的基础上设计并实现了一个中文文本分类原型系统，在系统上实验验证T - I G 方法和G L O A S V M 方法在中文文本分类上的有效性。 2 文本分类相关技术 硕士论文 2 文本分类相关技术 文本分类作为一门独立的学科，是由多个领域和学科交叉而成的，如语言学领域的 自然语言处理、数学领域的统计学、计算机学的模式识别、机器学习等等。文本分类技 术大致可以分为预处理、特征、分类器、评价等几个大的部分。本章就一般情况下的文 本分类典型过程对文本分类的相关技术做出相应阐述。 2 1 文本分类概述 文本分类是指在给定的类

18、别体系下，根据文本的内容自动地确定与文本关联的类 别，其中文本可以是指各种内容，如新闻、邮件、票单甚至是代码。文本的本质是语言 的明文表达，是由词条按照一定的语法语义搭配而成的非结构化或者半结构化数据，语 法语义构成的语句本身的抽象性非常强，而文本自动分类的载体计算机对于抽象事物的 处理能力是比较差的，相反，计算机对于数值计算和矩阵的处理能力比较强，所以我们 进行文本分类的时候，必须要对文本进行处理，处理成为计算机能够处理的形式。 让计算机代替人工进行识别和分类，是近些年计算机和自动化学科的研究热点，而 将待识别和分类的对象处理成为计算机能够或者说是方便处理的形式，就是其中比较重 要的环节。文

19、本作为一种待处理的对象，也必须要通过各种方法来达到这个目的，所以 出现了很多技术来解决这个问题。 通常来说，文本分类的工作流程是：对文本集合进行预处理，提取特征，并将其表 示为目标表示模型，然后构造分类器，用分类器对新文本进行分类，最后对结果进行评 价。其详细步骤如图2 1 所示。 i 预处理i ： 6 图2 1 文本分类详细步骤 硕士论文 中文文本分类算法研究 2 2 文本预处理 由于文本是由词作为元单位组成的，所以词就成为了文本的特征组成部分，文本预 处理工作主要是指从文本中提取出关键词的过程，在这一过程中首先要对文本进行分 词，然后去除停用词，有时还包括词性选择等工作，文本预处理过程是影

20、响文本分类性 能的重要过程之一。 2 2 1 中文分词 分词是文本分类的第一步，有着非常重要的作用，分词是否正确直接影响着分类的 正确率，分词技术一直以来都是影响中文自然语言处理的瓶颈。由于中文的语言特性， 导致了中文分词和英文分词的巨大差异，英文的词与词之间由空格隔开，助词介词等辅 助用词比较固定，并且不同的词性共用一个词根，对于英文的文本，按照空格作为分隔 符取出单词，再将单词映射为词根即可提取到词元。但是中文与英文有着根本的不同， 中文是以字和词为单位的连续性序列化语言，单字的词义蕴含也非常丰富，词是由字组 合而成，并且词与词之间没有分隔符，同样一句话可以有多种分词标准，如“羽毛球拍 卖

21、完了“ 这句，可以分词为：“羽毛球拍卖完了“ ，也可以分词为：“羽毛球拍卖完了“ ， 如何对于中文的歧义进行识别，就是中文分词的难点。 中文分词自8 0 年代初在中文信息处理领域被提出以来，许多专业学者对于这一学 科进行了深入的研究，取得了一些非常具有实用性的进展。现有的中文分词算法可以归 纳为三个大类：基于知识的分词方法、基于统计的分词方法和基于字符串匹配的分词方 法。以字符串匹配为主的方法，也称为机械分词方法。机械分词方法按照扫描方向的不 同，可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大匹配 和最小匹配；按照是否与词性标注过程相结合，可以分为单纯分词方法和分词与标注

22、相 结合的一体化方法1 2 外。 目前，在中文分词领域占据主流地位的是机械分词方法，经常使用正向最大匹配法、 逆向最大匹配法和最少切分的方法。这些方法实现比较简单，实用性比较强，但是最大 的缺点是词典的完备性不容易保障，总有一定比例的词汇是在词典之外。随着学者的深 入研究，近些年也出现了一些改进的分词方法，如李振星等提出的全二分最大匹配快速 分词算法【3 0 1 ，费红晓等提出的基于H a s h 结构的机械统计分词【3 1 1 等。国内国外也有一些 已经实现的中文分词系统，如北京航空航天大学设计实现的C D W S 系统，清华大学研 制开发的S E G 系统和S E G T A G 系统，中

23、国科学院计算技术研究所研制的I C T C L A S 系 统，微软研究院自然语言组研制的通用型多国语言处理平台N L P W i n 等等。 2 2 2 去除停用词 在语言学里，文本的主要思想是由名词、动词、形容词等实词实际表达的，至于其 7 2 文本分类相关技术 硕士论文 他的些词，在文本分类领域称为停用词( S t o pW o r d ) 。文本分类领域中的停用词，是指 在文本中实际意义不是很大，但是出现频率却比较高的词，一般来说是指副词、虚词、 介词、语气词等，也可能是一些对分类没有任何意义的词。总的来说，停用词包含两类 词，下面举例说明： ( 1 ) 虽然是名词、动词等实词，但是在

24、所有中文文本中均频繁出现，这样的词对于 区分类别没有任何含义，比如说“人民“ 、“中国“ 等等，这些词在绝大多数的文本中均 有出现，对于文本的类别确定没有任何贡献，这类词属于停用词。 ( 2 ) 代词、助词、介词、语气词、连接用语等，比如“我们“ 、“应该、“在“ 、“哎 呀“ 、“总的来说”、“言而总之”等等，这些词与类别没有任何联系，去除这些词，有利 于统计出对类别有用的主词。 停用词的集合叫做停用词表，整理停用词表之前一直由人工完成，需要凭借经验确 定停用词表，近年来，也出现了一些自动的停用词表整理办法，大多数依赖于训练集的 统计信息，比如顾益军等提出的基于统计原理的停用词自动抽取方法【

25、3 2 1 ，崔彩信提出的 基于统计和语言学结合的停用词选取方法【3 3 】等等，这些方法的出现在某种程度上减小了 因停用词导致的分类误差。 2 3 文本表示模型 文本是一种具有丰富内涵的自然语言，人能够读懂文本，是因为人脑接收到语言后 能够对语言的内容产生模糊的概念，而计算机并没有这种能力，所以必须要将文本处理 成计算机易于处理的形式，也就是文本的表示模型，常用的有布尔逻辑模型【3 4 ( B o o l e a n R e t r i e v a lM o d e l ，B R M ) 、向量空间模型( V e c t o rS p a c eM o d e l ，V S M ) 等。目前

26、效果比较好的 表示模型是向量空间模型。 这些文本表示模型基本上都以特征项为基础，这里的特征项可以是字、词甚至是句 子或是更大的单位，但在实际操作上，目前普遍认为词是比较好的特征选择，较其他形 式的特征有明显的优势。但是，对于特征项的处理，几种不同的表示模型又有自己的特 点。 2 3 1 布尔逻辑模型 布尔逻辑模型又叫布尔模型，布尔模型中，文本中的特征项权重有两种取值，取值 规则举例说明： 假设特征项集合为毛，乞，岛，吒，现有文本D ，布尔模型将文本看作是一个厅维向 量D = “，t 2 ，t 3 ，乙) ，其中第f 项的取值与特征项岛是否在D 中有关，如果t 在D 中， 则取值为l ，如果t

27、不在D 中，N t , 取值为0 。 可以看出，布尔模型最大的优点是机制简单，易于实现，缺点是无法体现出某个特 8 硕士论文中文文本分类算法研究 征项对于该文本的关键程度，也就是说，某个文本中的特征项都处于同样的地位，没有 体现出主次的区别。 2 3 2 向量空间模型 向量空间模型是以布尔模型为基础改进的一种表示模型，是由GS a l t o n 和M M c G i l l 在1 9 8 3 年提出来的【3 5 1 。它的基本思想是使用向量空间来表示文本，每一个特征 项都视为独立的一维，举例说明： 现有文本D ，特征项集合为毛，乞，岛9 o oo o0 9 吒，向量空间模型将文本看作是一个玎

28、维向 i ：O = ( ，w 2 ，w 3 ，) ，其中第f 项的取值为相应的特征项恕的权重，那么D 就可以 看作是一个n 维向量。 向量空间模型的提出在文本分类学界引发了非常大的热潮，因为向量空间模型第一 次把模糊抽象的语义用空间几何的方式表现了出来并进行了量化，我们可以通过几何方 法来对文本进行处理；另外，转化为向量的形式也便于计算两个不同的文本的相似度， 我们可以通过计算欧氏距离或是夹角余弦来计算相似度，大大简化了相似度的计算方 法。 随着向量空间模型的引入，新的问题也随之而来，那就是如何计算特征项的权重， 特征项的权重计算方法直接影响到了分类的效果，目前比较常用的权重计算方法有布尔 函

29、数、频度函数、开根号函数、对数函数、熵函数及T F I D F 函数等【3 6 】，其中T F I D F ( T e r m F r e q u e n c y I n v e r s eD o c u m e n tF r e q u e n c y ，词频- 逆向文档频率) 算法是目前占主流的权重计 算方法，它具有计算方法相对容易、准确率和召回率较高等优点。 T F - I D F 是由传统的权重计算方法T F ( T e r mF r e q u e n c y ，词频) 方法和I D F ( I n v e r s e D o c u m e n tF r e q u e n c y

30、 ，逆向文档频率) 方法结合而成，由GS a l t o n 等在1 9 9 8 年首次提出 3 7 】。其中T F 表示特征项k 在一个文档D 中的出现频率，I D F 表述特征项k 在文档集合 中的分布。T F I D F 的主要思想是：如果在某一个文档中某个特征项出现的频率比较高， 那么T F 值就比较高，这个特征项就应有较大的权值；如果在整个文档集合中包含某一 特征项的文档越少，那么I D F 值就越大，说明该特征项对类别的判定起积极作用，权值 也应该越大。 T F I D F 的计算公式如式2 1 ，2 2 所示【37 J ： 坝= l o g ( N n k + 0 0 1 ) (

31、 2 1 ) T F I D F ( d f ，七) = T F ( d J ，后) I D F ( k ) = T F ( d 。，后) l o g ( N n k + 0 0 1 ) ( 2 2 ) 其中k 是指某一个特征项，谚是指文档集合中第f 个文档，在式2 1 中，是指文 档集合的文档总数，魄是指包含特征项k 的文档数，式2 2 中的盯( 谚，k ) 是指文档Z 中 出现特征项k 的次数。一般来说，我们使用T F I D F 的归一化形式，如式2 3 所示： 9 2 文本分类相关技术 T F I D F ( d , ，后) = 其中M 是指文档集合中的文档数量。 2 4 文本特征约简

32、 模式识别是以特征为基础的，这些特征都是通过对研究对象的直接或间接观 的，很多情况下，获取的特征是人们可能观察到的特征集合，这个特征集合中有很多特 征都与待解决分类问题关系并不紧密，这些特征在后续的分类器设计中可能影响分类器 的性能；另一方面，虽然有一些特征项与分类问题关系紧密，但是特征过多会导致计算 量巨大，推广能力较差，甚至出现病态矩阵等问题而无法进行计算。 以文本为例，前文已经提到，文本分类目前公认的较优的特征项选择方案是以词为 单位，自然语言文本的特征是由词构成的序列化集合，也就决定了在文本中词汇量是非 常巨大的，直接反映在文本上的结果就是文本特征空间的高维性和向量空间的稀疏性。 一般

33、来说，如果不做任何操作，文本表示模型将会达到几万维甚至几十万维，这样复杂 的维度结构是目前任何分类算法都难以处理的，会导致时间和空间开销巨大，分类精度 低等问题，而中文文本在向量空间问题上比起英文来更为复杂，具体表现为词性更加灵 活、特征维数更大、稀疏性更强等【3 8 】。为解决这个问题，必须要对文本向量模型进行维 数约简处理，一般来说，维数约简有两种方法，特征提取和特征选择。 特征提取，是指通过一些数学运算方法从一组已有的特征中得到一组新特征。从集 合的角度来看，特征提取应符合如下定义：现有特征集合D ，寻找一种数学计算方法厂， 计算出一个新的特征集合D ，D 与D 没有相互包含关系。目前常

34、见的特征提取算法有 L S I 3 9 ( L a t e n tS e m a n t i cI n d e x i n g ，潜在语义索引) 、非线性流形学A - - - J 4 0 l 等。 特征选择，是指用计算的方法从一组已有的特征中选择一部分特征进行分类。从集 合的角度来看，特征选择应符合如下定义：现有特征集合D ，寻找一种数学计算方法厂， 得到一个新的特征集合D ，使得D D 。从实现过程来看，特征选择实现过程简单且 效果较好，是目前的主流方法，目前常用的特征选择方法有文档频率、信息增益、互信 息、z ：统计等，本文将在第4 章对特征选择方法进行详细阐述。 2 5 文本分类方法 文

35、本分类是模式分类的领域应用，具体做法是选择一个分类器模型，用已标记类别 的文本训练集合来训练一个分类器，然后用这个分类器对未标记类别的文本进行类别判 定。构建分类器作为文本分类的关键内容，一直是文本分类领域研究的前沿和热点。作 为模式识别的一个重要分支，基于统计和机器学习的方法已经成为文本分类的主流方 l O 硕士论文 中文文本分类算法研究 法，并且还在不断发展。比较常见的文本分类器有：朴素贝叶斯算法，K N N 分类算法， 决策树算法，神经网络，支持向量机等。 下面对这几种常见的分类器模型做一扼要介绍。 2 5 1 朴素贝叶斯 贝叶斯方法是统计模式识别中的一种基本方法【1 0 】，是一种较为

36、简单的线性分类器。 用这种方法进行分类时要求满足以下两个条件：( 1 ) 各类别总体的概率分布是已知的；( 2 ) 要决策的类别数是一定的。因此，贝叶斯方法在文本分类中应用较为普遍。朴素贝叶斯 ( N a f v eB a y e s ) 是一类特别的贝叶斯方法，假设d 为文本集合中的任意一个文档，特征集 合为d = t 。, t 2 ，岛，乙) ，文档类别集合为C = q ，C 2 ，c 3 ，c k ) ，它基于如下假设：文本 中的每一个特征项都是条件独立的，也即满足式2 4 。 P ( ，l ，t e ，乙lq ) - - II P ( 0Iq )( 2 4 ) 贝叶斯分类方法原理是基于

37、先验概率、后验概率、条件概率和贝叶斯公式的，假设 目标判定类别为，由贝叶斯公式，有： 气= a r g m a x c , 。c 攀背a r g m a x q 以，l f 2 ，州C 1 ) P ( C f ) ( 2 - 5 ) 由式2 4 和2 5 可以得出朴素贝叶斯的类别判别公式： = a r g m a x q E c _ P ( c ，) II P 心lC j ) ( 2 6 ) 由于P ( e ) 是已知的，所以看出，朴素贝叶斯方法的关键就是估算尸O ，I q ) 。目前 常用的估算模型有泊松模型等。 2 5 2K N N K N N ( KN e a r e s tN e i

38、g h b o r s ，K 最近邻) 算法是一种历史悠久的分类算法，已经有四 十多年的历史，它的基本思想是：对于待分类文本，计算出在已标记训练文本集合中与 该文本最相似( 最近) 的K 个文本，根据这K 个文本的已标记类别来确定待分类文本的类 别。目前较普遍的K N N 算法均是基于向量空间模型的，算法的具体步骤如下【4 1 】： ( 1 ) 根据特征集合，将待分类文本d 映射为一个n 维向量； ( 2 ) 计算出在训练集S 中与待分类文本最相似的K 个文本，也就是它的K 个邻居； ( 3 ) 根据K 近邻，计算出待分类文本d 对于类别集合C = q ，乞，q ，) 中每一个 类别C ，的隶

39、属权重，如式2 7 ： W ( d ，q ) = s i m ( d 。，d ) q D ( d i ，q ) ( 2 7 ) 其中s i m ( d ，d ) 为相似度计算函数，妒( Z ，c ，) 为类别判定函数； 2 文本分类相关技术 硕士论文 ( 4 ) 比较各个类别的权重，将待分类样本d 分到权重最大的那个类别。 从K N N 的计算步骤可以看出，K N N 算法的关键部分是相似度计算方法和k 值的选 取，目前比较常见的相似度计算方法是夹角余弦、欧氏距离等。k 值的选取没有比较好 的办法，目前仍然靠实验、测试和经验。 。K N N 算法的分类准确性和稳定性都比较高，而且不需要训练，但

40、是对训练集的文 本数量要求比较高，而且由于要和训练集中的每一个文本进行相似度计算，所以需要较 长的分类时间。 2 5 3 决策树方法 决策树是一种基于规则的分类方法，形状像是一棵树，在对待处理数据进行决策分 类任务时是采用树的结构来完成数据分类，自上世纪6 0 年代起，在数据分类、预测等 领域得到了广泛使用。决策树方法是由一系列的节点和分支组成的，树的每一个节点都 代表某一个条件下所考虑的属性，再根据该属性取值的不同来构建该节点的分支，递归 下去就能够形成一颗决策树【4 2 】。在对待分类数据进行分类时，先从根节点开始对该数据 样本的属性进行判定，并进入相应的分支，最终到达某一个叶节点，这个叶

41、节点就代表 着该样本的分类结果。 决策树方法中的一个难点是选择比较好的属性判别方法，使用好的属性判别方法， 可以加快决策树的生长速度，而且产生的决策树无论是结构还是分类准确度都比较好， 规则信息利用率也比较高；决策树方法的另一个难点是对于决策树的简化，如果决策树 模型构造得过于复杂，那么将影响用户对于决策过程的理解程度，使得决策树的性能下 降，简化决策树的方法较多，如预剪枝、后剪枝等【4 引。 决策树方法由于结构简单，易于理解，并且不需要其他的数据进行训练，所以比较 常用，实际效果也比较好，目前常见的方法有I D 3 、C 4 5 m l 等。 2 5 4 人工神经网络 人工神经网络( A r

42、 t i f i c i a lN e u r a lN e t w o r k s ，A N N ) ，简称为神经网络( N e u r a lN e t w o r k s ， M 町，由M c C u l l o c h 在1 9 4 3 年提出，是指用大量的简单计算单元( 神经元) 通过一定 的组织方式构成的非线性系统，它在一定程度上模仿了人脑的神经系统的信息、存储、 处理及检索功能，因而具有学习、记忆和计算等处理功能。神经网络具有如下特点：具 有非线性映射能力，不需要精确的数学模型，容易实现并行计算，易于软硬件实现，等 篁 4 5 1 寸 。 神经网络种类很多，在文本分类领域目前应用

43、较为广泛的种类是前馈式神经网络， 前馈式神经网络是指拓扑结构为有向无环图的神经网络，又叫多层感知器神经网络，它 具有从训练数据中学习任意复杂的非线性映射的能力，也包括实现复杂的非线性分类判 别函数，从模式识别角度来看，多层感知器方法可以看作是一种通用的非线性分类器设 1 2 研究 图2 2 多层感知器网络 人工神经网络已经被成功用于文本分类领域，如唐云等提出的结合粗糙集和神经网 络的文本分类算法1 4 7 1 、王燕霞等提出的基于级联神经网络和S V D 的文本分类方法【4 8 1 等。 人工神经网络的文本分类精度一般都比较高，但是难以解决计算复杂的问题，目前还是 缺少快速、高效的分类方法。

44、2 5 5 支持向量机 支持向量机( 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 等于2 0 世纪9 0 年代中期首次提出，最初是用于解决二分类问题。支 持向量机的目标是在向量空间模型的基础上，寻找一个可以将训练集合中的数据分开的 超平面，该超平面要求与离超平面最近的向量( 也就是所谓的支持向量) 之间的距离最 大，简言之，支持向量机的目标是寻找一个最优超平面来对数据集进行分类。 支持向量机在学习精度和泛化能力之间找到了一个平衡点，获得了比较好的推广能 力。自其被提出以来，就获

45、得了学者和研究工作者们的广泛关注，被认为是继神经网络 之后的新一研究热点，并将大大推动机器学习和模式识别的发展。目前，支持向量机已 经被应用于目标识别、人脸识别、音频识别、文本分类等领域，并且被认为是文本分类 领域最好的算法。本文主要工作之一也是围绕支持向量机出发，支持向量机相关理解将 于后续章节讲述。 2 6 多分类问题 有一些分类算法是基于二分类问题提出的，如支持向量机、决策树等，但是在实际 应用中，很多时候都会面对多类的分类问题，以文本分类为例，在大部分情况下都是多 分类问题。 1 3 2 文本分类相关技术硕士论文 在解决多类分类的问题上，目前有两种思路：1 ) 把多类分类问题分解为多个

46、二分 类问题；2 ) 直接设计多类分类器。对于支持向量机等二分类器而言，目前大多数研究 工作都应用于第一种思路，就是用多个二分类器联合而成一个多分类器。目前常用的二 分类器构建多分类器的方式是以下四种： ( 1 ) 一对多( O n e V e r s u s R e s t ，简称1 - v - r ) 在一对多多类分类模型中，如果类别集合中类别数为，则需构造个分类器， 第i ( i ) 个分类器把第f 个类认为是正例，其他的所有类别认为是负例，再针对各个分 类器的决策函数值来最后进行类别判决，以N = 4 为例，分类模型如图2 3 所示： 图2 3 一对多多分类模型 ( 2 ) 一对- -

47、 ( O n e V e r s u s O n e ，简称1 - v 一1 ) 在一对一多类分类模型中，如果类别集合中类别数为，则需构造N ( N 一1 ) 2 个 分类器，每一个分类器都实现类中的两类区分，最后根据各个分类器的分类结果进 行投票，根据投票结果来判定类别，仍然以N = 4 为例，分类模型如图2 4 所示： 1 4 图2 4 一对一多分类模型 ( 3 ) 有向无环图 在有向无环图多分类模型中，分类器构建方式与一对一模型相似，也是每一个分类 图2 。5 有向无环图多分类模型 ( 4 ) - - 叉树 二叉树多分类模型与有向无环图的分类模式相似，都是通过树来建立模型，不同的 是，二

48、叉树模型是先把类别集合中的类别分为两个子类，在下一轮再将每个子类继续一 分为二，循环下去直到分出类别。二叉树模型需构建N 1 个分类器，仍然以N = 4 为例， 分类模型如图2 6 所示： 2 7 分类评价方法 图2 6 二叉树多分类模型 分类效果评价是分类系统设计过程的最后阶段，对分类结果的评价，主要针对其有 效性、时间复杂度、空间复杂度三个角度来评价。其中有效性评价是最关键的角度，所 谓评价有效性，是指用量化的方法衡量分类器正确分类的能力。在文本分类领域，目前 常用的分类评价准则是准确率( P r e c i s i o n ) 和召回率( R e c a l l ) 。 文本分类中的准确

49、率，是指对于类别集合中的一个类别C ，被正确分到该类的文本 数与所有分到该类的文本数的比值，如式2 8 所示： 2 文本分类相关技术硕士论文 尸= 而a 1 0 0 口+ D ( 2 8 ) 其中，a 代表实际被分到类别C 中的文本数，b 代表被错误地分到类别C 文本数。 文本分类中的召回率，是指对于类别集合中的一个类别C ，被正确分到该类的文本 与本应分到该类的所有文本数量的比值，如式2 9 所示： R = j L 1 0 0 ( 2 9 ) a + C 其中，a 遵循式2 8 的定义，c 代表本应分到类别C 但是被错误分类的文本数。 准确率测度反应了分类系统的查准率，召回率测度反应了分类系统的查全率，但是 实际系统反映，准确率和召回率不可兼得，一般情况下甚至反应出相互矛盾的特性，为 了综合评价分类系统，有一种结合了准确率和召回率的新的评价标准，也即F l 测度， 如式2 1 0 所示： 巧= 筹 ( 2 1 0 ) 另