决策树算法是从有类标号的训练元组中学习决策模型。常用的决策树算法有ID3，C4.5和CART。它们都是采用贪心(即非回溯的)方法，自顶向下递归的分治方法构造。这几个算法选择属性划分的方法各不相同，ID3使用的是信息增益，C4.5使用的是信息增益率，而CART使用的是Gini基尼指数。下面来简单介绍下决策树的理论知识。内容包含信息熵、信息增益、信息增益率以及Gini指数的概念及公式，最后介绍决策树算法。

1 理论基础

1.1 信息熵

信息熵是度量样本集合纯度最常用的一种指标。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。 所以，信息熵也可以说是系统有序化程度的一个度量。一般而言，随着划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

假定，当前样本集合$D$中第$k$类样本所占的比例为$p_k(k=1,2,...,|y|)$，其中$|y|$表示总共的分类个数，对$D$中的元组所有分类所有可能值的信息期望，即$D$的信息熵定义为：

\[Ent(D)=-\sum\limits_{k=1}^{|y|}P_k\log_2 P_k\]

$Ent(D)$的值越小，则$D$的纯度越高。$Ent(D)$的最小值为0，最大值为$\log_2 |y|$。

1.2 信息增益

现在我们假设将训练元组$D$按属性$a$进行划分，而$a$有$v$个可能的取值$\{a_1,a_2,...,a_v\}$，则$a$对$D$划分的期望信息为：

\[Ent_a(D)=\sum\limits_{i=1}^{v}\dfrac{|D^i|}{|D|}Ent(D^i)\]

其中$D^i$表示样本集$D$中所有在属性$a$上取值为$a_i$的样本集合，$|D^i|$表示样本集合$D^i$的总样本个数。
于是可以求得通过属性$a$对样本集$D$进行划分所获得的信息增益：

\[Gain(D,a)=Ent(D)-Ent_a(D)=Ent(D)-\sum\limits_{i=1}^{v}\dfrac{|D^i|}{|D|}Ent(D^i)\]

一般而言，信息增益越大，则意味着使用属性$a$来进行划分所获得的“纯度提升”越大。在ID3算法中优先选取信息增益大的，信息增益对可取值数目较多的属性有所偏好。

1.3 信息增益率

ID3算法存在一个问题，就是偏向于多值属性，C4.5使用信息增益率（gain ratio）的信息增益扩充，来克服这个偏倚。信息增益率的计算公式如下：

\[Gain\_ratio(D,a)=\dfrac{Gain(D,a)}{IV(a)} \\ IV(a)=-\sum\limits_{i=1}^{v}\frac{|D^i|}{|D|}\log_2 \frac{|D^i|}{|D|}\]

其中，$IV(a)$被称为属性$a$的固有值。属性$a$的可能取值数目（即$v$）越大，则$IV(a)$的值通常会越大。

C4.5选择具有最大增益率的特征作为分裂特征。[网上大部分的说法]
注意： 信息增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的作为划分属性，而是先选择信息增益高于平均水平的属性，然后再从中选择信息增益率最高的。[西瓜书上的说法]

1.4 Gini指数

基尼指数主要在CART算法中用到，随机森林中用到的属性划分标准也是它。它度量的是数据分区或训练元组集$D$的不纯度，表示的是一个随机选中的样本在子集中被分错的可能性。 计算方式如下：

\[Gini(D)=1-\sum\limits_{k=1}^{|y|}P_k^2\]

其中，当前样本集合$D$中第$k$类样本所占的比例为$p_k(k=1,2,...,|y|)$，$|y|$表示总共的分类个数。

$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小，数据集$D$的不纯度越小，相反纯度越高。

属性$a$的基尼指数定义为：

\[Gini\_index(D,a)=\sum\limits_{i=1}^{v}\frac{|D^i|}{|D|}Gini(D^i)\]

选择使得基尼指数最小的属性作为最优化分属性。

2 决策树算法

