决策树

总体介绍

决策树模型顾名思义就是通过一条条的决策来将样本划分来从而达到分类或回归的目的。决策树模型呈树形结构，下图粗略展示了一个分类决策树

其中圆表示特征，方块表示叶子节点也是最终分类的类别，我们通过利用样本中高价值的特征(房子拥有情况，工作的拥有情况)来构建这么一个决策树，那么每当有新样本来临时就可以通过构建完成的决策树来对其进行分类。其中所有路径互斥且完备，即不存在两个相同的样本被划分到不同的类别(互斥),任意一个样本都会被划分到一个类别。
我们还可以认为决策树是定义在特征空间与类空间上的条件概率分布，即将特征空间划分成一个个互不相交的单元，这与之前所讲的KNN算法的核心思想一致。下图展示了决策树在两个特征\(x_1,x_2\)下的划分情况。

这意味着，当所有样本的两个特征满足下面的情况时
\(x_1 \leq a_1\)且\(x_2 \leq a_2\)或者\(x_1 > a_1\)且\(x_2 > a_3\)
将被划分为正类。
同时我们也可以上上面的图转换为决策树进行对照，如下图所示。

在使用决策树模型时通常包含三个步骤：特征选择、决策树生成和决策树剪枝。

决策树学习

从上面的介绍中，我们可以知道决策树是通过对特征的取值不断进行分解从而构建成树的，但是基于特征空间划分的类的条件概率模型有无穷多个，我们选择的模型不仅要对训练数据有很好的拟合更应该注重其泛化能力。总体上来说，决策的学习包括下面三个注意部分：

• 特征选择。特征选择的目的选择具有较强分类能力的特征，如果一个特征在对所有类别的区分不大，那么这个特征可能就没有较大的意义。衡量特征好坏有信息增益、信息增益比等指标。后面的内容会一步步剖析它们。
• 决策树的生成。当通过特征选择得到有价值的特征后，下面的目的就是通过这些特征来构建决策树，常见的算法ID3和C4.5。
• 决策树的剪枝。最后为了避免生成的决策树过于臃肿，我们需要使用剪枝算法对决策树进行约简，使其具有更好的泛化能力。相关剪枝算法也会在后面介绍。