📄 id3.cpp
字号:
#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iomanip.h>
#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[i][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][i][j]表示第k个候选属性划分的子集Sj中类Ci的样本数，数组的具体大小可根据给定训练数据调整
int ss[M][c][s_max];
//第k个候选属性划分的子集Sj中样本属于类Ci的概率
double p[M][c][s_max];
//count_s[i][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 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;
path_a[leaves][Trip]=ai;
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;
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;
}
}
}
}
}
}
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;
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[i][j];
}
//most记录训练集中哪类样本数比较多，以用于确定递归终止时不确定的类别
for(i=0,j=0,k=0;i<=count;i++){
if(s[i][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[i][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[i][path_b[j][1]]==path_a[j][1]&&test[i][path_b[j][2]]==path_a[j][2]&&test[i][path_b[j][3]]==path_a[j][3]&&test[i][path_b[j][4]]==path_a[j][4]&&test[i][path_b[j][5]]==path_a[j][5]&&test[i][path_b[j][6]]==path_a[j][6]){
l=1;
if(test[i][7]==path_a[j][0]) true_class+=1;
break;
}
if(test[i][7]==most && l==0) true_class+=1;
}
cout<<"测试集与训练集的比例为:"<<float(count_train)/count_test<<'\n';
cout<<"分类准确率为:"<<float(true_class)/count_test<<'\n';
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -