从零学习：详解基于树形结构的ML建模——决策树篇

来源：Analytics Vidhya

编译：Bot

编者按：通常，我们会把基于树形结构的学习算法认为是最好的、最常用的监督学习方法之一。树能使我们的预测模型集高精度、高稳定性和易解释于一身，与线性模型不同，它能更好地映射非线性关系，适用于解决分类或回归等任何问题。

谈及基于树的学习算法，决策树、随机森林、gradient boosting等是现在被广泛应用于各种数据科学问题的一些方法。本文旨在帮助初学者从头开始学习基于树形结构进行建模，虽然没有机器学习知识要求，但仍假设读者具备一定的R语言或Python基础知识。

“从零学习”系列第3篇“详解基于树形结构的ML建模（R & Python）——决策树篇”，来自知名印度数据科学网站Analytics Vidhya的内容团队。

目录

决策树及其工作原理

回归树VS分类树

决策树如何分裂

模型建立的关键参数及如何避免过拟合

决策树VS线性模型

用R和Python使用决策树

决策树及其工作原理

决策树是一种主要用于分类问题的监督学习算法（需要预定义目标变量），它可以用来分类，也可以基于连续输入预测输出。它表示对象属性和对象值之间的一种映射，树中的每一个节点表示对象属性的判断条件，其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果。

让我们举个例子。假设我们有一个包含30名学生的样本，其中有15人会在闲暇时间玩板球，已知学生的3个属性变量：性别（男/女）、班级（四班/五班）和身高（5—6英尺）。现在，创建一个模型来预测谁会在休息时间打板球。

在这个问题中，我们要做的是根据提供的这三个变量分析学生的课余生活，它们之间的关系是非线性的，因此相比线性模型，决策树的适用性被充分体现了出来。下图是基于三个输入变量的三棵简单的树，乍看之下，这三种分法并没有高下区别。

那决策树是如何判断变量的重要程度的？它又是怎么进行分裂的呢？在探究其中的算法前，我们先来了解一下决策树的类型。

决策树的类型

决策树的类型取决于我们拥有的目标变量的类型。它可以被分为两类：

分类变量决策树（分类树）：当决策树的目标变量是类别时（输出的是样本的类标），它就是分类（离散）变量决策树。如在上述例子中，决策树的目标变量是“学生玩不玩板球”，它的答案是“是”和“否”，所以是分类的。

连续变量决策树（回归树）：当决策树的目标变量是一系列的连续的变量时（输出的是一个实数），它就是连续变量决策树。

假设我们要建立一个模型来预测用户是否还得起贷款（是/否），已知用户的属性——是否已婚、是否有车、收入情况是三个非常重要变量，这时它是一个分类变量决策树。但是，如果我们不知道用户的收入情况，但因为这个变量很重要，我们需要根据他的职业、购买的产品和其他各种变量建立一棵决策树来预测收入细节，它的输出是一个数，那么这就是一个连续变量决策树。

决策树相关重要术语

我们来看一下决策树会涉及的一些基本术语：

根节点：代表整个群体或样本，可以被进一步分为两个或两个以上的同类集合；

分裂（Splitting）：将节点分成两个或两个以上子节点的过程；

决策节点：当一个子节点分裂成更多的子节点时，它就是决策节点；

叶子（终端）节点：不能再进行分裂的节点被称为叶子（终端）节点；

剪枝：当我们删除决策节点的子节点时，这一过程被称为剪枝，你也可以把它理解过分裂的反过程；

分支/子树：整棵树的子部分被称为分支或子树；

父节点和子节点：除根节点外每个节点都有父节点，若一个节点拥有子节点，那它就是这些子节点的父节点，而同一父节点的的子节点被称为同胞。

决策树的优点

容易理解：这是一种非常直观的图形表示，即使是没有数学分析背景，甚至是没有统计学基础的人，都能轻松将它和自己的假设联系起来；

可用于数据挖掘：决策树是挖掘多个变量中最重要的变量及其中关系的最快方法之一。在决策树的帮助下，我们可以创建新的变量/函数来预测目标变量；

较少的数据清洗要求：和其他建模方法相比，决策树对数据清洗的要求较低，因为无效值和缺失值对它的决策没有影响；

可处理多种数据类型：适用于数值型和标称型数据；

非参数方法：决策树是一种非参数方法，这意味着它没有关于空间分布和分类器结构的假设。

决策树的缺点

过拟合：过拟合是决策树模型最实际的难点之一，它可以通过设置模型参数和剪枝来解决；

不适合连续变量：在处理连续的数值变量时，决策树在对不同类别的变量进行分类时可能会丢失信息。

回归树VS分类树

