决策树（1）ID3

一、ID3【删特征】

ID3 算法是建立在奥卡姆剃刀[“切勿浪费较多东西去做，用较少的东西，同样可以做好的事情”]（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。

1.1 思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1. 初始化特征集合和数据集合；
2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

1.2 划分标准

ID3 使用的分类标准是信息增益，它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。

数据集的信息熵：

\[ H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} \]

其中\(C_{k}\)表示集合 D 中属于第 k 类样本的样本子集。针对某个特征 A，对于数据集 D 的条件熵 \(H(D \mid A)\)为：

\[ \begin{aligned} H(D \mid A) &=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right) \\ &=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}\left(\sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right) \end{aligned} \]

信息增益 = 信息熵 - 条件熵。信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。 \[ \operatorname{Gain}(D, A)=H(D)-H(D \mid A) \]

信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。

1.3 缺点【没有剪枝、特征偏好、缺失值】

• ID3 没有剪枝策略，容易过拟合；
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。