决策树（decision tree） 是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，递归的对剩下的属性进行测试，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树的生成是一个递归的过程。在决策树基本算法中有三种情形会导致递归返回：

1. 当前结点包含的样本全属于同一个类别，无需划分；
2. 当前的属性集为空，或是所有样本在所有属性集上取值相同，无法划分。此时，我们将当前结点标记为叶子结点，并将其类别设定为该结点所包含样本最多的类别；
3. 当前结点包含的样本集合为空，不能划分。我们同样将当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。

2.1 ID3

这个ID3算法可以归纳为以下几点：

1. 计算整个数据集的信息熵；
2. 分别计算以某个属性进行划分数据集时的信息熵，并联合整个数据集的信息熵计算信息增益；
3. 选取最大信息增益的属性最为分裂点；

ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。缺点是：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。

2.2 C4.5

C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点：

1. 用信息增益率来选择属性；
2. 在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过拟合（Overfitting），如果不考虑这些结点可能会更好；
3. 对非离散数据也能处理；
4. 能够对不完整数据进行处理。

C4.5的算法流程和ID3类似，只不过是计算信息增益率，然后选择信息增益率大的进行分裂。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。 其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

2.3 CART(分类回归树算法)

CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。

CART算法由以下两步组成：

1. 决策树生成： 就是递归地构建二叉决策树的过程，对回归树用平方差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树；
2. 决策树剪枝： 用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。

CART决策树既可以用于分类也可以用于回归，分类树与回归树的一个区别是：如果目标变量是离散型变量则用分类树，如果目标变量是连续型变量则用回归树。

2.3.1 分类树

分类树用基尼指数选择最优特征(与信息增益类似)，同时决定该特征的最优二值切分点。
对于二分类问题，若样本点属于第一个类的概率是$p$，则概率分布的基尼指数为：

\[Gini(p)=2p(1-p)\]

对于给定的样本集$D$，其基尼指数为：

\[Gini(D)=1-\sum\limits_{k=1}^{|y|}P_k^2\]

其中当$|y|=2$时，等式又可写为：

\[Gini(D)=2p(1-p)\]

如果样本集$D$根据属性$A$是否取某一可能值$a$被分割为$D_1$和$D_2$两部分，即：

\[D_1=\{(x,y)\in D|A(x)=a\}, D_2=D-D_1\]

则在属性$A$取值为$a$的条件下，样本集$D$的基尼指数定义为：

\[Gini(D,A=a)=\dfrac{|D_1|}{D}Gini(D_1)+\dfrac{|D_2|}{D}Gini(D_2)\]

CART分类树算法：
输入：训练数据集D。
输出：CART决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

1. 设结点的训练数据集为$D$，计算现有特征对该数据集的Gini系数。此时，是 对每一个特征$A$，对其可能取的每个值$a$，根据样本点对$A=a$的测试为“是”或 “否”将$D$分割成$D_1$和$D_2$两部分，计算A=a时的Gini系数。
2. 在所有可能的特征$A$以及它们所有可能的切分点$a$中，选择Gini系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
3. 对两个子结点递归地调用步骤l~2，直至满足停止条件。
4. 生成CART分类树。

2.3.2 回归树

回归树是用于目标变量是连续型变量的情况下，假设$X$与$Y$分别为输入和输出变量，并且$Y$是连续型变量，给定数据即$D=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$，根据训练数据集$D$生成决策树。 CART回归关键点是找到最优切分特征和最优切分点。

前面说过，回归树的生成准则是平方差(总离差平方和：实际观察值与一般水平即均值的离差总和)最小化准则，即预测误差最小化，所以我们的目的就是找到一个分界点，以这个点作为分界线将训练集$D$分成两部分$D_1$和$D_2$，并且使数据集$D_1$和$D_2$中各自的平方差最小。然后再分别从$D_1$和$D_2$中找类似的分界点，继续循环，直到满足终止条件。

注意： 算法中的变量$j$就是数据集中的特征，这里的$c_1$和$c_2$其实是两个子区域中输出值的均值。

3 连续值处理

