算法
$\qquad$ 输入：训练数据集 $D$ 和特征 $A$ ;
$\qquad$ 输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 。
$\qquad$ (1) 计算数据集 $D$ 的经验熵 $H(D)$
\[H(D)=-\sum_{k=1}^K \frac {|C_k|} {|D|} \log_2 {\frac {|C_k|} {|D|}}\]$\qquad$ (2) 计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$
\[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|}\]$\qquad$ (3) 计算信息增益
\[g(D,A)=H(D)-H(D|A)\]$\qquad$ (4) 计算信息增益比
\[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$ 取值的个数。
