中文文本分类算法设计和实现

1、 毕业设计（论文）题 目 中文文本分类算法的设计与其实现电信 学院计算机 系 84班学生 丰成平学 号 2008055089 指导教师 相明 设计所在单位交通大学计算机系2013年6 月49 / 58系 （ 所 ） 计算机科学与技术 系 (所) 主任 批 准 日 期 毕业设计(论文)任务书 电信学 院 计算机 系 84 班学生 丰成平 毕业设计(论文)工作自 2013 年 2 月 21 日起至 2013 年 6 月 20 日止毕业设计(论文)进行地点： 交通大学 课题的背景、意义与培养目标 随着文本文件的增多，对其自动进行分门别类尤为重要。文本分类是指采用计算机程序对文本集按照一定的分类体系进

2、行自动分类标记。文本分类器 的设计通常包括文本的特征向量表示、文本特征向量的降维、以与文本分类器的设计与测试三个方面。本毕设论文研究文本分类器的设计与实现。通过该毕业设计，可使学生掌握文本分类器设计的基本原理与相关方法，并通过具体文本分类算法的设计与编程实现，提高学生的实际编程能力。 设计(论文)的原始数据与资料 1、文本语料库（分为训练集与测试集语料库）。 2、关于文本分类的各种文献（包括特征表示、特征降维、以与分类器设计）以与资料。 3、中科院文本分词工具(nlpir)。 4、文本分类中需要用到的各种分类方法的资料描述。 课题的主要任务 1学习文本特征向量的构建方法与常用的降维方法。 2学

3、习各种分类器的基本原理与其训练与测试方法。 3设计并编程实现文本分类器。4、对试验结果进行分析，得出各种结论。5、撰写毕业论文。6、翻译一篇关于文本分类的英文文献。 课题的基本要求(工程设计类题应有技术经济分析要求)1、程序可演示。 2、对源代码进行注释。 3、给出完整的设计文档与测试文档。 完成任务后提交的书面材料要求(图纸规格、数量，论文字数，外文翻译字数等)1、提交毕业论文 2、提交设计和实现的系统软件源程序与有关数据 3、提交外文资料翻译的中文和原文资料 主要参考文献：自然语言处理与信息检索共享平台：./?action-viewnews-itemid-103Svm(支

4、持向量机)算法：基于神经网络的中文文本分析（中原）：.doc88./p-7.htmlTF-IDF的线性图解：bbs.e3ol./blog-170225-6014.html东南大学向量降维文献：.doc88./p-6.html指导教师 相明 接受设计(论文)任务日期 2013-02-212013-06-20 学生签名：西 安 交 通 大 学毕业设计(论文)考核评议书院系(专业)班级 指导教师对学生所完成的课题为的毕业设计(论文)进行的情况，完成的质量与评分的意见：指导教师 年 月 日毕业设计(论文)评审意见书评审意见： 评阅人职称 年 月 日 毕业设计(论文)答辩结果院 系(专业) 毕业设计(论

5、文)答辩组对学生所完成的课题为 的毕业设计(论文)经过答辩,其意见为并确定成绩为 毕业设计(论文)答辩组负责人 答辩组成员 年 月 日论文题目：中文文本分类算法的设计与其实现学生：丰成平指导教师：相明摘要随着当今社会，计算机的普遍使用，出现了连绵不断的文本文件，如何对这些毫无逻辑、毫无层次的文件进行分门别类的整理，做到井井有条，层次鲜明呢？文本自动分类就是针对上述情况，采用机器，通过一定的约束条件和一些分类算法，自动的对这些文件进行遍历，从而实现分门别类。这样用机器代替人来“阅读”文章，用机器代替人来“整理”文章，不仅减轻了工作人员的负担，而且大大节省了时间，工作人员可以去做更多有意义的事情。

6、 文本分类主要有以下三个方面：第1、 文本的空间向量表示：由于计算机并不能识别真正的文本，本质上只懂得0,1，因此若要对文本进行分类，首先要让计算机能够“读懂”每篇文章，引入文本空间向量表示，将文章里面的特征词形成空间向量，通过计算向量之间的差距，来实现分门别类。第2、 文本特征的降维：由于中文词汇成千上万，那么形成的文本向量肯定也很长，计算起来会很麻烦，因此要对向量进行处理。第3、 文本分类器的设计：文本分类方法例如：KNN、朴素贝叶斯、SVM、决策树，BP神经网络，运用这些算法设计分类器，从而处理文本向量之间的关系，实现对文本的分门别类。最后，将文本分类运用于众多领域，例如：信息过滤、文档

