机器学习算法——决策树3（信息增益和ID3算法）

信息增益

算法思想

信息增益的算法过程为：

出入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益
具体过程解释为：
- 先计算数据集D的经验熵 $H(D)$
  $H(D)=- \sum _{k=1}^{K} \frac{|C_k|}{|D|} \sum _{k=1}^{K} \frac{|D_{ik}|}{|D_i|}log_2 \frac {|D_{ik}|}{|D_i|}$
  上式表示为：样本中每个类的在总样本的占比，然后求出经验熵 $H(D)$
- 计算特征A对数据集D的经验条件熵 $H(D|A)$ ：表示在特征A的条件下，数据集D的条件熵
  $H(D|A)=\sum _{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^{n}\frac{|D_i|}{|D|} \sum _{k=1}^{K} \frac{|D_{ik}|}{|D_i|}log_2 \frac{|D_{ik}|}{|D_i|}$
- 计算信息增益： $g(D,A)=H(D)-H(D|A)$

栗子

image.png

下面具体解释下针对特征年龄 $A_1$ 的信息增益的计算过程

计算经验熵：
- 原始数据中，输出类别分为是与否，二者比例为9:6
- 根据经验熵的公式得出数据集D的经验熵为 $H(D)=-\frac {9}{15}log_2 \frac {9}{15} - \frac {6}{15}log_2\frac {6}{15}$
计算经验条件熵：
- 年龄有三个类别：青年、中年、老年，比例为5:5:5
- 根据表格中年龄属性的3个特征，青年、中年、老年：
  - 青年：是:否=2:3
  - 中年：是:否=3:2
  - 老年：是:否=4:1
    计算出以年龄为条件的， $H(D|A_1)$
将经验熵减去经验条件熵，便可以得到信息增益information gain $g_(D,A_1)=H(D)-H(D|A_1)$

信息增益率

以信息增益作为划分训练数据集的特征，存在一个问题：分类结果偏向于选择取值较多的特征。利用信息增益率可以校正这个问题。信息增益率定义为：

特征A对训练数据集D的信息增益比为 $g_R{(D,A)}$ ，定义为其信息增益 $g{(D,A)}$ 与训练数据集D关于特征A的值的熵 $H_A{(D)}$ 之比，即 $g_R(D,A)=\frac {g(D,A)}{H_A(D)}$ 其中， $H_A{(D)}=- \sum _{i=1}^{n}\frac{|D_i|}{|D|}log_2 \frac {|D_i|}{|D|}$ ，n是特征A取值的个数。

ID3算法

算法简述

ID3和CART算法是决策树中的经典算法。在本篇札记中主要讲解ID3算法。

ID3算法的核心是在决策树的各个节点上利用信息增益来进行特征的选择，通过递归方法构建决策树。

从根节点开始，对节点计算所有可能的特征的信息增益：计算所有的特征的信息增益
选择信息增益最大的特征作为节点的特征，构建子节点
对子节点递归调用上述方法，构建决策树。
直到所有特征的信息增益均很小或者没有特征可以选择

ID3算法相当于是利用极大似然法进行概率模型的选择。算法利用互信息或者信息增益作为特征选取的标准，倾向于选择特征取值较多的特征，这样能将训练数据集分成很多份，不确定性自然减少，这样ID3算法容易得到一颗矮胖的树。

算法步骤

输入：训练数据集D，特征集A阈值 $\varepsilon$
输出：决策树T

如果训练数据集中的实例全部属于同一个类 $C_k$ ，则T为单节点树，并且将 $C_k$ 作为实例的类进行输出。
若A为空集，则T为单节点树，并将D中实例最大的类 $C_k$ 作为节点的类进行输出
不满足上述两种情况，计算A中各个特征对D的信息增益，选择信息增益最大的特征 $A_g$
如果 $A_g$ 的信息增益小于阈值 $\sigma$ ，返回单节点树T
否则，对于 $A_g$ 中的每个取值 $a_i$ ，依 $A_g=a_i$ ，将数据集D分割为若干个子集 $D_i$ ，将 $D_i$ 中实例最大的类作为标记，构建子节点，由节点及其子节点构成树 $T$ ，返回T
对于第 $i$ 个子节点，以 $D_i$ 为训练集，以 $A-\{A_g\}$ 为特征集，递归地调用上述步骤，得到子树 $T_i$ ，返回 $T_i$