基于互信息与判别结构互补的特征选择

张开翔，李双杰，王小刚，李雅丽，陈倩茹，王淑琴

（天津师范大学计算机与信息工程学院，天津300387）

高维数据的维数约减是机器学习领域中的一个重要问题[1-2].维数约简的方法主要包括特征选择和特征提取.特征提取方法是基于原始特征集的线性或非线性组合来创建新的特征，从而将现有的特征空间转化为新的低维特征空间；而特征选择方法是在原始特征空间中按照某种评价指标选择有助于分类的特征子集.

特征选择是数据预处理的重要方法之一[3-4].在统计和机器学习领域，相关学者对特征选择方法进行了深入研究，其基本思想是通过消除无关和冗余特征来选择特征子集，这类方法已被广泛应用于图像[5]、视频[6]和文本[7-8]处理以及基因分析[9-11]等许多方面.特征选择方法主要包括Filter 和Wrapper 2 类.Filter 方法基于样本的固有属性来选择特征，这些属性通常由某些统计标准来测量，该方法具有计算效率高、数据集维数可伸缩性强以及与分类器相互独立等优点，适合处理大数据[12-14].Wrapper 方法通常使用分类器的预测精度来评价所有可能的特征集合，从而选出预测精度最好的特征子集.由于所选特征子集经过分类算法的优化，所以，一般情况下，Wrapper 方法的效果较好.但是，Wrapper 方法可能会导致学习算法产生过拟合.

在Filter 方法中，一般使用距离、互信息、相关系数和一致性度量来计算特征与特征、特征与类别之间的相关性.一般来说，相关性得分高的特征比得分低的特征具有更强的分类能力，因此，得分高的特征会被优先选择.然而，近年来一些研究表明，多个得分高特征的组合不一定总能得到好的分类效果，将一些低得分特征加入目标子集中效果反而可能会更好[15].得分高的特征对整个分类问题的分类能力较强，但并不代表该特征对某个子问题的分类能力也较强，在多类问题中总分类能力不强的特征也可能对某些子问题的分类能力较强.所以，使用单一的评价策略来评价特征的分类能力忽略了特征对不同子问题的分类能力.针对上述问题，本文提出了一种基于互信息与判别结构互补的特征选择算法（information gain and subproblem complementary-based feature selection，IGSCFS）.该算法首先使用互信息作为特征分类能力的度量，然后根据每个特征对不同子问题的分类能力来选择特征，是一种基于分类子问题的特征选择方法.该算法不仅考虑了特征对总分类问题的分类能力，也考虑了特征对子问题的分类能力.将本文算法与已有的6 个特征选择算法在6 个公开数据集上进行实验比较，结果表明，在大多数情况下，本文算法的分类性能优于其他特征选择算法.

1 互信息

2012 年，Brown 等[16]提出了一种基于信息论的特征选择统一框架，它是一种典型的特征选择方法[16].熵是随机变量不确定性的度量，用来度量随机变量所需的平均信息量[17].离散型随机变量X=（x1，x2，…，xn）的熵记为H（X），xi表示X 可能取到的值.H（X）定义为

其中：p（x）i为X 的概率密度函数，p（x）i的取值为

2 个随机变量X 和C=（c1，c2，…，cm）的联合熵定义为

其中：p（xi，c）j为X 和C 的联合概率密度函数.在给定X 的情况下变量C 的条件熵定义为

条件熵是引入变量X 后，C 中留下的不确定性，因此它不大于这2 个变量的熵.当且仅当2 个变量X 和C 相互独立时，H（C|X）=H（C）.联合熵与条件熵的关系为

X 和C 的互信息（mutual information，MI）是2 个变量共享的信息量，定义为

MI 表示变量X 提供的降低变量C 的不确定性的信息量.2 个随机变量的MI 越大表明其相关性越强，如果2 个变量是相互独立的，则MI = 0. MI 具有对称性，所以有