7、管理、网络安全、电子图书整理、网络图书馆，搜索引擎，这样则不是通过关键字过滤，而是基于文本容的过滤或者是搜索，能大大提高过滤的可靠性以与搜索的准确性，无疑使文本领域的一项重大的突破关 键 词：文本向量；特征降维；分类算法；分类器设计。Title: The design and implementation of Chinese text classification algorithmName: Feng ChengpingSupervisor: Xiang MingABSTRACTWith today's society, the widespread use of computer

8、s, the continuous of the text file, how about these no logic, no level of sort, classify files on do in perfect order, hierarchy and bright?Text automatic classification is according to the above situation, using the machine, through a certain constraint condition and some classification algorithm,

9、automatic to traverse these files, so as to realize classify. So using machines instead of people to "read", to "finish", replacing workers with machines not only reduce the burden of the staff, and greatly saves time and staff to do more meaningful things.Text classification is

10、mainly has the following three aspects: First, Text space vector said: because of the computer and can't identify the real text, essentially understand only 0, 1, so if you want to categorize text, first of all, allow the computer to "read" each article, introduction of text vector spa

11、ce, said the article in the formation of key space vector, vector by calculation, the gap between to classify. Second, Text feature dimension reduction: due to the hundreds of thousands of Chinese vocabulary, then form the text vector is also very long, calculate it will be very trouble, so want to

12、deal with vector. Third,Text classifier design: text classification method for example: KNN, naive bayes, the SVM and the decision tree, BP neural network, using these design classifier algorithm, to process the text vector, the relationship between the implementation of text categorization.Finally,

13、 the text classification used in many fields, such as: information filtering, document management, network security, electronic books and network library, search engine, it is not by keyword filtering, but based on text content filter or search, can greatly improve the accuracy of the reliability of

14、 the filter and search, no doubt make a significant breakthrough in the field of textKey words: text vector; Characteristics will be; Classification algorithms; Classifier design.Key words: text vector; feature reduction; Classification algorithms; Classifier design. 目录第一章 绪论61.1、文本分类背景和意义61.2、文本分类的

15、应用领域61.2.1、Internet上面应用61.2.2、网络图书馆方面的应用71.2.3、网络安全方面71.2.4、电子方面71.3、目前国外研究现状71.4、文本分类的发展趋势展望81.5、本章小结8第二章 文本分类主要过程92.1、文本分类的过程图92.2、关于语料库102.2.1、文本分类语料库介绍102.2.2、文本分类，训练阶段的主要步骤102.2.3、文本分类，分类（测试）阶段的主要过程102.3、关于文本分词102.4、文本空间向量的形成112.4.1、VSM（Vector Space Model）112.4.2、常见的权值计算方法、布尔框架（Booolea

16、n weighting）、TF-IDF计算权值算法122.4.3、词典、用户词典、停用词词典142.5、常用的降维方法142.5.1、信息增益方法152.5.2、互信息方法162.5.3、期望交叉熵方法172.5.4、X2统计方法172.5.5、文本证据权方法182.6、本章小结18第三章 常用的文本分类方法193.1、k临近分类器193.1.1、KNN算法概述193.1.2、KNN算法用于文本分类器构造193.1.3、KNN算法用于分类203.1.4、KNN算法效果评价203.2、支持向量机分类器213.2.1、SVM算法概述213.2.

17、2、SVM构造分类器、线性可分、线性不可分、映射函数（核函数）233.2.4、SVM分类评价243.3、决策树算法分类器243.3.1、决策树概述243.3.2、决策树分类器的构造263.3.3、决策树分类器的构造273.4、朴素贝叶斯分类器273.4.1、贝叶斯算法原理273.4.2、贝叶斯分类器283.4.3、贝叶斯进行分类283.5、BP神经网络分类器293.5.1、BP神经网络原理293.5.2、BP神经网络分类器303.5.3、BP神经网络进行分类313.6、本章小结31第四章 试验结果分析统计324.1、试验结果评估指标简介32

