基于最大化联合互信息和最小化联合熵的特征选择

Feature Selection Based on Maximizing Joint Mutual Information and Minimizing Joint Entropy

摘要: 随着大数据时代的到来，数据越来越容易获得，同时获得的数据的维度也越来越高。高维的数据能够详细记录事物的属性，但维度越高，冗余数据也就越多。从数据中剔除冗余特征就显得很重要。基于互信息(MI)的特征选择方法能够有效地降低数据维数和提高分类精度。但现有的方法在特征选择的过程中评判特征的标准单一，无法有效排除冗余特征。本文为此提出了一种基于最大联合互信息和最小联合熵的特征选择方法(JMIMJE)。JMIMJE在特征选择时考虑了整体联合互信息和联合熵两种因素，联合互信息衡量特征子集整体的与分类的相关性，联合熵衡量特征子集的稳定性。JMIMJE在筛选特征时对特征子集的相关性和稳定性进行了平衡。在预测精度方面，JMIMJE比mRMR (最小冗余度最大相关性)提高了2个百分点；与联合互信息(JMI)相比提高了1个百分点。

Abstract: With the advent of the data era, data is getting easier and easier to obtain, and the dimensions of the data are getting higher and higher. Higher-dimensional data can record the attributes of things in detail, but the higher the dimension, the more redundant data. It is important to remove redun-dant features from the data. The feature selection method based on mutual information (MI) is not good at reducing the data dimension and improving the classification accuracy. In the process of feature selection, the existing methods have a single feature evaluation criterion and can not effec-tively eliminate redundant features. A feature selection method (JMIMJE) based on maximum joint mutual information and minimum joint entropy is proposed. JMIMJE considers two factors, global joint mutual information and joint entropy, in feature selection. Combined mutual information to measure the correlation between the whole feature subset and the classification, combined entropy to measure the stability of the feature subset. JMIMJE balances the correlation and stability of fea-ture subsets during feature screening. In terms of prediction accuracy, JMIMJE is 2 percentage points higher than mRMR (minimum redundancy maximum correlation). Compared with Joint Mu-tual Information (JMI), an increase of 1 percentage point.

1. 引言

随着大数据时代的到来，我们能够得到目标的属性信息越来越多，同时也会得到大量的冗余信息。在对数据进行分析之前需要对数据进行筛选。特征选择方法是从高维数据中筛选出相关特征，减少特征个数，从而降低数据分析的复杂度和提高数据的解释度。互信息的优点是计算简单、可解释性强。互信息在深度学习、特征选择中有着广泛的应用。互信息特征选择的一个方向是Filter [1] 类型特征选择的一个方向。目前互信息特征选择方法主要从互信息、条件互信息、联合互信息、联合条件互信息方面研究的，其中条件互信息、联合互信息和联合条件互信息的计算都比较繁琐。为了不再降低特征选择的效率，一般使用选择路线复杂度低、效率高的贪婪向前搜索法。

为了解决互信息无法对相似特征评价的问题，董泽民等 [2] 提出了一种基于联合互信息(joint mutual information, JMI)的特征选择方法。JMI特征选择方法在筛选时不仅考虑特征子集与分类之间的关系，还考虑特征子集与未选特征子集之间的相关性。联合互信息特征选择方法在筛选特征时，随着筛选特征个数的增加，不同未选特征和已选特征的联合互信息趋近。当筛选特征变多时，JMI筛选效果就会变得不佳。本文提出基于最大化联合互信息和最小化联合熵的特征选择方法(feature selection based on maximizing joint mutual information and minimizing joint entropy, JMIMJE)。JMIMJE方法利用联合互信息筛选出效果明显的特征组合，再利用联合熵对联合互信息筛选出的特征组合进行二次筛选，这样筛选出的特征子集即可以保证特征子集与整体的相关性，又可以保证特征子集的稳定性。

2. 相关工作

最早应用于特征选择的互信息是信息增益(Information Cain, IG) [3] ，信息增益只根据特征与分类之间的互信息大小对特征进行筛选，无法对特征是否冗余进行判断。Liu [4] 等人提出了一种可以判断冗余特征的信息增益文本方法。Battiti等人 [5] 提出了不再假设特征之间相互独立的特征选择方法(Multual Information Feature Selection, MIFS)，但MIFS仍有不足之处。Fleuret等 [6] 提出了通过条件互信息降低数据维数的特征选择方法。

