7.3决策树
决策树
[P1] 对于现实生活中的复杂问题，由于影响决策的因素较多、相互之间的关系复杂等原因，人们经常有意或无意地采用多阶段决策法来解决这些问题。多阶段决策法把决策问题看作一个前后关联的具有链状结构的多阶段过程，并且各阶段间具有时间上的先后顺序。决策者需要做出时间上有先后之别的多次决策，并最终将多次决策的结果汇总成对当前问题的最终决策。这种过程的一种最自然的表达方式就是决策树。
[P2] 这一章我们分三节来讲解，第一节讲解什么是决策树，后面两节分别讲解决策树的 ID3 和 C4.5 生成算法。对于简单的问题，基于知识和经验，我们可以人工构建决策树，但是对于一些包含大量数据和影响因素的复杂问题，人工构建决策树的方法是不可行的。本章介绍的决策树算法可以通过自动化的、智能的方法找出数据中各因素与决策结果之间的复杂关系，从而自动地构建针对当前问题的决策树。
[P3] 一棵决策树由3类结点构成：根结点、内部结点（决策结点）和叶子结点。其中，根结点和内部结点都对应着要进行分类的属性集中的一个属性，而叶子结点是分类中的类标签的集合。
[P4] 现在我们来看一个具体的决策树的例子。如图所示是一棵决策树，它先测试 年龄 属性，对应的是根结点，当年龄属性取值小于等于30时，再对 学生 属性进行测试，若学生属性取值 是 时，该分枝的叶子结点表示购买计算机。从这里，我们清楚的看到，决策树的叶子节点是最终的结论，我们叫决策分类，比如最终是 买 还是 不买 这个最后决定，而中间的节点，是对每一个属性的一次决策选择，比如 年龄属性、学生属性 等等。
[P5] 现在我们知道了什么是决策树，那接下来的问题是，怎么建立一个决策树呢？建立一棵决策树，需要解决的问题主要有：第一，如何选择测试属性？测试属性的选择顺序影响决策树的结构甚至决策树的准确率，测试属性同时也构造了决策树的中间节点。第二，如果构造叶子节点。有了中间节点，叶子节点又是怎么来的呢？我们把停止划分的节点，就称为叶子节点，也就是中间节点，不再往下细分了，那它就是一个叶子节点。从根结点测试属性开始，每个内部结点测试属性都把样本空间划分为若干个子区域，一般当某个子区域的样本同类时，就停止划分样本，有时也通过阈值提前停止划分样本。
[P6] 有了前面的概念，接下来我们就具体看 ID3 算法是如何建立一个决策树的。ID3算法是 J.R.Quinlan 于1979年提出，并在1983年和1986年对其进行了总结和简化，使其成为典型的决策树学习算法。ID3算法主要是给出了通过信息增益的方式来选择测试属性。
[P7] 从信息论角度看，通过描述属性可以减少类别属性的不确定性。假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某蔬菜分类。在不给任何描述时，该蔬菜可能是蕃茄、茄子、黄瓜三种之一，不确定性大。在给出该蔬菜是“长的”形状描述时，该蔬菜可能是茄子、黄瓜两种之一，不确定性减小。在给出该蔬菜是“紫的”颜色描述时，该蔬菜只可能是茄子了，不确定性为零。
[P8] 这里是 ID3 算法的具体描述，输入为训练数据集S，描述属性集合A和类别属性C。输出为一个完整的决策树。
[P9] 这里是算法的具体代码实现，过程稍微有点复杂，大家可以课后再仔细查看。
[P10] 这是一个具体的例子，表中给出了训练数据集，前四列分别代表四个属性，属于内部节点，最后一列标红的是决策树的叶子节点。
[P11] 我们先构建第一个根节点，分别计算4个属性的增益值，如课件中计算的结果，年龄属性的增益最大。所以，我们选择年龄属性作为根节点。
[P12] 确定了根节点之后，我们再对剩下的三个属性计算增益值。注意，在考虑到年龄小于等于30这个分支上，计算其他属性的增益，如课件中的计算结果，学生属性的增益最大，所以我们把学生属性作为决策树的下一个节点。
[P13] 好，这里是添加了学生节点的决策树的图例。再次注意，这是在年龄小于等于30这个分支上。
[P14] 在学生节点上，继续往下计算，我们发现最终的结果 是否购买计算机 不管是哪个属性如何取值，最终结论都是一样的，这说明最终分类已经相同，无需再分，所以学生节点直接就可以生成后续两个叶子节点，不再需要生成额外的内部节点了。
[P15] 接下来，回到根节点，我们再次考虑 31到40岁 这个分支，经过计算，我们发现，不论属性如何取值，最终的分类结果都是一样的，所以这个分支直接就可以生成叶子节点，不需要额外的内部节点了。
[P16] 根节点还剩下一个分支就是年龄大于41岁这条。同样是对剩下的属性计算增益值，我们得到 信誉属性 的增益最大，于是下一个内部节点就用 信誉属性。
[P17] 这是把信誉节点加上之后的决策树的图。
[P18] 对信誉节点，继续计算剩余属性的增益以及对应的结果，我们发现，结果已经是同类了，所以信誉节点无需再分，直接就可以生成叶子节点了。
[P19] 这里展示了最终的决策树，可以看到，并不是所有的属性一定会生成为内部节点的，我们需要根据实际的情况，看结果是否同类，来决定是否需要进一步细分。
[P20] C4.5算法是 Quinlan 在1993年针对 ID3 算法存在的一些缺点提出的，它是 ID3 算法的后继，同时也成为诸多决策树算法的基础。C4.5 算法和 ID3 算法相比，改进的主要方面如下
1. C4.5 用信息增益率来选择属性，提高了衡量属性划分数据的广度和均匀性 2. C4.5 加进了对连续型属性、属性值空缺情况的处理 3. C4.5 对树的剪枝也有了较成熟的方法 。 C4.5 算法的提出，就是为了在 ID3 算法的基础上，避免算法倾向于优先选择取值更多的离散特征。C4.5 算法用来选择特征的主要指标是信息增益率，而不是信息增益。
[P21] 对于训练数据集S，若描述属性 Ak 的 v 的取值将训练数据集 S 划分为 v 个子集，每个子集的元组个数为nj，若相应的信息增益比率定义为课件上的公式。注意，我们这里用的是 信息增益率，而不是信息增益
[P22] 接下来是具体的代码算法，我们输入为 训练数据集S，描述属性集合A和类别属性C 。输出为以 Node 为根节点的 决策树。
[P23] 好，这里是具体的代码实现，代码我们就不细讲，大家可以课后在仔细看这里的实现代码。
[P24] 对于连续性属性的处理，C4.5 是这样操作的。1. 将训练数据集S中样本按连续描述属性A的值进行递增排序，一般采用快速排序法。假设S中属性A有m个不同的取值，则排好序的取值序列为 a1 到 Am 2. 按该顺序逐一将两个相邻值的平均值a'作为分割点，分割点将S划分为两个子集，分别对应属性A小于a'和大于a'的两个子集。这样共有m-1个分割点 3. 分别计算每个分割点的信息增益比率，选择具有最大信息增益比率的分割点 4. 按照上述方法求出当前候选属性集中所有属性的信息增益比率，找出其中信息增益比率最高的属性作为测试属性
[P25] 对缺失数据的处理：假设t是训练样本集S中的一个元组，但其描述属性A的值A(t)是未知的。采用的策略是为属性A的每个可能值赋予一个概率。
[P26] 后剪枝方法: 比较两个值，如果剪去Node结点的子树导致较小的代价复杂度，则剪去该子树；否则保留该子树。一般最小化代价复杂度的最小决策树是首选
[P27] 这里总结一下，我们这章介绍了什么是决策树，并且给大家介绍了生成决策树的两种算法，分别是 ID3算法 和 C4.5 算法。决策树是根据属性，将多次决策的结果汇总成对当前问题的最终决策。这种过程的一种最自然的表达方式就是决策树。ID3 算法通过计算不同的属性产生的增益值，来决定用那个属性作为决策树内部节点进一步细分，一旦分类相同的时候，就说明到了叶子节点无需再分了。C4.5 算法是对 ID3 算法的改进，采用信息增益比率作为比较属性的依据。