学习的简单笔记，只是对一些概念之类的进行简单记录

1. ID3算法

对于

对上图构建决策树




过度拟合： 如果决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过拟合”。

定义： 给定一个假设H，如果在假设空间上存在另一个假设H’，使得在训练集上H的错误率差比H’小，而在测试集上H的错误率却比H’要大，那么称假设H过度拟合训练数据。

产生过度拟合数据问题的原因有哪些？

原因1：样本问题
（1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；

（2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景；

（3）建模时使用了样本中太多无关的输入变量。

原因1的解决方法：
合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树；

原因2：构建决策树的方法问题

在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的*生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂

原因2的主要解决方法：
剪枝：提前停止树的增长或对已经生成的树按照一定的规则进行后剪枝。

2. C4.5的生成算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，用信息增益比来选择特征。（ID3采用信息熵进行构建，关于信息熵和信息增益的计算可参考https://blog.****.net/myhome908/article/details/88061168）

3. CART（分类与回归树）算法

• CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。
• CART假设决策树是二叉树，内部结点特征的取值为“是”和“否。
  这样的决策树等价于递归地二分每个特征。
• 步骤：
  （1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
  （2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择，生成二叉树。

4 决策树剪枝