Hoque等 [7] 和Cho等 [8] 提出了MIFS的改进方法，MIFS-ND方法和归一化互信息特征选择(Normalized Mutual Information Feature Selection, NMIFS)方法。这两种方法的效果都比MIFS的效果表现的好，但标准不一致的问题没有解决。Peng等 [9] 提出了由MIFS方法改进而来的基于互信息的最小冗余度最大相关性(minimum Redundancy Maximum Relevance, mRMR)的特征选择方法，但mRMR方法对相似特征的判断能力较差。

为了解决对相似特征判断的问题，董泽民等提出了基于联合互信息(Joint Mutual Information, JMI)的特征选择方法。Bennasar等 [10] 在考虑联合互信息整体稳定性之后提出了基于最大化联合互信息(Joint Mutual Information Maximisation, JMIM)的特征选择方法。

综上在进行特征选择时，判断特征是否冗余，筛选出的特征子集会因特征评价函数不同而不同。本文采用联合互信息和联合熵结合的方式，判断特征子集与分类相关性和特征子集的稳定性，希望能提高筛选特征的效果。

3. 互信息理论

1) 信息熵：1948年，英国数学家香农提出了“信息熵”概念。熵是随机变量的不确定度的度量，不确定程度越大，信息熵就越大，信息熵越大概率就越小。

信息熵的公式为：

$H\left(X\right)=-{\displaystyle \underset{x_i\in X}{\sum }p\left(x_i\right)lb\left(p\left(x_i\right)\right)}$ (1)

式中，P(x_i)表示的是x_i在X中的概率密度。

2) 联合熵：联合熵就是度量一个联合分布的随机系统的不确定度。两个变量的联合熵表示两个变量在一起的不确定度。

联合熵的公式为：

$H\left(X,C\right)=-{\displaystyle \underset{x_i\in X}{\sum }{\displaystyle \underset{c_j\in C}{\sum }p\left(x_i,c_j\right)lb\left(p\left(x_i,c_j\right)\right)}}$ (2)

式中，H(X,C)越大，说明随机变量X和C的联合分布的随机系统的不确定度就越大，P(x_i,c_j)表示两个变量的组合概率密度函数。

3) 互信息：互信息是一个变量与另一个变量的共享信息的度量。

互信息公式为：

$I\left(X;C\right)={\displaystyle \underset{x_i\in X}{\sum }{\displaystyle \underset{c_j\in C}{\sum }p\left(x_i,c_j\right)lb\left(\frac{p\left(x_i,c_j\right)}{p\left(x_i\right)p\left(c_j\right)}\right)}}$ (3)

式中，I(X,C)表示X与C之间的共享信息度量，I(X,C)越大说明X与C之间的相关性越强。

4) 联合互信息：联合互信息是一个联合分布的随机系统整体包含一个随机变量的信息量。

联合互信息公式为：

$I\left(X,Y;C\right)={\displaystyle \underset{x_i\in X}{\sum }{\displaystyle \underset{y_j\in Y}{\sum }{\displaystyle \underset{c_k\in C}{\sum }p\left(x_i,y_j,c_k\right)lb\left(\frac{p\left(x_i,y_j,c_k\right)}{p\left(x_i\right)p\left(y_j\right)p\left(c_k\right)}\right)}}}$ (4)

式中，I(X;C)表示X、Y整体与C之间的共享信息度量，I(X,Y;C)越大说明X、Y整体与C之间的相关性越强。

4. 问题陈述与分析

对高维数据进行筛选时，我们总是尽可能的剔除冗余的特征，利用少量的数据进行分析，对少量数据进行分析得到的结果具有吸引力和说服力。

设 $X=\left(x_1,x_2,\cdots ,x_n\right)$ ，X为全特征集合， $x_i\in X$ ， $1\le i\le n$ ，n表示为特征总量； $X=\left(x_1^i,x_2^i,\cdots ,x_m^i\right)$ 表示为所选特征集合的一个样本的样本值， $1\le m\le n$ 。当n较大，且 $m\ll n$ 时，不同的特征评价标准筛选出的特征子集不同，这时用互信息和联合互信息来计算，效果不佳 [11] 。

