ID3决策树

熵

对于一个系统, 如果只有一个可能, 则最有序, 混乱度最低, 熵为0, 若有很多可能则混乱度高, 熵大

对于一个随机变量, 若只有一种取值, 则熵为0, 若有多种取值, 则熵大

假设X可取{x1, x2, …, xn}, 其概率分布为P(X) = {p1, p2, …, pn}, 则X的熵定义为:

$$
E(X) = -\sum_{i=1}^{n} p_i \log_2(p_i)
$$

流程

假设有4个特征: age, income, student, credit_rating, 目标变量: buys_computer

1. 先看结果buys_computer的熵: 共14个样本, 9个买了电脑, 5个没买电脑

   $E(buys_computer) = -\frac{9}{14}\log_2(\frac{9}{14}) - \frac{5}{14}\log_2(\frac{5}{14}) = 0.940$

2. 若以age为特征划分

   1. 当age <= 30时, 5个样本, 2个买了电脑, 3个没买电脑, 熵为0.971

      $E(buys_computer|age<=30) = -\frac{2}{5}\log_2(\frac{2}{5}) - \frac{3}{5}\log_2(\frac{3}{5}) = 0.971$

   2. 当30 < age <= 40时, 4个样本, 4个买了电脑, 0个没买电脑, 熵为0, 高度有序

      $E(buys_computer|30<age<=40) = -\frac{4}{4}\log_2(\frac{4}{4}) - \frac{0}{4}\log_2(\frac{0}{4}) = 0$

   3. 当age > 40时, 5个样本, 3个买了电脑, 2个没买电脑, 熵为0.971

      $E(buys_computer|age>40) = -\frac{3}{5}\log_2(\frac{3}{5}) - \frac{2}{5}\log_2(\frac{2}{5}) = 0.971$

3. 加权求以age划分后的熵

   $E(buys_computer|age) = \frac{5}{14}*0.971 + \frac{4}{14}*0 + \frac{5}{14}*0.971 = 0.693$

4. 所以以age为特征划分的信息增益为

   $Gain(age) = E(buys_computer) - E(buys_computer|age) = 0.940 - 0.693 = 0.247$

5. 陆续以income, student, credit_rating为特征划分, 求信息增益, 选择信息增益最大的特征作为根节点

   特征	信息增益
   age	0.247
   income	0.029
   student	0.151
   credit_rating	0.048

6. 这里age信息增益最大, 以它为根节点, 有3个分支: age <= 30, 30 < age <= 40, age > 40

7. 对每个分支, 重复上述步骤, 直到所有特征都用完, 或者信息增益为0, 或者节点下的样本全是同一类别

8. 最终得到一棵决策树, 每个节点都是一个特征, 每个叶子节点是一个类别, 给定一个新样本, 从根节点开始, 根据特征值选择分支, 直到到达叶子节点, 该叶子节点的类别即为预测结果