由互信息的定义可以看出，MI 的值可能很大或很小，因此不同MI 值的特征的作用可能会被放大或弱化，对称不确定性（symmetric uncertainty，SU）可以补偿互信息对多值特征的偏向，并通过限制大熵输入，将SU 值限制在[0，1]范围内.随机变量X 和C 的对称不确定性定义为

2 基于互信息与判别结构互补的特征选择方法

2.1 误分类样本

对于实值特征的多类数据集D(p，q)，其中p、q 代表样本的类别，（p，q）代表所有类别属于p 和q 的样本的集合.记minq、maxq、minp、maxp为特征fj对应于（p，q）样本集合的特征值的最大值和最小值. 若第i 个样本的第j 个特征fj的特征值fji满足fji∈[minq，maxq]∩[minp，maxp]，则称第i 个样本被特征fj误分类.所有被fj误分类的样本的集合称为fj的误分类样本集，记为MSfj（p，q）.特征子集S 的误分类样本集为

2.2 判别结构向量

设O={f，f，…，f，C}n为一个有m 个特征、n1i2imiii=1个样本的数据集，其中：F = { f1，f2，…，fm}为特征集，S⊆F 为特征子集；fji为第i 个样本的第j 个特征值；C ={1，2，…，k}为类标签，Ci⊆C 为第i 个样本的类标签.k 类分类问题可以被分为k（k - 1）/2 个二分类子问题.对每一个特征，它对某个子问题的SU 值越大，则它对该子问题的分类能力就越强.由式（11）可以计算出特征fj对所有二分类子问题的分类能力，当特征的SU 值大于0 时，它对于分类是有帮助的.若每个特征的SU 值都大于0，则需要借助一个阈值来区分特征与类别之间相关性的强弱，阈值确定的具体原则在2.4 节给出.为了更好地体现每个特征对子问题的分类能力，本文算法对不同子问题设置了不同的阈值，如果特征的SU 值大于阈值，则认为该特征对于该子问题是有判别性的，基于此，为每个特征构建一个判别结构向量Vj，其维数等于二分类子问题的数量.使用函数vj（p，q）= I（SUj（p，q），θ(p，q)）来判定fj在给定阈值 θ(p，q)下对子问题（p，q）是否具有判别能力，

vj（p，q）=1（或0）表示特征fj对子问题（p，q）有（或无）判别能力.对于一个k 分类问题，特征fj在给定阈值Θ=[θ(1，2)，θ(1，3)，…，θ(1，k)，…，θ(k-1，k)]下的判别结构向量为Vj=[vj（1，2），vj（1，3），…，vj（1，k），…，vj（k-1，k）].

2.3 判别结构向量下的特征互补和特征覆盖

一般情况下，一个特征无法正确区分所有的分类问题，所以需要找到多个特征的组合来提升分类准确率.对于特征fi和fj，若vi（p，q）=0，vj（p，q）=1，即fi对子问题（p，q）无分类能力而fj对（p，q）有分类能力，则称fi和fj在子问题（p，q）上是互补的.对于2 个特征fi和fj的判别结构向量Vi和Vj，若Vi∨Vj=Vi，∨代表按位异或操作，则称特征fi覆盖了fj，记作fi≥fj.不是所有的被覆盖特征对分类都没有贡献，在进行特征选择中，若fj被fi覆盖，先判断加入fj后的特征子集的误分类样本集MSS（p，q）的数量是否减少，若减少，将加入fj，否则舍去fj.为选择性能较优的特征子集，应尽量选择互补的特征并舍去没有贡献的被覆盖特征.

2.4 阈值确定及候选特征子集

当一个特征对所有子问题都没有判别能力时，则认为它是无关特征.要将所有具有判别能力的特征选择出来，阈值的设置非常重要. 为了剔除无关特征，并保留对子问题有贡献的特征，本文采用动态方法调整阈值.首先将初始阈值设为0，以保证所有特征都有被选择的可能；然后用所有特征的SU 的平均值更新阈值，如果删除一些无关特征不影响分类效果，则继续调整阈值.具体算法流程如下.

算法1 IGSCFS 阈值确定及其候选特征子集的产生

