cart决策树（cart决策树算法例题）

本篇文章给大家谈谈cart决策树，以及cart决策树算法例题对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、决策树之CART算法
• 2、CART算法
• 3、随机森林

决策树之CART算法

一、基本概念

1.cart使用基尼系数作为划分标准。基尼系数越小，则不纯度越低，区分的越彻底。

2.假设有k个类别，第k个类别的概率为 ,则基尼系数表达式为：

Gini(p)= (1- )=1-

3.对于样本D，如果根据特征A 的值把样本分为D1,D2两部分，则在特征A条件下，D的基尼系数

Gini(D,A)= Gini(D1)+  Gini(D2)

4.CART建立起来的是二叉树，如果特征A有A1,A2，A3三个类别，CART会考虑把A分成{A1},{A2 ,A3}两组，或者是其他两种情况。由于这次A并没有完全分开，所以下次还有机会在子节点把A2,A3分开.

5.对于连续值的切分.假如有1 2 3 4 5 那么cart会有4个切分点 [1.5  2.5  3.5  4.5]

二.实例推导树的建立过程

1.假设我有以下源数据

序号 天气 周末 促销 销量

1 坏 是 是 高

2 坏 是 是 高

3 坏 是 是 高

4 坏 否 是 高

5 坏 是 是 高

6 坏 否 是 高

7 坏 是 否 高

8 好 是 是 高

9 好 是 否 高

10 好 是 是 高

11 好 是 是 高

12 好 是 是 高

13 好 是 是 高

14 坏 是 是 低

15 好 否 是 高

16 好 否 是 高

17 好 否 是 高

18 好 否 是 高

19 好 否 否 高

20 坏 否 否 低

21 坏 否 是 低

22 坏 否 是 低

23 坏 否 是 低

24 坏 否 否 低

25 坏 是 否 低

26 好 否 是 低

27 好 否 是 低

28 坏 否 否 低

29 坏 否 否 低

30 好 否 否 低

31 坏 是 否 低

32 好 否 是 低

33 好 否 否 低

34 好 否 否 低

该数据集有三个特征  天气  周末   促销

2.为了简化建立树的过程,我将忽略基尼系数与样本个数阀值

2.1  首先计算各个特征值对数据集的基尼系数,公式见---- 基本概念.3

Gini(D|天气)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706

Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063

Gini(D|促销)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131

周末的基尼系数最小，这也符合我们的一般认识

2.2  第一个分列特征选择周末。此时数据集按照是否周末分成两个。

Gini(周末|天气)=0.2679

Gini(周末|促销)=0.2714

Gini(非周末|天气)=0.3505

Gini(非周末|促销)=0.3875

此时，周末应该以天气作为划分，非周末也是以天气作为划分，下面放个图

三、CART树对于连续特征的处理

