精华内容
下载资源
问答
  • 决策树算法原理(ID3,C4.5) CART回归树 决策树的剪枝    在决策树算法原理(ID3,C4.5)中,提到C4.5的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理回归。对这些...

    决策树算法原理(ID3,C4.5)

    CART回归树 

    决策树的剪枝

     

      

      在决策树算法原理(ID3,C4.5)中,提到C4.5的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理回归。对这些问题,CART(Classification And Regression Tree)做了改进,可以处理分类,也可以处理回归。

     

    1. CART分类树算法的最优特征选择方法

      ID3中使用了信息增益选择特征,增益大优先选择。C4.5中,采用信息增益比选择特征,减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(比)相反。

      假设K个类别,第k个类别的概率为pk概率分布的基尼系数表达式:

      如果是二分类问题,第一个样本输出概率为p,概率分布的基尼系数表达式为:

      对于样本D,个数为|D|,假设K个类别,第k个类别的数量为|Ck|,则样本D的基尼系数表达式:

      对于样本D,个数为|D|,根据特征A的某个值a,把D分成|D1|和|D2|,则在特征A的条件下,样本D的基尼系数表达式为:

      比较基尼系数和熵模型的表达式,二次运算比对数简单很多。尤其是二分类问题,更加简单。

        和熵模型的度量方式比,基尼系数对应的误差有多大呢?对于二类分类,基尼系数和熵之半的曲线如下:

      基尼系数和熵之半的曲线非常接近,仅在45度角附近误差稍大。因此,基尼系数可以做为熵模型的一个近似替代。

      CART分类树算法每次仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。

     

    2. CART分类树算法对连续特征和离散特征的处理

      CART分类树算法对连续值的处理,思想和C4.5相同,都是将连续的特征离散化。唯一区别在选择划分点时,C4.5是信息增益比,CART是基尼系数。

      具体思路:m个样本的连续特征A有m个,从小到大排列a1,a2,......,am,则CART取相邻两样本值的平均数做划分点,一共取m-1个,其中第i个划分点Ti表示为:Ti = (ai + ai+1)/2。分别计算以这m-1个点作为二元分类点时的基尼系数选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at,则小于at的值为类别1,大于at的值为类别2,这样就做到了连续特征的离散化。

      注意的是,与ID3、C4.5处理离散属性不同的是,如果当前节点为连续属性,则该属性在后面还可以参与子节点的产生选择过程。

      CART分类树算法对离散值的处理,采用的思路:不停的二分离散特征。

      在ID3、C4.5,特征A被选取建立决策树节点,如果它有3个类别A1,A2,A3,我们会在决策树上建立一个三叉点,这样决策树是多叉树。

      CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况,找到基尼系数最小的组合,比如{A2}和{A1,A3},然后建立二叉树节点,一个节点是A2对应的样本,另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开,后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同,在ID3或C4.5的一颗子树中,离散特征只会参与一次节点的建立。

     

    3. CART分类树算法具体流程

      CART分类树建立算法流程,之所以加上建立,是因为CART分类树算法有剪枝。

      算法输入训练集D,基尼系数的阈值,样本个数阈值。

      输出的是决策树T。

      算法从根节点开始,用训练集递归建立CART分类树。

      (1)、对于当前节点的数据集为D,如果样本个数小于阈值或没有特征,则返回决策子树,当前节点停止递归。

      (2)、计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归。

      (3)、计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数,对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和C4.5算法里描述的相同。

      (4)、在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2。

      (5)、对左右的子节点递归的调用1-4步,生成决策树。

      对生成的决策树做预测的时候,假如测试集里的样本A落到了某个叶子节点,而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

     

    4. CART回归树建立算法

      CART回归树

      CART回归树和CART分类树的建立类似,这里只说不同。

      (1)、分类树与回归树的区别在样本的输出,如果样本输出是离散值,这是分类树;样本输出是连续值,这是回归树。分类树的输出是样本的类别,回归树的输出是一个实数。

      (2)、连续值的处理方法不同。

      (3)、决策树建立后做预测的方式不同

      分类模型:采用基尼系数的大小度量特征各个划分点的优劣。

      回归模型:采用和方差度量,度量目标是对于划分特征A,对应划分点s两边的数据集D1和D2,求出使D1和D2各自集合的均方差最小,同时D1和D2的均方差之和最小。表达式为:

    其中,c1为D1的样本输出均值,c2为D2的样本输出均值。

      对于决策树建立后做预测的方式,CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。回归树输出不是类别,采用叶子节点的均值或者中位数来预测输出结果

     

    5、CART树算法的剪枝

      CART树的生成:基于训练数据集递归构建二叉决策树。CART树的剪枝:用验证数据集对生成的树进行剪枝并选择最优子树,损失函数最小作为剪枝的标准。

      CART分类树的剪枝策略在度量损失的时候用基尼系数CART回归树的剪枝策略在度量损失的时候用均方差

      决策树很容易对训练集过拟合,导致泛化能力差,所以要对CART树进行剪枝,即类似线性回归的正则化。CART采用后剪枝法,即先生成决策树,然后产生所有剪枝后的CART树,然后使用交叉验证检验剪枝的效果,选择泛化能力最好的剪枝策略。

     

      剪枝损失函数表达式:

      α为正则化参数(和线性回归的正则化一样),C(Tt)为训练数据的预测误差,|Tt|是子树T叶子节点数量。

      当α = 0时,即没有正则化,原始生成的CART树即为最优子树。当α = ∞时,正则化强度最大,此时由原始的生成CART树的根节点组成的单节点树为最优子树。当然,这是两种极端情况,一般来说,α越大,剪枝剪的越厉害,生成的最优子树相比原生决策树就越偏小。对于固定的α,一定存在使得损失函数Cα(Tt)最小的唯一子树。

     

      剪枝的思路:

      对于位于节点t的任意一颗子树Tt,如果没有剪枝,损失函数是:

      如果将其剪掉,仅保留根节点,损失函数是:

      当α = 0或α很小,,当α增大到一定程度时

      当α继续增大时不等式反向,即满足下式:

      Tt和T有相同的损失函数,但T节点更少,因此可以对子树Tt进行剪枝,也就是将它的子节点全部剪掉,变为一个叶子结点T。

      

      交叉验证策略:

      如果我们把所有节点是否剪枝的值α都计算出来,然后针对不同α对应的剪枝后的最优子树做交叉验证。这样可以选择最好的α,有了这个α,用对应的最优子树作为最终结果。

      有了上面的思路,CART树的剪枝算法:

      输入是CART树建立算法得到的原始决策树T

      输出最优决策树Tα

      算法过程:

      (1)、初始化αmin = ∞,最优子树集合ω = {T}。

      (2)、从叶子结点开始自下而上计算内部节点 t 的训练误差损失函数Cα(Tt)(回归树为均方差,分类树为基尼系数),叶子节点数|Tt|,以及正则化阈值,更新αmin = α

      (3)、得到所有节点的α值得集合M。

      (4)、从M中选择最大的值αk,自上而下的访问子树 t 的内部节点,如果时,进行剪枝。并决定叶子节点 t 的值。如果是分类树,这是概率最高的类别,如果是回归树,这是所有样本输出的均值。这样得到αk对应的最优子树Tk

      (5)、最优子树集合ω = ωυTk,M = M - {αk}。

      (6)、如果M不为空,则回到步骤4。否则就已经得到了所有的可选最优子树集合ω

      (7)、采用交叉验证在ω选择最优子树Tα

     

    6. CART算法小结 

     算法 支持模型 树结构 特征选择  连续值处理 缺失值处理    剪枝
     ID3    分类  多叉树  信息增益  不支持  不支持  不支持
     C4.5    分类  多叉树  信息增益比  支持  支持  支持
     CART  分类回归  二叉树

     基尼系数

     均方差

     支持  支持  支持

    ωCART算法缺点:

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

    (2)、样本一点点改动,树结构剧烈改变。这个通过集成学习里面的随机森林之类的方法解决。

     

    7. 决策树算法小结

      这里不纠结ID3、C4.5、CART,这部分来自scikit-learn英文文档。

    优点:

    1. 简单直观,生成的决策树很直观。
    2. 基本不需要预处理,不需要提前归一化和处理缺失值
    3. 使用决策树预测的代价O(log2m)。m为样本数。
    4. 可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
    5. 可以处理多维度输出的分类问题。
    6. 相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以很好解释。
    7. 可以交叉验证的剪枝来选择模型,从而提高泛化能力
    8. 对于异常点的容错能力好,健壮性高。

    缺点:

    1. 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量限制决策树深度来改进
    2. 决策树会因为样本发生一点的改动,导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。 
    3. 寻找最优的决策树是一个NP难题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习的方法来改善
    4. 有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决
    5. 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

     

    转载于:https://www.cnblogs.com/keye/p/10564914.html

    展开全文
  •  在决策树算法原理(上)这篇里,我们讲到了决策树里ID3算法,和ID3算法的改进版C4.5算法。对于C4.5算法,我们也提到了它的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理...

    转载处刘建平博客 https://www.cnblogs.com/pinard/p/6053344.html
     在决策树算法原理(上)这篇里,我们讲到了决策树里ID3算法,和ID3算法的改进版C4.5算法。对于C4.5算法,我们也提到了它的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理回归等。对于这些问题, CART算法大部分做了改进。CART算法也就是我们下面的重点了。由于CART算法可以做回归,也可以做分类,我们分别加以介绍,先从CART分类树算法开始,重点比较和C4.5算法的不同点。接着介绍CART回归树算法,重点介绍和CART分类树的不同点。然后我们讨论CART树的建树算法和剪枝算法,最后总结决策树算法的优缺点。

    1. CART分类树算法的最优特征选择方法

    我们知道,在ID3算法中我们使用了信息增益来选择特征,信息增益大的优先选择。在C4.5算法中,采用了信息增益比来选择特征,以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的,这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢?有!CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。这和信息增益(比)是相反的。

    具体的,在分类问题中,假设有K个类别,第k个类别的概率为pk, 则基尼系数的表达式为:

    Gini§=∑k=1Kpk(1−pk)=1−∑k=1Kp2k
        如果是二类分类问题,计算就更加简单了,如果属于第一个样本输出的概率是p,则基尼系数的表达式为:

    Gini§=2p(1−p)
        对于个给定的样本D,假设有K个类别, 第k个类别的数量为Ck,则样本D的基尼系数表达式为:

    Gini(D)=1−∑k=1K(|Ck||D|)2

    特别的,对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分,则在特征A的条件下,D的基尼系数表达式为:

    Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)
        大家可以比较下基尼系数表达式和熵模型的表达式,二次运算是不是比对数简单很多?尤其是二类分类的计算,更加简单。但是简单归简单,和熵模型的度量方式比,基尼系数对应的误差有多大呢?对于二类分类,基尼系数和熵之半的曲线如下:

    从上图可以看出,基尼系数和熵之半的曲线非常接近,仅仅在45度角附近误差稍大。因此,基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。同时,为了进一步简化,CART分类树算法每次仅仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。这样一可以进一步简化基尼系数的计算,二可以建立一个更加优雅的二叉树模型。

    2. CART分类树算法对于连续特征和离散特征处理的改进

    对于CART分类树连续值的处理问题,其思想和C4.5是相同的,都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同,C4.5使用的是信息增益比,则CART分类树使用的是基尼系数。

    具体的思路如下,比如m个样本的连续特征A有m个,从小到大排列为a1,a2,…,am,则CART算法取相邻两样本值的平均数,一共取得m-1个划分点,其中第i个划分点Ti表示为:Ti=ai+ai+12。对于这m-1个点,分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at,则小于at的值为类别1,大于at的值为类别2,这样我们就做到了连续特征的离散化。要注意的是,与ID3或者C4.5处理离散属性不同的是,如果当前节点为连续属性,则该属性后面还可以参与子节点的产生选择过程。

    对于CART分类树离散值的处理问题,采用的思路是不停的二分离散特征。

    回忆下ID3或者C4.5,如果某个特征A被选取建立决策树节点,如果它有A1,A2,A3三种类别,我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同,他采用的是不停的二分,还是这个例子,CART分类树会考虑把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三种情况,找到基尼系数最小的组合,比如{A2}和{A1,A3},然后建立二叉树节点,一个节点是A2对应的样本,另一个节点是{A1,A3}对应的节点。同时,由于这次没有把特征A的取值完全分开,后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同,在ID3或者C4.5的一棵子树中,离散特征只会参与一次节点的建立。

    3. CART分类树建立算法的具体流程

    上面介绍了CART算法的一些和C4.5不同之处,下面我们看看CART分类树建立算法的具体流程,之所以加上了建立,是因为CART树算法还有独立的剪枝算法这一块,这块我们在第5节讲。

    算法输入是训练集D,基尼系数的阈值,样本个数阈值。

    输出是决策树T。

    我们的算法从根节点开始,用训练集递归的建立CART树。

    1) 对于当前节点的数据集为D,如果样本个数小于阈值或者没有特征,则返回决策子树,当前节点停止递归。

    2) 计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归。

    3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数,对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和上篇的C4.5算法里描述的相同。

    4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2.

    5) 对左右的子节点递归的调用1-4步,生成决策树。

    对于生成的决策树做预测的时候,假如测试集里的样本A落到了某个叶子节点,而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

    4. CART回归树建立算法

    CART回归树和CART分类树的建立算法大部分是类似的,所以这里我们只讨论CART回归树和CART分类树的建立算法不同的地方。

    首先,我们要明白,什么是回归树,什么是分类树。两者的区别在于样本输出,如果样本输出是离散值,那么这是一颗分类树。如果果样本输出是连续值,那么那么这是一颗回归树。

    除了概念的不同,CART回归树和CART分类树的建立和预测的区别主要有下面两点:

    1)连续值的处理方法不同

    2)决策树建立后做预测的方式不同。

    对于连续值的处理,我们知道CART分类树采用的是用基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型,但是对于回归模型,我们使用了常见的和方差的度量方式,CART回归树的度量目标是,对于任意划分特征A,对应的任意划分点s两边划分成的数据集D1和D2,求出使D1和D2各自集合的均方差最小,同时D1和D2的均方差之和最小所对应的特征和特征值划分点。表达式为:

    minA,s[minc1∑xi∈D1(A,s)(yi−c1)2+minc2∑xi∈D2(A,s)(yi−c2)2]
        其中,c1为D1数据集的样本输出均值,c2为D2数据集的样本输出均值。

    对于决策树建立后做预测的方式,上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别,它采用的是用最终叶子的均值或者中位数来预测输出结果。

    除了上面提到了以外,CART回归树和CART分类树的建立算法和预测没有什么区别。

    5. CART树算法的剪枝

    CART回归树和CART分类树的剪枝策略除了在度量损失的时候一个使用均方差,一个使用基尼系数,算法基本完全一样,这里我们一起来讲。

    由于决策时算法很容易对训练集过拟合,而导致泛化能力差,为了解决这个问题,我们需要对CART树进行剪枝,即类似于线性回归的正则化,来增加决策树的泛化能力。但是,有很多的剪枝方法,我们应该这么选择呢?CART采用的办法是后剪枝法,即先生成决策树,然后产生所有可能的剪枝后的CART树,然后使用交叉验证来检验各种剪枝的效果,选择泛化能力最好的剪枝策略。

    也就是说,CART树的剪枝算法可以概括为两步,第一步是从原始决策树生成各种剪枝效果的决策树,第二部是用交叉验证来检验剪枝后的预测能力,选择泛化预测能力最好的剪枝后的数作为最终的CART树。

    首先我们看看剪枝的损失函数度量,在剪枝的过程中,对于任意的一刻子树T,其损失函数为:

    Cα(Tt)=C(Tt)+α|Tt|
        其中,α为正则化参数,这和线性回归的正则化一样。C(Tt)为训练数据的预测误差,分类树是用基尼系数度量,回归树是均方差度量。|Tt|是子树T的叶子节点的数量。

    当α=0时,即没有正则化,原始的生成的CART树即为最优子树。当α=∞时,即正则化强度达到最大,此时由原始的生成的CART树的根节点组成的单节点树为最优子树。当然,这是两种极端情况。一般来说,α越大,则剪枝剪的越厉害,生成的最优子树相比原生决策树就越偏小。对于固定的α,一定存在使损失函数Cα(T)最小的唯一子树。

    看过剪枝的损失函数度量后,我们再来看看剪枝的思路,对于位于节点t的任意一颗子树Tt,如果没有剪枝,它的损失是

    Cα(Tt)=C(Tt)+α|Tt|
        如果将其剪掉,仅仅保留根节点,则损失是

    Cα(T)=C(T)+α

    当α=0或者α很小时,Cα(Tt)<Cα(T) , 当α增大到一定的程度时
    Cα(Tt)=Cα(T)
    。当α继续增大时不等式反向,也就是说,如果满足下式:

    α=C(T)−C(Tt)|Tt|−1
        Tt和T有相同的损失函数,但是T节点更少,因此可以对子树Tt进行剪枝,也就是将它的子节点全部剪掉,变为一个叶子节点T。

    最后我们看看CART树的交叉验证策略。上面我们讲到,可以计算出每个子树是否剪枝的阈值α,如果我们把所有的节点是否剪枝的值α都计算出来,然后分别针对不同的α所对应的剪枝后的最优子树做交叉验证。这样就可以选择一个最好的α,有了这个α,我们就可以用对应的最优子树作为最终结果。

    好了,有了上面的思路,我们现在来看看CART树的剪枝算法。

    输入是CART树建立算法得到的原始决策树T0。

    输出是最优决策子树Tα。

    算法主要过程如下:

    1)初始化αmin=∞,k=0,T=T0, 最优子树集合ω={T}。

    2)从叶子节点开始自下而上计算各内部节点t的训练误差损失函数Cα(Tt)(回归树为均方差,分类树为基尼系数), 叶子节点数|Tt|,以及正则化阈值α=min{C(T)−C(Tt)|Tt|−1,αmin}, 更新αmin=α
        3) αk=αmin。

    4)自上而下的访问子树t的内部节点,如果C(T)−C(Tt)|Tt|−1≤αk时,进行剪枝。并决定叶节点t的值。如果是分类树,则是概率最高的类别,如果是回归树,则是所有样本输出的均值。这样得到αk对应的最优子树Tk
        5)最优子树集合ω=ω∪Tk
        6) k=k+1,T=Tk, 如果T不是由根节点单独组成的树,则回到步骤2继续递归执行。否则就已经得到了所有的可选最优子树集合ω.

    7) 采用交叉验证在ω选择最优子树Tα

    6. CART算法小结

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

    算法 支持模型 树结构 特征选择 连续值处理 缺失值处理 剪枝
    ID3 分类 多叉树 信息增益 不支持 不支持 不支持
    C4.5 分类 多叉树 信息增益比 支持 支持 支持
    CART 分类,回归 二叉树 基尼系数,均方差 支持 支持 支持
        看起来CART算法高大上,那么CART算法还有没有什么缺点呢?有!主要的缺点我认为如下:

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

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

    1. 决策树算法小结
          终于到了最后的总结阶段了,这里我们不再纠结于ID3, C4.5和 CART,我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。这部分总结于scikit-learn的英文文档。

    首先我们看看决策树算法的优点:

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

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

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

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

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

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

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

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

    我们再看看决策树算法的缺点:

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

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

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

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

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

    以上就是决策树的全部内容了,里面有很多我个人思考的逻辑在,希望能对大家有所帮助,有错误的话请指正。

    展开全文
  • [决策树算法原理上](https://www.cnblogs.com/pinard/p/6050306.html) [决策树算法原理下](https://www.cnblogs.com/pinard/p/6053344.html) [scikit-learn决策树算法类库介绍]...
    [决策树算法原理上](https://www.cnblogs.com/pinard/p/6050306.html)
    [决策树算法原理下](https://www.cnblogs.com/pinard/p/6053344.html)
    [scikit-learn决策树算法类库介绍](https://www.cnblogs.com/pinard/p/6056319.html)
    
    展开全文
  • 树的叶子节点表示对象所属的预测结果,主要有ID3,C4.5和CART三种基础决策树 一、ID3算法 1、算法原理 ID3是采用信息增益作为特征选择的标准,信息增益上一篇博客有介绍,公式如下: 信息增益越大,说明此按此特征...

    决策树系列目录(文末有大礼相送
    决策树①——信息熵&信息增益&基尼系数
    决策树②——决策树算法原理(ID3,C4.5,CART)
    决策树③——决策树参数介绍(分类和回归)
    决策树④——决策树Sklearn调参(GridSearchCV)
    决策树⑤——Python代码实现决策树
    决策树应用实例①——泰坦尼克号分类
    决策树应用实例②——用户流失预测模型
    决策树应用实例③——银行借贷模型
    决策树应用实例④——淘宝&京东白条(回归&均方差&随机森林)

    决策树是一种运用统计概率分析的机器学习方法。它表示对象属性和对象值之间的一种映射,树中的每一个节点表示对象属性的判断条件,其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果,主要有ID3,C4.5和CART三种基础决策树

    一、ID3算法

    1、算法原理

    ID3是采用信息增益作为特征选择的标准,信息增益上一篇博客有介绍,公式如下:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    信息增益越大,说明此按此特征分类后越能消除信息的不确定性。

    2、算法过程

    ① 计算训练集所有样本的信息熵
    ② 计算按每一特征分类后的信息增益
    ③ 选择信息增益最大的特征进行分类,得到子节点
    ④ 在还未被选择的特征中迭代②和③,直到无特征可分或信息增益已经无法达到要求的标准时,算法终止

    二、C4.5算法

    1、算法原理

    ID3算法有2大缺点:1是类别越多的特征计算出的信息增益越大,易导致生成的决策树广而浅;2是只能处理离散变量,不能处理连续变量。

    C4.5是在ID3的算法基础上,采用信息增益率来做为特征选择,通过增加类别的惩罚因子,规避了类别越多信息增益越大的问题,同时也可以对连续变量通过均值离散化的方式,解决无法处理连续变量的问题。

    信息增益率的公式上一篇博客有介绍:
    在这里插入图片描述
    在这里插入图片描述
    2、算法过程
    ① 计算训练集所有样本的信息熵
    ② 计算按每一特征分类后的信息增益率
    ③ 选择信息增益率最大的特征进行分类,得到子节点
    ④ 在还未被选择的特征中迭代②和③,直到无特征可分或信息增益率已经无法达到要求的标准时,算法终止

    三、CART算法

    1、原理
    C4.5虽然解决了ID3的两大问题,但是仍有自己的缺憾,那就是不能处理回归问题,CART因此诞生。
    CART不再通过信息熵的方式选取最优划分特征,而是采用基尼系数,也叫基尼不纯度,两者衡量信息量的作用相当,但是基尼系数由于没有对数运算,可大大减少计算开销
    公式如下:
    在这里插入图片描述
    在这里插入图片描述
    CART算法处理分类问题时,以叶子节点上样本投票预测类别,处理回归问题时,以叶子节点的样本均值作为预测值

    2、算法过程

    ① 计算训练集所有样本的基尼系数
    ② 计算某一特征下每一属性划分后左右两边的基尼系数,找到基尼系数和最小的划分属性
    ③ 将每一个特征均按②中的方法计算,得到每一个特征最佳的划分属性
    ④ 对比③中每一个特征的最优划分属性下的基尼系数和,最小的就是最优的划分特征
    ⑤ 按最优的特征及最优属性划分,得到子节点
    ⑥ 在还未被选择的特征中迭代②-⑤,直到无特征可分或信息增益率已经无法达到要求的标准时,算法终止

    四、决策树应用场景

    可以用于二元或多元分类,以及回归,下面是我想到的一些业务场景:
    ① 判断什么样的用户流失概率最高
    ② 根据用户的消费属性,判断是否可以打白条,以及白条金额上限设定
    ③ 如何预测未来一段时间内,哪些顾客会流失,哪些顾客最有可能成为VIP客户
    ④ 如何根据用户的历史相亲情况,匹配最佳相亲对象等
    ……


    本人互联网数据分析师,目前已出ExcelSQLPandasMatplotlibSeaborn机器学习统计学个性推荐关联算法工作总结系列。


    微信搜索并关注 " 数据小斑马" 公众号,回复“机器学习”就可以免费领取下方机器学习—周志华、统计学习方法-李航等9本经典书籍
    在这里插入图片描述

    展开全文
  • 决策树算法原理详解

    2018-07-03 19:23:10
    决策树算法效果评估 决策树生成算法 ID3算法 ID3算法优缺点 C4.5算法 8 CART算法 8 ID3\C4.5\CART分类回归树算法总结 分类树和回归树的区别 决策树优化策略 决策树的剪枝 决策树剪枝过程 附录:
  • (作者:陈玓玏) 决策树的本质是什么?是将特征空间逐级划分,如下图过程所示: ...图示就是每次都找不同的切分点,将样本空间逐渐进行细分,...基本的决策树算法有三类,按时间顺序分别是:ID3、C4.5、CART。...
  •   在决策树算法原理(上)这篇里,我们讲到了决策树里ID3算法,和ID3算法的改进版C4.5算法。对于C4.5算法,我们也提到了它的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能...
  • 决策树算法原理

    千次阅读 2017-07-15 01:27:51
    本文就对决策树算法原理做一个总结,上篇对ID3, C4.5的算法思想做了总结,下篇重点对CART算法做一个详细的介绍。选择CART做重点介绍的原因是scikit-learn使用了优化版的CART算法作为其决策树算法的实现。 1. ...
  • 决策树算法原理及实现

    千次阅读 2019-03-08 18:47:08
    决策树算法原理及实现 转载自:https://www.cnblogs.com/sxron/p/5471078.html (一)认识决策树 1、决策树分类原理  决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似...
  • 决策树算法原理以及决策树规则生成方法 决策树是一种可解释性较强的策略分析工具。creditmodel提供了分类回归树和条件推断树两种决策树生成和提取规则的方法。 每一个风险管理人员都应该掌握使用决策树发现规则和对...
  • 基本的决策树知识不再赘述,只记录难点 决策树节点的划分依据: 1.基于信息增益的划分(ID3算法:信息增益;C4.5算法:信息增益率) 2.基于基尼系数的划分(CART算法)(更常用) 信息增益的预备知识:信息熵 定义:...
  • 决策树CART算法原理的理解

    千次阅读 2019-03-03 20:58:54
    决策树CART算法原理理解一、CART回归决策树算法原理(一)、回归树的生成最优特征及最优切分点的选择(二)、最小二乘回归树生成算法二、CART分类树算法原理(一)、分类树的生成最优特征及最优切分点的选择(二)、...
  • 本文详细总结了CART树,包括了CART分类树和CART回归树,给出了相关的推导和思想,然后重点介绍了决策树的剪枝,最后总结了决策树的优缺点。
  • 决策树算法原理(上)

    2019-07-19 17:54:00
    本文就对决策树算法原理做一个总结,上篇对ID3, C4.5的算法思想做了总结,下篇重点对CART算法做一个详细的介绍。选择CART做重点介绍的原因是scikit-learn使用了优化版的CART算法作为其决策树算法的实现。 一、决策...
  • 决策树算法原理(下)

    2019-07-19 17:54:00
    决策树算法原理(上)这篇里,我们讲到了决策树里ID3算法,和ID3算法的改进版C4.5算法。对于C4.5算法,我们也提到了它的不足,比如模型是用较为复杂的熵来度量,使用了相对较为复杂的多叉树,只能处理分类不能处理...
  • 决策树算法原理及只用numpy的代码实现1. 算法原理代码实现代码测试查看决策树的分裂详情:叶子节点:查看每个变量的最佳分裂点查看特征重要度排序预测 1. 算法原理 决策树本身的原理其实很好理解,就是不断做双向...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,403
精华内容 2,561
关键字:

cart决策树算法原理