简单朴素贝叶斯分类器的思想与算法分析.DOC

1、简单朴素贝叶斯分类器的思想与算法分析 1简单朴素贝叶斯分类器的思想与算法分析在数据仓库和数据挖掘应用中，分类是一种非常重要的方法分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型，即我们通常所说的分类器(Classifier)该函数或模型能够把数据集合中的数据记录映射到给定类别中的某一个值，从而可以应用于数据预测目前，分类的主要算法有贝叶斯算法、决策树算法（如ID3、C4.5 等） 、规则推导、人工神经网络、最近邻算法、支持向量机等等这些算法在许多现实数据集合上具有较好的预测精度其中朴素贝叶斯算法具有良好的可解释性等，在实践中的应用最为广泛朴素贝叶斯算法是基于统计理论的方法，它

2、能够预测所属类别的概率简单朴素贝叶斯分类器假设一个指定类别中各属性的取值是相互独立的这一假设称为给定类别条件下的独立性(Class Conditional Independence)假设，它可以有效减少在构造分类器时所需要的计算量简单朴素贝叶斯算法的分类模型是基于 Bayes 定理的，下面就简单介绍一下 Bayes 定理设 X 为一个类别未知的数据样本，H 为某个假设，C 表示类别集合，若数据样本 X 属于一个特定的类别 c，那么分类问题就是决定 P(H/X)，即在获得数据样本 X 时，H 假设成立的概率由于 P(H) , P(X), P(X/H)的概率值可以从（供学习使用的）数据集合中得到，

3、Bayes 定理描述了如何根据 P(H) , P(X), P(X/H)计算获得的 P(H/X)，有关的具体公式定义描述如下： (/)()(1)简单朴素贝叶斯分类器进行分类操作的步骤说明如下：1 每个数据样本均是由一个 n 维特征向量 X=x1,x2, , xn来描述其 n 个属性（A 1, A2, , An）的具体取值2 假设共有 m 个不同类别， C1, C2, , Cn给定一个未知类别的数据样本 X，分类器在已知样本 X 的情况下，预测 X 属于事后概率最大的那个类别也就是说，朴素贝叶斯分类器将未知类别的样本 X 归属到类别 Ci，当且仅当：P( Ci/X) P(Cj/X) 其中1j m,

4、ji也就是 P(Ci/X)最大其中的类别 Ci 就称为最大事后概率的假设，根据 Bayes 定理可知，(/)(/)iiiPXP(2)简单朴素贝叶斯分类器的思想与算法分析23 由于 P(X)对于所有的类别均是相同的，所以，要使公式（2）取得最大值，只需要 P(X/Ci)P(Ci)取最大即可类别的事前概率 P(Ci)可以通过公式 P(Ci)=si/s 进行估算，其中si 为训练样本集合类别 Ci 的个数，s 为整个训练样本集合的大小4 根据所给定包含多个属性的数据集，直接计算 P(X/Ci)的运算量是非常大的为实现对 P(X/Ci)的有效估算，朴素贝叶斯分类器通常都是假设各类别是相互独立的即各属性

5、的取值是相互独立的即： 1(/)(/)nikiPXx(3)可以根据训练数据样本估算 P(X1/Ci)，P( X2/Ci)，P(X n/Ci)的值，具体处理方法说明如下：若 Ak 是名称型属性 ,就有 P(Xk/Ci)=sik/si，这里 sik 为训练样本中类别为 Ci 且属性 Ak 的取值为 vk 的样本数，s i 为训练样本中类别为 Ci 的样本数若 Ak 是数值型属性 ,那么假设属性具有高斯分布，概率 P(Xk/Ci)就用概率密度 f(Xk/Ci)代替，即 2()1()(,)2iCii ixkikCfxge(4)其中， g(xk, ci, ci)为属性 Ak 的高斯规范密度函数， ci,

