学位论文-—中文文本分类算法设计及其实现.doc

毕业设计（论文）任务书

毕业设计（论文）

题 目 中文文本分类算法的设计及其实现

电信 学院 计算机 系 84 班

学生姓名 丰成平

学 号 2008055089

指导教师 相明

设计所在单位 西安交通大学计算机系

2013 年 6 月

系 （ 所 ） 计算机科学与技术
系 (所) 主任
批 准 日 期
毕业设计(论文)任务书
电信学 院 计算机 系 84 班 学生 丰成平

毕业设计(论文)工作自 2013 年 2 月 21 日起至 2013 年 6 月 20 日止
毕业设计(论文)进行地点： 西安交通大学

课题的背景、意义及培养目标

随着文本文件的增多，对其自动进行分门别类尤为重要。文本分类是指采用计算机程序对文本集按照一定的分类体系进行自动分类标记。文本分类器 的设计通常包括文本的特征向量表示、文本特征向量的降维、以及文本分类器的设计与测试三个方面。本毕设论文研究文本分类器的设计与实现。通过该毕业设计，可使学生掌握文本分类器设计的基本原理及相关方法，并通过具体文本分类算法的设计与编程实现，提高学生的实际编程能力。

设计(论文)的原始数据与资料

1、文本语料库（分为训练集与测试集语料库）。
2、关于文本分类的各种文献（包括特征表示、特征降维、以及分类器设计）以及资料。
3、中科院文本分词工具(nlpir)。
4、文本分类中需要用到的各种分类方法的资料描述。

课题的主要任务

1．学习文本特征向量的构建方法及常用的降维方法。
2．学习各种分类器的基本原理及其训练与测试方法。
3．设计并编程实现文本分类器。
4、对试验结果进行分析，得出各种结论。
5、撰写毕业论文。
6、翻译一篇关于文本分类的英文文献。

课题的基本要求(工程设计类题应有技术经济分析要求)
1、程序可演示。
2、对源代码进行注释。
3、给出完整的设计文档及测试文档。

完成任务后提交的书面材料要求(图纸规格、数量，论文字数，外文翻译字数等)
1、提交毕业论文
2、提交设计和实现的系统软件源程序及有关数据
3、提交外文资料翻译的中文和原文资料

主要参考文献：
自然语言处理与信息检索共享平台：http://www.nlpir.org/?action-viewnews-itemid-103

Svm(支持向量机)算法：

基于神经网络的中文文本分析（赵中原）：

TF-IDF的线性图解：

东南大学向量降维文献：
指导教师 相明
接受设计(论文)任务日期 2013-02-21~2013-06-20
学生签名：

西 安 交 通 大 学
毕业设计(论文)考核评议书
院 系(专业) 班级

指导教师对学生 所完成的课题为

的毕业设计(论文)进行的情况，完成的质量及评分的意见：

指导教师
年 月 日

毕业设计(论文)评审意见书

评审意见：

评阅人 职称
年 月 日

毕业设计(论文)答辩结果

院
系(专业)

毕业设计(论文)答辩组对学生 所完成的课题为

的毕业设计(论文)经过答辩,其意见为

并确定成绩为

毕业设计(论文)答辩组负责人
答辩组成员

年 月 日

摘要
论文题目：中文文本分类算法的设计及其实现
学生姓名：丰成平
指导教师：相明
摘要

随着当今社会，计算机的普遍使用，出现了连绵不断的文本文件，如何对这些毫无逻辑、毫无层次的文件进行分门别类的整理，做到井井有条，层次鲜明呢？
文本自动分类就是针对上述情况，采用机器，通过一定的约束条件和一些分类算法，自动的对这些文件进行遍历，从而实现分门别类。这样用机器代替人来“阅读”文章，用机器代替人来“整理”文章，不仅减轻了工作人员的负担，而且大大节省了时间，工作人员可以去做更多有意义的事情。
文本分类主要有以下三个方面：
第一、 文本的空间向量表示：由于计算机并不能识别真正的文本，本质上只懂得0,1，因此若要对文本进行分类，首先要让计算机能够“读懂”每篇文章，引入文本空间向量表示，将文章里面的特征词形成空间向量，通过计算向量之间的差距，来实现分门别类。
第二、 文本特征的降维：由于中文词汇成千上万，那么形成的文本向量肯定也很长，计算起来会很麻烦，因此要对向量进行处理。
第三、 文本分类器的设计：文本分类方法例如：KNN、朴素贝叶斯、SVM、决策树，BP神经网络，运用这些算法设计分类器，从而处理文本向量之间的关系，实现对文本的分门别类。
最后，将文本分类运用于众多领域，例如：信息过滤、文档管理、网络安全、电子图书整理、网络图书馆，搜索引擎，这样则不是通过关键字过滤，而是基于文本内容的过滤或者是搜索，能大大提高过滤的可靠性以及搜索的准确性，无疑使文本领域的一项重大的突破