基于互信息的特征选择是从全部特征集合中挑选出w个特征构成的特征子集 $S\in \left(x_1,x_1,\cdots ,x_w\right)$ ， $S\in X$ ，在高维多特征数据子集的特征筛选时，特征子集的联合互信息是小于因变量的信息熵。特征子集的联合互信息是对因变量信息熵的解释，若联合互信息 = 因变量的信息熵，那么特征子集就能百分百解释因变量。特征子集的联合熵是特征子集的不确定度。在高维数据中，联合互信息随着特征子集个数的增加而增加，联合互信息的增加速度是递减的。随着特征子集中特征个数的增加，待选特征子集的联合互信息比较接近，这时用联合互信息筛选特征子集的效果不好；在联合互信息相近时，联合熵小的特征子集的效果好。

下面对不同特征选择方法的计算过程进行比较。

1) IG特征选择：

这种方法是将每个特征与分类的信息增益值从大到小排序，选取前k( $1\le k\le n$ )特征即可。IG只能辨别单个特征对分类的相关性，无法衡量多个特征对分类的相关性。

2) mRMR特征选择：

$\alpha \left(f_i\right)=I\left(f_i;C\right)-\frac{1}{S}{\displaystyle \underset{f_s\in S}{\sum }I\left(f_i;f_s\right)}$ (5)

其中计算以 $I\left(f_i;C\right)$ 为基础值，考虑未加入的特征与每个子特征的互信息。mRMR特征选择方法能够排除与已选特征具有直接相关的特征，但无法筛选具有间接相关的特征，当 $f_i\in F-S$ 时， $f_{s1},f_{s2}\in S$ ，f_i分别与f_s1、f_s2独立，当 $I\left(f_i;f_{s1}\right)$ 与 $I\left(f_i;f_{s2}\right)$ 接近时，mRMR无法判断新加入的特征f_i是否合适。mRMR特征选择能够排除与已选特征具有直接相关的特征，但无法筛选具有间接相关的特征。当用JMI筛选特征时就不会出现这样的问题。

3) JMI特征选择：

$\alpha \left(f_i\right)={\displaystyle \underset{f_s\in S}{\sum }I\left(f_i,f_s;C\right)}$ (6)

根据JMI的计算公式可以得出，JMI考虑每一个f_i加入之后的特征子集整体与分类的联合互信息。JMI在筛选特征时考虑的是特征子集与分类的相关性，只要 ${\displaystyle {\sum }_{f_s\in S}I\left(f_i,f_s;C\right)}$ 计算值较大即可。

可以通过表1的ionosphere的数据集说明JMI存在的问题。ionosphere数据集是离散 + 连续型数据集，该数据集共有34个特征和一个分类。JMI在筛选特征时，随着筛选特征个数的增加，筛选特征子集的稳定性就变得更加重要。表2为JMI筛选特征的互信息和联合互信息。在筛选特征子集的联合互信息接近时，特征子集的稳定性与特征子集分类的准确性成正比。

该数据集共有34个特征( $f_1,f_2,\cdots ,f_{34}$ )和分类f₃₅，样本数量为351个。根据JMI计算方式筛选的前三个特征为f₁₄、f₁₉、f₁₅，其联合互信息和联合熵为0.9273517、5.636871；f₁₄、f₁₉、f₃的联合互信息和联合熵为0.9140590、4.376591。在分类的准确率上f₁₄、f₁₉、f₁₅的准确率小于f₁₄、f₁₉、f₃的准确率。在联合互信息接近时，联合熵小的特征子集的分类准确率高于联合熵大的特征子集。

Table 1. Characteristics and classification of ionosphere data

表1. Ionosphere数据的特征及分类

Table 2. Ionosphere mutual information and joint mutual information

表2. Ionosphere的互信息和联合互信息

通过对IG、mRMR、JMI方法分析可以得出，mRMR在进行特征选择时考虑单个特征加入后的互信息的大小，无法排除两个及两个以上特征相关情况。JMI通过联合互信息的方式降低了两个及以上特征相关情况，无法排除稳定性较差的特征子集。随着已选特征子集S中特征个数的增加，特征子集的稳定性也就显得重要起来。从下图1可以得出随着特征子集S个数的增加，ionosphere的联合互信息增加速度呈指数递减，当选择的特征子集个数达到g (0 < g ≤ n)时，该数据集的联合互信息稳定下来。ionosphere的联合熵增加速度也呈指数递减，但减小幅度小于联合互信息的减小幅度。

(a) ionosphere数据集的联合互信息 (b) ionosphere数据集的联合熵

Figure 1. Joint mutual information and joint entropy of the ionosphere dataset

图1. Ionosphere数据集的联合互信息和联合熵

