基于贝叶斯的文本自动分类的研究和实现

  题目     基于贝叶斯的文本自动分类的研究和实现

  专业     学号    姓名主要内容、基本要求、主要参考资料等：

近年来随着Internet的大规模普及和企业信息化程度的提高，有越来越多的信息积累，而需要信息的人还没有特别方便的工具去从来自异构数据源的大规模的文本信息资源中提取符合需要的简洁、精炼、可理解的知识，文本挖掘正是解决这一问题的一个方法。

本课题研究基于贝叶斯的文本分类系统，可以用于以下领域和系统中：企业知识门户、信息增值服务、智能搜索引擎 、数字图书馆 、情报分析 、信息安全和过滤、电子商务系统。文本自动分类不需人工干预的自动分类技术，有效提高非结构化信息资源的加工效率。利用朴素贝叶斯分类文法的分类器，分析已经手动分类的文本，根据文本内容计算分类条件概率，再利用训练好的分类器分析未分类的文本，根据分类器算出的所属领域概率最大的进行分类。

本课题任务要求：

1)学习关于朴素贝叶斯分类文法，查找相关的资料以供参考；

2)实现朴素贝叶斯分类文法的分类器；

3)人工对样本数据进行分类和标注；

4)利用贝叶斯分类文法的分类器，利用样本进行训练，然后对分类数据进行自动分类；

5)根据分类结果，调整分类阈值，弥补分类器的不足。

6)根据实验数据和结果，按时完成毕业设计论文。

主要参考资料：贝叶斯分类算法的论文和资料，未分类文本语料。

完成期限：

指导教师签章：                            

专业负责人签章：

年    月    日

摘要

随着计算机技术和通讯技术的飞速发展，人们可以获得越来越多的数字化信息，但同时也需要投入更多的时间对信息进行组织和管理。为了减轻这种负担，人们开始研究使用计算机对文本进行自动分类。文本自动分类就是在给定的分类体系下，让计算机根据文本的内容确定与它相关联的类别。自动文本分类是人工智能技术和信息获取技术相结合的研究领域。随着网络的发展，大量的文档数据涌现在网上，用于处理海量数据的自动文本分类技术变得越来越重要，已逐渐成为处理和组织大量文档数据的关键技术。

通过分析kNN(k Nearest Neighbor)、朴素贝叶斯(Naive Bayes)、SVM(Support Vector Machine)三种文本分类方法的优点和缺点，发现朴素贝叶斯分类器速度极快，具有最小的出错率，可在线化实现等优点，并对该分类方法进行了理论分析和实验对比，实验结果表明这种文本分类模型是高效的可行的。

本文首先介绍了基于贝叶斯的文本自动分类的研究和实现的背景,并且叙述了相关问题的概念知识，包括文本分类和中文分词等；其次，对相关的理论知识做了讲解，包括先验概率、条件概率、贝叶斯理论、贝叶斯算法等；第三，对如何实现文本分类进行了概述以及整体讲解，通过给出流程图，可以更直观的了解实现的过程；第四，详细介绍了实现本课题所用到的重要工具，包括JBuilder2007开发工具和全文检索引擎Lucene以及Java平台；第五，在前期工作基础上，给出了详细的实现过程，包括单文本分类和多文本分类以及相关具体操作；最后，通过多次大量重复试验，得出了实验数据，在此通过表格的形式，直观的给出了实验结果。

本课题研究基于贝叶斯的文本分类系统，根据所讨论的算法构造了贝叶斯文本自动分离器，并做出详尽的训练测试，从最终的试验结果可以看出，贝叶斯算法简单、性能优越，即使在不考虑贝叶斯假设的前提下，仍然取得良好的分类性能。

关键字：文本自动分类 ，贝叶斯分类 ，分类文本语料库。

Abstract

With the computer technology and the rapid development of communication technology, people can get more and more digital information, but it also needs to devote more time to organize and manage information. In order to alleviate that burden, people began to study the use of computers for automatic classification of text. Automatic text categorization is the classification of a given system, the computer determined in accordance with the contents of the text associated with its category. Automatic text classification is the artificial intelligence technology and access to information technology research field. With the development of network, data on the emergence of a large number of documents online, to deal with massive data technology of automatic text classification is becoming increasingly important, has become an increasingly large number of document processing and organization of the key technologies of data.

