决策树

在教学中的使用

决策树，影响性图表，应用函数以及其他的决策分析工具和方法主要的授课对象是学校里商业、健康经济学和公共卫生专业的本科生，属于运筹学和管理科学的范畴。

举例阐述

下面我们用例子来说明：
小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都来玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。
小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。
在2周时间内我们得到以下记录：
天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。当然还有顾客是不是在这些日子光顾俱乐部。最终他得到了14行5列的数据表格。
决策树模型就被建起来用于解决问题。
决策树是一个有向无环图。根结点代表所有数据。分类树算法可以通过变量outlook，找出最好地解释非独立变量play（打高尔夫的人）的方法。变量outlook的范畴被划分为以下三个组：
晴天，多云天和雨天。
我们得出第一个结论：如果天气是多云，人们总是选择玩高尔夫，而只有少数很着迷的甚至在雨天也会玩。
接下来我们把晴天组的分为两部分，我们发现顾客不喜欢湿度高于70%的天气。最终我们还发现，如果雨天还有风的话，就不会有人打了。
这就通过分类树给出了一个解决方案。小王（老板）在晴天，潮湿的天气或者刮风的雨天解雇了大部分员工，因为这种天气不会有人打高尔夫。而其他的天气会有很多人打高尔夫，因此可以雇用一些临时员工来工作。

公式

C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树的剪枝

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

由决策树扩展为决策图

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

Bash

决策树的代码实现可参考：决策树算法实现——Bash