天气决策树

-1-昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：人工智能开课实验室：信自楼计算机机房4442011年12月23日年级、专业、班学号姓名成绩实验项目名称天气决策树指导教师吴霖教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.上机内根据下列给定的14个数据,运用InformationGain构造一个天气决策树。例子编号属性分类天况温度湿度风况1晴热大无N2晴热大有N3多云热大无P4雨中大无P5雨冷正常无P6雨冷正常有N7多云冷正常有P-2-8晴中大无N9晴冷正常无P10雨中正常无P11晴中正常有P12多云中大有P13多云热正常无P14雨中大有N2.上机目的（1）学习用InformationGain构造决策树的方法；（2）在给定的例子上，构造出正确的决策树；（3）理解并掌握构造决策树的技术要点。二、实验原理及基本技术路线图（方框原理图或程序流程图）1、决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。用信息增益度量期望熵最低，来选择分类属性。公式为-3-算法：创建树的Root结点如果Examples都为正，那么返回label=+中的单结点Root如果Examples都为反，那么返回lable=-单结点树Root如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值否则开始A-Attributes中分类能力最好的属性Root的决策属性-A对于每个可能值在Root下加一个新的分支对应测试A=vi令Example-vi为Examples中满足A属性值为vi的子集如果Examples-vi为空在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的目标属性值否则在这个新分支下加一个子树ID3(example-vi,target-attribute,attributes-|A|)结束返回RootciiivAValuesvvppSEntropySEntropySSSEntropyASGain12)(log)()()(),(-4-算法实现:天气数据存放在data.txt中；第一行为样本数量14和每个样本中属性的数量4；第二行为每个属性取值的数量；后面n行皆为例子；节点数据结构structDTNode{intname;//用1,2,3,4表示选择的属性，0表示不用分类，即叶节点intdata[D_MAX+1];//表示此节点包含的数据,data[i]=1,表示包含二维数组data[][]中的第i条数据intleaf;//leaf=1正例叶节点；leaf=2反例叶节点；leaf=0不是节点intc;//c=1正类；c=0反类DTNode*child[P+1];//按属性值的个数建立子树};定义函数voidRead_data()//从数据文件data.txt中读入训练数据DT_pointerCreate_DT(DT_pointerTree,intname,intvalue)//创建决策树intchose(int*da)//选择分类属性floatGain(int*da,intp)//计算以p属性分类的期望熵floatEntropy(int*da)//计算数据的熵inttest_leaf(int*da)//测试节点属性-5-voidOut_DT(DT_pointerTree)//用线性表形式输出建立的决策树intClass(int*da)//对输入的测试样本分类全局变量FILE*fp;intp_num;//属性的数量intpi[P_MAX+1];//每个属性有几种取值intd_num;//数据的数量intdata[P_MAX+1][D_MAX+1];//存储训练数据三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）#includestdio.h#includemath.hinttrnum;structtr{intkey,childs,father,kind;intchild[4];}tree[100];intn=14,c[100][5],keykind[10][2],keykind_num;intp,q;intcaptionnum=4;floatmc;intouttree[5];intcaption[10]={3,3,2,2};charcaption_name[5][10]={天况,温度,湿度,风况,分类};charkey_name[5][3][10]={{晴,多云,雨},{热,中,冷},{大,正常},{无,有},{-,+}};-6-voidinitdata()//初始化数据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;}voidcalculate_pq()//计算在当前条件限制下，p=正例多少个，q=反例多少个，{intu,k,i;p=0;q=0;for(i=0;in;i++){u=1;for(k=1;k=keykind_num;k++)if(c[i][keykind[k][0]]!=keykind[k][1]){u=0;break;}-7-if(u)if(c[i][4]==1)q++;elsep++;}}voidcalculate_keykind(intx)//找出从当前节点出发，所有父节点的属性{inti;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;}}floatcalculate_mc(floatx,floaty)//计算相对于当前正例和反例的熵{if(x==0||y==0)return0;return-(x/(x+y))*(log(x/(x+y))/log(2))-(y/(x+y))*(log(y/(x+y))/log(2));}floatcalculate_gain(intx,intnum,floatmc1)//计算以属性x对当前节点进行决策的gain值{floatbc=0;inti;keykind[keykind_num][0]=x;for(i=0;icaption[x];i++)//计算B(C,属性X){keykind[keykind_num][1]=i+1;calculate_pq();bc=bc+((p+q)/(num+0.0))*calculate_mc(p,q);}returnmc1-bc;}intfindkey(intx)//找出当前点x的决策属性{intnot_use[10],i;calculate_keykind(x);//找出X节点及其父节点的所有决策calculate_pq();//计算正反实例的个数if(p==0||q==0)return-1;mc=calculate_mc(p,q);//计算正反实例的熵intnum=p+q,nowkey=-2;floatmax=-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;-8-keykind_num++;for(i=0;icaptionnum;i++)//枚举法一次讨论每个可用属性对X节点进行决策的gain值，取gain值最大的属性为决策属性if(not_use[i]){ans=calculate_gain(i,num,mc);if(ansmax){max=ans;nowkey=i;}}returnnowkey;}voidoutput_con(intx)//输出满足X节点以及其所有父节点的决策的实例集合{calculate_keykind(x);intu,k,i;p=0;q=0;for(i=0;in;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;kcaptionnum;k++)printf(%s,,key_name[k][c[i][k]-1]);printf(%s\n,key_name[k][c[i][k]-1]);}}}voidoutput(intx,intdeep)//输出X节点的实例，如果X不是叶子节点，则递归，一直找到叶节点才输出满足相应决策的实例集合{outtree[deep]=x;if(tree[x].childs=0){for(inti=0;i=tree[x].childs;i++)-9-output(tree[x].child[i],deep+1);}else{printf(\n);for(intj=0;j=deep-1;j++){printf(%s(%s)--,caption_name[tree[outtree[j]].key],key_name[tree[outtree[j]].key][tree[outtree[j+1]].kind-1]);}printf(\n);output_con(outtr