决策树入门教程

1 数学基础

    1.1 概率论入门
    1.2 Bootstrap抽样方法
    1.3 对数的深刻认识
    1.4 信息与信息熵
    1.5 偏差与方差
    1.6 信息增益
    1.7 基尼不纯度
2 决策树基础知识

    2.1 决策树概述
    2.2 ID3算法简介
    2.3 C4.5算法简介
    2.4 CART算法简介

信息增益

创建时间：2022-04-01 | 更新时间：2022-04-27 | 阅读次数：1355 次

信息增益

信息增益（Information Gain）是信息论中比较重要的一个计算方法，该方法能够估算系统中新引入的特征所带来的信息量，即信息的增加量。

信息增益的计算公式如下所示：

信息增益 = 信息熵 - 条件熵。

信息熵是代表随机变量的不确定度，这个概念令很多人丈二和尚摸不着头脑，而条件熵这个概念更让人云里雾里，请看其定义：

条件熵 $H(X|Y)$ 表示在已知随机变量Y的条件下，随机变量 $X$ 的不确定性。

比如，某数据集$S$中有若干数据$X$，而$X$有一属性$Y$，属性$Y$的取值为：$y_1$或者$y_2$，根据属性$Y$的取值不同，数据集会被分成不同的子集，然后分别计算这些子集的香农熵，再对其进行合并，所得到的这个熵称之为条件熵。

备注：对于数据集的理解，有两个角度，一种是集合角度，延伸出“集合-元素-属性”等概念，如上文所述；另外一个是概率角度，也就是说，将数据集里面的数据统一抽象成一个随机变量X和条件Y，可以求其熵，也可以求其条件熵。

接下来以天气预报的例子来说明。下面是描述天气数据表，学习目标是play或者not play。

index outlook temperature humidity windy play
1 sunny hot high FALSE no
2 sunny hot high TRUE no
3 overcast hot high FALSE yes
4 rainy mild high FALSE yes
5 rainy cool normal FALSE yes
6 rainy cool normal TRUE no
7 overcast cool normal TRUE yes
8 sunny mild high FALSE no
9 sunny cool normal FALSE yes
10 rainy mild normal FALSE yes
11 sunny mild normal TRUE yes
12 overcast mild high TRUE yes
13 overcast hot normal FALSE yes
14 rainy mild high TRUE no

可以看出，一共14个样例，包括9个正例和5个负例。那么当前信息的熵计算如下：

$$ Entropy(S) = - \frac{9}{14} log_2 \frac{9}{14} - \frac{5}{14} log_2 \frac{5}{14} = 0.940286 $$

在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用属性Outlook来分类，那么如下图：

划分后，数据被分为三部分了，那么各个分支的信息熵计算如下

$$ Entropy(sunny) = - \frac{2}{5} log_2 \frac{2}{5} - \frac{3}{5} log_2 \frac{3}{5} = 0.970951 $$
$$ Entropy(overcast) = - \frac{4}{4} log_2 \frac{4}{4} - 0 \cdot log_2 0 = 0 $$
$$ Entropy(rainy) = - \frac{3}{5} log_2 \frac{3}{5} - \frac{2}{5} log_2 \frac{2}{5} = 0.970951 $$

那么划分后的信息熵为：

$$Entropy(S|T) = \frac{5}{14} \cdot 0.970951 + \frac{4}{14} \cdot 0 + \frac{5}{14} \cdot 0.970951 = 0.693536$$

$Entropy(S|T)$代表在特征属性$T$的条件下样本的条件熵。那么最终得到特征属性$T$带来的信息增益为：

$$IG(T) = Entropy(S) - Entropy(S|T) = 0.24675 $$

信息增益的计算公式如下所示：

$$IG(S|T) = Entropy(S) - \sum\limits_{value(T)} \frac{|S_v|}{S} Entropy(S_v)$$

其中$S$为全部样本集合，$value(T)$是属性$T$所有取值的集合，$v$是$T$的其中一个属性值，$S_v$是$S$中属性$T$的值为$v$的样例集合，$|S_v|$为$S_v$中所含样例数。

信息增益比

在选择决策树中某个结点上的分支属性时，假设为下面这种情况：

（1）假设该结点上的数据集为$DataSet$，则样本总数为$len(DataSet)$

（2）假设数据集$DataSet$，包含$FeatureNumber$个属性

（3）假设属性$Feature$总共有$M$个不同的取值，则利用属性$Feature$可以将数据集$DataSet$划分为$M$个子集，如下所示:

$${DataSet_1,DataSet_2,…,DataSet_N,…,DataSet_M}$$

每个对应的子集的样本的数量为：

$${len_1,len_2,…,len_N,…,len_M}$$

由此，计算出用属性$Feature$来划分给定的数据集$DataSet$所得到的信息增益比为：

$$ GainRatio(Feature)=\frac{ Gain(Feature) }{ split(Feature) }$$
$$ split(Feature)=-\sum\limits_{N=1}^M \frac{ len_N }{ len(DataSet) } \times log_2(\frac{ len_N }{ len(DataSet) } )$$

$Gain(Feature)$的算法和上文计算信息增益的算法是一样的，事实上，求$GainRatio$的过程就是在上述的计算信息增益的过程中加上一个对其“稀释”的作用，使得取值多的$Feature$不会占据主导地位。