决策树

决策树一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。

决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。比如，在贷款申请中，要对申请的风险大小做出判断，图是为了解决这个问题而建立的一棵决策树，从中我们可以看到决策树的基本组成部分：决策节点、分支和叶子。

决策树中最上面的节点称为根节点，是整个决策树的开始。决策树的每个节点子节点的个数与决策树在用的算法有关。如CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。决策树的内部节点（非树叶节点）表示在一个属性上的测试。

每个分支要么是一个新的决策节点，要么是树的结尾，称为叶子。在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上问题的不同回答导致不同的分支，最后会到达一个叶子节点。这个过程就是利用决策树进行分类的过程，利用几个变量（每个变量对应一个问题）来判断所属的类别（最后每个叶子会对应一个类别）。

下面来看个例子。

某电子商务公司要从A地向B地的用户发送一批价值为90000元的货物。从A地到B地有水、陆两条路线。走陆路时比较安全，其运输成本为10000元；走水路时一般情况下的运输成本只要7000元，不过一旦遇到暴风雨天气，则会造成相当于这批货物总价值的10%的损失。根据历年情况，这期间出现暴风雨天气的概率为1/4，那么该电子商务公司该如何选择呢？

这是一个不确定性决策问题，其决策树如图4-3-3所示。

图4-3-3    决策树示例

由于该问题本身带有外生的不确定因素，因此最终的结果不一定能预先确定。不过，该电子商务公司应该根据一般解决带概率分布、具有不确定性的问题时常用的数学期望值进行决策，而不是盲目碰运气或一味害怕、躲避风险。

根据本问题的决策树，走水路时，成本为7000元的概率为75%，成本为16000元的概率为25%，因此走水路的期望成本为(7000*75%)+(16000*25%) = 9250元。走陆路时，其成本确定为10000元。因此，走水路的期望成本小于走陆路的成本，所以应该选择走水路。