3.6 决策树
决策树吸引人的地方在于其模型的可解释性。正如其名称“决策树”所意味的那样，我们可以把此模型看作将数据自顶向下进行划分，然后通过回答一系列问题来做出决策的方法。
以下图为例，我们使用决策树来决定某一天的活动：
基于训练数据集的特征，决策树模型通过一系列的问题来推断样本的类标。虽然上面的示例在类别变量的基础上给出了决策树的概念，但这些概念在面对特征变量时也同样适用。此模型也适用于数据特征取值为实数的鸢尾花数据集。例如，我们可以简单为萼片宽度设定一个临界值，并提出一个二元问题：“萼片宽度是否达到2.8厘米？”
使用决策树算法，我们从树根开始，基于可获得最大信息增益（information gain，IG）的特征来对数据进行划分，我们将在下一节详细介绍信息增益的概念。通过迭代处理，在每个子节点上重复此划分过程，直到叶子节点。这意味着在每一个节点处，所有的样本都属于同一类别。在实际应用中，这可能会导致生成一棵深度很大且拥有众多节点的树，这样容易产生过拟合问题，由此，我们一般通过对树进行“剪枝”来限定树的最大深度。
3.6.1 最大化信息增益——获知尽可能准确的结果
为了在可获得最大信息增益的特征处进行节点划分，需要定义一个可通过树学习算法进行优化的目标函数。在此，目标函数能够在每次划分时实现对信息增益的最大化，其定义如下：
其中，f为将要进行划分的特征，Dp与Dj分别为父节点和第j个子节点，I为不纯度衡量标准，Np为父节点中样本的数量，Nj为第j个子节点中样本的数量。可见，信息增益只不过是父节点的不纯度与所有子节点不纯度总和之差——子节点的不纯度越低，信息增益越大。然而，出于简化和缩小组合搜索空间的考虑，大多数（包括scikit-learn）库中实现的都是二叉决策树。这意味着每个父节点被划分为两个子节点：Dleft和Dright。
就目前来说，二叉决策树中常用的三个不纯度衡量标准或划分标准分别是：基尼系数（Gini index，IG）、熵（entropy，IH），以及误分类率（classification error，IE）。我们从非空类别（p（i|t）≠0）熵的定义开始讲解：
其中，p（i|t）为特定节点t中，属于类别c的样本占特定节点t中样本总数的比例。如果某一节点中所有的样本都属于同一类别，则其熵为0，当样本以相同的比例分属于不同的类时，熵的值最大。例如，对二类别分类来说，当p（i＝1|t）＝1或p（i＝0|t）＝0时，熵为0，如果类别均匀分布，即p（i＝1|t）＝0.5且p（i＝1|t）＝0.5时，熵为1。因此，我们可以说在决策树中熵的准则就是使得互信息最大化。
直观地说，基尼系数可以理解为降低误分类可能性的标准：
与熵类似，当所有类别是等比例分布时，基尼系数的值最大，例如在二类别分类中（c＝2）：
然而，在实践中，基尼系数与熵通常会生成非常类似的结果，并不值得花费大量时间使用不纯度标准评估树的好坏，而通常尝试使用不同的剪枝算法。
另一种不纯度衡量标准是误分类率：
这是一个对于剪枝方法很有用的准则，但是不建议用于决策树的构建过程，因为它对节点中各类别样本数量的变动不敏感。我们通过下图中两种可能的划分情况对此进行解释：
以数据集Dp为例（在父节点Dp），它包含属于类别1的40个样本和属于类别2的40个样本，我们将它们分别划分到Dleft和Dright。在A和B两种划分情况下，使用误分类率得到的信息增益都是相同的（IGE＝0.25）：
然而，在使用基尼系数时，与划分A（IGG＝0.125）相比，更倾向于使用B（IGG＝0.16）的划分，因为这样子节点处的类别纯度相对更高：
同样，以熵为评估标准时，也是B（IGG＝0.31）的信息增益大于A（IGG＝0.19）：
为了更直观地比较前面提到的三种不同的不纯度衡量标准，我们绘制样本属于类别1、概率介于[0,1]情况下不纯度的图像。注意，我们在图像中对熵（entropy/2）做了缩放，以便直接观察熵和误分类率对基尼系数的影响。代码如下：
执行上述代码后可得到如下图像：
3.6.2 构建决策树
决策树可以通过将特征空间进行矩形划分的方式来构建复杂的决策边界。然而，必须注意：深度越大的决策树，决策边界也就越复杂，因而很容易产生过拟合现象。借助于scikit-learn，我们将以熵作为不纯度度量标准，构建一棵最大深度为3的决策树。虽然特征缩放是出于可视化的目的，但在决策树算法中，这不是必须的。代码如下：
执行上述代码，我们得到了决策数中与坐标轴平行的典型决策边界：
scikit-learn一个吸引人的功能就是，它允许将训练后得到的决策树导出为.dot格式的文件，这使得我们可以使用GraphViz程序进行可视化处理。GraphViz支持Linux、Windows和Mac OS X系统，可在http://www.graphviz.org免费下载。
首先我们从scikit-learn的tree子模块中调用export_graphviz函数生成.dot文件，代码如下：
在电脑上安装好GraphViz后，通过命令行窗口在保存tree.dot文件的路径处执行下面的命令，可将tree.dot文件转换为PNG文件。
通过观察GraphViz创建的图像，可以很好地回溯决策树在训练数据集上对各节点进行划分的过程。最初，决策树根节点包含105个样本，以花瓣宽度≤0.75厘米为界限，将其划分为分别包含34和71个样本的两个子节点。第一次划分后，可以看到：左子树上的样本均来自Iris-Setosa类（熵＝0），已经无需再划分。在右子树上进一步划分，直到将Iris-Versicolor和Iris-Virginica两类分开。
3.6.3 通过随机森林将弱分类器集成为强分类器
由于具备好的分类能力、可扩展性、易用性等特点，随机森林（random forest）过去十年间在机器学习应用领域获得了广泛的关注。直观上，随机森林可以视为多棵决策树的集成。集成学习的基本理念就是将弱分类器集成为鲁棒性更强的模型，即一个能力更强的分类器，集成后具备更好的泛化误差，不易产生过拟合现象。随机森林算法可以概括为四个简单的步骤：
1）使用bootstrap抽样方法随机选择n个样本用于训练（从训练集中随机可重复地选择n个样本）。
2）使用第1）步选定的样本构造一棵决策树。节点划分规则如下：
（1）不重复地随机选择d个特征；
（2）根据目标函数的要求，如最大化信息增益，使用选定的特征对节点进行划分。
3）重复上述过程1～2000次。
4）汇总每棵决策树的类标进行多数投票（majority vote）。多数投票将在第7章中详细介绍。
此处，步骤2）对单棵决策树的训练做了少许修改：在对节点进行最优划分的判定时，并未使用所有的特征，而只是随机选择了一个子集。
虽然随机森林没有决策树那样良好的可解释性，但其显著的优势在于不必担心超参值的选择。我们通常不需要对随机森林进行剪枝，因为相对于单棵决策树来说，集成模型对噪声的鲁棒性更好。在实践中，我们真正需要关心的参数是为构建随机森林所需的决策树数量（步骤3））。通常情况下，决策树的数量越多，但是随机森林整体的分类表现就越好，但这同时也相应地增加了计算成本。
尽管在实践中不常见，但是随机森林中可优化的其他超参分别是：bootstrap抽样的数量（步骤1））以及在节点划分中使用的特征数量（步骤（2）），它们所采用的技术将在第5章中讨论。通过选择bootstrap抽样中样本数量n，我们可以控制随机森林的偏差与方差权衡的问题。如果n的值较大，就降低了随机性，由此更可能导致随机森林的过拟合。反之，我们可以基于模型的性能，通过选择较小的n值来降低过拟合。包括scikit-learn中RandomForestClassifier在内的大多数对随机森林的实现中，bootstrap抽样的数量一般与原始训练集中样本的数量相同，因为这样在折中偏差与方差方面一般会有一个好的均衡结果。而对于在每次节点划分中用到的特征数量m，我们选择一个比训练集中特征总量小的值。在scikit-learn及其他程序实现中常用的默认值一般是
，其中m是训练集中特征的总量。
为了方便起见，我们不是自己从决策树开始构造随机森林，而是使用scikit-learn中已有的实现来完成：
执行上述代码后，通过随机森林中决策树的组合形成的决策区域如下图所示：
在上述代码中，我们在节点划分中以熵为不纯度衡量标准，且通过参数n_estimators使用了10棵决策树进行随机森林的训练。虽然我们只是在一个很小的训练数据集上构建了一个非常小的随机森林，但是出于演示的要求，我们使用n_jobs参数来设定训练过程中所需的处理器内核的数量（在此使用了CPU的两个内核）。