熵表示的是数据中包含的信息量的大小,熵越小,数据的纯度越高,亦即数据越趋于一致,这是我们希望划分之后每个子结点的状况。信息增益 = 划分前熵 - 划分后熵。信息增益越大,则意味着使用属性 $a$ 来进行划分所获得的”纯度提升”越大。也就是说,用属性 $a$ 来划分训练集,得到的结果纯度比较高。

  决策树的一种经典实现算法 Iterative Dichotomiser 3 (ID3) 就是采用了这种信息增益最大的特征选择准则,从根节点开始,对节点计算所有可能特征的信息增益,选择最大的作为节点的特征;根据该特征的不同取值建立子节点,然后对子节点递归进行上述流程构建决策树;直到最后所有特征的信息增益均很小或没有特征可以选择为止,得到决策树。

  ID3 算法流程:

  • 输入:训练数据集 $D$,特征集 $A$,阈值 $\epsilon$
  • 输出:决策树 $T$
  1. if $D$ 中所有样本属于同一类 $C_k$:
    • 则 $T$ 为单节点树(树桩),将类 $C_k$ 作为该节点的类标记,返回 $T$。
  2. elif $A=\varnothing$:
    • 则 $T$ 为单节点树(树桩),将 $D$ 中样本数最多的类 $C_k$ 作为该节点的类标记,返回 $T$。
  3. else: 计算 $A$ 中个特征对 $D$ 的信息增益,选择信息增益最大的特征 $A_g$。endif
  4. if $A_g$ 的信息增益小于阈值 $\epsilon$:
    • 则置 $T$ 为单节点树(树桩),并将 $D$ 中样本数最多的类 $C_k$ 作为该节点的类标记,返回 $T$。
  5. else: 对 $A_g$ 的每个可能值 $a_i$,依据 $A_g=a_i$ 将 $D$ 拆分为若干个非空子集 $D_i$,将 $D_i$ 中最大的类作为类标记,构建子节点,由节点及其子节点构成树 $T$,返回 $T$。 endif
  6. repeat: 对第 $i$ 个子节点,以 $D_i$ 为训练集,以 $A-{A_g}$ 为特征集,递归的调用步骤 (1)-(5),得到子树 $T_i$,返回 $T_i$。

总结

  • 核心思想
    • 以生长树结构的方式训练模型,中间结点是判断结点,以一个特征的每个具体值作为划分不同的划分路径,将该结点下所有样本划分开来;如果子节点为叶节点的话,以每一个子节点中的多数类别为当前叶子结点的所属类别。
    • 根据信息论指标,尝试通过训练数据找到特征空间的划分原则,从而可以将样本归属到对应的类别中
  • 决策函数
    • 训练好的决策树是一个树结构,预测时按照树的访问顺序依次访问到叶节点找到对应的类别即可
  • 损失函数
    • 局部地选择信息增益最大的形式,等价于 log-likelihood 损失。(看参考 3,待进一步理解和整理)
  • 优化算法
    • 从根节点开始,迭代生成整棵树
    • 对于每一个内部结点,遍历所有的特征,选择一个使得信息增益最大的特征作为划分特征,进行样本划分
    • 迭代进行以上步骤,直到特征集为空
  • 优点:
    • 理论清晰,方法简单,学习能力较强
  • 缺点:
    • 只能处理离散型数据,无法处理连续型数据
    • 只有树的生成没有剪枝,容易发生过拟合
    • ID3 采用信息增益来划分子树,所以导致倾向于选择取值较多的属性
    • 没有考虑缺失值的情况
    • 划分过程会由于子集规模过小而造成统计特征不充分而停止(咋理解?)

References

  1. Decision Tree 🌲
  2. 决策树算法中,CART与ID3、C4.5特征选择之间的区别会对实际应用有哪些影响?哪种的结果会更好些?
  3. 值得一看,对决策树划分方法找到了损失函数的对应