一、决策树简介
决策树（Decision Tree）是一种基于信息论的启发式的监督模型，决策树背后的生成算法依赖于衡量当前数据划分的信息量，它会不断地寻找数据的划分方法，使得在当前的划分下能取得最大的“信息量”， 根据“信息量”衡量方式的不同，常见的决策树算法又可以分成ID3, C4.5， CART，这些算法的生成方式的不同取决于信息量的度量方式不同，在正式介绍各种决策树算法之前，我们先详细介绍一下信息的度量方式——不确定性。
1.1不确定性（Uncertainty）
在决策树的生成过程中，每次划分获取的信息量的多少是从反方向来定义的，即：若某种划分能使得数据的“不确定性”减少的更多，则意味着该种划分能够获得更多的信息。因从问题的关键就是在于如何度量数据的不确定性（Uncertainty）或者是不纯度（Impurity）。常见的不确定性度量方式有：信息熵（Entropy）和基尼系数（Gini Coefficient）。
信息熵（Entropy）
信息熵的公式如下所示：
对于具体的随机变量，在实际的操作中我们通常利用其在实际的数据集
上的经验熵来估计真实的信息熵， 即：
这里假设随机变量的取值空间为
，然后在观测空间上以观测频率
来估计概览
。通常来说，公式中对数的底会取2，此时的信息熵
的单位又称之为比特（bit）；如果把对数取为自然对数，则
的单位称之为纳特（nat）。通过观测信息熵的公式我们可以发现，当：
时，会取到最大值
，也就是
。
基尼系数（Gini Coefficient）
基尼系数的定义相比信息熵会显得更简单一些，公式如下：
同样的我们也可以在观测数据集上，利用观测来得到经验基尼系数：
同样的，通过观测Gini系数的公式，我们也可以得出这样的结果，当
时，此时的
取得最大值
。
1.2信息的增益（Information Gain）
在定义完不确定性的度量之后，接下来我们看一下如何获得信息。信息增益时针对随机变量和特征变量
来说的，所谓的信息增益指的就是特征变量
所能给我们带来的关于y的“信息量的大小”。为此我们引入条件熵的概念来定义信息的增益。
条件熵（ Conditional Entropy）
所谓条件熵，值得就是根据特征变量的不同取值
对变量
进行限制后，先对这些被限制的
分别计算信息熵，然后把这些信息熵根据本身的概率进行加权求和，从而得到总的条件熵。换句话说，条件熵是由被特征变量
的不同取值限制的各个部分的
的不确定性乘以
d的不同取值的概率加强得到的。因此条件熵
越小，意味变量
着被特征变量
限制后的总的不确定性就越小。条件熵的公式如下：
其中：
因此：
从条件熵的直观含义，我们可以很轻松地得出信息增益的衡量方式，也就是互信息（Mutual Information）。
互信息（Mutual Information）
ID3算法中使用互信息进行信息增益的度量，其公式如下：
根据互信息的公式我们可以知道，如果简单的以作为特征选择的标准的化，会存在偏向于选择取值较多的特征，因为变量
如果被特征变量
划分成更多份的话，其不确定性自然会减少更多，这从直观上也很好理解。但是这种情况下会使得到的决策树更倾向于一个“矮胖”的决策树，但这并不是我们想要的，因为决策树越“矮胖”表明参与到决策中的特征数量就越少，决策树的决策结果就越片面，因此单纯以
作为标准，并不能得到一个拟合效果更好的决策树。为了解决这个问题，我们可以通过在特征
上针对类别数量
增加一个相应的惩罚，这样就得到了信息增益比（Information Gain Ratio）。
信息增益比（Information Gain Ratio）
信息增益比是C4.5算法在生成决策树过程中用到的评估方法，其公式为：
其中是
关于
的熵，其定义为：
基尼增益（Gini Gain）
基尼增益是类比上述的条件熵和互信息的，因此同样也可以利用基尼系数来定义信息的增益。类比条件熵，可以先定义条件基尼系数：
其中：
这样的话，基于Gini系数的信息增益可以自然地定义为：
二、ID3（Interactive Dichotomizer-3， 交互式二分法）
虽然ID3算法的名字里带有“二分”的含义，但是ID3算法完全适用于“多分”的场景。ID3算法选择信息增益作为特征选择和划分的度量依据，算法过程如下：
input：训练数据集
， 样本类别空间
steps：
(1)将数据集喂给一个Node；
(2)若，则该Node不再继续生成，并将其类别标记为
(3)若特征已经是0维向量，亦即没有特征可选，此时将数据集
(4)否则，按照互信息的定义计算每列特征的信息增益：
然后选择使得信息增益最大的特征
作为划分标准。
(5)若
(6)否则，根据特征，将数据集
，同时将特征
的第
列去掉，使其变成
列的特征向量。
(7)对于每个划分出来的数据集，从step(1)开始递归调用当前生成过程。
outpt：原始数据对应的根节点Node。
其中算法第（5）步中的停止条件又称之为“预剪枝”，是一种防止当前决策树过拟合的手段，常用的方法有几种：
- 决策树深度达到某个固定深度，则停止。
- 若选择
小于某一传入的截断阈值
，则停止。
- 采用交叉验证的思想，事先把数据集划分成训练集和测试集，若训练集得到的
以上停止策略同样适用于C4.5和CART，后面将不再赘述。
三、C4.5
C4.5使用信息增益比来作为信息增益的度量，以缓解ID3算法优先选择特征值较多的特征变量从而生成“矮胖”决策树的倾向。算法过程如下：
input：训练数据集
steps：
(1)将数据集
(2)若
(3)若特征
(4)否则，按照信息增益比的定义来计算第然后选择使得信息增益比最大的特征
(5)若
(6)否则，根据特征
(7)对于每个划分出来的数据集
outpt：原始数据对应的根节点Node。
这里需要注意的是，C4.5算法虽然不会倾向于选择特征值比较多的特征列，但是可能会倾向于选择特征值比较少的列，这样又会走向另一个极端。因此在1993年，Quinlan提出了一种启发式的方法来解决这个问题，就是先选出互信息比平均互信息高的特征，然后从这些特征中选出信息增益比最高的特征列。
另外需要注意的是，由信息增益比的公式我们可以知道，C4.5更倾向于选择特征分布不平均的特征，这样的之间后果是导致每次划分的时候，更倾向于将数据集划分成几个小Node和一个大Node，然后大Node又会按照这种方式继续划分下去，这样会直接导致决策树往更深处发展，进而导致过拟合现象的产生。因此前面提到的停止策略也适合这里，特别是当某个分支的深度达到指定高度时，及时停止当前Node的进一步划分。
四、CART（Classification And Regression Tree， 分类回归树）
CART，又叫分类回归树，从名字我们就可以知道CART即可以用来实现分类，也可以用来实现回归。CART算法一般使用基尼增益作为信息增益的度量方式，当然并不是说CART不可以使用互信息和信息增益比作为信息增益的度量方式，可以视具体场合而定。CART树最大的特色在于它假设了最终生成的决策树为二叉树，也就是说它即使在处理离散特征时也会通过决策出二分的标准来划分数据。
算法过程如下：
input：训练数据集
steps：
(1) 将数据集
(2) 若
(3) 若特征
(4) 否则，不妨设在当前数据集中的取值范围为
，且它们满足
，那么：
(4.1) 若
(4.2) 若作为二分标准。
然后按照基尼系数定义的信息增益来计算特征
(5) 若
(6) 否则，根据特征
(7) 对于每个划分出来的数据集
outpt：原始数据对应的根节点Node。
从分类问题到回归问题并不是一个简单的转化问题，它们的最大区别在于：回归问题除了特征是连续型变量外，其因变量也是连续型，在分类问题中的损失可以定义成数据的不确定性，而在回归问题中，一般将损失定义为预测值与真实值之间的误差平方和（SSE），当损失函数为SSE时，此时生成的CART回归树又称之为最小二乘回归树。
五、总结
决策树生成算法发展至今已经产生了很多的变种，上面三种是比较基本的决策树生成算法，事实上，上述三种算法的区别仅仅表现在度量信息增益和数据划分方式的不同上。而它们之间也存在着某种程度上的递进关系：
- ID3算法是最朴素的决策树生成算法，其给出了针对离散型数据分类的解决方案。
- C4.5算法是在ID3算法的基础上，通过减低特征类比的影响，给出了一种针对混合型数据分类的解决方案。
- CART算法则更近一步，给出了数据回归的解决方案。scikit-learn中决策树的实现就是用的CART的优化版本，使用
DecisionTreeClassifier和DecisionTreeRegressor来分别支持分类和。
虽然这些算法的功能越来越强大，但是他们的核心思想都是一样的：以使当前信息增益达到最大为目的，通过不断划分数据集来生成决策树。其背后的思想也是普适的机器学习思想：模型的损失就是数据集的不确定性，模型算法的目的就是最小化当前数据集的不确定性。因此，通过启发式的方式，在每一步选择当前状态下的最优解对数据集进行划分，最终生成决策树模型。
