熵表示的是数据中包含的信息量的大小，熵越小，数据的纯度越高，亦即数据越趋于一致，这是我们希望划分之后每个子结点的状况。信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 $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 采用信息增益来划分子树，所以导致倾向于选择取值较多的属性
- 没有考虑缺失值的情况
- 划分过程会由于子集规模过小而造成统计特征不充分而停止（咋理解？）