基于高维复杂数据的变量选择方法研究

Research on Variable Selection Method Based on High-Dimensional Complex Data

摘要: 针对目前大多数基于信息论的线性累加特征选择算法的缺点和不足，将类别变量的信息，引入到对待选特征与已选特征子集的冗余性度量之中，考虑到特征与类别变量之间的对称不确定度，提出了一种新的以信息论为基础的，基于最大相关最小冗余原则的过滤式特征选择方法，并在11个公开的标准数据集上进行了验证，通过与6种其他基于信息论的特征选择方法的结果进行对比，验证了所提出的算法的有效性。

Abstract: In view of the shortcomings and deficiencies of most current linear accumulation feature selection algorithms based on information theory, the information of categorical variables is introduced into the redundancy measure of the feature to be selected and the selected feature subset, taking into account the relationship between the feature and the categorical variable, a new filtering feature selection method based on information theory and the principle of maximum correlation and min-imum redundancy is proposed, and verified on 11 public standard datasets. The results of six other information theory-based feature selection methods are compared to verify the effectiveness of the proposed algorithm.

1. 引言

随着计算机技术与网络的发展，数据的采集、存储的设备与方法日益普及和不断更新，我们所需要面对的数据集从以前的简单特征数据集向具有数据存储量巨大、数据结构多样、数据属性维数高、数据相关性强、数据特征时变等特点的大规模复杂数据集发展。在现代数据分析过程中，第一步也是必不可少的步骤就是对数据进行降维。降维主要有两种方法：特征提取和特征选择。与特征提取相比，特征选择可以保留原始特征，使结果的解释具有现实意义。所以在本文的研究中，我们关注的是特征选择而不是特征提取。

按照特征选择过程与分类器之间的关系，特征选择方法一般被分为嵌入式特征选择方法(Embedded) [1] [2]，包装式特征选择方法(Wrapper) [3] 和过滤式特征选择方法(Filter) [4] [5] [6] 三大类。嵌入式(Embedded)特征选择方法在选择特征的过程中同时完成了模型的学习。包装式(Wrapper)特征选择方法是使用分类算法对特征选择得到的特征子集进行评价，通过使用特定分类器的预测精度作为所选特征子集质量的度量来搜索特征空间并测试所有可能的特征组合子集。过滤式(Filter)特征选择方法是独立于分类器的，不与特定的分类器相关联，它根据一些标准来评估特征的预测能力。并且基于过滤式(Filter)的特征选择方法计算量相对小，通用性强，简单高效的特点，同时也可以作为数据挖掘中的预处理步骤，与其他各种方法结合，具有良好的性质。因此本文将研究重点放在基于互信息的过滤式特征选择方法。

2. 信息论的基本概念

2.1. 熵原理及信息熵

本文算法是基于信息论的，因此本节首先介绍一些信息论的基本概念 [7]。

熵概念的建立将不确定性和信息量结合到了一起，事件发生的概率越低，所蕴含的信息量就越大。

随机变量的熵是对其不确定性的度量，以及描述随机变量所需的平均信息量。对于离散的随机变量 $X=\left\{x_1,x_2,\cdots ,x_N\right\}$ 和随机变量 $Y=\left\{y_1,y_2,\cdots ,y_M\right\}$，信息熵定义为：

$H\left(X\right)=-{\displaystyle \underset{i=1}{\overset{N}{\sum }}p\left(x_i\right)\log \left(p\left(x_i\right)\right)}$

2.2. 互信息

互信息(MI)是信息论的另一个重要概念。它是新引入的变量所提供的信息量，也可以看作是两个变量共享的信息量。MI用于量化两个变量之间的相互依赖关系。当两个变量相互独立时，MI为零，并且随着一个变量对另一个变量的依赖程度的增加而增加。变量Y和变量X之间的互信息记为I(Y; X)，可以表述为：

$I\left(X;Y\right)={\displaystyle \int p\left(x,y\right)\log \frac{p\left(x,y\right)}{p\left(x\right)p\left(y\right)}\text{d}x\text{d}y}$

