【Decision Tree】林轩田机器学习技法

首先沿着上节课的AdaBoost-Stump的思路，介绍了Decision Tree的路数：

AdaBoost和Decision Tree都是对弱分类器的组合：

1）AdaBoost是分类的时候，让所有的弱分类器同时发挥作用

2）Decision Tree是每次根据condition让某个弱分类器发挥作用

林强调了一点，Decision Tree很多套路都是前人的insights，觉得这用好就这样处理了，没有那么完备的理论保证。

从递回的角度，可以这样看Decision Tree:

Decision Tree = Σ分支条件.子树

根据如上的递回思路，可以写出Decision Tree的算法的大概思路：

有点儿像dfs的代码模板：

输入：N个样本点

终止条件：达到base hypothesis gt(x)

dfs步骤：

　　1）获得分支条件

　　2）根据分支条件，将数据切分成C份

　　3）由这C份数据生成C棵子树

　　4）将C棵子树 & 分支判断条件合在一起return

其中很关键的一个步骤就是如何划分输入样本D成C分，这里介绍一种C&RT的方法。

这个方法的特点是每次只产生2一个判断条件，将数据分成两份（即binary tree）

选择判断条件的准则是：经过判断条件的划分后数据更纯了。

这里的“纯”还做了一个处理，就是“加权纯”，如果样本量大的那一堆数据更纯，认为划分的效果更好。

到这里需要停顿一下，整理下思路：b(x)是根据x划分分支条件的函数，跟定一个x就产生一种分支，即对数据产生一种划分。

接下来要考虑，划分出来的每组数据的impuirity如何计算呢？

根据需求不同impurify有两种计算套路：

1）如果是regression的：就可以用均方差来衡量

2）如果是classification的：就可以用Gini index来衡量（想象一个极端情况，如果数据D都属于一类了，那么Gini index就是0了，即不纯度是0）

接下来，看这种算法迭代的终止条件：

有两种强行终止条件：

1）如果impurity=0了，即只剩一类数据了，就不用再划分了

2）如果xn全部相同了，也没法划分了，因为b(x)的输出只有一个

完整的C&RT算法如上图，非常neat的算法。

但是上述的算法隐含问题，就是overfitting的问题。

可以通过剪枝来处理这个问题，一个可行的算法就是，每次除去叶子节点i，保证除去某个叶子节点后Ein(i)能最小。

另外，考虑pratical场景，有可能有枚举类型（categorical features)特征，对于这样的特征C&RT模型也可以轻易的处理。

如果有missing feature怎么办？

其中一个办法就是surrogate branch，简单来说，就是如果某种属性缺失了，可以找到其替代品。

最后林对比了Decision Tree和AdaBoost-Stump两种算法：

区别：

1）C&RT可以conditional的切，切的效率可能更高

2）AdaBoost-Stump只能完全横刀或完全竖刀来切，有可能没有Decision Tree切的效率高

最后，林总结了Decision Tree的优势：

巴特西