6、 ci 为训练样本中类别为 Ci的属性为 Ak 的均值和方差数值型属性的均值计算公式为： xmean=(x1+x2+xn)/n，其中 x1, x2, , xn 表示数值型属性的值， n 表示实例个数数值型属性的方差计算公式为：221()()()1meameannmeaxxDevs(5)其中 x1, x2, , xn 表示数值型属性的值， xmean 表示方差，n 表示实例个数5 为预测一个样本 X 的类别，可对每个类别 Ci 估算相应的 P(X/Ci)P(Ci)，样本 X 归属到类别 Ci，当且仅当：P(C i/X) P(Cj/X) 其中 1jm, j i也可通过求百分比 percent(Ci

7、)= P(Ci/X)/ P(Ck/X)，百分比最大值对应的类标就位样本X 的类别下面就以有关天气问题的数据为例仔细介绍一下朴素贝叶斯分类器进行分类的过程有关天气的数据如下表所示： outlook(类型)temperature(温度)humidity(湿度)windy(风)play(玩)sunny 85 85 False Nosunny 80 90 True Noovercast 83 86 False Yesrainy 70 96 False Yesrainy 68 80 False Yesrainy 65 70 True Noovercast 64 65 True Yessunny 72 9

8、5 False Nosunny 69 70 False yes简单朴素贝叶斯分类器的思想与算法分析 3rainy 75 80 False yessunny 75 70 True yesovercast 72 90 True yesovercast 81 75 False yesrainy 71 91 True no概率的表示方法：P(yes/sunny,80,76,false)=0.25 就表示在 outlook=sunny, temperature=80, humidity=76,windy=false 的条件下 paly=yes 条件概率为 0.251求得名称型属性的后验概率以 P(sun

9、ny/yes)为例进行详细说明首先，计算类标为 yes 的实例个数为 9 个，然后计算类标为 yes 并且 outlook 属性为 sunny 的实例个数为 2，所以 P(sunny/yes)=2/9，这是很自然的事情，为了避免有时该概率值为 0，需要对该概率值进行标准化：即分子加上属性outlook 值的个数，也就是 3（因为 outlook 的值有 sunny, rainy, overcast 三个） ，分母加上1，标准化后的条件概率 P(sunny/yes)=(2+1)/(9+3)=3/12重复上述步骤，可得属性 outlook的后验概率为：P(sunny/yes)=3/12 P(ove

10、rcast/yes)=5/12 P(rainy/yes)=4/12P(sunny/no)=4/8 P(overcast/no)=1/8 P(rainy/no)=3/8属性 windy 的后验概率为：P(false/yes)=7/11 P(false /yes)=4/11P(false/no)=3/7 P(false /no)=4/72求得数值型属性的均值数值型属性的均值计算公式为：x mean=(x1+x2+xn)/n，其中 x1, x2, , xn 表示数值型属性的值，n 表示实例个数下面就以求在 play=yes 的条件下数值型属性 temperature 的均值为例详细说明求解过程：me

11、an- temperature(yes)=(83+70+68+64+69+75+75+72+81)/9=73 同理：mean- temperature(no)=(85+80+65+72+71)/5=74.6mean- humidity(yes)=(86+96+80+65+70+80+70+90+75)/9=79.1mean- humidity(no)=(85+90+70+95+91/5=86.23求得数值型属性的方差数值型属性的方差计算公式为： 2221()()()1meanmeannmeaxxxDevs(6)其中 x1, x2, , xn 表示数值型属性的值， xmean 表示方差，n 表示

12、实例个数下面就以求在 play=yes 的条件下数值型属性 temperature 的方差为例详细说明求解过程Devs-temperature(yes)=(83-73)2+(70-73)2+(68-73)2+(64-73)2+(69-73)2+(75-73)2+(75-73)2+(72-73)2+(81-73)2)/9=6.2同理，可求得简单朴素贝叶斯分类器的思想与算法分析4Devs-temperature(no)=7.9Devs-humidity(no)=10.2Devs-humidity(no)=9.74求得类属性的先验概率以 P(yes)为例进行详细说明首先计算数据集的实例总数为 14，

