天气决策树(共11页).doc

《天气决策树(共11页).doc》由会员分享，可在线阅读，更多相关《天气决策树(共11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：人工智能 开课实验室：信自楼计算机机房444 2011 年12月 23日年级、专业、班学号姓名成绩实验项目名称天气决策树指导教师 吴霖教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内根据下列给定的14个数据,运用

2、Information Gain构造一个天气决策树。例子编号属 性分类天况温度湿度风况1晴热大无N2晴热大有N3多云热大无P4雨中大无P5雨冷正常无P6雨冷正常有N7多云冷正常有P8晴中大无N9晴冷正常无P10雨中正常无P11晴中正常有P12多云中大有P13多云热正常无P14雨中大有N2.上机目的（1）学习用Information Gain构造决策树的方法；（2）在给定的例子上，构造出正确的决策树；（3）理解并掌握构造决策树的技术要点。二、实验原理及基本技术路线图（方框原理图或程序流程图）1、决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明

3、了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。用信息增益度量期望熵最低，来选择分类属性。公式为算法：创建树的Root结点如果Examples都为正，那么返回label=+中的单结点Root如果Examples都为反，那么返回lable=-单结点树Root如果A

4、ttributes为空，那么返回单节点树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算法实现:天气数据存放在data.txt 中；第

5、一行为样本数量14和每个样本中属性的数量4；第二行为每个属性取值的数量；后面n行皆为例子；节点数据结构struct DTNode int name; /用 1,2,3,4表示选择的属性，0表示不用分类，即叶节点 int dataD_MAX+1; /表示此节点包含的数据,datai=1,表示包含二维数组data中的第i条数据 int leaf; /leaf=1 正例叶节点；leaf=2 反例叶节点；leaf=0不是节点 int c; /c=1 正类 ；c=0 反类 DTNode *childP+1; /按属性值的个数建立子树;定义函数void Read_data() /从数据文件data.txt

6、中读入训练数据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; /属性的数量in

7、t piP_MAX+1; /每个属性有几种取值int d_num; /数据的数量int dataP_MAX+1D_MAX+1;/存储训练数据三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件四、实验方法、步骤（或：程序代码或操作过程）#include stdio.h#include math.hint trnum;struct trint key,childs,father,kind;int child4;tree100;int n=14,c1005,keykind102,keykind_num;int p,q;int captionnum=4;flo

8、at mc;int outtree5;int caption10=3,3,2,2;char caption_name510=天况,温度,湿度,风况,分类;char key_name5310=晴,多云,雨,热,中,冷,大,正常,无,有,-,+;void initdata()/初始化数据 c00=1: 表示第一个实例的天况为晴c00=1;c01=1;c02=1;c03=1;c04=1;c10=1;c11=1;c12=1;c13=2;c14=1;c20=2;c21=1;c22=1;c23=1;c24=2;c30=3;c31=2;c32=1;c33=1;c34=2;c40=3;c41=3;c42=2;

9、c43=1;c44=2;c50=3;c51=3;c52=2;c53=2;c54=1;c60=2;c61=3;c62=2;c63=2;c64=2;c70=1;c71=2;c72=1;c73=1;c74=1;c80=1;c81=3;c82=2;c83=1;c84=2;c90=3;c91=2;c92=2;c93=1;c94=2;c100=1;c101=2;c102=2;c103=2;c104=2;c110=2;c111=2;c112=1;c113=2;c114=2;c120=2;c121=1;c122=2;c123=1;c124=2;c130=3;c131=2;c132=1;c133=2;c134=

10、1;tree0.father=-1;void calculate_pq()/计算在当前条件限制下，p=正例多少个，q=反例多少个，int u,k,i;p=0;q=0; for (i=0;in;i+)u=1;for (k=1;k=0) keykind_num+;keykindkeykind_num0=treetreei.father.key;keykindkeykind_num1=treei.kind;i=treei.father;float calculate_mc(float x,float y)/计算相对于当前正例和反例的熵if (x=0|y=0) return 0;return -(x/

11、(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;keykindkeykind_num0=x; for (i=0;icaptionx;i+)/计算 B(C,属性X)keykindkeykind_num1=i+1;calculate_pq(); bc=bc+(p+q)/(num+0.0)*calculate_mc(p,q);return mc1-bc;int findke

12、y(int x)/找出当前点x的决策属性int not_use10,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_usei=1;for (i=1;i=keykind_num;i+) not_usekeykindi0=0;keykind_num+;for (i=0;im

13、ax)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;in;i+)u=1;for (k=1;k=keykind_num;k+)if (cikeykindk0!=keykindk1) u=0;break;if (u)for (k=0;k=0) for (int i=0;i=treex.childs;i+) output(treex.childi,deep+1); else printf(n);

14、 for (int j=0;j,caption_nametreeouttreej.key,key_nametreeouttreej.keytreeouttreej+1.kind-1); printf(n); output_con(outtreedeep); void main()int i;initdata(); trnum=0; int open=0; while (open=0) for (i=0;icaptiontreeopen.key;i+)/决策成功，向决策树加入新的节点 trnum+; treetrnum.kind=i+1; treeopen.childs+; treeopen.c

15、hildtreeopen.childs=trnum; treetrnum.father=open; open+; output(0,0);五、实验过程原始记录( 测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）通过该实验，我了解了如何采用Information Gain构建天气决策树，以及了解什么是熵，如何计算熵等等。而在编写本程序过程中，让我复习了C语言的很多知识，实验虽然能够实现功能，但是还存在不足之处，例如默认训练数据是正确的，对是否发生错误不予考虑；没有考虑训练数据可以包含缺少属性值的实例；只能分正反两类。同时，通过上机，我更加深刻的体会到了理论与实践一致性的重要，有时候我们是懂得了理论知识，但是在具体的运用之中，我们会发现很难实施，因此我们要多进行实践操作，这样很有利于我们以后的学习，提高我们的实际操作能力。专心-专注-专业