当属性类型为离散型，无须对数据进行离散化处理；当属性类型为连续型，则需要对数据进行离散化处理。决策树算法针对连续属性的离散化处理，核心思想：将属性$A$的$N$个属性值按照升序排列；通过二分法将属性$A$的所有属性值分成两部分（共有$N-1$种划分方法，二分的阈值为相邻两个属性值的中间值）；接下来的选择最佳划分点过程和离散属性的选择过程类似，以基尼系数或信息增益作为度量，选择使信息增益最大或基尼系数最小的候选划分点作为最佳划分点。详细流程如下：

1. 将节点Node上的所有数据样本按照连续型属性$A$的具体取值，由小到大进行排列，得到属性$A$的属性值取值序列$(x_1^A,...,x_N^A)$。
2. 在序列$(x_1^A,...,x_N^A)$中共有$N-1$种二分方法，即共产生$N-1$个分隔阈值。对于第$i$种二分方法，其二分阈值$\theta_i=\dfrac{x_i^A+x_{i+1}^A}{2}$。它将该节点上的数据集划分为2个子数据集$(x_1^A,...,x_i^A)$和$(x_{i+1}^A,...,x_N^A)$。计算此种二分结果下的信息增益或基尼系数。
3. 分别计算$N-1$种二分结果下的信息增益或基尼系数，选取信息增益最大或基尼系数最小的二分结果作为对属性A的划分结果，并记录此时的二分阈值。

4 决策树剪枝

决策树很容易发生过拟合，也就是由于对train数据集适应得太好，反而在test数据集上表现得不好。这个时候我们要么是通过阈值控制终止条件避免树形结构分支过细，要么就是通过对已经形成的决策树进行剪枝来避免过拟合。另外一个克服过拟合的手段就是基于Bootstrap的思想建立随机森林(Random Forest)。

此处主要讨论决策树的剪枝操作，剪枝通常分为两类：“预剪枝(Pre-Pruning)” 和 “后剪枝(Post-Pruning)” ，其中预剪枝是指决策树生成过程中，对每个节点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶子节点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上的对非叶子结点进行考察，若将该节点对应的子树替换为叶子节点能带来决策树泛化能力提升，则将该子树替换为叶子结点。

4.1 预剪枝

预剪枝就是在树的构建过程（只用到训练集），先计算该结点在不划分分支的情况下验证集精度，然后在计算该结点在划分分支的情况下验证集精度，对比两个精度，如果划分后精度降低则将当前结点设置为叶子结点，不再进行划分。

优点： 预剪枝使很多分支没有展开，降低了过拟合的风险，减少决策树的训练时间开销和测试时间开销；
缺点： 容易产生欠拟合。

4.2 后剪枝

后剪枝算法有很多种，这里只介绍Reduced-Error Pruning(REP,错误率降低剪枝)：
这个思路很直接，为了避免过拟合，将数据集分为训练集和测试集，使用训练集生成一棵完整的决策树，然后通过测试数据集来纠正这棵决策树。算法流程如下：

1. 对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树；
2. 然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，那么该子树就可以替换成叶子节点；
3. 该算法以bottom-up(自底向上) 的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

优点： 欠拟合风险小，泛化能力优于预剪枝决策树；
缺点： 决策树训练时间开销大。

5 总结

优点：

• 计算简单，易于理解，可解释性强；
• 比较适合处理有缺失属性的样本；
• 能够处理不相关的特征；
• 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

缺点：

• 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
• 忽略了数据之间的相关性；
• 对于那些各类别样本数量不一致的数据，在决策树当中，信息增益的结果偏向于那些具有更多数值的特征（只要是使用了信息增益，都有这个缺点，如RF）。

参考文献

机器学习算法-决策树理论
算法杂货铺——分类算法之决策树(Decision tree)
分类算法：决策树（C4.5）
数据挖掘十大算法之CART详解
决策树-CART
统计学习方法：CART算法
CART之回归树构建
决策树的剪枝算法
决策树基础