本文用于记录决策树相关的启发函数及剪枝技巧，主要用于自我温习回顾基础。
基本目录如下：
启发函数的类型
1.1 ID3 - 最大信息增益
1.2 C4.5 - 最大信息增益比
1.3 CART - 最大基尼指数
1.4 总结剪枝处理
2.1 预剪枝
2.2 后剪枝
------------------第一菇 - 启发函数的类型------------------
1.1 信息增益
决策树是一种十分常见的传统机器学习方法，而其最核心的部分即为如何选择最优划分属性。我们最后的期望肯定是其最后叶结点所包含的样本尽可能属于同一类别，即最后的“纯度”越来越高。而“信息熵（information entropy）”就是度量样本集合的一种指标。
假定当前样本集合D中第k类样本所占的比例为，则D的信息熵定义为，
其中若，则其对应的
，
然后计算某个特征A对于数据集D的经验条件熵为，
其中，表示D中特征A取第i个值的样本子集，
表示
中属于第
类的样本子集。
于是用A特征作为划分结点的信息增益即可以计算为，
公式看着很绕，但其实理解起来真的很简单。注意上式括号外的部分，其实计算的就是用特征A划分的数据集的占比，该值的作用其实就是加权求平均（指用A划分的每一个子集的信息熵）。而括号内计算的就是每一个小集合的信息熵。因此，该式子其实就想计算，当用A作为特征值，划分数据集以后，数据整体的信息熵是多少～而信息增益就是数据的“混乱”程度下降了多少（即俩者差值）！而每选取一个特征值，都选择能带来最大信息增益的特征值的决策树的启发函数，就是著名的ID3决策树学习算法。初学者可以找一个例子，手算走一遍流程，加深理解（似乎这应该是决策树课后必做习题😄）～
1.2 最大信息增益比
上面的最大信息增益算法看似完美，但其实还有很多不足的情况。举一个极端的例子，如果我们把样本的ID值作为特征值进行划分，则显然每一个样本都只会属于一个叶结点（类别），每一个分支结点的纯度都为0，显然是信息增益最大的一个特征值！但，实际上，没有人会直接拿这种特征进行类别划分，主要原因就是，完全过拟合了，不具有泛化能力，基本就是个废模型～而这也是信息增益的一个弊端，即他会对可取值数目较多的属性有所偏好，为减少这种偏好带来的不利影响，就有了C4.5决策树算法，即利用“增益率”来选择最优特征值。
增益率的定义如下，
其中，
该式子可以理解为数据集D关于A的取值熵，大家显然可以发现，该增益率的算法会对取值数目较少的属性有所偏好哈哈～因此，C4.5算法并不是直接选择增益率最大的特征值，而是与最大信息增益相结合的一种启发式算法。即从信息增益大于一定阈值的特征值里面，再去挑选一个信息增益率最高的～
1.3 基尼指数
基尼（Gini）也是描述数据的纯度的另一种表示，与信息熵的含义类似，其可以定义为，
其中，指的是样本集合
中属于第
类的样本子集。简单来说，
反映了从数据集D中随机抽取俩个样本，其类别标记不一致的概率。因此，其值越小，则表示数据集D的纯度越高。跟上面的熵增益一样，当选择特征值A时，其基尼指数定义为，
因此，每一次选择特征值划分的时候，我们都选基尼指数最小的那一个即可～值得注意的是，CART（Classification and Regression Tree）本身是一颗二叉树，采用的二元切割法，每一步将数据按照特征A的值切成两份，分别进入左右子树，因此，其天然也适用于连续型变量和回归任务。
1.4 总结
上面介绍的三种方法，在实际的应用场景中可以说各有千秋～上面也提到了，C4.5是对ID3的一个很好的补充，避免其过拟合，能提升泛化能力～
另外，从样本类型的角度看，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量～C4.5就是将连续型变量转换为多个取值区间的离散型变量～
从应用角度来说，ID3和C4.5都只能用于分类任务（信息熵得有类别的概念才能计算把），而CART可以应用于回归任务（取特征值的时候，用最小平方误差准则）。
从定义上来理解，其实都很简单，但具体到实战中的时候，需要仔细琢磨选型，针对不同场景灵活变通～
------------------第二菇 - 剪枝技巧------------------
对于决策树而言，剪枝操作其实就是为了防止过拟合的，一般我们都会通过一些主动的剪枝手段来维持模型的鲁棒性～
2.1 预剪枝
西瓜书上的定义：预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。
预剪枝的思想比较直接暴力，一般比较依赖于经验判断（存在一定欠拟合的风险），其主要的几个方法包括，
1）当树达到一定深度的时候，停止树的生长。
2）当某一结点的样本数量小于一定阈值的时候，停止树的增长。
3）计算每一次分裂的准确率的提升，当小于一定阈值的时候，停止树的增长。
2.2 后剪枝
西瓜书上的定义：后剪枝是指从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
相比于预剪枝，后剪枝的方法通常可以得到泛化能力更强的决策树（毕竟其事先已经先生成了一颗完全生长的决策树，避免了一些欠拟合的风险，代价就是时间开销更大）。因此具有更高的准确性，所以大量的研究都集中在这一块，想一口气全部讲完也是不可能的，比较著名的有错误率降低剪枝（REP），悲观剪枝（PEP），代价复杂度剪枝（CCP）等，其方法都各有利弊，优化的角度也各不相同。有兴趣的同学可以多多深入了解一些～这里就不具体展开了～
至此，涉及决策树中的一些核心概念已经全部回顾完成了～希望大家读完本文后对决策树的一些概念会有一个全新的认识。有说的不对的地方也请大家指出，多多交流，大家一起进步～😁