很难准确地找到概率密度函数(p(x)，p(y)，p(x, y))。因此，通常首先对连续变量进行离散化，然后用离散定义计算熵和互信息。

互信息可以被条件化，条件互信息 $I\left(Y;X_i|X_j\right)$ 量化了选择 $X_j$ 时 $X_i$ 提供的新判别信息，定义如下：

$I\left(Y;X_i{X}_j\right)={\displaystyle \underset{x_j\in X_j}{\sum }p\left(x_j\right)}{\displaystyle \underset{x_i\in X_i}{\sum }{\displaystyle \underset{y\in Y}{\sum }p\left(y,x_i{x}_j\right)}}\log \frac{p\left(y,x_i{x}_j\right)}{p\left(y{x}_j\right)p\left(x_i{x}_j\right)}$

联合互信息(JMI)量化了Y和联合变量( $X_i,\cdots ,X_k$ )共享的信息，定义如下：

$I\left(Y;X_i,\cdots ,X_k\right)=H\left(Y\right)-H\left(Y|X_i,\cdots ,X_k\right)$

将三个变量之间共享的信息量定义为交互信息，其定义如下：

$I\left(Y;X_i;X_j\right)=I\left(Y;X_i\right)+I\left(Y;X_j\right)-I\left(Y;X_i,X_j\right)$

$I\left(Y;X_i;X_j\right)$ 的值可以是正数、负数或零，也可以看作是两个特征共享的判别信息。如果 $I\left(Y;X_i;X_j\right)$ 为正，则表示X_i，X_j有冗余。如果 $I\left(Y;X_i;X_j\right)$ 为负数，则表示X_i，X_j是互补的。当 $I\left(Y;X_i;X_j\right)$ 为零时，表示X_i和X_j相互独立。所以条件互信息 $I\left(Y;X_i|X_j\right)$ 可以重写为 $I\left(Y;X_i|X_j\right)=I\left(Y;X_i\right)-I\left(Y;X_i;X_j\right)$。这意味着候选特征提供的新信息越多，它对应的冗余信息就越少。

3. 相关工作

基于信息论的特征选择算法主要可以分为两类，一类是基于线性累积求和思想的特征选择方法，其主要思想是通过求累积和的方式来判断特征与类别的相关性大小，从而选出符合一定标准的特征，大多数方法都是基于此种思想。还有一类是基于非线性计算的特征选择方法。原则是认为通过求和的方式会过高的估计公共冗余信息所占的比例，希望通过非线性的方式来代替求和，以降低对公共冗余信息估计的误差。

布朗 [8] 等人认真分析和研究了基于互信息的特征选择方法，并提出了统一的特征选择框架。我们可以看到，现有的大多数基于信息论的方法都可以从这个框架中衍生出来。实际上，这个框架是基于线性累积求和思想的线性组合。定义如下：

$J\left(X_i\right)=I\left(Y;X_i\right)-\beta {\displaystyle \underset{X_j\in S}{\sum }I\left(X_i;X_j\right)}+\gamma {\displaystyle \underset{X_j\in S}{\sum }I\left(X_i;X_j|Y\right)}$

在这个公式中，它涉及到三种信息：相关性、冗余性和互补性。当 $\beta$ 和 $\gamma$ 取不同的值时，可以得到

不同的特征选择方法。例如，当 $\gamma =0$ 时，可以得到MIFS方法，当时，可以得到JMI方法，当 $\gamma =0$ 且 $\gamma =\frac{1}{\left|S\right|}$ 时，可以得到mRMR，而当 $\gamma =\beta =0$ 时，能够得到MIM。相关性和冗余是两个矛盾的方面，高相关性通常意味着高冗余，如何平衡这两个方面仍然是特征选择方法的一个悬而未决的问题。

在此基础上，Wang [9] 等人又提出(最大相关性和最大独立性，MRI)特征选择算法，提出的算法独立的分类信息(独立分类信息，ICI)，即 $I\left(Y;X_i,X_j\right)=I\left(X_i;Y|X_j\right)+I\left(X_j;Y|X_i\right)$，其筛选标准为

