决策树程序实验.docx

决策树程序实验.docx决策树程序实验众所周知,数据库技术从20世纪80年代开始,己经得到广泛的普及和应用。随着数据库容量的膨胀,特别是数据仓库以及web等新型数据源的日益普及,人们面临的主要问题不再是缺乏足够的信息可以使用,而是面对浩瀚的数据海洋如何有效地利用这些数据。从数据屮生成分类器的一个特别冇效的方法是生成一个决策树(DecisionTree)0决策树表示方法是应用最广泛的逻辑方法之一,它从一组无次序、无规则的事例屮推理出决策树表示形式的分类规则。决策树分类方法采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支,在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则,整棵决策树就对应着一组析取表达式规则。决策树是应用非常广泛的分类方法,目前有多种决策树方法,如ID3、CM2、SLIQ、SPRINT等。一、问题描述].1相关信息决策诂是一个类似于流程图的树结构,其中毎个内部结点表示在一个属性上的测试,每个分支代表一个测试输入,而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。puter,它预测顾客是否可能购买计算机。内部结点用矩形表示,而树叶结点用椭I员I表示。为了对未知的样本分类,样本的屈性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则,因此决策树容易转化成分类规则。■决策树中每一个非叶结点对应着一个非类别屈性,树枝代表这个屈性的值。一个叶结点代表从树根到叶结点Z间的路径对应的记录所屈的类别屈性值。■每一个非叶结点都将与屈性屮具冇最大信息量的非类别屈性相关联。■采用信息增益來选择能够最好地将样木分类的屈性。信息增益基于信息论屮爛的概念。ID3总是选择具有最高信息增益(或最大爛压缩)的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小,并反映划分的最小随机性或“不纯性”。1・2问题重述1、 目标概念为“寿险促销”2、 让算每个属性的信息増益3、 确定根节点的测试属性数据收入范出存険促销信用K保险性别年龄40-50K否否453O-4OK是否女404O-5OK否否男423O-4OK是是4350-60K是女3820—3OK育女S53O-4OK是是3520—30K否273O-4OK否女4330—4()K是否女414O-5OK是育432O-3OK是女2950-60K是女394O-5OK否否5520—30K是是女19模型求解构造决策树的方法是采用自上而下的递归构造,其思路是:■以代表训练样本的单个结点开始建树(步骤1)O■如杲样木都在同一类,则该结点成为树叶,并用该类标记(步骤2和3)。■否则,算法使用称为信息增益的机遇爛的度量为启发信息,选择能最好地将样本分类的属性(步骤6)。该属性成为该结点的“测试”或“判定”属性(步骤7)。值得注意的是,在这类算法中,所有的属性都是分类的,即取离散值的。连续值的属性必须离散化。■对测试属性的每个已知的值,创建一个分支,并据此划分样木(步骤8〜10)。■算法使用同样的过程,递归地形成每个划分上的样本决策树。一旦一个屈性岀现在一个结点上,就不必考虑该结点的任何后代(步骤13)o■递归划分步骤,当下列条件Z—成立时停止:给定结点的所冇样本属于同一类(步骤2和3)。没有剩余属性可以用来进一步划分样木(步骤4)。在此情况下,采用多数表决(步骤5)。这涉及将给定的结点转换成树叶,并用samples•I•的多数所在类别标记它。换一种方式,可以存放结点样本的类分布。分支test_attribute=aj没有样本。在这种情况下,以samples中的多数类创建一个树叶(由骤12)o算法Decision_Tree(samples,attribute_list)输入由离散值圍性描述的训练样本集samples;候选属性集合attribute_listo输出一棵决策树。创建节点N;Ifsamples都在同一类C中then返回N作为叶节点,以类C标记;Ifattribute_list为空then(5)返回N作为叶节点,以samples中最普遍的类标记;//多数表决选择attribute_list中具有最高信息增益的属性test_attribute;以test_attribute标记节点N;Foreachtestattribute的已知值v〃划分samples由节点N分出一个对应test_attribute=v的分支;令Sv为samples中test_attribute=v的样本集合;//一个划分块IfSv为空then加上一个叶节点,以samples中最普遍的类标记;Else加入一个由Decision_Tree(Sv,attribute_list~test_attr让ute)返回节点值E(S)=(-