关 键 词：文本向量；特征降维；分类算法；分类器设计。

1

Title: The design and implementation of Chinese text classification algorithm
Name: Feng Chengping
Supervisor: Xiang Ming

ABSTRACT

With today's society, the widespread use of computers, 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, 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 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 space, 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 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, 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 the filter and search, no doubt make a significant breakthrough in the field of text
Key words: text vector; Characteristics will be; Classification algorithms; Classifier design.

Key words: text vector; feature reduction; Classification algorithms; Classifier design.

1

目录

目录

第一章 绪论 6
1.1、文本分类背景和意义 6
1.2、文本分类的应用领域 6
1.2.1、Internet上面应用 6
1.2.2、网络图书馆方面的应用 7
1.2.3、网络安全方面 7
1.2.4、电子邮件方面 7
1.3、目前国内外研究现状 7
1.4、文本分类的发展趋势展望 8
1.5、本章小结 8
第二章 文本分类主要过程 9
2.1、文本分类的过程图 9
2.2、关于语料库 10
2.2.1、文本分类语料库介绍 10
2.2.2、文本分类，训练阶段的主要步骤 10
2.2.3、文本分类，分类（测试）阶段的主要过程 10
2.3、关于文本分词 10
2.4、文本空间向量的形成 11
2.4.1、VSM（Vector Space Model） 11
2.4.2、常见的权值计算方法 12
2.4.2.1、布尔框架（Booolean weighting） 12
2.4.2.2、TF-IDF计算权值算法 12
2.4.3、词典 14
2.4.3.1、用户词典 14
2.4.3.2、停用词词典 14
2.5、常用的降维方法 14
2.5.1、信息增益方法 15
2.5.2、互信息方法 16
2.5.3、期望交叉熵方法 17
2.5.4、X^2统计方法 17
2.5.5、文本证据权方法 18
2.6、本章小结 18
第三章 常用的文本分类方法 19
3.1、k临近分类器 19
3.1.1、KNN算法概述 19
3.1.2、KNN算法用于文本分类器构造 19
3.1.3、KNN算法用于分类 20
3.1.4、KNN算法效果评价 20
3.2、支持向量机分类器 21
3.2.1、SVM算法概述 21
3.2.2、SVM构造分类器 21
3.2.2.1、线性可分 21
3.2.2.2、线性不可分 22
3.2.2.3、映射函数（核函数） 23
3.2.4、SVM分类评价 24
3.3、决策树算法分类器 24
3.3.1、决策树概述 24
3.3.2、决策树分类器的构造 26
3.3.3、决策树分类器的构造 27
3.4、朴素贝叶斯分类器 27
3.4.1、贝叶斯算法原理 27
3.4.2、贝叶斯分类器 28
3.4.3、贝叶斯进行分类 28
3.5、BP神经网络分类器 29
3.5.1、BP神经网络原理 29
3.5.2、BP神经网络分类器 30
3.5.3、BP神经网络进行分类 31
3.6、本章小结 31
第四章 试验结果分析统计 32
4.1、试验结果评估指标简介 32
4.2、使用KNN分类算法部分结果分析 32
4.2.1、训练总篇数对分类结果的影响 32
4.2.2、不同的K值对分类结果的影响 33
4.2.3、降维深度对分类结果的影响 35
4.2.4、采用不同的降维方法对试验结果的影响 36
4.2.5、分而统计各个类别的详细信息 36
4.3、使用SVM分类算法结果分析 37
4.3.1、训练总篇数对分类结果的影响 37
4.3.2、降维深度对分类结果的影响 38
4.3.3、采用不同的降维方法对试验结果的影响 39
4.3.4、分而统计各个类别的详细信息 40
4.4、本章小结 41
总结与展望 42
参考文献 44
致谢 45
附录 46

第一章 绪论
1.1、文本分类背景和意义