$J_{\text{MRI}}\left(X_i\right)=I\left(X_i;Y\right)+{\displaystyle \underset{X_j\in S}{\sum }I\left(X_i;Y|X_j\right)}+I\left(X_j;Y|X_i\right)$

基于非线性计算的特征选择方法有以下几种：条件互信息最大化(CMIM) [10] 采用“最大化最小值”的标准。通过选择最小条件互信息最大的特征，CMIM确保所选特征既具有单独的信息量，又相互弱依赖。CMIM定义如下：

$J_{\text{CMIM}}\left(X_i\right)=\arg {\max }_{X_i\in F-S}\left(\underset{X_j\in S}{\min }\left(I\left(Y;X_i|X_j\right)\right)\right)$

李 [11] 等人认为交互信息是优于条件互信息，并提出联合互信息最大化算法(JMIM)基于最大和最小标准。这算法的评价标准如下：

$J_{\text{JMIM}}\left(X_i\right)=\arg {\max }_{X_i\in F-S}\left(\underset{X_j\in S}{\min }\left(I\left(Y;X_i,X_j\right)\right)\right)$

Zeng等人 [12] 提出了一种基于动态交互权重的特征选择方法IWFS，可以动态的影响到候选特征与类别变量的交互关系，同时，以对称不确定性的互信息来衡量相关关系，其评价标准如下：

$J_{\text{IWFS}}\left(X_i\right)=\left(IW\left(X_i,X_j\right)+1\right)\times SU\left(X_i,Y\right)$

其中， $IW\left(X_i,X_j\right)=1+\frac{I\left(X_i;X_j;Y\right)}{H\left(X_i\right)+H\left(X_j\right)}$ 定义为动态交互因子，并且得到了 $0\le IW\left(X_i;X_j\right)\le 2$ 的结论。进一步分析后可以判断，若 $0\le IW\left(X_i;X_j\right)\le 1$，则两个特征之间为冗余的关系；若 $1\le IW\left(X_i;X_j\right)\le 2$，则两个特征之间为冗余的关系。 $SU\left(X_i,Y\right)$ 代表的是对称不确定度，其定义为 $SU\left(X_i,Y\right)=2\times \frac{I\left(X_i;Y\right)}{H\left(X_i\right)+H\left(Y\right)}$，同时这也是一种标准化互信息的定义，在部分文献中，也被用 $NMI\left(X_i,Y\right)$ 来表示。

胡等人 [13] 提出了动态相关和联合互信息最大化算法(DRJMIM)，其评价标准如下：

$J_{\text{DRJMIM}}\left(X_i\right)=\underset{X_j\in S}{\min }\left(I\left(X_i;X_j;Y\right)\right)\times I\left(X_i;Y\right)+2\times \frac{I\left(X_i;Y|X_j\right)-I\left(X_i;Y\right)}{H\left(X_i\right)+H\left(Y\right)}\times I\left(X_j;Y\right)$

高等人 [14] 将已选特征动态变化项与“最大相关最小冗余”原则相结合，采用先全局函数上首先选择最小的冗余特征，再选择最相关的特征的方式来进行特征选择，其评价标准是：

$J_{\text{NDCSF}}\left(X_i\right)=\arg {\max }_{X_i\in F-S}\left(\underset{X_j\in S}{\min }\left(I\left(X_i;Y|X_j\right)+I\left(X_j;Y|X_i\right)-I\left(X_i;X_j\right)\right)\right)$

4. 本文算法

从对上述基于信息论的特征选择算法的分析来看，大多数的特征选择算法仅根据相关性和类无关特征的冗余性，过于依赖类的特征。这些算法存在两个明显的缺点，一个是计算相关性时，忽略了类别与特征之间因数量大而存在偏差，二是对特征冗余的高估，无法处理好特征间的高阶关系。

针对于上面总结出的两大问题，分别提出解决办法，综合考虑后，提出一种新的特征选择方法：