By analyzing the k Nearest Neighbor、Naive Bayes、Support Vector Machine method of text classification in three strengths and weaknesses found in Naive Bayesian classifier speed, with the smallest error rate, can achieve the advantages of online technology, and the classification of the theoretical analysis and experimental comparison, experimental results show that the text categorization model is feasible and efficient.

 This paper first introduces the Bayesian-based text categorization of the research and realization of the background and describes the issues related to the concept of knowledge, including text classification and Chinese word segmentation  .

 Second, the relevant theoretical knowledge to do the explaining, including a priori probability, conditional probability, Bayesian theory, the Bayesian algorithm . 

Third, on how to achieve the outlined text classification as well as on the whole, through the given flow chart, you can achieve a more intuitive understanding of the process. 

Fourth, in detail on achieving this important task by use of tools, including development tools and JBuilder2007 full-text search engine Lucene and Java platform.

Fifth, prior to the adoption of the work detailed in this paper the realization of the process, including single-and multi-text classification text categorization and related specific operations; Finally, a large number of repeat tests many times, the experimental data obtained in this form through the form, intuitive experimental results are given.

The research based on Bayesian text classification system, according to the algorithm discussed in the text automatically constructed Bayesian separator and training to make a detailed test results from the final we can see that the Bayesian algorithm is simple, superior performance, even without taking into account the assumption that the premise of Bayesian still achieve good classification performance. 

 Keywords: Automatic Text Categorization, Bayesian Classifier, 

 Classification of text corpora.

目录

1.绪论    2

1.1研究背景    2

1.2 文本分类的研究现状    2

1.3分类的含义    3

1.4文本分类的含义    3

1.5自动分类    3

1.6中文分词    3

1.7中文分词的意义和作用    4

1.8中文分词的应用    4

1.9 本文的组织    4

2.条件概率    6

2.1 条件概率定义    6

2.2 全概率公式和贝叶斯公式    6

2.3 贝叶斯学习理论    6

2.4朴素贝叶斯分类    7

2.5贝叶斯文本分类算法    9

2.6文本自动分类的特点    10

3.设计概述    11

3.1流程图    11

3.2概要设计    14

4.系统开发环境    15

4.1 JAVA    15

4.2开放源代码的全文检索引擎Lucene简介    16

5.贝叶斯的文本自动分类的分析与设计    19

5.1 引言    19

5.2 详细设计    19

5.3 程序实现    29

5.4试验数据    35

6结论    36

全文总结    36

未来展望    36

致谢    37

参考文献    38

1.绪论

1.1研究背景

我们正处在一个信息急剧丰富的时代，据1998年的统计结果显示，全世界每年出版大约15600种期刊，而且这一数字以每年12000种的速度递增,同期，仅美国国内就有近140万种图书在付印，这一数据还以平均每年6万种的速度在增加。1998年美国国会图书馆藏书约1700万种，而平均每天接收到的新书就多达7000种。

另一个增长惊人的信息渠道是Internet，1999年的统计结果表明，Internet上约有3.5亿个静态HTML（HyperText Markup Language超文本标记语言）页面，每天增加将近100万。这些页面大部分是以文本文档的形式存在，而我们日常所接触的信息，也绝大部分是文本的形式，它们或以印刷品的方式存在，或以电子文档的形式出现。尤其是近十年来，随着网络的飞速发展，数字图书馆的出现，越来越多的文本信息以电子文档的形式存在。

面对如此庞大而又急剧膨胀的信息海洋，如何有效地组织和管理这些信息，并能快速、准确、全面地从中找到用户所需要的信息是当前信息科学与技术领域所面临的一大挑战。文本分类作为处理和组织大量文本数据的关键技术，可以在较大程度上解决信息的纷繁杂乱问题，方便用户快度、准确地定位所需要的信息。因此，自动文本分类已作为一项具有较大实用价值的关键技术，得到了广泛关注，取得了很大进展。

1.2 文本分类的研究现状

国外文本数据分类的研究始于20世纪50年代末，Luhn在这一领域进行了开创性的研究，其后许多学者在这一领域进行了卓有成效的研究。