输入：训练集D，特征集F，误分类样本集MSj（p，q），预设误分率ε

输出：阈值Θ，候选特征子集FC

令FC= ，Θ=[0，…，0]，对F 中的每一个特征fj和并令v（jp，q）=1

算法1 首先初始化阈值和判别结构向量，默认每个特征对每个子问题都有判别能力，并计算每个特征的SU 值，将所有特征SU 的平均值作为子问题的阈值θC，然后计算当前阈值下的误分率是否小于预设值ε，如果小于ε，则继续调整阈值，否则确定阈值，再根据阈值得到候选特征子集.经多次实验发现当预设误分率为0.02 时实验结果较好，因此设ε=0.02.

2.5 基于判别结构互补的特征选择

由算法1 得到候选特征子集后，根据特征的判别结构互补进行特征选择，形成目标特征子集.为了使所选特征能够区分更多的样本，定义特征的全局分类能力（global classification ability，GCA），特征fj的GCA 为

其中w（p，q）为每个子问题的权重.设子问题（p，q）包含样本数为N（p，q），数据集样本总数为n，类别数为k，则

特征的GCA 较高，表明其不仅对整个分类任务具有更强的判别能力，而且对更多的子问题具有判别能力.

在生成目标子集之前，先将候选特征按照GCA值降序排列，GCA 值高的特征将被优先选择，并寻找其互补特征.目标特征子集选择算法的具体流程如下.

算法2 基于判别结构互补的特征选择

输入：已排序的候选特征子集FC，候选特征子集中特征的判别结构向量集WC，每个特征对于每个子问题的误分类样本集MSj（p，q）

输出：目标子集Ft

令Ft= ，VC=[0，…，0]

For 每个子问题（p，q）

MS（p，q）=D(p，q)

For 每个特征fj

将状态标记置为0，表示尚未被选择，flagj=0

For 每个特征fj

If flagj=0

将特征标记为候选状态t=j

If VC∨Vj=VC

For 每个被特征fj覆盖并且flagi= 0 的特

征fi

将特征fi设置为候选状态t=i

首先将目标子集与目标子集的判别结构向量设置为空，表示当前目标子集下没有子问题被正确分类.然后初始化误分类样本集，将每个子问题的初始误分类样本集设为该子问题的样本集，并将每个特征的状态初始化为0，表示所有特征都未被选择.接下来开始选择特征，对于每个特征fj，判断将fj加入目标子集后目标子集的判别结构向量是否变化，如果变化则将该特征加入目标子集；若无变化则判断是否有特征fi被fj覆盖，若fi被覆盖，并且将fi加入目标子集后的误分类样本数小于将fj加入目标子集后的误分类样本数，则将候选特征设为fi，重复上述步骤.若将候选特征加入目标子集后的误分类样本数小于未加入时的误分类样本数，则表明该候选特征与目标子集中的某个特征是互补的，该候选特征也会被加入目标子集.

3 实验与性能分析

3.1 数据集

为验证IGSCFS 算法的正确性与有效性，在6 个公 开 数 据 集Forest、Urban、Lung cancer、Arrhythmia、Movement 和Leukemia1 上进行实验，其中：Leukemia1下载自基因表达数据库，另外5 个数据集下载自UCI机器学习库[18].所选数据集均为实值特征的多类数据集，在实验前均做归一化处理，数据集描述见表1.

表1 数据集Tab.1 Data sets

3.2 实验环境及设置

将IGSCFS 与已有的6 种特征选择算法进行比较，包括基于排序的DISR（double input symmetrical relevance）[19]、IG（information gain）[17]、MIFS（mutual information feature selection）[20]、FSSC_SD（feature selection by spectral clustering_spectral clustering based on standard deviation）[21-22]算法，以及基于生成子集的CFS（correlation-based feature selection）[23]和FCBF（fast correlation-based feature selection）[24]算法. 实验采用十重交叉验证，使用决策树（decision tree）、朴素贝叶斯（naive Bayes）和随机森林（random forest）3 种分类器进行分类，所有实验均在PyCharm 集成环境中进行.IGSCFS 为子集方法，为方便，排序方法（IG、DISR、MIFS 和FSSC_SD）选择的特征数量与IGSCFS 目标子集一致.使用分类准确率、选择特征的数量、F1-Score来评价各算法的分类性能.

