决策树总结

决策树学习的本质是从训练集中归纳出一组分类规则。与训练集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能没有。我们要求解的是一个与训练数据拟合度高，泛化能力强的决策树。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。但是这种基于特征空间划分的类条件概率有无穷多个，我们应该选择其中一个，不仅对训练数据有较好的拟合，而且对未知数据也有很好的预测（泛化能力）。

特征选择有四种方法：

• 第一种方法是基于信息增益。

• 第二种方法是基于信息增益率。

• 第二种方法是基于Gini指数的特征选择方法。

• 第三种方法是基于最小误差算法。

依照上述特征选择方法进行决策树的建立，由于算法采用自顶向下的递归划分方法，因此沿着树向下，记录数量会越来越少。在叶节点记录可能记录太少。这种叶节点划分的类，不能做出具有统计意义的判决，这就是所谓的数据碎片。

因此，一颗完全生长的树，虽然很好的拟合了训练数据的样本，但是有可能出现过拟合，对于测试样本不会有很好的测试效果。因此，为了提升模型的泛化能力，采用剪枝算法限制决策树的生长，剪枝算法分为前剪枝和后剪枝。

前剪枝是在决策树的生成过程中，通过预设的熵增阈值来决定决策树是否继续生长。虽然该方法可以避免决策树模型生长为过于复杂的模型，但是阈值很难选择。如果阈值太小则不能充分达到剪枝的功能，如果阈值过大，那么就会过早地终止决策树的生长，导致模型对训练数据的拟合程度严重不足。所以，为了达到更好的剪枝效果，一般使用后剪枝。

后剪枝的策略是，在一棵决策树完全生长之后，自底向上的修剪决策树。可以用新的叶子节点代替子树，也可以用子树中最长使用的分支代替子树，当模型不能再改进时，终止剪枝步骤。与前剪枝相比，后剪枝更倾向于产生全局最优解。但是，被裁剪掉的子树计算时间浪费，所以后剪枝时间花销比前剪枝大。

得到决策树之后，我们应该如何验证模型的好坏？通常有三种方法：

• 第一种是Holdout方法。该方法的局限性是训练样本少（因为训练样本中一部分被用作测试样本），训练集和测试集的构成会影响模型的拟合度。
• 第二种方法是K折交叉验证，该方法检验集之间是互斥的，并且完全覆盖了整个测试集。但是随着K值增大，检验的开销也变大。
• 最后一种方法是自助法，该方法采用又放回抽样的办法，使得测试集和原有的测试集数量相同。

Adaboost是为了将多个弱分类器进行加权组合，得到一个强分类器，在adaboost算法学习过程中需要不断调整样本的权值和每个决策树的权值，最终得到的强分类器准确率高于单独的弱分类器