决策树在很多公司都实际运用于风险控制，之前阐述了决策树-ID3算法和C4.5算法和Python中应用决策树算法预测客户等级。
本文致力于让大家从原理出发，彻底理解CART决策树，为之后的机器学习算法：随机森林、GBDT、XGBoost、Lightgbm的学习打好扎实的基础。
本文目录
- CART树理解
- 分类CART树生成 2.1 基尼指数 2.2 应用基尼指数生成CART分类树实例
- 回归CART树生成 3.1 误差平方和 3.2 应用误差平方和生成CART回归树实例
- CART树剪枝
- ID3、C4.5、CART树对比总结
一、CART树理解
CART(classification and regression tree)树：又称为分类回归树，从名字可以发现，CART树既可用于分类，也可以用于回归。
当数据集的因变量是离散值时，可以采用CART分类树进行拟合，用叶节点概率最大的类别作为该节点的预测类别。
当数据集的因变量是连续值时，可以采用CART回归树进行拟合，用叶节点的均值作为该节点预测值。
但需要注意的是，该算法是一个二叉树，即每一个非叶节点只能引伸出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。
为了大家对CART树有一个更清晰的理解，先放一张理解图：
从上图知CART决策树分为分类CART树和回归CART树，只是在特征选择时一个采用基尼指数，一个采用残差平方和。
二、分类CART树生成
1 基尼指数(Gini index)
假设数据集D中有K个类，样本属于第K类的概率为pk，基尼指数Gini(D)表示集合D的不确定性(纯度)，公式如下：
从上面的公式可以发现，当数据集D中只有1个类时，pk=1，Gini(D)=0，说明基尼指数越小，样本纯度越高。
对于特征A，将集合D划分成D1和D2，基尼指数Gini(D,A)表示经过A=a划分后集合D的不确定性，公式如下：
其中|D|、|D1|、|D2|分别表示数据集D、D1、D2中样本数量。
2 应用基尼指数生成CART决策树实例
为了大家更清晰地理解公式，接下来阐述用基尼指数挑选特征建立CART决策树的实例。
表1 贷款申请样本数据表
首先计算各特征的基尼指数，选择最优特征以及最优切分点。为了公式的简洁，分别以A1、A2、A3、A4表示年龄、是否有工作、是否买房、信贷表现。
首先求特征A1的基尼指数，A1中有三个类别：青年、中年、老年，样本数量都是5，根据公式
假设要求Gini(D,A1=青年)的值，其中|D|表示整个数据集中样本个数，从编号知值为15，|D1|表示年龄是青年的样本个数，值为5，|D2|表示年龄不是青年的样本个数，值为10。
Gini(D1)表示青年这个类别的基尼指数，对应的Y有两种可能，一种是放贷(1)，另一种是不放贷(0)，代入公式可得：
同理可得Gini(D2)，故
同理可得
由于A2、A3只有一个切分点，所以算出来的基尼值相同，算其中一个即可。
从上面的计算可以知道，Gini(D,A3=0) =Gini(D,A3=1)=0.27最小，所以选择A3作为最优特征，A3=1或A3=0作为最优切分点，依次递归计算划分值，建立决策树如下：
由于t2这个子节点已经很纯了(只有放贷客户)，所以不需要再分裂，只需考虑t1这个节点，按t0节点同样的方法筛选变量进行分裂，具体计算结果如下：
从上面的计算知，Gini(D1,A2=0)=0最小，所以选择A2作为最优特征，A2=1或A2=0作为最优切分点，依次递归计算划分值，建立决策树如下：
由上面的决策树知，叶子节点t2、t3、t4都是纯的了，无需再进行划分。这只是理想数据，便于大家理解基尼指数，现实数据远远比这复杂，不过用Python处理也很方便。
三、回归CART树生成
1 误差平方和
如果之前对回归分析有了解的朋友应该知道，我们在预测模型时希望真实值和预测值越接近越好，说明预测误差小。
若yi表示训练集D={(x1,y1),(x2,y2),...,(xn,yn)}的输出变量，是连续值。f(xi)是预测值，则预测误差可以表示为：
我们拟合的目标就是寻找最佳划分特征里的最佳划分点，找到每一个f(xi)，使得误差平方和最小化。
把误差平方和应用到CART回归树中，数学表达式如下：
其中j、s分别表示第j个变量的划分点s，R1(j,s)表示在该划分下的左区域，R2(j,s)表示在该划分下的右区域，C1、C2为区域R1(j,s)、R2(j,s)的最优输出值(因变量均值)。
2 应用误差平方和生成CART回归树实例
为了大家更清晰地理解公式，接下来阐述应用误差平方和挑选特征建立CART回归树的具体实例。
为了得到这个问题的最小二叉回归树，首先需要选择特征切分点。
特征x包含了10个元素，且已排好序了，直接以(xi xi 1)/2，i∈{1,2,...,10}为切分点s，容易求得：
则C1、C2为：
其中N1、N2分别是R1、R2中的样本点数，C1、C2为R1、R2中的因变量均值。
针对x考虑如下切分点：1.5、2.5、3.5、4.5、5.5、6.5、7.5、8.5、9.5，可以求出相应的R1、R2、C1、C2，以及
例如，当s=1.5时，R1={1}，R2={2,3,...,10}，C1=5.56，C2=7.5，则
同理可得其它划分点的最小误差如下：
由上表知，当x=6.5时m(s)达到最小值，即此时误差平方和最小。此时R1={1,2,...,6}，R2={7,8,...,10}，C1=6.24、C2=8.9，所以回归树T1(x)为：
用f1(x)拟合训练数据的残差见下表，表中r2i=yi-f1(xi)(i=1,2,...1,10)。
第2步求T2(x)方法与求T1(x)，只是拟合的数据是上表的残差，可以得到：
可以根据此方法继续求解，直至拟合训练数据的误差平方和小于某个阈值时作为结束条件，那么f(x)=fi(x)即为所求回归树。
四、CART树剪枝
一般而言，训练集中预测值和真实值越接近说明拟合效果越好，但是有时数据过度地拟合训练数据，导致模型的泛化能力较差，在测试数据中的表现并不好。
为了防止模型发生过拟合，可以对“完全生长”的CART树底端剪去一些枝，使得决策树变小从而变得简单。
其实剪枝分为预剪枝和后剪枝，预剪枝是在构建决策树的过程中，提前终止决策树的生长，从而避免过多的节点产生。但是由于很难精确判断何时终止树的生长，导致预剪枝方法虽然简单但实用性不强。
后剪枝是在决策树构建完成之后，通过比较节点子树用叶子结点代替后的误差大小，如果叶子结点合并后误差小于合并前，则进行剪枝，否则不剪枝。
CART树采用后剪枝的策略，为了让大家彻底弄懂剪枝，首先来看几个和剪枝有关的函数。
1 损失函数
损失函数计算公式如下：
其中T是任意子树，C(T)为子树的预测误差，分类树用基尼指数，回归树用均方误差。
|T|是子树T的叶子节点个数，a是正则化参数，用来平衡决策树的预测准确度和树的复杂度。
a越大，表示惩罚越大，在求最小化损失函数Ca(T)时，要求子树的叶子节点个数越少，表示树越简单，剪枝越厉害。a越小，表示树越复杂。
2 误差增加率
1) 从整体树的任意内部节点t开始。
2) 以t为单节点的树的损失为：
3) 以t为根节点的树的损失为：
4) 如果Tt与t有同样的损失，且t的节点更少，那么t比Tt更可取，所以剪掉Tt，此时有Ca(t)=Ca(Tt)，根据2)和3)变形得：
这表示剪枝后整体损失函数增加的程度。其中C(t)表示节点t的子树被剪枝之后节点t的误差，C(Tt)表示节点t的子树没有被剪枝时子树Tt的误差。
C(t)=c(t)*p(t)，c(t)是节点的误差率，p(t)是节点上的数据占所有数据的比例。
剪枝之后决策树的叶子减少了|Tt|-1，|Tt|为子树Tt的叶子数。
为了更清晰地展示剪枝，借鉴参考文献4中的一个实例进行说明，具体决策树如下：
由上图知，决策树中训练样本总个数为80，对于节点t4，其中A类样本46个，B类样本4个，根据大多数原则，节点t4中样本为A类，故节点t4的子树(t8,t9)被剪枝之后的误差为：
节点t4的子树(t8,t9)被剪枝之前的误差为：
故误差增加率
按此方法，依次得到原始树T0中的4个非叶节点的误差增加率，如下表：
从上表知，原始树T0中的4个非叶节，t4节点剪枝后损失函数增加的程度最少，因此可以考虑首先裁剪t4下面的叶子节点，在图上展示如下：
同理可得，剪枝后树T1中的3个非叶节点的误差增加率，如下表：
从上表知，树T1中的3个非叶节点，虽然t2节点和t3节点剪枝后损失函数增加的程度一样少，但是裁剪t2节点的分枝可以得到更小的决策树，因此考虑裁剪t2下面的叶子节点，在图上展示如下：
由上图知，经过两轮剪枝后只剩一个非叶子节点，再剪就只剩根节点了。这个例子只是为了大家熟悉CART剪枝，所以比较理想化。
在现实应用中一般对误差增加率a设定一个阈值，小于该阈值则进行剪枝，否则保留。
五、ID3、C4.5、CART对比总结
之前已经介绍过ID3、C4.5算法，本文介绍了CART算法，为了大家对这几个算法有一个更系统的认识，总结如下：
至此，CART决策树已全部讲解完毕，感兴趣的同学可以自己推理一遍
。
参考文献
代码语言：javascript复制周志华《机器学习》
https://zhuanlan.zhihu.com/p/99855846
https://www.sohu.com/a/109389515_466874
https://www.pianshen.com/article/70041892550/
https://blog.csdn.net/xiaokang06/article/details/76685902
https://blog.csdn.net/qq_40587575/article/details/80219080
https://blog.csdn.net/qq_27717921/article/details/74784400
https://segmentfault.com/a/1190000022071836?utm_source=tag-newest
