机器学习技法-lecture9：Decision Tree

Decision Tree

Lecture8中我们主要介绍了AdaBoost演算法，实现这个算法的关键是两点：1、调整weight产生不一样的hypothesis，2、根据g表现的差异给与不同的票数即α，然后用linear aggregation将g合起来。本节课我们学习决策树演算法。

Decision Tree Hypothesis

我们首先看看研究的大课题aggregation model(即将得到的g组合成一个表现更好的G的过程）走到了哪一步，这块主要有两个大方向：1、在g是已知的情形下，我们可以做blending，方式主要有三种：每个g的权重一致的情况下使用voting/averaging的方法；每个g的权重不一致的情况下，可以将g当成特征转换，转换之后再丢进一个linear model中做就行了；为了在不同的情形下使用不同的g即conditional地使用g，同样可以将g当成特征转换，转换之后再丢入一个非线性的模型中做可以实现stacking。2、在g不知道的情形下，我们就需要一边学习得到g一边做aggregation，方式对应的同样的有三种，今天要介绍了就是表格的最后一个方块。

然后我们借助“下班后是否看线上教程”来搭建我们的model，我们画出整个决策示意图如右图，我们定义决策函数G(x)的公式如上图所示，其中g为那些基础的hypothesis,q为条件在某个节点是否成立

我们还可以从数据结构的角度来理解决策树，可以将其视为树根和一系列子树共同组成的集合，然后在子树内部又可以拓展成新的节点和子树，如此递归循环产生了完整的决策树。

然后我们看看决策树背后的一些事情，历史上决策树是一个被广泛使用的比较有效率的model，需要指出的是前人总结了多个决策树演算法，但是这些演算法更多地是前人实践总结出来的，并没有太多理论上保证，也就没法判断说孰优孰劣，所以总结地来说决策树加入了很多前人的“巧思”，但是这些并没有太多理论上的保证只是在实践层面的效果还不错而已。

Decision Tree Algorithm

接着我们可以搭建起基本的决策树演算法流程如上图，其中的关键4要素是：1、分支的数量C；2、分支的条件b;3、终止的条件；4、回传的基础hypothesis g。

接着我们介绍一个具体的决策树演算法—CART树，这个验算法有两个特性：1、C=2,即每个分支都是拆成两个；2、最后回传的g是一个常数，如果是做分类则最后回传的是资料集中标签较多的那项，如果是做回归则最后回传的是资料集标签的均值。

然后我们关注下cart怎么实现分支，我们一般通过decision stump(利用某个特征来将资料集切割成两份)将资料切成了两份D1和D2，然后我们又知道最后回传的g是一个常数，于是前人的思路是使用purifying来做分支的条件。这里的purifying指的是分类时标签一致或是回归时标签值比较接近，进而模型整体的表现会比较好。于是我们可以定义相应的b函数计算资料集D的“加权纯度”，公式见上图，所以接下来的问题是不纯度的计算问题。

很自然的一个思路是使用Ein来度量impurity，做回归任务时很自然可以使用标签值相对平均值的均方误差来度量impurity；做分类任务时，可以先计算数据集的纯度然后反算impurity，一种方式是直接计算数据集中标签个数最多的标签的占比，但是这种计算方式对整体资料集的利用比较有限；另一种方式是计算每个数据标签占比平方和，这种方法的有点在于考虑了资料集所有标签的分布情况，这种计算方式对应的impurity称为Gini系数，实际应用中Gini系数是使用比较多的方法。

最后我们看CART什么情况下会停下来，我们总结了两种不得不停下来的情形：1、非纯度变为0的时候;2、特征集都一样的时候，即没法做decision stump的时候。

我们最后一下总结CART数：它是一棵完全生长的树，它的树叶是常数，并且使用purifying作为二分枝的标准的树算法。

Decision Tree Heuristics in C&RT

我们已经建立了基本的CART树演算法流程，通过它我们可以得到fully-grown tree,仔细分析我们会发现这个model也是适用于做多分类任务的。

在fully-grown tree的生成过程中，理论上而言，如果我们输入的x的部分都是有差异的，则切割可以一直进行到底，结合最后返回一个常数可以知道我们最后可以实现Ein=0，这看起来是一个危险的信号，这意味着我们付出了过多的model复杂度的代价，往往预示着过拟合的发生，结合切割过程可以解释为随着切割的进行，节点上资料集变得越来越小，于是overfitting随着发生了。因此fully-grown tree往往不是一个好的模型，我们需要在他的基础上加入一些正则化的动作。

容易知道模型的复杂度正比于叶子的数量，于是很自然的正则化的方式是剪枝，具体的实现方式是找到所有的decision tree，然后最小化正则化后的error，但是找出所有的决策树是很难实现的，实践中我们通常的做法是先找到fully-grown tree G0,然后在G0上减去一片叶子，找出其中Ein最小的作为G1，接着在G1上载减去一片叶子，找出其中Ein最小的作为G2，……最后再最小化正则化的error，其中还有一个问题就是参数的选择，这时候validation会是一个不错的选择。

此外，CART演算法还有两个明显的特征，其一为它能有效地分割类别型数据；其二为它能在测试时有处理数据集中某特征缺失的情况，原因是建模过程中演算法会将特征对应的替代特征的切割方法保存起来，以供测试时调用。

Decision Tree in Action

接下来我们看看CART树算法的实践效果，首先我们看看在简单的数据集上的分类效果，可以发现决策树的分割边界不一定是跨平面的而AdaBoost stump的分割边界一定是跨平面的。

在复杂的数据集上做分类，通过比较可以发现决策树相对AdaBoost stump会更加有效率，这主要是因为他的切割方式可以做的更细致。

最后我们可以总结得到CART演算法的特点如下：

本节课我们主要学习了决策树演算法，首先我们指出它在aggregation model中的定位，接着我们采用递归思路建立了基础的模型框架和明确了模型要素，然后我们介绍了CART树模型，介绍了他的四要素，更进一步介绍了过拟合的解决方案，最后我们展示了model的表现。