18、4.2、使用KNN分类算法部分结果分析324.2.1、训练总篇数对分类结果的影响324.2.2、不同的K值对分类结果的影响334.2.3、降维深度对分类结果的影响354.2.4、采用不同的降维方法对试验结果的影响364.2.5、分而统计各个类别的详细信息364.3、使用SVM分类算法结果分析374.3.1、训练总篇数对分类结果的影响374.3.2、降维深度对分类结果的影响384.3.3、采用不同的降维方法对试验结果的影响394.3.4、分而统计各个类别的详细信息404.4、本章小结41总结与展望42参考文献44致45附录46第一章 绪论1.1、文本分类背景和意义互联网发展，网上电子图书（txt

19、文档、pdf文档、微小说、期刊论文等等），企业公司部文件整理，电子文档的增加，为了高效访问和使用这些文档数据，如果人为的对这些文件信息进行处理，不仅需要花费大量的时间翻阅每一篇文章，了解每篇文章的大体容，而且要付出很大的精力去统计。毕竟人的大脑工作能力有限，长期处于这种工作环境中，会造成大脑极大的负担，很可能由于一时疏忽而出现了错误，甚至信息量太过庞大，人脑不可能记录这么多类别信息，在最后评估的时候也有可能做出错误的判断。不仅耽误时间，而且不能实现分布式管理，如果由多人进行这项工作，很可能导致意见不同而导致纠纷等等。甚至同一个人，在不同的时间不同的地点，对一篇文章的分类页不尽一样，这样，很多严

20、峻的问题随之而来。文本自动分类就是针对上述情况，采用机器，通过一定的约束条件和一些分类算法，自动的对这些文件进行遍历，从而实现分门别类。这样用机器代替人来“阅读”文章，用机器代替人来“整理”文章，不仅减轻了工作人员的负担，而且大大节省了时间，这样工作人员就有更多的时间来处理其他的事情。用机器代替人来工作，这样在整理的过程中也不会出现一时疏忽而出现错误，更可以夜以继日的进行分类，一旦有新的文章进入，就可以通过机器“读取”这篇文章，然后自动的进行处理，可以带来很多的方便1.2、文本分类的应用领域1.2.1、Internet上面应用 把文本分类系统结合到搜索引擎（谷歌、百度）之类，可以大大提高搜索的

21、准确性，目前大部分搜索引擎是通过查找关键字进行匹配，用这种方法必须要遍历每篇文章，找出其中的关键字，然后统计结果输出，这种查询的精度不是很高，速度方面由于要遍历很多文章，速度当然不会很快。如用引入文本分类系统，当查询某个关键字的时候，可以自动判定与之相关的文件类别，基于容的查询，可以直接命中目标，查询速度和精度能得到有效的提升1.2.2、网络图书馆方面的应用 任何一个图书馆的馆藏资源成千上万，如果没能很好的分门别类，大量的图书便会杂乱无章，不仅浪费工作人员的时间进行整理和查询，而且读者在找寻自己想要的图书方面也会花费很大的时间。因此可以使用文本分类引擎实现电子图书的分门别类，使管理更加方便，是

22、查询更加简单。1.2.3、网络安全方面 internet的普与，人们上网浏览信息，很多是对读者有用的，但是也有不法分子将不健康的信息通过internet进行传播，不仅影响了读者的时间，更会影响读者的情绪，影响工作效率。如果将文本分类引擎引入绿色上网功能中，对用户要访问的容事先进行分析，去除没有用的垃圾信息，就可以为用户带来很多方便。目前 电信绿色上网，360绿色上网等都可以考虑引入此引擎，相信效果会更上一层楼。1.2.4、电子方面 可以自动为用户预处理，将分门别类，而且必要的时候，可以自动屏蔽一些没有用的垃圾，给用户带来了很多方便。1.3、目前国外研究现状 国外主要的研究单位：CMU、斯坦福。

23、国主要的研究单位有：复旦大学、中科院计算所等，国的方法一般是在了解国外已有分类算法或者分类方法之后，在此基础上进行创新和改进，以进一步适应中文文本分类的需求。 到目前为止，文本自动分类在国外大致经历了三个发展阶段： 预测分析阶段（1958-1964）判断文本分类是否能够真正的在现实社会中起到作用 实际运用构思阶段（1965-1974）主要进行文本分类的初步构思，形成大概的理论和框架。 开发应用阶段（1975-至今）进行实际使用和运用阶段，在电子分类、网络安全、信息过滤等方面取得较为广泛的应用。 我国文本分类的研究工作始于20世纪80年代，大体经历了可行性探讨、辅助分类系统、自动分类系统三个阶段

