KING

Tree-based ensemble methods

random forest
gradient boosted decision trees

• main idea is greedy algorithm
  • 通过构造一棵决策树分类器
• 随机森林是通过构造10000课树

决策树

• 其实就是二叉树
• 实际应用，一般为二叉树
• 每个非叶子节点都是一个分割
  • 相当于一个分类条件
• 每个叶子节点都是一类性质相同的样本

• 用同一种数据存在多种构造决策树的情况

• 决策树使用来分类的模型

  • 相当于svn和LR
• 如何建树
  • 是一种回归分类算法
    • “切分”和“解决”
  • 一开始的时候，所有的训练样本都在根部
  • 然后分类的样本将基于选择的分类属性进行递归。
• 理论上特征是可以重复选的
• 怎么找到比较好的树？
  • 模型准确率高
  • 找到尽可能最小的数来满足数据
    • 分枝少
    • 节点少
  • occam’s Racor：在效果超不多的时候，选比较简单的模型
• 基本策略
  • 贪心
    • 当前把每个节点中的最优的特征作为分类标准
    • 这样就不用穷举
    • 评估
      • 基尼系数（Gini index）
      • 信息增益
        • 用熵来衡量
        • 混乱程度
          • 如果容易分别出那个分类多，则混乱程度小
          • 反之同理
        • e.g 99/1（小） 50/50（大）
      • 则把每个叶子节点的熵都算出来
        • 然后整棵树的熵则是用所有叶子节点的熵加权
      • 把分割前的熵减掉分割之后的，就是信息增益
        • 如果比较大，那么就比较好
    • Gini index
      • 把叶子节点的熵换掉
      • 换成基尼系数
      • 基本上也是混乱度
      • 只是公式不一样了
    • 整棵树的Gini系数是加权的分支的基尼
    • 如何防止overfitting？
      • 早一点停止树的增长
      • 先把所有节点来构造树，然后用的是90%的样本
        • 然后用剩下的样本来检验效果
        • 但是太慢了
• Bagging
  • 构造k棵树
  • 每棵树在1000各样本中随机选900个,构造决策树（只筛选样本）
    • 然后把所有树的据结果统计，如果是分类问题，就少数服从多数。
    • 随机选出的数据室可以重复的。
  • 如果是回归问题，则最终直接相加

• random forest

  • 不使用全部特征
  • 不单只筛选样本，也筛选特征。
  • e.g 每次只用随机抽取的70%的样本，只用50%随机抽取的特征，来建立决策树
  • 是目前分类回归中最好的off-the-shelf的算法
    • 即拿即用

• 这两个算法加上boosting的不同在于训练集的构造的不同。

• Boosting
  • 结果是把每棵决策树的结果加权加起来
  • 所有样本的权值加起来为1
  • 对那些错的样本，权值是比较大的
  • 缺点是在高噪声的环境下效果很不好
    • 优点是在低噪声环境下效果很好