13、然后计算类标为 yes的实例总数为 9，所以 P(yes)=9/14，为避免有时该概率值为 0，需要对该概率值进行标准化：即分子加上类属性 play 值的个数，也就是 2（因为 play 的值有 yes, no 二个） ，分母加上 1，标准化后的条件概率 P(yes)=(9+1)/(14+2)=10/16，同理可求得 P(no)=(5+1)/(14+2)=6/165根据上述参数计算待分类实例属于每个类的概率，选择概率值最大的类作为待分类实例的类标下面以实例（sunny，66，90，true）为例说明一下其分类过程：首先求 P(yes/sunny,66,90,true),根据 bayes 定理和

14、条件独立性假设，P(yes/sunny,66,90,true)=(P(yes)P(sunny/yes)P(true/yes)f(66/yes)f(90/yes)/P(sunny,66,90,true)由于 P(sunny,66,90,true)为常数，最后求类的百分比的时候可以抵消，可以不加考虑，而 P(66/yes)可用概率密度 f(66/yes)来代替，这对最后的求类的百分比也没有影响，所以我们只需求 P(yes)P(sunny/yes)P(true/yes) f(66/yes) f(90/yes)而 P(yes)，P(sunny/yes)，P(true/yes)已经求得，根据正态分布假设

15、，f (66/yes), f(90/yes) 也很容易求得 2(mean-tprtue(ys)2Dvs1(6/)2 Devs-tpratuey)xyes(6)2(673).0.4 .同理可求得 f(90/yes)=0.0221，所以：P(yes)P(sunny/yes)P(true/yes) f(66/yes) f(90/yes)=10/163/120.0340.02214/11=0.000043重复上述步骤可得：f(66/no)=0.0291，f(90/no)=0.0380，因而有：P(no)P(sunny/no)P(true/no) f(66/no) f(90/no)=6/164/84/7

16、0.02910.0380=0.00018所以，待分类实例属于类 yes 的百分比为probability-of-yes=0.000043/(0.000043+0.000118)=26.7%probability-of-no=0.000118/(0.000043+0.000118)=73.3%因此，待分类实例的类属性值为 no基于本文所述 ID3 的基本思想， ID3 的具体算法是：下面我们介绍一下其算法实现的有关细节我们所介绍的 ID3 程序是在 weka 系统下利用 java 语言编写的分类器程序该程序主要包括以下几个方法：globalInfo()简单朴素贝叶斯分类器的思想与算法分析 5返回

17、该分类器的描述字符串BuildClassifier(Instances instances)BuildClassifier()方法从一个训练数据集合 instances 构造一个分类器求出所有名称型属性的后验概率，类属性的先验概率，数值属性的均值和方差，为后来的分类工作做准备distributionForInstance (Instance instance)该方法计算待分类实例 instance 属于各个类标的百分比，并且将各个百分比数值存于一个数组中，最后返回该数组toString()把分类器的参数（均值，方差，各先验概率，各后验概率）以字符串的形式返回normalDens(double

18、x, double mean, double stdDev)该方法用于根据正态分布（均值为 mean，方差为 stdDev）计算数值型属性当属性值为x 时的概率密度Main()当类从命令行被执行时，就会调用 main()方法它只是用所给的命令行选项告诉 Weka的 Evaluation 类来评估朴素贝叶斯，并且打印所得到的数组完成这个功能的一行表达式包括在 try-catch 声明中try-catch 声明用于发现 Weka 例程或其它 Java 方法中抛出的各种异常附一：朴素贝叶斯源程序及其注解：/* This program is free software; you can redist

19、ribute it and/or modify* it under the terms of the GNU General Public License as published by* the Free Software Foundation; either version 2 of the License, or* (at your option) any later version.* This program is distributed in the hope that it will be useful,* but WITHOUT ANY WARRANTY; without ev

20、en the implied warranty of* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the* GNU General Public License for more details.* You should have received a copy of the GNU General Public License* along with this program; if not, write to the Free Software简单朴素贝叶斯分类器的思想与算法分析6* Foundation, Inc.,

21、 675 Mass Ave, Cambridge, MA 02139, USA./* 本程序为免费软件;你可以通过免费软件中心的发布的 GNU 公共许可的任何版本下下重写或者修改它.* 开发本程序的目的是是希望它是有用的,但没有任何授权,甚至没有潜在的商用或其它特殊目的的授权.* 想要了解更多细节,请参阅 GNU 公共许可.*在拿到程序的同时,你应该收到 GNU 公共许可; 假如没有的话 ,请致函免费软件中心Inc., 675 MassAve, Cambridge, MA 02139, USA./* NaiveBayesSimple.java* Copyright (C) 1999 Eibe

22、Frank*/package weka.classifiers.bayes;import weka.classifiers.Classifier; import weka.classifiers.Evaluation; import java.io.*;import java.util.*;import weka.core.*;/* Class for building and using a simple Naive Bayes classifier.* Numeric attributes are modelled by a normal distribution. For more* i

23、nformation, see* Richard Duda and Peter Hart (1973).Pattern* Classification and Scene Analysis. Wiley, New York.* author Eibe Frank (eibecs.waikato.ac.nz)* version $Revision: 1.15 $简单朴素贝叶斯分类器的思想与算法分析 7*/*创建和使用 Naive Bayes 分类器的类*数值型属性均符合正态分布*/public class NaiveBayesSimple eXtends Classifier /分类器的构造函数

24、public NaiveBayesSimple() try jbInit(); /分类器初始化 catch (EXception eX) eX.printStackTrace(); /创建分类器对象时若出现异常则输出堆栈信息/* All the counts for nominal attributes. 所有名称型属性的计数数组 */protected double m_Counts; /*属于每个类每个名称型属性的每个取值的个数数组,其中第一维表示类名,第二维表示属性名,第三维表示属性值,比如 m_Countsyesoutlooksunny*/* The means for numeric

25、 attributes. 数值型属性的均值数组 */protected double m_Means; /*数值型属性的均值数组,其中第一维表示类名, 第二维表示属性名,比如 m_Meansnotemperature, 公式为：12nmeanxx (7)*/* The standard deviations for numeric attributes.数值型属性的标准差数组 */protected double m_Devs; /*数值型属性的标准差数组，其中第一维表示类名，第二维表示属性名，比如 m_Devsnotemperature，公式为：2221()()()1meanmeannmea

26、xxxDevs(8)*/* The prior probabilities of the classes. 每个类的先验概率数组 */protected double m_Priors; /每个类的先验概率,第一维表示类名,比如 m_Prioryes/* The instances used for training. 用于训练的实例*/protected Instances m_Instances; /定义用于训练的实例/* Constant for normal distribution. 正态分布常量*/protected static double NORM_CONST = Math.

27、sqrt(2 * Math.PI); /正态分布常量 2简单朴素贝叶斯分类器的思想与算法分析8/* Returns a string describing this classifier* return a description of the classifier suitable for* displaying in the eXplorer/eXperimenter gui*/*返回该分类器的描述字符串*返回适合于图形界面用户的分类器的描述*/方法一：public String globalInfo() /返回该分类器的描述字符串return “Class for building an

28、d using a simple Naive Bayes classifier.“+“Numeric attributes are modelled by a normal distribution. For more “+“information, seenn“+“Richard Duda and Peter Hart (1973). Pattern “+“Classification and Scene Analysis. Wiley, New York.“;/* Generates the classifier.* param instances set of instances ser

29、ving as training data* eXception EXception if the classifier has not been generated successfully*/* 构造分类器* 参数 instances 表示训练例集合* 若分类器不正正常构造,则出现异常提示*/方法二：public void buildClassifier(Instances instances) throws EXception / 构造分类器简单朴素贝叶斯分类器的思想与算法分析 9int attIndeX = 0; /属性索引double sum; /属于每个类的每个名称型属性的总个数i

30、f (instances.checkForStringAttributes() throw new UnsupportedAttributeTypeEXception(“Cannot handle string attributes!“); /若实例集合为 string 型则提示异常if (instances.classAttribute().isNumeric() throw new UnsupportedClassTypeEXception(“Naive Bayes: Class is numeric!“); /若实例集合的类属性为数值型则提示异常m_Instances = new Ins

31、tances(instances, 0); /空实例/ Reserve space 为数组 m_Counts,m_Means,m_Devs,m_Priors分配空间m_Counts = new doubleinstances.numClasses() instances.numAttributes() - 10; /*属于每个类每个名称型属性的每个取值的个数数组 ,其中第一维表示类名,第二维表示属性名,第三维表示属性值,instances.numClasses() 返回实例集的类值的个数,instances.numAttributes()返回实例集的属性个数,包括类属性,这也是第二维减一的原因

32、,第三维之所以为零是 因为后续分配空间的方便*/m_Means = new doubleinstances.numClasses() instances.numAttributes() - 1;/*数值型属性的均值数组,其中第一维表示类名 , 第二维表示属性名,instances.numClasses()返回实例集的类值的个数 , instances.numAttributes()返回实例集的 属性个数,包括类属性,这也是第二维减一的原因, */m_Devs = new doubleinstances.numClasses()instances.numAttributes() - 1;/*数值

33、型属性的标准差数组,其中第一维表示类名 , 第二维表示属性名,instances.numClasses()返回实例集的类值的个数 , instances.numAttributes()返回实例集的 属性个数,包括类属性,这也是第二维减一的原因, */m_Priors = new doubleinstances.numClasses(); /*每个类的先验概率数组,第一维表示类名 ,instances.numClasses()返回实例集的类值的个数, */第一步：Enumeration enu = instances.enumerateAttributes(); /返回一个实例集的属性集whil

34、e (enu.hasMoreElements() /遍历实例集的每个属性,为 m_Counts分配简单朴素贝叶斯分类器的思想与算法分析10空间Attribute attribute = (Attribute) enu.neXtElement(); /循环从属性集中取每个属性if (attribute.isNominal() /属性若为名称型属性for (int j = 0; j instances.numClasses(); j+) /遍历类m_CountsjattIndeX = new doubleattribute.numValues();/*为属于每个类的每个名称型属性的每个取值的个数数

35、组 m_Counts预留空间,attribute.numValues()返回属性 attibute 的值的个数. */ else /属性若为数值型属性for (int j = 0; j instances.numClasses(); j+) /遍历类m_CountsjattIndeX = new double1; /若该属性不为名称型属性,则数组初始化为长度为 1 的一维数组attIndeX+; /属性索引加一,执行下一个属性第二步：Enumeration enu = instances.enumerateAttributes(); /返回一个实例集的属性集while (enu.hasMore

36、Elements() /遍历实例集的每个属性,为 m_Counts分配空间Attribute attribute = (Attribute) enu.neXtElement(); /循环从属性集中取每个属性if (attribute.isNominal() /属性若为名称型属性for (int j = 0; j instances.numClasses(); j+) /遍历类m_CountsjattIndeX = new doubleattribute.numValues(); /*为属于每个类的每个名称型属性的每个取值的个数数组 m_Counts预留空间,attribute.numValues()返回属性 attibute 的值的个数. */ else /属性若为数值型属性for (int j = 0; j instances.numClasses(); j+) /遍历类m_CountsjattIndeX = new double1; /若该属性不为名称型属性,则数组初始化为长度为 1 的一维数组attIndeX+; /属性索引加一,执行下一个属性