《中文文本分类算法设计及其实现(45页).doc》由会员分享，可在线阅读，更多相关《中文文本分类算法设计及其实现(45页).doc（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-中文文本分类算法设计及其实现-第 37 页毕业设计（论文）题 目 中文文本分类算法的设计及其实现 电信 学院 计算机 系 84 班学生姓名 丰成平 学 号 2008055089 指导教师 相明 设计所在单位 西安交通大学计算机系 2013 年 6 月系 （ 所 ） 计算机科学与技术 系 (所) 主任 批 准 日 期 毕业设计(论文)任务书 电信学 院 计算机 系 84 班 学生 丰成平 毕业设计(论文)工作自 2013 年 2 月 21 日起至 2013 年 6 月 20 日止毕业设计(论文)进行地点： 西安交通大学 课题的背景、意义及培养目标 随着文本文件的增多，对其自动进行分门别类尤为重
2、要。文本分类是指采用计算机程序对文本集按照一定的分类体系进行自动分类标记。文本分类器 的设计通常包括文本的特征向量表示、文本特征向量的降维、以及文本分类器的设计与测试三个方面。本毕设论文研究文本分类器的设计与实现。通过该毕业设计，可使学生掌握文本分类器设计的基本原理及相关方法，并通过具体文本分类算法的设计与编程实现，提高学生的实际编程能力。 设计(论文)的原始数据与资料 1、文本语料库（分为训练集与测试集语料库）。 2、关于文本分类的各种文献（包括特征表示、特征降维、以及分类器设计）以及资料。 3、中科院文本分词工具(nlpir)。 4、文本分类中需要用到的各种分类方法的资料描述。 课题的主要
3、任务 1学习文本特征向量的构建方法及常用的降维方法。 2学习各种分类器的基本原理及其训练与测试方法。 3设计并编程实现文本分类器。 4、对试验结果进行分析，得出各种结论。 5、撰写毕业论文。 6、翻译一篇关于文本分类的英文文献。 课题的基本要求(工程设计类题应有技术经济分析要求)1、程序可演示。 2、对源代码进行注释。 3、给出完整的设计文档及测试文档。 完成任务后提交的书面材料要求(图纸规格、数量，论文字数，外文翻译字数等)1、提交毕业论文 2、提交设计和实现的系统软件源程序及有关数据 3、提交外文资料翻译的中文和原文资料 主要参考文献：自然语言处理与信息检索共享平台：http:/www.n
4、lpir.org/?action-viewnews-itemid-103Svm(支持向量机)算法：基于神经网络的中文文本分析（赵中原）：TF-IDF的线性图解：东南大学向量降维文献： 指导教师 相明 接受设计(论文)任务日期 2013-02-212013-06-20 学生签名： 西 安 交 通 大 学毕业设计(论文)考核评议书 院 系(专业) 班级 指导教师对学生 所完成的课题为 的毕业设计(论文)进行的情况，完成的质量及评分的意见： 指导教师 年 月 日毕业设计(论文)评审意见书评审意见： 评阅人 职称 年 月 日 毕业设计(论文)答辩结果 院 系(专业) 毕业设计(论文)答辩组对学生 所完
5、成的课题为 的毕业设计(论文)经过答辩,其意见为 并确定成绩为 毕业设计(论文)答辩组负责人 答辩组成员 年 月 日论文题目：中文文本分类算法的设计及其实现学生姓名：丰成平指导教师：相明 摘要随着当今社会，计算机的普遍使用，出现了连绵不断的文本文件，如何对这些毫无逻辑、毫无层次的文件进行分门别类的整理，做到井井有条，层次鲜明呢？文本自动分类就是针对上述情况，采用机器，通过一定的约束条件和一些分类算法，自动的对这些文件进行遍历，从而实现分门别类。这样用机器代替人来“阅读”文章，用机器代替人来“整理”文章，不仅减轻了工作人员的负担，而且大大节省了时间，工作人员可以去做更多有意义的事情。 文本分类主
6、要有以下三个方面：第一、 文本的空间向量表示：由于计算机并不能识别真正的文本，本质上只懂得0,1，因此若要对文本进行分类，首先要让计算机能够“读懂”每篇文章，引入文本空间向量表示，将文章里面的特征词形成空间向量，通过计算向量之间的差距，来实现分门别类。第二、 文本特征的降维：由于中文词汇成千上万，那么形成的文本向量肯定也很长，计算起来会很麻烦，因此要对向量进行处理。第三、 文本分类器的设计：文本分类方法例如：KNN、朴素贝叶斯、SVM、决策树，BP神经网络，运用这些算法设计分类器，从而处理文本向量之间的关系，实现对文本的分门别类。最后，将文本分类运用于众多领域，例如：信息过滤、文档管理、网络安
7、全、电子图书整理、网络图书馆，搜索引擎，这样则不是通过关键字过滤，而是基于文本内容的过滤或者是搜索，能大大提高过滤的可靠性以及搜索的准确性，无疑使文本领域的一项重大的突破关 键 词：文本向量；特征降维；分类算法；分类器设计。Title: The design and implementation of Chinese text classification algorithmName: Feng ChengpingSupervisor: Xiang Ming ABSTRACT With todays society, the widespread use of computers, the c
8、ontinuous 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, automat
9、ic 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 mainly has the following three
10、aspects: First, Text space vector said: because of the computer and cant 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 space, said the article in the formation of key spa
11、ce 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 deal with vector. Third,Text classifier design:
12、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, the text classification used in many fields, s
13、uch 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 the filter and search, no doubt make a signifi
14、cant 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、文本分类的应用领域61.2.1、Internet上面应用61.2.2、网络图书馆方面的应用71.2.3、
15、网络安全方面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、常见的权值计算方法122.4.2.1、布尔框架（Booolean weighting）122.4.2.2、TF-IDF计算权值算法122.4.3、词典
16、142.4.3.1、用户词典142.4.3.2、停用词词典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.2、SVM构造分类器213.2.2.1、线性可分213.2.2.2、线性不可分223.2
17、.2.3、映射函数（核函数）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、试验结果评估指标简介324.2、使用KNN分类算法部分结果分析324.2.1、训练总篇数对分类结果的影响324.
18、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文档、pdf文档、微小说、期刊论文等等），企业公司内部文件整理，电子文档的增加，为
19、了高效访问和使用这些文档数据，如果人为的对这些文件信息进行处理，不仅需要花费大量的时间翻阅每一篇文章，了解每篇文章的大体内容，而且要付出很大的精力去统计。毕竟人的大脑工作能力有限，长期处于这种工作环境中，会造成大脑极大的负担，很可能由于一时疏忽而出现了错误，甚至信息量太过庞大，人脑不可能记录这么多类别信息，在最后评估的时候也有可能做出错误的判断。不仅耽误时间，而且不能实现分布式管理，如果由多人进行这项工作，很可能导致意见不同而导致纠纷等等。甚至同一个人，在不同的时间不同的地点，对一篇文章的分类页不尽相同，这样，很多严峻的问题随之而来。文本自动分类就是针对上述情况，采用机器，通过一定的约束条件和
20、一些分类算法，自动的对这些文件进行遍历，从而实现分门别类。这样用机器代替人来“阅读”文章，用机器代替人来“整理”文章，不仅减轻了工作人员的负担，而且大大节省了时间，这样工作人员就有更多的时间来处理其他的事情。用机器代替人来工作，这样在整理的过程中也不会出现一时疏忽而出现错误，更可以夜以继日的进行分类，一旦有新的文章进入，就可以通过机器“读取”这篇文章，然后自动的进行处理，可以带来很多的方便1.2、文本分类的应用领域1.2.1、Internet上面应用 把文本分类系统结合到搜索引擎（谷歌、百度）之类，可以大大提高搜索的准确性，目前大部分搜索引擎是通过查找关键字进行匹配，用这种方法必须要遍历每篇文
21、章，找出其中的关键字，然后统计结果输出，这种查询的精度不是很高，速度方面由于要遍历很多文章，速度当然不会很快。如用引入文本分类系统，当查询某个关键字的时候，可以自动判定与之相关的文件类别，基于内容的查询，可以直接命中目标，查询速度和精度能得到有效的提升1.2.2、网络图书馆方面的应用 任何一个图书馆的馆藏资源成千上万，如果没能很好的分门别类，大量的图书便会杂乱无章，不仅浪费工作人员的时间进行整理和查询，而且读者在找寻自己想要的图书方面也会花费很大的时间。因此可以使用文本分类引擎实现电子图书的分门别类，使管理更加方便，是查询更加简单。1.2.3、网络安全方面 internet的普及，人们上网浏览
22、信息，很多是对读者有用的，但是也有不法分子将不健康的信息通过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 文本分类过程图2.2、关于语料库
26、2.2.1、文本分类语料库介绍 本次试验中采用复旦大学语料库，分为训练集与测试集，训练集20个类别，共计9804篇，测试集20个类别，共计9833篇。由于计算时间的关系，如果全部语料库用来测试，那么逐篇文章遍历，生成空间向量，需要太长的时间，因此试验过程中为了研究某些统计特征，只是从语料库中随机抽取样本进行测试，分析最后结果。 复旦大学语料库提供的预料有20个类别，但是各个类别里面的文章数差别太大，有的累里面有一千多篇，但是有的类别只有几十篇，此处从中抽取样本数较多的10个类别进行分析研究，10个类别分别是：环境、计算机、经济、军事、历史、农业、太空、艺术、运动、政治，在实验过程中都是随机选取
27、其中的文章进行试验，没有人为的对实验结果进行定向干涉，保证了结果的随机性。也就是说，在试验的过程中，尽可能减少人的主观性思维，尽量避免实验者的主观因素去影响试验结果，力求结果的可靠性、可认证性。2.2.2、文本分类，训练阶段的主要步骤（1） 定义类别集合C=C1，C2，CiCm，在本次实验中一共有10个类别，那么m的值为10，分别是：环境、计算机、经济、军事、历史、农业、太空、艺术、运动、政治。（2） 文本集合Cm=S1,S2,SjSn,Sn表示某个类别里面的一片文章，每篇文章Sn都有所属的类别Cm，例如Sn属于环境类，那么就有标识。（3） 对于训练集中的所有文本，对其进行处理，形成空间文本向
28、量，然后根据该特征向量和该文本所属的类别，依据特定训练分类规则，形成分类器。这样分类器就形成了2.2.3、文本分类，分类（测试）阶段的主要过程（1） 对于某个等待分类的文本，先对该文本进行分词形成空间向量，然后根据分类器采用的规则判断该文本属于训练集中的哪一类。（2） 然后输出所有分类的文本的类别，并对结果进行统计。2.3、关于文本分词对于随意给出的一篇文章，或者一则短消息，要获取消息或者文章的内容，须从中提取关键词语，因此使用中科院张华平教授研发的中文分词工具：NLPIR（原名:ICTCLAS）汉语分词工具，把文章分词.关于nlpir：NLPIR汉语分词系统,主要功能包括中文分词；词性标注；
29、命名实体识别；用户词典功能；新增微博分词、新词发现与关键词提取；张华平博士先后倾力打造十余年。为何要对文章进行分词，词是构成文章的基础，计算机去识别一篇文章就是需要先对文章进行分词，进而将词表示成空间向量的形式，这样才能进行计算，因此分词的好坏直接影响到最后的分类结果的好坏，一个好的分词工具当然是词分的越细越好，词语提取的越准确越好，nlpir的分词效果，较一般的分词工具分的更准确，更权威。如下图是对语料库里面的一篇文章的分词处理结果： 图2-2 一篇文章的分词展示 有了分词工具之后，接下来就是怎样将一篇文章形成一个空间向量。2.4、文本空间向量的形成2.4.1、VSM（Vector Spac
30、e Model） 俗称向量空间模型。根据一篇文章中词或者字出现的频率，以及权值，将文本形象的转化为一个很长维的向量，向量的总维数长度与字典里面的词字个数相同，如果某个词在该文章中并没有出现，那么相应的此处的值为0，如果出现次数比较多，权重比较高，则为：1,2,3（实际计算形成的权值一般是实数，很少是整数）.等等。 这样就把文本转化为计算机可以处理计算的向量形式。然后通过比较向量之间的相似度，或者通过分析向量之间的差别来进行文本的识别。 最后，一篇文章就被转化为一个n维向量空间中的一个点，n可以理解为词典中包括的总词/短语数。用数学公式表示为：N=（W1,W2,W3,W4.WiWn），其中Wi为
31、某个词/短语的权值。 说明：、向量是有顺序的，如果在词典中未出现，那么该位标记为0或者在该向量形成的时候，前面做标记位进行识别。 、词典是包含了所有语料库中出现的词根/词/短语 ，没有重复字词。 、即使是一篇很短的文章，也可能形成维数很长的向量。2.4.2、常见的权值计算方法2.4.2.1、布尔框架（Booolean weighting） 对于某个特征词i，布尔框架对其权值的定义为： 权值定义为：1 特征词i出现在文档k中 （2-1） Wik =0 特征词i未出现在文档k中 分析：此种方法只是显示了特征词是否存在，但是出现的次数不能得到很好的统计，当然对分类结果也不能达到很好的要求，因此在实验
32、过程中，不选择此种框架，而采用另外一种框架TF-IDF框架2.4.2.2、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(反文档频率)计算公式 （2-3） 其中D表示语料库文章总数，Si表示在D的样本中，包含词i的文章篇数。 举例2：在总语料库中，含有地球的文章数量为100，总文章数为100000，那么地球这个词的反文档频率为：IDF=lg(100000/100)
34、=3 。TF-IDF最后得到i的权值公式为（2-4） 举例3：综合例1，例2，那么地球这个词，在语料库中的权值为：TF*IDF=0.007*3=0.021TF-IDF计算权值的好处分析 首先，如果不使用此方法，例如地球的公转，“地球” 、“的”、 “公转” 在文章中出现的次数分别为7、100、5，如果只是统计词频，假设文章有一千词，那么三个词的词频分别为：0.007 ，0.100 ,0.005 显然，“的”的词频很大，三个词总共的贡献度为0.112，但是“的”占了绝大部分，显然这个词不能表示本文的特征，反之，地球与公转这两个词能表征文本大意，但是所占的比例却相当的小。 其次，引入IDF，此问题
35、就能得到很好的解释：如上例子，还是以“地球” 、“的”、 “公转”为例，出现次数如上所示。语料库含有的总文章数为：105 ，含有“地球”文章数为102，含有“的”的文章数为105，含有“公转”的文章数为103，那么根据DF-IDF计算公式，计算得出 W（地球）=0.007*lg(105/102)=0.021 W（的）=0.100*lg(105/105)=0 W(公转)=0.005*lg(105/103)=0.010这样计算，得出的结果“的”的权值为0，而地球和公转分别占了0.021和0.010，这样的结果符合正常的逻辑情况。2.4.3、词典2.4.3.1、用户词典在对语料库中所有的文章进行分词
36、之后，势必会有很多的字以及词语，每当产生一个新的词语的时候，相应的用户词典就会把这个词加入进去，每当有新词进入的时候，词典的长度就会加一，这样对于训练集，训练集越大形成的词典也就越大，相应的对各篇文章的区分度会更好，有词典的存在，每当出现新词的时候，用户也不用担心，加入词典就可以。最终的词典长度和空间向量的长度是相同的。2.4.3.2、停用词词典 停用词，顾名思义，就是文本分类过程中不需要用到的词语，这些词语千篇一律，不仅对文章没有表征作用，而且会增加处理的复杂度，如果把这些词加入计算，会影响计算的时间，因此专门设计一个停用词词典，对这些词不加入计算，停用词里面的内容，见后面附录.2.5、常用的降维方法 当一个空间向量形成之后，由于词典词数肯定是成千上万，可想而知向量的长度肯定也是相当的长，在这样长的向量之间运用分类算法，效果一般不是很好，计算的时间可能也会相当的长，因此要用一些算