朴素贝叶斯

朴素贝叶斯在符号型数据库分类中的实现王海波河北大学数学与计算机学院DepartmentofMathematicsandComputerScienceHebeiUniversity结构重点贝叶斯理论贝叶斯分类器实验结果与分析参考文献重点：朴素贝叶斯在符号型数据库上的实现这里所说的符号型数据库是指属性的取值满足以下特点：离散无序有限无运算Ω={A1×A2×...×Am}，是由所有未知类别的可能样本组成的集合；Ωc={A1×A2×...×Am×C}是由所有已知类别的样本组成的集合。DΩc是训练样例集合。Ω中的元素x表示为x=a1,a2,…,am。Ωc中的元素x表示为x=a1,a2,…,am,cj。其中ai表示第i个属性的某个取值。描述用到的符号我们用Ai表示第i个属性，C表示决策属性；aik表示第i个属性的第k个取值，cj表示第j类；加上绝对值则表示相应的个数，如|Ai|表示第i个属性的取值个数，|cj|表示第j类样例个数。贝叶斯定理设x∈Ω是一个类别未知的数据样本，cj为某个类别，若数据样本x属于一个特定的类别cj，那么分类问题就是决定P(cj|x)，即在获得数据样本x时，确定x的最佳分类。所谓最佳分类，一种办法是把它定义为在给定数据集D中不同类别cj先验概率的条件下最可能（mostprobable）分类。贝叶斯理论提供了计算这种可能性的一种直接方法更精确地讲，贝叶斯法则基于假设的先验概率、给定假设下观察到不同数据的概率，提供了一种计算假设概率的方法贝叶斯公式先验概率P(cj)P(cj|x)=P(x|cj)P(cj)P(x)联合概率P(x|cj)后验概率P(cj|x)如果没有这一先验知识，那么可以简单地将每一候选类别赋予相同的先验概率。不过通常我们可以用样例中属于cj的样例数|cj|比上总样例数|D|来近似，即先验概率P(cj)P(cj)代表还没有训练数据前，cj拥有的初始概率。P(cj)常被称为cj的先验概率(priorprobability)，它反映了我们所拥有的关于cj是正确分类机会的背景知识,它应该是独立于样本的。jj|c|P(c)=|D|联合概率是指当已知类别为cj的条件下，看到样本x出现的概率。联合概率P(x|cj)若设x=a1,a2…am则P(x|cj)=P(a1,a2…am|cj)后验概率P(cj|x)即给定数据样本x时cj成立的概率,而这正是我们所感兴趣的P(cj|x)被称为C的后验概率（posteriorprobability），因为它反映了在看到数据样本x后cj成立的置信度贝叶斯分类我们现在计算P(cMAP|x)=maxP(cj|x)j∈(1,|C|)则P(cMAP|x)称为最大后验概率然后我们就把x分到cMAP类中朴素贝叶斯分类器一设x=a1,a2…am，为一个有m个属性的样例=maxP(a1,a2…am|cj)P(cj)P(a1,a2…am)=maxP(a1,a2…am|cj)P(cj)(1)P(cMAP|x)=maxP(cj|x)j∈(1,|C|)=maxP(cj|a1,a2…am)朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2…am的概率正好是对每个单独属性的概率乘积朴素贝叶斯分类器二12mjij1P(a,a,...,a|c)=P(a|c)mi(2)将(2)式其代入(1)式中，可得到朴素贝叶斯分类器，如下朴素贝叶斯分类器三概括地讲，朴素贝叶斯学习方法需要估计不同的P(cj)和P(ai|cj)项，也就是它们在训练数据上的频率。然后使用公式(3)来分类新实例。ijP(a|c)1miCNB=argmaxP(cj)jcC（3）其中CNB表示朴素贝叶斯分类器输出的目标值。注意在朴素贝叶斯分类器中，须从训练数据中估计的不同P(ai|cj)项的数量只是不同的属性值数量乘以不同目标值数量——这比要估计P(a1,a2…am|cj)项所需的量小得多||()||jjcPcD||(|)||iijijjAaCcPacCc举例说明目标概念PlayTennis的训练样例DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo第一步统计个数表1类别为cj及在cj条件下Ai取ai的样例数OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong2432433663Yes93022214123No5估计先验概率和条件概率表2先验概率P(cj)和条件概率P(ai|cj)OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong0.2220.4440.3330.2220.4440.3330.3330.6670.6670.333Yes0.6430.600.40.40.40.20.80.20.40.6No0.357样例判别现在假设有一个样例xx={Sunny,Hot,High,Weak}等于yes的概率P(Yes|x)=p(Yes)*p(Sunny|Yes)*p(Hot|Yes)*p(High|Yes)*p(Weak|Yes)*=0.643*0.222*0.222*0.333*0.667=0.007039等于No的概率P(No|x)=p(No)*p(Sunny|No)*p(Hot|No)*p(High|No)*p(Weak|No)*=0.357*0.6*0.4*0.8*0.4=0.027418max(P(Yes|x),P(No|x))=P(No|x),所以我们把x分类为No概率为零在大多数情况下，观察到的比例P(ai|cj)是对其真实概率的一个良好估计，但当|Ai=ai∧C=cj|很小时估计较差。特别是当|Ai=ai∧C=cj|等于0时，P(ai|cj)也等于0，如果将来的待估样例中，包含第i个属性的取值ai时，此概率项会在分类器中占统治地位。概率为零之m-估计一般采用m-估计来解决这个问题。m-估计定义如下：ijijnmpnm||,||ijiikjjjnAaCcnCcpi是将要确定的概率P(ai|cj)的先验概率，而m是等效样本大小的常量，它确定了对于观察到的数据如何衡量pi的作用。在缺少其他信息是选择p的一种典型方法是假定pi=1/|Ai|。也就是将nj个实际观察扩大，加上m个按pi分布的虚拟样本。概率为零之个数比较在本次实现中我们采用的不是m-估计，而是下面一种简单的0个数比较法。即下面的几条规则。在公式（3）中，对每一个类别j，统计P(ai|cj)=0的个数，记为zj。然后按以下3条规则得到CNB。1.如果对任意的j，zj都为0，则直接按公式（3）得到CNB3.如果对任意的j，zj不为0且不相等，则取zj最小者对应的类别作为CNB。若zj最小者不唯一，则对这些最小值对应的j采用第二条规则进行判别。2.如果对任意的j，zj不为0且相等，则按公式（3）计算时只计算P(ai|cj)为非零的项,然后得到CNB实验结果数据库训练样例测试样例训练精度标准差测试精度标准差BALANCE5716391.40.00387.40.056Hatehi1481689.20.01187.10.053heart2512886.10.00583.90.033Mushroom654672799.50.00099.50.003TIC-TAC-TOE8719671.00.01070.00.055结果分析从上面的实验结果我们可以得到朴素贝叶斯分类器的以下几个特点:训练精度≈测试精度意义明确,便于理解时间复杂度低,可以应用大型数据库易于实现增量参考文献1ZhuMing.DataMing.Anhui:UniversityofScienceandtechnologyofChina,2002(inChinese)（朱明.数据挖掘.安徽:中国科技大学出版社,2002）2TomM.Mitchell.MachineLearning.Beijing:ChinaMachinePress,2003Thanks!