决策树
决策树简介
和朴素贝叶斯一样，决策树(decision tree)也是一种简单但有效的分类算法。决策树的原理是将数据的分布规律表达为一系列的条件判断，从而在引入新样本时通过一系列条件判断将其分到合理的类别中。这一系列条件判断会形成一个树形的结构，每个节点都是一次判断过程：
接下来看一个实际的示例。对于以下数据：
显然靠左侧位置分布的都是红色的样本，因此第一次可以将这些样本划分出来：
而靠右侧位置分布的都是蓝色的样本，接下来将这些样本划分出来：
对于中间位置的样本，靠上方的是蓝色位置的样本：
靠下方的是红色位置的样本：
这几个决策过程就构成了完整的分类依据。
在 Scikit-Learn 中，可以从以下位置导入决策树：
下图展示了 Scikit-Learn 中决策树的分类边界：
可以看到 Scikit-Learn 中的决策树似乎找到了一个更好的规律，使得只需要两次判断就能完成分类。不过相应的决策边界更靠近样本，过拟合的可能性增大。
既然一个数据集的决策树不是唯一的，那么就需要有一种指标来衡量哪些是好的决策树，或者说如何建立一棵决策树。决策树的建树依据主要是基尼系数(gini)和信息熵(Entropy)，它们的本质都是一样的，用于度量一个系统中的失序程序。建立决策树的思路就是使每一次决策后系统的混乱程度降低，从而得到有序的决策结果。
什么是基尼系数
数据集 \\( D \\) 的基尼系数 \\( \text{Gini}(D) \\) 反映了从数据集 \\( D \\) 中随机抽取两个样本，它们的类别不一致的概率。因此，如果数据有 \\( k \\) 个类别，则基尼系数的计算公式为：
\\[ \text{Gini}(D) = \sum_{i=1}^{k} p_i(1-p_i) = 1 - \sum_{i=1}^{k} p_i^2 \\]基尼系数用于衡量一个系统的不确定性，系统的基尼系数越大，表示系统不确定性越高，系统的混乱程度越高，分类效果越差。
接下来看一个具体示例。假设某个数据集中有 300 个数据，形成 3 个分类，每个分类数据个数相同，那么数据集的基尼系数为：
\\[ \begin{align} \text{Gini}(D) &= 1 - (\frac 1 3)^2 - (\frac 1 3)^2 - (\frac 1 3)^2 \\ &= \frac 2 3 \approx 0.67 \end{align} \\]经过决策树的一次分类，将 \\( S_1=100 \\) 个数据划分成一个子数据集，该数据集分别包含每个分类的样本 10 、20 、70 个，那么该子数据集的基尼系数为：
\\[ \begin{align} \text{Gini}(D_1) &= 1 - (\frac 1 {10})^2 - (\frac 2 {10})^2 - (\frac 7 {10})^2 \\ &= 0.46 \end{align} \\]而另一部分子数据集的基尼系数为：
\\[ \begin{align} \text{Gini}(D_2) &= 1 - (\frac 9 {20})^2 - (\frac 8 {20})^2 - (\frac 3 {20})^2 \\ &= 0.615 \end{align} \\]分类后，整个数据集的基尼系数需要考虑各自的样本量：
\\[ \begin{align} \text{Gini}(D) &= \frac{S_1}{S_1 + S_2}\text{Gini}(D_1) + \frac{S_2}{S_1 + S_2}\text{Gini}(D_2) \\ &\approx 0.563 \end{align} \\]划分后，系统的基尼系数降低，说明该划分有效。从直观上看，每个子数据集的样本更容易确定属于哪个类别，样本的纯度更高。因此基尼系数也称基尼不纯度(gini impurity)
如果经过若干次划分后，每个数据集中所有的样本都属于同一个类别，那么此时每个数据集的基尼系数为 0 ，总的基尼系数也为 0 ，得到了最好的划分结果。决策树的目的就是得到这样的结果。
除了基尼系数外，还可以使用信息熵作为评估方式，它的含义是类似的。具体使用哪种评估方式通过超参数 criterion 设置，默认的标准是基尼系数。
决策树的一个特点是它天然支持多分类，而不需要使用一对多方法实现。下图展示了一棵多分类决策树的决策边界：
对于连续数据，Scikit-Learn 使用分类和回归树(Classification and Regression Tree, CART)算法来建立一棵决策树，该算法找到某个特征变量合适的切分点，使得切分后左右两侧数据总体的基尼系数发生下降，那么说明这是一次合理的切分，可以作为一次决策过程。而左右两侧数据可以使用相同的逻辑递归切分，直到总的基尼系数降为 0 或达到停止条件为止。可以看出该算法仅生成二叉树，即它是一种 if ... else 形式的决策。而其它算法（例如 ID3 算法和它的改进版 C4.5 算法）可能找到多个切分点，形成类似 elif 的决策。
CART 是一种贪婪算法，因为每次切分只能得到一个局部较优解，但不能确定是否是全局最优解。而寻找全局最优解是一个很复杂的问题，当前的算法需要采用指数级的时间复杂度才能给出解，显然是不实际的。
CART 算法的这种性质还会带来另一个问题：由于每次被切分的维度是任意的，因此同一个模型多次调用决策树得到的决策边界往往不会完全相同。下图展示了相同的数据集使用不同随机种子生成的决策树，由于每次选择不同的维度划分数据而导致不同的结果：
除此之外，由于 CART 算法每次都只从一个维度上切分，因此得到的决策边界由垂直于坐标轴的直线构成。如果数据集的边界是倾斜的，那么决策树只能通过锯齿状的边界来模拟它，这既会导致不必要的多次判断，也容易使决策树发生过拟合：
正则化与决策树剪枝
以上多分类的决策树看似表现良好，但注意到其中出现了一些不合常理的细长边界，这说明决策树可能已经出现了过拟合。
解决过拟合的方式是约束模型的某些参数不要过大，而约束决策树的方式是让它不要过度生长，导致决策太详细而出现过拟合。剪枝(pruning)是常见的约束方式，用于缩小决策树的规模，在防止决策树出现过拟合的同时还能提高分类速度。
决策树的剪枝方式主要分为以下两种：
- 前剪枝(Pre-Pruning)
前剪枝的思路是设置一个生长阈值，使决策树在生长完成前如果达到阈值就停止生长。
最简单的约束条件就是约束决策树的深度（根到树叶的路径长），在 Scikit-Learn 中由超参数 max_depth 控制。一旦达到最大深度，则决策树停止生长。
除了最大深度外，Scikit-Learn 还提供了一些其它前剪枝参数，如下：
| 参数 | 说明 |
|---|---|
| min_samples_split | 节点继续划分（生长）所需的最小样本数，默认值为 2 ，因此只要可以都会继续划分 |
| min_samples_leaf | 叶节点需要包含的最小样本数，默认值为 1 ，因此可能出现单个异常样本被划到一组的情况 |
| max_leaf_nodes | 最大叶节点数，默认值 None 代表不限制，因此形成的决策边界可以无限复杂 |
| min_impurity_decrease | 如果继续划分能使基尼不纯度的下降大于该值，那么便继续划分。默认值 0.0 代表只要能使不纯度下降就继续划分 |
可以看出决策树的默认参数并没有限制决策树的增长，适当增加最小值与约束最大值可以防止异常值的影响，并增强决策树的泛化能力。下图展示了一棵没有约束的决策树和加上不同约束条件后的决策边界：
- 后剪枝(Post-Pruning)
相比前剪枝，后剪枝的处理方式更复杂但也更有效。后的思路是先让决策树完全生长，再将其中不必要的分支去除（通常去除某个节点的子树或在结果中合并相近的类别）。后剪枝有许多算法，其中比较常用的是代价复杂度剪枝(Cost Complexity Pruning, CCP)。
剪枝用于平衡决策树的规模和正确率，代价复杂度剪枝中代价表示因剪枝而增加的错分样本，复杂度表示因剪枝而缩减的树的规模。代价复杂度剪枝使用以下公式衡量某个节点子树的代价复杂度：
其中 \\( R(T) \\) 表示该节点未剪枝时的误差，\\( R(t) \\) 表示剪枝后的误差，那么分母就表示由于剪枝增加的误差（代价）；\\( N(T) \\) 表示该节点所有子树的树叶个数，那么分子可以反映子树的规模（复杂度）；因此 \\( \alpha \\) 代表总体的代价复杂度，如果 \\( \alpha \\) 很小，代表剪除某个节点的子树增加的误差不大且能去除较大规模的枝叶，那么这就是一次好的剪枝。
在实际剪枝中，一般先计算决策树每个非叶节点的 \\( \alpha \\) ，并按 \\( \alpha \\) 由小到大的顺序剪除对应节点的子树，直到设定的 \\( \alpha \\) 阈值为止。也可以从每次剪枝都得到的决策树中选择最好的一棵。
在 Scikit-Learn 中，可以通过 .cost_complexity_pruning_path(X, y) 方法获取决策树每一次 CCP 剪枝后的 \\( \alpha \\) 值（按 \\( \alpha \\) 由小到大剪枝）和不纯度：
再次生成决策树时，通过 ccp_alpha 超参数可以控制决策树生长的阈值，这样就实现了后剪枝。
决策树与模型可视化
决策树的一个优点是每一步的决策过程都是透明的，如果有需要的话甚至可以检查决策树的每一步细节。
Scikit-Learn 提供了决策树与 Graphviz 交互的接口。Graphviz 是一个开源的可视化工具包，它可以绘制使用 dot 标记语言描述的包括流程图、关系图在内的各种图表。
可以在 https://graphviz.gitlab.io/download/ 里下载该软件。下载完成后安装到本地，安装时注意要将其添加到系统的环境变量中，这一步的目的是使用它提供的 dot 命令行工具完成文本到图片的编译。
可以使用 Scikit-Learn 提供的工具将模型导出为 .dot 文件：
然后在命令行中使用 dot 工具完成图片的输出。可以输出的图片格式有许多种，包括常见的 PNG 、PDF 和 SVG 等：
输出的决策过程如下：
其中 X[0] 表示样本的第一个特征变量（本例中为横坐标的值）；gini 表示该节点的基尼系数；samples 表示该节点包含的样本数；value 表示该节点中各类别样本的数量。根据这些提供的信息，就能清楚地了解到决策树运作的过程。下图是该决策树最终形成的决策边界：
决策树回归
决策树也可以用作回归。这种情况下，每个树叶节点不再预测离散的类别，而是一个连续的值，就像这样：
决策树回归与分类的原理是类似的，只不过不再采用基尼系数或熵作为划分的依据，而是均方误差 \\( \text{MSE} \\) 。具体来说，就是在每一次分裂时试图使以下结果最小：
\\( \text{MSE} \\) 是节点中包含的所有样本真实值和预测值差值的和，预测值可以用所有样本的均值来描述。
决策树回归的优点是不用添加额外特征也能拟合曲线数据，但是拟合结果也不是曲线，而是阶跃的直线，并且和分类一样也有着严重的过拟合问题：如果不加约束地生长，决策的最终结果会落到每个值上：
可以用相同的方式对回归决策树剪枝，或者使用 Graphviz 导出为可视化图片。
总的来说，决策树是一种简单且直观的算法，它只求能够将两类样本分开，而不考虑分类的质量如何。除了容易导致过拟合外，决策树的分类边界也不够理想，不仅均垂直于坐标轴，而且完全没有考虑远离样本的问题，因此对异常值较为敏感。