特征选择

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

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

1. 信息增益

信息增益（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)。

关于熵、条件熵、互信息参考链接。关于信息增益和互信息之间的差别，参考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)$$

示例：

贷款申请样本数据表：

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

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$。

2. 信息增益比

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

使用信息增益比(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$的取值个数。

3. 基尼指数

分类问题中，假设有$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$为最优切分点。