决策树是一种非参数监督学习算法,可用于分类和回归任务。它具有分层的树形结构,由根节点、分支、内部节点和叶节点组成。
从下图中可以看出,决策树从根节点开始,该节点没有任何传入分支。然后,来自根节点的传出分支馈送到内部节点,也称为决策节点。根据可用功能,两种节点类型都会开展评估以形成同质子集,这些子集用叶节点或终端节点表示。叶节点代表数据集内所有可能的结果。
举个例子,假设您正在尝试评估是否应该去冲浪,您可以使用以下决策规则来做出选择:
这种类型的流程图结构还能轻松表示决策过程,让组织中的不同群体都能更好地理解决策的原因。
决策树学习采用分而治之的策略,通过执行贪心搜索来识别决策树中的最佳分割点。然后,以自上而下的递归方式重复此分割过程,直到所有或大多数记录都被归类到特定的类标签下。
所有数据点是否都被归类为同质集合在很大程度上取决于决策树的复杂性。较小的决策树更容易获得纯净叶节点,即单个类中的数据点。然而,随着决策树规模的增大,维持这种纯度变得越来越困难,通常会出现指定子树内的数据过少的情况。这种情况被称为数据碎片,并且往往会造成过拟合。
因此,决策树最好采用小树,这与奥卡姆剃刀中的简约原则一致;即,“如无必要,勿增实体”。换句话说,仅在必要时才增加决策树的复杂性,因为最简单的解释往往就是最佳解释。为了降低复杂性并防止过度拟合,决策树通常会采用修剪的方法;这是一个过程,用于去除依据重要性较低的特征分割出的分支。之后,可以通过交叉验证过程来评估模型的拟合度。
决策树保持准确性的另一种方法是通过随机森林算法构建集成;此分类器预测的结果更为准确,尤其是在个别树彼此不相关的情况下。
20 世纪 60 年代开发的 Hunt 算法用于在心理学中对人类学习进行建模,该算法成为了许多主流决策树算法的基础,比如以下算法:
- ID3:ID3 由 Ross Quinlan 提出,是“迭代二分法 3”的简称。该算法利用熵和信息增益作为评估候选分割的指标。Quinlan 自 1986 年以来对该算法的一些研究可在此处查看。
- C4.5:该算法被视为 ID3 的后期迭代版本,也是由 Quinlan 提出的。该算法可以使用信息增益或增益比来评估决策树中的分割点。
- CART:术语 CART 是“分类和回归树”的缩写,由 Leo Breiman 提出。此算法通常利用基尼系数来确定要分割的理想属性。基尼系数可衡量随机选择的属性被错误分类的频率。使用基尼系数进行评估时,值越低,表示越理想。
虽然可通过多种方法在每个节点上选择最佳属性,但信息增益和基尼系数这两种方法可以说是决策树模型的主流分割标准。它们有助于评估每个测试条件的质量以及将样本分类的能力。
如果不先讨论熵的概念,便很难解释何为信息增益。熵是源于信息论的一个概念,它可用于衡量样本值的不纯度。它可通过以下公式来定义,其中:
熵的值介于 0 和 1 之间。如果数据集 S 中的所有样本都属于一个类,则熵将等于零。如果一半的样本归类为一类,另一半样本归类为另一类,则熵将达到最高值 1。为了选择分割依据的最佳特征并找到最佳决策树,应使用熵量最小的属性。
信息增益表示依据给定属性进行分割之前和之后熵的差异。信息增益最高的属性将产生最佳分割,因为它在根据目标分类对训练数据进行分类方面表现最好。信息增益通常用以下公式表示,
其中
让我们通过一个例子来加深对这些概念的理解。假设我们有以下任意数据集:
对于此数据集,熵为 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 是纯净的,即属于同一类,则其系数为零。计算公式如下:
虽然决策树可用于各种用例,但其他算法的性能通常优于决策树算法。即便如此,决策树对于数据挖掘和知识探索任务特别有用。我们将在下文进一步探讨使用决策树的主要优点和挑战:
IBM Granite 是我们开放式、性能优异、值得信赖的 AI 模型系列,专门为企业量身定制,并经过优化,可以帮助您扩展 AI 应用程序。深入了解语言、代码、时间序列和护栏选项。
我们对 2,000 家组织进行了调查,旨在了解他们的 AI 计划,以发现哪些方法有效、哪些方法无效,以及如何才能取得领先。
深入探讨监督学习方法,如支持向量机和概率分类器。
学习基本概念并通过亲手实验、课程、指导项目、试用等方式培养您的技能。
了解如何为您的用例选择最合适的 AI 基础模型。