国外文本数据分类研究大体上可以分为三个阶段:第一阶段是20世纪80年代前。在这一时期，模式识别和信息检索相继发展成一门学科。这一阶段主要是集中在对分类理论的研究，应用方面则主要是用于信息检索。第二阶段是20世纪80年代到90年代。这一阶段主要是采用传统的知识工程技术，在这一时期，信息检索技术逐渐成熟应用，为文本分类提供了许多技术支持。第三阶段是20世纪90年代以后。互连网技术的发展，文本数据量急剧增加，这种耗时、灵活性差、应用难度大的知识工程方法越来越不能满足实际应用的需要，于是逐渐被机器学习的方法取而代之。

基于机器学习的文本分类方法克服了以前手工建立分类器的缺点，使得文本分类具有了真正的实用价值。这一时期分类器的特点:一是分类知识来源于机器对训练集的自动学习，不再依赖于专家；二是学习和分类过程不需要人工干预，分类效率和准确率都有很大提高。所谓机器学习是指由计算机代替人来学习关于认识世界、改造世界的知识。

国内文本数据分类研究起步较晚，始于20世纪80年代初期。我国文本分类的研究大体上经历了可行性探讨、辅助分类、自动分类系统三个发展阶段。早期对中文文本的分类研究较少，采用的技术也主要是把英文文本分类的技术应用到中文文本分类当中。自上世纪90年代后期才开始着重于对中文文本分类的研究，结合中文文本的特点，形成中文文本数据分类研究体系。文本分类方面的文献也非常丰富，常见于信息检索、机器学习、知识挖掘与发现、模式识别、人工智能、计算机科学与应用等各种国际会议及相关的期刊或杂志。

1.3分类的含义

广义的分类（classification或者categorization）有两种含义：一种含义是有指导的学习（supervised learning）过程，另一种是无指导的学习（unsupervised learning）过程。通常前者称为分类，后者称为聚类（clustering），后文中提到的分类是指有指导的学习过程。给定分类体系，将文本集中的每个文本分到某个或者某几个类别中，这个过程称为文本分类（text categorization）。

1.4文本分类的含义

文本分类过程可以分为手工分类和自动分类。前者最著名的实例是yahoo的网页分类体系，是由专家定义了分类体系，然后人工将网页分类。这种方法需要大量人力，现实中已经采用的很少了。自动文本分类（automatic text categorization）算法大致可以分为两类：知识工程（knowledge engineering）方法和机器学习（machine learning）方法。知识工程方法指的是由专家为每个类别定义一些规则，这些规则代表了这个类别的特征，自动把符合规则的文档划分到相应的类别中。这方面最著名的系统是CONSTRUE。上个世纪90年代之后，机器学习方法成为主导。机器学习方法与知识工程方法相比，能够达到相似的精确度，但是减少了大量的人工参与。下面主要介绍基于机器学习方法的文本分类。

1.5自动分类

1.自动分类基于内容、不需人工干预的文本自动分类技术。系统提供分类训练工具，允许用户自行根据自己的分类需求和数据特点设定分类结构，自动生成特征模板，进行分类训练。TRS自动分类支持反馈学习机制，可以根据用户的反馈自动对分类模板进行完善，从而逐步增加分类的准确率。

2.自动分类是利用模式识别技术实现对遥感影像内容的自动标志识别和分类，即计算机辅助判读。通常采用特征空间识别方法。是建立在概率论和数理统计基础上，立足于寻找能反映影像特点的一些特征，经过信息压缩、特征抽取、特征选择和决策规划来识别地物的计算机自动分类方法。

1.6中文分词

什么是中文分词?中文分词与其他的分词又有什么不同呢？分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。我们知道，在英文的行文中，单词之间是以空格作为自然分界符的，而中文只是字、句和段可以通过明显的分界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的划分问题，但是在词这一层上，中文比之英文要复杂的多、困难的多。 

1.7中文分词的意义和作用

