决策树

基础

决策树自上而下，树形分类的算法；有监督的算法
学习过程　

  • 特征选择　　
  • 决策树生成　　
  • 决策树剪枝　　

熵

  • 随机变量的不确定程度
  • $ H(x) = －\sum_{i=0}^n pi * log(pi) $
  • 熵越大不确定性就越大

ID3 算法

步骤

  1. 计算数据集D的熵
  2. 计算某个特征A对于数据集D的条件熵H(D|A)
  3. 计算信息增益g(D,A) = H(D) - H(D|A)

    局限性

  • 只能处理离散型变量，无法处理连续性变量
  • 对样本缺失值比较敏感
  • 每次分裂亲相遇取值多的特征，发哦之泛化性能较差

决策树的剪枝　

  • 提高决策树的泛化能生长力

    剪枝方法

    预剪枝

    树节点分裂之前，先计算划分是否可以提升模型的泛化能力
  • 三种情况
    1. 当树达到一定的深度时，停止树的生长
    2. 到达当前节点的样本数量小于某个阈值时，停止生长
    3. 计算每次分裂对测试集准确率的提升，小于某个阈值时不再生长

      后剪枝

      完全生长成的决策树，然后自底向上进行减枝
  • 原则
    • 测试集上准确率的提升