跳转至

ID3 决策树

学习目标

  1. 掌握信息熵的概念
  2. 掌握条件熵的概念
  3. 掌握ID3决策树构建过程

1. 信息熵

ID3 树是基于信息增益构建的决策树.

定义

  • 熵在信息论中代表随机变量不确定度的度量。
  • 熵越大，数据的不确定性度越高
  • 熵越小，数据的不确定性越低

公式

\[ \large H = -\sum_{i=1}^{k}p_i\log(p_i) \]

例子1：假如有三个类别，分别占比为：{⅓,⅓,⅓}，信息熵计算结果为：

\(H=-\frac{1}{3}\log(\frac{1}{3})-\frac{1}{3}\log(\frac{1}{3})-\frac{1}{3}\log(\frac{1}{3})=1.0986\)

例子2：假如有三个类别，分别占比为：{1/10,2/10,7/10}，信息熵计算结果为：

\(H=-\frac{1}{10}\log(\frac{1}{10})-\frac{2}{10}\log(\frac{2}{10})-\frac{7}{10}\log(\frac{7}{10})=0.8018\)

熵越大，表示整个系统不确定性越大，越随机，反之确定性越强。

例子3：假如有三个类别，分别占比为：{1,0,0}，信息熵计算结果为：

\(H=-1\log(1)=0\)

公式的转换

当数据类别只有两类的情况下，公式可以做如下转换

\[ \begin{align}\large H &= -\sum_{i=1}^{k}p_i\log(p_i) \tag 1 \\ \large H &= -x\log(x)-(1-x)\log(1-x) \tag2 \\ \end{align} \]

代码角度理解信息熵的概念

import numpy as np
import matplotlib.pyplot as plt

def entropy(p):
    return -p*np.log(p)-(1-p)*np.log(1-p)

x = np.linspace(0.01,0.99,200)
plt.plot(x,entropy(x))
plt.show()

观察上图可以得出，当我们的系统每一个类别是等概率的时候，系统的信息熵最高，当系统偏向于某一列，相当于系统有了一定程度的确定性，直到系统整体百分之百的都到某一类中，此时信息熵就达到了最低值，即为0。上述结论也可以拓展到多类别的情况。

2. 信息增益

定义

特征\(A\)对训练数据集D的信息增益\(g(D,A)\)，定义为集合\(D\)的经验熵\(H(D)\)与特征A给定条件下D的经验熵\(H(D|A)\)之差。即

\[ \large g(D,A)=H(D)-H(D|A) \]

根据信息增益选择特征方法是：对训练数据集D，计算其每个特征的信息增益，并比较它们的大小，并选择信息增益最大的特征进行划分。表示由于特征\(A\)而使得对数据D的分类不确定性减少的程度。

算法：

设训练数据集为D，\(\mid D\mid\)表示其样本个数。设有\(K\)个类\(C_k\)，\(k=1,2,\cdots,K\)，\(\mid C_k\mid\)为属于类\(C_k\)的样本个数，\(\sum\limits_{k=1}^{K}=\mid{D}\mid\)。设特征A有\(n\)个不同取值\(\{a_1, a_2, \cdots,a_n\}\)，根据特征A的取值将D划分为\(n\)个子集\(D_1, D_2, \cdots,D_n\)，\(\mid D_i\mid\)为\(D_i\)样本个数，\(\sum\limits_{i=1}^n\mid D_i\mid=\mid D\mid\)。子集中属于类\(C_k\)的样本集合为\(D_{ik}\)，即\(D_{ik}=D_i\bigcap C_k\)，\(\mid D_{ik}\mid\)为\(D_{ik}\)的样本个数。信息增益算法如下：

  • 输入：训练数据集D和特征A；

  • 输出：特征A对训练数据集D的信息增益\(g(D,A)\)

  • (1) 计算数据集D的经验熵\(H(D)\)

\(H(D)=-\sum\limits_{k=1}^{K}\frac{\mid C_k\mid}{\mid D\mid}\log_2\frac{\mid C_k\mid}{\mid D\mid}\)

  • (2) 计算特征A对数据集D的经验条件熵\(H(D\mid A)\)

