决策树

决策树的生成算法递归的产生决策树，直到不能继续下去为止，这样产生的决策树容易出现过拟合，过拟合的原因在于，模型对训练数据分类分的太细致，模型太复杂，从而我们需要剪枝来简化模型。

决策树

• 1.决策树模型与学习
  • 决策树模型
    • 描述对实例进行分类的树形结构，有内节点和叶节点。
  • 决策树学习
    • 假设给定的数据集是有标签的数据，决策树学习的本质是从训练集中归纳出一组分类规则。
    • 另一个角度看是估计一个条件概率模型。
• 2.特征选择
  • 特征选择问题
    • 特征选择在于选取对训练数据具有分类能力的特征，选择一些具备较强分类能力的特征，可以提高决策树学习的效率。
  • 信息增益
    • 决策树学习应用信息增益准则选择特征，给定数据集D和特征A，H(D)表示对数据集D进行分类的不确定性，H(D|A)表示给定特征A下对D进行分类的不确定性，他们的差就是信息增益，表示特征A对D进行分类的不确定性减少的程度。
    • 熵
      • 子主题1
    • 条件熵
  • 信息增益比
    • 以信息增益作为划分训练数据集的特征，存在偏向于选取值较多的特征的问题，使用信息增益比可以矫正这一问题。
• 3.决策树的生成
  • ID3
    • ID3算法的核心是在决策树的各个结点上应用信息增益准则选择特征
  • C4.5
    • C4.5与ID3类似，只是其中使用信息增益比来选择特征
• 4.决策树的剪枝
  • 决策树的生成算法递归的产生决策树，直到不能继续下去为止，这样产生的决策树容易出现过拟合，过拟合的原因在于，模型对训练数据分类分的太细致，模型太复杂，从而我们需要剪枝来简化模型。
  • 算法细节，首先计算每个结点的经验熵，然后从叶节点递归的回缩，设一叶节点回缩到父结点之前的整体树分为T1,T2,计算他们的损失函数。