24、。总体来书，中文文本分类还处于在试验研究阶段，正确分类率约为60%90%，目前已经在国受到重视，相关的学术研究成果也层出不穷，相信不久以后，文本分类将涉与到中文的各个领域，发挥自己的一技之长。1.4、文本分类的发展趋势展望 只要汉语甚至语言文字依旧在使用，那么文本分类将永远有自己的重要性，而且随着文字数目的增多，文件类别的加剧，文本分类引擎将会越来越得到各界人士的关注，运用领域将会越来越广泛，重要性也会越来越高。相信在不就的将来，nternet方面、电子、网络图书馆、绿色上网安全方面，都会运用文本分类引擎以达到更好的效果，研究文本分类，必定会发展自己的独特优势，为用户带来更多的方便。1.5、本

25、章小结本章主要从文本分类的背景以与应用方面入手，提出了文本分类的研究的历史背景，以与对应的应用领域，叙述了众多文本分类的好处，通过对比国外的相关研究成果，分析国目前文本分类的现状对文本分类的前景趋势进行展望。第二章 文本分类主要过程2.1、文本分类的过程图首先把文本分类的总体流程图展示出来，主要包括对文本的处理，对处理之后向量的降维，然后对训练集测试集语料库进行仿真，文本分类过程图如图所示。开始训练集、测试集语料库输入文本采用中科院nlpir分词文本分词TF-IDF计算权值空间文本向量降维方法向量降维分类方法：svm/决策树.进行文本分类Weka、C+、matlab仿真最终结果 图2-1 文本

26、分类过程图2.2、关于语料库2.2.1、文本分类语料库介绍本次试验中采用复旦大学语料库，分为训练集与测试集，训练集20个类别，共计9804篇，测试集20个类别，共计9833篇。由于计算时间的关系，如果全部语料库用来测试，那么逐篇文章遍历，生成空间向量，需要太长的时间，因此试验过程中为了研究某些统计特征，只是从语料库中随机抽取样本进行测试，分析最后结果。 复旦大学语料库提供的预料有20个类别，但是各个类别里面的文章数差别太大，有的累里面有一千多篇，但是有的类别只有几十篇，此处从中抽取样本数较多的10个类别进行分析研究，10个类别分别是：环境、计算机、经济、军事、历史、农业、太空、艺术、运动、政治

27、，在实验过程中都是随机选取其中的文章进行试验，没有人为的对实验结果进行定向干涉，保证了结果的随机性。也就是说，在试验的过程中，尽可能减少人的主观性思维，尽量避免实验者的主观因素去影响试验结果，力求结果的可靠性、可认证性。2.2.2、文本分类，训练阶段的主要步骤（1） 定义类别集合C=C1，C2，···Ci···Cm，在本次实验中一共有10个类别，那么m的值为10，分别是：环境、计算机、经济、军事、历史、农业、太空、艺术、运动、政治。（2） 文本集合Cm=S1,S2,···Sj··

28、83;Sn,Sn表示某个类别里面的一片文章，每篇文章Sn都有所属的类别Cm，例如Sn属于环境类，那么就有标识。（3） 对于训练集中的所有文本，对其进行处理，形成空间文本向量，然后根据该特征向量和该文本所属的类别，依据特定训练分类规则，形成分类器。这样分类器就形成了2.2.3、文本分类，分类（测试）阶段的主要过程（1） 对于某个等待分类的文本，先对该文本进行分词形成空间向量，然后根据分类器采用的规则判断该文本属于训练集中的哪一类。（2） 然后输出所有分类的文本的类别，并对结果进行统计。2.3、关于文本分词对于随意给出的一篇文章，或者一则短消息，要获取消息或者文章的容，须从中提取关键词语，因此使用