第一，针对互信息在多值目标与特征之间存在的偏差问题，使用对称不确定性度量的互信息来解决。对称不确定性度量的互信息也是一种标准化的互信息，其表示如下：

$NMI\left(X_i;Y\right)=2\times \frac{I\left(X_i;Y\right)}{H\left(X_i\right)+H(\; Y\; )}$

当特征间具有复杂的交互关系时，单纯的计算互信息来衡量特征与目标变量间的相关关系，忽略其交互的信息在总的不确定度下的比重，也可能会高估某些特征的重要性，而通过考虑对称不确定度的互信息，是一种很好的解决方案。

第二，针对特征冗余的高估，无法处理好特征间的高阶关系的问题，所有考虑到冗余项的基于信息论的特征选择方法都需要计算包含已选特征子集的互信息或条件互信息，如 $I\left(S,Y\right)=I\left(X_1,X_2,\cdots ,X_k;Y\right)$。其中的计算涉及到高维的概率密度函数，由于样本的限制，所有关于已选特征子集的互信息都不能得到精确计算，只能采用逼近的方法近似计算。经典的特征选择算法都是在使用多个低维互信息公式的相加来近似表示高维互信息的计算，近似过程中不可避免地会产生重复计算而过高的估计某些特征所含的信息，造成冗余。

所以要避免使用线性累和的方法计算冗余度，可以通过极端值来代替平均累积和。可以用 $I\left(X_i,S,Y\right)$ 来表示待选变量X_i与已选特征集合S和目标变量Y之间的交互信息， $I\left(Y;X_i|S\right)$ 来表示已知已选特征集合S时，待选变量X_i和目标变量Y之间的条件互信息。通过信息论的知识可得，

$I\left(Y;X_i|S\right)\le \underset{X_j\in S}{\min }\left(I\left(Y;X_i|X_j\right)\le \frac{1}{\left|S\right|}{\displaystyle \underset{X_j\in S}{\sum }I\left(Y;X_i|X_j\right)}\right)$

$I\left(X_i,S,Y\right)\le \min \left\{I\left(X_i;S\right),I\left(S;Y\right),I\left(X_i;Y\right)\right\}$

极端准则方法比使用平均原理的方法产生的冗余更少，并且在某些特殊情况下可以获得更好的结果。

我们可以通过交互信息与条件互信息来度量待选特征、已选特征子集和类别变量之间的冗余。首先， $I\left(X_i;X_j\right)$ 度量的是待选特征与一个已选特征之间的冗余， $I\left(X_i;X_j|Y\right)$ 度量的是已知类别变量Y时，待选特征X_i与已选特征X_j之间的冗余， $I\left(X_i;X_j|Y\right)$ 与 $I\left(X_i;X_j\right)$ 的值越大，说明候选特征与已选特征的关系越紧密，候选特征与已选特征越冗余。采用极端准则方法来降低对冗余的过高估计。 $I\left(X_i;Y|X_j\right)$ 与冗余的差越大，代表对分类的结果帮助越大。

所以基于最大相关最小冗余原则的特征选择方法NMI-JMI的筛选标准为：

$J_{\text{NMIJMI}}\left(X_i\right)=NI\left(X_i,Y\right)-\max \{I\left(X_i;Y|X_j\right)-I\left(X_i;X_j|Y\right)\}$

因此，NMIJMI算法可以看作是一个过滤式特征选择算法。我们将它命名为NMIJMI是因为其结合了标准化互信息NMI与联合互信息JMI的原理。

算法的伪代码

输入：原始数据集M，其中包括所有特征 $F=X_1,X_2,X_3,\cdots ,X_n$ 和类别变量Y；指定的特征子集阈值K

输出：选择出的特征子集S

1: 初始化： $S=\varnothing$，k = 1

2: for i = 1 do

3: 计算每个候选特征与类别变量之间的对称不确定度 $NMI\left(X_i;Y\right)$

4: end for

5: 从 $NMI\left(X_i;Y\right)$ 中选择最大的值，将令 $NMI\left(X_i;Y\right)$ 最大时的X_i记作X_selected

6: $S=S\cup X_j$

7: F = F − X_selected

