搜索
朴素贝叶斯分类算法一．贝叶斯分类的原理贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。也就是说，贝叶斯分类器是最小错误率意义上的优化。贝叶斯分类器是用于分类的贝叶斯网络。该网络中应包含类结点C，其中C的取值来自于类集合(c1,c2,...,cm)，还包含一组结点X=(X1,X2,...,Xn)，表示用于分类的特征。对于贝叶斯网络分类器，若某一待分类的样本D，其分类特征值为x=(x1,x2,...,xn)，则样本D属于类别ci的概率P(C=ci|X1=x1,X2=x2,...,Xn=xn)，(i=1,2,...,m)应满足下式：P(C=ci|X=x)=Max{P(C=c1|X=x),P(C=c2|X=x),...,P(C=cm|X=x)}贝叶斯公式：P(C=ci|X=x)=P(X=x|C=ci)*P(C=ci)/P(X=x)其中，P(C=ci)可由领域专家的经验得到,而P(X=x|C=ci)和P(X=x)的计算则较困难。二．贝叶斯伪代码整个算法可以分为两个部分，“建立模型”与“进行预测”，其建立模型的伪代码如下：numAttrValues等简单的数据从本地数据结构中直接读取构建几个关键的计数表for(为每一个实例){for(每个属性){为numClassAndAttr中当前类，当前属性，当前取值的单元加1为attFrequencies中当前取值单元加1}}预测的伪代码如下：for(每一个类别){for(对每个属性xj){for(对每个属性xi){if(F(xi)小于m){出现的次数没有超过阀值，不予考虑}else{查numClassAndAttr计算F(y,xi,xj)}}查numClassAndAttr计算F(y,xi)}计算公式（7）中的评价函数，记录下这个类别的评价函数值}得到了各个类别上的条件概率，再带入贝叶斯公式算出最后的概率三、算法实现代码(1)建立模型voidGetModel::TrainModel(){intSplitVal;Cache();//为模型分配内存for(inti=0;i=gi-MaxAttNo;i++){if(!gi-MaxAttValNo[i])SplitPoint[i]=gi-SplitContinuousAtt(i);}for(inti=0;i=gi-MaxItemNo;i++){for(intj=0;j=gi-MaxAttNo;j++){if(gi-MaxAttValNo[j])PostFreq[gi-Item[i][gi-MaxAttNo+1].DiscrValue][j][gi-Item[i][j].DiscrValue]++;else{if(gi-Item[i][j].continuousVal=SplitPoint[j])SplitVal=1;elseSplitVal=2;PostFreq[gi-Item[i][gi-MaxAttNo+1].DiscrValue][j][SplitVal]++;}}}}voidGetModel::Cache(){PostFreq=(float***)calloc(gi-MaxClassNo+1,sizeof(float**));for(inti=0;i=gi-MaxClassNo;i++){PostFreq[i]=(float**)calloc(gi-MaxAttNo+1,sizeof(float*));for(intj=0;j=gi-MaxAttNo;j++){if(gi-MaxAttValNo[j])PostFreq[i][j]=(float*)calloc(gi-MaxAttValNo[j]+1,sizeof(float));elsePostFreq[i][j]=(float*)calloc(3,sizeof(float));}}SplitPoint=(float*)calloc(gi-MaxAttNo+1,sizeof(float));}(2)预测PredictClass::PredictClass(GetInfo*i,GetModel*m,stringname,stringAttname):MaxClassNo(-1),MaxDiscrValNo(2),MaxAttNo(-1){gi=i;gm=m;filename=name;this-Inc=1024;AttFileName=Attname;}voidPredictClass::Predict(){float*prob;intBestI=-1;floatMaxProb=0;intj;GetName();GetData();prob=(float*)calloc(MaxClassNo+1,sizeof(float));for(inti=0;i=MaxClassNo;i++)prob[i]=1.0;for(inti=0;i=MaxItemNo;i++){for(j=0;j=MaxClassNo;j++){for(intk=0;k=MaxAttNo;k++){if(MaxAttValNo[k])prob[j]*=(gm-PostFreq[j][k][Item[i][k].DiscrValue]/gi-ClassFreq[j]);else{if(Item[i][k].continuousVal=gm-SplitPoint[k])prob[j]*=(gm-PostFreq[j][k][1]/gi-ClassFreq[j]);elseprob[j]*=(gm-PostFreq[j][k][2]/gi-ClassFreq[j]);}}prob[j]*=(gi-ClassFreq[j]/(gi-MaxItemNo+1));if(prob[j]MaxProb){MaxProb=prob[j];BestI=j;}}cout概率最大MaxProb类别=ClassName[BestI]endl;Item[i][MaxAttNo+1].DiscrValue=BestI;/*重置*/{BestI=-1;MaxProb=0;for(inti=0;i=MaxClassNo;i++)prob[i]=1.0;}}show();}voidPredictClass::show(){inti,j;for(i=0;i=MaxItemNo;i++){for(j=0;j=MaxAttNo;j++){if(MaxAttValNo[j])coutAttValName[j][Item[i][j].DiscrValue];elsecoutItem[i][j].continuousVal;}cout预测结果为:ClassName[Item[i][j].DiscrValue]endl;}}voidPredictClass::GetData(){FILE*Nf;charFn[50];filename=filename+.data;filename.copy(Fn,filename.length());Fn[filename.length()]=NULL;if(!(Nf=fopen(Fn,r)))Error(0,Fn,);intItemNo=0;intItemSpace=0;do{MaxItemNo=ItemNo;/*Makesurethereisroomforanotheritem*/if(ItemNo=ItemSpace){if(ItemSpace){ItemSpace+=Inc;Item=(Description*)realloc(Item,ItemSpace*sizeof(Description));}else{Item=(Description*)malloc((ItemSpace=Inc)*sizeof(Description));}}Item[ItemNo]=GetDescription(Nf);}while(Item[ItemNo]!=0&&++ItemNo);fclose(Nf);MaxItemNo=ItemNo-1;}voidPredictClass::Error(intn,strings1,strings2)/*-----*/{coutERROR:;switch(n){case0:coutcannotopenfiles1s2endl;break;case1:coutcolonexpectedafterattributenames1endl;break;case2:coutunexpectedEOFwhilereadingattributes1endl;break;case3:coutattributes1hasonlyonevalueendl;break;case4:coutcaseMaxItemNo+1'svalueof's2'forattributes1isillegalendl;//Error(4,AttName[AttNo],name);break;case5:coutcaseMaxItemNo+1'sclassof's2'isillegalendl;break;}coutprocessstop!endl;exit(1);}DescriptionPredictClass::GetDescription(FILE*Df){intAttNo;/*attributenumber,0..MaxAttNo*/charname[50],*endname;intDv;floatCv;DescriptionDvec;if(ReadName(Df,name)){Dvec=(Description)calloc(MaxAttNo+2,sizeof(AttValue));//因为aMaxAttNo是从a开始计数的在加上类别属性，所以+2for(AttNo=0;AttNo=MaxAttNo;AttNo++){if(MaxAttValNo[AttNo]){/*Discretevalue*/Dv=Which(name,AttValName[AttNo],1,MaxAttValNo[AttNo]);if(!Dv){Error(4,AttName[AttNo],name);}Dvec[AttNo].DiscrValue=Dv;}else{/*Continuousvalue*/Cv=(float)strtod(name,&endname);if(endname==name||*endname!='\0')Error(4,AttName[AttNo],name);Dvec[AttNo].continuousVal=Cv;}ReadName(Df,name);}returnDvec;}else{return0;}}voidPredictClass::GetName(){FILE*Nf;charBuffer[1000];charFn[100];intAttCeiling=100;intClassCeiling=100;intValCeiling;AttFileName.copy(Fn,AttFileName.length());Fn[AttFileName.length()]=NULL;strcat_s(Fn,.names);if(!(Nf=fopen(Fn,r)))Error(0,Fn,);ClassName=(string*)calloc(ClassCeiling,sizeof(string));do{ReadName(Nf,Buffer);if(++MaxClassNo=ClassCeiling){ClassCeiling+=100;ClassName=(string*)real