1、机器学习朴素贝叶斯学习原理分析与C语言代码实现数据挖掘课程大作业题 目： 机器学习-朴素贝叶斯 班 级： 信管2014-2班 指导教师： 汪传建 日期:2017年11月21日机器学习-朴素贝叶斯学习原理分析与 C 语言代码实现一， 任务介绍本文介绍朴素贝叶斯学习的基本原理以及其算法实现的 C 语言代码。朴素贝叶斯学习也叫朴素贝叶斯分类器，它是根据贝叶斯法则进行学习的一种算法。贝叶斯法则是条件概率相互计算的法则，即在已知 P(A|B)的情况下怎么计算 P(B|A)。P(A|B)是条件概率，表示在条件 B 成立的条件下条件 A 发生的概率，贝叶斯法则的表达式如下： 即在条件 A 成立的条件下条件
2、B 发生的概率，等于条件 B 成立的条件下条件 A 发生的概率，乘以条件 B 发生的概率，再除以条件 A 发生的概率。朴素贝叶斯学习器(分类器)就是需要计算在某个样例条件下，计算每个目标属性项发生的概率,然后选出概率最大的目标属性。举例说明，假设现在我们在已知某一天气候的情况下(用 weather 表示)，需要确定是否打网球(用 yes 和 no 表示)。朴素贝叶斯分类器就是要计算在已知 weather 的条件下，打网球的概率 P(yes|weather)和 P(no|weather)，如果前者大于后者，就去打网球，否则就不去打网球。二， 朴素贝叶斯学习器的原理说明根据前面的介绍，朴素贝叶斯学
3、习器就是需要计算在已知气候的情况下，分别计算出打网球的概率和不打网球得概率，然后选择概率大者作为最终的学习(分类)结果。在这里，气候 weather 用四个属性表示，分别是 Outlook(天气)、Temperature(温度)、Humidity(湿度)和Wind(风强度)。先用贝叶斯公式表示为： 称 vMAP 为在给定实例的属性值(weather 的各属性值)下，得到的最可能的目标值，也就是条件概率最大的值。其中 V=yes,no，也就是说 vM AP 为目标属性集 V 中各取值(yes 或 no)的概率最大的。朴素贝叶斯学习器即使根据上面的公式推导而来。现在我们根据贝叶斯法则重写上面的公式
4、：要作一些相应的假定，即给定目标值时，各属性值之间的相互条件独立。我们把 weather 用Outlook, Temperature , Humidity ,Wind表示，把式重写为：根据假定，给定目标值时，某气候下的概率就等于给定该目标值时各属性的概率的乘积：P(Outlook,Temperature,Humidity,Wind|vj) =P(Outlook|vj)*P(Temperature|Vj)*P(Humidity|vj)*P(Wind|vj)5把式带入式中就得到我们要求的朴素贝叶斯的表达式： 三， 示例为了能更进一步了解朴素贝叶斯学习的原理，我们用一个示例来加以说明。该示例用表1
5、中的数据作为训练样例，然后根据表达式 6 对测试样例进行朴素贝叶斯分类，测试样例如下：weather=Outlook=sunny,Temperature=cool,Humidity=high,Winds=strong;DayOutlookTemperatureHumidityWindPlayTennisDlSunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCool
6、NormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesDl0RainMildNormalWeakYesDl1SunnyMildNormalStrongYesDl2OvercastMildHighStrongYesDl3OvercastHotNormalWeakYesDl4RainMildHighStrongNo表 1：朴素贝叶斯学习起使用的训练样例我们先计算 P(Vj)的值，Vj 有两个值，yes 和 no：P(yes)=9/14=0.643，P(no)=5/14=0.357。然后分别计算在目标属性为 yes 和 no 时，测试
7、样例的各个属性的条件概率。注意，我们在计算各个属性的条件概率时，采用了 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 代表训练
8、样例总数，p=0.33 代表在属性 Outlook 下共有个属性值，所以这个先验概率就等于 1/3。选择 m-估计的原因是为了避免当训练样例数量较小时，训练样例中有可能没有测试样例中列出的某些属性值，也就是上面的 nc=0，如果按照普通的方法，采用公式nnc ，计算出的条件概率(比如 P(sunny|yes)就会等于，这样，根据式计算出的条件概率因为是相乘的nc +m p关系，其值也会为，这样就会出现对训练样例过拟合的情况。而 m-估计采用公式 n+m 的形式，就可以避免出现过拟合的情况，m 取值一般为训练样例的总数，p 的值如果某个属性有k 个可能值，则 p=1/k，如上面 P(sunny|
9、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)
10、=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 语言代码实现/Copyrig
11、ht:wxh5055#include /天气类型 typedef enum _outlooksunny,overcast, rain_outlook;/温度类型 typedef enum _temperaturehot,mild, cool _temperature;/湿度类型 typedef enum _humidityhigh, normal_humidity;/风强度类型 typedef enum _windweak, strong_wind;/目标属性typedef enum _targetAttributeyes, no_targetAttribute;/训练实例#define TR
12、AIN_NUM 14/定义 14 个训练实例#define ATTR_NUM 4/每个训练实例有 4 个属性int trainSampleATTR_NUM+1=sunny , hosunny, hot , high, strong, no ,/2overcast, hot , high, weak, yes,/3rain, mild, high, weak, yes,/4rain, cool, normal, weak, yes,/5rain, cool, normal, strong, no ,/6overcast, cool, normal, strong, yes,/7sunny, mi
13、ld, high, weak, no ,/8sunny, cool, normal, weak, yes,/9rain, mild, normal, weak, yes,/10sunny, mild, normal, strong, yes,/11overcast, mild, high, strong, yes,/12overcast, hot , normal, weak, yes,/13rain, mild, high, strong, no ,/14t , high , weak , no ,/1;/需要分类的新实例 int newSanpleATTR_NUM=sunny,cool,h
14、igh,strong;/m-估计的每个属性对应的先验概率 float prePATTR_NUM=(float)0.333,(float)0.333,(float)0.50,(float)0.50; /m-估计的 m 值等于训练样例数#define m TRAIN_NUM/计算训练样例集的正样本数和负样本数/输入训练样例集/输出训练样例集的正样本数和负样本数 void CalcPosAndNegNum(int *pPosNum,int *pNegNum)int i;/取出训练样例/先清 0 *pPosNum=0; *pNegNum=0;for(i=0;iTRAIN_NUM;i+)/trainSa
15、mple 为训练样例首地址，每个训练样本共有 ATTR_NUM 个属性/根据目标属性地址存储的 yes 或 no 值来增加 pPosNum 或 pNegNum if(trainSampleiATTR_NUM=yes)(*pPosNum)+;else(*pNegNum)+; return; /朴素贝叶斯学习器算法程序 void NaiveBayes(void) int i,j,cntY,cntN; /存储训练样例目标属性为yes和no的样本数 int posNum,negNum; /存储目标值yes和no的概率 float PVyes,PVno,PVyesTemp,PVnoTemp; /存储目标
16、值为yes时需分类的每个属性的概率 float PAttrYesATTR_NUM; /存储目标值为no时需分类的每个属性的概率 float PAttrNoATTR_NUM; /计算训练样例集的正样本数和负样本数 CalcPosAndNegNum(&posNum,&negNum); /计算目标值yes的概率 PVyes=(float)posNum/(float)TRAIN_NUM; /计算目标值no的概率 PVno=(float)negNum/(float)TRAIN_NUM; /计算目标值分别为yes和no时各个需分类属性对应的概率 for(j=0;jATTR_NUM;j+) /清0计数变量
17、cntY=0; cntN=0; for(i=0;iTRAIN_NUM;i+) /统计目标值为yes时各个需分类的属性在训练样例中的个数 if(trainSampleiATTR_NUM=yes) /如果训练样例的目标属性是yes /且该训练样例的属性值和需要分类的样例的属性值相等,则计数 if(trainSampleij=newSanplej) cntY+; /统计目标值为no时各个需分类的属性在训练样例中的个数 else if(trainSampleiATTR_NUM=no) /如果训练样例的目标属性是no /且该训练样例的属性值和需要分类的样例的属性值相等,则计数 if(trainSampl
18、eij=newSanplej) cntN+; /计算目标值为yes时需分类的各个属性的概率 PAttrYesj=(float)cntY+(float)m*prePj)/(float)(posNum+m); /计算目标值为no时需分类的各个属性的概率 PAttrNoj=(float)cntN+(float)m*prePj)/(float)(negNum+m); /分别计算需要分类的样例的目标值为yes和no的概率 for(i=0;iPVnoTemp) printf(所以实例被分类为:yesn); else printf(所以实例被分类为:non); return; /主函数 int main(void) /调用朴素贝叶斯学习器算法 NaiveBayes(); return 1;
