决策树学习综合指南

决策树是最广泛使用的监督式机器学习算法之一 (已标记的数据集)进行归纳推理。决策树学习是一种近似离散值目标函数的方法,其中在训练过程中学习的函数由决策树表示。学到的树也可以表示为嵌套的if-else规则,以提高人们的可读性。

目录:

  1. 介绍
  2. 直觉
  3. ID3算法
  4. 最佳分类器是哪个属性?
  5. 信息增益
  6. 信息增益比
  7. 实值数据的决策树
  8. 决策树回归
  9. 偏差偏差权衡
  10. 避免在决策树中过度拟合
  11. 时空复杂度
  12. 决策树的利与弊

1.简介:

决策树学习用于分类,回归通常分别称为分类树和回归树。期限 分类和回归树(CART) 分析用于引用这两个任务。决策树学习应用于从学习到诊断医疗案例到学习获得贷款申请人的信用风险的广泛任务。

 

2.直觉: 

AI Time Journal资源
您正在学习数据科学吗?

Check out what 图书 帮助20多个成功的数据科学家成长。

每当我们在做出某个决定之前问自己一个问题时,决策树算法就像人的大脑一样工作。例如,是否正在网上购物进行折扣优惠?如果是,那么我将购买产品,否则我将不购买。

在整个本文中,我们将使用机器学习世界中一个著名的数据集,称为天气数据集。数据集具有4个特征,即日,展望,湿度,风和一个分类的输出变量y(是或否)。

从以上的14个实例中,我们需要学习X和Y之间的映射(哪个机器学习总是执行),并想基于新的特征向量(X)预测约翰是否会打网球?

决策树采用训练集,并根据特征将其分成较小的子集。我们在具有不同子集和属性的树的每个节点上重复此过程,直到不确定约翰是否会扮演角色为止?

当出现新的数据点时,我们只需查看该点属于哪个子集中,然后将一个点分类到该类中即可。

假设我们使用Outlook属性分割数据集。 Outlook具有3种可能的值,即晴天,阴天和雨天。因此,我们将数据集分为3个较小的子集,如下所示:

在拆分Outlook属性后,我们有了John始终在其中播放的一个纯节点。因此,从直觉上讲,我们可以说,当Outlook被覆盖时,John总是在播放。

另一方面,我们有2个不纯净的组合,即在那些子集中,我们不知道约翰会不会参加比赛?对于那些子集,需要进一步拆分。假设将Sunny作为Outlook的子集,我们采用Humidity并将其进一步拆分,则树如下所示:

现在我们有2个纯子集和1个不纯子集。当阳光明媚,湿度高时,约翰不会上场,而在正常湿度下,约翰会上场。

对于多雨的子集,由于它不是纯子集,因此我们将基于Wind进行进一步拆分。

在这一点上,我们已经根据一小套规则将整个训练集划分为较小的子集,并且每个子集都是纯的,即在John参与或不参与的所有子集中。

用标签替换实例后的最终决策树如下所示:

到目前为止,我们已经讨论过的数据集说明了决策树作为数据结构确切产生了什么。

 

3. ID3算法:

ID3(迭代二分器)是Ross Quinlan发明的一种递归算法。 ID3算法的中心选择是选择要在树中的每个节点上测试的属性。我们想选择对示例分类最有用的属性。什么是对属性价值的好的定量度量?稍后,我们将定义一个统计信息属性,称为信息增益,该属性测量给定属性根据训练样本的目标分类将训练样本分开的程度。

ID3使用此信息增益度量来在生长树的每一步中从候选属性中进行选择。

 

ID3算法的伪代码:

参数:

  1. 示例:这是培训示例。
  2. Target_Attribute:这是其值将由树预测的属性。
  3. 属性:这是可以由学习的决策树测试的其他属性的列表。

ID3(示例,Target_Attribute,属性)

