基于最大信息系数的关联性特征选择算法:MICCFS

罗幼喜, 谢昆明, 胡超竹, 李翰芳

(湖北工业大学理学院, 武汉 430068)

在日益增长的高维复杂数据分析中,数据降维是去除数据中多余信息、使数据“干净化”的有效手段,降维主要有特征选择和特征抽取两类,特征抽取是在原始特征上再创造新的特征,特征选择是选择原始特征的子集,去除的是冗余特征和不相关特征[1].对目标变量有用的特征往往只有少数几个,特征选择能减少计算时间并且增加模型的可解释性[2].特征选择可分为三种类型:过滤式,包裹式和嵌入式[3].包裹式通常以最终使用学习器的性能作为特征子集的评价准则[4],通常表现较好但计算量较大,如SVMRFE[5](support vector machine recursive feature elimination);嵌入式是在算法学习过程中就选择出最优特征,计算量较大,如LASSO(least absolute shrinkage and selection operator)算法[6];而过滤式是独立于分类器的,通常计算量较低,速度较快[7],先选择特征后再进行训练,尤其在高维数据中具有可操作性,过滤式特征选择常见有互信息最大化(mutual information maximization,MIM)[8]、Relief F[9]、卡方法(Chi-Square)[10]等.

基于关联性特征选择算法(correlation-based feature selection,CFS)[7]是基于一种评价准则进行搜索最优子集的算法,由于其同时考虑到特征与目标变量的相关性以及特征与特征之间的冗余性,所以被广泛应用于各领域,如李浩文等[11]将算法应用于短期风电功率预测的关键影响特征选择问题中,邱纯等[12]则利用其筛选大规模胶质瘤相关基因.CFS算法思想是一个好的特征子集应该与输出类别高度相关而与其他特征不相关[7,13],评价准则是基于选出的特征与类之间平均相关性最大化、特征之间平均相关性最小化的思想来评估特征子集的价值,以此进行搜索特征子集,对于回归和分类任务,度量两个变量之间的关系分别是线性相关系数和对称不确定度量SU.而线性相关系数只能度量两个变量间存在的线性关系,无法检测其他非线性关系;SU是一种归一化的互信息,SU的分母过大[14],同时互信息在计算连续变量相关性时不易计算,通常需要离散化,而互信息的计算结果受不同离散化的方式的影响较大[15].如何改进CFS中相关性度量方法,使其既能度量变量间的线性关系和任意非线性关系,且同时适用于离散型变量和连续型变量是该算法研究中的一项重要课题.Reshef等[16]在2011年提出的最大信息系数(maximal information coefficient,MIC)为解决该问题提供了一条重要途径. MIC是一种度量属性间相关性的方法,不仅能度量变量间的线性关系,也能度量其非线性关系以及非函数关系,适用离散和连续数据.Reshef等还证明了MIC具有较强泛化性和公平性,适用于变量间任意形式的函数,对于不同形式函数的相同水平噪声能得到同样的结果.该度量方法一经提出就引起众多学者关注,被广泛应用于医学[17]、电力[18]、环境[19]、军事[20]等领域.

鉴于MIC良好的相关性度量特性,本文拟针对CFS算法的不足,提出一种基于MIC的CFS特征选择算法:MICCFS.将回归和分类中度量变量间相关性方式改进成MIC,依据评价准则来进行特征搜索选择,并通过实际数据比较和分析算法的有效性.

1 基于关联性的特征选择算法

基于关联性的特征选择算法(CFS)[7]是一种同时考虑特征间冗余性和特征与响应变量间的关联性的算法,是基于特征搜索空间的算法.其基本思想是一个好的特征子集应该与响应变量高度相关而与其它特征不相关.首先,定义评估函数如下:

(1)

利用式(1)作为评价函数,CFS采用早停准则搜索特征空间[13],最终选择的特征子集Fk为

(2)

2 基于MIC改进的CFS算法:MICCFS

