决策树通用算法流程
决策树算法是根据数据中不同的属性将数据划分到不同的区域（叶子节点）来完成分类或者回归的任务。
下面我们先来看看决策树的通用算法：
输入：
训练集D
属性集A
TreeGenerate(D,A){
生成节点Node;
If D中所有数据属于同一类别：
将node标记为叶节点，记录其类别，return;
end if
if A为空 或 D中样本在A上的取值相同：
将node标记为叶节点，记录其类别为D中样本数最多的类别，return;
end if
选择A中最优划分属性a;
for 属性a的每一个属性值：
为node生成一个分支节点child,包含数据集合Dc
if child为空：
将child的类别标记为父节点node的节点, return ;
else
TreeGenerate(Dc,A除掉属性a的集合)
end if
end for
}
可以观察到，这是一个递归算法；算法主要有以下核心点：
- 何时停止分裂
- 如何选择最优划分属性
下面就这两个核心点进行些细致的讨论。
何时停止分裂
可以看到，在上面的算法中节点停止分裂有下面几种情况：
- 该节点中所有数据属于同一种类
- 可供该节点划分的属性A为空（一个变种为当叶子节点少于某个阈值时停止分裂）
- 该节点中所有数据在A上的取值相同
如何选择最优划分属性
由于选择最优划分属性的标准的不同而产生不同的种类的决策树，例如ID3，C4.5，CART 决策树。 其中ID3和C4.5都是利用信息熵度量样本集合的纯度，而CART是利用基尼系数来度量样本集合的纯度。
两个概念
-
信息熵 定义为数据集D的信息熵，其中N为数据样本的类别总数。显然，信息熵越小，样本集合越纯。
-
基尼值 基尼系数作为另一种衡量样本集合纯度的指标，它的物理含义可以理解为：从数据集中随机抽取两个样本，其类别标记不一样的概率，因此越小越好。
信息增益
假设对于某个属性a有v个取值,则分裂前后的信息熵分别为：
-
分裂前，
-
分裂后，
其中，是属性a取值为的时候样本数。
因此，最终的信息增益就是前后的信息熵之差，
在ID3算法中，就是选择信息增益最大的属性。不过这个算法有个很大的缺点，通常属性取值的可能性越多，信息增益会越大，这种偏爱带来的不利影响就应运而生下面的C4.5算法，采用信息增益率解决这个问题。
信息增益率
其中，被称为属性a的固有值(intrinsic value)，
显然，当属性a的取值可能性较多造成信息增益很大时，相应的也会变大。
但是，也许有点矫枉过正的嫌疑，信息增益率是偏爱属性取值较少的，依然不能直接作为一个完美的标准去选择。 因此，在C4.5算法中，并不是直接选择信息增益率最大的属性作为最优划分属性。而是先选出信息增益高于平均水平的属性，再从这些候选属性中选出信息增益率最高的。
属性a的基尼指数
CART算法选择基尼指数最小的属性作为最优划分属性。
剪枝
为了避免过拟合，决策树算法一般采用剪枝算法。剪枝根据剪枝的时机分为预剪枝和后剪枝。
-
预剪枝 顾名思义，在决策树生成之前，在每个节点分裂之前进行衡量节点的分裂是否会带来决策树泛化性能的提升，如果是，则分裂。
-
后剪枝 后剪枝则相反，是在整个决策树生成之后，再自下而上的衡量节点的分裂是否会给决策树的泛化性能带来提升，如果是，则保留该节点；如果否，则删除该节点的子节点。
两者的优缺点：
-
性能 后剪枝显然学习出的决策树更佳，因为它是基于所有分裂可能的情况考虑的；而预剪枝则不一样，很有可能会出现当前某一节点的分裂没有带来性能的提升，但在其分裂若干次后性能却反而提升的情况，这种情况则被预剪枝忽略了。
-
开销 由于预剪枝没有考虑到所有的分裂情况，因此运行学习时花费的开销更小。
连续值与缺失值的处理
现实世界中，数据有可能是连续的有很多种取值，这个时候再向处理离散时候的特性那样是不适合的；还有些时候，数据有可能缺失，那么在决策树中如何应对这两种情况呢？
连续值的处理
在计算机里，任何时候遇到连续值，很多时候都是采用连续值离散化的方法进行处理。在决策树中，最简单的就是将连续属性二分处理的方法。
假设连续属性a具有n个属性值。将其从小到大排序后，则基于划分点t，可以将数据集分为两部分，一部分是a属性值小于t的数据样本集，一部分是a属性值大于t的数据样本集。则其信息增益为：
通常t的集合：
遍历此集合的t，选择信息增益最大的t。
缺失值的处理
数据缺失太常见了。因此选择合适的方法对缺失值进行处理显得至关重要。
参考文献：
[1]统计学习方法，李航
[2]机器学习，周克华