互联网发展，网上电子图书（txt文档、pdf文档、微小说、期刊论文等等），企业公司内部文件整理，电子文档的增加，为了高效访问和使用这些文档数据，如果人为的对这些文件信息进行处理，不仅需要花费大量的时间翻阅每一篇文章，了解每篇文章的大体内容，而且要付出很大的精力去统计。毕竟人的大脑工作能力有限，长期处于这种工作环境中，会造成大脑极大的负担，很可能由于一时疏忽而出现了错误，甚至信息量太过庞大，人脑不可能记录这么多类别信息，在最后评估的时候也有可能做出错误的判断。不仅耽误时间，而且不能实现分布式管理，如果由多人进行这项工作，很可能导致意见不同而导致纠纷等等。甚至同一个人，在不同的时间不同的地点，对一篇文章的分类页不尽相同，这样，很多严峻的问题随之而来。
文本自动分类就是针对上述情况，采用机器，通过一定的约束条件和一些分类算法，自动的对这些文件进行遍历，从而实现分门别类。这样用机器代替人来“阅读”文章，用机器代替人来“整理”文章，不仅减轻了工作人员的负担，而且大大节省了时间，这样工作人员就有更多的时间来处理其他的事情。用机器代替人来工作，这样在整理的过程中也不会出现一时疏忽而出现错误，更可以夜以继日的进行分类，一旦有新的文章进入，就可以通过机器“读取”这篇文章，然后自动的进行处理，可以带来很多的方便

1.2、文本分类的应用领域
1.2.1、Internet上面应用
把文本分类系统结合到搜索引擎（谷歌、百度）之类，可以大大提高搜索的准确性，目前大部分搜索引擎是通过查找关键字进行匹配，用这种方法必须要遍历每篇文章，找出其中的关键字，然后统计结果输出，这种查询的精度不是很高，速度方面由于要遍历很多文章，速度当然不会很快。如用引入文本分类系统，当查询某个关键字的时候，可以自动判定与之相关的文件类别，基于内容的查询，可以直接命
5

第一章 绪论
中目标，查询速度和精度能得到有效的提升

1.2.2、网络图书馆方面的应用
任何一个图书馆的馆藏资源成千上万，如果没能很好的分门别类，大量的图书便会
杂乱无章，不仅浪费工作人员的时间进行整理和查询，而且读者在找寻自己想要的图书方面也会花费很大的时间。因此可以使用文本分类引擎实现电子图书的分门别类，使管理更加方便，是查询更加简单。

1.2.3、网络安全方面
internet的普及，人们上网浏览信息，很多是对读者有用的，但是也有不法分子将不健康的信息通过internet进行传播，不仅影响了读者的时间，更会影响读者的情绪，影响工作效率。如果将文本分类引擎引入绿色上网功能中，对用户要访问的内容事先进行分析，去除没有用的垃圾信息，就可以为用户带来很多方便。目前 电信绿色上网，360绿色上网等都可以考虑引入此引擎，相信效果会更上一层楼。

1.2.4、电子邮件方面
可以自动为用户预处理邮件，将邮件分门别类，而且必要的时候，可以自动屏蔽一些没有用的垃圾邮件，给用户带来了很多方便。

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

系统、自动分类系统三个阶段。总体来书，中文文本分类还处于在试验研究阶段，正确分类率约为60%~90%，目前已经在国内受到重视，相关的学术研究成果也层出不穷，相信不久以后，文本分类将涉及到中文的各个领域，发挥自己的一技之长。

1.4、文本分类的发展趋势展望
只要汉语甚至语言文字依旧在使用，那么文本分类将永远有自己的重要性，而且随着文字数目的增多，文件类别的加剧，文本分类引擎将会越来越得到各界人士的关注，运用领域将会越来越广泛，重要性也会越来越高。相信在不就的将来，nternet方面、
电子邮件、网络图书馆、绿色上网安全方面，都会运用文本分类引擎以达到更好的效果，研究文本分类，必定会发展自己的独特优势，为用户带来更多的方便。

1.5、本章小结

本章主要从文本分类的背景以及应用方面入手，提出了文本分类的研究的历史背景，以及对应的应用领域，叙述了众多文本分类的好处，通过对比国内外的相关研究成果，分析国内目前文本分类的现状对文本分类的前景趋势进行展望。

19

第二章 文本分类的主要过程
第二章 文本分类主要过程
2.1、文本分类的过程图
首先把文本分类的总体流程图展示出来，主要包括对文本的处理，对处理之后向量的降维，然后对训练集测试集语料库进行仿真，文本分类过程图如图所示。

开始

训练集、测试集语料库

输入文本

采用中科院nlpir分词

文本分词

TF-IDF计算权值

空间文本向量

降维方法

向量降维

分类方法：svm/决策树...

进行文本分类

Weka、C++、matlab仿真

最终结果

图2-1 文本分类过程图

第二章文本分类的国主要过程

2.2、关于语料库
2.2.1、