决策树法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,决策树法,决策树的简介,决策树(Decision Tree）,是在已知各种情况发生概率的,基础,上，通过构成决策树来求取净现值的,期望值,大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。,决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则,；,采用,自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性值从该节点向下分支，而叶节点是要学习划分的类,。,从,根节点到叶节点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。,决策树的构造,决策树图示,决策点,方案枝,状态枝,机会点,后果点,名词解释,决策点,：一般用方形框表示,决策者在这里对各,行动方案进行选择,.,方案枝,：由决策点引出的代,表行动方案的线段,.,机会点,：方案枝末端的圆,.,状态枝,：由机会点引出的代,表可能发生的状态,的线段,.,后果点,：状态枝末端的三角,形,.,d,1,d,2,d,3,P(,h,1,),P(,h,2,),P(,h,1,),P(,h,2,),P(,h,1,),P(,h,2,),l,(,d,1,h,1,),l(d,1,h,2,),l(d,2,h,1,),l(d,2,h,2,),l,(,h,3,h,1,),l,(,h,3,h,2,),决策树的一般表示：,d,1,d,2,d,3,表示,3,种行动方案,.,P,(,h,1,),P,(,h,2,),表示,2,种可能状态的概率，,l,(,d,h,),(,或,q,(,d,h,),则表示损益函数的值,.,之后先计算出损益函数的均值写在机会点上，再根据决策目标选择最优方案，,最后剪去其他方案,.,决策树的剪枝,剪枝是决策树停止分支的方法之一，剪枝有分,预先剪枝,和,后剪枝,两种,。,决策树的剪枝,预先剪枝,是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生,“,视界局限,”,，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行,“,好,”,的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。,决策树的剪枝,后剪枝,中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服,“,视界局限,”,。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种,“,合并,”,叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。,明确,问题的决策目标，所有行动方案，所有 可能状态，状态分布列，损益函数的所有取值；,从,左到右依次画出决策点，方案枝，机会点，机会枝后果点，并标注；,计算,并标注机会点的值；,根据,决策目标选择最优方案，并剪去其他方案枝,.,绘制决策树的步骤：,为了适应市场的需要，某地准备扩大电视机生产。市场预测表明：产品销路好的概率为,0.7,；销路差的概率为,0.3,。备选方案有三个：第一个方案是建设大工厂，需要投资,600,万元，可使用,10,年；如销路好，每年可赢利,200,万元；如销路不好，每年会亏损,40,万元。第二个方案是建设小工厂，,需投资,280,万元；如销路好，每年可赢利,80,万元；如销路不好，每年也会赢利,60,万元。第三个方案也是先建设小工厂，但是如销路好，,3,年后扩建，扩建需投资,400,万元，可使用,7,年，扩建后每年会赢利,190,万元。,试作出决策。,实例,计算各点期望值：,点,：,0.7,200,10+0.3,（,-40,）,10-600,（投资）,=680,（,万 元,）,点,：,1.0,190,7-400=930,（万元）,点,：,1.0,80,7=560,（万元,）,比较决策点,4,的情况可以,看到,由于,点（,930,万元）与点（,560,万元）相比，点的期望利润值较大，因此应采用扩建的方案，而舍弃不扩建的方案,。,解：,把,点的,930,万元移到点,4,来，可计算出点的期望利润值,。,点,：,0.7,80,3+0.7,930+0.3,60,（,3+7,）,-280=719,（万元）最后比较决策点,1,的情况。由于点（,719,万元）与点,（,680,万元）相比，点的期望利润值较大，因此取点而,舍点,。,解：,这样，相比之下，建设大工厂的方案不是最优方案,，,合理的策略应采用前,3,年建小工厂，如销路好，后,7,年进行,扩建的,方案,。,决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。,对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。,易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。,优点,小结,1),对连续性的字段比较难预测。,2),对有时间顺序的数据，需要很多预处理的工作。,3),当类别太多时，错误可能就会增加的比较快。,4),一般的算法分类的时候，只是根据一个字段来分类。,小结,缺点,再见！,