特征选择在于选取对训练集有分类能力的特征，这样可以提高决策树学习的效率。

通常特征选择的准则是信息增益或信息增益比。

信息增益

信息增益（information gain）表示得知特征$$X$$的信息而使得类$$Y$$的信息不确定性减少称。

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

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

一般地，熵$$H(X)$$与条件熵$$H(Y|X)$$之差称为互信息(mutual information)。

关于熵、[条件熵](/shu-xue-ji-chu/xin-xi-lun/tiao-jian-shang.md)、互信息参考链接。关于信息增益和互信息之间的差别，参考https://www.zhihu.com/question/39436574。

在给定训练数据集$$D$$和特征$$A$$，经验熵$$H(D)$$表示对数据集$$D$$进行分类的不确定性。而经验条件熵$$H(D|A)$$表示在特征$$A$$给定的条件下对数据集$$D$$进行分类的不确定性，那么它们的差就表示由于特征$$A$$而使得对数据集$$D$$的分类的不确定性减少的程度。信息增益大的特征具有更强的分类能力。

信息增益的算法

假设训练数据集为$$D$$，$$|D|$$表示样本容量，即样本个数。设有$$K$$个类$$C_k$$，$$k=1,2,...,K$$，$$|C_k|$$为属于类$$C_k$$的样本个数，$$\displaystyle\sum_{k=1}^K|C_k|=|D|$$。

设特征$$A$$有$$n$$个不同的取值$${a_1,a_2,...,a_n}$$，根据特征$$A$$的取值将$$D$$划分为$$n$$个子集$$D_1,D_2,...,D_n$$，$$|D_i|$$为$$D_i$$的样本个数，$$\displaystyle\sum_{i=1}^n|D_k|=|D|$$。记子集$$D_i$$中属于类$$C_k$$的样本集合为$$D_{ik}$$，$$|D_{ik}|$$为$$D_{ik}$$的样本个数。

算法：

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

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

1）计算数据集$$D$$的经验熵$$H(D)$$

$$ H(D)=-\displaystyle\sum_{k=1}^K \dfrac{|C_k|}{|D|}\mathrm{log}_2 {\dfrac{|C_k|}{|D|}} $$

2）计算特征$$A$$对数据集$$D$$的经验条件熵$$H(D|A)$$

$$ H(D|A)=\displaystyle\sum_{i=1}n \dfrac{|D_i|}{|D|}H(D_i)=-\displaystyle\sum_{i=1}n \dfrac{|D_i|}{|D|}\displaystyle\sum_{k=1}^K \dfrac{|D_{ik}|}{|D_i|}\mathrm{log}2 {\dfrac{|D{ik}|}{|D_i|}} $$

3）计算信息增益

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

示例：

贷款申请样本数据表：

1）计算经验熵$$H(D)$$，样本中“是”有9个，“否”有6个

$$ H(D)=-\dfrac{9}{15}\mathrm{log}_2\dfrac{9}{15}-\dfrac{6}{15}\mathrm{log}_2\dfrac{6}{15}=0.971 $$

2）计算各个特征对数据集的信息增益，$$A_1$$：年龄，$$A_2$$：有工作，$$A_3$$：有房子，$$A_4$$：信贷情况

$$H(D|A_1)=\dfrac{5}{15}H(D_1)+\dfrac{5}{15}H(D_2)+\dfrac{5}{15}H(D_3)$$

$$=\dfrac{5}{15}(-\dfrac{2}{5}\mathrm{log}_2\dfrac{2}{5}-\dfrac{3}{5}\mathrm{log}_2\dfrac{3}{5})+\dfrac{5}{15}(-\dfrac{3}{5}\mathrm{log}_2\dfrac{3}{5}-\dfrac{2}{5}\mathrm{log}_2\dfrac{2}{5})+\dfrac{5}{15}(-\dfrac{4}{5}\mathrm{log}_2\dfrac{4}{5}-\dfrac{1}{5}\mathrm{log}_2\dfrac{1}{5})=0.888$$

$$H(D|A_2)=\dfrac{5}{15}H(D_1)+\dfrac{10}{15}H(D_2)$$

$$H(D|A_3)=\dfrac{6}{15}H(D_1)+\dfrac{9}{15}H(D_2)$$

$$H(D|A_4)=\dfrac{5}{15}H(D_1)+\dfrac{6}{15}H(D_2)+\dfrac{4}{15}H(D_3)$$

3）计算信息增益：

