Difference between revisions 26422772 and 28589489 on zhwiki

< previous diff
next diff >
决策树
[[决策论]]中 (如[[风险管理]])，'''决策树'''({{lang|en|Decision tree}})由一个决策[[图论|图]]和可能的结果(包括资源成本和风险)组成， 用来创建到达目标的规划。决策树建立并用来辅助决策，是一种特殊的[[树结构]]。决策树是一个利用像树一样的图形或决策模型的决策支持工具，包括随机事件结果，资源代价和实用性。它是一个算法显示的方法。决策树经常在运筹学中使用，特别是在决策分析中，它帮助确定一个能最可能达到目标的策略。如果在实际中，决策不得不在没有完备知识的情况下被在线采用，一个决策树应该平行概率模型作为最佳的选择模型或在线选择模型算法。决策树的另一个使用是作为计算条件概率的描述性手段。

==簡介==
(contracted; show full)

与设置停止增长条件相对应的是在树建立好之后对其进行修剪。先允许树尽量生长，然后再把树修剪到较小的尺寸，当然在修剪的同时要求尽量保持决策树的准确度尽量不要下降太多。

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

==由决策树扩展为决策图==
在决策树中所有从根到叶节点的路径都是通过“与”（AND）运算连接。在决策图中可以使用“或”来连接多于一个的路径。

== 决策树的实现 ==
===Bash===
决策树的代码实现可参考：[http://liuzhiqiangruc.iteye.com/blog/1601922 决策树算法实现——Bash]
(contracted; show full)
[[Category:决策论]]
[[Category:分类算法]]
[[Category:机器学习]]
[[Category:人工智能]]


[[category:机器学习]]