从零学习:详解基于树形结构的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

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

开发 | 用卷积神经网络处理 “图” 结构数据应该怎么办?这篇文章告诉你答案

本文要介绍的这一篇 paper 是 ICML2016 上一篇关于 CNN 在图(graph)上的应用。ICML 是机器学习方面的顶级会议,这篇文章 --<<Le...

313120
来自专栏MyBlog

利用双向注意流进行机器理解

本文基于Bi-Directional Attention Flow For Machine Comprehension一文

13130
来自专栏SIGAI学习与实践平台

卷积神经网络的压缩和加速

我们先来看看当前深度学习平台中,卷积层的实现方式,其实当前所有的深度学习平台中,都是以矩阵乘法的方式实现卷积的(如图1左侧):

1.1K80
来自专栏量化投资与机器学习

【Python机器学习】系列之线性回归篇【深度详细】

谢谢大家的支持!现在该公众号开通了评论留言功能,你们对每篇推文的留言与问题,可以通过【写评论】给圈主留言,圈主会及时回复您的留言。 本次推文介绍用线性模型处理回...

1.2K90
来自专栏SIGAI学习与实践平台

网络表征学习综述

当前机器学习在许多应用场景中已经取得了很好的效果,例如人脸识别与检测、异常检测、语音识别等等,而目前应用最多最广泛的机器学习算法就是卷积神经网络模型。但是大多应...

53230
来自专栏AI研习社

用卷积神经网络处理 “图” 结构数据应该怎么办?这篇文章告诉你答案

本文要介绍的这一篇 paper 是 ICML2016 上一篇关于 CNN 在图(graph)上的应用。ICML 是机器学习方面的顶级会议,这篇文章 --<<Le...

40090
来自专栏专知

吴恩达高徒语音专家Awni Hannun:序列模型Attention Model中的问题与挑战

【导读】注意力模型(Attention Model)被广泛使用在自然语言处理、图像识别及语音识别等各种不同类型的深度学习任务中,是深度学习技术中最值得关注与深入...

50960
来自专栏技术随笔

[译] End-to-end people detection in crowded scenes

39860
来自专栏程序员Gank

神经网络和深度学习(吴恩达-Andrew-Ng):一二周学习笔记

机器学习: 机器学习研究的是计算机怎样模拟人类的学习行为,以获取新的知识或技能,并重新组织已有的知识结构使之不断改善自身。简单的说,就是计算机从数据中学习规律和...

95010
来自专栏决胜机器学习

神经网络和深度学习(二) ——从logistic回归谈神经网络基础

神经网络和深度学习(二)——从logistic回归谈神经网络基础 (原创内容,转载请注明来源,谢谢) 一、概述 之前学习机器学习的时候,已经学过logisti...

50670

扫码关注云+社区

领取腾讯云代金券