Machine-learning-DecisionTree

前言

决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶节点表示类别。从顶部根节点开始，所有样本聚在一起，经过根节点的划分，样本被分到不同的子结点中，在根据子结点的特征进一步划分，直至所有样本都被归到某一个类别（即叶结点）中。
————《百面机器学习》
决策树作为最基础、最常见的有监督学习模型，常被用于分类问题和回归问题，将决策树应用集成学习思想可以得到随机森林、梯度提升决策树等模型。
决策树的生成包含了特征选择、树的构造、树的剪枝三个过程
从若干不同的决策树中选取最优的决策树是一个NP完全问题(Non-deterministic Polynomial,即无法在多项式时间内完成)

Questions

决策树有哪些常用的启发函数？
如何对决策树进行剪枝？

常用的决策树算法及其启发函数

ID3(最大信息增益)

对于样本集合D,类别数为K,数据集D的经验熵表示为

其中$C_k$是样本集合D中属于第k类的样本子集，$|C_k|$表示该子集的元素个数，$|D|$表示样本集合的元素个数。
熵度量了事物的不确定性，越不确定的事物，它的熵就越大。
举例，比如D有2个可能的取值，而这两个取值各为1/2时D的熵最大，此时D具有最大的不确定性。如果一个值概率大于1/2，另一个值概率小于1/2，则不确定性减少。
然后计算某个特征A对于数据集D的经验条件熵$H(D|A)$为

样例：

由上图的样例可知，写代码的信息增益最大，所有样本根据此特征，可以直接被分到叶节点中，完成决策树增长。

C4.5最大信息增益比

特征A对于数据集D的信息增益比定义为

其中

CART 最小基尼指数(Gini)

Gini描述的是数据的纯度，与信息熵含义类似

CART在每一次迭代中遍历所有特征属性及其取值，选择基尼指数最小的特征属性取值及其对应的切分点进行分类，分为两类（该取值为切分点，如上例的工资特征，以中等为切分点，高和低为一类，中等为另一类）但与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树
特征A的Gini指数定义为

ID3,C4.5以及CART之间的差异

首先ID3是采用信息增益作为评价标准，除了主要特征外，会倾向于取值较多的特征，因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大，若分类特征过多，则ID3分类的泛化能力是非常弱的。
C4.5是在ID3基础上进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。
其次，从 大专栏 Machine-learning-DecisionTree样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART,由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。
从应用角度，ID3和C4.5只能用于分类任务，而CART(Classification and Regression Tree, 分类回归树)不仅可以用于分类，也可以用于回归任务（回归树使用最小平方误差准则）。
从实现细节、优化过程等角度，ID3对样本缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，最后形成一棵二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

参考：
https://www.cnblogs.com/pinard/p/6050306.html

如何对决策树进行剪枝

一棵完全生长的决策树会面临一个很严重的问题，即过拟合，若特征数量过多，如DNA特征，完全生长的决策树会面临所对应的每个叶结点中只会包含一个样本，这就导致决策树是过拟合的。剪枝操作可以提升模型泛化能力。
决策树的剪枝通常有两种方法：预剪枝（pre-pruning）和后剪枝(post-pruning)

预剪枝

预剪枝，即在生成决策树的过程中提前停止树的增长。
预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树，此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法。
（1）当树到达一定深度的时候，停止树的生长。
（2）当到达当前结点的样本数量小于某个阈值，停止树的生长。
（3）计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。
预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题，但如何准确地估计何时停止树的生长（即上述方法中的深度或阈值），需要经验积累。
预剪枝存在局限性，有欠拟合的风险，针对不同的测试集，准确率会存在波动。

后剪枝

后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。相对于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树。
常见的后剪枝方法包括错误率降低剪枝（Reduced Error Pruning, REP）、悲观剪枝（Pessimistic Error Pruning, PEP）、代价复杂度剪枝（Cost Complexity Pruning, CCP）、最小误差剪枝（Minimum Error Pruning, MEP）、CVP（Critical Value Pruning）、OPP（Optimal Pruning）等方法
代价复杂剪枝（CCP）主要包含以下两个步骤。
1）从完整决策树$T_0$开始，生成一个子树序列${T_0,T_1,T_2,…,T_n}$,其中$T_{i+1}$由$T_i$生成，$T_n$为树的根节点。
2）在子树序列中，根据真实误差选择最佳的决策树。
从$T_0$开始，裁剪Ti中关于训练数据集合误差增加最小的分支以得
到$T_{i+1}$。具体地，当一棵树T在结点t处剪枝时，它的误差增加可以用$R(t)−R(T_t)$表
示，其中$R(t)$表示进行剪枝之后的该结点误差，$R(T_t)$表示未进行剪枝时子树Tt的误
差。考虑到树的复杂性因素，我们用$|L(T_t)|$表示子树$T_t$的叶子结点个数，则树在结点t处剪枝后的误差增加率为

在得到$T_i$后，我们每步选择$alpha$最小的结点进行相应剪枝。

巴特西