决策树主要包括ID3，C4.5以及CART。下面给出三种算法的说明：
C4.5是ID3的改进版，而CART是最常用的，因此本文主要介绍CART。
首先看下面表格中的示例数据(随机生成，仅供参考)。其中类似年龄，身高，月收入为连续变量，学历，工作为离散变量。
-
如果把动心视为目标变量，此问题为分类问题。
-
如果把动心度视为目标变量，此问题为回归问题。
| 编号 | 年龄 | 学历 | 工作 | 月收入(k) | 身高(cm) | 动心 | 动心度 |
|---|---|---|---|---|---|---|---|
| 0001 | 24 | 专科 | 国企 | 5 | 175 | N | 0.56 |
| 0002 | 35 | 博士 | 国企 | 13 | 180 | N | 0.49 |
| 0003 | 27 | 硕士 | 私企 | 13 | 173 | Y | 0.76 |
| 0004 | 23 | 硕士 | 私企 | 5 | 180 | N | 0.67 |
| 0005 | 30 | 硕士 | 国企 | 5 | 166 | N | 0.58 |
| 0006 | 22 | 硕士 | 国企 | 13 | 166 | Y | 0.60 |
| 0007 | 28 | 博士 | 国企 | 5 | 175 | Y | 0.73 |
| 0008 | 38 | 博士 | 私企 | 19 | 180 | N | 0.40 |
| 0009 | 23 | 专科 | 私企 | 13 | 175 | N | 0.52 |
| 0010 | 30 | 博士 | 国企 | 13 | 173 | Y | 0.88 |
CART的目的是生成一个类似下面这样的树：分类树或者回归树。
叶子节点若为Y或者N，是分类树；若是数字，则为回归树。下面分别讲述回归树和分类树的生成方式：
-
分类树
ID3算法使用信息增益来选择特征，信息增益大的优先选择，这种方式会使得特征值较多的特征容易被选择【示例数据中的学历可能会比工作优先选择，因为学历有3个值，而工作有2个值】。
在C4.5算法中，采用了信息增益比来选择特征，改进了ID3容易选择特征值多的特征的问题。C4.5也是优先选择较大的。
上述2者都是基于信息论的熵模型的，这里面会涉及对数运算，因此计算成本较大。
CART分类树算法使用基尼系数，既减少了计算成本，又保留了熵这种运算形式的优点。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。
-
基尼系数
对于一个样本集合S，假设其包含m个不同的值，这m个值可看作m个不同的类。其中由类i组成的集合为Si，那么对于属于类i的样本点k而言，其概率为P(k)=集合Si的样本个数除去集合S的样本个数。则基于概率分布的基尼指数定义如下：
其中符号||为计算集合内元素个数的符号，对于m等于2的情况，上面的式子等价与
如果样本集合S，被某个规则R划分为n个数据子集，分别为S1， S2，……， Sn，则此时的计算基尼系数公示如下：
在CART算法中，上述n的值一定为2。因为每一次分裂，都是把数据集合一分为二。
针对离散、连续的变量，下面给出具体的计算基尼系数的步骤：
-
离散变量：以工作为例
- 将数据集合D分为Dg1=D(学历=国企)以及Dg2=D(学历!=国企)，其中Dg1中动心构成的集合为Mg1；Dg2中动心构成的集合为Mg2;
此时的基尼系数计算如下：
因为工作只有2个变量，因此按照工作为私企和工作为国企的基尼系数是相同的。
-
连续变量：以月收入为例
- 首先将月收入的值去重后，按照从小到大的排列顺序为[5, 13, 19],相邻的数值取平均值得到序列[9, 16]。类似于离散变量的情况，以9为例：将数据集分为Dn9=D(月收入<9)以及Dm9=D(月收入>9)，相应的动心组成的集合分别为Mn9,Mm9。
下面给出计算基尼系数的过程：
年龄的处理方式相似，假如不考虑年龄，只考虑月收入和工作，则按着月收入为16这个界限分类，是最优的，因为0.44是最小值。
- 树的输出
叶子节点数据集中，目标变量中占多数的类别，为这个叶子节点的输出类别。如果把上面给定的示例数据集看作一个叶子节点的话，如果某条数据正好落在这个数据集内，则这个数据的分类为N，因为这个数据集中有6条数据为N，多于为Y的数据条数。
-
-
回归树
以上面给出的示例数据为例，下面说明2种形式的变量生成回归树的方式。将数据集合定义为D，
-
离散变量：以学历为例
- 将数据集合D分为Dsp1=D(学历=专科)以及Dsp2=D(学历!=专科)，其中Dsp1中动心度构成的集合为Msp1，均值为asp1；Dsp2中动心度构成的集合为Msp2，均值为asp2；计算2个数据子集合的误差序列方差的和值：
类似于MSE(sp)，遍历所有学历中的值，得到下面的MSE(ms)，MSE(dr)。
其中
数据集Dms1=D(学历=硕士) 以及 Dms2=D(学历!=硕士)，Dms1中动心度构成的集合为Mms1，均值为ams1；Dms2中动心度构成的集合为Mms2，均值为ams2；
Ddr1=D(学历=博士) 以及 Ddr2=D(学历!=博士)，Ddr1中动心度构成的集合为Mdr1，均值为adr1；Ddr2中动心度构成的集合为Mdr2，均值为adr2
-
计算示例
得到以上结果后，MSE最小的为MSE(sp) ，其对应的特征值为专科，可以说特征学历最小的MSE为MSE(sp)，如果最终的最佳特征为学历，则以学历是否为专科作为分类标准。
-
连续变量：以身高为例
- 将身高的所有值去重后按照从小到大的顺序排列，得到集合H=[166,173,175,180], 取相邻两个数的中间值得到集合MH=[169.5,174,177.5],接下来的计算就类似于离散变量的情况，挨个遍历，把数据分为小于、大于这2个数据子集。以169.5为例，把数据集分为Dn169.5=D(身高<169.5)和Dm169.5=D(身高>169.5)，数据子集相应的动心度组成的集合分别为Mn169.5,Mm169.5,集合相应的均值为an169.5, am169.5。
174，177.5的符号命名规则类似，不一一赘述。
- 计算示例
可知对于特征身高最小的MSE为MSE(169.5)。如果最终的最佳特征是身高，则要把数据集分为身高高于169.5cm、以及不足169.cm的两部分数据子集。
从以上可以看出学历是比身高还要好的分类特征，是否为专科为最佳的分割变量。其他特征就不一一计算。到此，对离散、连续的变量的处理方式的说明已经结束。按照上述的方式就可以将分裂形成的数据集再次进行分裂，形成树。
-
树的输出
树是通过一个个叶子节点决定输出的。输出的方式也包括2种：
-
回归树：叶子节点代表的数据子集中目标变量的均值，就作为输出值。例如示例中的叶子节点，其输出值为0.56+0.52=0.54。当要预测的某条数据恰好属于这个数据子集，则针对这条数据的动心度的预测值就是0.54。
-
模型树：对于一个叶子节点来说，有输入，也有对应的输出。 根据输入和输出的关系，建立模型，这个模型可以是线性回归，也可以通过神经网络来建立。这个叶子节点的输出值是所建立的模型的输出值。当要预测的某条数据恰好属于这个数据子集，则针对这条数据的动心度的预测值就是将数据带入建立的模型中得到的值。
-
-
-
停止生长
上面说明了怎么生成一个树。当然树不能无限生长下去，这里说一下什么时候让某个数据子集停止分裂，也就是将这个数据子集形成一个叶子节点。一般有2种方式：
-
通过限制树的深度。树的深度和人们计算家谱有几代方式相同，只不过比其少一代。示例图中显示出来的树的深度是3， 如果是家谱的就可看作4代。
-
通过给定误差序列方差或者基尼系数的阈值，当这个数据集的MSE或者基尼系数小于这个阈值时，就不再分裂，停止生长。
-
-
树的剪枝
可以想象，如何让树无限的生长下去，最终会对每一条数据都生成一个叶子节点，这就导致了过拟合，降低了树的泛化能力。因此需要进行树的剪枝。所谓剪枝就是将某些已经分裂的数据集合，不让他分裂了。
剪枝策略主要分为两类：从上往下剪枝和从下往上剪枝。上往下剪枝也就是从根开始，遍历所有节点进行剪枝，称为预剪枝；从下往上剪枝是从叶节点开始从下往上剪枝，称为后剪枝。
- 预剪枝是在决策树生成过程中，对树进行剪枝，提前结束树的分支生长。
- 后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。
其实上文的停止生长，也可看作预剪枝，但是这样设置的目的不是剪枝，而是减小树的规模，提高后面真正剪枝的计算效率。
假设现在有一颗充分生长的树，我们希望减少树的大小来防止过拟合，但又担心去掉一些叶子节点后预测的误差会变大，如何达到这两个变量之间的平衡是问题的关键。从这这个角度可以引出比较常用的后剪枝策略：代价复杂剪枝。所谓代价复杂剪枝就是在树的规模(复杂)和树的误差(代价)之间寻求一个平衡。树规模越大，树的误差越小。树的规模越小，树的误差越大。
我们的目的是为了降低代价复杂度。令其为Ca(T)，其中T代表树。我们用树的叶子节点的个数描述树的规模，记为|T|， 树T的误差记为E(T)：
其中 a 为权重，a 越大，则树规模越小，树的误差越大；a 越小，则树规模越大，树的误差越小；
因为代价复杂度是和a有关系的，每一个a值都会得到最优树(代价复杂度最低的树)，并且每个a值对应的最优树是唯一的。当a值从0慢慢增大的时候，最优的树便会进入一个削剪枝叶的过程，最优树会从充分分裂后得到的树削剪到没有经过任何分裂的树。此时我们就形成了一个树的嵌套集合，并且前面的树包含后面的树。在形成的树的集合中，我们可以用交叉验证的方式得到最优的树，从而得到最终的树的结果。
现在的问题是如何实现a值慢慢增大。下面描述实现方式:
inter = 0 a(0) = 0 T(0) = 充分生长的树 while 树T(inter)不是仅有一个节点时： for node in 树T的内部节点(父节点)： 计算node为叶子节点时的E(T_Son_node) 计算node为父节点时的E(T_Fa_node) 计算g(node) =(E(T_Son_node) - E(T_Fa_node))/ (|T_Fa_node| - 1) 在所有的g(node)中选择值最小的对应的node，如果node不唯一，则选择辈分最小的node。 inter += 1 T(inter) = 树T(inter-1)的父节点node变为叶子节点形成的树 a(inter) = g(node) 从a(0)开始形成了从0逐渐变大的序列，从T(0)开始形成了从茂盛到精简的树的集合，下面利用验证数据集获取最优的a值以及对应的树： 1，计算验证数据集在每一个a值及其对应的树下的复杂代价度 2，选择复杂代价度最小的，就是最优的 符号说明： T_Son_node：当前的树T以node为叶子节点时的子树，也就是node节点没有经过分裂，也就是node节点剪枝后； T_Fa_node：当前的树T以node为根节点时的子树，也就是node节点分裂了，也就是node节点剪枝前； E(T)：树T所有叶子节点的误差(分类问题：误分率*样本比例，回归问题：误差平方和*样本比例）之和； |T|：树T的叶子节点的个数；下面给出分类的示例
上述问题中总的数据条数是40。因为分类问题，是以占多数的类别作为输出类别，因此两个数字中较小的数字除以数字之和就是误分率。样本比例就是这个节点占的数据条数除以总的数据条数。
g(t7)最小，节点t7应该被剪枝，a(1)=1/40，树T(1)变为下面这样：
回归和分类类似，将误分率变为误差平方和即可。