29、中科院华平教授研发的中文分词工具：NLPIR（原名:ICTCLAS）汉语分词工具，把文章分词.关于nlpir：NLPIR汉语分词系统,主要功能包括中文分词；词性标注；命名实体识别；用户词典功能；新增微博分词、新词发现与关键词提取；华平博士先后倾力打造十余年。为何要对文章进行分词，词是构成文章的基础，计算机去识别一篇文章就是需要先对文章进行分词，进而将词表示成空间向量的形式，这样才能进行计算，因此分词的好坏直接影响到最后的分类结果的好坏，一个好的分词工具当然是词分的越细越好，词语提取的越准确越好，nlpir的分词效果，较一般的分词工具分的更准确，更权威。如下图是对语料库里面的一篇文章的分词处理结

30、果： 图2-2 一篇文章的分词展示 有了分词工具之后，接下来就是怎样将一篇文章形成一个空间向量。2.4、文本空间向量的形成2.4.1、VSM（Vector Space Model） 俗称向量空间模型。根据一篇文章中词或者字出现的频率，以与权值，将文本形象的转化为一个很长维的向量，向量的总维数长度与字典里面的词字个数一样，如果某个词在该文章中并没有出现，那么相应的此处的值为0，如果出现次数比较多，权重比较高，则为：1,2,3（实际计算形成的权值一般是实数，很少是整数）.等等。 这样就把文本转化为计算机可以处理计算的向量形式。然后通过比较向量之间的相似度，或者通过分析向量之间的差别来进行文本的识别

31、。 最后，一篇文章就被转化为一个n维向量空间中的一个点，n可以理解为词典中包括的总词/短语数。用数学公式表示为：N=（W1,W2,W3,W4.···Wi···Wn），其中Wi为某个词/短语的权值。 说明：、向量是有顺序的，如果在词典中未出现，那么该位标记为0或者在该向量形成的时候，前面做标记位进行识别。 、词典是包含了所有语料库中出现的词根/词/短语 ，没有重复字词。 、即使是一篇很短的文章，也可能形成维数很长的向量。2.4.2、常见的权值计算方法、布尔框架（Booolean weighting） 对于某个特征词i，布尔

32、框架对其权值的定义为： 权值定义为：1 特征词i出现在文档k中 （2-1） Wik =0 特征词i未出现在文档k中 分析：此种方法只是显示了特征词是否存在，但是出现的次数不能得到很好的统计，当然对分类结果也不能达到很好的要求，因此在实验过程中，不选择此种框架，而采用另外一种框架TF-IDF框架、TF-IDF计算权值算法TF-IDF（term frequencyinverse document frequency），TF-IDF是一种统计方法，即根据某个词/短语在自身文章中出现的比例，以与该短语在总体语料库中出现的比例，来计算该词/短语的权值，权值越高，证明该词越能表示这篇文章的类

33、别，相反权值越低，该词对文章的贡献度越小，用这种方法来评估一个字词对于一篇文章或一个语料库的重要程度。词频与反文档频率的大体思想是：一个字词对这篇文章的重要性随着它在本篇文章中出现的次数正比例增加，但是相对整体语料库而言，如果在整体语料库中出现的次数太多，该字词的表征作用会呈反比例下降。TF（词频）计算公式（2-2）其中Mi表示某个词在该篇文中中出现的次数，Q表示文中出现的总词数，一样的词第二次出现则Q不会叠加，Q统计的总次数，不存在重复。举例1：在一篇科普类文章中，地球在文中出现次数为7,文章中的总词数是1000，那么地球这个词的词频为：TF=3/1000=0.7% IDF(反文档频率)计算

34、公式（2-3） 其中D表示语料库文章总数，Si表示在D的样本中，包含词i的文章篇数。 举例2：在总语料库中，含有地球的文章数量为100，总文章数为100000，那么地球这个词的反文档频率为：IDF=lg(100000/100)=3 。TF-IDF最后得到i的权值公式为（2-4） 举例3：综合例1，例2，那么地球这个词，在语料库中的权值为：TF*IDF=0.007*3=0.021TF-IDF计算权值的好处分析 首先，如果不使用此方法，例如地球的公转，“地球” 、“的”、 “公转” 在文章中出现的次数分别为7、100、5，如果只是统计词频，假设文章有一千词，那么三个词的词频分别为：0.007 ，0

