引言：
这篇小结是为了准备面试而写的，从决策树的基本概念到决策树的学习再到决策树的剪枝，粗中有细，话不多说开始咯。
决策树模型
决策树模型是一个有监督的分类模型，其本质是选择一个能带来最大信息增益的特征进行节点分裂，直到满足某些约束条件例如叶子结点纯度到达一定阈值。下图为决策树的一个示例：
1.决策树与if-then规则、条件概率分布
在理解决策树的时候，可以将决策树看做一个if-then规则的集合。对于一棵决策树，我们将决策树的根节点到叶子节点的每一条路径对应一条规则；其中路径上的内部节点对应着规则的条件，而叶节点的类或者值对应这条规则的结论。决策树上的路径有一个重要的性质：互斥且完备性质。什么意思呢，就是说每一个实例都被一条路径所覆盖，且一个实际仅被一条路径覆盖。这里所谓的特征是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树还可以表示为给定特征下的类条件概率分布。这个条件概率分布定义在特征空间的一个划分上。将特征空间划分为互补相斥的区域，并在每个区域上定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个区域，决策树所表示的条件概率分布由各个单元给定条件下的类的条件概率组成（有点绕）。举个例子，假设$X$为表示特征的随机变量，$Y$为表示类别的随机变量，那么这个条件概率分布可以写为$P(Y|X)$。$X$的取值于给定划分下区域的集合，Y取值于类的集合。决策树分类的时候将该节点的实例强行分到条件概率大的一类中去。
下图(a)表示了特征空间的一个划分。图中的大正方形表示特征空间。这个大正方形被若干个小矩形分割，每个小矩形表示一个单元。特征空间划分上的单元构成了一个集合，$X$取值为单元的集合。为简单起见，假设只有两类：正类和负类。下图(b)表示特征空间划分确定的时候，特征给定条件下类的条件概率分布，当某个单元$c$的条件概率满足$P(Y = +1|X = c) > 0.5$时，则认为这个单元属于正类。图(c)为对应于图(b)中条件概率分布的决策树。
2. 决策树的学习
决策树的学习本质上是从训练集中归纳出一组分类规则。与训练数据集不矛盾的决策树可能有n个(n>=0)，我们需要的是一个与训练数据矛盾较小的决策树，同时这棵树也要具备较好的泛化能力。决策树的学习的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数，调整树的结构使目标函数最小化。
当损失函数确定之后，学习的问题就变为在损失函数确定情况下选择最优决策树的问题了。因为从所有可能的决策树中选取最优决策树是$NP$完全问题，所以在实践中决策树的学习算法一般是采用启发式方法，近似求解这一最优化问题。大致的构造流程为：构建根结点，将所有训练数据都放在根结点。 选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在 当前条件下最好的分类。如果这些子集己经能够被基本正确分类，那么构建叶结点， 并将这些子集分到所对应的叶结点中去:如果还有子集不能被基本正确分类，那么就 对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进 行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每 个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据 却未必有很好的分类能力，即可能发生过拟合现象。 我们需要对己生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。
简单的总结就是决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。 决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。决策树学习常用的算法有ID3、C4.5与CART，接下来会结合这些算法简单的讲解决策树学习的特征选择、决策树的生成和剪枝。
2.1 特征选择
特征选择在于选取对训练数据具有分类能力的特征，使用具备较好分类能力的特征进行训练可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个 特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
2.1.1 信息增益
先给出熵以及条件熵的定义。
在信息论与概率统计中，熵(entropy)是对随机变量不确定性的度量。设$X$是一个取有限个值的离散随机变量，其概率分布为:$P(X = x_{i}) = p_{i}, i = 1, 2, ...,n$。则随机变量$X$的熵定义为：
有定义可知，熵只依赖于$X$的分布，而与$X$的取值无关，熵越大，随机变量的不确定性也就越大。
原文：https://www.cnblogs.com/z1141000271/p/12768236.html