什么是决策树?

什么是决策树?

决策树是一种非参数监督学习算法,可用于分类和回归任务。它具有分层的树形结构,由根节点、分支、内部节点和叶节点组成。

从下图中可以看出,决策树从根节点开始,该节点没有任何传入分支。然后,来自根节点的传出分支馈送到内部节点,也称为决策节点。根据可用功能,两种节点类型都会开展评估以形成同质子集,这些子集用叶节点或终端节点表示。叶节点代表数据集内所有可能的结果。

举个例子,假设您正在尝试评估是否应该去冲浪,您可以使用以下决策规则来做出选择:

这种类型的流程图结构还能轻松表示决策过程,让组织中的不同群体都能更好地理解决策的原因。

决策树学习采用分而治之的策略,通过执行贪心搜索来识别决策树中的最佳分割点。然后,以自上而下的递归方式重复此分割过程,直到所有或大多数记录都被归类到特定的类标签下。

所有数据点是否都被归类为同质集合在很大程度上取决于决策树的复杂性。较小的决策树更容易获得纯净叶节点,即单个类中的数据点。然而,随着决策树规模的增大,维持这种纯度变得越来越困难,通常会出现指定子树内的数据过少的情况。这种情况被称为数据碎片,并且往往会造成过拟合

因此,决策树最好采用小树,这与奥卡姆剃刀中的简约原则一致;即,“如无必要,勿增实体”。换句话说,仅在必要时才增加决策树的复杂性,因为最简单的解释往往就是最佳解释。为了降低复杂性并防止过度拟合,决策树通常会采用修剪的方法;这是一个过程,用于去除依据重要性较低的特征分割出的分支。之后,可以通过交叉验证过程来评估模型的拟合度。

决策树保持准确性的另一种方法是通过随机森林算法构建集成;此分类器预测的结果更为准确,尤其是在个别树彼此不相关的情况下。

决策树类型

20 世纪 60 年代开发的 Hunt 算法用于在心理学中对人类学习进行建模,该算法成为了许多主流决策树算法的基础,比如以下算法:

- ID3:ID3 由 Ross Quinlan 提出,是“迭代二分法 3”的简称。该算法利用熵和信息增益作为评估候选分割的指标。Quinlan 自 1986 年以来对该算法的一些研究可在此处查看。

- C4.5:该算法被视为 ID3 的后期迭代版本,也是由 Quinlan 提出的。该算法可以使用信息增益或增益比来评估决策树中的分割点。

- CART:术语 CART 是“分类和回归树”的缩写,由 Leo Breiman 提出。此算法通常利用基尼系数来确定要分割的理想属性。基尼系数可衡量随机选择的属性被错误分类的频率。使用基尼系数进行评估时,值越低,表示越理想。

小球在轨道上滚动的三维设计

最新的 AI 新闻 + 洞察分析

在每周的 Think 时事通讯中,发现专家精选的有关 AI、云等的洞察分析和新闻。 

如何在每个节点上选择最佳属性

虽然可通过多种方法在每个节点上选择最佳属性,但信息增益和基尼系数这两种方法可以说是决策树模型的主流分割标准。它们有助于评估每个测试条件的质量以及将样本分类的能力。

熵和信息增益

如果不先讨论熵的概念,便很难解释何为信息增益。熵是源于信息论的一个概念,它可用于衡量样本值的不纯度。它可通过以下公式来定义,其中:

  • S 表示计算熵所用的数据集
  • c 表示集合 S 中的类
  • p(c) 表示属于 c 类的数据点占集合 S 中总数据点数量的比例

熵的值介于 0 和 1 之间。如果数据集 S 中的所有样本都属于一个类,则熵将等于零。如果一半的样本归类为一类,另一半样本归类为另一类,则熵将达到最高值 1。为了选择分割依据的最佳特征并找到最佳决策树,应使用熵量最小的属性。

信息增益表示依据给定属性进行分割之前和之后熵的差异。信息增益最高的属性将产生最佳分割,因为它在根据目标分类对训练数据进行分类方面表现最好。信息增益通常用以下公式表示,

其中

  • a 代表特定属性或类标签
  • Entropy(S) 是数据集 S 的熵
  • |Sv|/|S| 表示 Sv 中的值占数据集中值的数量 S 的比例。