2.1 最大信息系数

最大信息系数(MIC)是基于互信息来计算变量间相关程度,具体计算过程如下.

设有随机变量X和Y,对于由其样本{(xi,yi),i=1,2,…,N}组成的有序对集合D,在二维平面上分别沿x轴方向分割成a段,沿y轴方向分割成b段,得到a×b的网格G,令D|G表示集合D中的点落在网格G上的概率分布,并记I(D|G,a,b)为该分隔情形下对应的X和Y互信息估计值.对于不同的划分网格G,可以估计出不同的互信息I(D|G,a,b)值,记I*(D,a,b)为所有不同划分G下的互信息最大值,即:

(3)

则最大信息系数计算公式为

(4)

其中,N为样本数,B(N)是样本的函数,表示网格总的小单元数a×b满足小于B(N),根据文献[16],一般取B(N)=N0.6.Reshef等[16]证明了MIC值范围为[0,1],当两变量间的MIC值越大,相关性越强,反之MIC值越小,则两变量相关性越小.且MIC具有很强的泛化能力,适用变量间任意形式的函数,同时还具有公平性,即对不同形式的函数在相同水平噪声下都能得到同样的结果.

鉴于MIC以上优良的性质,本文利用MIC来度量特征与特征间的关系以及特征与类别间的关系,从而既能度量离散变量间相关性,也能度量连续变量间相关性,以此对CFS算法中的变量间关系度量方式进行改进.

2.2 MICCFS算法

(5)

依据式(5)进行搜索特征子集,算法MICCFS简单描述如下.

输入:D={F1,F2,…,Fp,C}//含有p个特征,一个响应变量的数据集

输出:Fsub//最终得到的特征子集

步骤一:初始化最终特征子集Fsub为空集.

步骤二:计算每个特征与类别间的最大信息系数MIC(Fi,C)(i=1,2,…,p),每两个特征之间的最大信息系数MIC(Fi,Fj)(i,j=1,2,…,p).

步骤三:重复以下步骤,直至遍历完所有特征或者满足CFS早停准则时停止搜索,

步骤四:返回最终特征子集Fsub.

此算法由两部分组成:

①计算特征与类别间以及特征与特征间的最大信息系数;

2.3 时间复杂度比较

3 实验及结果分析

3.1 实验数据集

本文实验中回归和分类数据集均来自UCI机器学习数据仓库,如表1、表2所示,其中回归数据集中Friedman.1.data是R语言tgp包中的数据.实验软件为Python 3.7、R 3.5.2语言编程,系统运行环境为:Intel(R) Core(TM) i5-3337U 处理器、1.8 GHz CPU, 8GB RAM, Win10 操作系统.

表1 回归数据集描述

表2 分类数据集描述

数据预处理:在计算变量间的MIC时,将字符型变量进行编码转化为数值型,再进行计算,同时,对于字符型变量,进行One-Hot编码处理,数据进入模型前进行标准化处理;连续型变量的缺失值用均值代替,离散型变量缺失值用众数代替;将预处理后的数据作为初始实验数据集.

3.2 分类器参数设置

实验采用最常见的四种分类器,支持向量机(SVM)[21]、决策树(DT)[22]、朴素贝叶斯(NB)[23]、k近邻(KNN)[24],这些都是比较常用并且广泛应用于各种领域的分类器,超参数设置如下.

k近邻分类器在计算样本距离时,为了消除数据尺度不同对结果的影响,计算前需要对数据进行标准化处理,同时为简便起见,本文中k统一取3.

决策树采用CART决策树,采用Python中第三方库sklearn,回归时的函数参数设置:criterion=′mse′, splitter=′best′;分类时函数参数:criterion=′gini′, splitter=′best′,max＿depth=5, min＿samples＿split=20,其余参数均采用默认设置.

高斯朴素贝叶斯分类器,后验分布参数

不需要调节,即假设特征的条件概率分布满足高斯分布.

