Fork me on GitHub

决策树学习总结

花了一点时间学习《统计学习方法》中的第5章决策树,现将学习笔记总结如下:

  1. 介绍:一个不断将样本增加到树中的框架。这个框架对应着样本集的条件概率分布。
  2. 训练:将样本加到树中时,以“每个子节点的样本尽可能纯”为目标来分裂节点。评估”每个子节点样本尽可能纯“的方式是信息增益,每个特征对应的信息增益是用所有样本的信息熵减去基于该特征的值进行分类之后,每个子类的信息熵的加权和,以子类样本占比作为权值。
  3. 测试:通过对比新样本的各个特征,将新样本与一个叶子节点对应,并赋予这个叶子节点的类标记
  4. ID3算法:先根据信息增益选择特征,再根据每个特征值生成一个子类。再对每个子类执行相同的操作。每个子类不再分割的结束条件是:信息增益不够大或子类中所有样本都有同样的类标记。
  5. C4.5算法:与ID3的区别在于它是根据信息增益比来选择特征。ID3是用分裂之后总的信息熵能下降多少来评估特征,C4.5是用这个下降的熵再除以特征自身对应的熵来评估。相当于加上了feature-special weight
  6. CART算法:它不再是通过比较各个特征的信息增益/增益比来选择特征。而是遍历所有特征和每个特征的所有值,找到使得gini指数最小的特征和值来做分裂的特征和特征值。结束条件是结点中样本个数小于阈值。或样本集的gini指数小于阈值。
  7. 剪枝:因为提高信息熵的算法/最小化gini指数的算法会倾向于让子节点分裂使得树过拟合。为了防止这一点,所以要用cost function对树进行剪枝,即将子节点删除,以父节点作为叶子节点。步骤是从叶节点往上依次计算剪枝前后的cost function,如果剪枝后cost function变小了则保留剪枝结果。
No pain, No gain