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

简单朴素贝叶斯分类器的思想与算法分析1简单朴素贝叶斯分类器的思想与算法分析在数据仓库和数据挖掘应用中，分类是一种非常重要的方法．分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型，即我们通常所说的分类器(Classifier)．该函数或模型能够把数据集合中的数据记录映射到给定类别中的某一个值，从而可以应用于数据预测．目前，分类的主要算法有贝叶斯算法、决策树算法（如ID3、C4.5等）、规则推导、人工神经网络、最近邻算法、支持向量机等等．这些算法在许多现实数据集合上具有较好的预测精度．其中朴素贝叶斯算法具有良好的可解释性等，在实践中的应用最为广泛．朴素贝叶斯算法是基于统计理论的方法，它能够预测所属类别的概率．简单朴素贝叶斯分类器假设一个指定类别中各属性的取值是相互独立的．这一假设称为给定类别条件下的独立性(ClassConditionalIndependence)假设，它可以有效减少在构造分类器时所需要的计算量．简单朴素贝叶斯算法的分类模型是基于Bayes定理的，下面就简单介绍一下Bayes定理．设X为一个类别未知的数据样本，H为某个假设，C表示类别集合，若数据样本X属于一个特定的类别c，那么分类问题就是决定P(H/X)，即在获得数据样本X时，H假设成立的概率．由于P(H),P(X),P(X/H)的概率值可以从（供学习使用的）数据集合中得到，Bayes定理描述了如何根据P(H),P(X),P(X/H)计算获得的P(H/X)，有关的具体公式定义描述如下：(/)()(/)()PXHPHPHXPX(1)简单朴素贝叶斯分类器进行分类操作的步骤说明如下：1．每个数据样本均是由一个n维特征向量X={x1,x2,……,xn}来描述其n个属性（A1,A2,……,An）的具体取值．2．假设共有m个不同类别，{C1,C2,……,Cn}．给定一个未知类别的数据样本X，分类器在已知样本X的情况下，预测X属于事后概率最大的那个类别．也就是说，朴素贝叶斯分类器将未知类别的样本X归属到类别Ci，当且仅当：P(Ci/X)P(Cj/X)其中1≤j≤m,j≠i．也就是P(Ci/X)最大．其中的类别Ci就称为最大事后概率的假设，根据Bayes定理可知，(/)()(/)()iiiPXCPCPCXPX(2)3．由于P(X)对于所有的类别均是相同的，所以，要使公式（2）取得最大值，只需要P(X/Ci)P(Ci)取最大即可．类别的事前概率P(Ci)可以通过公式P(Ci)=si/s进行估算，其中si为训练样本集合类别Ci的个数，s为整个训练样本集合的大小．简单朴素贝叶斯分类器的思想与算法分析24．根据所给定包含多个属性的数据集，直接计算P(X/Ci)的运算量是非常大的．为实现对P(X/Ci)的有效估算，朴素贝叶斯分类器通常都是假设各类别是相互独立的即各属性的取值是相互独立的．即：1(/)(/)nikikPXCPxC(3)可以根据训练数据样本估算P(X1/Ci)，P(X2/Ci)，……，P(Xn/Ci)的值，具体处理方法说明如下：若Ak是名称型属性,就有P(Xk/Ci)=sik/si，这里sik为训练样本中类别为Ci且属性Ak的取值为vk的样本数，si为训练样本中类别为Ci的样本数．若Ak是数值型属性,那么假设属性具有高斯分布，概率P(Xk/Ci)就用概率密度f(Xk/Ci)代替，即22()21()(,,)2CiCiiiixkikCCCfxCgxe(4)其中，g(xk,μci,δci)为属性Ak的高斯规范密度函数，μci,δci为训练样本中类别为Ci的属性为Ak的均值和方差．数值型属性的均值计算公式为：xmean=(x1+x2+……+xn)/n，其中x1,x2,……,xn表示数值型属性的值，n表示实例个数．数值型属性的方差计算公式为：22212()()()1meanmeannmeanxxxxxxDevsn(5)其中x1,x2,……,xn表示数值型属性的值，xmean表示方差，n表示实例个数．5．为预测一个样本X的类别，可对每个类别Ci估算相应的P(X/Ci)P(Ci)，样本X归属到类别Ci，当且仅当：P(Ci/X)P(Cj/X)其中1≤j≤m,j≠i．也可通过求百分比percent(Ci)=P(Ci/X)/∑P(Ck/X)，百分比最大值对应的类标就位样本X的类别．下面就以有关天气问题的数据为例仔细介绍一下朴素贝叶斯分类器进行分类的过程．有关天气的数据如下表所示：outlook(类型)temperature(温度)humidity(湿度)windy(风)play(玩)sunny8585FalseNosunny8090TrueNoovercast8386FalseYesrainy7096FalseYesrainy6880FalseYesrainy6570TrueNoovercast6465TrueYessunny7295FalseNosunny6970Falseyesrainy7580Falseyessunny7570Trueyesovercast7290Trueyesovercast8175Falseyesrainy7191Trueno简单朴素贝叶斯分类器的思想与算法分析3概率的表示方法：P(yes/sunny,80,76,false)=0.25就表示在outlook=sunny,temperature=80,humidity=76,windy=false的条件下paly=yes条件概率为0.25．1．求得名称型属性的后验概率以P(sunny/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/12P(overcast/yes)=5/12P(rainy/yes)=4/12P(sunny/no)=4/8P(overcast/no)=1/8P(rainy/no)=3/8属性windy的后验概率为：P(false/yes)=7/11P(false/yes)=4/11P(false/no)=3/7P(false/no)=4/72．求得数值型属性的均值数值型属性的均值计算公式为：xmean=(x1+x2+……+xn)/n，其中x1,x2,……,xn表示数值型属性的值，n表示实例个数．下面就以求在play=yes的条件下数值型属性temperature的均值为例详细说明求解过程：mean-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．求得数值型属性的方差数值型属性的方差计算公式为：22212()()()1meanmeannmeanxxxxxxDevsn(6)其中x1,x2,……,xn表示数值型属性的值，xmean表示方差，n表示实例个数．下面就以求在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同理，可求得Devs-temperature(no)=7.9Devs-humidity(no)=10.2Devs-humidity(no)=9.7简单朴素贝叶斯分类器的思想与算法分析44．求得类属性的先验概率以P(yes)为例进行详细说明．首先计算数据集的实例总数为14，然后计算类标为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/16．5．根据上述参数计算待分类实例属于每个类的概率，选择概率值最大的类作为待分类实例的类标．下面以实例（sunny，66，90，true）为例说明一下其分类过程：首先求P(yes/sunny,66,90,true),根据bayes定理和条件独立性假设，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)已经求得，根据正态分布假设，f(66/yes),f(90/yes)也很容易求得．22(mean-temperature(yes))2(Devs-temperature(yes))1(66/)2Devs-temperature(yes)xfyese(6)22(6673)26.210.03426.2e同理可求得f(90/yes)=0.0221，所以：P(yes)P(sunny/yes)P(true/yes)f(66/yes)f(90/yes)=10/16×3/12×0.034×0.0221×4/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/16×4/8×4/7×0.0291×0.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()返回该分类器的描述字符串．BuildClassifier(Instancesinstances)BuildClassifier()方法从一个训练数据集合instances构造一个分类器．求出所有名称型属性的后验概率，类属性的先验概率，数值属性的均值和方差，为后来的分类工作做准备．简单朴素贝叶斯分类器的思想与算法分析5distributionForInstance(Instanceinstance)该方法计算待分类实例instance属于各个类标的百分比，并且将各个百分比数值存于一个数组中，最后返回该数组．toString()把分类器的参数（均值，方差，各先验概率，各后验概率）以字符串的形式返回．normalDe