朴素贝叶斯.docx

朴素贝叶斯文本分类算法 (刘世刚 大连海洋大学 研究生学院 捕捞学)摘 要朴素贝叶斯分类器是一种简单而高效的分类器，基于朴素贝叶斯技术的分 类是当前数据挖掘领域的一个研究热点。本文以突破朴素贝叶斯分类模型属性 间独立性假设限制为研究内容，从两个方面对朴素贝叶斯分类模型进行了深入 的研究，并将朴素贝叶斯分类模型应用于指导学生选择专业方向。 本文主要工作如下：(1)基于属性相关性分析是改进朴素贝叶斯分类模型的结构。通过分析属 性相关性度量和进行属性约简，得到满意的属性约简子集。在此基础上提出一 种基于厲性相关性度量的朴素贝叶斯分类模型EANBC。实验结果表明，与朴 素贝叶斯分类模型相比，EANBC分类模型具有较高的分类正确率。(2)基于强属性限定是对朴素贝叶斯分类模型的结构进行了扩展。通过分 折贝叶斯定理的变形公式和属性相关性度量，提出一种基于强属性限定的贝叶 斯分类模型EANBC已实验结果表明，与朴素贝叶斯分类模型相比，EANBC分类椟型具有较高的分类正确率。(3)将朴素贝叶斯分类模型应用于指导学生选择专业方向。通过建立专业 方向选择的朴素贝叶斯分类模型，充分利用以往各届学生选择专业方向的先验 知识，指导学生根据自己的专业知识结构以及专业知识的掌握程度科学合理地 选择专业方向。关键词：贝叶斯定理朴素贝叶斯分类模型属性相关性属性约简前言随着人类迈入崭新的信息时代，信息资源与0俱增，尤其近年来随着计算 机科学技术的迅猛发展、数据库和计算杌网络的广泛应用5使数据库领域的新内 容、新应用、新技术层出不穷，产生大量的数据信息。数据的丰富带来了对强 有力的数据分析工具的需求，数据挖掘就是在这种背景下产生并成为当前人智 能领域的研究热点。本章概述了数据挖掘的研究和发展概况，重点介绍了其中 的分类问题，此外还给出了本文的内容组织。 1.1数据挖掘概述 1,1.1什么是数据挖掘数据挖掘也称数据库中的知识发现是指从大型数据库或数据仓库中提取人们感兴趣的知 识的过程，这些知识是隐含的、事先未知的、潜在有用的信息。提取的知I只一 般可表示为概念规则、规律、模式等形式。用数据库系统来存储数据，用机器学习的方法分析数据，挖掘大量数 据背后蕴含的知识，这两者的结合促成了数据挖掘技术的产生。数据挖掘作为 一门交叉学科，涉及到机器学习、模式识别、归纳推理、统计学、智能数据库、 数据可视化、专家系统、髙性能计算等多个领域。数据挖掘技术的提出和广泛的接受是由于计算机及其相关技术的发展为其 提供了研究和应用的技术基础。归纳数裾挖掘产生的技术背景，下面一些相关 技术的发展起到了决定性的作用：1、数据库、数据仓库和Internet等信息技术的发展；2、计算机性能的提高和先进的体系结构的发展；3、统计学和人工智能等方法在数据分析中的研究和应用。计算机芯片技术的发展使计算机的处理和存储能力曰益提高；计算机的体 系结构，特别是并行处理技术的3趋成熟和普遍应用，已成为支持大型数据库 处理应用的基础；计算机性能的提高和先进的体系结构的发展使数据挖掘技术 的研究和应用成为可能。历经几十年的发展，包括基于统计学、人工智能等在内的理论与技术成果 已经被成功地应用到数据的处理和分析中，这些应用从某种意义上为数据挖掘 技术的提出和发展起到了极大的推动作用。正是由于实际的需求和相关技术的 发展，数据挖掘技术才遂步发展起来。目前数据挖掘技术已成为国际上数据库 和信息决策领域的最前沿的研究方向之一。目前，对数据挖掘的研究主要体现在以下几个方面：一是对知识发现方法的 研究进一步发展，如近年来注重对8吵衍丨贝叶斯方法以及800由叩方法的研 究；二是传统的统计学回归法在数据挖掘中的应用；三是数据挖掘技术与数据 库的结合越来越紧密。在应用方面数据挖掘商业软件工具不断产生和完善，国外很多计算机公司非常重视数据挖掘系统的开发应用,比较典型的有SAS公司的Enterprise Miner，IBM公司的Intelligent miner, miner，SGI公司的Setlliner，SPSS公司的Clementine等。数据挖掘的研究趋势体现在以下几个方面:(1)挖掘方法和用户交互问题：这反映在所挖掘的知识类烈、在多粒度上挖掘知识能力、领域知识的使用、特定的挖掘积知识显示；(2)性能问题：包括数据挖掘算法的有效性、可伸缩性和并行处理以及分布式和增量挖掘算法：(3)挖掘中的可视化方法：使得知识发现的过程能够被用户理解，也便于在妇识发现遥程中的人梳交互；(4)加强对各种非结构化数据的挖掘：如文本数据、图形图象数据、多媒体数据：(5)研究在皤络环境下的数据挖撼技术：特别是在Internet上建立DM Server与数据库服务器配合，实现数据挖掘。分类算法的比较研究发现，一种称作朴素贝叶斯分类的简单贝叶斯分类算法可以与决策树和神经网络分类算法相媲美。用于大型数据库，贝叶斯分类也己表现出高准确率与高速度。例如文献中，Lewis与Ringuette用实验验证了，贝叶斯分类器比决策树分类器有更好的性能。第一章 朴素贝叶斯(Naive Bayes)模型贝叶斯定理给出了最小化误差的最优解决方法，可用于分类和预测，理论上它看起来很完美，但在实际中它并不能被直接利用，因为它需要知道证据的确切分布概率，而实际上我们并不能确切地给出证据的分布概率。为了使用贝叶斯定理来分类，在很多分类方法为了使用贝叶斯定理来分类，在很多分类方法中都做出某种假设以逼近贝叶斯定理的要求，朴素贝叶斯分类方法就是其中的一种，图1 直观地描述了朴素贝叶斯分类模型的结构特点。该模型中，假设所有的属性都独立于类变量，即每一个属性变量都以类变量作为惟一的父节点。这种假设大大降低了计算的复杂度，简化所需的计算，且具有较高的精确度，这一假设称作条件独立。做此假定是为了简化所需的计算，并在此意义下称为“朴素的”。这种假设大大降低了计算的复杂度，且具有较高的精确度。使用Naive Bayes模型进行分类的做法是通过概率计算，从待分类的实例的属性值al,a2,an求出最可能的分类目标值，其工作过程如下：（1）每个数据样本用一个n维特征向量=x1,x2,x3,xn表示，分别描述对n个属性Al,A2,A3,An样本的n个度量。（2）假定有m个类C1,C2,Cm。给定一个未知的数据样本(即没有类标号)，分类法将预测x属于具有最高后验概率(条件下)的类。即是说，朴素贝叶斯分类将未知的样本分配给类 i，当且仅当P(i/)(j/)，1jm, ji。P(i/)最大的类Ci称为最大后验假定。（3）根据贝叶斯定理，由于P(X)对于所有类为常数，要最大化P(Ci/X)只要P(X/Ci)P(Ci)最大化即可。如果类的先验概率未知，则通常假定这些类是等概率的，即P(Cl)=P(C2)=P(Cm)，并据此只对P(X/Ci)最大化，否则对P(X/Ci)P(Ci)最大化，P(Ci)可用P(Ci)=si/s来计算，其中，si是类i中的训练样本数，s 是训练样本总数。（4） 给定的样本具有许多属性时，计算P(/Ci)的开销可能很大。为降低计算P(X/Ci)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样就有:概率P(X/Ci)，P(X2/Ci) ，P(Xn/Xi)可由训练样本估值，其中如果Ak是分类属性，则P(Xk/Ci) = sik/si，其中sik是在属性Ak上具有值Xk的类Ci的训练样本数，而Si是Ci中的训练样本数。如果Ak是连续属性，则通常假定该属性服从高斯分布。（5）对未知样本分类，对每个类Ci，计算P(P/Ci)P(Ci)。样本被指派到类Ci，当且仅当P(X/Ci)P(Ci)P(Cj/X)P(Cj)，ijm，ji，也就是说X被指派到其P(X/Ci)P(Ci)最大的类Ci。第二章 基于朴素贝叶斯的文本分类算法2.1文本分类问题在文本分类中，假设我们有一个文档dX，X是文档向量空间(document space)，和一个固定的类集合C=c1,c2,cj，类别又称为标签。显然，文档向量空间是一个高维度空间。我们把一堆打了标签的文档集合作为训练样本，XC。例如：=Beijing joins the World Trade Organization, China对于这个只有一句话的文档，我们把它归类到 China，即打上china标签。我们期望用某种训练算法，训练出一个函数，能够将文档映射到某一个类别：:XC这种类型的学习方法叫做有监督学习，因为事先有一个监督者（我们事先给出了一堆打好标签的文档）像个老师一样监督着整个学习过程。朴素贝叶斯分类器是一种有监督学习，常见有两种模型，多项式模型(multinomial model)和伯努利模型(Bernoulli model)。2.2多项式模型1、基本原理在多项式模型中， 设某文档d=(t1,t2,tk)，tk是该文档中出现过的单词，允许重复，则先验概率P(c)= 类c下单词总数/整个训练样本的单词总数类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+1)/(类c下单词总数+|V|)V是训练样本的单词表（即抽取单词，单词出现多次，只算一个），|V|则表示训练样本包含多少种单词。在这里，m=|V|, p=1/|V|。P(tk|c)可以看作是单词tk在证明d属于类c上提供了多大的证据，而P(c)则可以认为是类别c在整体上占多大比例(有多大可能性)。2、伪代码/C，类别集合，D，用于训练的文本文件集合TrainMultiNomialNB(C,D) / 单词出现多次，只算一个VExtractVocabulary(D)/ 单词可重复计算NCountTokens(D)for each cC/ 计算类别c下的单词总数/ N和Nc的计算方法和Introduction to Information Retrieval上的不同，个人认为/该书是错误的，先验概率和类条件概率的计算方法应当保持一致NcCountTokensInClass(D,c)priorcNc/N/ 将类别c下的文档连接成一个大字符串textcConcatenateTextOfAllDocsInClass(D,c)for each tV/ 计算类c下单词t的出现次数TctCountTokensOfTerm(textc,t)for each tV/计算P(t|c)condprobtcreturn V,prior,condprobApplyMultiNomialNB(C,V,prior,condprob,d) / 将文档d中的单词抽取出来，允许重复，如果单词是全新的，在全局单词表V中都/ 没出现过，则忽略掉WExtractTokensFromDoc(V,d)for each cCscorecpriorcfor each tWif tVdscorec *= condprobtcreturn max(scorec)3、举例给定一组分类好了的文本训练数据，如下：docIddoc类别In c=China?1Chinese Beijing Chineseyes2Chinese Chinese Shanghaiyes3Chinese Macaoyes4Tokyo Japan Chineseno给定一个新样本Chinese Chinese Chinese Tokyo Japan，对其进行分类。该文本用属性向量表示为d=(Chinese, Chinese, Chinese, Tokyo, Japan)，类别集合为Y=yes, no。类yes下总共有8个单词，类no下总共有3个单词，训练样本单词总数为11，因此P(yes)=8/11, P(no)=3/11。类条件概率计算如下：P(Chinese | yes)=(5+1)/(8+6)=6/14=3/7P(Japan | yes)=P(Tokyo | yes)= (0+1)/(8+6)=1/14P(Chinese|no)=(1+1)/(3+6)=2/9P(Japan|no)=P(Tokyo| no) =(1+1)/(3+6)=2/9分母中的8，是指yes类别下textc的长度，也即训练样本的单词总数，6是指训练样本有Chinese,Beijing,Shanghai, Macao, Tokyo, Japan 共6个单词，3是指no类下共有3个单词。有了以上类条件概率，开始计算后验概率，P(yes | d)=(3/7)31/141/148/11=108/1848770.00058417P(no | d)= (2/9)32/92/93/11=32/2165130.00014780因此，这个文档属于类别china。2.3伯努利模型1、基本原理P(c)= 类c下文件总数/整个训练样本的文件总数P(tk|c)=(类c下包含单词tk的文件数+1)/(类c下单词总数+2)在这里，m=2, p=1/2。后验概率的计算，也有点变化，见下面的伪代码。2、伪代码/C，类别集合，D，用于训练的文本文件集合TrainBernoulliNB(C, D) / 单词出现多次，只算一个VExtractVocabulary(D)/ 计算文件总数NCountDocs(D)for each cC/ 计算类别c下的文件总数NcCountDocsInClass(D,c)priorcNc/Nfor each tV/ 计算类c下包含单词t的文件数NctCountDocsInClassContainingTerm(D,c,t)/计算P(t|c)condprobtc(Nct+1)/(Nct+2)return V,prior,condprobApplyBernoulliNB(C,V,prior,condprob,d) / 将文档d中单词表抽取出来，如果单词是全新的，在全局单词表V中都没出现过，/ 则舍弃VdExtractTermsFromDoc(V,d)for each cCscorecpriorcfor each tVif tVdscorec *= condprobtcelsescorec *= (1-condprobtc)return max(scorec)3、举例还是使用前面例子中的数据，不过模型换成了使用伯努利模型。类yes下总共有3个文件，类no下有1个文件，训练样本文件总数为11，因此P(yes)=3/4, P(Chinese | yes)=(3+1)/(