最新决策树教学讲义ppt课件.ppt

《最新决策树教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、决策树目录1决策树的应用过程2决策树的细节分析3示例应用详解决策树的应用过程学前总结数据挖掘的研究方向有很多：数据的分类、聚类、分析与预测、关联规则挖掘、序列模式挖掘等。数据挖掘的主要方法：统计方法、决策树、神经网络、人工智能、贝叶斯网络、相关规则、数据可视化、遗传算法、近邻算法、连机分析处理、粗糙集。数据挖掘中的统计方法，如描述统计、概率论、回归分析、时间序列分析、多元分析等，多元分析中又包含有主成分分析、因子分析、判别分析、聚类分析及典型相关分析等。决策树分类算法起源于概念学习系统CLS(ConceptLearnin

2、gSystem)，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5，有名的决策树方法还有CART和Assistant，Sliq、Sprint等等。最初利用信息论中信息增益方法寻找数据库中具有最大信息量的字段，作决策树的一个结点字段的某些值作门限建立树的分支；在分支下建立下层结点和子分支，生成一棵决策树。再剪枝，优化，然后把决策树转化为规则，利用这些规则可以对新事例进行分类。决策树的应用过程决策树的决策过程1绘制树状图，根据已知条件排列出各个方案和每一方案的各种自然状态。2将各状态概率及损益值标于概率枝上

3、。3计算各个方案期望值并将其标于该方案对应的状态结点上。4进行剪枝，比较各个方案的期望值，并标于方案枝上，将期望值小的(即劣等方案剪掉)所剩的最后方案为最佳方案。决策树的应用过程决策树的应用实现某企业在下年度有甲、乙两种产品方案可供选择。每种方案都面临滞销、一般、和畅销三种市场状态。各状态的概率和损益值如下图左，以及应用决策树解决如下图右。目录1决策树的应用过程2决策树的细节分析3示例应用详解决策树的细节分析决策树的计算方法决策树的细节分析决策树的计算方法决策树的细节分析决策树的计算方法决策树的细节分析决策树的计算方法决

4、策树的细节分析决策树的剪枝剪枝按其实施的时间分为两种方法：事前修剪法、事后修剪法---事前剪枝---该方法通过提前停止树的构造而对树“剪枝”，即通过在当前节点上判断是否需要继续划分该节点所含训练样本集来实现。一旦停止，节点不再继续分裂，当前节点就成为一个叶节点。该叶节点中可能包含多个不同类别的训练样本，由于该修剪是在分枝之前做出的，所以称之为事前修剪。事前修剪法的优点是在树生成的同时进行了剪枝，因而效率高，但是它可能剪去了某些有用但还没生成的节点。常用的方法是设定决策树的最大高度(层数)来限制树的生长。还有一种方法是设定

5、每个节点必须包含的最少记录数，当节点中记录的个数小于这个数值时就停止分割。然而，选择一个适当的阈值是比较困难的，较高的阈值可能导致过分简化的树，而较低的阈值可能会导致多余树枝无法修剪。决策树的细节分析决策树的剪枝---事后剪枝---该方法是由完全生长的树剪去分枝。通过删除节点的分枝，剪掉树节点。它在允许决策树得到最充分生长的基础上，再根据一定的规则，剪去决策树中的那些不具有一般代表性的叶节点或分枝。修剪后，被修剪的分枝节点就成为一个叶节点，并将其标记为它所包含样本中类别个数最多的类别。事后修剪是一边修剪一边检验的过程，一

6、般规则是：当树建好之后，对每个内部节点，首先计算该节点上的子树被剪枝可能出现的错误率，然后，使用每个分枝的错误率，结合沿每个分枝观察的权重评估，计算不对该节点剪枝的期望错误率。如果剪掉该节点能够降低错误率，那么该节点的所有子节点就被剪掉，该节点成为叶节点。产生一组逐渐被剪枝的树之后，使用一个独立的测试集评估每棵树的准确率，就能得到具有最小期望错误率的决策树。当然也可以结合使用事前修剪和事后修剪，形成混合的修剪方法。事后修剪比事前修剪需要更多的计算时阃，但通常产生的决策树更为可靠。目录1决策树的应用过程2决策树的细节分析3

7、示例应用详解示例应用详解例：构造决策树。下表给出了取自AllElectronics顾客数据库元组训练集。编号年龄收入学生信用等级类别：购买电脑1<=30高否一般不会购买2<=30高否良好不会购买331…40高否一般会购买4>40中等否一般会购买5>40低是一般会购买6>40低是良好不会购买731…40低是良好会购买8<=30中等否一般不会购买9<=30低是一般会购买10>40中等是一般会购买11<=30中等是良好会购买1231…40中等否良好会购买1331…40高是一般会购买14>40中等否良好不会购买示例应用详解解：由

8、题意可知：s＝14，类标号属性“购买电脑”有两个不同值（即｛会购买，不会购买｝），因此有两个不同的类（即m＝2）。设类C1对应于“会购买”，类C2对应于“不会购买”。则s1＝9，s2＝5，p1＝9/14，p2=5/14。①计算对给定样本分类所需的期望信息：②计算每个属性的熵。先计算属性“年龄”的熵。对于年龄＝“<=3