我们都知道，叶子节点位于决策树底部，这就意味着决策树其实是一棵颠倒的“树”，如下图所示：

根据数据类型，我们可以把决策树分成回归树和分类树，它们的工作原理其实几乎相同，这里我们来分析一下其中的差异和相似性：

因变量为连续的值时，用回归树；因变量为分类时，用分类树；

使用回归树时，叶子节点的输出是落在该区域训练数据观察值的均值。因此，如果有一个未知的数据观察值落进该区域，我们会根据均值计算它的预测值；

使用分类树时，叶子节点的输出是落在该区域训练数据观察值所属的类别。因此，如果同样有一个未知观察值落进该区域，那我们预测的是它属于某一类别的概率；

回归树和分类树都会把预测空间（自变量）分成几个不同的、不重叠的子集；

回归树和分类树都遵循自上而下的贪婪方法，称为递归二元分裂。我们把这称为是“自上而下”的，因为当所有数据都被集中在一起时，它从树的顶端开始连续不断地把变量空间分裂成多个分支。另外，由于算法只关心在当前位置找到最重要的变量，而不会基于未来步骤采取更好的分裂方法，因此它是贪婪的；

它们的分裂过程是人为可控的，会在用户定义的位置停止分裂。例如，我们设每个节点的观察值数量不低于50，那算法会在每个节点只有50个观察值时停止分裂；

回归树和分类树在到达用户定义的停止位置前会持续分裂，但是完全分裂的树会出现过拟合的问题。

决策树如何分裂

决策树的分裂过程决定了模型预测的准确性，对于回归树和分类树，它们的分类方法不尽相同。

决策树的分裂涉及多种算法，它们会判断如何将一个节点分成两个或多个子节点。这种多子节点的分裂方法有助于提高下一代子节点的同质化水平，换句话说，就是提高了下一代子节点相对于目标变量的纯度（纯度越高，包含信息越少，不确定性越低）。根据算法的工作原理，决策树先是对所有可用变量进行分裂，然后再对更重要的变量子节点做一轮又一轮的分裂。

分裂用到的各种算法也可根据目标变量类型进行划分，以下是4种决策树中常用的算法：

基尼系数（Gini Index）

基尼系数是一个统计学概念，它常被用来判断收入分配公平程度。在决策树中，它表示的是模型的不纯度。基尼系数越小，不纯度越低，特征值越多。如果我们随机从一个集中抽取两个样本，那它们应该拥有同样的特征和概率，如果这个集的纯度很高，那它的基尼系数就接近1。

基尼系数适用于分类目标变量：“Success” 和 “Failure”；

（在CART树中）它只执行二元分裂（二叉树）；

基尼系数值越高，同质化水平越高；

CART（分类和回归树）可使用基尼系数做二元分裂。

基尼系数分裂步骤：

利用概率值的平方求和公式：p^2+q^2，计算子节点的基尼系数；

利用每个子节点基尼系数加权后的值计算整个分裂的基尼系数。

例：在学生打板球这道题中，我们想根据目标变量（打不打板球）进行分类。如下图所示，我们选取了输入变量为性别和班级的两棵树，通过计算基尼系数判断哪种分裂产生了分布更加均匀的子节点。

性别组：

计算子节点“女生”的基尼系数：0.2×0.2+0.8×0.8=0.68；

计算子节点“男生”的基尼系数：0.65×0.65+0.35×0.35=0.545；

计算二叉树的加权基尼系数：(10÷30)×0.68+(20÷30)×0.545≈0.59。

班级组：

计算子节点“四班”的基尼系数：0.43×0.43+0.57×0.57≈0.51；

计算子节点“五班”的基尼系数：0.56×0.56+0.44×0.44≈0.51；

计算二叉树的加权基尼系数：(14÷30)×0.51+(16÷30)×0.51≈0.51。

从上述计算结果可以看出，性别组的基尼系数比班级组更高，也就是纯度更高，因此决策树会根据性别进行分裂。

卡方检验（CHAID）

卡方分布是概率论与统计学中常用的一种概率分布，它计算的是子节点与父节点之间差异的统计意义，即实际观察值与理论推断值之间的偏离程度，这个偏离程度决定了卡方值的大小，卡方值越大，偏离程度越大；卡方值越小，偏差越小；若两个值完全相等，卡方值就为0，表明理论值完全符合。

在统计学中，若n个相互独立的随机变量均服从标准正态分布，那这些变量的平方和能构成一个新的随机变量。我们可以利用这个思路计算目标变量观察值和理论推断值的差异。

卡方检验适用于分类目标变量：“Success” 和 “Failure”；

它可以执行二元分裂或多元分裂；

