（LXTML笔记）Decision Tree

决策树也是有集成模型的形式，如图所示

如果以每一条路径为条件qt$q_t$，叶子为最后的分类函数gt$g_t$（有时候是常数）的话，那么整棵树可以表示为G(x)=∑Tt=1qt⋅gt$G(x)=\sum _{t=1}^T{q}_t\cdot g_t$，这是条件型集成模型的形式。更一般地，我们常常写成递归的形式，即

其中b(x)$b(x)$为分支方法，C$C$为该节点的分支数量，Gc$G_c$是c$c$分支对应的子树，那么要进行learning的话，涉及到下面几点

1. 如何学习（定义）分支b(x)$b(x)$;
2. 根据b(x)$b(x)$将主句分类；
3. 递归建立子树Gc$G_c$.

CART

CART即 classification and regression tree，这是一种特殊的决策树，它的分支是2，是一颗二叉树，且底部叶子的分类函数gt$g_t$返回的是一个最优的常数（如0/1 error时就返回{yn}$\{y_n\}$中最多的那个，squared error的话就返回平均值，这些后面会讲到）。

我们如上图所示定义分支函数b(x)$b(x)$，其中这里的纯度impurity很好理解，实际就是一种误差的表达，比如

这样的情况下，树的生长在两种情况下回停止，

1. 所有的yn$y_n$都相同，此时纯度为0，所以此时gt=yn$g_t=y_n$
2. 所有的xn$x_n$都相同，所有的资料特征都相同，此时根本下不了刀

我们称这样自动停止的树称为full-grown tree，显然根据上面的算法，这棵树迟早是完全体树的。

而对于完全体树，其Ein=0$E_{in}=0$，由之前的课程我们知道，如果一个模型的Ein=0$E_{in}=0$，那么肯定是付出很大的代价的，这里即几乎算完了每一种情况，所以我们应该对模型增加一些限制（正则化），这里限制的是叶子的数量。

生成fully-grown tree G(0)$G^{(0)}$之后，我们定义最优目标

G(1)$G^{(1)}$的意思是遍历所有的叶子，试着摘掉其中一个叶子（即合并二叉树节点的两个分支），看什么时候argmin最小，接着再合并第二次得到G(2)$G^{(2)}$，如此下去，直到满足我们要求的叶子数量为止。