分享

决策树

 穷且益坚青云志 2014-08-23

决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中,决策树是最直观的一种。决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

中文名 决策树
外文名 Decision Tree

□——决策点,是对几种可能方案的选择,即最后选择的最佳方案。如果决策属于多级决策,则决策树的中间可以有多个决策点,以决策树根部的决策点为最终决策方案。

○——状态节点,代表备选方案的经济效果(期望值),通过各状态节点的经济效果的对比,按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝,概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。

△——结果节点,将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。

【概述来源】

机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术,可以用于分析数据,同样也可以用来作预测。

从数据产生决策树的机器学习技术叫做决策树学习,通俗说就是决策树。

一个决策树包含三种类型的节点:

决策树学习也是资料探勘中一个普通的方法。在这里,每个决策树都表述了一种树型结构,它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时,递归过程就完成了。另外,随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树同时也可以依靠计算条件概率来构造。

决策树如果依靠数学的计算方法可以取得更加理想的效果。数据库已如下所示:

(x,y)=(x1,x2,x3…,xk,y)

相关的变量Y表示我们尝试去理解,分类或者更一般化的结果。其他的变量x1,x2,x3等则是帮助我们达到目的的变量。

决策树易于理解和实现,人们在在学习过程中不需要使用者了解很多的背景知识,这同时是它的能够直接体现数据的特点,只要通过解释后都有能力去理解决策树所表达的意义。[1]

对于决策树,数据的准备往往是简单或者是不必要的,而且能够同时处理数据型和常规型属性,在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

易于通过静态测试来对模型进行评测,可以测定模型可信度;如果给定一个观察的模型,那么根据所产生的决策树很容易推出相应的逻辑表达式。

1)对连续性的字段比较难预测。

2)对有时间顺序的数据,需要很多预处理的工作。

3)当类别太多时,错误可能就会增加的比较快。

4)一般的算法分类的时候,只是根据一个字段来分类。[2]

为了适应市场的需要,某地准备扩大电视机生产。市场预测表明:产品销路好的概率为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年进行扩建的方案。[3]

剪枝是决策树停止分支的方法之一,剪枝有分预先剪枝和后剪枝两种。预先剪枝是在树的生长过程中设定一个指标,当达到该指标时就停止生长,这样做容易产生“视界局限”,就是一旦停止分支,使得节点N成为叶节点,就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法,导致产生的树不纯度降差最大的地方过分靠近根节点。后剪枝中树首先要充分生长,直到叶节点都有最小的不纯度值为止,因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们,如果消去能引起令人满意的不纯度增长,那么执行消去,并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反,经过剪枝后叶节点常常会分布在很宽的层次上,树也变得非平衡。后剪枝技术的优点是克服了“视界局限”效应,而且无需保留部分样本用于交叉验证,所以可以充分利用全部训练集的信息。但后剪枝的计算量代价比预剪枝方法大得多,特别是在大样本集中,不过对于小样本的情况,后剪枝方法还是优于预剪枝方法的。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多