初识决策树算法

原文链接:Classification And Regression Trees for Machine Learning
决策树在预测性的建模机器学习中是一个非常重要的算法类型。经典的决策树算法已经发展了几十年,一些比较近代的变种(例如,随机森林)已经成为了目前最强有力的技术之一。

在本篇博客中,我们将会了解决策树算法——或者一个更加现代的名称:CARTClassification And Regression Tree,分类回归树)。在阅读完本篇博客后,我们将会了解:

  • 机器学习领域用来描述CART算法的别称
  • 实际存储在磁盘上的/训练好的CART模型使用的表示
  • 一个CART模型如何从训练数据中学习
  • 如何使用一个训练好的CART模型来对未知数据进行预测
  • 可以用来了解更多关于CART的其它资源以及相关算法

如果我们之前有上过【算法与数据结构】的课程,那么实现这个简单但是强大的算法对我们来说并不困难。但是,在这日,我们离实现自己的随机森林还是一小步的距离。

决策树

CARTClassification and Regression Tree(分类回归树)的缩写,由Leo Breiman提出,指的是决策树算法,可以用来对可预测的建模问题进行分类或者回归。

一般说来,该算法指的是决策树,但是在一些平台上(例如R),一般会称作CART

CART算法为一些重要的算法(例如装袋决策树/随机森林/提升决策树)提供了基础。

CART模型表示

CART的模型表示是一个二叉树。

也就是算法与数据结构中的二叉树,并没有什么新奇的。每个根节点表示一个单一的输入变量:x和在那个变量上的分割点(假设该变量为数值型)。

树的叶子节点保护一个输出变量y,用来进行预测。

给定一个有两个输入的数据集(高度单位为厘米,体重单位为千克),输出为性别(男/女),下图是一个二叉决策树的简单示例(相关数据纯属虚构,只用作展示目的)。

决策树示例
图:决策树示例

这棵树可以作为一个图或者一系列的规则存储到文件中。例如,下面的代码就将上面的决策树作为了一系列的规则。

If Height > 180 cm Then Male
If Height <= 180 cm AND Weight > 80 kg Then Male
If Height <= 180 cm AND Weight <= 80 kg Then Female
Make Predictions With CART Models

通过上述CART模型的二叉树表示,进行预测的话相对比较直接。

给定一个新的输入,通过评估从树的根节点开始的特定输入对树进行遍历。

训练好的二叉树实际上是输入空间的分割。我们可以将每个输入变量看作是p维空间的一个维度。决策树将整个空间分割到长方形(当p=2,2个输入变量时)或者其它类型的超矩形。

新数据通过树进行过滤,并且会落在其中一个矩形中;该矩形的输出就是模型生成的预测。这种方法为我们提供了这种类型的决策:CART可以生成规则的界限。

例如,给定输入[height = 160 cm, weight = 65 kg],我们可以使用如下的方法对树进行遍历:

Height > 180 cm: No
Weight > 80 kg: No
Therefore: Female

从数据中训练CART模型

构建一个CART模型包括:选择输入变量和在这些变量上选择分割点,直到生成一颗合适的树。

输入变量的选择以及特定分割或者切割点的选择可以使用贪心算法来最小化成本函数。可以使用一个预先定义好的停止准则来停止构建,例如:分配给树中的每个叶子节点的最小训练实例数。

贪心分割

构建一个二叉树实际上是一个分割输入空间的过程。用来分割空间的贪心算法被称为:递归二进制分割。

这是一个数值的过程:所有值都被列出出来,使用一个成本函数对不同的分割点进行尝试和测试。选择拥有最佳成本(由于我们要最小化成本,因此这里指的是最低成本)的分割点。

使用贪心的风格对所有的输入变量和可能的分割点进行评估和选择(例如,每次选择最佳的分割点)。

对于回归预测性建模问题,用来最小化成本函数来选择分割点的方法是:计算落在矩形中所有训练样本中的误差平方和:

$$ sum((y-prediction) ^2)$$

其中,y是训练样本的输出,prediction是该矩形的预测输出。

对于分类问题,可以使用基尼指数函数来提供叶子节点“纯度”的标识(训练数据被分配给每个节点的混合度)。

$$G=sum(p_k*(1-p_k))$$

其中,G表示所有分类下的基尼指数,$$p_k$$表示在矩形兴趣中第k类训练实例的比例。一个有所有相同类型(完美的类纯度)的所有类节点的基尼指数为0,而在二分类问题中有50-50分割比例的类(最差纯度)的基尼指数为0.5

对于二分类问题,该计算公式可以写成:

$$G=2*p_1*p_2$$
或者
$$G=1-(p_1^2+p_2^2)$$

每个节点的基尼指数计算方式是:使用父节点的实例总数进行加权。在一个二分类问题中,使用下面的公式来计算选择某个分割点的基尼指数:

$$G = ((1 – (g1_1^2 + g1_2^2)) * (ng1/n)) + ((1 – (g2_1^2 + g2_2^2)) * (ng2/n))$$

其中,G是分割点的基尼指数,$$g1_1$$是类1中在组1中实例的比例,$$g1_2$$类2;$$g2_1$$:组2对类1;$$g2_2$$:组2对类2ng1ng2分别是组1和组2的总数,n是我们从父节点中试图分组的总实例数。

终止原则

在对训练数据构建树时,上面描述的递归二进制分割流程需要知道什么时候停止分割。

最通用的终止准则是:针对训练集中分配给每个叶子结点设置一个最小的训练实例数目。如果计数小于某些最小值,那么就不接受该分割,把该节点看作是最终的叶子节点。训练数目的基数根据具体的数据集进行调整,例如,5或者10。这控制了训练数据生成的树有多特殊。如果太过特殊的话(例如,计数为1),这棵树将会和训练数据过拟合,有可能在测试集合上出现糟糕的性能。

剪枝

终止原则非常重要,因为它会极大地影响树的性能。在训练了树之后,我们必须使用剪枝来提高性能。

决策树的复杂性被定义为树中分割的数目。我们更偏好与简单的树,它们比较易于理解(我们可以将其打印出来,然后将它们展示给主观的问题专家),并且比较不容易出现过拟合现象。

最快和最简单的剪枝方法是:对每个树中的叶子节点进行遍历,使用一个价差验证的测试机来评估删除该节点的影响。只有在删除该节点之后对整个测试集的整体成本函数有降低的情况下才删除叶子节点。当无法有任何提高时,可以停止删除节点。

可以使用一些更加复杂的剪枝方法:例如成本复杂简直(也被成为:最弱链接剪枝),使用一个学习参数(alpha)基于子树的大小来决定是否可以删除该节点。

CART的数据准备

除了合适的问题描述,CART不需要任何特殊的数据准备。

拓展阅读

本部分将会介绍一些资源供大家更进一步了解CART
分类和回归树

下面是一些从机器学习角度介绍CART算法的/优秀的机器学习材料:

总结

在本篇博客中,我们了解了机器学习中的CARTClassification and Regression Tree,分类和回归树),具体说来,包括以下几个方面:

  • 机器学习领域用来描述CART算法的别称
  • 实际存储在磁盘上的/训练好的CART模型使用的表示
  • 一个CART模型如何从训练数据中学习
  • 如何使用一个训练好的CART模型来对未知数据进行预测
  • 可以用来了解更多关于CART的其它资源以及相关算法

ps: 这周五周六参加了公司组织的黑客马拉松大赛,再一次深深地感受到了自己的不足,在技术深度上的缺陷,希望接下来能好好扩展自己的知识面和技术面,能够了解更多自己工作相关的前沿技术和信息!加油!

打赏

mickey

记录生活,写给几十年后的自己。