3.3 实验结果及分析

表2～表4 给出了7 种算法分别使用3 种分类器在6 个数据集上的分类准确率，以及每种算法在6 个数据集上的分类准确率的平均值，表5 给出了3 种分类器准确率的平均值，其中：7 种算法在同一数据集的最高分类准确率用黑体标出，WTL（win/tie/loss）表示IGSCFS 在6 个数据集上的分类准确率中高于/等于/小于其他算法的数量.表6 给出了3 种基于生成子集的算法在6 个数据集上选择特征的数量（3 种分类器的平均值）.

由表2～表4 可见，对于每种分类器，IGSCFS 相比其他算法均在4 个数据集上得到了最高的准确率，6 个数据集的平均准确率均为最高.由表5 可见，对于各算法3 种分类器的平均准确率，IGSCFS 也在4个数据集上取得最高值，尤其在Arrhythmia 和Leukemia1 数据集上，其平均准确率比排名第2 的算法分别高10%和33%，IGSCFS 在6 个数据集上的平均准确率为75%，也是7 种算法中最高的.由表6 可见，在6 个数据集上，FCBF 都是选择特征数量最少的算法，IGSCFS 在Urban、Lung cancer 和Leukemia1数据集上选择特征的数量低于CFS，在另外3 个数据集上选择特征数量高于CFS.

表2 决策树分类器的准确率Tab.2 Accuracy rates of decision tree classifier

表3 朴素贝叶斯分类器的准确率Tab.3 Accuracy rates of naive Bayes classifier

表4 随机森林分类器的准确率Tab.4 Accuracy rates of random forest classifier

表5 3 种分类器准确率的平均值Tab.5 The average accuracy rates of 3 classifiers

表6 3 种算法选择特征的数量Tab.6 The number of selected features by 3 algorithms

由表2～表6 可以看出，在特征数较少的Forest和Lung cancer 数据集上，IGSCFS 算法的性能与其他算法相差不多，而在特征数较多的另外4 个数据集上，除少数情况外，IGSCFS 的分类准确率明显高于其他算法；在与基于排序的算法进行比较时，由于选取和IGSCFS 一样的特征数，所以当IGSCFS 选择的特征数较少时，IG 和DISR 的性能不是很好；与基于生成子集的算法进行比较可以发现，虽然FCBF 选择了较少的特征，但是其性能并不好，CFS 选择的特征数量在某些数据集上与IGSCFS 相差不多，但IGSCFS的分类性能优于CFS，尤其在高维数据集Leukemia1上，IGSCFS 仅选择了3 个特征就达到了87%的分类准确率.

在特征选择算法中，需要得到更高的分类准确率并选择尽可能少的特征，本文使用F-Score 评价特征选择算法的效果，F-Score 是准确率P 和召回率R 的调和平均，定义为

当参数α=1 时即为常见的F1-Score.图1 给出了6 个数据集上7 种算法的F1-Score 的比较结果.由图1 可见，IGSCFS 在Movement 上的F1-Score 排在第2 位，在Forest 上的F1-Score 排在第4 位，在其他4 个数据集上的F1-Score 均排在第1 位.综合来看，IGSCFS 的效果优于其他算法.

图1 IGSCFS 与其他算法在6 个数据集上的F1-Score 比较Fig.1 Comparison of F1-Score between IGSCFS and other algorithms on 6 datasets

4 结论

特征选择是机器学习和数据挖掘领域重要的维数约简方法.本文提出一种基于互信息与判别结构互补的特征选择算法IGSCFS，在6 个真实数据集上与其他6 种特征选择算法进行比较实验，结果表明IGSCFS 可以得到更好的分类准确率以及较高的F1-Score.在未来的工作中可以尝试其他度量特征分类能力的方法，以进一步提高分类准确率.