8: while k < K do

9: for $X_i\in F$ do

10: 计算 $J_{\text{NMIJMI}}(\; X\; i\; )$

11: end for

12: 从 $J_{\text{NMIJMI}}\left(X_i\right)$ 中选择最大的值，将令 $J_{\text{NMIJMI}}\left(X_i\right)$ 最大时的X_i记作X_selected

13: $S=S\cup X_j$

14: F = F − X_selected

15: k = k + 1

16: end while

5. 实验结果与分

为了说明所提出方法的性能，我们在十一个基准数据集上将其与六种基准方法mRMR、CMIM、JMI、NMIFS、MRI和JMIM进行了比较。由于本文的对比实验采用的是公开的标准数据集，所以不需要验证特征与类别变量的相关性。

这些数据集来自UCI机器学习库和scikit特征选择库，实例的大小从77到7797不等，特征数量从18到5469不等，类的数量从2到26不等。这些数据集来自不同的应用领域，其中WDBC和DLBCL是生物学数据，Movement为视频处理数据，COIL20、ORL、faces为人脸图像数据，Isolet为音频处理数据，semeion为手写图像数据，vehicle是车辆数据，CNAE9是文本数据，sonar是声呐数据集，这些数据集的特点是如表1所示：

Table 1. Eleven public data sets

表1. 十一个公共数据集

以上数据集都被广泛地用于各种特征选择算法中，所以本文使用这十一个数据集作为研究对象。虽然这十一个数据集都已经被从最开始的原始数据转为了数值型数据集，但是在进行特征选择之前，进行离散化处理。通过观察数据集的具体数据，本文选取等距离散法作为对连续型数据的离散化方法。为了便于对互信息的计算，决定将所有的数据划分到20个不同的区间并用区间的中点值对区间内的数据重新赋值。在本次实验中，我们对数据使用10-折交叉验证划分训练集和验证集，实现对分类器的训练及验证过程，使用的是经过筛选得到的特征子集中的原始数据。为了消除量纲对结果的负面影响，使得所有特征在数值上具有可比性，对每列特征采用min-max标准化方法进行标准化处理。

如果数据集的特征数的一半超过50，选择，50个特征，如果数据集的特征数小于100，则选择该数据集的所有特征数的一半。将不同特征选择算法下得到的特征子集在同一个分类器上学习，将获得的分类性能进行比较。表2~4为7个算法分别在KNN分类器(其中K取3)、SVM分类器、RF分类器上的宏平均F1值。表中的宏平均F1值为各个算法10折交叉验证在各个分类器上获得的宏平均F1值的平均值。其中符号“±”后面的值为宏平均F1值的标准偏差。并且我们通过利用t检验方法对实验结果进行显著性测试，设置统计P值小于0.05。符号“a”表示使用t检验之后，NMIJMI在该数据集显著优于当前比较算法；符号“b”表示NMIJMI在该数据集显著劣于当前比较算法。最后一行“W/T/L”统计NMIJMI显著优于/不显著/显著劣于比较算法的数据集个数。同时使用粗体标示出每个数据集在该分类器下最高的宏平均F1值的平均值。

Table 2. F1_macro of seven algorithms on 3NN

表2. 七种算法在3NN分类器上的宏平均F1值

表2是六种对比算法和本文提出的NMIJMI算法在KNN分类器上的宏平均F1值的平均值的比较，由表中结果可以看到，NMIJMI方法在除了movement-libras数据集外的10个数据集上都取得了最高的宏平均F1值的平均值，在DLBCL数据集上取得了100%的分类准确率，在7个数据集上的分类准确率超过了80%。并且与mRMR、CMIM、MRI相比，在所有的施压数据集上都取得了显著优势，与mRMR、CMMIM、JMI、NMIFS、MRI和JMIM这六个对比算法相比，NMIJMI取得显著优势的数据集个数分别为 11、11、8、9、11、10，同时仅在movement-libras数据集上显著弱于NMIFS方法。总的来说，利用NMIJMI算法筛选得到的特征子集能够在3NN分类器上使分类的精度得到有效地提高。也就意味着NMIJMI算法可以更好地保留原始数据中的有效信息。

