ID3

作者: zhouycoriginal | 来源:发表于2020-02-04 13:25 被阅读0次

基于信息增益(Information Gain)的ID3算法

ID3算法的核心是在各个结点上应用信息增益准则来进行特征选择，以此递归的构建决策树，具体方法是：从根结点开始，对结点计算所有可能的信息增益，选择信息增益最大的特征作为该结点的特征，结点的信息增益根据样本的标签进行计算。

信息增益

熵

信息增益与熵(entropy)有关，在概率论中，熵是随机变量不确定性的度量，熵越大，随机变量的不确定性就越大；假设 $X$ 是取有限个值的离散随机变量，其概率分布为：
$P(X=x_i)=p_i,i=1,2,3,...,n$
则，熵的定义为：
$H(X)=-\sum_{i=1}^{n}p_i*\log{p_i}$ 一般取自然对数 $e$ 为底数
值得注意的是，熵实际上是随机变量 $X$ 的分布的泛函数，它并不依赖 $X$ 的实际取值，而仅仅依赖 $X$ 的概率分布，所以它又可以被记作：
$H(p)=-\sum_{i=1}^{n}p_i*\log{p_i}$
其中, $n$ 表示 $X$ 的 $n$ 种不同的取值, 这个值一般是离散的. $p_i$ 表示为 $X$ 取到值为 $i$ 的概率. $log$ 一般是自然底数
例子:

条件熵

多个变量的熵叫联合熵, 比如两个变量 $X,Y$ 的联合熵就表示为:
$H(X,Y)=-\sum_{i=1}^{n}p_{(x_i,y_i)}\log p_{(x_i,y_i)}$
类似于条件概率,熵同样也存在着条件熵, 条件熵描述了知道某个变量以后, 剩下的变量的不确定性, 其表达式如下:
$H(X|Y)=-\sum_{i=1}^{n}p_{(x_i,y_i)}\log p(x_i|y_i)$

信息增益

$H(X)$ 度量了 $X$ 的不确定性, $H(X|Y)$ 度量了知道 $Y$ 后, $X$ 的不确定性, 那么 $H(X)-H(X|Y)$ 度量的可以理解为:知道 $Y$ 的基础上, $X$ 不确定性减少的程度,我们记为 $I(X,Y)$ ,如图:

更多理解

假定当前样本集合 $D$ 中,第 $k$ 类样本所占比例为 $p_k(k=1,2,3...,|y|)$ , 则 $D$ 的信息熵定义为:
$Ent(D)=-\sum_{k=1}^{|y|}p_k \log p_k$
假定离散属性 $a$ 有 $V$ 个可能的取值 ${a^1,a^2...a^v}$ , 若使用 $a$ 来对样本集进行划分,则会产生 $V$ 个分支结点, 也就是说, ID3构建的决策树, 是多叉树, 那么它的信息增益就是
$Gain(D,a) = Ent(D)-\sum_{v=1}^{V} \frac{|D^v|}{|D|}Ent(D^v)$
比如: 一个二分类数据集, 包含17个样本, 其中正例为8,反例为9,那么, 数据集 $D$ 的信息熵为:
$Ent(D)=-(\frac{8}{17}\log \frac{8}{17}+\frac{9}{17}\log \frac {9}{17})$
对于变量 $a$ ,他有三个取值, 那么它可以将数据集划分为三个子集: $D^1,D^2,D^3$ , 其样本里分别为6,6,5, 这三个自数据集中, 正负样本分别为(3,3) (4,2),(1,4), 这三个分支结点的信息熵为为:
$Ent(D^1)=-(\frac{3}{6} \log \frac{3}{6}+\frac{3}{6} \log \frac{3}{6})$
$Ent(D^2)=-(\frac{4}{6} \log \frac{4}{6}+\frac{2}{6} \log \frac{2}{6})$
$Ent(D^3)=-(\frac{1}{5} \log \frac{1}{5}+\frac{4}{5} \log \frac{4}{5})$
那么变量 $a$ 的信息增益为:
$Gain(D,a)=Ent(D)-\sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v)$