机器学习树模型——从决策树开始

介绍

决策树（Decision Tree）是一类基本的分类和回归方法，它的生成过程可以简单的概括为if-then——即满足某个条件，进行下一步，直到能通过这样的方式递归区分所有的样本。同时决策树又可以作为集成模型的基模型。比如决策树通过Bagging可以集成为随机森林（Random Forest），GBDT选择CART作为基分类器等等。
定义：决策树模型是一种描述对实例进行分类的树形结构，由结点和有向边组成。
如下图所示，圆形代表内部结点（internal node），表示一个特征或者属性；方形代表叶子结点（leaf node），表示一个类。

特征选择

决策树可以看成是一个if-then规则的集合：由决策树的根节点到叶节点的每一条路径构成一个规则，路径上的内部结点的特征对应着规则的条件，而叶节点对应着规则的结论。并且每个规则的条件是互斥且完备的。如何选择内部结点的特征就成为了核心问题，一个好的特征选择需要满足以下准则：每次找到能使当前子集有更好的分类的特征。

信息增益——ID3

熵（entropy）表示随机变量不确定性的度量，记为：
$H(X) = -\sum_{i=1}^{n}p_{i}log{p_{i}}$H(X)=−i=1∑n​pi​logpi​
其中，$p_{i}$pi​为变量X取值的概率，n表示变量X总共可能的取值个数。显然，熵之和变量取值的概率相关，与取值大小无关。 熵越大，变量取值的不确定性越大。
条件熵H（Y|X）表示在已知随机变量X的条件下随机变量Y的不确定性，定义为：
$H(Y|X) = \sum_{i=1}^{n}p_{i}H(Y|X=x_{i})$H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)
$p_{i} = P(X=x_{i})$pi​=P(X=xi​)表示X取值的概率。当熵和条件熵中的概率由极大似然估计得到，那么所求的熵和条件熵分别称之为经验熵（Empirical entropy）和经验条件熵(Empirical conditional entropy)。 信息增益表示 得知X特征的信息后使Y的不确定性减少的程度，记为：
$g(D,A) = H(D) - H(D|A)$g(D,A)=H(D)−H(D∣A)
计算步骤如下：
第一步：计算经验熵H(D)：
$H(D) = -\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log_{2}{\frac{|C_{k}|}{|D|}}$H(D)=−k=1∑K​∣D∣∣Ck​∣​log2​∣D∣∣Ck​∣​
其中K表示类别数量，D表示的是训练集，$C_{k}$Ck​表示的类别为k的样本集合。
第二步：计算经验条件熵H(D|A):
$H(D|A) = -\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log_{2}{\frac{|D_{ik}|}{|D_{i}|}}$H(D∣A)=−i=1∑n​∣D∣∣Di​∣​k=1∑K​∣Di​∣∣Dik​∣​log2​∣Di​∣∣Dik​∣​
其中$n$n表示特征A的取值个数，$D_{i}$Di​表示样本的属性A取值i的集合，$D_{ik}$Dik​表示子集$D_{i}$Di​中属于类别$C_{k}$Ck​的集合。
第三步：计算信息增益:
$g(D,A) = H(D) - H(D|A)$g(D,A)=H(D)−H(D∣A)
然后比较那个属性的信息增益最大就选取该特征作为内部结点。
ID3算法就是选择信息增益作为特征选择的决策树分类算法，递归地构建决策树。具体如下：首先从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；然后对子结点递归地使用以上方法构建决策树，直到最后所有的特征的信息增益都很小（小于阈值）或没有特征选择为止。

信息增益比——C4.5

C4.5和ID3算法只在特征选择不相同，它将信息增益换成了信息增益比。信息增益比的计算公式如下：
$g_{R}(D,A) = \frac{g(D,A)}{H(D)}$gR​(D,A)=H(D)g(D,A)​

Gini指数——CART

分类回归树也是决策树的一种，可用于分类和回归（这里主要考虑分类树）。和ID3，C4.5不同，CART生成是二叉树，左边是判断条件为“是”的分支，右边去判断条件为“否”的分支。而且，CART不光包含树的生成，也包含树的剪枝，而且特征选择的方法也不一样，下面一一详细介绍。首先是Gini指数，计算如下：
$Gini(D) = \sum_{k=1}^{K}p_{k}\sum_{k\neq k^{\prime}}p_{k^{\prime}}= 1-\sum_{k=1}^{K}p_{k}^{2}$Gini(D)=k=1∑K​pk​k​=k′∑​pk′​=1−k=1∑K​pk2​
如果样本集合根据特征A是否取某一值$a$a被分割成两个集合$D_{1}$D1​ 和$D_{2}$D2​。因此在特征A的条件下，集合D的基尼指数定义为：
$Gini(D,A) = \frac{|D_{1}|}{|D|}Gini(D_{1})+ \frac{|D_{2}|}{|D|}Gini(D_{2})$Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)
我们计算了所有的$Gini(D,A)$Gini(D,A)之后，取Gini指数最小值的条件$a$a作为特征。Gini指数和熵的含义相似，都表示样本集合D的不确定性。有了特征选择，那么就可以按照ID3和C4.5的方法生成决策树。
生成了决策树之后，还需要对其进行剪枝（Pruning）。说到剪枝，决策树存在一个严重的问题，那就是过拟合。对训练数据拟合得太好了，可能就会导致泛化性能不够好，因此需要去掉一些分支来降低过拟合的风险。CART用到的剪枝策略是一种后剪枝，对于生成的树$T_{0}$T0​先减掉一个子树生成$T_{1}$T1​，再在$T_{1}$T1​上减掉一个子树，依次类推，最后得到一个只剩根节点的子树。然后再用这得到的n+1棵子树预测独立的验证数据集，谁的误差最小就选谁。那么问题来了，每次应该选择哪颗子树剪枝呢？，按照以下公式来求解：
$g(t) = \frac{C(t)-C(T_{t})}{|T_{t}|-1}$g(t)=∣Tt​∣−1C(t)−C(Tt​)​
其中$C(t)$C(t)为对训练数据的预测误差（Gini指数），$T_{t}$Tt​表示以t为根结点的树。上式表示的是剪枝后整体损失函数减少的程度，我们希望剪掉该子树，会使整体损失函数减小，因此我们调整的是$\alpha$α的值，至此我们认为找到了子节点t，也就是完成了剪枝得到子树$T_{1}$T1​。为了得到$T_{0}$T0​的所有子序列，直接递归下去，直到根节点即可。在这一过程中，不断地增加$\alpha$α的值，产生新的区间。之后就是用测试集去验证哪个子树的准确率最高，哪颗数就获胜。