3.6　决策树学习

如果关心可解释性，那么决策树分类器就是有吸引力的模型。正如其名称所暗示的那样，我们可以认为该模型是根据一系列要回答的问题做出决定来完成数据分类。

在下面的例子中，让我们考虑用决策树来决定某一天的活动安排，如图3-17所示。

基于训练数据集的特征，决策树模型通过对一系列问题的学习来推断样本的分类标签。虽然图3-17说明了基于分类变量的决策树概念，但是如果特征是像鸢尾花数据集这样的实数，这些概念也同样适用。例如，我们可以简单地定义萼片宽度特征轴的临界值，并且问一个二元问题：“萼片的宽度≥2.8厘米吗？”

使用决策树算法，我们从树根开始，在信息增益（IG）最大的特征上分裂数据，后续章节会更加详细地解释。各子节点在迭代过程中重复该分裂过程，直至只剩下叶子节点为止。这意味着所有节点上的样本都属于同一类。在实践中，这可能会出现根深叶茂的树，这样容易导致过拟合。因此，我们通常希望通过限制树的最大深度来对树进行修剪（prune）。

3.6.1　最大化信息增益——获得最大收益

为保证在特征信息增益最大的情况下分裂节点，我们需要先定义目标函数，然后进行决策树学习和算法优化。该目标函数可以在每次分裂的时候最大化信息增益，定义如下：

这里f是分裂数据的特征依据，Dp和Dj为父节点和第j个子节点，I为杂质含量，Np为父节点的样本数，Nj是第j个子节点的样本数。正如我们所看到的那样，父节点和子节点之间的信息增益仅在杂质含量方面存在着差异，即子节点杂质含量越低信息增益越大。然而，为简便起见，同时考虑到减少组合搜索空间，大多数软件库（包括scikit-learn）只实现二元决策树。这意味着每个父节点只有Dleft和Dright两个子节点：

在二元决策树中，度量杂质含量或者分裂标准的三个常用指标分别为基尼杂质度（IG）、熵（IH）和分类误差（IE）。我们从非空类（p（i|t）≠0）熵的定义开始：

其中p（i|t）≠0为某节点t属于i类样本的概率。如果节点上的所有样本都属于同一个类，则熵为0，如果类的分布均匀，则熵值最大。例如，对二元分类，如果p（i＝1|t）＝1或p（i=0|t）=0，则熵为0。如果类分布均匀，p（i＝1|t）＝0.5，p（i＝0|t）＝0.5，则熵为1。所以，我们可以说熵准则试图最大化决策树中的互信息。

直观地说，可以把基尼杂质理解为尽量减少错误分类概率的判断标准：

与熵类似，如果类是完全混合的，那么基尼杂质最大，例如在二元分类中（c=2）：

然而，基尼杂质和熵在实践中经常会产生非常相似的结果，而且通常并不值得花很多时间用不同的杂质标准来评估树，更好的选择是尝试不同的修剪方法。

另外一种杂质度量的方法是分类误差：

IE（t）=1-max{p（i|t）}

这对修剪树枝是个有用的判断标准，但我们并不推荐把它用于决策树，因为它对节点的分类概率变化不太敏感。可以通过图3-18所示的两种可能的分裂场景来说明。

从数据集的父节点Dp开始，它包含40个分类标签为1的样本和40个分类标签为2的样本，要分裂成Dleft和Dright两个数据集。在A和B两种场景下，用分类误差作为分裂标准得到的信息增益（IGE=0.25）相同：

然而，与场景A（IGG=0.125）相比，基尼杂质有利于分裂场景B（IGG=0.16），该场景确实是纯度更高：

同样，与场景A（IGH=0.19）相比，熵准则对场景B（IGH=0.31）更为有利：

为了能更直观地比较前面讨论过的三种不同的杂质标准，我们将把分类标签为1、概率在［0,1］之间的杂质情况画在图上。注意，我们还将添加一个小比例样本的熵（熵/2）来观察介于熵和分类误差中间的度量标准——基尼杂质，具体的示例代码如下：

执行前面的示例代码得到图3-19。

3.6.2　构建决策树

通过将特征空间划分成不同的矩形，决策树可以构建复杂的决策边界。然而，我们必须小心，因为决策树越深，决策边界就越复杂，越容易导致过拟合。假设最大深度为4，以熵作为杂质度量标准，用scikit-learn来训练决策树模型。虽然为了可视化，我们可能需要进行特征缩放，但请注意该特征缩放并非决策树算法的要求。代码如下：

执行代码后，通常我们会得到决策树与坐标轴平行的决策边界，如图3-20所示。

scikit-learn有一个不错的功能，它允许我们在训练完成后轻松地通过下述代码可视化决策树模型（如图3-21所示）：

然而，作为绘制决策树的后端，用Graphviz程序可以更好地完成可视化。读者可以从http://www.graphviz.org免费下载该程序，它支持Linux、Window和macOS。除了Graphviz以外，我们还将采用被称为PyDotPlus的Python库，其功能与Graphviz类似，它允许把.dot数据文件转换成决策树的图像。在安装Graphviz后，我们可以直接调用pip程序安装PyDotPlus（http://www.graphviz.org/download上有详细的指令），例如，在你自己的计算机上可以执行下面的命令：

安装PyDotPlus的先决条件

注意到在某些系统中，在安装PyDotPlus之前，你可能要先执行下述命令以安装其所依赖的软件包：

执行下述代码将在本地目录以PNG格创建决策树的图像文件：