$$g(D,A_1)=H(D)-H(D|A_1)=0.971-0.888=0.083$$

$$g(D,A_2)=H(D)-H(D|A_2)=0.971-0.647=0.324$$

$$g(D,A_3)=H(D)-H(D|A_3)=0.971-0.551=0.420$$

$$g(D,A_4)=H(D)-H(D|A_4)=0.971-0.608=0.363$$

其中$$g(D,A_3)$$最大，因此先选择特征$$A_3$$。

信息增益比

以信息增益比作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。

使用信息增益比(information gain ratio)可以对这个问题进行校正。

特征$$A$$对训练数据集$$D$$的信息增益比$$g_{\small R}(D,A)$$定义为信息增益$$g(D,A)$$与训练数据集$$D$$关于特征$$A$$的值的熵$$H_A(D)$$之比，即

$$ g_{\small R}(D,A)=\dfrac{g(D,A)}{H_A(D)} $$

其中$$H_A(D)=-\displaystyle\sum_{i=1}^n \dfrac{|D_i|}{|D|}\mathrm{log}_2 {\dfrac{|D_i|}{|D|}}$$，$$n$$是特征$$A$$的取值个数。

基尼指数

分类问题中，假设有$$K$$个类，样本点属于第$$k$$类的概率为$$p_k$$，则概率分布的基尼指数定义为

$$ Gini(p)=\displaystyle\sum_{k=1}K p_k(1-p_k)=1-\displaystyle\sum_{k=1}Kp^2_k $$

对于二分类问题，若样本属于第一个类的概率为$$p$$，则概率分布的基尼指数为

$$ Gini(p)=2p(1-p) $$

对于给定的样本集合$$D$$，其基尼指数为

$$ Gini(D)=1-\displaystyle\sum_{k=1}K \dfrac{|C_k|2}{|D|^2} $$

这里$$C_k$$是$$D$$中属于第$$k$$类的样本子集，$$K$$是类的个数。

如果样本集合$$D$$根据特征$$A$$是否取某一个可能的$$\alpha$$被分割成$$D_1$$和$$D_2$$两部分，即

$$ D_1= {(x,y)\in D|A(x)=\alpha},\ \ \ D_2=D-D_1 $$

则在特征$$A$$的条件下，集合$$D$$的基尼指数定义为：

$$ Gini(D,A)=\dfrac{|D_1|}{|D|}Gini(D_1)+\dfrac{|D_2|}{|D|}Gini(D_2) $$

基尼指数$$Gini(D)$$表示集合$$D$$的不确定性，基尼指数$$Gini(D,A)$$表示经过$$A=\alpha$$分割后集合$$D$$的不确定性。基尼指数越大，样本集合的不确定性也越大，这一点与熵相似。在选择特征的时候，选择基尼指数最小（也就是不确定性最小）的特征及其对应的切分点作为最优特征和切分点。

根据上表计算基尼指数：

$$A_1$$：年龄（1，2，3分别表示青，中，老年），

$$Gini(D,A_1=1)=\dfrac{5}{15}(2\cdot\dfrac{2}{5}\cdot (1-\dfrac{2}{5}))+\dfrac{10}{15}(2\cdot\dfrac{7}{10}\cdot (1-\dfrac{7}{10}))=0.44$$

$$Gini(D,A_1=2)=0.48$$

$$Gini(D,A_1=3)=0.44$$

由于$$Gini(D,A_1=1)$$和$$Gini(D,A_1=1)$$相等且最小，所以$$A_1=1,A_1=3$$都可以作为$$A_1$$的最优切分点。

$$A_2$$：有工作（1，2分别表示有，无工作），

$$Gini(D,A_2=1)=0.32$$

$$A_3$$：有房子（1，2分别表示有，无房子）

$$Gini(D,A_3=12)=0.27$$

$$A_2$$和$$A_3$$只有一个切分点，所以它们就是最优切分点。

$$A_4$$：信贷情况（1，2，3分别表示信贷非常好，好，一般）

$$Gini(D,A_4=1)=0.36$$，$$Gini(D,A_4=2)=0.47$$，$$Gini(D,A_4=3)=0.32$$

$$Gini(D,A_4=3)$$最小，所以为$$A_4$$的最优切分点。

在$$A_1,A_2,A_3,A_4$$中，$$Gini(D,A_3=12)=0.27$$最小，所以选择特征$$A_3$$为最优特征，且$$A_3=1$$为最优切分点。