卡方值越高，子节点、父节点的偏离程度越高；

我们可以用公式计算每个节点的卡方；

卡方公式：卡方值=((实际值-理论值)^2/理论值)^1/2；

卡方检验分裂步骤：

它处理的是分类问题，所以可以通过计算各概率的差异来得出节点的卡方值；

利用每个子节点的卡方值计算分裂的卡方值。

例：同样是上面的例子，计算性别和班级的卡方值。

性别组：

首先我们要为子节点“女生”补充“玩板球”和“不玩板球”的实际值，分别是2人和8人；

计算“玩板球”和“不玩板球”人数的期望值（理论推断值）。因为父节点的概率是50%（15/30），所以我们期望有5人；

计算差值：实际值-理论值。“玩板球”：2-5=-3；“不玩板球”：8-5=3；

用公式计算卡方值（如下表所示）。

用相同的方法计算子节点“男生”的卡方值；

求和计算分裂的卡方值。

班级组：

4.58>1.46，用卡方检验算法得出的结论也是按性别分裂比按班级分裂效果更好。

信息增益（Information Gain）

下面是决策树的三个节点，它们中的哪个节点更容易描述呢？很显然，第3个，因为它所有的值都是相似的，包含的信息量少。而B节点相较于C拥有更多的信息描述，A则是最多的。换句话说，C的纯度最高，B其次，A最不纯。

现在我们可以得出这样一个结论：纯度高的节点包含更少的信息量，而纯度低的节点包含更多的信息量。

信息熵衡量的是数据的不确定度。如果样本是完全均匀的，那熵就是0；如果样本是等分的，那熵就是1。它可以用如下公式计算：

其中p和q分别是该节点分类（“Success” 和 “Failure”）的概率。信息熵也可用于分类目标变量，它的思路是选择和父节点和其他分裂方法相比熵值最低的那个树。结合上图可知，熵越小，样本越均匀，信息含量越少，节点纯度越高。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。

信息增益分裂步骤：

计算父节点的熵；

计算分裂后每个子节点的熵，并进行加权平均。

例：让我们继续计算学生玩不玩板球。

父节点的熵：-(15÷30) log2 (15÷30) – (15÷30) log2 (15÷30) =1。这是一个等分的节点（一半人玩板球，一半人不玩板球）；

子节点“女生”的熵：-(2÷10) log2 (2÷10) – (8÷10) log2 (8÷10) =0.72；

子节点“男生”的熵：-(13÷20) log2 (13÷20) – (7÷20) log2 (7÷20) =0.93；

性别组的熵=子节点加权熵：(10÷30)×0.72 + (20÷30)×0.93=0.86；

子节点“四班”的熵：-(6÷14) log2 (6÷14) – (8÷14) log2 (8÷14)=0.99；

子节点“五班”的熵：-(9÷16) log2 (9÷16) – (7÷16) log2 (7÷16) = 0.99；

班级组的熵：(14÷30)×0.99 + (16÷30)×0.99=0.99。

性别组的熵比班级组低，纯度高，因此决策树会按性别分裂，而它的信息增益=1-0.86=0.14。

减少方差

上述3种算法都是针对分类树的分裂方法，在这里，我们再介绍一种用于连续目标变量（回归问题）的算法。这种算法用方差公式选择最佳分裂方法。方差越小，方法越好。

上式中，X拔是平均值，X是实际值，n是样本数量。

减少方差分裂步骤：

计算每个节点的方差；

计算这些方差的加权平均值，并作为分裂的方差。

例：我们设玩板球为1，不玩板球为0，现在按以下步骤来进行计算：

根节点方差：平均值=(15×1+15×0)÷30=0.5；方差=((1-0.5)^2+(1-0.5)^2+……+(0-0.5)^2+(0-0.5)^2+……)÷30=(15×(1-0.5)^2+15×(0-0.5)^2)÷30=0.25；

子节点“女生”的方差：平均值=(2×1+8×0)÷10=0.2；方差=(2×(1-0.2)^2+8×(0-0.2)^2)÷10=0.16；

子节点“男生”的方差：平均值=(13×1+7×0)÷20=065；方差=(13×(1-0.65)^2+7×(0-0.65)^2)÷20=0.23；

性别组方差：(10÷30)×0.16 + (20÷30)×0.23=0.21；

子节点“四班”的方差：平均值= (6×1+8×0)÷14=0.43，方差= (6×(1-0.43)^2+8×(0-0.43)^2)÷14= 0.24；

子节点“五班”的方差：平均值=(9×1+7×0)÷16=0.56，方差=(9×(1-0.56)^2+7×(0-0.56)^2)÷16 = 0.25；

班级组方差：(14÷30)×0.24+(16÷30)×0.25=0.25。

