人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

    分类回归树(CART)算法详解(含Python代码实现)

    < 上一篇:岭回归和Lasso回归 下一篇:没有了 >
    前面章节分别介绍了线性回归的相关算法,在基本的线性回归算法中,样本的特征与样本的标签之间存在线性相关关系,但是,对于样本特征与样本标签存在非线性的关系时,如图 1 所示。

    样本特征与样本标签之间是非线性关系
    图 1 样本特征与样本标签之间是非线性关系

    对于图 1 所示的非线性的回归问题,简单的线性回归算法无法求解,利用简单的线性回归求解的结果如图 2 所示。

    简单的线性回归的求解结果
    图 2 简单的线性回归的求解结果

    为了能够实现对非线性数据的拟合,可以使用局部加权线性回归,当 k=0.05 时,其局部加权线性回归的求解结果如图 3 所示。

    局部加权线性回归的求解结果
    图 3 局部加权线性回归的求解结果

    局部加权线性回归能够对非线性的数据实现较好拟合,与简单的线性回归算法相比,局部线性加权回归算法是局部的线性模型,而简单的线性回归模型是全局的模型,利用局部的模型能够较好拟合出局部的数据。

    虽然基于局部加权线性回归模型能够较好拟合非线性数据,但是局部加权线性回归模型属于非参学习算法,在每次对数据进行预测时,需要利用数据重新训练模型的参数,当数据量较大时,这样的计算是非常耗费时间的。

    是否存在一种基于参数的学习算法,能够实现对非线性数据的回归呢?

    CART算法

    基于树的回归算法也是一类基于局部的回归算法,通过将数据集切分成多份,在每一份数据中单独建模。与局部加权线性回归不同的是,基于树回归的算法是一种基于参数的学习算法,利用训练数据训练完模型后,参数一旦确定,无需再改变。

    分类回归树(CART)算法是使用较多的一种树模型,CART 算法可以处理分类问题,也可以处理回归问题。在随机森林算法中,我们介绍了如何利用 CART 算法处理分类问题,在本章中,我们着重介绍如何利用 CART 算法处理回归问题。

    CART 算法中的树采用一种二分递归分割的技术,即将当前的样本集分为左子树和右子树两个子样本集,使得生成的每个非叶子节点都有两个分支。因此,CART 算法生成的决策树是非典型的二叉树。

    利用 CART 算法处理回归问题的主要步骤:
    1. CART回归树的生成;
    2. CART回归树的剪枝。

    CART回归树生成

    CART回归树的划分

    CART分类树算法中,利用 Gini 指数作为划分树的指标,通过样本中的特征,对样本进行划分,直到所有的叶节点中的所有样本都为同一个类别为止。但是在 CART 回归树中,样本的标签是一系列的连续值的集合,不能再使用 Gini 指数作为划分树的指标。

    我们注意到,Gini 指数表示的是数据的混乱程度,对于连续数据,当数据分布比较分散时,各个数据与平均数的差的平方和较大,方差就较大;当数据分布比较集中时,各个数据与平均数的差的平方和较小。方差越大,数据的波动越大;方差越小,数据的波动就越小。

    因此,对于连续的数据,可以使用样本与平均值的差的平方和作为划分回归树的指标。假设,我们有 m 个训练样本 {(X(1),y(1))),(X(2),y(2)),…,(X(m),y(m))},则划分 CART 回归树的指标为:

    CART回归树的指标

    其中,y(i) 为第 i 个样本的标签,y 为 m 个样本标签值的均值。现在,让我们利用 Python 实现 CART 回归树的划分指标,在计算的过程中,需要使用 numpy 中的相关函数,因此,首先需要导入 numpy 模块:
    import numpy as np
    CART 回归树的划分指标的具体形式如下所示:
    def err_cnt(dataSet):
        '''回归树的划分指标
        input:  dataSet(list):训练数据
        output: m*s^2(float):总方差
        '''
        data = np.mat(dataSet)
        return np.var(data[:, -1]) * np.shape(data)[0]
    有了划分的标准,那么,应该如何对样本进行划分呢?

    与 CART 分类树中的方法一样,我们根据每一维特征中的每一个取值,尝试将样本划分到树节点的左右子树中,如取得样本特征中的第 j 维特征中值 x 作为划分的值,如果一个样本在第 j 维处的值大于或者等于 x,则将其划分到右子树中,否则划分到左子树中,具体划分的过程如图 4 所示。

    左右子树的划分
    图 4 左右子树的划分

    在图 4 中,原始节点中有 m 个样本,根据与值 x 的对比,将样本划分到左右子树中,左子树被分到 m1 个样本,剩下的 m2 个样本被划分到右子树中。具体划分的过程如下所示:
    def split_tree(data, fea, value):
        '''根据特征fea中的值value将数据集data划分成左右子树
        input:  data(list):训练样本
                fea(float):需要划分的特征index
                value(float):指定的划分的值
        output: (set_1, set_2)(tuple):左右子树的聚合
        '''
        set_1 = []  # 右子树的集合
        set_2 = []  # 左子树的集合
        for x in data:
            if x[fea] >= value:
                set_1.append(x)
            else:
                set_2.append(x)
        return (set_1, set_2)
    split_tree 函数根据 fea 位置处的特征,按照值 value 将样本划分到左右子树中,当样本在 fea 处的值大于或者等于 value 时,将其划分到右子树中;否则,将其划分到左子树中。

    CART回归树的构建

    CART分类树的构建过程如下所示:
    1. 对于当前训练数据集,遍历所有属性及其所有可能的切分点,寻找最佳切分属性及其最佳切分点,使得切分之后的基尼指数最小,利用该最佳属性及其最佳切分点将训练数据集切分成两个子集,分别对应着判别结果是左子树和判别结果是右子树。
    2. 对第一步中生成的两个数据子集递归地调用第一步,直至满足停止条件。
    3. 生成CART决策树。
    为了能构建 CART 回归树算法,首先,需要为 CART 回归树中节点设置一个结构,其具体的实现如下所示:
    class node:
        '''树的节点的类
        '''
        def __init__(self, fea=-1, value=None, results=None, right=None, left=None):
            self.fea = fea  # 用于切分数据集的属性的列索引值
            self.value = value  # 设置划分的值
            self.results = results  # 存储叶节点的值
            self.right = right  # 右子树
            self.left = left  # 左子树  
    在 CART 回归树的节点类中,属性 fea 表示的是待划分数据集的特征的索引,属性 value 表示的是划分的具体的值,属性 results 表示的是叶子节点的具体的值,属性 right 表示的是右子树,属性 left 表示的是左子树。

    现在,让我们一起实现 CART 回归树,CART 回归树的构建过程如下所示:
    def build_tree(data, min_sample, min_err):
        '''构建树
        input:  data(list):训练样本
                min_sample(int):叶子节点中最少的样本数
                min_err(float):最小的error
        output: node:树的根结点
        '''
        # 构建决策树,函数返回该决策树的根节点
        if len(data) <= min_sample:
            return node(results=leaf(data))
       
        # 1、初始化
        best_err = err_cnt(data)
        bestCriteria = None  # 存储最佳切分属性以及最佳切分点
        bestSets = None  # 存储切分后的两个数据集
       
        # 2、开始构建CART回归树
        feature_num = len(data[0]) - 1
        for fea in range(0, feature_num):
            feature_values = {}
            for sample in data:
                feature_values[sample[fea]] = 1
           
            for value in feature_values.keys():
                # 2.1、尝试划分
                (set_1, set_2) = split_tree(data, fea, value)
                if len(set_1) < 2 or len(set_2) < 2:
                    continue
                # 2.2、计算划分后的error值
                now_err = err_cnt(set_1) + err_cnt(set_2)
                # 2.3、更新最优划分
                if now_err < best_err and len(set_1) > 0 and len(set_2) > 0:
                    best_err = now_err
                    bestCriteria = (fea, value)
                    bestSets = (set_1, set_2)
    
        # 3、判断划分是否结束
        if best_err > min_err:
            right = build_tree(bestSets[0], min_sample, min_err)
            left = build_tree(bestSets[1], min_sample, min_err)
            return node(fea=bestCriteria[0], value=bestCriteria[1], 
                        right=right, left=left)
        else:
            return node(results=leaf(data))  # 返回当前的类别标签作为最终的类别标签
    build_tree 函数用于构建 CART 回归树模型,在构建 CART回归树模型的过程中,如果节点中的样本的个数小于或者等于指定的最小的样本数 min_sample,则该节点不再划分。

    函数 leaf 用于计算当前叶子节点的值,当节点需要划分时,首先计算当前节点的 error 值;在开始构建的过程中,根据每一维特征的取值尝试将样本划分到左右子树中,即产生左子树和右子树,此时计算左右子树的 error 值,若此时的 error 值小于最优的 error 值,则更新最优划分;当该节点划分完成后,继续对其左右子树进行划分。

    其中,函数 leaf 的具体实现如下所示:
    def leaf(dataSet):
        '''计算叶节点的值
        input:  dataSet(list):训练样本
        output: np.mean(data[:, -1])(float):均值
        '''
        data = np.mat(dataSet)
        return np.mean(data[:, -1])

    CART回归树剪枝

    在 CART 树回归中,当树中的节点对样本一直划分下去时,会出现的最极端的情况是:每一个叶子节点中仅包含一个样本,此时,叶子节点的值即为该样本的标签的值。这种情况极易对训练样本“过拟合”,通过这样的方式训练出来的样本可以对训练样本拟合得很好,但是对于新样本的预测效果将会较差。

    为了防止构建好的 CART 树回归模型过拟合,通常需要对 CART 回归树进行剪枝,剪枝的目的是防止 CART 回归树生成过多的叶子节点。

    在剪枝中主要分为:前剪枝后剪枝

    前剪枝

    前剪枝是指在生成CART回归树的过程中对树的深度进行控制,防止生成过多的叶子节点。

    在前面的 build_tree 函数中,我们通过参数 min_sample 和 min_err 来控制树中的节点是否需要进行更多的划分。通过不断调节这两个参数,来找到一个合适的 CART 树模型。

    后剪枝

    后剪枝是指将训练样本分成两个部分:
    • 一部分用来训练CART树模型,这部分数据被称为训练数据;
    • 另一部分用来对生成的CART树模型进行剪枝,这部分数据被称为验证数据。
    由上述过程可知,在后剪枝的过程中,通过验证生成好的 CART 树模型是否在验证数据集上发生了过拟合,如果出现过拟合的现象,则合并一些叶子节点来达到对 CART 树模型的剪枝。

    在本章中,我们主要使用前剪枝的策略,通过调整参数 min_sample 和 min_err 来控制 CART 树模型的生成。
    < 上一篇:岭回归和Lasso回归 下一篇:没有了 >