假如特雹滑征A为连续型变量，则把特征A按照段磨从小到大进行排序，取相邻两点的平均值为切分点，计算基尼系数。则基尼系数最小的点为切分点，大于切分点的为一类，小于切分点的为另一类。举例：特征A的值为 1，2，3，4，5，6     目标变量是高、低、高、低、高、低。则1.5处的基尼系数为  (1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.4                                                2.5处的基尼系数为  (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5               握肆斗               3.5处的基尼系数为   (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44                          4.5处的基尼系数为   (4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5                            5.5处的基尼系数为    (5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4                                          结论：  1.5和5.5处的基尼系数最小，可以把1分为一类，2-6分为另一类。或者6分为一类，1-5另一类。

四、关于回归树

1.回归树和分类树的区别在于输出值类型不同。分类树输出的是离散值，回归树输出的是连续值。

2.和分类树使用基尼系数不同，回归树使用和均方差来度量最佳分隔点。假设有1 2 3 4 5 6 六个数。假设3.5处把数据分开最合适，那么(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割点中取得最小值。2，5为各自数据段的平均值。

3.回归树采用最后叶子的平均值或者中值作为输出结果

[img]

CART算法

CART算法就是分类回归念差树，它只支持二叉树，既可以作分类树，又可以作回归树。

那什么是分类树，什么是回归树呢？假如有个数据集，分别给出了，不同年龄、职业、性别的不同学习时间。如果我构造了一棵决策树，辩高仿想要基于数据判断这个人的职业身份，这个就属于分类树，因为是从几个分类中来做选择。如果是给定了数据，想要预测这个人的年龄，那就属于回归树。分类树可以处理离散数据，也就是数据种类有限的数据，它输出的是样本的类别，而回归树可以对连续型的数值进行预测，也就是数据在某个区间内都有携纤取值的可能，它输出的是一个数值。

CART算法属性指标是基尼系数。基尼系数本身反应了样本的不确定性。当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低。分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。所以CART算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分。  

随机森林

随机森林是一种集成算法(Ensemble Learning)，它属于Bagging类型，通过组合多个弱分类器，最终结果通过投票或取均值，使得整体模型的结果具有较高的精确度和泛化性能。其可以取得不错成绩，主要归功于 "随机"和“森林” ，一个使它具有抗过拟合能力，一个使它更加精准。

Bagging 是一种在原始数据集上通过有放回抽样重新选出k个新数据集来训练分类器的集成技术。它使用训练出来的分类器的集合来对新样本进行分类，然后用多数投票或者对输出求均值的方法统计所有分类器的分类结果，结果最高的类别即为最终标签。此类算法可以有效降低bias，并能够降低variance。

【 自助法 】它通过自助法（bootstrap）重采样技术，从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。

【OOB】 在Bagging的每轮随机采样中，训练集中大约有36.5%的数据没有被采样集采集中。 对于这部分没有采集到的数据，我们常常称之为袋外数据(Out of Bag, 简称OOB) 。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

【随机性】 对于我们的Bagging算法，一般会对样本使用boostrap进行随机采集，每棵树采集相同的样本数量，一般小于原始样本量。这样得到的采样集每次的内容都不同 ，通过这样的自助法生成K个分类树组成随机森林，做到样本随机性 。

【输出】 Bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到的最终的模型输出。

【弱兆碰分类器】 首先，RF使用了CART决策树作为弱学习器。换句话说，其实我们只是将实验CART决策树作为弱学习器的Bagging方法称为随机森林。

【随机性】 同时，在生成每棵树的时候， 每个树选取的特征都不仅仅是随机选出的少数特征，一般默认取特征总数m的开方。 而一般的CART树则会选取全部的特征进行建模。因此 ，不但特征是随机的，也保证了特征随机性 。

【样本量】 相对于一般的Bagging算法，RF会选择采集和训练集样本数N一样个数的样本。、

【特点】 由于随机性，对于降低模型的方差很有作用，故随机森林一般不需要额外剪枝，即可以取得较好的泛化能力和抗拟合能力(Low Variance)。当然对于训练集的拟合程度就会差一点，也就是模型的偏倚会大一些(High Bias)，仅仅是相对的。

在关于随机森林的原始论文中，显示随机森林错误率取决于两件事：

      森林中任何两棵树之间的相关性。增加相关性会增加森林错误率。

      森林中每棵树的力量(具有低错误率的树是强分类器)。增加单棵数据的强度(分类更精确)会降低森林错误率。

    随机森林的弱分类器使用的是CART树，CART决策树又称为分类回归树。当数据集的因变量为连续型数值时，该树算法就是一个回归树，可以用叶节点观察的均值作为预测值；当数据集的因变量为离散型数值时，该树算算法就是一个分类树，可以很好地解决分类问题。但是需要注意的是，该算法是一个二叉树，即每一个叶节点只能引申出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。同时，若某个非叶节点是连续变量时，决策树也将把他当做离散变量来处理族雀谈(即在有限的可能值中做划分)。

    特征选择目前比较流行的方法是信息增益、增益率、基尼系数和卡方检验。这里主要介绍基于基尼系数(Gini)的特征选择，因为随机森林采用的CART决策树就是基于基尼系数选择特征的。

    基尼系数的选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一分类，此岁喊时基尼系数最小，纯度最高，不确定度最小。对于一般的决策树，加入总共有K类，样本属于第K类的概率：pk,则该概率分布的基尼指数为：

基尼指数越大，说明不确定性就越大；基尼系数越小，不确定性越小，数据分割越彻底，越干净。

对于CART树而言，由于是二叉树，可以通过下面的表示：

在我们遍历每个特征的每个分割点时，当使用特征A=a，将D划分为两部分，即D1（满足A=a的样本集合），D2（不满足A=a的样本集合）。则在特征A=a的条件下D的基尼指数为：

Gini(D)：表示集合D的不确定性。

Gini(A,D)：表示经过A=a分割后的集合D的不确定性。

随机森林中的每棵CART决策树都是通过不断遍历这棵树的特征子集的所有可能的分割点，寻找Gini系数最小的特征的分割点，将数据集分成两个子集，直至满足停止条件为止。

    首先，正如Bagging介绍中提到的，每个树选择使用的特征时，都是从全部m个特征值随机产生的，本身就已经降低了过拟合的风险和趋势。模型不会被特定的特征值或特征组合所决定，随机性的增加，将控制模型的拟合能力不会无限提高。

    第二，与决策树不同，RF对决策树的简历做了改进。对于普通的决策树，我们会在节点上所有的m个样本特征中选择一个最优的特征来做决策树的左右子树划分。但是RF的每个树，其实选用的特征是一部分，在这些少量特征中，选择一个最优的特征来做决策树的左右子树划分，将随机性的效果扩大，进一步增强了模型的泛化能力。

    假设每棵树选取msub个特征，msub越小，此时模型对于训练集的拟合程度会变差，偏倚增加，但是会泛化能力更强，模型方差减小。msub越大则相反。在实际使用中，一般会将msub的取值作为一个参数，通过开启OOB验证或使用交叉验证，不断调整参数以获取一个合适的msub的值。

优点：

    （1）由于采用了集成算法，本身精度比大多数单个算法要好。

    （2）在测试集上表现良好，由于两个随机性的引入，使得随机森林不容易陷入过拟合( 样本随机，特征随机 )

    （3）在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定优势。

    （4）由于树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类(拟合)模型。

    （5） 它能够处理很高维度(feature很多)的数据 ，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。

    （6）训练速度快，可以运用在大规模数据集上。

    （7）由于袋外数据(OOB)，可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量。

    （8）在训练过程中，能够检测到feature间的互相影响， 且可以得出feature的重要性 ，具有一定参考意义。

    （9）由于每棵树可以独立、同时生成，容易做成并行化方法。

    （10）由于实现简单、 精度高、抗过拟合能力强 ，当面对非线性数据时，适于作为基准模型。

缺点：

    （1）随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过拟合。（PS:随机森林已经被证明在某些噪音较大的分类或者回归问题上会过拟合）

（2）对于许多统计建模者来说，随机森林给人感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。

（3）可能有很多相似的决策树，掩盖了真实的结果。

（4）对于小数据或者低维数据(特征较少的数据)，可能不能产生很好的分类。( 处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处 )。

（5）执行数据虽然比boosting等快，但是比单棵决策树慢多了。

（1） 不要求是线性特征，比如逻辑回归很难处理类别型特征 ，而树模型，是一些决策树的集合，可以很容易的处理这些情况。

（2） 由于算法构建的过程，这些算法很容易处理高维的数据，大量的训练数据的场景 。

极端随机树是随机森林的一个变种，原理几乎和RF一模一样，仅有区别有：

（1）对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。

（2）在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是极端随机树比较的激进，他会随机的选择一个特征值来划分决策树。

关于cart决策树和cart决策树算法例题的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。