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

1、机器学习决策树ID3算法的源代码上（VC6.0测试通过）发布：2009-4-16 11:42 |作者：天涯|来源：资讯i=s本帖最后由 天涯于2009-4-17 13:03编辑这个的重要，不用多说了吧，有什么意见和建议跟帖留言啊，哈，觉得好，请顶一个第一部分：#include#include#include#include#include#include#define N 500 /N定义为给定训练数据的估计个数#define M 6 /M定义为候选属性的个数#define c 2 /定义c=2个不同类#define s_max 5 /定义s_max为每个候选属性所划分的含有最大的子集数int

2、 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个候选属性划

3、分的子集Sj中样本属于类Ci的概率double pMcs_max;/count_sj用来记录第i个候选属性的第j个子集中样本个数break;int count_sMs_max;/分别定义EM , GainM表示!W和!W的期望压缩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 trainname

4、256,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;case 1:scount1=temp;break;case 2:scount2=temp;break;case 3:scount3=te

5、mp;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记录训练集的样本数co

6、unt_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);

7、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;天涯(2009-4-16 11:43:00)break;case 4:testcount_test4=temp;break;case 5:testcount_test5=temp;break;case 6:testcount_test6=temp;break;testfile.

8、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&am

9、p;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;for(i=0;ibn-1;i+)第二部分:void Generate_decision_tree(int bM+2,int bn,int attribute_test_list,int sn,int ai,in

10、t 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

11、)(path_aleavesi=path_aleaves-1i;path_bleavesi=path_bleaves-1i;coutn,IF ;for(i=1;i=Trip;i+)if(i=1) coutapath_bleavesi=path_aleavesi;else coutMAapath_bleavesiM=Mpath_aleavesi;cout THEN class=1;i-)if(path_aleavesi=avpath_bleavesi-1) Trip-=1;elsebreak;Trip-=1;leaves+=1;else(same_class=1;if(bi0=bi+10)for

12、(i=0,k=-1;il;i+)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;elsecoutAapath_bleavesi=path_aleavesi;cout THEN class=1;

13、i-)if(path_aleavesi=avpath_bleavesi-1)Trip-=1;elsebreak;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;k+;for(ll=0;llM+2;ll+)skll=aill;count=count-bn;elseif(sn=0)/候选属性集为空时，标记为训练集中最普通的类/记录路径与前一路径相同的部分for(i=1;iTri

14、p;i+)if(path_aleavesi=0)path_aleavesi=path_aleaves-1i;path_bleavesi=path_bleaves-1i;coutn,IF ;for(i=1;i=Trip;i+)if(i=1) coutapath_bleavesi=path_aleavesi;else coutMAapath_bleavesiM=Mpath_aleavesi;/判断类别for(i=0,ll=0,lll=0;illl) cout THEN class=0;path_aleaves0=0;elsecout1;i-)if(path_aleavesi=avpath_blea

15、vesi-1) Trip-=1;elsebreak;Trip-=1;leaves+=1;/未分类的样本集减少for(i=0,l=-1 ;i=count;i+)for(j=0,lll=0;jbn;j+)if(siM+1=bjM+1) III+;if(lll=O)l+=1;for(ll=0;IKM+2;ll+)al=siH；for(i=0,k=-1 ;il;i+)k+;for(ll=0;IKM+2;ll+)skll=aill;count=count-bn;else/待分结点的样本集不为空时定义count_Positive记录属于正例的样本数int count_Positive=0;/p1,p2分别

16、定义为正负例的比例double p1,p2;double Entropy_Es; /Entropy_Es表示熠for(i=0;i=count;i+)if(siO=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+)/以当前

17、属性分成的小类(每个属性包含的种类数)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_

18、test_listj-1-1sij-1+=1;elsessattribute_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_t

19、est_listi-1k;for(i=0;isn;i+)Eattribute_test_listi-1=0.0;/计算嫡for(j=0;javattribute_test_listi-1;j+)(/if语句处理0*log10(0)=0if(pattribute_test_listi-10j=0|pattribute_test_listi-11j=0) /初始化for(i=0;isn;i+)/当前的属性包含的个数for(i=1;i=avj;i+)pattribute_test_listi-10j=1;pattribute_test_listi-11j=1;Eattribute_test_list

20、i-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=att