本文共 2134 字，大约阅读时间需要 7 分钟。

决策树，顾名思义就是用树形结构来做决策。

如何把我们想达到的算法表达成一棵树

直接上例子，图源来自维基百科（titanic dataset)：

决策树其实就是一个根据条件从上往下的判断流程，根据条件的是或否，分支成下一层的判断与决策。如果分支不再是一个判断条件，那么它就是一个决策。

从这个图我们可以看出feature（在这里面就是判断条件啦）的重要性，直接决定了你会走往哪个决策，性别，年龄，是否是sibsp，这些features共同决定了给定数据会通往哪个决策，survived or died。

决策树的分类

根据决策树给出的结果，我们可以把决策树分成分类决策树和回归决策树。

分类决策树：决策树得出的结果是不同的类别，比如可贷款和不可贷款 回归决策树：决策是对连续变量的预测，如预测房价 使用哪类决策树看你想解决什么样的问题，是分类还是回归。 决策树的构建算法有三种：

1. ID3
2. C4.5
3. CART

构建算法名字有些奇怪，会在下篇文章介绍这三种构建算法，ID3是基本算法，后两种都是在ID3的基础上优化后的算法。

我们接下来举的例子都是用CART。

怎么构造决策树

主要有三个问题：

1. 选什么特征来当条件
2. 条件判断的属性值是什么？年龄 > 10? 还是年龄 > 15？
3. 什么时候停止分裂，达到我们需要的决策

递归二叉分裂

我们有一堆特征，最直接的想法就是，我们都试一下然后看看谁效果好就选谁嘛。这里看谁效果好是用的损失函数来判断的。为什么这个方法的名字前面有递归二字呢，因为选好最好的特征进行二叉分裂后，对分裂的结果可以再进行相同的办法进行分裂（用损失函数判断哪个特征最适用）。

这其实就是贪心的思想，我们每一步都力求最好，让损失函数达到最低。

CART的损失函数思想

从上面的递归二叉分裂方法可以看出，损失函数在这个方法中起到了至关重要的作用。

首先明确一个想法，损失函数是想把差不多属性的数据弄到一个结点里的，换言之，就是我进行分裂之后，分裂出来的两个结点，我们希望他们的决策有比较鲜明的差异。比如决策结果为患病和不患病，选择特征进行分裂后，我们希望一边集中的是患病的结果，一边集中的是不患病的结果，这才是一个好的分类决策树。如果分裂完，你两边患病不患病都是五五开，那跟我们自己闭着眼睛进行分类有什么区别呢？ 明确损失函数想干什么后，我们就可以来看看分类决策树和回归决策树的损失函数具体长什么样了。

分类树的损失函数

$$G=\sum _i(ps\ast (1-ps))$$

在以上公式中，G是损失函数，i代表分裂出的不同的组，ps是在这个组里有相同结果的数据占总数据的比例。 比如我的结果是患病和不患病，我用年龄当我的特征将训练集分裂成了两个结点，每个结点都是100个数据。我是知道训练集数据的label的，第一个结点数据中结果是患病的有70个，不患病30个。第二个结点数据中结果是患病的有10个，不患病90个。我的损失函数计算就是： $$0.7\ast 0.3+0.1\ast 0.9=0.3$$ 最糟糕的情况就是分出来的两个结点里，每个结点患病不患病都是各占一半，那这个分裂毫无作用，损失函数也会达到最大值： $$0.5\ast 0.5+0.5\ast 0.5=0.5$$

回归树的损失函数

回归的话，损失函数度量的就是预测值和真实值的偏差了，在这里用残差的平方和来衡量：

$$G=\sum _i(y_p-y{)}^2$$ yp是y prediction，是我们通过回归决策树回归出来的预测值，y是实际的真值，损失函数用预测值和真值差的平方和来表示。

到这已经解决了1、2两个问题了。选择特征是把全部特征都试一遍，选择边界是把属性值都试一遍（连续型的变量衍生出多个条件比如小于20岁，20-40岁，40-60岁），衡量的标准是损失函数。那么什么时候出决策的结果呢，即什么时候停止分裂？

停止分裂的条件

如果我们把所有特征都用上，让他疯狂分裂，那么他最后就是一个很复杂的树，并且有非常严重的过拟合。所以我们需要设置一个让树停止生长分裂的条件，一般有两种：

1. 叶结点包含的最小数据量，一旦小与这个值，就停止分裂。（比如你分裂出来的一个结点只有8个数据，你设置的最小数据量是10，那么这个结点就不要再分裂了！）
2. 树的最大深度，一旦你的树分裂到了最大深度，那么不要再让处于这个深度的结点继续分裂下去了！

总结

1. 决策树是使用树形结构，从上而下根据条件判断，最后得出决策的一种算法
2. 根据输出的决策结果是为了解决分类还是回归问题，决策树可分为分类决策树和回归决策树
3. 建树需要解决三个问题：选择特征，选择判断条件的属性值，确定停止分裂的情况。
4. 解决前两个问题用的是损失函数，选择损失函数最小的特征和其分裂条件。解决第三个问题是设立一些分裂的门槛如叶节点最小数据量和决策树最大深度。

转载地址：http://vkksi.baihongyu.com/