1 min to read

决策树

Featured image

通过之前对线性回归和逻辑回归的学习，应该了解到 损失函数是研究一个算法的着手点，也是模型优化的指标；下面介绍决策树的损失函数，需要从信息熵说起

信息熵

熵是对不确定性的测量，一个随机变量X的信息熵定义为：H(X)=Σp(x)log p(x) 其中，x是X的一种可能结果；

决策树有很多种类型，常见的有ID3、C4.5、CART树，下面一一介绍

ID3

决策树构建的关键是选择合适的特征值作为树节点的分裂标准，那么应该如何选择呢？
对于ID3来说，是将信息增益作为分裂结果的衡量，信息增益就是分裂前的信息熵与分裂后的信息熵的差值，这个差值越大越好；分裂后的信息熵是计算分裂后的每一个集合的信息熵，然后按照样本比例加权求和（总体权重为1）
基于这个标准，ID3只能处理离散特征和分类问题；对于回归问题和连续特征，则可能需要通过一定的方式转化为分类问题和离散特征去处理。

树的构建过程就是遍历离散特征进行分类，然后寻找最优特征，循环进行下去，直到节点不能再分裂或者是满足预剪枝的条件（预剪枝在后面会提到）

ID3算法的缺点：

C4.5

c4.5是对ID3算法的改进，主要是解决ID3在特征选择上偏重于分类值比较多的特征；
c4.5与ID3的主要区别在于，特征选择的标准不同，C4.5的特征选择是根据信息增益率（信息增益比）作为标准，选择特征。 信息增益率是通过引入一个被称为分裂信息的惩罚项来惩罚取值较多的Feature，分裂信息用来衡量分裂的广度和均匀性，计算方式如下：

分裂信息计算公式
其中D表示分裂前的集合，Di表示分裂后的其中一个子集，A表示分裂的属性
信息增益率的计算公式如下：
信息增益率

其中，分子表示信息增益，分母表示属性A的分裂信息固有值，特征对应的取值类别越多，这个值越大；

C4.5虽然解决了ID3偏重于选择特征值较多的特征，但是也存在一些弊端，当Di的大小跟D比较接近时，分裂信息的值就会接近于0,这时候就会导致信息增益率较大。实际使用中的解决办法是，只对那些信息增益较大的分裂选择项（如增益高于平均增益的选择项），去计算信息增益率

另外，C4.5在具体实现上，解决了ID3不能使用连续特征的不足之处，解决方法是：

第三点改进，可以对缺失值进行处理，针对缺失值，可以根据其他样本赋予默认值，如：取平均值，取出现次数最多的值，或者是一些加权计算的方法

但是C4.5仍然只能解决分类问题，这是由于特征选择的标准决定的

C4.5在实际计算过程中并不是取信息增益率最大的特征分裂，为了防止偏好分裂数目较小的特征，是选取信息增益较大的分裂可能性，在这些分裂可能性里面再选取信息增益率最大的；

cart

CART树是一棵二叉树（id3和c4.5不是），是用的最多的一种树，既可以处理分类问题，也可以处理回归问题。

在处理分类问题和回归问题时，选择分裂的标准不同，处理分类问题时一般选择基尼系数作为分裂依据（主要是计算简单一些），在处理回归问题时一般选用均方差作为分裂依据。

基尼系数用来衡量样本的纯度，基尼系数越小，纯度越高；基尼系数的计算方式如下
基尼系数计算方式

剪枝

剪枝的目的主要是为了防止过拟合，通过对树节点的删减合并增加模型的泛化能力。常用的剪枝策略有两类，一类是预剪枝，另一类是后剪枝

预剪枝

预剪枝是在构建决策树过程中，通过某些限制条件及早的阻止某些节点的生成。
正常情况下都是在熵、基尼系数或者均方差无法进一步降低的条件下，不得不停止分裂，但这时候可能已经是过拟合状态了；
常用的预剪枝策略有：

预剪枝是常常使用，用来防止过拟合；但是也有一些缺陷，比如通过控制深度和叶节点的样本数，略带一些盲目，需要去调参，比较不容易选择出合适的值；而限制收益可能会造成比较大的损失，比如也许这次的分裂收益并不是很大，但是后面会获取到比较大的收益！

后剪枝

后剪枝是指在决策树生成完之后，再进行节点的删减合并！
从损失函数说起，决策树的损失函数日下：

决策树损失函数
其中C(T)表示原始损失，α|T| 表示惩罚项；Nt表示第t个叶子节点样本的数量，Ht表示第t个叶子的损失，|T|表示树的节点个数

后剪枝的操作一般是在测试集上进行，自底而上依次删除每个节点的子树，并将子树样本点合并到此节点，计算α值，使得删除前和删除后的损失一样；这样就会得到一系列的树，每棵树对应一个α值，然后将树按照α值，有小到大排序；取α值最小的那棵树；
对于α值，可以理解为α越大则说明需要加大惩罚才能使得合并子节点之后的树和合并之前的损失相等，也就是说这个合并的损失较大，需要更大的α去弥补这个损失。所以应该取α最小值对应的那棵树。