决策树

原理

顾名思义，决策树就是用一棵树来表示我们的整个决策过程。这棵树可以使二叉树(CART只能是二叉树),也可以使多叉树(ID3,C4.5 可以是多叉树或二叉树)
根节点包含整个样本集，每个叶节点都对应一个决策结果(注意，不同的叶节点可能对应同一个决策结果)，每一个内部节点都对应一次决策过程或者说是一次属性测试。
从根节点到每个叶子节点的路径对应一个判定测试序列。
决策树的生成就是不断的选择最优的特征对训练集进行划分，是一个递归的过程,递归返回的条件有三种：
1.当前节点包含的样本属于同一类别，无需划分
2.当前属性集为空，或所有样本在属性集上取值相同，无法划分
3.当前节点包含样本集合为空，无法划分

ID3使用信息增益作为选择特征的准则；C4.5使用信息增益比作为选择特征的准则；CART使用Gini指数作为选择特征的准则

ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。也就是说，用属性a来划分训练集，得到的结果中纯度比较高。
ID3仅仅能够处理离散属性。

信息熵：

$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$

条件熵：

$H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{D |} H\left(D_{i}\right)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}\left(-\sum_{k=1}^{k} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right)$

信息增益

$g(D, A)=H(D)-H(D | A)$

C4.5

C4.5克服了ID3仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。
信息增益比 = 信息增益 / 划分前熵
选择信息增益比最大的作为最优特征
C4.5处理连续特征是将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

信息增益比

$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$
其中分母是取值熵：
$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}$

CART

CART与ID3，C4.5不同之处在于CART生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点智能根据属性值进行二分。
CART的全称是分类与回归树。从这个名字中就应该知道，CART既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化细则，来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

分类树种，使用Gini指数最小化准则来选择特征并进行划分；
Gini指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。

Gini系数计算过程：

Gini纯度公式：

$\operatorname{Gini}(D)=1-\sum_{k=1}^{n}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$

按特征A切分两份后的Gini指数公式
$\operatorname{Gini}(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \operatorname{Gini}\left(D_{i}\right)$

剪枝

决策树算法很容易过拟合(overfitting),剪枝算法就是用来防止决策树过拟合，提高泛化性能你的方法
剪枝分为预剪枝和后剪枝
预剪枝是指在决策树的生成过程中，对每个节点在划分前进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。
后剪枝是指从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。
那么怎么来判断是否带来泛化性能的提升呢？最简单的放就是留出法，即预留一部分数据作为验证集来进行性能评估。

总结

决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用的算法有ID3,C4.5,CART
特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini指数
决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集。
决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