精华内容
下载资源
问答
  • 什么是决策树 在现实生活中,我们会遇到各种选择,不论是选择男女朋友,还是挑选水果,都是基于以往的经验来做判断。如果把判断背后的逻辑整理成一个结构图,你会发现它实际上是一个树状图,这就是决策树决策树的...

    什么是决策树

    在现实生活中,我们会遇到各种选择,不论是选择男女朋友,还是挑选水果,都是基于以往的经验来做判断。如果把判断背后的逻辑整理成一个结构图,你会发现它实际上是一个树状图,这就是决策树。决策树的工作原理基本上就是把我们以前的经验总结出来。例如一个打篮球的训练集。如果我们要出门打篮球,一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断,最后得到结果:去打篮球?还是不去?
    在这里插入图片描述

    什么是CART算法

    CART算法,英文全称叫做Classification And Regression Tree,中文叫做分类回归树,CART决策树,既可以作分类树,又可以作回归树。

    举个例子,你能看到不同职业的人,他们的年龄不同,学习时间也不同。如果我构造了一棵决策树,想要基于数据判断这个人的职业身份,这个就属于分类树,因为是从几个分类中来做选择。如果是给定了数据,想要预测这个人的年龄,那就属于回归树。
    在这里插入图片描述

    分类树可以处理离散数据,也就是数据种类有限的数据,它输出的是样本的类别,而回归树可以对连续型的数值进行预测,也就是数据在某个区间内都有取值的可能,它输出的是一个数值。

    CART算法实战

    在Python的sklearn中,如果我们想要创建CART分类树,可以直接使用DecisionTreeClassifier这个类。

    1.用CART分类树,给iris数据集构造一棵分类决策树
    # encoding=utf-8
    from sklearn.model_selection import train_test_split
    from sklearn.metrics import accuracy_score
    from sklearn.tree import DecisionTreeClassifier
    from sklearn.datasets import load_iris
    # 准备数据集
    iris=load_iris()
    # 获取特征集和分类标识
    features = iris.data
    labels = iris.target
    # 随机抽取33%的数据作为测试集,其余为训练集
    train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
    # 创建CART分类树
    clf = DecisionTreeClassifier(criterion='gini')
    # 拟合构造CART分类树
    clf = clf.fit(train_features, train_labels)
    # 用CART分类树做预测
    test_predict = clf.predict(test_features)
    # 预测结果与测试集结果作比对
    score = accuracy_score(test_labels, test_predict)
    print("CART分类树准确率 %.4lf" % score)
    
    2.用CART回归树做预测

    sklearn自带的波士顿房价数据集,该数据集给出了影响房价的一些指标,比如犯罪率,房产税等,最后给出了房价。

    # encoding=utf-8
    from sklearn.metrics import mean_squared_error
    from sklearn.model_selection import train_test_split
    from sklearn.datasets import load_boston
    from sklearn.metrics import r2_score,mean_absolute_error,mean_squared_error
    from sklearn.tree import DecisionTreeRegressor
    # 准备数据集
    boston=load_boston()
    # 探索数据
    print(boston.feature_names)
    # 获取特征集和房价
    features = boston.data
    prices = boston.target
    # 随机抽取33%的数据作为测试集,其余为训练集
    train_features, test_features, train_price, test_price = train_test_split(features, prices, test_size=0.33)
    # 创建CART回归树
    dtr=DecisionTreeRegressor()
    # 拟合构造CART回归树
    dtr.fit(train_features, train_price)
    # 预测测试集中的房价
    predict_price = dtr.predict(test_features)
    # 测试集的结果评价
    print('回归树二乘偏差均值:', mean_squared_error(test_price, predict_price))
    print('回归树绝对值偏差均值:', mean_absolute_error(test_price, predict_price))
    

    总结

    在这里插入图片描述

    展开全文
  • 作者:xiaoyu介绍:一个半路转行的数据挖掘工程师推荐导读:本篇为树模型系列第三篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboo...
        

    作者:xiaoyu

    介绍:一个半路转行的数据挖掘工程师


     





    推荐导读:本篇为树模型系列第三篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboost,为要想要深入了解机器学习算法和参加数据挖掘竞赛的朋友提供帮助。


    640?wx_fmt=png


    前情回顾


    前两篇介绍了决策树主要的三个步骤,以及ID3和C4.5算法:


    本篇将继续介绍决策的第三种算法:CART算法,它可以说是学习决策树的核心了。高级集成学习很多复杂框架都是基于CART的。下面将详细介绍CART算法的来龙去脉。


    • CART生成算法

    • CART剪枝算法

    • CART算法小结

    • 决策树算法优缺点总结


    CART生成算法


    为什么叫CART算法呢?这还要从它的英文单词说起。CART是 "Classification and Regression Trees" 的缩写,意思是 "分类回归树"。从它的名字上就不难理解了,CART算法是既可以用于分类的,也可以用于回归的。


    很多朋友诧异于决策树为什么可以用于回归,明明是if-then结构用于分类的。下面我们来分别介绍CART分类和回归两种情况。


    分类树生成算法


    CART算法的分类树是与ID3和C4.5有所不同。下面我们针对特征值的类型来分别介绍CART算法是如何进行分类的,以及和C4.5有什么异同。


    如果特征值是连续值:CART的处理思想与C4.5是相同的,即将连续特征值离散化。唯一不同的地方是度量的标准不一样,CART采用基尼指数,而C4.5采用信息增益比。下面举个例子说明下:


    640?wx_fmt=png

    特征a有连续值m个,从小到大排列。m个数值就有m-1个切分点,分别使用每个切分点把连续数值离散划分成两类,将节点数据集按照划分点分为D1和D2子集,然后计算每个划分点下对应的基尼指数,对比所有基尼指数,选择值最小的一个作为最终的特征划分。

    640?wx_fmt=png

    基尼指数公式,以及基于特征A划分后的基尼指数


    以上就实现了将连续特征值离散化,但是CART与ID3,C4.5处理离散属性不同的是:如果当前节点为连续属性,则该属性(剩余的属性值)后面还可以参与子节点的产生选择过程。


    如果特征值是离散值:CART的处理思想与C4.5稍微所有不同。如果离散特征值多于两个,那么C4.5会在节点上根据特征值划分出多叉树。但是CART则不同,无论离散特征值有几个,在节点上都划分成二叉树。CART树是如何进行分类的呢?

    640?wx_fmt=png

    还是假设特征a有m个离散值。分类标准是:每一次将其中一个特征分为一类,其它非该特征分为另外一类。依照这个标准遍历所有的分类情况,计算每种分类下的基尼指数,最后选择值最小的一个作为最终的特征划分。


    特征值连续和离散有各自的处理方法,不应该混淆使用。比如分类0,1,2只代表标签含义,如果进行加减的运算或者求平均则没有任何意义。因此,CART分类树会根据特征类型选择不同的划分方法,并且与C4.5不同是,它永远只有两个分支。

    640?wx_fmt=png


    李航 “统计学习方法” 中的分类树算法流程仅仅是针对特征是离散型的情况,并没有提及连续值的情况。本篇根据上面我们介绍两个特征类型情况重新给出一个算法流程(主要就是区分两种不同特征类型):


    输入:训练数据集D,停止计算的参数条件。 输出:CART决策树。根据训练数据集,从根结点开始,递归地对每个结点进行以下操作,构建二叉决策树:1:如果样本个数小于阈值或者没有特征,   则返回决策子树,当前节点停止递归。2:计算样本集D的基尼系数,如果基尼系数小于阈值,   则返回决策树子树,当前节点停止递归。3:识别各个特征类型,离散值还是连续值?   对每种类型使用相应的处理方法并计算每个切分下的基尼系数。   缺失值的处理方法和C4.5算法里描述的相同。4:在计算出来的各个特征的各个特征值对数据集D的基尼系数中,   选择基尼系数最小的特征A和对应的特征值a。   根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,   同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2.5:对左右的子节点递归的调用1-4步,生成决策树。算法停止计算的条件是:如步骤1,2中所示,结点中的样本个数小于预定阈值,或样本集的Gini系数小于预定阈值(样本基本属于同一类),或者没有更多特征。


    回归树生成算法


    与分类树不同,回归树的预测变量是连续值,比如预测一个人的年龄,又或者预测季度的销售额等等。另外,回归树在选择特征的度量标准决策树建立后预测的方式上也存在不同。


    预测方式


    一个回归树对应着输入特征空间的一个划分,以及在划分单元上的输出值。先假设数据集已被划分,R1,R2,...,Rm共m的子集,回归树要求每个划分Rm中都对应一个固定的输出值cm。

    640?wx_fmt=png

    这个cm值其实就是每个子集中所有样本的目标变量y的平均值,并以此cm作为该子集的预测值。所有分支节点都是如此,叶子节点也不例外。因此,可以知道回归树的预测方式是:将叶子节点中样本的y均值作为回归的预测值。分类树的预测方式则是:叶子节点中概率最大的类别作为当前节点的预测类别


    选择特征的度量标准


    CART回归树对于特征类型的处理与分类树一样,连续值与离散值分开对待,并只能生成二叉树。但是CART回归树对于选择特征的度量标准则完全不同。


    分类树的特征选择标准使用基尼指数,而回归树则使用RSS残差平方和。了解线性回归的朋友知道,损失函数是以最小化离差平方和的形式给出的。回归树使用的度量标准也是一样的,通过最小化残差平方和作为判断标准,公式如下:

    640?wx_fmt=png

    注意:计算的是属性划分下样本的目标变量y的残差平方和,而非属性值。


    • yi:样本目标变量的真实值。

    • R1&R2:被划分的两个子集,回归树是二叉树,固只有两个子集。

    • c1&c2:R1&R2子集的样本均值。

    • j:当前的样本特征

    • s:划分点


    上面公式的含义是:计算所有的特征以及相应所有切分点下的残差平方和,找到一组(特征j,切分点s),以满足:分别最小化左子树和右子树的残差平方和,并在此基础上再次最小化二者之和。


    其实,回归树也有分类的思想。所谓 “物以类聚”,相同类之间的目标变量值才会更接近,方差值也就会更小。对于回归树的生成算法,除了以上两点外,其它都分类树是相同的。


    CART剪枝算法


    对于决策树剪枝,上一篇已经介绍:决策树学习笔记(二):剪枝,ID3,C4.5。这部分重点介绍下CART是如何剪枝的?选择的是哪种方式?


    CART回归树和CART分类树的剪枝策略除了在度量损失的时候一个使用均方差,一个使用基尼系数,算法基本完全一样,因此将它们统一来说。CART采用的办法是后剪枝法,即先生成决策树,然后产生所有可能的剪枝后的CART树,然后使用交叉验证来检验各种剪枝的效果,选择泛化能力最好的剪枝策略。


    也就是说,CART树的剪枝算法可以概括为两步:

    1)是从原始决策树生成各种剪枝效果的决策树序列。

    2)是用交叉验证来检验剪枝后的预测能力,选择泛化预测能力最好的剪枝后的数作为最终的CART树。


    1)生成决策树序列


    CART采用CCP(代价复杂度)的后剪枝方法,定义了决策树的损失函数和正则化项。公式如下:

    640?wx_fmt=png

    • T:决策树中的任意一个节点

    • |T|:叶子节点数

    • alpha:正则化参数,惩罚系数

    • C(T):无惩罚项情况下的预测误差,比如基尼指数

    • C_alpha(T):在正则参数alpha情况下节点T对应的预测误差


    CART剪枝与C4.5有所不同,C4.5剪枝算法是人为给定一个alpha,然后从叶结点逐渐向根节点回溯,然而CART多了一个遍历alpha的步骤,从0~+无穷


    我们先明确几个概念,然后将这几个概念结合起来就可以理解整个生成决策树序列的算法流程了。


    现假设我选定了决策树的任意一个节点t,并将节点t作为根节点。那么这个时候我想知道节点t下的分支是否需要剪枝,怎么办呢?


    很容易想到,我们可以对比一下剪枝以后的预测误差和剪枝以前的预测误差值的大小,如果不剪枝的误差比剪枝的大,那么我们就执行剪枝。用公式来抽象描述一下:

    640?wx_fmt=png

    以t为单节点树的损失函数,|t|=1(剪枝后)


    640?wx_fmt=png

    以t为根节点的Tt损失函数(剪枝前)


    现在我们有了以t为根节点剪枝前后的损失函数,我们只需要对比一下就知道了。由于alpha未确定,因此临界的情况是:

    640?wx_fmt=png

    我们把这时候的alpha临界值称为误差增益率,用g(t)来表示,公示如下:

    640?wx_fmt=png

    我们可以将g(t)简单的理解为一种阈值,如果alpha大于或者等于g(t),那么就剪枝。因为在相等的情况下,不剪枝和剪枝达到同样的效果,也就相当于这些分支没有什么作用。如果alpha小于g(t),则保留,不剪枝。


    考虑另外一个问题,如何选择用哪个节点进行剪枝呢?


    我们上面已经找到了对某个节点下是否该剪枝的方法了,但我们开始假设的是任意一个节点t,是一个通用的方法。对于一个生成完整的决策树而言,是至少拥有一个节点的。如果一个决策树有n个节点,那么我就会有相应的n个误差增益率g(t)


    现在alpha是未知的,我们需要从零开始遍历,直到正无穷。显然,如果节点下的g(t)越小,alpha就会越先达到该节点的阈值,而此时的alpha大小还不足以达到其它节点的阈值。这说明g(t)越小的节点应该越先被剪枝。


    如果我们将所有g(t)排序,g1(t),g2(t),...,gn(t),那么我就会先对g1(t)对应的节点剪枝,得到一个最优子树,和alpha区间。然后在此基础上再对g2(t)对应的节点进行剪枝,得到第二个最优子树,直到得到n个最优子树的序列。


    有的朋友不明白:既然是遍历alpha,从0~+无穷,那为什么还会得到一个alpha的区间呢?这个很好理解,因为每个alpha区间是对应一个特征节点的,而决策树的节点是有限的,因此我们真正的目的并不是遍历alpha,而是通过遍历alpha与各个g(t)比较而得到(n+1)个最优子树序列。


    交叉验证

    得到字数序列以后,我们可以使用独立的验证数据集,测试各子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。并且,每颗子树都对应着一个alpha,所以最优子树确定了,alpha也就确定了。


    上面已经将CART剪枝进行详细的分析了,下面看一下CART剪枝的整个算法流程。


    640?wx_fmt=png


    CART算法小结


    上面我们对CART算法做了一个详细的介绍,CART算法相比C4.5算法的分类方法,采用了简化的二叉树模型,同时特征选择采用了近似的基尼系数来简化计算。当然CART树最大的好处是还可以做回归模型,这个C4.5没有。下表给出了ID3,C4.5和CART的一个比较总结。希望可以帮助大家理解。


    640?wx_fmt=png

    看起来CART算法高大上,那么CART算法还有没有什么缺点呢?有,主要的缺点如下:


    1)无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策,但是大多数,分类决策不应该是由某一个特征决定的,而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候,多变量决策树不是选择某一个最优特征,而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1,这里不多介绍。


    2)如果样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。   


    决策树算法优缺点总结


    我们前面介绍了决策树的特征选择,生成,和剪枝,然后对ID3, C4.5和CART算法也分别进行了详细的分析。下面我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。


    决策树算法的优点


    1)简单直观,生成的决策树很直观。

    2)基本不需要预处理,不需要提前归一化,处理缺失值。

    3)使用决策树预测的代价是O(log2m)O(log2m)。 m为样本数。

    4)既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

    5)可以处理多维度输出的分类问题。

    6)相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释

    7)可以交叉验证的剪枝来选择模型,从而提高泛化能力。

    8) 对于异常点的容错能力好,健壮性高。


    决策树算法的缺点


    1)决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

    2)决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

    3)寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。

    4)有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。

    5)如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。


    下一篇将会介绍一个决策树应用的实战内容,以及如何使用sklearn进行决策树的调参。


    [1] 统计学习方法,李航,p73

    [2] https://www.cnblogs.com/pinard/p/6053344.html

    [3] https://blog.csdn.net/zlsjsj/article/details/81387393



    展开全文
  • 分类回归(Classification And Regression Trees,CART)是一种构造的监督学习方法。笔记实现了回归和模型

    分类回归树(Classification And Regression Trees,CART)是一种构造树的监督学习方法。

    和ID3决策树作比较:

    1. ID3每次直接用最佳特征分割数据,即如果当前特征有4个可能值,那么数据将被分成4份,处理的是标称型数据,不能直接处理连续型数据。CART则利用二元切分来处理连续型变量,每次会找一个最佳特征的阈值,把数据集分成两部分,也就是左子树和右子树。

    2. CART使用方差计算来代替香农熵。但目的都是找最佳切分特征。

    import numpy as np
    '''
    CART使用二元切分来处理连续型变量。
    回归树和分类树类似,只是叶节点的数据类型是连续型不是离散型
    (其实也不是真正的“连续”,切分时仍取决于属性值,只不过数值都是浮点数)
    以下是两种CART:回归树,模型树
    '''
    def loadData(filename):
        dataM = []
        fr = open(filename)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = map(float, curLine)  # 每行存成一组浮点数
            dataM.append(fltLine)
        return dataM
    
    # ----------------- 回归树(regression tree)每个叶节点包含单个值 -------------------
    def regLeaf(data): # 数据不需要再切分时用来生成叶节点(常量)
        return np.mean(data[:,-1])
    
    def regErr(data):  # 误差用均方差计算
        return np.var(data[:,-1]) * np.shape(data)[0]
    
    # 找最佳的切分的位置(特征)和阈值
    def chooseBestSplit(data, leafType=regLeaf, errType=regErr, ops=(1,4)):
        tolS = ops[0]  # 允许的误差减少量的最低值
        tolN = ops[1]  # 允许切分的最少样本数
        if len(set(data[:,-1].T.tolist()[0])) == 1:  # 标签值只有一个值(都是一类)
            return None, leafType(data)
        m, n = np.shape(data)
        S = errType(data)  # 目标变量的总方差
        bestS = inf
        bestIdx = 0
        bestVal = 0
        for featIdx in range(n-1):
            for splitVal in set(data[:, featIdx]):
                mat0, mat1 = binSplitData(data, featIdx, splitVal)
                if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
                    continue    # 划分条件
                newS = errType(mat0) + errType(mat1)
                if newS < bestS:
                    bestIdx = featIdx
                    bestVal = splitVal
                    bestS = newS
        if (S-newS) < tolS:                        
            return None, leafType(data)  # 如果误差变化量很小就退出
        mat0, mat1 = binSplitData(data, bestIdx, bestVal)
        if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
            return None, leafType(data)  # 如果切分的数据集很小也退出
        return bestIdx, bestVal
    
    # 数据集的切分函数
    def binSplitData(data, feature, value):
        mat0 = data[np.nonzero(data[:, feature] > value)[0], :]  # 左子树
        mat1 = data[np.nonzero(data[:, feature] <= value)[0], :] # 右子树
        return mat0, mat1
    
    def createTree(data, leafType=regLeaf, errType=regErr, ops=(1,4)):
        feat, val = chooseBestSplit(data, leafType, errType, ops)
        if feat == None:  # feat为None是chooseBestSplit()决定的不再切分数据
            return val    # val是leafType()生成的叶节点 (这里是常值, 变量均值)
        retTree = {}
        retTree['spInd'] = feat
        retTree['spVal'] = val
        lfData, rtData = binSplitData(data, feat, val)
        retTree['left'] = createTree(lfData, leafType, errType, ops)
        retTree['right']= createTree(rtData, leafType, errType, ops)
        return retTree
    
    # ------------------ 模型树(model tree)每个叶节点包含一个线性方程 -------------------
    def linearNode(data):
        m, n = np.shape(data)
        x = np.mat(np.ones((m,n)))
        y = np.mat(np.ones((m,1)))
        x[:, 1:n] = data[:, 0:n-1]
        y = data[:, -1]
        xTx = x.T * x
        if linalg.det(xTx) == 0.0:
            raise(NameError('This matrix is singular, cannot do inverse'))
        w = xTx.I * (x.T * y)
        return w, x, y
    
    def modelLeaf(data):  # 数据不需要再切分时用来生成叶节点(线性函数) 
        w, x, y = linearNode(data)
        return w
    
    def modelErr(data):   # 误差用平方差计算
        w, x, y = linearNode(data)
        yHat = x * w
        return np.sum(np.power(y-yHat, 2))
    
    def createTree(data, leafType=modelLeaf, errType=modelErr, ops=(1,4)):
        feat, val = chooseBestSplit(data, leafType, errType, ops)
        if feat == None:  # feat为None是chooseBestSplit()决定的不再切分数据
            return val    # val是leafType()生成的叶节点 (这里是直线, 回归系数 )
        retTree = {}
        retTree['spInd'] = feat
        retTree['spVal'] = val
        lfData, rtData = binSplitData(data, feat, val)
        retTree['left'] = createTree(lfData, leafType, errType, ops)
        retTree['right']= createTree(rtData, leafType, errType, ops)
        return retTree
    
    # ----------------------------- 回归树和模型树做预测 ----------------------------------
    def regTreeEval(treeNode, xdata):   # 叶节点为常量值
        return float(treeNode)
    
    def modelTreeEval(treeNode, xdata): # 叶节点为回归系数
        n = np.shape(xdata)[1]
        x = np.mat(np.ones((1, n+1)))
        x[:, 1:n+1] = xdata
        return float(x*treeNode)
    
    def isTree(obj):
        return (type(obj).__name__ == 'dict')
    
    # modelEval指定树的类型,区分两种叶节点
    def treePredict(tree, xTest, modelEval=regTreeEval): 
        if not isTree(tree):
            return modelEval(tree, xTest)
        if xTest[tree['spInd']] > tree['spVal']:  # 划分特征的值大于阈值,分到左子树
            if isTree(tree['left']):                       # 左子树还有分支
                return treePredict(tree['left'], xTest, modelEval)
            else:                                          # 左子树已经是叶节点
                return modelEval(tree['left'], xTest)
        else:                                     # 划分特征的值小于阈值,分到右子树
            if isTree(tree['right']):
                return treePredict(tree['right'], xTest, modelEval)
            else:
                return modelEval(tree['right'], xTest)



    展开全文
  • 决策树CART算法

    2020-08-22 09:06:59
    而这正是CART算法的核心思想。 核心思想 假设决策树是二叉树,内部节点特征的取值为“是”与“否”。左分支取值为“是”,右分支取值为“否”。这样决策树就等价于递归地二分每个特征,将输入空间划分为了有限个单元...

    前提

    决策树算法详解(一)

    连接

    在前面介绍的决策树算法中,其特征的取值是离散的。就比如人的性别这个属性,只分为男女两个离散的值。在这样的情况下,决策树算法就无法应用到连续值上面去。为了将前面讲到的决策树算法应用到连续值上去。那么我们能想到的一种的思想就是:根据连续值中的一个值将特征划分为两类。而这正是CART算法的核心思想。

    核心思想

    假设决策树是二叉树,内部节点特征的取值为“是”与“否”。左分支取值为“是”,右分支取值为“否”。这样决策树就等价于递归地二分每个特征,将输入空间划分为了有限个单元。

    回归树

    特征选择依据

    平方误差最小化准则

    思想

    我们知道决策树是对输入空间的一个划分,同时在每个划分空间对应一个输出值。对于每一个空间划分Rm,其上面的输出值Cm,通过回归树模型可以表示为:
    在这里插入图片描述在上式中:
    I(x∈R_m):指示函数,表示一个数据x是否属于空间划分Rm

    有了上式,我们想要知道一个划分空间的最优输出值。而我们知道特征选择依据是平方差最小化准则。其实这时候一个划分空间的最优输出值就是在这个划分空间内的所有数据的输出值的均值。

    现在:我们已经知道了每个划分空间的最优输出值了,那么我们现在要做的就是对决策树的特征选择。我们知道CART的核心思想是:将连续值通过一个固定值将其一分为二。那么此时的特征选择就是计算每个特征的每个划分点的最优损失函数。根绝损失函数最小化来选择特定的特征,并且特定的划分值将特征一分为二。

    算法步骤

    在训练数据集所在的输入空间中,递归的将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树

    1. 选择最优切分变量(最优特征)j与切分点(划分值)s,求解:(也就是最小化损失函数,C是划分空间内所有数据的均值)
      在这里插入图片描述
    2. 用选定的(j,s)划分区域并决定相应的输出值:
      在这里插入图片描述
    3. 继续对两个子区域调用步骤1和步骤2,循环递归,知道满足停止条件。
    4. 将输入空间划分为了M个空间,输出决策树

    分类树

    特征选择依据

    基尼指数最小化准则

    基尼系数

    假设有K个类,样本点属于第K类的概率为P,则概率分布的基尼系数定义为:
    在这里插入图片描述在某个条件上被划分下基尼系数为:(比如特征A将数据集划分为两部分)
    在这里插入图片描述
    基尼系数Gini(D)表示集合D的不确定性,基尼指数Gini(D,A)表示经过A=a分割后集合D的不确定性。基尼指数值越大,样本集合的不确定性就越大。

    算法步骤

    1. 设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。即:测试灭个每个特征上的每个可以能的取值,根据该取值将数据集划分为两部分,计算该特征下数据集的基尼系数
    2. 在所有的特征中以及他们所有可能的切分点中,选择基尼系数最小的特征及其对应的切分点作为最优特征和最优切分点。依据此将数据集划分为两部分
    3. 递归调用步骤1,步骤2,直至满足停止条件
    4. 生成CART决策树

    算法停止条件:

    1. 结点中的样本个数小于预定阈值;
    2. 样本集的基尼系数小于预定阈值
    3. 没有更多特征

    算法剪枝

    损失函数:
    在这里插入图片描述式子中:
    第一项:训练数据集中的训练误差
    第二项:决策树的叶子结点树,表示模型的复杂度

    从式子中,我们知道:
    当α大的时候,最优树偏小,即树的叶子节点较少;当α小的时候,最优树偏大,即树的节点较多;极端情况下,当α=0时,整体书最优,即不剪枝;当α=∞时,根节点组成的单节点树最优

    递归对树进行剪枝

    将α从小增大时,0=a1<a2<…<an<+∞时,产生一系列的区间[ai,ai+1),,剪枝得到的子数{T0,T1,T2,…,Tn},序列中的子数是相互嵌套的。

    详细解读

    从整体书T0开始剪枝,对T0的任意内部结点t,以t为单节点的损失函数是:
    在这里插入图片描述以t为根节点的子树Tt的损失函数是:
    在这里插入图片描述当 a = 0 及a充分小的时候,有不等式:
    在这里插入图片描述
    解释:当a=0时,即不考虑模型的复杂度,这时候肯定是决策树划分得越细,其误差越小
    当a逐渐增大时,到达某一个值时,有:
    在这里插入图片描述
    当a再增大时,上面得不等式就会反向,只要:
    在这里插入图片描述Tt与t就有相同的损失函数,而以t为单节点的树结点少,因此更加可取,对Tt进行剪枝。

    因此:对T0中的任一内部结点,计算:
    在这里插入图片描述它表示剪枝后,整体损失函数的减少程度。在T0
    中剪去g(t)最小的Tt,将得到的子数作为T1,同时将最小的g(t)设为a1,T1为区间[a1,a2)的最优子树

    展开全文
  • 决策树(Decision Tree)是一种基于规则的基础而又经典的分类...典型的决策树有ID3、C4.5和CART(Classification And Regression),它们的主要区别在于树的结构与构造算法。其中ID3和C4.5只支持分类,而CART支持分类和...
  • 决策树cart算法详解

    2019-06-25 10:56:15
    CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些...
  • 参考博客:... 目录 1、ID3算法原理 2、算法实现代码(利用pandas) 2.1 构建训练集 ...2.2 算法实现 ...3、决策树调包使用 3.1 代码 3.2 参数设置相关 4、决策树的优缺点 1、ID3算法原理 I...
  • 1.4 决策树剪枝算法 二、随机森林RF 2.1随机森林的生成 2.2 随机森林的特点 一、决策树CART CART分类回归树是一种典型的二叉决策树,可以处理分类或者回归问题。如果待预测结果是离散型数据,则CART生成分类...
  • CART决策树算法

    2020-09-04 10:45:07
    内容整理参考文档决策树——CART算法及其后的参考文章。 CART(classification and regression tree)分类与回归树,既可用于分类,也可用于回归。 CART分类树生成 CART分类树算法使用基尼系数来选择特征。基尼系数...
  • 文章目录决策树决策树ID3算法的不足决策树C4.5算法对ID3的改进决策树C4.5算法的不足与改进CART算法CART分类树算法对连续特征和离散特征的处理...具体流程CART回归树建立算法CART树算法的剪枝CART算法小结CART算法缺点...
  • 决策树综述 决策树的工作原理 决策树(decision tree)分类法是一种简单但广泛使用的分类技术。以是否贷款违约的二分类问题为例,当我们希望根据给定的训练集习得一个模型对新出现的贷款人进行分类时,经常需要从...
  • 决策树是基于人们总结经验的树状决策图,是一种基本的分类和回归算法。 二、决策树的原理 1、 构造原理,如何构造出一个决策树,即选择哪些属性分别作为根节点、中间节点以及叶节点。 2、剪枝原理,即给决策树瘦身,...
  • 机器学习算法第十篇 主要内容:决策树算法+CART(回归树) ...CART算法包含决策树生成和决策树剪枝两部分 CART决策生成树部分主要分为生成回归树和生成分类树 本篇主要讲生成回归树   \     \ &...
  • 递归构建决策树递归构建决策树代码6 C4.5:信息增益率7 CATR: Gini系数8 过拟合与剪枝过拟合 Overfitting9 决策树算法种类10 决策树鸢尾花实战案例一案例二决策树可视化环境搭建案例三 构建决策树 1.决策树的构建 ...
  • R语言 CART算法和C4.5算法(决策树

    千次阅读 2020-02-26 14:39:00
    关注微信号:小程在线 关注CSDN博客:程志伟的博客 R版本:3.4.4 最新的R官网取消了mvpart包,有需要的可以留言或者加微信...J48函数:实现C4.5算法 maptree包:提供draw.tree函数 mvpart包:提供数据集car.tes...
  • 决策树Cart算法

    2017-11-09 10:07:00
    Contents   ... Classification And Regression Tree,即分类回归树算法,简称CART算法,它是决策树的一种实现,通  常决策树主要有三种实现,分别是ID3算法,CART算法和C4.5算法。   ...
  • CART决策树算法总结

    千次阅读 2016-06-15 13:55:27
    CART决策树算法,顾名思义可以创建分类树(classification)和回归树(regression)。1.分类树。当CART决策树算法用于创建分类树时,和ID3和C4.5有很多相似之处,但是CART采用基尼指数作为选择划分属性的依据,数据...
  • 在决策树各个节点上应用信息增益准则选择特征,每一次都选择是的信息增益最大的特征进行分裂,递归的构建决策树 具体计算可以参考 决策常用算法数学计算过程 ID3代码实现 import numpy as np import math a=[[2,3],...
  • 机器学习:决策树cart算法构建回归树
  • 前面两篇博文我们介绍了一下决策树的ID3和C4.5算法,现在我们一起来看看CART算法吧,CART是英文Classification And Regression Tree的缩写,也就是分类回归树,顾名思义,CART可以用作分类也可以用作回归。...
  • 机器学习算法第十一篇 主要内容:决策树算法+CART(分类树) ...CART算法包含决策树生成和决策树剪枝两部分 CART决策生成树部分主要分为生成回归树和生成分类树 本篇主要讲生成分类树   \     \ ...
  • 决策树CART算法原理详解

    千次阅读 2019-04-13 20:21:48
    大家好,今天用一个简单的例子来给大家介绍一下决策树中的CART算法。 CART分类树 CART分类树适用于预测结果为离散型数据的情况下,主要是计算每一组特征的Gini系数增益来确定决策树划分的优先规则,主要是采用一种...
  • 决策树__CART算法

    2019-05-19 21:48:38
    CART决策树的生成就是递归地构建二叉树的过程.CART用基尼(Gini)系数最小化准则来进行特征选择,生成二叉树. Gini系数计算: CART算法例子: 分别计算他们的Gini 系数增益,取Gini系数增益值最大的属性作为决策...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,032
精华内容 3,212
热门标签
关键字:

cart算法构建决策树