既然上次讲到了随机森林，而随机森林是由多棵决策树构成的，现在就回头仔细看看决策树。
博客园中已经有介绍决策树的非常好的 博文 。其中详细介绍了ID3，C4.5决策树的构造，这篇博文主要关注在树的每个节点如何确定 最佳分裂属性 和 剪枝 。
1.确定最佳分裂属性
一般介绍决策树都是以ID3(Quinlan 1986)为例。ID3算法使用的是信息增益，信息增益的具体细节我不再赘述。在决策树的节点N上，ID3算法选取在该节点对应的训练样例集合D上用输入属性进行分类后信息增益最大的输入属性。信息增益的定义为：
。其中S为节点N上的训练样例集合，A为某个输入属性。对于所有在节点N上可用的输入属性，我们选取信息增益值最大的属性进行分裂。因为上式中第一项对于所有输入属性都是一样的，所以第二项越小，信息增益值越大。
其实，除了信息增益（亦即熵值）之外，还有许多其他方法用来确定最佳分裂属性。他们都统称为不纯性度量（impurity measure）。使用某个属性对训练样例集进行划分，如果划分后每个分支内的所有样例都属于同一类，则称该划分是纯的，如果每个划分里的样例属于很多不同的类，则称该划分是不纯的。
我们用不纯性度量来衡量用某个属性划分训练样例的纯洁度，度量值越高表示划分越不纯（因为这是不纯性度量，不是纯性度量），我们在每个节点上进行分裂时尽量选取不纯度低的输入属性。上述的熵值可以用作不纯性度量，熵值越小，信息增益越大，不纯度越小，这种划分越好。除了熵值之外，还可以采用以下几种不纯度度量方法（仅表示一个划分内的不纯度度量，对于整体划分的不纯度度量可用各划分的不纯度度量值的加权和即可）：
(1) Gini指数：
，其中fi为该划分中属于i分类的训练样例的比率，Gini系数是Breiman于1984年提出来的，主要用在CART(Classfication and Regression Tree)中。
(2)误分类误差：1-max(f1,f2,...,fm)。
2.剪枝
在创建决策树的过程中，停止分裂的条件是 (1) 该节点处所有的样例都属于同一类别 或者 (2) 没有可以用的输入属性。
但是按照这样的停止条件训练出来的决策树往往会过度拟合(overfit)训练数据，亦即该模型对于训练数据有非常高的分类准确率，但是对于新的数据，分类的准确率较差。有两种方法可以用来避免过度拟合：
(1) 及早停止树增长，亦即先剪枝(prepruning)。
比如，如果决策树中一个节点的训练样例的数目小于整个训练集的某个百分比(如5%)，则该节点不进行分裂，而是对该节点训练样例进行"多数表决"。因为基于较少实例的决策树会导致较大方差，从而导致较大泛化误差(Generalization Error)。
(2)后剪枝(postpruning)。
后剪枝的方法很多，这里只介绍训练和验证集法的一个变种：
首先让决策树完全增长，然后我们找出过分拟合的子树并剪裁掉。具体的做法是：我们从之前的训练数据中取出一部分作为验证集，其余的还是作训练集。用训练集训练处一个完全增长的决策树，然后对于决策树中的每个子树，我们都用包含该子树的所有训练样例的叶节点来代替，该叶节点的分类为"多数表决"的结果。我们用验证集来测试替换前后分类性能的变化。如果替换后分类准确性有所上升，则我们有理由认为之前的那个子树过于复杂，对于训练集中的训练样例过度拟合，所以将之替换为叶节点。否则不予替换。
通常的做法是将可用训练样例的三分之二作为训练集，剩余的三分之一作为验证集。
两种剪枝方法比较，先剪枝比较快，可以再构建决策树的同时进行。而后剪枝比较慢，要在构造完决策树之后对于每一个子树进行替换和验证，但是其准确性比先剪枝要高。
参考文献：
[1] 算法杂货铺——分类算法之决策树(Decision tree)
[2] 机器学习 Tom M. Mitchell
[3] 机器学习导论 Ethern Alpaydin