表3是六种对比算法和本文提出的NMIJMI算法在SVM分类器上的宏平均F1值的平均值的比较，可知NMIJMI方法在7个数据集上取得了最高的宏平均F1值的平均值，在6个数据集上的分类准确率超过了80%，分类的结果要比在KNN分类器上稍弱。同一数据集在这两种不同的分类器上得到的结果也互有优劣，如WDBC数据集、movement-libras数据集和ORL数据集在SVM分类器上可以明显的得到比KNN分类器上更好的结果。与mRMR、CMIM、JMI、NMIFS、MRI和JMIM这六个对比算法相比，NMIJMI取得显著优势的数据集个数分别为10、8、7、8、8、11，比KNN分类器稍差。此次在movement-libras数据集上与于NMIFS方法结果相近。在semeion数据集得到的结果最差，显著弱于6个对比算法中的三个，低于最高的NMIFS算法12%。在WDBC数据集上与JMI算法同时取得了最高的宏平均F1值的平均值，均为97.33%，但是标准差要比JMI的小。总体上看，NMIJMI算法在SVM分类器上表现良好，能够有效的提高分类性能。

Table 3. F1_macro of seven algorithms on SVM

表3. 七种算法在SVM分类器上的宏平均F值

Table 4. F1_macro of seven algorithms on RF

表4. 七种算法在RF分类器上的宏平均F1值

表4是七种算法在随机森林分类器上的宏平均F1值比较，可以看出，表现在随机森林分类器上表现最好的两个特征选择算法分别是NMIJMI算法和NMIFS算法。其中NMIJMI算法表现最好，在8个数据集上取得了最好的分类结果，在6个数据集上的分类精度超过了80%，NMIFS在余下的两个数据集中取得了最好的分类结果，且在6个数据集上分类精度超过80%。JMI与MRI结果相仿，JMI算法略优于MRI算法。在WDBC和movement-libras数据集上，7中算法都得到了相对较好的分类结果，在

Figure 1. Line chart of F1_macro versus number of feature for 7 algorithms

图1. 7种算法的宏平均F1值随特征数变化折线图

movement-libras数据集上，最好的结果与最差的结果间差距仅为6.3%，其中五种算法结果的差距在2%以内，在WDBC数据集上，最好的结果与最差的结果间差距不到3%。也可以得出，NMIJMI算法在随机森林分类器上也得到了良好的结果，可以认为其筛选效果优于其他6中特征选择算法。

为了能够清晰地说明不同的特征选择算法在选取不同数量的特征时的分类表现，本文给出这七中算法使用KNN分类器在这11个数据集下的分类宏平均F1值折线图，使结果更加具有说服力。如图1所示，图中的横坐标为特征的数量，纵坐标为宏平均F1值。

6. 结论

高维数据代表着数据中包含大量的信息，其中很多信息属于冗余信息和噪声信息，这些信息的存在其必然会导致数据的复杂性，加大数据分析与处理的难度。高维数据中，有效信息只是少数，如何保留有效信息，剔除无效的、冗余的信息以及无关的噪声信息，是统计学领域的热点问题，对机器学习、模式识别等领域有着重要意义。降维是处理高维数据问题的重要手段，而特征选择是一项重要的降维方式。本文针对高维复杂数据的特征选择展开了讨论与研究，重点研究内容是基于信息论的过滤式特征选择方法，目的是尽可能地保留相关特征，去除冗余的和无关的特征，达到降维的效果，从而提高学习算法的性能，同时降低计算成本，能够当作数据预处理的一个步骤，对数据分析与挖掘起到积极作用。文章依据最大相关最小冗余原则，利用互信息和条件互信息来综合度量特征的相关性和冗余性，着重对特征冗余性进行改进，并结合已选特征动态变化项，提出了一种非线性的过滤式特征选择算法。实验结果表明新的特征选择算法能够在某些数据集上取得良好的分类效果，选择出能提高分类器性能的特征子集。