机器学习技法第九课——Decision Tree

发表于   |   分类于

此文是本人学习林轩田老师教授的机器学习技法第九课——Decision Tree——的笔记。这节课主要讲解 CART (Classification And Regression Tree) 算法，属于决策树。

参考

决策树的基本思想

就举课上的例子好了。要处理的问题是：我回家后是否看学习视频呢？处理这个问题，首先可能想到，我是什么时候回家的呢？那么这个问题分成2种情况。如果回家很早，那么，我是不是有什么约会呢？有约会就不看了，没约会就看。如果回家晚，那么，学习的截止时间是不是快到了呢？快截止了就勉强看下吧，否则就算了。

决策树模型与上述处理问题的过程类似。决策树顾名思义，是一棵树。树的节点是决策器，决策器输入问题，稍做判断，又将问题交给某个合适的下层决策器（下层节点），最终最下层的决策器输出这个问题的处理结果。所以，在处理问题时，问题从决策树的根节点进入，经过一层层的决策，最终输出决策结果。

CART 是决策树中的一种，它是一棵二叉树，可处理分类或回归问题。

CART 训练步骤

CART 模型训练主要分为 2 步，一、生成完全树，二、剪枝。

完全树 是能够将所有训练数据都完全无误地预测的决策树，即在训练集上的误差为 0。实际上，训练数据往往有误差，而完全树做到对训练数据判断的无误差，导致在实际预测时误差较大，有很大的复杂度方面的代价。所以，需要做正则化方面的工作，CART 采用的就是 剪枝 。顾名思义，剪枝会剪去完全树的部分树枝，减小模型的复杂度。

生成完全树

完全树的训练可用递归方式。完全树的节点是“决策器”，实际上是分类器（或回归算法）。决策器将数据大致分类（或用回归预测做大致分类），然后分别交给下层的决策器。

1
2
3
4
5
6
7
8
9
function trainCART：
  - 输入：训练数据集 D
  - 输出：CART 二叉树 Tree
学习决策器 decisionNode，将 D 分为 Dl, Dr;
if Dl 可以再分：
  call trainCART 处理 Dl 得到 treeL;
同上处理 Dr 得到 treeR;
decisionNode 作为根节点，合并 treeL, treeR, 得到二叉树 tree;
return tree;
递归训练终止条件

整个递归的终止条件是“数据是否可再分”，在两种条件下不再分。如果训练数据都相同，即 $\mathbf{x}_n$ 都相同，无法分割；如果训练数据分类都相同，即 $y_n$ 都相同，不用分割。

决策器选择指标与不纯度

学习决策器时，CART 的每个决策器被称为 决策树桩（decision stump） ，每个决策树桩对输入数据进行切割。对于多个候选决策器，CART 的选择标准为：

$$ \underset{decision\; stumps\; hi(\mathbf{x})}{argmin} \frac{|D{i,l}|}{|D|} \cdot impurity(D{i,l}) + \frac{|D{i,r}|}{|D|} \cdot impurity(D_{i,r}) $$

其中，$hi(\mathbf{x})$ 指第 $i$ 个决策树桩模型， $D$ 指训练数据， $D{i,l},\; D_{i,r}$ 分别是 $hi(\mathbf{x})$ 将 $D$ 划分的数据， $\frac{|D{i,l}|}{|D|}$ 计算了 $D_{i,l}$ 数据量在 $D$ 中的占比， impurity 是计算划分数据的 不纯度 函数。一个决策树桩划分的数据的不纯度越小越好。

不纯度指数据中类别的不相同的程度。比如，”被判定为鸭群，有 7 只鸭和 3 只鸡”比“被判定为鸡群，有 9 只鸡和 1 只鸭”更“不纯”，前者不纯度更高。

CART 对于回归与分类的不纯度公式稍有区别。

回归不纯度公式

$$ impurity(D) = \frac{1}{N} \sum_{n=1}^N (y_n - \overline{y})^2 $$

分类不纯度——Gini 指数

$$ impurity(D) = 1-\sum{k=1}^K(\frac{\sum{n=1}^N [y_n=k]}{N})^2 $$

其中， $K$ 是分类的种数，对于二分类， $K=2$； $k$ 表示分类编号； $[y_n=k]$ 是一个布尔判断，如果第 $n$ 个数据是第 $k$ 类，得 1，否则为 0。

剪枝（Pruning）

CART 采用 后剪枝(Post-Pruning)，即在已生成的完全树上进行剪枝。大致流程：

  • 分别剪去一个叶子节点，得到多棵决策树
  • 计算每棵决策树剪枝“代价”，保留代价最小的决策树
  • 重复以上流程，直至剪枝代价高于不剪枝的代价

代价公式可表示为：

$$ cost(G) = E_{in}(G) + \lambda\cdot NumberOfLeaves(G) $$

其中， $G$ 表示一个决策树模型， $NumberOfLeaves(G)$ 即决策树的树叶数目，树叶数目越少，模型越复杂，（回归）越容易过拟合， $\lambda$ 是指定的正则化参数。

决策树桩（decision stump）

如前撰述，决策树桩是深度为一的决策树，典型的弱分类器，也可用于回归，常被用作集成学习中的基础模型。它可以将输入数据按照某种标准分为两部分。

决策树桩需要选择一个恰当的特征维度 $i$（ 输入向量 $\mathbf{x}$ 的一个维度）、 阈值 $\theta$ 与方向 $s={-1,1}$ 进行切割。它的分类器可表示为：

$$h_{s,i,\theta}(\mathbf{x}) = s \cdot sign(x_i - \theta)$$

对于训练数据 $D$ ，如何训练出一个最佳的决策树桩？根据决策树的训练方法，最原始的方法应该是尝试每一个可选的 $i, \theta, s$ ，计算不纯度，选择不纯度最低的一组参数。