35、.100 ,0.005 显然，“的”的词频很大，三个词总共的贡献度为0.112，但是“的”占了绝大部分，显然这个词不能表示本文的特征，反之，地球与公转这两个词能表征文本大意，但是所占的比例却相当的小。 其次，引入IDF，此问题就能得到很好的解释：如上例子，还是以“地球” 、“的”、 “公转”为例，出现次数如上所示。语料库含有的总文章数为：105 ，含有“地球”文章数为102，含有“的”的文章数为105，含有“公转”的文章数为103，那么根据DF-IDF计算公式，计算得出 W（地球）=0.007*lg(105/102)=0.021 W（的）=0.100*lg(105/105)=0 W(公转)=0

36、.005*lg(105/103)=0.010这样计算，得出的结果“的”的权值为0，而地球和公转分别占了0.021和0.010，这样的结果符合正常的逻辑情况。2.4.3、词典、用户词典在对语料库中所有的文章进行分词之后，势必会有很多的字以与词语，每当产生一个新的词语的时候，相应的用户词典就会把这个词加入进去，每当有新词进入的时候，词典的长度就会加一，这样对于训练集，训练集越大形成的词典也就越大，相应的对各篇文章的区分度会更好，有词典的存在，每当出现新词的时候，用户也不用担心，加入词典就可以。最终的词典长度和空间向量的长度是一样的。、停用词词典停用词，顾名思义，就是文本

37、分类过程中不需要用到的词语，这些词语千篇一律，不仅对文章没有表征作用，而且会增加处理的复杂度，如果把这些词加入计算，会影响计算的时间，因此专门设计一个停用词词典，对这些词不加入计算，停用词里面的容，见后面附录.2.5、常用的降维方法当一个空间向量形成之后，由于词典词数肯定是成千上万，可想而知向量的长度肯定也是相当的长，在这样长的向量之间运用分类算法，效果一般不是很好，计算的时间可能也会相当的长，因此要用一些算法，对这些空间向量进行一定的处理，以减少向量的长度。常用的降维方法有：信息增益、互信息、期望交叉熵、X2统计、文本证据权等方法。 当然对于某些算法，不使用降维直接对空间向量进行计算，效果也

38、不一定会很差，但是对于绝大多数算法，运用降维之后处理还是方便一些。2.5.1、信息增益方法在介绍信息增益方法之前，首先引入一个熵的概念，对于一些互斥事件，如果所有事件发生的概率之和为1，那么这个事件相应的就有一个对应的熵，熵的计算公式如下：（2-5）称为事件X的的信息熵。比如一个很简单的例子，X表示随机抛出一枚硬币，出现的结果的概率，由于抛出硬币的可能性有两种：正面朝上、反面朝上（很少有可能会竖着站立不到，除非是人为因素或者是地表柔软，硬币扎入地中，这些意外情况不记入其中）最后随机出现的两种结果概率都是1/2,那么对于抛硬币这个等概率事件，X的信息熵计算结果为： H（X）=-0.5*(-1)-

39、0.5*(-1)=0.5*2=1又如X表示从盒子里面有四种颜色的求，红、黄、蓝、绿各一个，现在随机从里面抽出一个，那么各种结果出现的概率为1/4。计算得到信息熵为： H（X）=-4*0.25*log2(0.25)=2如果有八种颜色的球，同样的方法计算最后得到的信息熵为： H（X）=-8*0.125*log2(0.125)=3可见最后可能出现的结果越多，相应的事件X的信息熵就会更大，因此信息熵是衡量某个事件结果发生的稳定性的度量，信息熵越小证明该事件越趋于稳定，信息熵越大，则该事件越显得杂乱无章。 在文本分类中，信息增益的使用还是较为普遍的，信息增益的方法的大体思想是：首先计算含有该特征词时的信

40、息熵，然后减去不含该词的信息熵，以此用来计算特征词t 的权重，在最后得到的结果中，每个词都有一个对应的权重，权重的值由大到小进行排列，这样就可以随意选取前面较大权重的词列入计算，这就是信息增益降维的大体思想。一篇文章包含的词可能有一千个，我们可以选取其中的前500个进行试验，也可以选取100个 甚至10个进行试验，只是最后得到的结果会有差异，对于结果如何，在后面的试验中会有详细的数据对比。 信息t的信息增益的公式为：（2-6） 注：其中P(Ci)表示某个文章属于Ci的概率；P(t)表示包含有特征词t的文本出现的概率；则表示不包含特征词t的文本出现的概率；P(Ci|t)表示包含特征词时属于类别C