{

  1. 创建树的根节点。
  2. 如果所有示例均为正,则返回带有标签的单节点树根为正。
  3. 如果所有示例均为负数,则返回带有标签的单节点树根为负数。
  4. 否则,开始:

4.1. A ←属性中对示例进行最佳分类的属性

4.2。对于A中的每个可能值Vi

4.2.1。在根下方添加一个新的树枝,对应于测试A = Vi

4.2.2. 让 Vj be the subset of examples that have value Vi

4.2.3。如果Vj为空: 添加带有标签的新叶节点作为Target_Attribute的最常用值 in Examples.

4.2.4。其他

ID3 (Vj,Target_Attribute,属性– {A})

返回根。

}

 

4.哪个属性是最好的分类器:

我们真的可以选择任何属性将其划分为训练数据,这将导致数据的不同分区。那么,我们如何确定一个数据分区比另一个分区更好呢?

 

让我们以原始数据集为例,我们得到9是和5否。现在,我们可以如下图所示拆分Outlook或Humidity。

以上2个分割之间有什么区别?

如果我们在Outlook上拆分,则最终得到3个子集,其中一个是纯子集。另一方面,如果将其拆分,湿度将得到2个子集,其中没有一个是纯子集。

仅通过查看上面的分割,您更喜欢哪个分割?

可以直观地说,Outlook比湿度更好,因为它只有一个纯子集。

如果我们查看湿度的两个子集,那么即使它不是完全纯净的,直觉上正常也比高更好。

所以我们想要的决策树是 分裂使我们的子集严重偏向正负 。因为在该子集中存在任何一个类的许多实例,这告诉我们我们将要预测的内容,即使其中有一些类的要点。

如果我们在子集中有完美的平衡点,那么我们不知道我们要预测什么?

因此,我们需要采取某种措施来确定子集的纯度。

 

5.熵:

熵是数据中存在的不确定性量。在拆分之前,我们不确定哪些点是正的,哪些点是负的。但是在分裂之后,我们更加确定。如果我们有纯子集,那么我们完全可以确定,如果我们有50-50%,那么我们就完全不确定该分割中的点。

因此从直觉上讲,我们可以说熵应该尽可能小。

yi是一个o / p变量,可能有k个情况。

请注意,熵是针对特定子集计算的,因此p(yi)是yi属于该特定子集而不是整个数据集的概率。

让 yi∈{0,1}

情况1: 如果我们有50%的几率是0以及1。

 

情况2: 如果我们有完全纯集,即说4是和0否。

 

6.信息获取:

熵仅针对一个子集计算,对于每个节点,我们有多个子集。因此,我们将取每个子集的熵的平均值。

其中v =属性A的可能值

S =拆分前的示例集

Sv = XA等于v的子集

 

简而言之,信息增益(IG)是在分裂之前和分裂之后可能的A值之间的熵之差。”

我们将拆分后的熵乘以| Sv | / | S |其中Sv是属性A中可能值的数量,S是拆分之前的值数量。

通过这样做,我们为较大的子集赋予较高的权重,为较小的子集赋予较低的权重。因为在较小的子集中,如果只有一个实例,则可以保证它属于该类之一,但是对于较大的子集,情况是不同的。

让’s以天气数据集来说明信息获取。

我们将Wind属性视为分裂数据集的根节点。下图显示了风分割前后的计算结果。

 

因此,根节点上的属性Wind的信息增益为0.04。

我们如何使用该增益来确定哪个属性更好?

因此,我们选择具有最大IG的属性。在根节点,我们为所有属性计算IG,并取一个IG最大值。除了先前选择的属性外,我们对所有节点重复相同的过程。

 

7.信息增益比:

信息获取是一个很好的衡量标准,但它有一些我们需要理解的缺陷。

如果我们将数据集拆分为Day属性,则以单例子集结束。那就是约翰在每一天都会参加或不参加。

就IG而言,日子是最好的选择。因为魔术只能将单个属性拆分为不同的子集。

通常,有一些具有很多值的属性,这些属性导致非常小的子集。此属性通常不适用于测试。

因此,我们可以使用如下计算的IG比率代替IG。

 