3.3 评价比较准则

对于回归任务,比较最终选取的特征数量p和均方根误差

其中,N是样本数,ypred是预测值,ytrue是真实值,并记SVM、3NN、DT三种模型下得到的最小均方根误差为mRMSE.由于希望得到较少的特征数量和较小的均方根误差,因此对于特征数量和均方误差给出一个综合指标REI:

其中,fRS是回归任务选择出的特征数量,fRA是数据集原有特征数量,REI越小越好.

类似的,对于分类任务,对比选择出的特征数量p和分类准确度Acc,记SVM、3NN、DT、NB四种模型下得到的最大分类精度为mAcc.由于希望得到较少的特征数量和较大的分类准确度,对于衡量模型复杂度和精度给出一个综合指标CEI:

其中,fCS是分类任务选择出的特征数量,CEI越大越好.所有分类数据的精度采用10次5折交叉验证.

综上,对于回归问题,重点比较选取的特征数量、RMSE、mRMSE和REI;而对于分类问题,比较特征数量,分类精度,最大分类精度mAcc和CEI.

3.4 结果与讨论

3.4.1 回归结果 得到的回归结果均方根误差和选择出的特征数量如表3所示,表中字体加粗表示MICCFS的RMSE小于CFS的RMSE.

表3 回归结果下的特征数量和均方根误差

从表3可看到,首先对于选择的特征,MICCFS算法在CH、CCS、diab、Fried这4个数据集上选择出的特征数量小于或等于CFS算法,其余的数据集上CFS算法选择出来的特征数量均小于MICCFS选择出的特征数量,在11个数据集上,CFS最大的特征减少度为92.30%(数据集Bos),MICCFS最大的特征减少度为76.92%(数据集Bos),CFS特征数量上比MICCFS少,两者都对原始数据中特征进行了筛选,简化了数据结构;然后对于预测均方根误差,MICCFS在11个数据集上在3种分类器上分别有7、8、6个数据集的RMSE比CFS小,最大的差距为10.18(CH数据集,3NN分类器),其余数据集上,CFS比MICCFS的RMSE小,最大差距仅为2.15(CCS数据集,3NN分类器),在均方根误差上MICCFS比CFS较优;取不同的数据集在三种模型下的最小均方根误差,如图1所示．

图1 不同数据集在三种情况下的mRMSE

从图1看到,总体11个数据集,MICCFS算法在7个数据集上的mRMSE比CFS算法小,但原始特征下的得到的分别有6个数据集的mRMSE比CFS算法得到的mRMSE小,原始特征下有8个数据集的mRMSE比MICCFS算法得到的mRMSE小,其中最大差距为20.08(FF数据集),最小的差距仅为0.02(Fried数据集).

综合考虑特征数量和最小均方根误差,本文运用综合指标REI(见定义2)来进行比较,结果见图2,图中no＿REI、CFS＿REI、MICCFS＿REI分别表示原特征、CFS算法、MICCFS算法下的REI值.

从图2可看到,11个数据集中,MICCFS算法有6个数据集比原特征下的REI小,同时MICCFS算法有6个数据集上的REI比CFS算法下的REI小.总体来说,MICCFS算法较CFS更优.

3.4.2 分类结果 分类结果如表4、表5所示,表中粗字体表示MICCFS的分类精度比CFS高.

表4 SVM和NN下的分类精度结果

表5 DT和NB下的分类精度结果

从表4、表5可看到,在4种分类器、11个数据集下,MICCFS算法得到的特征数量均小于或等于CFS算法得到的特征数量,其中MICCFS的最小特征减少度为61.76%(Derm数据集),CFS的最小特征减少度为38.46%(Wine数据集);两者最大的特征减少度均有99%(HV数据集),特征数量上MICCFS比CFS少,两者均筛选出了特征子集,去除了冗余信息.同时11个数据集中MICCFS在4种分类器下分别有3、4、7、3个数据集的分类精度比CFS高,最大差距为7.38个百分点(Con数据集,NB分类器),其余数据集上CFS得到的分类精度高于MICCFS得到的分类精度,最大差距为30.38个百分点.同样,取出不同分类器下的最大分类精度如图3所示．