要想说清楚中文分词的意义和作用，就要提到智能计算技术。智能计算技术涉及的学科包括物理学、数学、计算机科学、电子机械、通讯、生理学、进化理论和心理学等等。简单的说，智能计算就是让机器“能看会想，能听会讲”。要想实现这样的一个目标，首先就要让机器理解人类的语言，只有机器理解了人类的语言文字，才使得人与机器的交流成为可能。再反观我们人类的语言中，“词是最小的能够活动的有意义的语言成分”，所以对于中文来讲，将词确定下来是理解自然语言的第一步，只有跨越了这一步，中文才能像英文那样过渡到短语划分、概念抽取以及主题分析，以至于自然语言理解，最终达到智能计算的最高境界，实现人类的梦想。

从现阶段的实际情况来看，英文已经跨越了分词这一步，也就是说在词的利用上已经先我们一步，并且已经展现了良好的应用前景，无论是信息检索还是主题分析的研究都要强于中文，究其根本原因就是中文要通过分词这道难关，只有攻破了这道难关，我们才有希望赶上并超过英文在信息领域的发展，所以中文分词对我们来说意义重大，可以说直接影响到使用中文的每一个人的方方面面。

1.8中文分词的应用

中文分词主要应用于信息检索、汉字的智能输入、中外文对译、中文校对、自动摘要、自动分类等很多方面。下面就以信息检索为例来说明中文分词的应用。 

通过近几年的发展，互联网已经离我们不再遥远。互联网上的信息也在急剧膨胀，在这海量的信息中，各类信息混杂在一起，要想充分利用这些信息资源就要对它们进行整理，如果由人来做这项工作，已经是不可能的，而如果面对中文信息不采用分词技术，那么整理的结果就过于粗糙，而导致资源的不可用，例如：“制造业和服务业是两个不同的行业”和“我们出口日本的和服比去年有所增长”中都有“和服”，而被当作同一类来处理，结果是检索“和服”的相关信息，会将他们都检索到，在信息量少的情况下，似乎还能够忍受，如果是海量信息，这样的结果就会令人讨厌了。通过引入分词技术，就可以使机器对海量信息的整理更准确更合理，在“制造业和服务业是两个不同的行业”中“和服”不会被当作一个词来处理，那么检索“和服”当然不会将它检索到，使得检索结果更准确，效率也会大幅度的提高。所以中文分词的应用会改善我们的生活，使人们真正体会到科技为我所用。

2.条件概率

2.1 条件概率定义

定义 设A, B是两个事件，且P(A)>0 称P(B∣A)=P(AB)/P(A)为在条件A下发生的条件事件B发生的条件概率。

乘法公式 设P(A)>0 则有P(AB)=P(B∣A)P(A) 

2.2 全概率公式和贝叶斯公式

定义  设S为试验E的样本空间，B1, B2, …Bn为E的一组事件，若BiBj=Ф, i≠j, 

（i, j=1, 2, …,n）；B1∪B2∪…∪Bn=S则称B1, B2, …, Bn为样本空间的一个划分。

定理  设试验E的样本空间为S，A为E的事件，B1, B2, …,Bn为的一个划分，且P(Bi)>0 

(i=1, 2, …n)，则P(A)=P(A∣B1)P(B1)+P(A∣B2)P（B2）+…+P(A∣Bn)P(Bn)称为全概率公式。

定理  设试验E的样本空间为S，A为E的事件，B1, B2, …,Bn为的一个划分，则

P(Bi∣A)=P(A∣Bi)P(Bi)/∑P(B｜Aj)P(Aj)=P(B｜Ai)P(Ai)/P(B) 称为贝叶斯公式。

下面我再举个简单的例子来说明下。考虑一个医疗诊断问题，有两种可能的假设：

（1）病人有癌症。

（2）病人无癌症。

样本数据来自某化验测试，它也有两种可能的结果：阳性和阴性。假设已经有先验知识：在所有人口中只有0.008的人患病。此外，化验测试对有病的患者有98%的可能返回阳性结果，对无病患者有97%的可能返回阴性结果。

上面的数据可以用以下概率式子表示：

P(cancer)=0.008,P(无cancer)=0.992

P(阳性|cancer)=0.98,P(阴性|cancer)=0.02

P(阳性|无cancer)=0.03，P(阴性|无cancer)=0.97

假设现在有一个新病人，化验测试返回阳性，是否将病人断定为有癌症呢？可以计算极大后验假设：

P(阳性|cancer)p(cancer)=0.98*0.008 = 0.0078

P(阳性|无cancer)*p(无cancer)=0.03*0.992 = 0.0298