41、i的概率，反之为不包括特征词t时属于Ci的概率。 信息增益的好处是，通过比较含有该词、不含该词的时候对文章类别、语料库全局的影响来评判一个词的重要性，这种方法不是仅仅局限在某一篇文章之中，也不是局限在某一个类别之中，而是把文章、类别、总体语料库综合起来进行评判，以达到很好的统计效果。这样一个词的信息增益越大，在后期设计分类器或者进行分类时，该词就更重要，反之信息增益越小，那么该词的重要性就比较低，去除那些信息增益非常低的词之后，剩下的词相对就比较少了，对提升算法的速度有很大的帮助。2.5.2、互信息方法互信息原本是信息论中的一个概念，主要表示两个事物之间的相关程度，把互信息应用到文本分类中，则

42、很明显可知，互信息表示的是特征词t与文本类别C之间的关系，例如某个特征词t对类别C1的表征作用比较高，但是对其他类别的表征作用比较低，那么这个词相对于该类别的互信息就比较高。互信息的计算公式如下：（2-7）注：P（tCi）为特征词t与类别Ci同时出现，其余的概率统计与之前的一样，此公式后面的推到用到了贝叶斯算法的公式，关于贝叶斯算法，后面将会详细讲述。2.5.3、期望交叉熵方法期望交叉熵方法与别的方法不同之处在于，期望交叉熵方法在计算计算时不考虑特征词t不出现的情况，期望交叉熵的方法反应了文本类别的概率分布，以与在计算入特征词t情况下各个类别之间的概率分布。期望交叉熵的算法公式为：（2-8）用

43、这种算法 当某个特征词与类别关系较大时，得到的权值结果自然会比较大，当特征词与类别关系较小时，得到的结果会比较小，进行降维的时候也是采取取大去小的原则进行计算。2.5.4、X2统计方法X2统计方法表示特征词t与文本类别C的相关度，顾名思义，当然是相关度越高，该特征词对某个类别的表征作用越明显，反之表征作用越低。X2统计方法的计算公式如下：（2-9）注：A表示特征词t与类Ci同时出现的次数，D表示二者同时不出现的次数B表示t出现但是且不出现的次数，C表示满足（t不出现且Ci出现）的次数，N表示语料库中的总文章数。由上式分析得出，由于分母都是出现的次数，当然次数不可能为负数，所以分母和乘积为正数，

44、而分子N为正整数，所以决定t的权值的正负就取决于（AD-BC）值得正负，当AD>BC时，权值为正，可以称之为正相关，权值越大时，当特征词t出现时，某个类别很可能就会出现反之当AD<BC时，权值为负数，称之为负相关，权值绝对值越大时，当特征词t出现时，某个类别很可能就不出现。2.5.5、文本证据权方法文本证据权方法是通过比较文本出现的概率和给定某个特征词t时，某个类的条件概率之间的差别，进而进行计算，得到相应的权值 文本证据权的计算公式如下：（2-10）注：Od表示的是事件发生的概率比上事件不发生的概率所得的值，特征词和类别的相关度记作：P(Ci|t) 相关度越大，而且相应类别出现的

45、概率越小，则计算得出的结果权值就越大，表示该词对某个类的表征作用就越强，相反如果相关度越小，则表示,类别出现的概率越大，则表示该词对某个类的表征作用就越弱，在实行向量降维的时候，就要考虑把这些表征能力比较弱的词的向量可以略去不管。2.6、本章小结本章首先介绍了文本分类的总体过程，然后分而叙述各个比较重要的部分，讲述了语料库的大概结构，讲解了如何将一篇毫无逻辑的纯文本文章形成为空间向量，然后如何对向量进行处理，使其更简易计算。讲述了词典、停用词词典，讲述了对向量维数的处理，第三章就是针对前面的已经做好的容设计分类器，当然会提到各种常用的分类方法。第三章 常用的文本分类方法前面部分已经介绍了文本分

