实验二-决策树实验-实验报告

1、决策树实验一、实验原理 决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer，它预测顾客是否可能购买计算机。内部结点用矩形表示，而树叶结点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。 图1ID3算法：      决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树

2、根到叶结点之间的路径对应的记录所属的类别属性值。      每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。      采用信息增益来选择能够最好地将样本分类的属性。信息增益基于信息论中熵的概念。ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。二、算法伪代码算法Decision_Tree(data,AttributeName)输入由离散值属性描述的训练样本集data;候选属性集合Attrib

3、uteName。输出一棵决策树。（1） 创建节点N；（2） If samples 都在同一类C中then（3） 返回N作为叶节点，以类C标记；（4） If attribute_list为空then（5） 返回N作为叶节点，以samples 中最普遍的类标记；/多数表决（6） 选择attribute_list 中具有最高信息增益的属性test_attribute;（7） 以test_attribute 标记节点N；（8） For each test_attribute 的已知值v /划分 samples（9） 由节点N分出一个对应test_attribute=v的分支；（10令Sv为 sampl

4、es中 test_attribute=v 的样本集合；/一个划分块（11）If Sv为空 then（12）加上一个叶节点，以samples中最普遍的类标记；（13）Else 加入一个由Decision_Tree(Sv,attribute_list-test_attribute)返回节点值。三、实验数据预处理Age:30岁以下标记为“1”；30岁以上50岁以下标记为“2”；50岁以上标记为“3”。Sex：FEMAL-“1”；MALE-“2”Region：INNER CITY-“1”；TOWN-“2”； RURAL-“3”； SUBURBAN-“4”Income：50002万-“1”；2万4万-“

5、2”；4万以上-“3”MarriedChildrenCarMortgagePep：以上五个条件，若为“是”标记为“1”，若为“否”标记为“2”。Age sex region income married children car mortgage pep1 2 1 1 2 1 1 2 21 2 1 1 2 2 2 2 12 1 4 1 2 1 2 2 12 1 1 1 1 2 2 2 21 2 1 1 1 2 2 2 21 2 1 1 2 1 2 1 12 1 2 1 1 2 1 1 22 1 1 1 2 1 1 2 12 1 3 1 2 2 1 2 12 1 2 2 2 1 2 2 22 2

6、 1 2 2 2 2 1 12 1 2 2 1 1 2 1 12 2 1 2 1 2 2 1 21 1 1 2 1 2 2 2 13 2 1 2 1 1 1 2 21 1 1 2 1 1 1 2 11 1 3 2 2 2 1 2 13 1 2 2 1 2 2 2 13 2 3 3 1 1 1 2 13 2 2 3 1 2 1 1 23 1 3 3 1 1 2 2 13 2 1 3 1 2 1 2 23 2 1 3 1 1 1 1 13 1 1 3 1 2 1 1 23 1 3 3 1 2 2 2 23 2 4 3 1 2 2 1 13 1 3 3 2 2 1 1 2 4、 实验主函数funct

7、ion mainclc;DataSet=1 2 1 1 2 1 1 2 21 2 1 1 2 2 2 2 12 1 4 1 2 1 2 2 12 1 1 1 1 2 2 2 21 2 1 1 1 2 2 2 21 2 1 1 2 1 2 1 12 1 2 1 1 2 1 1 22 1 1 1 2 1 1 2 12 1 3 1 2 2 1 2 12 1 2 2 2 1 2 2 22 2 1 2 2 2 2 1 12 1 2 2 1 1 2 1 12 2 1 2 1 2 2 1 21 1 1 2 1 2 2 2 13 2 1 2 1 1 1 2 21 1 1 2 1 1 1 2 11 1 3 2

8、2 2 1 2 13 1 2 2 1 2 2 2 13 2 3 3 1 1 1 2 13 2 2 3 1 2 1 1 23 1 3 3 1 1 2 2 13 2 1 3 1 2 1 2 23 2 1 3 1 1 1 1 13 1 1 3 1 2 1 1 23 1 3 3 1 2 2 2 23 2 4 3 1 2 2 1 13 1 3 3 2 2 1 1 2 ;AttributName=11 12 13 14 15 16 17 18 19;Tree RulesMatrix=DecisionTree(DataSet,AttributName)End五、实验结果The Decision Tree:

9、(The Root):Attribut |_1_Attribut | |_1_Attribut | | |_1_Attribut | | | |_1_leaf 1 | | | |_2_leaf 2 | | |_2_leaf 2 | | |_3_Attribut | | |_1_Attribut | | | |_1_leaf 1 | | | |_2_leaf 2 | | | |_3_leaf 1 | | |_2_leaf 2 | |_2_Attribut | |_1_Attribut | | |_1_leaf 2 | | |_2_leaf 1 | |_2_leaf 1 |_2_Attribut

10、| |_1_leaf 2 | |_2_Attribut | | |_1_leaf 1 | | |_2_leaf 2 | |_3_leaf 2 |_3_Attribut | |_1_leaf 2 | |_2_Attribut | |_1_leaf 1 | |_2_Attribut | |_1_leaf 1 | |_2_leaf 2 |_4_leaf 1Tree = Attribut: 3 Child: 1x4 structRulesMatrix = 1 1 1 0 1 0 0 0 1 1 2 1 0 1 0 0 0 2 2 0 1 0 1 0 0 0 2 3 0 1 1 1 1 0 0 1 3 0 1 2 1 1 0 0 2 3 0 1 3 1 1 0 0 1 3 0 1 0 1 2 0 0 2 1 0 1 0 2 0 1 0 2 2 0 1 0 2 0 1 0 1 0 0 1 0 2 0 2 0 1 0 0 2 1 0 0 0 0 2 0 0 2 2 1 0 0 0 1 0 0 2 2 2 0 0 0 2 0 0 2 3 0 0 0 0