决策树这一段在刚开始看的时候实际是比较吃力的，倒不是因为难以理解，主要是决策树整个过程的东西还是比较多的。
决策树的介绍 id3决策树的理解 我个人重点关注的是它的决策过程，当然首先应该清楚决策的目的是什么，那么在这之前要知道决策树是什么。决策树是什么？资料和书籍都说它是一种模型，符合人类思维的模型。既然它是模型，那么根据前面几节可知，模型的目的都是用于预测用的。以西瓜为例的话，它也是用来在不敲开西瓜的前提下预测这个瓜是好瓜还是坏瓜的，同时跟其他模型一样它也有训练阶段和预测阶段。
下面重点介绍ID3决策树过程。
以西瓜为例，首先是训练集：
编号色泽根蒂敲声纹理脐部触感好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否10青绿硬挺清脆清晰平坦软粘否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否首先根据总的数据集计算信息熵 纯度：我们希望节点所包含的样本尽可能属于同一类别，即节点纯度越来越高。 信息熵：用于度量样本集合的纯度，信息熵的值越小，则该集合的纯度越高。对于它的定义是这样的，假定当前样本集合D中第k类样本所占比例为pk(k=1,2,…,|y|)，则D的信息熵定义为： E n t ( D ) = ∑ k = 1 y p k l o g 2 p k Ent(D) = \sum_{k = 1} ^ y p_k log_2 p_k Ent(D)=k=1∑ypklog2pk 那么上面西瓜的数据集，y = 2，因为只需要分成是和否两类。在决策树开始学习的时候，根节点包含D中所有的样例，其中正例是8/17，反例是9/17，根据上面的公式，根节点的信息熵为： Ent(D) = -( (8/17) * log2(8/17) + (9/17) * log2(9/17) ) = 0.988
找到最大信息增益的属性作为根节点的属性 要找到（色泽，根蒂，敲声，纹理，脐部，触感）几个属性中最大信息增益的那一个，就需要把所有属性的信息增益算出来，再比较大小。 比如色泽，它有三个可能的取值（青绿，乌黑，浅白），然后在上面的17个西瓜数据集中把青绿色的西瓜挑出来作为D1 = {1,4,6,10,13,17}，把乌黑的西瓜挑出来作为D2 = {2,3,7,8,9,15}，最后剩下的就是浅白色的西瓜D3 = {5,11,12,14,16}。接下来，根据上面信息熵的公式把这三个集合的信息熵算出来。步骤跟上面一样，y依然为2，因为只有是和否两类，然后分别计算D1，D2和D3的正反例占比，再带入上面Ent(D)公式，可得： Ent(D1) = -( (3/6) * log2(3/6) + (3/6) * log2(3/6) ) = 1 Ent(D2) = -( (4/6) * log2(4/6) + (2/6) * log2(2/6) ) = 0.918 Ent(D3) = -( (1/5) * log2(1/5) + (4/5) * log2(4/5) ) = 0.722 这里也可以看到为什么我们第一步要计算信息熵，因为第二步计算信息增益的时候会用到。现在三个集合的信息熵有了，接下来就计算色泽这个属性的信息增益，为什么这里要计算信息增益？简单理解因为信息增益越大，则说明使用这个属性越适合来作为根节点。那么信息增益的公式和计算如下： G a i n ( D ， 色 泽 ) = E n t ( D ) − ∑ v = 1 3 D v D E n t ( D v ) Gain(D，色泽) = Ent(D) - \sum_{v = 1} ^ 3 \frac{D^v}{D}Ent(D^v) Gain(D，色泽)=Ent(D)−v=1∑3DDvEnt(Dv) 即0.988 - ((6/17)1 + (6/17) 0.918 + (5/17)*0.722) = 0.109 类似的我们可以计算出其他属性的信息增益： Gain(D，根蒂) = 0.143； Gain(D，敲声) = 0.141； Gain(D，纹理) = 0.381； Gain(D，脐部) = 0.289； Gain(D，触感) = 0.006。 显然“纹理”这个属性的信息增益最大，于是它就被选为划分属性。
划分 上面划分属性被选出来了，那么这一步就是进行划分了，在决策树上，这一步就是“分叉”这个动作。 因为纹理的属性值有三个（清晰，稍糊，模糊），那么第二行就被分为这三个节点。
递归1-3 以第二行第一个节点为例，参照第三步，这个节点是通过“纹理”属性划分，与第一步相比，第一步根节点的集合是总的西瓜集合，而这个节点的集合是{1,2,3,4,5,6,8,10,15}即纹理清晰的西瓜。以它为基础，要找到（色泽，根蒂，敲声，脐部，触感）几个属性中最大信息增益的那一个，“纹理”属性因为已经被选过因此这里不参与计算。还是和第二步一样，要挨着计算除了“纹理”的所有属性的增益，因为依据的集合不同，因此各个属性的增益肯定也会和根节点的计算结果不一样，再寻找最大值作为划分属性。
叶子结点 什么时候证明当前节点是叶子节点，递归结束？ 1，当前节点依据的集合全都属于一种分类，如上一步中，纹理属性为“模糊”的集合，其标签全都是否。那么它就是叶子节点，这个分支也就到此结束。 2，当前节点的依据的集合为空，换句话说，如色泽为浅白的西瓜在数据集中没有。 3，属性集为空，相当于决策树也有最大深度，最大深度等于属性的个数，上面西瓜就有6个属性，因此深度最多也就到6，当树延伸到了第六行，那么属性的个数已经在前面的递归过程中递减到了0。
总结下来，决策树过程的实质，其实就是在递归过程中，属性的个数在依次递减，划分依照的集合各不相同，从而把各个叶子结点都计算出来，形成一个分类模型。预测的阶段就是把预测数据从根节点开始沿着各个分支判断一直往下走，落到了哪一个叶子节点就依据哪一个叶子节点的标记得出结果。
增益率：它的用途与上面id3决策树算法中信息增益的作用一样，都是用来选择最优的划分属性的。因为id3对可取值数目较多的属性有偏好，所以增益率可以用来减少偏好带来的不利影响。C4.5决策树算法就使用了它。增益率虽然有上面的优点，但也有缺点，就是对可取值数目较少的属性有偏好，和信息增益形成对照。所以C4.5决策树算法是先找出信息增益高于平均水平的属性，再从中选择增益率最高的。 基尼指数：与增益率的用途一样，它可以用于度量集合的纯度，该指数值越小，纯度就越高，那么，在选择最优划分属性时需要选择该指数最小的属性。
剪枝处理：因为决策树学习有时会存在过拟合的现象，那么就需要主动去掉一些分支来降低它的风险。其基本策略包括“预剪枝”和“后剪枝”。 预剪枝：在决策树的每个节点划分属性前，先进行评估当前节点的划分能否带来泛化性能的提升，不能则停止划分。 后剪枝：先生成了一颗决策树，然后自底向上对非叶子节点进行考察，若将该节点对应的子树替换为叶子节点能否带来泛化性能的提升，如果可以则将该子树替换为叶子节点。 预剪枝和后剪枝具体过程 总结，预剪枝会禁止一个节点的划分而降低过拟合的风险，而当前节点的子节点及其后续节点又有可能会显著提升泛化性能，因此它存在欠拟合的风险。但后剪枝就好很多，因为它的本质只是叶子结点往回缩，并不会影响到整条分支或其他分支，与预剪枝相比保留了更多的分支，一般情况下，它的欠拟合风险更小，泛化性能更好。而后剪枝由于要自底向上的注意考察，因此训练时间的开销比预剪枝更大。
连续与缺失值 前面可以看到西瓜的根蒂属性的取值包括稍蜷，蜷缩，硬挺三个离散的值，但如果像含糖率这样的属性取值肯定是0到1之间的任意值，对于这样的连续值在决策树中如何考量？C4.5算法采用的二分法对连续属性值进行决策，原理就是在集合中选取划分点，然后像处理离散属性一样选取最优的花粉店进行样本集合的划分。需注意，前面用过一次连续值划分，后续依然可以用，不像前面说的西瓜的“纹理”属性已经被选过划分属性后续就不能再使用。 缺失值的处理 多变量决策树估计后续会细讲。
