天气决策树ID3

一、上机目的及内容
1.上机内
根据下列给定的14个样本数据,运用ID3算法构造一个是否适宜打网球的天气决策树。

2.上机目的
（1）学习用Information Gain构造决策树的方法；
（2）在给定的例子上，构造出正确的决策树； （3）理解并掌握构造决策树的技术要点。

二、实验原理及基本技术路线图（方框原理图或程序流程图）
1、决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。

树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。

构造好的决策树的关键在于如何选择好的逻辑判断或属性。

对于同样一组例子，可以有很多决策树能符合这组例子。

人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。

要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。

由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。

用信息增益度量期望熵最低，来选择分类属性。

公式为
算法：
创建树的Root 结点
如果Examples 都为正，那么返回label=+中的单结点Root 如果Examples 都为反，那么返回lable=-单结点树Root
如果Attributes 为空，那么返回单节点树Root ，lable=Examples 中最普遍的目标属性值
否则开始
∑∑=∈⨯-=-=c
i i
i v A Values v v p p S Entropy S Entropy S
S S Entropy A S Gain 12)(log )()
()(),(
A<-Attributes中分类能力最好的属性
Root的决策属性<-A
对于每个可能值
在Root下加一个新的分支对应测试A=vi
令Example-vi为Examples中满足A属性值为vi的子集
如果Examples-vi为空
在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的目标属性值
否则在这个新分支下加一个子树ID3(example-vi,target-attribute,attributes-|A|)
结束
返回 Root
算法实现:
天气数据存放在data.txt 中；
第一行为样本数量14和每个样本中属性的数量4；
第二行为每个属性取值的数量；
后面n行皆为例子；
节点数据结构
struct DTNode
{
int name; //用 1,2,3,4表示选择的属性，0表示不用分类，即叶节点
int data[D_MAX+1]; //表示此节点包含的数据,data[i]=1,表示包含二维数
组data[][]中的第i条数据
int leaf; //leaf=1 正例叶节点；leaf=2 反例叶节点；leaf=0不是节点 int c; //c=1 正类；c=0 反类
DTNode *child[P+1]; //按属性值的个数建立子树
};
定义函数
void Read_data() //从数据文件data.txt中读入训练数据
DT_pointer Create_DT(DT_pointer Tree,int name,int value) //创建决策树int chose(int *da) //选择分类属性
float Gain(int *da,int p) //计算以p属性分类的期望熵
float Entropy(int *da) //计算数据的熵
int test_leaf(int *da) //测试节点属性
void Out_DT(DT_pointer Tree) //用线性表形式输出建立的决策树
int Class(int *da) //对输入的测试样本分类
全局变量
FILE *fp;
int p_num; //属性的数量
int pi[P_MAX+1]; //每个属性有几种取值
int d_num; //数据的数量
int data[P_MAX+1][D_MAX+1];//存储训练数据
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程）
#include "stdio.h"
#include "math.h"
int trnum;
struct tr
{
int key,childs,father,kind;
int child[4];
}tree[100];
int n=14,c[100][5],keykind[10][2],keykind_num;
int p,q;
int captionnum=4;
float mc;
int outtree[5];
int caption[10]={3,3,2,2};
char caption_name[5][10]={"天况","温度","湿度","风况","分类"};
char key_name[5][3][10]={{"晴","多云","雨"},{"热","中","冷"},{"大","正常"},{"无","有"},{"-","+"}};
void initdata()//初始化数据c[0][0]=1: 表示第一个实例的天况为晴
{
c[0][0]=1;c[0][1]=1;c[0][2]=1;c[0][3]=1;c[0][4]=1;
c[1][0]=1;c[1][1]=1;c[1][2]=1;c[1][3]=2;c[1][4]=1;
c[2][0]=2;c[2][1]=1;c[2][2]=1;c[2][3]=1;c[2][4]=2;
c[3][0]=3;c[3][1]=2;c[3][2]=1;c[3][3]=1;c[3][4]=2;
c[4][0]=3;c[4][1]=3;c[4][2]=2;c[4][3]=1;c[4][4]=2;
c[5][0]=3;c[5][1]=3;c[5][2]=2;c[5][3]=2;c[5][4]=1;
c[6][0]=2;c[6][1]=3;c[6][2]=2;c[6][3]=2;c[6][4]=2;
c[7][0]=1;c[7][1]=2;c[7][2]=1;c[7][3]=1;c[7][4]=1;
c[8][0]=1;c[8][1]=3;c[8][2]=2;c[8][3]=1;c[8][4]=2;
c[9][0]=3;c[9][1]=2;c[9][2]=2;c[9][3]=1;c[9][4]=2;
c[10][0]=1;c[10][1]=2;c[10][2]=2;c[10][3]=2;c[10][4]=2;
c[11][0]=2;c[11][1]=2;c[11][2]=1;c[11][3]=2;c[11][4]=2;
c[12][0]=2;c[12][1]=1;c[12][2]=2;c[12][3]=1;c[12][4]=2;
c[13][0]=3;c[13][1]=2;c[13][2]=1;c[13][3]=2;c[13][4]=1;
tree[0].father=-1;
}
void calculate_pq()//计算在当前条件限制下，p=正例多少个，q=反例多少个，{
int u,k,i;
p=0;q=0;
for (i=0;i<n;i++)
{
u=1;
for (k=1;k<=keykind_num;k++)
if (c[i][keykind[k][0]]!=keykind[k][1])
{
u=0;
break;
}
if (u)
if (c[i][4]==1) q++;else p++;
}
}
void calculate_keykind(int x)//找出从当前节点出发，所有父节点的属性
{
int i;
i=x;keykind_num=0;
while (tree[i].father>=0)
{
keykind_num++;
keykind[keykind_num][0]=tree[tree[i].father].key;
keykind[keykind_num][1]=tree[i].kind;
i=tree[i].father;
}
}
float calculate_mc(float x,float y)//计算相对于当前正例和反例的熵
{
if (x==0||y==0) return 0;
return -(x/(x+y))*(log(x/(x+y))/log(2))-(y/(x+y))*(log(y/(x+y))/log(2));
}
float calculate_gain(int x,int num,float mc1)//计算以属性x对当前节点进行决策的gain值
{
float bc=0;
int i;
keykind[keykind_num][0]=x;
for (i=0;i<caption[x];i++)//计算B(C,属性X)
{
keykind[keykind_num][1]=i+1;
calculate_pq();
bc=bc+((p+q)/(num+0.0))*calculate_mc(p,q);
}
return mc1-bc;
}
int findkey(int x)//找出当前点x的决策属性
{
int not_use[10],i;
calculate_keykind(x);//找出X节点及其父节点的所有决策
calculate_pq();//计算正反实例的个数
if (p==0||q==0) return -1;
mc=calculate_mc(p,q);//计算正反实例的熵
int num=p+q,nowkey=-2;
float max=-1,ans;
for (i=0;i<=captionnum;i++) not_use[i]=1;
for (i=1;i<=keykind_num;i++) not_use[keykind[i][0]]=0;
keykind_num++;
for (i=0;i<captionnum;i++)//枚举法一次讨论每个可用属性对X节点进行决策的gain值，取gain 值最大的属性为决策属性
if (not_use[i])
{
ans=calculate_gain(i,num,mc);
if (ans>max)
{
max=ans;
nowkey=i;
}
}
return nowkey;
}
void output_con(int x)//输出满足X节点以及其所有父节点的决策的实例集合
{
calculate_keykind(x);
int u,k,i;
p=0;q=0;
for (i=0;i<n;i++)
{
u=1;
for (k=1;k<=keykind_num;k++)
if (c[i][keykind[k][0]]!=keykind[k][1])
{
u=0;
break;
}
if (u)
{
for (k=0;k<captionnum;k++)
printf("%s,",key_name[k][c[i][k]-1]);
printf("%s\n",key_name[k][c[i][k]-1]);
}
}
}
void output(int x,int deep)//输出X节点的实例，如果X不是叶子节点，则递归，一直找到叶节点才输出满足相应决策的实例集合
{
outtree[deep]=x;
if (tree[x].childs>=0)
{
for (int i=0;i<=tree[x].childs;i++)
output(tree[x].child[i],deep+1);
}
else
{
printf("\n");
for (int j=0;j<=deep-1;j++)
{
printf("%s(%s)-->",caption_name[tree[outtree[j]].key],key_name[tree[outtree[j]].key][tree[outtree[j+1]].ki nd-1]);
}
printf("\n");
output_con(outtree[deep]);
}
}
void main()
{
int i;
initdata();
trnum=0;
int open=0;
while (open<=trnum)//open用来一次访问决策树的每个节点
//每次访问一个节点，就对其进行决策，如果决策成功，则将新的点加入到决策树中，直至不能再扩展
{
tree[open].key=findkey(open);//寻找决策属性
tree[open].childs=-1;
if (tree[open].key>=0)
{
for (i=0;i<caption[tree[open].key];i++)//决策成功，向决策树加入新的节点
{
trnum++;
tree[trnum].kind=i+1;
tree[open].childs++;
tree[open].child[tree[open].childs]=trnum;
tree[trnum].father=open;
}
}
open++;
}
output(0,0);
}
五、实验过程原始记录( 测试数据、图表、计算等)
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。

其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
通过该实验，我了解了如何采用ID3构建天气决策树，以及了解什么是熵，如何计算熵等等。

………。