因此，应该判断为无癌症。

2.3 贝叶斯学习理论

贝叶斯是一种基于概率的学习算法，能够用来计算显式的假设概率，它基于假设的先验概率，给定假设下观察到不同数据的概率以及观察到的数据本身。

本课题用P(h)表示没有训练样本数据前假设h拥有的初始概率，也就称为h的先验概率，它反映了我们所拥有的关于h是一个正确假设的机会的背景知识。当然如果没有这个先验知识的话，在实际处理中，可以简单地将每一种假设都赋给一个相同的概率。类似，P(D)代表将要观察的训练样本数据D的先验概率（也就是说，在没有确定某一个假设成立时D的概率）。然后是P(D/h)，它表示假设h成立时观察到数据D的概率。在机器学习中，所感兴趣的是P(h/D),也就是给定了一个训练样本数据D,判断假设h成立的概率，这也称之为后验概率，它反映了在看到训练样本数据D后假设h成立的置信度。（注：后验概率p(h/D)反映了训练数据D的影响，而先验概率p(h)是于D的）。

              　 ＝        　　　　        （2.1）

注意，在最后一步去掉了P（D），因为它是不依赖于h的常量。在某些情况下，可假定H中每个假设有相同的先验概率（即对H中任意hi和hj,P(hi)=P(hj)）。这时可把等式（2.1）进一步简化，只需考虑P（D|h）来寻找极大可能假设。P（D|h）常被称为给定h时数据D的似然度，而使P（D|h）最大的假设被称为极大似然（maximum likelihood，ML）假设hML

　　　　　　　P(h|D) = P(D|h)P(h)/p(D)   （2.2）

从贝叶斯公式可以看出，后验概率p(h/D)取决于P(D|h)P(h)这个乘积，这就是贝叶斯分类算法的核心思想。要做的就是要考虑候选假设集合H，并在其中寻找当给定训练数据D时可能性最大的假设h（h属于H）。

简单点说，就是给定了一个训练样本数据（样本数据已经人工分类好了），应该如何从这个样本数据集去学习，从而当碰到新的数据时，可以将新数据分类到某一个类别中去。那可以看到，上面的贝叶斯理论和这个任务是吻合的。

2.4朴素贝叶斯分类

可使用贝叶斯公式将此表达式重写为：

　                      　　    （2.3）

　现在要做的是基于训练数据估计式（2.3）中两个数据项的值。估计每个P（vj）很容易，只要计算每个目标值vj出现在训练数据中的频率就可以。然而，除非有一个非常大的训练数据的集合。否则用这种方法估计不同的P(a1,a2,an |vj)项不大可行。问题在于这些项的数量等于可能实例的数量乘以可能目标值的数量。因此为获得合理的估计，实例空间中每个实例必须出现多次。

  朴素贝叶斯分类器基于一个简单的假定：再给定目标值时属性值之间相互条件。换言之，该假定说明在给定实例目标值情况下，观察到联合的a1,a2,…an的概率等于每个单独属性的概率乘积：

                      （2.4）

   将其带入（2.3）中，可得朴素贝叶斯分类器所使用的方法：

                                         （2.5）

其中vNB是朴素贝叶斯分类器输出的目标值。注意，在朴素贝叶斯分类器中，需从训练数据中估计的不同P(ai|vj)项的数量只是不同的属性值数量乘以不同目标值数量——这比要估计P(a1,a2,…an|vj)P(a1,a2,…an|vj)所需要的量要小的多。

举个简单的例子，让大家对这个算法的原理有个快速的认识。

假设给定了表2.1中训练样本数据，学习的目标是根据给定的天气状况判断你对PlayTennis这个请求的回答是Yes还是No。

可以看到这里样本数据集提供了14个训练样本，本课题将使用此表的数据，并结合朴素贝叶斯分类器来分类下面的新实例：

(Outlook = sunny,Temprature = cool,Humidity = high,Wind = strong)

本课题的任务就是对此新实例预测目标概念PlayTennis的目标值(yes或no).

由上面的公式可以得到：

=        

                                  （2.6）

可以得到：

P(PlayTennis =yes) = 9/14 = 0.

P(PlayTennis=no)=5/14 = 0.36

P(Wind=Stong| PlayTennis =yes)=3/9=0.33

p(Wind=Stong| PlayTennis =no)=3/5 = 0.6

其他数据类似可得，代入后得到：

P(yes)P(Sunny|yes)P(Cool|yes)P(high|yes)P(Strong|yes) = 0.0053

P(no)P(Sunny|no)P(Cool|no)P(high|no)P(Strong|no)=0.0206

因此应该分类到no这一类中。

2.5贝叶斯文本分类算法

根据联合概率公式（全概率公式）

                                 （2.7）

即得到贝叶斯公式

                                             （2.8）

则贝叶斯文本分类的任务就是将表示成为向量的待分类文本X(x1,x2,…xn)归类到与其关联最紧密的类别C(C1,C2,…Cj)C(C1,C2,…Cj)中去。其中X(x1,x2,…xn)为待分类文本Xq的特征向量，C(C1,C2,…Cj)为给定的类别体系。也就是说，求解向量X(x1,x2,…xn)属于给定类别C1,C2,…Cj的概率值(P1,P2,…Pn )，其中，Pj为X(x1,x2,…xn)属于Cj的概率，则max(P1,P2,…Pn)所对应的类别就是文本X所属的类别，因此分类问题被描述为：求解方程（2.8）式的最大值。

                                （2.9）

其中，

1）P(cj)——训练文本集中，文本属于类别cj的概率；

2）P(x1,x2,…xn|cj)——如果待分类文本属于类别cj，则类别cj中包含向量(x1,x2,…xn)的概率；

3）P(c1,c2,…cn)——给定的所有类别的联合概率； 

显然，对于给定的所有类别，分母P(c1,c2,…cn)是一个常数，所以求解（2.8）式的最大值转化为求解下式的最大值，

                                   （2.10）

又根据贝叶斯假设，文本特征向量属性x1,x2,…xn同分布，其联合概率分布等于各个属性特征概率分布的乘积，即:

                                       （2.11）

所以（2.10）式变为:

                                        （2.12）

即为所求解的用以分类的分类函数。

尽管推导出了分类函数，但是分类函数中的概率值P(cj)和P(xi|cj)还是未知的，因此，为了计算分类函数的最大值，（2.11）式中的先验概率值分别估算如下：

1）   

 其中，N(C=cj)——训练文本中属于cj类别的文本数量；N——训练文本总数量。

2）  

其中：

N(Xi=xi,C=cj)——类别cj中包含属性xi的训练文本数量；

N(C=cj)——类别中的训练文本数量；

M——训练文本集合中经过踢出无用词去除文本预处理之后关键字的数量。

2.6文本自动分类的特点

文本分类是将一个文本归入预先定义好的几个类别中的一个分类中的过程。而文本的自动分类是使用计算机程序来实现这样的分类。第一，用于分类所需要的类别体系是预先确定好的。这种分类层次一旦确定，在相当长的时间内都是不可变的。或者即使要变更，也要付出相当大的代价。第二，一个文本并没有严格规定只能被分配给一个类别。这与分类的这个问题的主观性有关。这就造成了分类的准确性不可能达到100%的正确，本课题的主要目标就是尽最大可能提高分类的准确性。

参考文献

【1】王丁,运海红,张辉; 文本自动分类系统的研究与实现 [J];信息技术; 2005年03期; 68-69

【2】卢苇,彭雅; 几种常用文本分类算法性能比较与分析 [J];湖南大学学报(自然科学版); 2007年06期; 72-74

【3】宋枫溪; 自动文本分类若干基本问题研究 [D];南京理工大学; 2004年

【4】董学春,胡学钢,谢飞,吴共庆; 基于词向量空间模型的文本分类方法 [A];计算机技术与应用进展

【5】石志伟,吴功宜; 改善朴素贝叶斯在文本分类中的稳定性 [A];NCIRCS2004第一届全国信息检索与内容安全学术会议论文集 [C]; 2004年

【6】Jyotishman Pathak. Text Classification Using A Naïve Bayes Approaeh[J].Department of Computer Science lowa State University. 

【7】Aynur Akkus and H.Altay Guvenir.K Nearest Neighbor Classifications on Feature Projections[J].Dept.of Computer Engr.And info.Sci.Bilkent University,Ankara,Turkey.