机器学习决策树 ID3算法的VC源代码.doc

机器学习决策树 ID3算法的源代码上（VC6.0测试通过）#include#include#include#include#include#include#define N 500/N定义为给定训练数据的估计个数#define M 6/M定义为候选属性的个数#define c 2/定义c=2个不同类#define s_max5 /定义s_max为每个候选属性所划分的含有最大的子集数int avM=3,3,2,3,4,2;int sNM+2,aNM+2;/数组sj用来记录第i个训练样本的第j个属性值int path_aNM+1,path_bNM+1;/用path_aNM+1,path_bNM+1记录每一片叶子的路径int count_list=M;/count_list用于记录候选属性个数int count=-1; /用count+1记录训练样本数int attribute_test_list1M;int leaves=1;/用数组sskj表示第k个候选属性划分的子集Sj中类Ci的样本数，数组的具体大小可根据给定训练数据调整int ssMcs_max;/第k个候选属性划分的子集Sj中样本属于类Ci的概率double pMcs_max;/count_sj用来记录第i个候选属性的第j个子集中样本个数int count_sMs_max;/分别定义EM，GainM表示熵和熵的期望压缩double EM;double GainM;/变量max_Gain用来存储最大的信息增益double max_Gain;int Trip=-1;/用Trip记录每一个叶子递归次数int most;void main(void) int i,j=-1,k,temp,l,count_test,true_class=0,count_train; char trainname256,testname256; int testN8; couttrainname; ifstream trainfile; trainfile.open(trainname,ios:in|ios:nocreate); if(!trainfile) cout无法使用训练集，请重试!temp) j=j+1; k=j%(M+2); if(k=0|j=0) count+=1; /count为训练集的第几个,k代表室第几个属性 switch(k) case 0:scount0=temp; break; case 1:scount1=temp; break; case 2:scount2=temp; break; case 3:scount3=temp; break; case 4:scount4=temp; break; case 5:scount5=temp; break; case 6:scount6=temp; break; case 7:scount7=temp; break; trainfile.close(); /输出训练集 for(i=0;i=count;i+) if(i%2=0) coutn; for(j=0;jM+2;j+) coutsetw(4)sj; /most记录训练集中哪类样本数比较多，以用于确定递归终止时不确定的类别 for(i=0,j=0,k=0;ik) most=0; else most=1; /count_train记录训练集的样本数 count_train=count+1; /训练的属性 for(i=0;iM;i+) attribute_test_list1=i+1; /首次调用递归函数，即是生成根结点的分支 Generate_decision_tree(s,count+1,attribute_test_list1,count_list,0,0); coutn叶子结点的个数为:leavesn; couttestname; ifstream testfile; testfile.open(testname,ios:in|ios:nocreate); if(!testfile) cout无法使用训练集，请重试!temp) j=j+1; k=j%(M+2); if(k=0) count_test+=1; switch(k) case 0:testcount_test7=temp; break; case 1:testcount_test1=temp; break; case 2:testcount_test2=temp; break; case 3:testcount_test3=temp; break; case 4:testcount_test4=temp; break; case 5:testcount_test5=temp; break; case 6:testcount_test6=temp; break; testfile.close(); for(i=1;i=count_test;i+) test0=0;/以确保评估分类准确率 coutcount_test=count_testn; coutcount_train=count_trainn; /用测试集来评估分类准确率 for(i=1;i=count_test;i+) l=0; for(j=1;j=leaves;j+) if(testpath_bj1=path_aj1&testpath_bj2=path_aj2&testpath_bj3=path_aj3&testpath_bj4=path_aj4&testpath_bj5=path_aj5&testpath_bj6=path_aj6) l=1; if(test7=path_aj0) true_class+=1; break; if(test7=most & l=0) true_class+=1; cout测试集与训练集的比例为:float(count_train)/count_testn; cout分类准确率为:float(true_class)/count_testn;天涯 (2009-4-16 11:43:00)第二部分：void Generate_decision_tree(int bM+2,int bn,int attribute_test_list,int sn,int ai,int aj) /定义数组a记录目前待分的训练样本集，定义数组b记录目前要分结点中所含的训练样本集 /same_class用来记数，判别samples是否都属于同一个类 Trip+=1;/用Trip记录每一个叶子递归次数 path_aleavesTrip=ai;/用path_aNM+1,path_bNM+1记录每一片叶子的路径 path_bleavesTrip=aj; int same_class,i,j,k,l,ll,lll; if(bn=0) /待分结点的样本集为空时，加上一个树叶，标记为训练集中最普通的类 /记录路径与前一路径相同的部分 for(i=1;iTrip;i+) if(path_aleavesi=0) path_aleavesi=path_aleaves-1i; path_bleavesi=path_bleaves-1i; coutnIF; for(i=1;i=Trip;i+) if(i=1) coutapath_bleavesi=path_aleavesi; else coutapath_bleavesi=path_aleavesi; coutTHENclass=1;i-) if(path_aleavesi=avpath_bleavesi-1)Trip-=1; else break; Trip-=1; leaves+=1; else same_class=1; for(i=0;ibn-1;i+) if(bi0=bi+10) same_class+=1; if(same_class=bn)/待分样本集属于同一类时以该类标记 /记录路径与前一路径相同的部分 for(i=1;iTrip;i+) if(path_aleavesi=0) path_aleavesi=path_aleaves-1i; path_bleavesi=path_bleaves-1i; coutnIF; for(i=1;i=Trip;i+) if(i=1) coutapath_bleavesi=path_aleavesi; else coutapath_bleavesi=path_aleavesi; coutTHENclass=1;i-) if(path_aleavesi=avpath_bleavesi-1) Trip-=1; else break; Trip-=1; leaves+=1; /未分类的样本集减少 for(i=0,l=-1;i=count;i+) for(j=0,lll=0;jbn;j+) if(siM+1=bjM+1) lll+; if(lll=0) l+=1; for(ll=0;llM+2;ll+) alll=sill; for(i=0,k=-1;il;i+) k+; for(ll=0;llM+2;ll+) skll=aill; count=count-bn; else if(sn=0)/候选属性集为空时，标记为训练集中最普通的类 /记录路径与前一路径相同的部分 for(i=1;iTrip;i+) if(path_aleavesi=0) path_aleavesi=path_aleaves-1i; path_bleavesi=path_bleaves-1i; coutnIF; for(i=1;i=Trip;i+) if(i=1) coutapath_bleavesi=path_aleavesi; else coutapath_bleavesi=path_aleavesi; /判断类别 for(i=0,ll=0,lll=0;illl) coutTHENclass=0; path_aleaves0=0; else cout1;i-) if(path_aleavesi=avpath_bleavesi-1)Trip-=1; else break; Trip-=1; leaves+=1; /未分类的样本集减少 for(i=0,l=-1;i=count;i+) for(j=0,lll=0;jbn;j+) if(siM+1=bjM+1) lll+; if(lll=0) l+=1; for(ll=0;llM+2;ll+) alll=sill; for(i=0,k=-1;il;i+) k+; for(ll=0;llM+2;ll+) skll=aill; count=count-bn; else/待分结点的样本集不为空时 /定义count_Positive记录属于正例的样本数 int count_Positive=0; /p1,p2分别定义为正负例的比例 double p1,p2; double Entropy_Es;/Entropy_Es表示熵 for(i=0;i=count;i+) if(si0=1) count_Positive+=1; p1=double(count_Positive)/(count+1); p2=1-p1; Entropy_Es=-p1*log10(p1)/log10(2)-p2*log10(p2)/log10(2); coutp1tp2tEntropy_Esn;天涯 (2009-4-16 11:43:32)继续：/初始化 for(i=0;isn;i+)/当前的属性包含的个数 for(j=0;jc;j+)/类别 for(k=0;kavi;k+)/以当前属性分成的小类(每个属性包含的种类数) ssattribute_test_listi-1jk=0; /用数组sskij表示第k个候选属性划分的子集Sj中类Ci的样本数，数组的具体大小可根据给定训练数据调整 for(i=0;isn;i+) for(j=0;javi;j+) count_sattribute_test_listi-1j=0;/初始化某个属性的某个具体值的全部个数 for(i=0;icount+1;i+) for(j=1;j=sn;j+) if(si0=0)/找出每个属性具体某个值属于反例的个数 ssattribute_test_listj-1-10sij-1+=1; count_sattribute_test_listj-1-1sij-1+=1; else ssattribute_test_listj-1-11sij-1+=1; count_sattribute_test_listj-1-1sij-1+=1; /计算分别以各个候选属性划分样本后，各个子集Sj中的样本属于类Ci的概率 for(i=0;isn;i+) for(j=0;jc;j+) for(k=0;kavi;k+) if(count_sattribute_test_listi-1k!=0) pattribute_test_listi-1jk=double(ssattribute_test_listi-1jk)/count_sattribute_test_listi-1k; for(i=0;isn;i+) Eattribute_test_listi-1=0.0; /计算熵 for(i=0;isn;i+) for(j=0;javattribute_test_listi-1;j+) /if语句处理0*log10(0)=0 if(pattribute_test_listi-10j=0|pattribute_test_listi-11j=0) pattribute_test_listi-10j=1; pattribute_test_listi-11j=1; Eattribute_test_listi-1+=(ssattribute_test_listi-10j+ssattribute_test_listi-11j)*(-(pattribute_test_listi-10j*log10(pattribute_test_listi-10j)/log10(2)+pattribute_test_listi-11j*log10(pattribute_test_listi-11j)/log10(2)/(count+1); /计算熵的信息增益 for(i=0;isn;i+) Gainattribute_test_listi-1=Entropy_Es-Eattribute_test_listi-1; /找出信息增益的最大值,用j记录哪个候选属性的信息增益最大 max_Gain=Gain0; j=attribute_test_list0-1; for(i=0;isn;i