46、类的大体框架，也叙述了如何将文本形成可以处理的向量形式，本章则主要针对各种分类器的构造进行阐述，讲解各种分类器的形成原理以与形成方法。常用的文本分类算法有：决策树算法、朴素贝叶斯算法、K临近算法、支持向量机算法、BP神经网络算法等等。3.1、k临近分类器3.1.1、KNN算法概述KNN算法（即K-邻近算法），这种算法可以说是最简单而又普遍的算法，通过寻找相邻的点，然后计算各个点和所要决策的点之间的距离，从中找出距离最近的一个点，那么要判断的点就属于那个点所在的类别。如图所示： 图3-1 KNN临近点图示 寻找与所要查询点距离最近的点，找到最近的点之后，那么所要查询的点就跟着那个最近的点走，根据

47、那个最近点所属的类别而判定查询点所属的类别。3.1.2、KNN算法用于文本分类器构造 用KNN算法用于文本分类的大致原理如下： 首先，从训练集中选择K个与所要查询的点最相近的点与所要查询的点（文本已经形成了空间向量）进行计算，计算相似度公式为：（3-1） 其中K的值是不固定的，它随着语料库中总文章数而改变，文章数多的时候K会适当增大一些，在实际匹配计算的过程中，会根据结果调节K的取值，带有一定的启发性质，比较能够适应现在社会的自动化学习。3.1.3、KNN算法用于分类 上述是K个文本，那么这K个文本肯定有各自所属的类别，接下来关键部分就是计算每个类别与某个文本S之间的权值，例如本试验中有10个

48、类别，那么计算的时候，就应该分别计算这10个类别与该文本S的权值，然后选择最后权值结果最大的类别，将该文本归入其中权值的计算公式为：（3-2）上式中，di表示的是K个文本中的某个文本形成的向量。y(di,cj)是判断di这个文本是否属于类别，属于类别，则其值为1，反之其值为0。Cj,Sim是计算二者的相似度，相似度越高，那么结果权值越大，最后比较计算得出的结果就可以得出该文本所属的类别。由于此种方法简单容易理解，不会像决策树那样有太多的分支，太多判断条件的先后不同，本次试验采用了此种方法进行仿真，试验结果见第四章。3.1.4、KNN算法效果评价 KNN算法，简单，容易被大多数人接受，但是由于其

49、简单的系统结构，对分类效果并不是非常可观。例如在某个语料库中，可能其中某个类别里面的文章数比较多，而另外一个类别里面的文章数很少，那么在选择的时候，肯定文章数比较多的文章靠近S的点会比较多，这样就相当于定向的将结果趋近于文章数比较多的那个类别，因此，在使用KNN分类算法时，训练集语料库中的各个类别的文本数最好比较平均为好，这也是为什么本人在试验的时候，不直接把复旦语料库直接拿来应用，而是经过自己处理进行使用，就是为了保证结果的合理性。 看过复旦语料库的相信都知道，该语料库含有20个类别，其中9个类别文章数非常多，有上千篇，其中一个类别中性，将近100篇，其余10个类别文章数非常少，甚至还有30

50、、40篇文章的类别，因此在试验过程中我去掉的了那文章数非常少的10个类别，用另外10个类别进行试验。3.2、支持向量机分类器3.2.1、SVM算法概述SVM算法，即支持向量机算法，是目前使用较为普遍的文本分类算法，这种算法由于其分割、分类时使用空间向量，或者空间超平面，因此这种算法针对维数较长的向量处理效果会比较好。支持向量机的数学描述： w·x-b=0 表示一个超平面的公式，其中x是超平面上的点,w表示垂直平面的一个向量，b的取值可以理解为是位移不断的改变b的取值，可以在脑海中构思，会形成很多个平行于原本平面的平面，然后我们从这些平面中选取2个平面：这两个平面到原本平面的距离是相等的，一个在原平面的上方，一个在下方，或一个左边一个右边，可以形象的这样进行理解，引入这个的目的是什么呢，接下来会以图结合文字的方法进行叙述。当然了上式也可以运用于线性空间，原理与之类似。当问题很复杂，需要用到高维的时候，就需要用到n-1维超平面了。3.2.2、SVM构造分类器、线性可分首先给出一个简单的分类问题，要求区分两个类别，要求用一条直线，将下图中黑色的点和白色的点分开：图3-2 多条线性划分图示图中的条件，我们可以画无数条用于分割的直线，但是这些直线中，哪一条最好，最符合要求呢？要选择哪条直线，才能使两边的类别划分的越开越好呢，当有一个新的点