朴素贝叶斯分类算法
一．贝叶斯分类的原理
贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出 其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对 象所属的类。也就是说，贝叶斯分类器是最小错误率意义上的优化。
贝叶斯分类器是用于分类的贝叶斯网络。该网络中应包含类结点 C，其中 C 的取值来自于类集合( c1 , c2 , ... , cm)，还包含一组结点 X = ( X1 , X2 , ... , Xn)，表示用于分类的特征。对于贝叶斯网络分类器，若某一待分类的样本 D， 其分类特征值为 x = ( x1 , x2 , ... , x n) ，则样本 D 属于类别 ci 的概率 P( C = ci | X1 = x1 , X2 = x 2 , ... , Xn = x n) ，( i = 1 ,2 , ... , m) 应满足下式：
} } SplitPoint=(float *)calloc(gi->MaxAttNo+1,sizeof(float)); }
(2)预测 PredictClass::PredictClass(GetInfo *i,GetModel *m,string Attname):MaxClassNo(-1),MaxDiscrValNo(2),MaxAttNo (-1) {
/* Make sure there is room for another item */
if ( ItemNo >= ItemSpace )
{
if ( ItemSpace )
{
ItemSpace += Inc;
Item
=
(Description
*)realloc(Item,
ItemSpace*sizeof(Description));
/* Discrete value */ Dv = Which(name, AttValName[AttNo], 1, MaxAttValNo[AttNo]); if ( ! Dv ) {
Error(4, AttName[AttNo], name);
}
Dvec[AttNo].DiscrValue=Dv;
MaxItemNo=ItemNo - 1;
}
void PredictClass::Error(int n, string s1, string s2)
/* ----- */
{
cout<<"ERROR: ";
switch(n) { case 0: cout<<"cannot open file "<<s1<<s2<<endl;
else {
if(gi->Item[i][j].continuousVal<=SplitPoint[j]) SplitVal=1;
else SplitVal=2;
PostFreq[gi->Item[i][gi->MaxAttNo+1].DiscrValue][j][SplitVal]++; }
} } } void GetModel::Cache() { PostFreq=(float ***) calloc(gi->MaxClassNo+1,sizeof(float **)); for(int i=0;i<=gi->MaxClassNo;i++) {
filename.copy(Fn,filename.length());
Fn[filename.length()]=NULL;
if ( ! ( Nf = fopen(Fn, "r") ) )
Error(0, Fn, "");
int ItemNo=0;
int ItemSpace=0;
do
{
MaxItemNo = ItemNo;
} for(int i=0;i<=gi->MaxItemNo;i++) {
for(int j=0;j<=gi->MaxAttNo;j+Байду номын сангаас) {
if(gi->MaxAttValNo[j])
PostFreq[gi->Item[i][gi->MaxAttNo+1].DiscrValue][j][gi->Item[i][j].DiscrValue]+ +;
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) 的计算则较困难。
三、算法实现代码
(1)建立模型
void GetModel::TrainModel() {
int SplitVal; Cache();//为模型分配内存 for(int i=0;i<=gi->MaxAttNo;i++) {
if(!gi->MaxAttValNo[i]) SplitPoint[i]=gi->SplitContinuousAtt(i);
PostFreq[i]=(float **) calloc(gi->MaxAttNo+1,sizeof(float *)); for(int j=0;j<=gi->MaxAttNo;j++) {
if(gi->MaxAttValNo[j]) PostFreq[i][j]=(float
*)calloc(gi->MaxAttValNo[j]+1,sizeof(float)); else PostFreq[i][j]=(float *)calloc(3,sizeof(float));
Dvec = (Description)calloc(MaxAttNo+2, sizeof(AttValue));//因为aMaxAttNo 是从a开始计数的在加上类别属性，所以+2
for(AttNo=0;AttNo<=MaxAttNo;AttNo++) {
if ( MaxAttValNo[AttNo]) {
}
else
{
/* Continuous value */
Cv = (float)strtod(name, &endname);
case 3:cout<<"attribute "<<s1<<" has only one value"<<endl; break;
case 4:cout<<"case "<< MaxItemNo+1<<"'s value of '"<<s2<<"' for attribute "<<s1<<"is illegal"<<endl;//Error(4, AttName[AttNo], name);
break;
case 5:cout<<"case "<<MaxItemNo+1<<"'s class of '"<<s2<<"' is illegal"<<endl; break;
} cout<<"process stop!"<<endl; exit(1); } Description PredictClass::GetDescription(FILE *Df) { int AttNo;/* attribute number, 0..MaxAttNo */ char name[50], *endname; int Dv; float Cv; Description Dvec; if ( ReadName(Df, name) ) {
}
else
{
Item
=
(Description
*)malloc((ItemSpace=Inc)*sizeof(Description));
}
}
Item[ItemNo] = GetDescription(Nf);
}while ( Item[ItemNo] != 0 && ++ItemNo);
fclose(Nf);
prob[i]=1.0; for(int i=0;i<=MaxItemNo;i++) {
name,string
for(j=0;j<=MaxClassNo;j++) {
for(int k=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]); else prob[j]*=(gm->PostFreq[j][k][2]/gi->ClassFreq[j]); }