和父节点方差值相比，性别组方差更小，所以分裂方法更优。

截至目前，我们已经掌握了决策树的基础知识，以及如何计算决策树的最佳分裂。现在，我们将进一步学习它在分类、回归问题上的具体应用。

模型建立的关键参数及如何避免过拟合

如果说决策树有什么缺点，那过拟合一定是其中最突出的问题。建立决策树模型时，如果我们没有合理限制、调整决策树的生长，而是放任它自由分裂的话，那它将会过度学习训练集中的知识，使结果完全拟合训练数据，不再适用于其他所有数据。因为在最糟糕的情况下，决策树会为每个观察值都分裂一个叶子节点。因此，建模决策树时防止过拟合是重中之重，它一般有两种解决办法：

限制决策树大小；

剪枝。

让我们来简要介绍一下它们。

限制决策树大小

这可以通过定义决策树的各项超参数来完成。首先，如下图所示，让我们来看看决策树的一般结构：

图中的这些超参数都与工具无关，在R语言和Python中，它们都是现成的，我们要了解的是它们在决策树中的作用（表格中部分内容引自刘建平blog www.cnblogs.com/pinard/p/6056319.html，侵删）：

更多超参数，可访问博客地址查看。

剪枝

如前所述，定义超参数利用的还是算法的贪婪性，换句话说，就是决策树会不断计算最佳的分裂方法进行生长，直至抵达终止条件。为了更形象，我们可以举一个开车的例子：

已知同一方向有两条车道，一条车道上排列着以80km/h速度行驶的绿色轿车，另一条则排着两辆以30km/h速度形式的卡车。这时，如果你驾驶的是图中的黄车，你会怎么开？是继续直行，还是换车道跟在卡车后面。

让我们分析一下这两个选择。如果你选择换车道，那你能马上加速超过原本排在前面的两辆绿车，而原本排在你后面的那些车就都能上前一个车位。假设你的目标是在几秒内前进最大的距离，这种方法确实更优。如果你选择继续直行，那你在短时间内就能超过卡车，至于怎么超过前面的车，这取决于之后的路况。

这正是常规决策树和剪枝决策树之间的区别。一棵简单受限的决策树看不到前面的卡车，它会贪婪地向右变线超车。而经过剪枝的决策树则“目光”更加长远。所以剪枝其实比设置超参数的效果更好，它也是防止决策树过拟合的主流方法。

一般情况下，我们会把剪枝分为预剪枝（pre-pruning）和后剪枝（post-pruning）。其中前者是在决策树的构建过程中同时进行的，我们需要预先定义一个阈值，当分裂的信息增益小于阈值时，决策树会通过剪枝停止生长。而后剪枝是一种更高效的方法，它的实现思路主要有3步：

定义决策树的最大深；

从底向上删除一些相对于父节点信息增益为负的叶节点；

假设一个分裂的信息增益为-10，但它产生的下一个分裂的信息增益为20，这是决策树会删除其子树，并保留为一个集合了所有信息的叶节点：+10。

剪枝前 来源：IBM

剪枝后 来源：IBM

决策树VS线性模型

如果我们能用logistic regression算法解决所有分类问题，能用线性回归解决所有回归问题，那学习决策树意义何在？相信很多已经接触过线性模型的读者会有这个疑问，事实上，这是个好问题。

在用机器学习算法解决问题的过程中，其实你可以随意选择算法，只要它们有效就可以了。而选择算法的关键在于你正在解决的问题类型，以下是一些小建议：

如果自变量和因变量的关系可用线性模型近似表达，那线性模型整体效果比决策树、随机森林等树形结构模型更优；

如果自变量和因变量的关系是非线性的，甚至是高度复杂的，那树形结构模型性能更好；

如果你要构建一个易于解释的模型，那决策树会是首选。

用R和Python使用决策树

最后是我们的代码环节。以下只是一些标准代码块，如果要使用到自己的模型中，记得修改变量名称。

对于R语言开发者，ctree、rpart、tree等都是一些可用来实现决策树的工具包。

在上面的代码中：ytrain表示因变量；xtrain表示自变量；x表示训练数据。

对于Python开发者：

在下一篇文章中，我们将继续学习基于树形结构的建模方法，学习另一种广泛应用的树型算法——随机森林。

原文地址：www.analyticsvidhya.com/blog/2016/04/complete-tutorial-tree-based-modeling-scratch-in-python/

参考文献：

IBM DeveloperWorks：www.ibm.com/developerworks/cn/analytics/library/ba-1507-decisiontree-algorithm/index.html

刘建平pinard博客：www.cnblogs.com/pinard/p/6056319.html