对于以上方法存在的问题，本文提出的方法兼顾特征子集的相关性和稳定性。当有多个相似值存在时，通过联合熵的选择在筛选特征子集与分类的相关性和筛选特征子集的稳定性之间找到平衡。

5. JMIMJE总体思路

JMIMJE特征选择方法从联合互信息和联合熵两方面筛选特征，通过对已选特征与未选特征的联合互信息筛选出联合互信息较大值的特征集合C，再通过联合熵对特征集合C进行二次筛选。这种方法可以解决现有联合互信息在特征选择过程中出现的无法排除冗余及不相关特征的问题。在指定子集大小的情况下，挑选出的特征子集S与分类的相关性最大，稳定性较高。

5.1. 最大联合互信息

1) 特征相关性：当已选特征子集 $S=\left\{f_1,f_2,\cdots ,f_{s-1},f_s\right\}$ ， $f_i,f_j\in F-S$ ，如果 $I\left(f_i,S;C\right)>I\left(f_j,S;C\right)$ ，那么在已选特征子集S的前提下，特征f_i和已选特征子集S整体与分类C的相关性强于特征f_j和已选特征子集S整体与分类C的相关性。

2) 最大联合互信息的计算：

Table 3. Maximum joint mutual information schematic table

表3. 最大联合互信息示意表

表3中，当子集 $S=\left\{f_1\right\}$ 时，从未选特征集合 $\left\{f_2,f_3,f_4,f_5\right\}\in F-S$ 中筛选特征。表中的null表示已加入集合S的特征，将 $\left\{f_2,f_3,f_4,f_5\right\}$ 分别与子集 $\left\{f_1\right\}$ 计算得到 $I\left(f_1,f_2;C\right)$ 、 $I\left(f_1,f_3;C\right)$ 、 $I\left(f_1,f_4;C\right)$ 和 $I\left(f_1,f_5;C\right)$ 。当 $I\left(f_1,f_2;C\right)$ 为最大值时，从F-S中筛选出最佳特征f₂，此时筛选出的特征集合 $S=\left\{f_1,f_2\right\}$ 为最佳特征子集。同理，从 $\left\{f_3,f_4,f_5\right\}$ 挑选出联合互信息最大值加入集合S中，这样筛选出的特征子集S与C的相关性较强。

5.2. 最小联合熵

Table 4. Minimum joint entropy schematic table

表4. 最小联合熵示意表

表4中，当子集 $S=\left\{f_1\right\}$ ，将 $\left\{f_2,f_3,f_4,f_5\right\}$ 分别与子集 $\left\{f_1\right\}$ 计算得到 $H\left(f_1,f_2\right)$ 、 $H\left(f_1,f_3\right)$ 、 $H\left(f_1,f_4\right)$ 和 $H\left(f_1,f_5\right)$ ，当 $H\left(f_1,f_2\right)$ 为最小值时，从F-S中筛选出特征f₂，说明特征子集 $\left\{f_1,f_2\right\}$ 的稳定性最好。同理，从 $\left\{f_3,f_4,f_5\right\}$ 筛选出联合熵最小值加入集合S中，这样筛选出的集合S的稳定性较强。

5.3. 最大联合互信息和最小联合熵

在特征选择的过程中，我们希望每次选择的特征集合S与分类C之间的相关性都能得到最大提升，联合互信息值体现了特征子集整体与分类的相关性，联合熵体现了特征子集的不确定度。本文希望得到的是与分类相关性强和稳定性强的特征子集，对这样的子集进行回归、分类和分析时得到的结果就更准确。

本文先用联合互信息的值筛选出未选特征集合{F-S}中联合互信息最大值的特征i，或者与联合互信息最大值接近的特征j、k；然后再计算出未选特征 $\left\{i,j,k\right\}$ 与已选特征集合S的联合熵，未选特征 $\left\{i,j,k\right\}$ 与已选特征集合S的联合互信息为M，与已选特征集合S的联合熵为H；选出特征 $\left\{i,j,k\right\}$ 中M/H值最大的特征加入特征集合S中。这样选出的特征集合与分类C之间的相关性能得到保证，其稳定性也强于其他方法筛选的特征子集。

5.4. 方法流程

输入：数据集F，分类C，特征数N，要选择的特征个数num；

输出：要选择的特征集合S

1) S←Ø

2) list←0/计算特征与分类的互信息

3) S = max(list)/选取最大的互信息特征加入S