因此,简而言之,我们通过分裂熵对信息增益进行归一化。

8.实值数据的决策树:

到目前为止,我们已经在具有分类值的属性上构建了树。但是,如果我们一直重视数据呢?

因此,针对实值属性的决策树会选择一些阈值,因为它将对数据进行分区。因此,基于属性的条件,我们拆分了数据。分割数据后,我们重复进行与分类数据相同的计算信息增益的过程。

唯一需要做的额外工作就是找到所有可能的阈值,这非常昂贵。但是,如果我们选择正确的数据结构来找到阈值,那么它并不昂贵。

关于实值数据的一件有趣的事情是,我们最终可能会不止一次地拆分一个属性。

 

9.决策树回归:

在回归过程中,我们将计算真实值而不是将点分类到一个类。

与计算信息增益不同,我们计算方差并尝试将其最小化。因此,我们根据属性将数据分为多个子集,并以最小的方差选取了一个子集。

在测试时,我们到达特定的叶子节点,并对该子集中所有点取平均值,然后将平均值分配给该测试点。

 

10.偏差偏差权衡:

树的深度是造成偏差变化的原因。

1. 到目前为止,我们已经拆分了数据,直到获得纯节点。如果我们将精度图看成是树的大小的函数,则将如下所示。

我们可以清楚地看到,该模型在训练数据上表现良好,但在测试数据上,准确性突然下降到较小的值。因此,在此情况下,我们可能会过度拟合。

2. 如果树的深度太小,则可能不适合。

 

11.避免在决策树中过度拟合:

避免过度拟合DT意味着在成长树对训练数据变得过于具体之前停止进一步生长。有两种避免在DT中过拟合的方法:

  1. 预修剪
  2. 修剪后

1预修剪: 在预修剪中,它会尽早停止树木的建造。如果节点的优劣程度(即低于阈值),它将停止拆分节点。但是,选择适当的阈值是完全不可行的。

 

2.修剪后: 在修剪后,我们将训练数据分为两部分。从我们称为交叉验证的算法中完全隐藏数据的一部分,并训练完整的决策树,直到获得叶节点。

现在,取出验证集并在学习的树上进行测试,由于模型过拟合,因此不会给出100%的准确性。在此之后,对于树中的每个非叶节点,我们会暂时修剪该节点并将其替换为多数类。再次在修剪的树上测试验证集,我们将获得另一个准确性。对每个非叶节点重复相同的过程,并记录验证准确性,并修剪一棵树,这将对验证数据提供最高的准确性。

伪代码:

1.将火车数据分为两部分。

  1. 在火车数据上构建完整的树。
  2. 直到交叉验证的准确性提高为止

{

对于每个非叶节点

  1. 暂时修剪并以多数票取代。
  2. 在CV数据上测试模型的准确性。
  3. 永久修剪CV上的精度最高的节点。
    }

 

12.时间和空间的复杂性:

培训阶段:

T(n)= O(nlogn * m)

其中m =特征数量

测试阶段:

S(n)=嵌套if-else条件的脚本

 S(n)= O(总节点数)

T(n)= O(深度)

 

13.决策树的利与弊:

优点: 

  1. DT是if-else的序列,对人类高度解释。
  2. 它可以轻松处理不相关的属性。
  3. DT自动进行多类分类。
  4. 一旦构建了DT,它就会在测试时变得非常快。
  5. DT非常紧凑。

缺点:

  1. 决策树可能不会总是找到最好的树,因为它使用贪婪的方法来构建树。
  2. 对于每个大尺寸数据,训练时间都很高。
  3. DT仅为实值属性形成轴平行超平面。

相关文章:

  1. 强化学习变得容易
  2. XGBoost分类和功能选择简介

贡献者

皮莱工程学院|机器学习爱好者

贡献者表达的观点是他们自己的观点。

关于阿克沙伊·查万(Akshay Chavan)

皮莱工程学院|机器学习爱好者

查看Akshay Chavan发表的所有帖子→