基本思想
1.选择一个属性放置在根节点，为每个可能的属性值产生一个分支
2.将样本划分成多个子集，一个子集对应于一个分支
3.在每个分支上递归地重复这个过程，仅使用真正到达这个分支的样本
4.如果在一个节点上的所有样本拥有相同的类别，即停止该部分树的扩展
ID3算法思想：
(1)初始化决策树T为只含一个树根(X,Q)，其中X是全体样本集，Q为全体属性集。
(2) if(T中所有叶节点(X’,Q’)都满足X属于同一类或Q’为空)then算法停止；
(3) else
{任取一个不具有(2)中所述状态的叶节点(X’,Q’)；
(4) for each Q’中的属性A do计算信息增益gain(A,X’)；
(5)选择具有最高信息增益的属性B作为节点(X’,Q’)的测试属性；
(6) for each B的取值bi do
{从该节点(X’,Q’)伸出分支，代表测试输出B=bi；
求得X中B值等于bi的子集Xi，并生成相应的叶节点(Xi’,Q’-{B})；}
(7)转(2)；}
ID3算法的问题：
(1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。
(2)ID3是非递增算法。
(3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。
(4)抗噪性差，训练例子中正例和反例的比例较难控制。
#include<iostream> #include<fstream> #include<string> #include<stdlib.h> #include<math.h> #include<iomanip> #include<string.h> using namespace std; #define N 500 //N定义为给定训练数据的估计个数 #define M 6 //M定义为候选属性的个数 #define c 2 //定义c=2个不同类 #define s_max 5 //定义s_max为每个候选属性所划分的含有最大的子集数 int av[M]={3,3,2,3,4,2}; int s[N][M+2],a[N][M+2]; //数组s[j]用来记录第i个训练样本的第j个属性值 int path_a[N][M+1],path_b[N][M+1]; //用path_a[N][M+1],path_b[N][M+1]记录每一片叶子的路径 int count_list=M; //count_list用于记录候选属性个数 int count=-1; //用count+1记录训练样本数 int attribute_test_list1[M]; int leaves=1; //用数组ss[k][j]表示第k个候选属性划分的子集Sj中类Ci的样本数，数组的具体大小可根据给定训练数据调整 int ss[M][c][s_max]; //第k个候选属性划分的子集Sj中样本属于类Ci的概率 double p[M][c][s_max]; //count_s[j]用来记录第i个候选属性的第j个子集中样本个数 int count_s[M][s_max]; //分别定义E[M]，Gain[M]表示熵和熵的期望压缩 double E[M]; double Gain[M]; //变量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[256],testname[256]; int test[N][8]; cout<<"请输入训练集文件名:"; cin>>trainname; ifstream trainfile; trainfile.open(trainname,ios::in|ios::nocreate); if(!trainfile){ cout<<"无法使用训练集，请重试!"<<'\n'; exit(1); } //读取训练集 while(trainfile>>temp){ j=j+1; k=j%(M+2); if(k==0||j==0) count+=1; //count为训练集的第几个,k代表室第几个属性 switch(k){ case 0:s[count][0]=temp; break; case 1:s[count][1]=temp; break; case 2:s[count][2]=temp; break; case 3:s[count][3]=temp; break; case 4:s[count][4]=temp; break; case 5:s[count][5]=temp; break; case 6:s[count][6]=temp; break; case 7:s[count][7]=temp; break; } } trainfile.close(); //输出训练集 for(i=0;i<=count;i++){ if(i%2==0) cout<<'\n'; for(j=0;j<M+2;j++) cout<<setw(4)<<s[j]; } //most记录训练集中哪类样本数比较多，以用于确定递归终止时不确定的类别 for(i=0,j=0,k=0;i<=count;i++){ if(s[0]==0) j+=1; else k+=1; } if(j>k) most=0; else most=1; //count_train记录训练集的样本数 count_train=count+1; //训练的属性 for(i=0;i<M;i++) attribute_test_list1[i]=i+1; //首次调用递归函数，即是生成根结点的分支 Generate_decision_tree(s,count+1,attribute_test_list1,count_list,0,0); cout<<'\n'<<"叶子结点的个数为:"<<leaves<<'\n'; cout<<"请输入测试集文件名:"; cin>>testname; ifstream testfile; testfile.open(testname,ios::in|ios::nocreate); if(!testfile){ cout<<"无法使用训练集，请重试!"<<'\n'; exit(1); } count_test=0; j=-1; //读取测试集数据 while(testfile>>temp){ j=j+1; k=j%(M+2); if(k==0) count_test+=1; switch(k){ case 0:test[count_test][7]=temp; break; case 1:test[count_test][1]=temp; break; case 2:test[count_test][2]=temp; break; case 3:test[count_test][3]=temp; break; case 4:test[count_test][4]=temp; break; case 5:test[count_test][5]=temp; break; case 6:test[count_test][6]=temp; break; } } testfile.close(); for(i=1;i<=count_test;i++) test[0]=0; //以确保评估分类准确率 cout<<"count_test="<<count_test<<'\n'; cout<<"count_train="<<count_train<<'\n'; //用测试集来评估分类准确率 for(i=1;i<=count_test;i++){ l=0; for(j=1;j<=leaves;j++) if(test[path_b[j][1]]==path_a[j][1]&&test[path_b[j][2]]==path_a[j][2]&&test[path_b[j][3]]==path_a[j][3]&&test[path_b[j][4]]==path_a[j][4]&&test[path_b[j][5]]==path_a[j][5]&&test[path_b[j][6]]==path_a[j][6]){ l=1; if(test[7]==path_a[j][0]) true_class+=1; break; } if(test[7]==most && l==0) true_class+=1; } cout<<"测试集与训练集的比例为:"<<float(count_train)/count_test<<'\n'; cout<<"分类准确率为:"<<float(true_class)/count_test<<'\n'; } void Generate_decision_tree(int b[][M+2],int bn,int attribute_test_list[],int sn,int ai,int aj) { //定义数组a记录目前待分的训练样本集，定义数组b记录目前要分结点中所含的训练样本集 //same_class用来记数，判别samples是否都属于同一个类 Trip+=1;//用Trip记录每一个叶子递归次数 path_a[leaves][Trip]=ai;//用path_a[N][M+1],path_b[N][M+1]记录每一片叶子的路径 path_b[leaves][Trip]=aj; int same_class,i,j,k,l,ll,lll; if(bn==0) {//待分结点的样本集为空时，加上一个树叶，标记为训练集中最普通的类 //记录路径与前一路径相同的部分 for(i=1;i<Trip;i++) if(path_a[leaves][i]==0){ path_a[leaves][i]=path_a[leaves-1][i]; path_b[leaves][i]=path_b[leaves-1][i]; } cout<<'\n'<<"IF "; for(i=1;i<=Trip;i++) if(i==1) cout<<"a["<<path_b[leaves][i]<<"]="<<path_a[leaves][i]; else cout<<"^a["<<path_b[leaves][i]<<"]="<<path_a[leaves][i]; cout<<" THEN class="<<most; path_a[leaves][0]=most; //修改树的深度 if(path_a[leaves][Trip]==av[path_b[leaves][Trip]-1]) for(i=Trip;i>1;i--) if(path_a[leaves][i]==av[path_b[leaves][i]-1]) Trip-=1; else break; Trip-=1; leaves+=1; } else { same_class=1; for(i=0;i<bn-1;i++) if(b[i][0]==b[i+1][0]) same_class+=1; if(same_class==bn){//待分样本集属于同一类时以该类标记 //记录路径与前一路径相同的部分 for(i=1;i<Trip;i++) if(path_a[leaves][i]==0){ path_a[leaves][i]=path_a[leaves-1][i]; path_b[leaves][i]=path_b[leaves-1][i]; } cout<<'\n'<<"IF "; for(i=1;i<=Trip;i++) if(i==1) cout<<"a["<<path_b[leaves][i]<<"]="<<path_a[leaves][i]; else cout<<"^a["<<path_b[leaves][i]<<"]="<<path_a[leaves][i]; cout<<" THEN class="<<b[0][0]; path_a[leaves][0]=b[0][0]; //修改树的深度 if(path_a[leaves][Trip]==av[path_b[leaves][Trip]-1]) for(i=Trip;i>1;i--) if(path_a[leaves][i]==av[path_b[leaves][i]-1]) Trip-=1; else break; Trip-=1; leaves+=1; //未分类的样本集减少 for(i=0,l=-1;i<=count;i++){ for(j=0,lll=0;j<bn;j++) if(s[i][M+1]==b[j][M+1]) lll++; if(lll==0){ l+=1; for(ll=0;ll<M+2;ll++) a[l][ll]=s[i][ll]; } } for(i=0,k=-1;i<l;i++){ k++; for(ll=0;ll<M+2;ll++) s[k][ll]=a[i][ll]; } count=count-bn; } else { if(sn==0){//候选属性集为空时，标记为训练集中最普通的类 //记录路径与前一路径相同的部分 for(i=1;i<Trip;i++) if(path_a[leaves][i]==0){ path_a[leaves][i]=path_a[leaves-1][i]; path_b[leaves][i]=path_b[leaves-1][i]; } cout<<'\n'<<"IF "; for(i=1;i<=Trip;i++) if(i==1) cout<<"a["<<path_b[leaves][i]<<"]="<<path_a[leaves][i]; else cout<<"^a["<<path_b[leaves][i]<<"]="<<path_a[leaves][i]; //判断类别 for(i=0,ll=0,lll=0;i<bn;i++){ if(b[i][0]==0) ll+=1; else lll+=1; } if(ll>lll) { cout<<" THEN class=0"; path_a[leaves][0]=0; } else { cout<<" THEN class=1"; path_a[leaves][0]=1; } //修改树的深度 if(path_a[leaves][Trip]==av[path_b[leaves][Trip]-1]) for(i=Trip;i>1;i--) if(path_a[leaves][i]==av[path_b[leaves][i]-1]) Trip-=1; else break; Trip-=1; leaves+=1; //未分类的样本集减少 for(i=0,l=-1;i<=count;i++){ for(j=0,lll=0;j<bn;j++) if(s[i][M+1]==b[j][M+1]) lll++; if(lll==0){ l+=1; for(ll=0;ll<M+2;ll++) a[l][ll]=s[i][ll]; } } for(i=0,k=-1;i<l;i++){ k++; for(ll=0;ll<M+2;ll++) s[k][ll]=a[i][ll]; } 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(s[i][0]==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); cout<<p1<<'\t'<<p2<<'\t'<<Entropy_Es<<'\n'; //初始化 for(i=0;i<sn;i++)//当前的属性包含的个数 for(j=0;j<c;j++)//类别 for(k=0;k<av[i];k++)//以当前属性分成的小类(每个属性包含的种类数) ss[attribute_test_list[i]-1][j][k]=0; //用数组ss[k][i][j]表示第k个候选属性划分的子集Sj中类Ci的样本数，数组的具体大小可根据给定训练数据调整 for(i=0;i<sn;i++) for(j=0;j<av[i];j++) count_s[attribute_test_list[i]-1][j]=0;//初始化某个属性的某个具体值的全部个数 for(i=0;i<count+1;i++) for(j=1;j<=sn;j++) if(s[i][0]==0){//找出每个属性具体某个值属于反例的个数 ss[attribute_test_list[j-1]-1][0][s[i][j]-1]+=1; count_s[attribute_test_list[j-1]-1][s[i][j]-1]+=1; } else { ss[attribute_test_list[j-1]-1][1][s[i][j]-1]+=1; count_s[attribute_test_list[j-1]-1][s[i][j]-1]+=1; } //计算分别以各个候选属性划分样本后，各个子集Sj中的样本属于类Ci的概率 for(i=0;i<sn;i++) for(j=0;j<c;j++) for(k=0;k<av[i];k++) if(count_s[attribute_test_list[i]-1][k]!=0) p[attribute_test_list[i]-1][j][k]=double(ss[attribute_test_list[i]-1][j][k])/count_s[attribute_test_list[i]-1][k]; for(i=0;i<sn;i++) E[attribute_test_list[i]-1]=0.0; //计算熵 for(i=0;i<sn;i++) for(j=0;j<av[attribute_test_list[i]-1];j++){ //if语句处理0*log10(0)=0 if(p[attribute_test_list[i]-1][0][j]==0||p[attribute_test_list[i]-1][1][j]==0) { p[attribute_test_list[i]-1][0][j]=1; p[attribute_test_list[i]-1][1][j]=1; } E[attribute_test_list[i]-1]+=(ss[attribute_test_list[i]-1][0][j]+ss[attribute_test_list[i]-1][1][j])*(-(p[attribute_test_list[i]-1][0][j]*log10(p[attribute_test_list[i]-1][0][j])/log10(2)+p[attribute_test_list[i]-1][1][j]*log10(p[attribute_test_list[i]-1][1][j])/log10(2)))/(count+1); } //计算熵的信息增益 for(i=0;i<sn;i++) Gain[attribute_test_list[i]-1]=Entropy_Es-E[attribute_test_list[i]-1]; //找出信息增益的最大值,用j记录哪个候选属性的信息增益最大 max_Gain=Gain[0]; j=attribute_test_list[0]-1; for(i=0;i<sn;i++)//找出最大的信息增益 if(max_Gain<Gain[attribute_test_list[i]-1]) { max_Gain=Gain[attribute_test_list[i]-1]; j=attribute_test_list[i]-1; } //利用得到的具有最大信息增益的属性来划分待分的样本集b[bn][8] int temp[s_max]; int b1[N][M+2]; int temp1=-1; int temp_b[s_max][N][M+2]; for(i=1;i<=av[j];i++){ temp[i]=-1; for(k=0;k<bn;k++)//样本的个数 if(b[k][j+1]==i){ temp[i]+=1; for(l=0;l<M+2;l++) temp_b[i][temp[i]][l]=b[k][l]; } } //对于每一个分支使用递归函数重复生成树 for(i=1;i<=av[j];i++){ for(k=0;k<=temp[i];k++) for(l=0;l<M+2;l++) b1[k][l]=temp_b[i][k][l]; if(i==1){ for(ll=0,l=0;ll<sn;ll++) if(attribute_test_list[ll]-1!=j) attribute_test_list[l++]=attribute_test_list[ll]; Generate_decision_tree(b1,k,attribute_test_list,l,i,j+1); sn-=1; } else { Generate_decision_tree(b1,k,attribute_test_list,sn,i,j+1); if(i==av[j]) attribute_test_list[sn]=j+1; } } } } } }