4) For i = 1 to (N-S) do

5) 计算F-S中每个特征和已选特征子集S与分类C的联合互信息并储存M

6) End for

7) 选取M中联合互信息最大值的特征，加入到特征子集S中

8) 重复步骤4~7，直到选取num-2个特征

9) 从F-S中选取2个特征计算联合互信息并储存M

10) 选取M中联合互信息最大值和联合互信息最大值近似的特征

11) 计算选取的特征的联合熵H

12) 选取M/H值最大的特征加入特征子集S

13) 输出特征子集S

6. 实验验证

6.1. 实验方案

表5的实验数据来自UCI公开的数据集，实验数据来自UCI公开的数据集，实验数据包括离散数据、连续数据、离散 + 连续数据。实验中还将IG、mRMR、JMI与JMIMJE进行比较，用判别分析对选择的特征进行验证。通过分类的正确率判断选择特征的合理性。

连续变量的联合互信息的计算是比较繁琐的。目前，连续变量联合互信息的计算方法是将连续变量离散化，然后计算离散变量的联合互信息。连续变量的联合互信息与连续变量离散化的联合互信息还是有一些区别的。将每个数据集随机划分出70%的数据用作训练集，整个数据集用作测试集；将实验数据中的连续型数据转化成离散型数据；再将不同方法已选的特征子集S输入到贝叶斯分类模型中，用分类的准确率来判断特征子集的合理性。图2为实验流程图。

Table 5. Experimental data set

表5. 实验数据集

Figure 2. Experimental flow

图2. 实验流程

6.2. 实验预测精度分析

图3中，横坐标表示数据集上选择的特征个数，纵坐标表示对应特征个数下贝叶斯分类预测精度。通过不同的数据集上不同特征选择方法的分类预测精度变化图可以得出下列结论。

(a) ionosphere (b) wine (c) wdbc (d) kr-vs-kp

Figure 3. Different methods are accurate in selecting the number of features

图3. 不同方法在选择特征个数是的精确度

1) 从图3中可以看到JMIMJE在样本较少的数据集上的预测结果：在ionosphere数据集中，JMIMJE在筛选第9、10个特征时的分类准确率小于JMI筛选特征的分类准确率；wine数据集用JMIMJE筛选特征第7、8、11、12个特征时的分类准确率小于JMI的分类准确率。在预测精度上，JMIMJE的分类准确率要高于JMI的分类准确率；kr-vs-kp数据集用JMIMJE筛选少量特征(小于50%特征总数)时的分类准确率优于其他三种特征选择方法的分类准确率。

2) 在特征个数逐渐增加时，特征选择方法在预测精度上呈现先增加后减小的趋势：IG、mRMR在特征选择时并没有明显表现出这一趋势。IG和mRMR的预测精度有上下波动的情况，这是IG、mRMR在特征选择时考虑的标准比较单一所造成的，加入的特征为提供分类的信息量相对于其他变量较少。

3) 表6的wine数据集上，在wine数据集上，JMIMJE的平均预测精度比IG、mRMR的平均预测精度提升了1个百分点，比JMI提升了0.1个百分点。在ionosphere数据集上，JMI的平均预测精度最低，原因是在筛选少量特征的预测精度时出现了较大的偏差。在wdbc数据集上，JMIMJE的预测精度最高。在kr-vs-kp数据集上，JMIMJE的平均预测精度最高，其预测精度在少量(低于50%)特征上的预测精度明显高于其他三种方法。

4) JMIMJE特征选择方法在分类时考虑了特征子集与分类的相关性和特征子集的稳定性。JMI和JMIMJE的预测精度波动总体上小于IG、mRMR的预测精度的波动，这说明了JMI和JMIMJE的预测稳定性好于IG和mRMR。在预测精度上，JMIMJE的平均预测精度要高于IG、mRMR和JMI。

Table 6. Comparison of prediction accuracy of different methods

表6. 不同方法的预测精度对比

7. 结论

本文比较了4种特征选择方法筛选特征在不同数据集上的平均预测精度，JMIMJE从联合互信息和联合熵两个方面对特征选择进行筛选，在保证了特征子集与分类相关性的同时增加了特征子集的稳定性。JMIMJE平均预测精度高于IG、mRMR和JMI的平均预测精度，其波动性小于IG、mRMR和JMI的预测波动性。同时，JMIMJE也有其不足之处，在数据不均衡的情况下筛选效果不佳。