机器学习-朴素贝叶斯学习-原理分析与C语言代码实现

机器学习-朴素贝叶斯学习原理分析与C语言代码实现作者：wxh5055一，任务介绍本文介绍朴素贝叶斯学习的基本原理以及其算法实现的C语言代码。朴素贝叶斯学习也叫朴素贝叶斯分类器，它是根据贝叶斯法则进行学习的一种算法。贝叶斯法则是条件概率相互计算的法则，即在已知P(A|B)的情况下怎么计算P(B|A)。P(A|B)是条件概率，表示在条件B成立的条件下条件A发生的概率，贝叶斯法则的表达式如下：PBA=PAB∗P(B)P(A)即在条件A成立的条件下条件B发生的概率，等于条件B成立的条件下条件A发生的概率，乘以条件B发生的概率，再除以条件A发生的概率。朴素贝叶斯学习器(分类器)就是需要计算在某个样例条件下，计算每个目标属性项发生的概率,然后选出概率最大的目标属性。举例说明，假设现在我们在已知某一天气候的情况下(用weather表示)，需要确定是否打网球(用yes和no表示)。朴素贝叶斯分类器就是要计算在已知weather的条件下，打网球的概率P(yes|weather)和P(no|weather)，如果前者大于后者，就去打网球，否则就不去打网球。二，朴素贝叶斯学习器的原理说明根据前面的介绍，朴素贝叶斯学习器就是需要计算在已知气候的情况下，分别计算出打网球的概率和不打网球得概率，然后选择概率大者作为最终的学习(分类)结果。在这里，气候weather用四个属性表示，分别是Outlook(天气)、Temperature(温度)、Humidity(湿度)和Wind(风强度)。先用贝叶斯公式表示为：𝑣𝑀𝐴𝑃=𝑎𝑟𝑔𝑚𝑎𝑥𝑣𝑗∈𝑉𝑃(𝑣𝑗|𝑤𝑒𝑎𝑡ℎ𝑒𝑟)称vMAP为在给定实例的属性值(weather的各属性值)下，得到的最可能的目标值，也就是条件概率最大的值。其中V={yes,no}，也就是说vMAP为目标属性集V中各取值(yes或no)的概率最大的。朴素贝叶斯学习器即使根据上面的公式推导而来。现在我们根据贝叶斯法则重写上面的公式：𝑣𝑀𝐴𝑃=𝑎𝑟𝑔𝑚𝑎𝑥𝑣𝑗∈{𝑦𝑒𝑠,𝑛𝑜}𝑃𝑣𝑗𝑤𝑒𝑎𝑡ℎ𝑒𝑟……………………..1𝑣𝑀𝐴𝑃=𝑎𝑟𝑔𝑚𝑎𝑥𝑣𝑗∈{𝑦𝑒𝑠,𝑛𝑜}𝑃𝑤𝑒𝑎𝑡ℎ𝑒𝑟𝑣𝑗∗𝑃(𝑣𝑗)𝑃(𝑤𝑒𝑎𝑡ℎ𝑒𝑟)……………….....2𝑣𝑀𝐴𝑃=𝑎𝑟𝑔𝑚𝑎𝑥𝑣𝑗∈{𝑦𝑒𝑠,𝑛𝑜}𝑃𝑤𝑒𝑎𝑡ℎ𝑒𝑟𝑣𝑗∗𝑃(𝑣𝑗)………….3从第二步到第三步的简化是因为某一天的气候是独立于我们的选择结果的，所以可以剔出P(weather)项；况且因𝑣𝑀𝐴𝑃是求目标属性vj中概率最大的，而所有目标属性的概率的分母都是P(weather)，所以分子最大也就说明目标属性vj的概率最大。现在我们需要做的就是计算式３中𝑃𝑤𝑒𝑎𝑡ℎ𝑒𝑟𝑣𝑗和𝑃(𝑣𝑗)的值，计算𝑃(𝑣𝑗)的值比较容易，只需要把训练样例中每个目标属性𝑣𝑗出现的概率即可；要计算𝑃𝑤𝑒𝑎𝑡ℎ𝑒𝑟𝑣𝑗的值，需要作一些相应的假定，即给定目标值时，各属性值之间的相互条件独立。我们把weather用{Outlook,Temperature,Humidity,Wind}表示，把式３重写为：𝑣𝑀𝐴𝑃=𝑎𝑟𝑔𝑚𝑎𝑥𝑣𝑗∈{𝑦𝑒𝑠,𝑛𝑜}𝑃𝑂𝑢𝑡𝑙𝑜𝑜𝑘,𝑇𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒,𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦,𝑊𝑖𝑛𝑑𝑣𝑗∗𝑃(𝑣𝑗)………….4根据假定，给定目标值时，某气候下的概率就等于给定该目标值时各属性的概率的乘积：P(Outlook,Temperature,Humidity,Wind|vj)=P(Outlook|vj)*P(Temperature|Vj)*P(Humidity|vj)*P(Wind|vj)……………………………5把式５带入式４中就得到我们要求的朴素贝叶斯的表达式：𝑣𝑁𝐵=𝑎𝑟𝑔𝑚𝑎𝑥𝑣𝑗∈{𝑦𝑒𝑠,𝑛𝑜}𝑃𝑂𝑢𝑡𝑙𝑜𝑜𝑘𝑣𝑗∗𝑃𝑇𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒𝑣𝑗∗𝑃𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦𝑣𝑗∗𝑃(𝑊𝑖𝑛𝑑|𝑣𝑗)∗𝑃(𝑣𝑗)……..6三，示例为了能更进一步了解朴素贝叶斯学习的原理，我们用一个示例来加以说明。该示例用表1中的数据作为训练样例，然后根据表达式6对测试样例进行朴素贝叶斯分类，测试样例如下：weather={Outlook=sunny,Temperature=cool,Humidity=high,Winds=strong};DayOutlookTemperatureHumidityWindPlayTennisDlSunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesDl0RainMildNormalWeakYesDl1SunnyMildNormalStrongYesDl2OvercastMildHighStrongYesDl3OvercastHotNormalWeakYesDl4RainMildHighStrongNo表1：朴素贝叶斯学习起使用的训练样例我们先计算P(Vj)的值，Vj有两个值，yes和no：P(yes)=9/14=0.643，P(no)=5/14=0.357。然后分别计算在目标属性为yes和no时，测试样例的各个属性的条件概率。注意，我们在计算各个属性的条件概率时，采用了m-估计的方法计算。比如在计算P(sunny|yes)(目标属性为yes，Outlook的属性值为Sunny的概率)时，按普通的计算方法：P(sunny|yes)=nc/n=2/9，nc=2是在训练样例中目标属性为yes的条件下Outlook=sunny的样例数，n=9是训练样例中目标属性值为yes的样例数；但是按m_估计的方法，计算出的概率是：P(sunny|yes)=(nc+m*p)/(n+m)=(2+14*0.33)/(9+14)，nc=2和n=9代表的意思和上一样，m=14代表训练样例总数，p=0.33代表在属性Outlook下共有３个属性值，所以这个先验概率就等于1/3。选择m-估计的原因是为了避免当训练样例数量较小时，训练样例中有可能没有测试样例中列出的某些属性值，也就是上面的nc=0，如果按照普通的方法，采用公式ncn，计算出的条件概率(比如P(sunny|yes))就会等于０，这样，根据式６计算出的条件概率因为是相乘的关系，其值也会为０，这样就会出现对训练样例过拟合的情况。而m-估计采用公式nc+m∗pn+m的形式，就可以避免出现过拟合的情况，m取值一般为训练样例的总数，p的值如果某个属性有k个可能值，则p=1/k，如上面P(sunny|yes)中，因为Outlook有３个可能值，所以p=1/3。有了条件概率的计算公式，我们就可计算出式６中的所有项的值：P(sunny|yes)=0.290;P(cool|yes)=0.333;P(high|yes)=0.435;P(strong|yes)=0.435;P(sunny|no)=0.403;P(cool|no)=0.298;P(high|no)=0.579;P(strong|no)=0.526;所以根据式６：P(vj=yes)=P(yes)*P(sunny|yes)*P(cool|yes)*P(high|yes)*P(strong|yes)=0.0117;P(vj=no)=P(no)*P(sunny|no)*P(cool|no)*P(high|no)*P(strong|no)=0.0131。所以，该测试样例的朴素贝叶斯分类结果为PlayTennis=no，因条件概率P(vj=no)大于条件概率P(vj=yes)。如果把这两个概率进行归一化处理，则P(vj=yes)=0.473，P(vj=no)=0.528。四，朴素贝叶斯学习器代码朴素贝叶斯学习器的代码很简单，先训练样例统计各个属性的概率，然后根据测试样例的各个属性值取出对应的概率，并相乘即可，测试结果如下：朴素贝叶斯学习器完整代码如下：//朴素贝叶斯学习器算法C语言代码实现//Copyright:wxh5055#includestdio.h//天气类型typedefenum_outlook{sunny,overcast,rain}_outlook;//温度类型typedefenum_temperature{hot,mild,cool}_temperature;//湿度类型typedefenum_humidity{high,normal}_humidity;//风强度类型typedefenum_wind{weak,strong}_wind;//目标属性typedefenum_targetAttribute{yes,no}_targetAttribute;//训练实例#defineTRAIN_NUM14//定义14个训练实例#defineATTR_NUM4//每个训练实例有4个属性inttrainSample[][ATTR_NUM+1]={{sunny,hot,high,weak,no},//1{sunny,hot,high,strong,no},//2{overcast,hot,high,weak,yes},//3{rain,mild,high,weak,yes},//4{rain,cool,normal,weak,yes},//5{rain,cool,normal,strong,no},//6{overcast,cool,normal,strong,yes},//7{sunny,mild,high,weak,no},//8{sunny,cool,normal,weak,yes},//9{rain,mild,normal,weak,yes},//10{sunny,mild,normal,strong,yes},//11{overcast,mild,high,strong,yes},//12{overcast,hot,normal,weak,yes},//13{rain,mild,high,strong,no},//14};//需要分类的新实例intnewSanple[ATTR_NUM]={sunny,cool,high,strong};//m-估计的每个属性对应的先验概率floatpreP[ATTR_NUM]={(float)0.333,(float)0.333,(float)0.50,(float)0.50};//m-估计的m值等于训练样例数#definemTRAIN_NUM//计算训练样例集的正样本数和负样本数//输入训练样例集//输出训练样例集的正样本数和负样本数voidCalcPosAndNegNum(int*pPosNum,int*pNegNum){inti;//取出训练样例//先清0*pPosNum=0;*pNegNum=0;for(i=0;iTRAIN_NUM;i++){//trainSample为训练样例首地址，每个训练样本共有ATTR_NUM个属性//根据目标属性地址存储的yes或no值来增加pPosNum或pNegNumif(trainSample[i][ATTR_NUM]==yes){(*pPosNum)++;}else{(*pNegNum)++;}}return;}//朴素贝叶斯学习器算法程序voidNaiveBayes(void){i