机器学习技法笔记 – Decision Tree(决策树)

Decision Tree Hypothesis

在上一章中,我们介绍了通过Re-weighted思想来差异化\(u^{(t)}_n\)(权重)训练出不同的\(g_t(x)\)然后做Aggregation的AdaBoost。

AdaBoost本质上是一种non-uniform的Bagging Aggregation方法。

在本章中,我们将介绍一种conditional的Bagging Aggregation方法,称之为Decision Tree(决策树)

首先,我们从下图在视觉上初步认识一下决策树:

上图是一个形象化的例子,通过树形图的方式描述了“要不要上课”这一条件决策流程。

其公式化的描述如下:

需要注意的是这是一种递归的描述,其中,\(G(x)\)是一颗生成树,是整颗决策树的入口,\(b(x)\)是判断是否要进入当前分支\(c\)的Branching Criteria Function,\(G_c(x)\)是子树的入口。

接下来,将介绍生成决策树的算法。

Decision Tree Algorithm

生成决策树具有很多著名的算法,在本文中我们介绍C&RT(Classification and Regression Tree),这个算法的主要思路如下:

即对于决策树函数,对于输入的数据集\(D\),如果递归至叶子节点,则输出叶子节点的\(g_t(x)\)对于数据集\(D\)中\((x_n, y_n)\)的值,否则,在当前数据集\(D\)上训练\(b(x)\),然后在将数据集\(D\)一分为二,递归调用决策树函数。

在C&RT中,如何训练\(b(x)\)是非常重要的话题。

其中,\(b(x)\)具有以下形式:

对于每一个\(b(x)\),最小化\(\sum^{2}_{c=1} \vert h(D_c) \vert · impurity(h(D_c))\),可以看出\(c=2\),即\(b(x)\)的输入是被分为两份的数据集\(D\),表现在数据结构上,即是二叉树,而\(impurity(h(D_c))\)是不纯度。

通常,对于回归问题,其\(impurity(h(D_c))\)通常有以下定义:

而对于分类问题,\(impurity(h(D_c))\)则有以下定义:

对于基础的Base Hypothesis,我们依然选择Decision Stump(决策桩),它具有以下形式:

通过最小化\(impurity(h(D_c))\),可以求出最佳的\(\theta\),接下来我们将给出完整的C&RT算法。

Decision Tree Heuristics in C&RT

一个完整的C&RT算法如下:

当\(impurity(h(D_c))=0\),或者\(D_c\)不可再分,则C&RT算法结束。

需要注意的是,C&RT算法生成的决策树如果没有任何的Regularization操作,放任子树生长,会使得\(E_{in}=0\),即会带来Overfitting,所以我们需要为C&RT算法加上Regularization项来避免Overfitting的发生,这个过程也称之为剪枝。

通常可以通过对叶子节点剪枝来做Regularization:

而Regularization项具有以下形式:

具体过程如下:

  • 首先通过C&RT生成决策树
  • 随机剪枝一个或多个叶子节点,重复多次,得到\(N\)个\(G(x)\)
  • 对所有\(G(x)\)在数据集\(D\)做Validation,选取\(E_{in}\)最小的\(G(x)\)

决策树不仅可以用在Numerical Features中,也可以用于Categorical Features:

对于数据集中不分数据的缺失,也可以通过训练多个\(b_n(x)\),来做最佳\(b(x)\)的近似。

Decision Tree in Action

下图是一个C&RT与AdaBoost算法的对比,通常情况下C&RT具有更高的效率:

最后对C&RT做一个总结:

C&RT具有诸多优点,例如对于人类易于解释,易于处理多分类问题,对于有缺失的数据集也可以应对,易于处理非线性分类或者预测问题。

以上是对Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Random Forest。