让我们通过一个例子来加深对这些概念的理解。假设我们有以下任意数据集:

对于此数据集,熵为 0.94。这可以通过查找“打网球”为“是”的天数比例(即 9/14)和“打网球”为“否”的天数比例(即 5/14)来计算。然后,可以将这些值插入上面的熵公式中。

Entropy (Tennis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0.94

然后,我们可以单独计算每个属性各自的信息增益。例如,“湿度”属性的信息增益如下:

Gain (Tennis, Humidity) = (0.94)-(7/14)*(0.985) – (7/14)*(0.592) = 0.151

回顾一下,

- 7/14 表示湿度为“高”的值占湿度值总数的比例。在这种情况下,湿度为“高”的值的数量与湿度为“正常”的值数量相同。

- 0.985 是湿度为“高”时的熵

- 0.59 是湿度为“正常”时的熵

然后,对上表中的每个属性重复计算信息增益,并选择信息增益最高的属性作为决策树中的第一个分割点。在这种情况下,Outlook 产生的信息增益最高。此后,对每个子树重复这一过程。

基尼系数

基尼系数是指根据数据集的类分布标记数据集中的随机数据点时,对此随机数据点进行错误分类的概率。与熵类似,如果设置了 S,且 S 是纯净的,即属于同一类,则其系数为零。计算公式如下:

决策树的优点和缺点

虽然决策树可用于各种用例,但其他算法的性能通常优于决策树算法。即便如此,决策树对于数据挖掘和知识探索任务特别有用。我们将在下文进一步探讨使用决策树的主要优点和挑战:

优势

  • 易于解释:决策树的布尔逻辑和可视化表达方式使其更易于理解和使用。借助决策树的分层特性,人们还能轻松看出哪些属性最重要,而其他算法(如神经网络)并不总能清晰分辨出。

  • 几乎无需准备数据:决策树有许多特征,因而比其他分类器更灵活。决策树可以处理各种数据类型,例如离散或连续值,且连续值可以通过使用阈值转换为分类值。此外,决策树还可以在存在缺失值的情况下对值进行处理,其他分类器(如 Naïve Bayes)对此问题可能束手无策。

  • 更灵活:决策树既可用于分类任务,也可用于回归任务,因此比其他一些算法更加灵活。此外,决策树对属性之间的底层关系不太敏感;这意味着,如果两个变量高度相关,该算法将只选择其中一个特征进行分割。

缺点

  • 容易过度拟合:复杂的决策树往往会过度拟合,不能很好地概括新数据。可以通过前期修剪或后期修剪流程来避免这种情况。当数据不足时,前期修剪会让树停止生长,而后期修剪会在树构造完成后去除数据不足的子树。

  • 高方差估算器:数据中的微小差异也会产生截然不同的决策树。可以采用装袋法(或称估算值平均)来减少决策树的方差。不过,这种方法也存在局限性,可能会造成预测变量高度相关。

  • 成本更高:由于决策树在构建过程中采用贪心搜索方法,因此与其他算法相比,决策树的训练成本可能更高。
专家荟萃 | 播客

解码 AI:每周新闻摘要

加入我们的世界级专家团队,包括工程师、研究人员、产品负责人等,他们将穿透 AI 的喧嚣,为您带来最新的 AI 新闻和见解。

相关解决方案
IBM watsonx.ai

使用面向 AI 构建器的新一代企业级开发平台 IBM watsonx.ai,可以训练、验证、调整和部署生成式 AI、基础模型和机器学习功能。使用一小部分数据,即可在很短的时间内构建 AI 应用程序。

了解 watsonx.ai
人工智能 (AI) 解决方案

借助 IBM 业界领先的人工智能专业知识和解决方案组合,让人工智能在您的业务中发挥作用。

深入了解 AI 解决方案
AI 咨询与服务

通过增加 AI 重塑关键工作流程和运营,最大限度提升体验、实时决策和商业价值。

深入了解人工智能服务
采取后续步骤

一站式访问跨越 AI 开发生命周期的功能。利用用户友好型界面、工作流并访问行业标准 API 和 SDK,生成功能强大的 AI 解决方案。

深入了解 watsonx.ai 预约实时演示