朴素贝叶斯分类器.doc

朴素贝叶斯分类器Naive Bayesian ClassifierC语言实现2013年2月8日1. 贝叶斯公式通过贝叶斯公式，我们可以的知在属性F1-Fn成立的情况下，该样本属于分类C的概率。而概率越大，说明样本属于分类C的可能性越大。若某样本可以分为2种分类A，B。要比较P(A | F1,F2.) 与 P(B | F1,F2.)的大小只需比较，P(A)P(F1,F2.| A) ,与P(B)P(F1,F2.| B) 。因为两式分母一致。而P(A)P(F1,F2.| A)可以采用缩放为P(A)P(F1|A)P(F2|A).(Fn|A)因此，在分类时，只需比较每个属性在分类下的概率累乘，再乘该分类的概率即可。分类属性outlook属性temperature属性humidity属性windnosunnyhothighweaknosunnyhothighstrongyesovercasthothighweakyesrainmildhighweakyesraincoolnormalweaknoraincoolnormalstrongyesovercastcoolnormalstrongnosunnymildhighweakyessunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweaknorainmildhighstrong以上是根据天气的4种属性，某人外出活动的记录。若要根据以上信息判断(Outlook = sunny,Temprature = cool,Humidity = high,Wind = strong)所属分类。P(yes| sunny ,cool ,high ,strong )=P(yes)P(sunny|yes)P(cool |yes)P(high|yes)P(strong|yes)/KP(no| sunny ,cool ,high ,strong )=P(no)P(sunny|no)P(cool |no)P(high|no)P(strong|no)/KK为缩放因子，我们只需要知道两个概率哪个大，所以可以忽略K。P(yes)=9/14 P(no)=5/14P(sunny|yes)=2/9 P(cool|yes)=1/3 P(high|yes)=1/3 P(strong|yes)=1/3P(sunny|no)=3/5 P(cool|no)=2/5 P(high|no)=4/5 P(strong|no)=3/5P(yes| sunny ,cool ,high ,strong)=9/14*2/9*1/3*1/3*1/3=0.00529P(no| sunny ,cool ,high ,strong )=5/14*3/5*1/5*4/5*3/5=0.20571No的概率大，所以该样本实例属于no分类。2.数据结构及代码实现1.属性及分类我们限定分类器的属性不大于9个，每个属性拥有不大于9个值。于是，我们考虑采用一个9 X 9的表格存储属性及其值。属性1值1值2值3值4值5值6值7值8值9属性2值1值2值3值4值5值6值7值8值9属性3值1值2值3值4值5值6值7值8值9属性4值1值2值3值4值5值6值7值8值9属性5值1值2值3值4值5值6值7值8值9属性6值1值2值3值4值5值6值7值8值9属性7值1值2值3值4值5值6值7值8值9属性8值1值2值3值4值5值6值7值8值9属性9值1值2值3值4值5值6值7值8值9为了调用数据方便，我们把数据从第一行开始储存。为了充分利用存储空间，我们把第零行储存分类数据。分类1分类2分类3分类4分类5分类6分类7分类8分类9属性1值1值2值3值4值5值6值7值8值9属性2值1值2值3值4值5值6值7值8值9属性3值1值2值3值4值5值6值7值8值9属性4值1值2值3值4值5值6值7值8值9属性5值1值2值3值4值5值6值7值8值9属性6值1值2值3值4值5值6值7值8值9属性7值1值2值3值4值5值6值7值8值9属性8值1值2值3值4值5值6值7值8值9属性9值1值2值3值4值5值6值7值8值9现在，我们可以采用一个10 X 10 的表格来储存数据了。而每个单元格的内容需要占用一定的储存空间，我们可以用一个三维数组char feature101010来表示这种结构的数据。用来容纳9个属性的9个值。第0行，我们用来储存分类数据。而第一行的第一列没有被使用，而其中含有10个char类型的数据我们可以用它来储存属性值的多少。如图：分类的个数属性1值的个数属性2值的个数.属性9值的个数前一段的数据：分类： yes no属性outlook： sunny overcast rain属性temperature： hot mild cool属性humidity： high normal属性wind： strong weak如下图yesnooutlooksunnyovercastrainTemperahotmildcoolhumidityhighnormalwindstrongweak第0行，第0列23322代码如下：int x=1,y;printf(请输入属性名称(小于9个字符):);gets(featurex0);printf(该属性有几种值(不多于9个值):);scanf(%c,&feature00x);/把属性值储存入feature00x;feature00x-=48;/feature00x是由字符格式输入的-48变为数字getchar();system(cls);for(y=1;y=feature00x;y+)/根据feature00x循环输入，将属性的值存入数组printf(请输入第%d个值:,y);gets(featurexy);x+;通过这段代码的循环，输入属性及其值进入feature数组。通过以下代码将分类数据存入数组第0行。printf(该事物可以被分为几种类别:);scanf(%c,&feature000);/分类数目存入feature000feature000-=48;getchar();system(cls);for(y=1;y=feature000;y+)/通过循环将分类存入第0行printf(请输入第%d种类别的名称:,y);gets(feature0y);2. 训练样本每个训练样本的属性最多有9个值，再加上分类一个值，所以，我们采用一个10列的表格储存训练样本数据。nosunnyhothighweaknosunnyhothighstrongyesovercasthothighweakyesrainmildhighweakyesraincoolnormalweaknoraincoolnormalstrongyesovercastcoolnormalstrongnosunnymildhighweakyessunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweaknorainmildhighstrong 同样，每个单元格里限制最多有9个字符，加上一个0终止符，共十个。而样本数量，也就是行数，可以适当的多一点，暂设为30。因此我们采用三维数组char sample301010来容纳样本数据。X的初始值为1for(y=1;y=FeatureNum;y+)printf(特征%s的取值:,featurey0);gets(samplex-1y);printf(该样本归于哪一种分类:);gets(samplex-10);x+;SampleNum+;/统计样本的数量3. 计算概率class probabilitypublic:int id;/给每个概率值一个定位ID，方便查找double p;probability()p=0;probability prob729;采用一729个类来存放每个属性值在不同分类下的概率。至多有9种属性，每个属性至多拥有9个值，而要计算这9个属性的9种值在9种不同分类下的概率，所以我们用了729个类。并且在构造函数里面初始化概率p为0.接下来，统计各种分类出现的个数。9种分类出现的数目，分别储存在SampleClassNum9的不同单元格里。int SampleClassNum9=0,0,0,0,0,0,0,0,0;for(c=1;c=feature000;c+)for(x=0;xSampleNum;x+)if(strcmp(feature0c,samplex0)=0)SampleClassNumc-1+;然后，我们可以开始计算概率了。for(c=1;c=feature000;c+)for(x=1;x=FeatureNum;x+)for(y=1;y=feature00x;y+)probcounter.id=c*100+x*10+y;for(i=0;iSampleNum;i+)if(strcmp(featurexy,sampleix)=0& strcmp(feature0c,samplei0)=0)probcounter.p+;/统计某一值在某一分类下的出现个数probcounter.p=probcounter.p/SampleClassNumc-1;/出现个数除以分类出/现总数，计算出概率counter+;每个概率的ID为3位整数，百位记录了分类信息，个位十位分别是，其属性值在表格中的X，Y坐标。然后，进行比较，统计出出现个数，接着除以分类的出现总数，计算出概率。4. 对新的实例进行分类输入该新的实例。char instance910;double Pinstance9=1,1,1,1,1,1,1,1,1;int PID9;printf(贝叶斯分类器 Sept 5n);printf(请输入要分类的样本属性n);for(i=1;i=FeatureNum;i+)printf(特征%s的取值,featurei0);gets(instancei-1);然后，计算出不含分类信息的值在表格中的X，Y坐标。for(x=1;x=FeatureNum;x+)for(y=1;y=feature00x;y+)if(strcmp(featurexy,instancex-1)=0)PIDx-1=x*10+y;break;根据X，Y坐标加上分类坐标，组成完整的3位数坐标。在概率表prob中查找即可找到。通过累乘，然后乘上某一分类的概率，即可求出最终的概率。for(c=1;c=feature000;c+)for(y=0;yFeatureNum;y+)for(i=0;i729;i+)if(probi.id=PIDy+c*100)break;Pinstancec-1=Pinstancec-1*probi.p;/累乘求概率Pinstancec-1=Pinstancec-1*(SampleClassNumc-1/(double)SampleNum);/最后乘上这一分类的概率，即可求出最终概率system(cls);6. 输出各概率及分类最后，比较各概率的大小，最大的所属分类，就是该实例的所属分类。double t=0;for(i=0;ifeature000;i+)if(tPinstancei)t=Pinstancei;for(i=0;ifeature000;i+)if(t=Pinstancei)break;for(y=1;y=feature000;y+)printf(%s的概率为:%lfn,feature0y,Pinstancey-1);3. 程序源代码#include#include#includevoid main()int x=1,y,FeatureNum,SampleNum=0;char feature101010;char sample301010;char select;/-Sept 1-while(1)while(1)printf(贝叶斯分类器 Sept 1n);printf(1.创建一个属性n);printf(2.下一步nnn);printf(输入序号选择功能:);select=getchar();getchar();if(select=1 | select=2)system(cls);break;system(cls);if(select=2) break;printf(请输入属性名称(小于9个字符):);gets(featurex0);printf(该属性有几种值(不多于9个值):);scanf(%c,&feature00x);feature00x-=48;getchar();system(cls);for(y=1;y=feature00x;y+)printf(请输入第%d个值:,y);gets(featurexy);x+;system(cls);FeatureNum=x-1;/-Sept 2-printf(贝叶斯分类器 Sept 2n);printf(该事物可以被分为几种类别:);scanf(%c,&feature000);feature000-=48;getchar();system(cls);for(y=1;y=feature000;y+)printf(请输入第%d种类别的名称:,y);gets(feature0y);system(cls);/-Sept 3-x=0;while(1)while(1)printf(贝叶斯分类器 Sept3n);printf(1.录入一个训练样本n);printf(2.下一步nnn);printf(输入序号选择功能:);select=getchar();getchar();if(select=1 | select=2)system(cls);break;system(cls);if(select=2) break;for(y=1;y=FeatureNum;y+)printf(特征%s的取值:,featurey0);gets(samplexy);printf(该样本归于哪一种分类:);gets(samplex0);x+;SampleNum+;system(cls);/-Sept 4-printf(贝叶斯分类器 Sept 4n);printf(计算中，请稍候.n);int c,i,counter=0;class probabilitypublic:int id;double p;probability()p=0;probability prob729;int SampleClassNum9=0,0,0,0,0,0,0,0,0;for(c=1;c=feature000;c+)for(x=0;xSampleNum;x+)if(strcmp(feature0c,samplex0)=0)SampleClassNumc-1+;for(c=1;c=feature000;c+)for(x=1;x=FeatureNum;x+)for(y=1;y=feature00x;y+)probcounter.id=c*100+x*10+y;for(i=0;iSampleNum;i+)if(strcmp(featurexy,sampleix)=0 & strcmp(feature0c,samplei0)=0)probcounter.p+;probcounter.p=probcounter.p/SampleClassNumc-1;counter+;printf(计算完成，按回车键继续.);getchar();system(cls);/