熵表示的是数据中包含的信息量的大小,熵越小,数据的纯度越高,亦即数据越趋于一致,这是我们希望划分之后每个子结点的状况。信息增益 = 划分前熵 - 划分后熵。信息增益越大,则意味着使用属性 $a$ 来进行划分所获得的”纯度提升”越大。也就是说,用属性 $a$ 来划分训练集,得到的结果纯度比较高。
决策树的一种经典实现算法 Iterative Dichotomiser 3 (ID3) 就是采用了这种信息增益最大的特征选择准则,从根节点开始,对节点计算所有可能特征的信息增益,选择最大的作为节点的特征;根据该特征的不同取值建立子节点,然后对子节点递归进行上述流程构建决策树;直到最后所有特征的信息增益均很小或没有特征可以选择为止,得到决策树。
ID3 算法流程:
- 输入:训练数据集 $D$,特征集 $A$,阈值 $\epsilon$
- 输出:决策树 $T$
- if $D$ 中所有样本属于同一类 $C_k$:
- 则 $T$ 为单节点树(树桩),将类 $C_k$ 作为该节点的类标记,返回 $T$。
- elif $A=\varnothing$:
- 则 $T$ 为单节点树(树桩),将 $D$ 中样本数最多的类 $C_k$ 作为该节点的类标记,返回 $T$。
- else: 计算 $A$ 中个特征对 $D$ 的信息增益,选择信息增益最大的特征 $A_g$。endif
- if $A_g$ 的信息增益小于阈值 $\epsilon$:
- 则置 $T$ 为单节点树(树桩),并将 $D$ 中样本数最多的类 $C_k$ 作为该节点的类标记,返回 $T$。
- else: 对 $A_g$ 的每个可能值 $a_i$,依据 $A_g=a_i$ 将 $D$ 拆分为若干个非空子集 $D_i$,将 $D_i$ 中最大的类作为类标记,构建子节点,由节点及其子节点构成树 $T$,返回 $T$。 endif
- repeat: 对第 $i$ 个子节点,以 $D_i$ 为训练集,以 $A-{A_g}$ 为特征集,递归的调用步骤 (1)-(5),得到子树 $T_i$,返回 $T_i$。
总结
- 核心思想
- 以生长树结构的方式训练模型,中间结点是判断结点,以一个特征的每个具体值作为划分不同的划分路径,将该结点下所有样本划分开来;如果子节点为叶节点的话,以每一个子节点中的多数类别为当前叶子结点的所属类别。
- 根据信息论指标,尝试通过训练数据找到特征空间的划分原则,从而可以将样本归属到对应的类别中
- 决策函数
- 训练好的决策树是一个树结构,预测时按照树的访问顺序依次访问到叶节点找到对应的类别即可
- 损失函数
- 局部地选择信息增益最大的形式,等价于 log-likelihood 损失。(看参考 3,待进一步理解和整理)
- 优化算法
- 从根节点开始,迭代生成整棵树
- 对于每一个内部结点,遍历所有的特征,选择一个使得信息增益最大的特征作为划分特征,进行样本划分
- 迭代进行以上步骤,直到特征集为空
- 优点:
- 理论清晰,方法简单,学习能力较强
- 缺点:
- 只能处理离散型数据,无法处理连续型数据
- 只有树的生成没有剪枝,容易发生过拟合
- ID3 采用信息增益来划分子树,所以导致倾向于选择取值较多的属性
- 没有考虑缺失值的情况
- 划分过程会由于子集规模过小而造成统计特征不充分而停止(咋理解?)