从图3可看到,MICCFS算法在4个数据集上的mAcc比CFS大,最大差距为11.2个百分点(Aaw数据集),其余数据集上的CFS算法得到的mAcc比MICCFS大,最大差距为6.09个百分点(LM数据集).同时原始特征下得到的6个数据集的mAcc比CFS算法得到的mAcc大,原始特征下有7个数据集的mAcc比MICCFS算法得到的mAcc大,最大差距为7.10个百分点(LM数据集),最小差距为0.11个百分点(Derm数据集).与回归中类似,综合考虑特征数量和最大分类精度,运用综合指标CEI(见定义4)来进行比较,结果见图4,图中no＿CEI、CFS＿CEI、MICCFS＿CEI分别表示原特征、CFS算法、MICCFS算法下的CEI值.

从图4可看到,10个数据集中,MICCFS算法下所有数据集的CEI均比CFS算法下的CEI大,总体来看,可得到MICCFS较CFS更优的结论.

此外,本文还将MICCFS算法与其他常用特征选择算法SVMRFE、Lasso、MIM、Relief F、Chi-Square,使用表2中数据进行了对比,其中 SVMRFE 属于封装式的常用的方法;Lasso 是嵌入式的,是统计学中变量选择被使用较多且经典的变量压缩算法,其余的是过滤式的,也是常用且流行被使用在各个领域的方法.CFS和MICCFS算法均是基于特征子集的算法,将MICCFS和基于特征子集的算法Lasso(超参数alpha=0.3,其余参数采用Python默认设置)比较,比较选择的特征数量、mAcc和CEI;以及基于排序式的特征选择算法Relief F、 SVMRFE、Chi-Square、MIM,选择和MICCFS相同数量的特征时来比较mAcc,与前面计算方式类似,在4种分类器下,得到这些算法的结果如表6,表中加粗字体表示MICCFS的mAcc比其他算法大或者CEI比Lasso算法高.

表6 六种不同方法下的特征、mAcc、CEI结果

从表6可看到,MICCFS和5种基于权重排序的特征选择算法中,10个数据集中有5个数据集MICCFS算法的mAcc均优于其他算法,其他算法分别只有1～2个数据集是最优的,同时,MICCFS和Lasso对比,10个数据集中9个数据集的MICCFS选择出的特征小于或等于Lasso选择出的特征; 6个数据集的最大分类精度mAcc比Lasso高,最大差距为16.39个百分点(数据集Derm),其余4个数据集Lasso的mAcc比MICCFS高,最大差距仅为5.21个百分点(数据集LM);同时,对于CEI指标,有9个数据集的CEI均比Lasso高,综合数据来看,MICCFS较其他常用特征选择算法有优势.

4 结论

本文基于最大信息系数(MIC)对关联性的特征选择算法(CFS)进行了改进,提出MICCFS算法,它运用MIC衡量变量间的复杂关系,统一回归时和分类时变量关系衡量方式,再依据评估函数来选择特征子集,是一种更有效的特征选择方法.对于CFS算法中的回归任务和分类任务,首先,将回归任务中衡量变量间关系的线性相关系数替换为MIC系数,使其能衡量的关系更为复杂,3种模型在UCI中11个回归数据集上进行验证,比较其特征选择数量、mRMSE和综合指标REI,综合比较,结果表明MICCFS较CFS有优势;然后将分类任务中衡量变量间的关系的对称不确定性度量替换为MIC系数,4种模型在UCI中10个分类数据集上进行验证,比较其特征数量、mAcc和CEI,综合比较,MICCFS较CFS更优.最后将MICCFS和其它常用特征选择算法进行比较,结果表明MICCFS也具有一定优势.