决策树常用的算法包含：ID3、C4.5和CART。其总结如下表，本章主要关注
特征选择
：
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分类、回归 | 二叉树 | 基尼系数，均方差 | 支持 | 支持 | 支持 |
首先举一个例子引出特征选择问题：
下表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征：第1个特征是年龄，有三个可能值：青年，中年，老年；第2个特征是有工作，有2个可能值：是，否；第3个特征是有自己的房子，有两个可能值：是，否；第四个特征是信贷情况，有3个可能值：非常好，好，一般。表的最后一列是类别，是否同意贷款，取二个值：是，否。
信息增益
主要用于ID3算法决策树（其核心就是根据最大信息增益作为划分当前数据集的最好特征），用于处理离散的特征值，但不能处理特征为连续的情况。想要弄明白信息增益，首先要明白信息、信息熵和条件熵。
信息
：信息是用来消除随机不确定性的东西（引至香农的《通信的数学原理》）
信息熵
:信息熵是消除不确定性所需信息量的度量，也即未知事件可能含有的信息量。若不确定性越大，则信息量越大，熵越大；若不确定性越小，则信息量越小，熵越小。对于任意一个随机变量X，它的信息熵定义如下：
条件熵
：条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。其定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
信息增益
：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。其可以理解为信息熵与条件熵的差值。根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
信息增益计算公式：
特征选择过程举例：
信息增益比
信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，著名的C4.5决策树算法[Quinlan，1993]不直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优划分属性。信息增益比本质：是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不能直接选择增益率最大的候选划分属性，而是是使用了一个启发式[Quinlan，1993]:先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼(Gini)指数
Gini系数是一种与信息熵类似的做特征选择的方式，可以用来表示数据的不纯度。一般在CART算法中采用基尼指数构造二叉决策树（分类树）。Gini系统最早应用于经济学，用于衡量收入分配公平度的指标，基尼系数介于0-1之间，基尼系数越大，表示不平等程度越高（0-完全相等，1-完全不相等），当分布绝对均匀时候，取极值。一般取基尼指数最小的作为划分的依据。
特征选择过程举例：
首先计算各特征的基尼指数，选择最优特征以及最优切分点。分别以A1,A2,A3,A4表示年龄、有工作、有自己的房子和信贷情况4个特征，并以1，2，3表示年龄的值为青年、中年和老年，以1，2表示有工作和有自己的房子的值是和否，以1，2，3表示信贷情况的值为非常好、好和一般。
注：
-
为什么有了信息熵还要考虑采用基尼系数作为选择的方式？
在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
均方差
均方差常用于CART回归树算法，采用样本的最小方差作为特征选择的依据。方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。
回归方差计算公式：
举例说明
回归树总体流程：以年龄为例，预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄，如唯一，则直接取这个叶子节点上人的年龄即可。
参考：
《统计学习方法》- 李航
《机器学习》- 周志华
https://blog.csdn.net/u014688145/article/details/53326910
https://www.cnblogs.com/pinard/p/6053344.html