\(H(D\mid A)=\sum\limits_{i=1}^{n}\frac{\mid D_i\mid}{\mid D\mid}H(D_i)=-\sum\limits_{i=1}^{n}\frac{\mid D_i\mid}{\mid D\mid}\sum_\limits{k=1}^{K}\frac{\mid D_{ik}\mid}{\mid D_i\mid}\log_2\frac{\mid D_{ik}\mid}{\mid D_i\mid}\)

  • (3) 计算信息增益

\(g(D,A)=H(D)-H(D|A)\)

例子：

下面以常用的贷款申请样本数据表为样本集，通过数学计算来介绍信息增益计算过程。

ID 年龄 有工作 有房子 信贷情况 类别
1 青年 否 否 一般 拒绝
2 青年 否 否 好 拒绝
3 青年 是 否 好 同意
4 青年 是 是 一般 同意
5 青年 否 否 一般 拒绝
6 中年 否 否 一般 拒绝
7 中年 否 否 好 拒绝
8 中年 是 是 好 同意
9 中年 否 是 非常好 同意
10 中年 否 是 非常好 同意
11 老年 否 是 非常好 同意
12 老年 否 是 好 同意
13 老年 是 否 好 同意
14 老年 是 否 非常好 同意
15 老年 否 否 一般 拒绝

Step1 计算经验熵

类别一共是两个拒绝/同意，数量分别是6和9，根据熵定义可得：

\[ H(D)=-\frac{9}{15}\log_2\frac{9}{15}-\frac{6}{15}\log_2\frac{6}{15}=0.971 \]

Step2 各特征的条件熵

将各特征分别记为 \(A_1,A_2,A_3,A_4\) ，分别代表年龄、有无工作、有无房子和信贷情况，那么

\[ \begin{align} H(D\mid A_1)&=\frac{5}{15}(-\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5})+\frac{5}{15}(-\frac{3}{5}\log_2\frac{3}{5}-\frac{2}{5}\log_2\frac{2}{5})+\frac{5}{15}(-\frac{4}{5}\log_2\frac{4}{5}-\frac{1}{5}\log_2\frac{1}{5})=0.888 \\ H(D\mid A_2)&= \frac{5}{15}(-\frac{5}{5}\log_2\frac{5}{5})+\frac{10}{15}(-\frac{4}{10}\log_2\frac{4}{10}-\frac{6}{10}\log_2\frac{6}{10})=0.647 \\ H(D\mid A_3) &= 0.551 \\ H(D\mid A_4) &= 0.608 \end{align} \]

Step3 计算增益

\[ \begin{align} g(D,A_1) = H(D)-H(D\mid A_1) = 0.083\\ g(D,A_2) = H(D)-H(D\mid A_2) = 0.324\\ g(D,A_3) = H(D)-H(D\mid A_3) = 0.420\\ g(D,A_4) = H(D)-H(D\mid A_4) = 0.363 \end{align} \]

根据计算所得的信息增益，选取最大的\(A_3\) 作为根节点的特征。它将训练集 \(D\) 划分为两个子集\(D_1\)（取值为“是”）和\(D_2\)（取值为“否”）。由于\(D_1\)只有同一类的样本点，所以成为一个叶节点，节点标记为“是”。

对于\(D_2\)需从特征\(A_1,A_2,A_4\)中选择新的特征。计算各个特征的信息增益

\[ g(D_2,A_1)=0.918-0.668=0.251\\ g(D_2,A_1)=0.918\\ g(D_2,A_1)=0.474 \]

选择信息增益最大的特征\(A_2\)作为节点的特征。由于\(A_2\)有两个可能取值，一个是“是”的子节点，有三个样本，且为同一类，所以是一个叶节点，类标记为“是”；另一个是“否”的子节点，包含6个样本，也属同一类，所以也是一个叶节点，类别标记为“否”。

最终构建的决策树如下：

3. ID3算法步骤

  1. 计算每个特征的信息增益
  2. 使用信息增益最大的特征将数据集 S 拆分为子集
  3. 使用该特征（信息增益最大的特征）作为决策树的一个节点
  4. 使用剩余特征对子集重复上述（1，2，3）过程

4. 小结

  1. 信息熵是一个变量（特征）包含信息多少的度量方式。信息熵的值大，则认为该变量包含的信息量就大
  2. 条件熵用于衡量以某个特征作为条件，对目标值纯度的提升程度
  3. 信息增益用于衡量那个特征更加适合优先分裂
  4. 使用信息增益构建的决策树成为 ID3 决策树