通过设置out_file=None，可以直接把数据赋予dot_data变量，而不是在磁盘上产生中间文件tree.dot。参数filled、rounded、class_names和feature_names为可选项，但是要使图像的视觉效果更好，就需要添加颜色、边框的边缘圆角，并在每个节点上显示大多数分类标签，以及分裂标准的特征。这些设置完成后将得到图3-22所示的决策树图像。

现在，我们可以在决策树图上很好地追溯训练数据集的分裂过程。从105个样本的根节点开始，以花瓣宽度0.75厘米作为截止条件，先把样本数据分裂成大小分别为35和70的两个子节点。我们可以看到左面子节点的纯度已经很高，它只包含Iris-setosa类（基尼杂质度=0）。而右面子节点则进一步分裂成Iris-versicolor和Iris-virginica两类。

在树以及决策区域图上，我们可以看到决策树在花朵分类上的表现不错。不幸的是scikit-learn目前还不提供手工修剪决策树的函数。然而，我们可以返回到前面的代码示例，把决策树的参数max_depth修改为3，然后与当前的模型进行比较，但是我们将把这作为练习题留给感兴趣的读者。

3.6.3　多个决策树的随机森林组合

在过去十年里，由于集成方法具有良好的分类性能和对过拟合的鲁棒性，该算法在机器学习的应用中广受欢迎。虽然在第7章中，我们将讨论包括装袋（bagging）和boosting在内的不同集成方法，但是在这里我们将先讨论基于决策树的随机森林算法，该算法以其良好的可扩展性和易用性而闻名。可以把随机森林视为决策树的集成。随机森林的原理是对受较大方差影响的多个决策树分别求平均值，然后构建一个具有更好泛化性能和不易过拟合的强大模型。随机森林算法可以概括为以下四个简单的步骤：

1）随机提取一个规模为n的bootstrap样本（从训练数据集中有放回地随机选择n个样本）。

2）基于bootstrap样本生成决策树。在每个节点上完成以下的任务：

a. 不放回地随机选择d个特征。

b. 根据目标函数的要求，例如信息增益最大化，使用选定的最佳特征来分裂节点。

3）把步骤1和2重复k次。

4）聚合每棵树的预测结果，并以多数票机制确定标签的分类。在第7章中，我们将更详细地讨论多数票机制。

应该注意，在步骤2中训练单个决策树时，并不需要评估所有的特征来确定节点的最佳分裂方案，而是仅仅考虑其中的一个随机子集。

有放回抽样和不放回抽样

如果你对有放回抽样的概念不熟悉，那么可以通过一个简单的思考实验来说明。假设我们玩抽奖游戏，从一个罐中随机抽取数字。罐中有0、1、2、3和4五个独立的数字，每次抽一个。第一轮从罐中抽出某个数字的概率是1/5。如果不放回抽样，每轮抽奖后抽出的数字将不再放回罐中。因此，下一轮从剩余的数字中抽到某个数字的概率就取决于前一轮。例如，如果剩下的数字是0、1、2和4，那么在下一轮抽到0的概率将变成1/4。

然而，有放回抽样会把每次抽到的数字放回罐中，以确保在下一轮抽奖时，抽到某个数字的概率保持不变。换句话说，在有放回抽样时，样本（数字）是独立的，并且协方差为零。例如五轮随机数的抽样结果如下所示：

• 不放回随机抽样：2、1、3、4、0
• 有放回随机抽样：1、3、3、4、1

尽管随机森林的可解释性不如决策树好，但是其显著优势在于不必担心超参数值的选择。通常不需要修剪随机森林，因为集成模型对来自单个决策树的噪声有较强的抵抗力。实际上，唯一需要关心的参数是在步骤3中如何选择随机森林中树的数量k。通常，树越多，随机森林分类器的性能就越好，当然计算成本的增加也就越大。

虽然在实践中并不常见，但是随机森林分类器的其他超参数也可以被优化，我们可以用在第6章中将要讨论的技术进行优化。这些超参数分别包括步骤1 bootstrap样本的规模n和步骤2.a中每次分裂随机选择的特征数d。通过bootstrap样本规模n来控制随机森林的偏差-方差权衡。

因为特定训练数据被包含在bootstrap样本中的概率较低，所以减小bootstrap样本的规模会增加在单个树之间的多样性。因此，缩小bootstrap样本的规模可能会增加随机森林的随机性，这有助于降低过拟合。然而，较小规模的bootstrap样本通常会导致随机森林的总体性能较差，训练样本和测试样本之间的性能差别很小，但总体测试性能较低。相反，扩大bootstrap样本的规模可能会增加过拟合。由于bootstrap样本的存在，各个决策树之间会变得更相似，它们能通过学习更加紧密地拟合原始的训练数据集。

包括scikit-learn中的RandomForestClassifier实现在内，在大多数的随机森林实现中，bootstrap样本的规模一般与原始训练数据集样本的规模保持一致，这通常会有一个好的偏置-方差权衡。对于每轮分裂的特征数d，我们希望选择的值小于训练数据集的特征总数。在scikit-learn以及其他实现中，合理的默认值为，这里m为训练数据集的特征总数。

为了方便起见，我们并未从决策树本身开始构建随机森林分类器，因为scikit-learn已经实现了一个分类器可供我们使用：

执行前面的代码可以看到由随机森林中树的集成产生的决策区域，如图3-23所示。

通过设置参数n_estimators并用基尼杂质度作为准则来分裂节点，我们利用前面的代码训练了由25个决策树组成的随机森林。虽然在非常小的训练数据集上生长出来小规模随机森林，但是为了演示我们设置参数n_jobs，它使我们可以用多核计算机（这里是双核）来并行训练模型。