[原]【机器学习基础】决策树算法

在之前的两节博文 《混合和装袋》 和 《自适应提升》 中，我们已经有现成的一堆假设g在手中，我们还如何将这些g混合起来，得到更好的分类器。

混合方式可以分为三种情况：

1. 把g看做是同等地位，通过投票或者平均的方式将它们合起来，称为Bagging
2. g是不平等的，有好有坏，一个可行的做法是把g当成是特征的转换，然后丢进线性模型训练就可以了，这称为AdaBoost
3. 如果是不同的条件下，使用不同的g，那么我们仍然可以将g当做是特征转换，接下来使用一个非线性模型来得到最终的模型参数，这就是该文要介绍的决策树算法

决策树的表示方式可以有两种形式。

第一种是从路径的角度（Path View），将每个从根到叶子的路径作为一个假设g，通过不同的条件组合得到最后的G(X)。

第二种是从递归的角度（Recursive View），父树是由子树递归定义的tree=(root,sub-trees)。

1. 从数据中看看如何做分支（branching criteria）
2. 根据分支将数据分成几块
3. 根据不同的数据学习子树
4. 得到最终的决策树

分类回归树(CART,Classification And Regression Tree)算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。

CART根据不同的条件，对数据进行切分，到达叶子节点时，根据剩下的数据进行预测，输出一个常数。

CART算法中每个节点（看做是一个决策桩decision stump）对数据进行切分，如果分出来的数据的y都很接近（回归问题）或者都一样（分类问题），那么我们说这样的数据是“纯的”，这样用标量对数据进行预测可以得到比较小的误差。

我们通过上面的公式，来计算对于每一个节点的决策桩来说，分出来的两份数据的纯度是怎样的。该公式通过计算数据集Di（i=1 or 2）的纯度并根据数据集的数量对其进行加权，其加权的意义是 如果数据集的数量比较大的话，那个纯度对其比较重要，反之，就不那么重要。

CART通过分出的两部分数据综合起来的纯度对决策桩进行选择，选择“最纯”的分割方式作为当前的分支。

我们可以将分割出来的数据和回传的常数的误差作为评价纯度的方法，利用数据的y和回传的y_ba的均方误差来评价回归问题的纯度；利用0/1误差函数来评价分类问题的纯度。

如果是分类问题，我们还可以使用一个别的方法。通过基尼不纯度来度量分类问题的纯度问题。

下面是CART算法完整流程：

一棵完全长成的树的训练误差为0Ein(G)=0，这会有过拟合的危险，在每一个节点上的数据越来越少，导致拟合到这些节点的数据可能是过拟合的。

所以，我们需要一个正则化的机制，来控制模型复杂度，让模型不那么容易出现过拟合现象。

CART剪枝算法从完全生长的决策树的底端剪去一些子树，使决策树变简单，从而能够对未知数据有更准确的预测。

上图告诉我们使用叶子的数目作为正则项（regularizer），最终得到一个正则化的决策树。

关于剪枝的具体做法时：

• 首先得到完全长成的树作为G(0)；
• 然后试图摘掉一片叶子，将所有摘掉一片叶子后的树计算Ein，将最小的那棵摘掉一片叶子的数作为G(1)；
• 如此这般，得到摘掉两片叶子的最优树G(2)，这样不断剪枝，直到根结点，形成一个子树序列；
• 最终对这个子树序列使用argmin Ein(G)+λΩ(G)来得到最后的输出。

机器学习技法课程，林轩田，台湾大学