决策树

决策树是广泛用于分类和回归任务的模型。

本质上，它从一层层的 if/else问题中进行学习，并得出结论。
这些问题类似于你在“20 Questions”游戏 9 中可能会问的问题。想象一下，你想要区分下面这四种动物：熊、鹰、企鹅和海豚。你的目标是通过提出尽可能少的 if/else 问题来得到正确答案。

决策树

在这张图中，树的每个结点代表一个问题或一个包含答案的终结点（也叫叶结点 ）。树的边将问题的答案与将问的下一个问题连接起来。用机器学习的语言来说就是，为了区分四类动物（鹰、企鹅、海豚和熊），我们利用三个特征（“有没有羽毛”“会不会飞”和“有没有鳍”）来构建一个模型。我们可以利用监督学习从数据中学习模型，而无需人为构建模型。

用于构造决策树的数据集
深度为 1 的树的决策边界（左）与相应的树（右）
深度为 2 的树的决策边界（左）与相应的树（右）
深度为 9 的树的决策边界（左）与相应的树的一部分（右）

想要对新数据点进行预测，首先要查看这个点位于特征空间划分的哪个区域，然后将该区域的多数目标值（如果是纯的叶结点，就是单一目标值）作为预测结果。从根结点开始对树进行遍历就可以找到这一区域，每一步向左还是向右取决于是否满足相应的测试。

决策树也可以用于回归任务，使用的方法完全相同。预测的方法是，基于每个结点的测试对树进行遍历，最终找到新数据点所属的叶结点。这一数据点的输出即为此叶结点中所有训练点的平均目标值。

控制决策树的复杂度

通常来说，构造决策树直到所有叶结点都是纯的叶结点，这会导致模型非常复杂，并且对训练数据高度过拟合。纯叶结点的存在说明这棵树在训练集上的精度是 100%。训练集中的每个数据点都位于分类正确的叶结点中。

防止过拟合有两种常见的策略：
一种是及早停止树的生长，也叫预剪枝 （pre-pruning）；
另一种是先构造树，但随后删除或折叠信息量很少的结点，也叫后剪枝 （post-pruning）或剪枝 （pruning）。
预剪枝的限制条件可能包括限制树的最大深度、限制叶结点的最大数目，或者规定一个结点中数据点的最小数目来防止继续划分。