决策树剪枝
一、决策树的生成算法
基本的决策树生成算法主要有ID3和C4.5, 它们生成树的过程大致相似，ID3是采用的信息增益作为特征选择的度量，而C4.5采用信息增益比。构建过程如下：
1.从根节点开始，计算所有可能的特征的信息增益（互信息），选择计算结果最大的特征为根节点。
2.根据算出的特征建立子节点，执行第一步，直到所有特征的信息增益（互信息）很小或者没有特征可以选择为止。
二、决策树剪枝
为什么要进行剪枝？决策树的过拟合的风险很大，理论上在测试阶段所有样本都可以被分类完全
剪枝策略:
预剪枝:
限制深度,叶子节点个数,叶子节点样本数,信息增益等,
优点：可以边建立树的过程中进行剪枝
后剪枝:
决策树后剪枝一般通过极小化损失函数或者代价函数来实现:
C(t)表示模型对训练数据损失函数(限误差)，即拟合度。|T|表示当叶子节点个数，参数α≥0控制两者之间的影响。剪枝就是当α确定时，选择损失函数最小的模型。子树越大，数据拟合得越好，但是模型的复杂度越高；相反，字数越小，数据拟合较差，模型的复杂度较低。损失函数正好表示对两者的平衡。