最大相关与独立分类信息最大化特征选择算法

周传华，李 鸣，吴幸运

(1.安徽工业大学 管理科学与工程学院，安徽 马鞍山 243002；2.中国科学技术大学 计算机科学与技术学院，安徽 合肥 230026)

0 引 言

随着大数据技术的发展，高维数据已遍布模式识别、自然语言处理和生物信息学等各个领域。数据中包含大量的无关与冗余特征，极大地降低了分类性能，造成“维数灾难”[1]。同时，高维数据增加了模型训练周期，造成计算开销大、处理效率低。数据降维能有效应对“维数灾难”，并缩短模型训练周期。

数据降维分为特征抽取和特征选择。特征抽取将高维空间的样本通过映射或转化到低维空间，如PCA[2]、LDA[3]等，存在计算效率低、转化后的特征可解释性差等问题[4]。特征选择是从原始特征中去除无关和冗余特征。按照评价准则，特征选择可分为filter、wrapper和embedded三种模式。wrapper和embedded都是结合分类器来评价特征子集。其中wrapper方法利用分类精度评价特征子集，计算开销大且易造成模型过拟合，embedded方法在构造分类器的过程中选择特征，其计算效率高于wrapper方法，但无法避免造成模型过拟合。filter模式以距离、信息、依赖性和一致性等指标作为评价依据，独立于分类器的学习过程，计算效率高，且易于理解。

基于互信息的评价方法能检测特征与类别、特征之间的线性和非线性依赖关系，在filter方法中广泛运用[5]。按照特征评价准则的不同，其可分为最小化特征冗余和最大化新分类信息两类[3]。最小化特征冗余偏向于选择与已选特征子集冗余度较少的特征，代表性算法有MIFS[6]、MIFS-ND[7]、mRMR[8]、CMIFS[9]等。最大化新分类信息的方法偏向选择能贡献较多的已选特征子集未能提供的分类信息的特征，代表性算法如JMI[10]、JMIM、CMIM[11]、IF[12]、DISR[13]等。在特征选择过程中，备选特征的冗余性较低，不一定包含较高的新分类信息，反之亦然。特征选择所选的特征应具有较高的类分辨能力和较低的特征之间的冗余性，需要综合考虑备选特征的冗余性和提供的新分类信息，Wang等人[14]在2017年提出独立分类信息(ICI)这一新概念，并提出了基于最大相关性最大独立性(MRI)的特征选择算法，其运用ICI综合衡量特征冗余与新分类信息，并运用互信息衡量特征相关性，选择出较优的特征子集。Gao等人[15]提出最小冗余最大新分类信息的特征选择算法(MR-MNCI)，结合mRMR和CMIM的特征评价准则，平衡特征冗余和新分类信息的重要性，取得了较好的效果。Gao等人[16]还通过分析特征相关性的组成，提出了一种考虑特征相关性组合的特征选择算法(CFR)，运用条件互信息来衡量新分类信息，并利用交互信息评价特征之间的冗余性，选择出具有高类辨别能力和低冗余的特征。

可见，同时考虑特征冗余与新分类信息的特征选择算法可获得具有高类辨别能力和低冗余的特征。但该类算法运用累加求和的方法衡量新分类信息和特征冗余，过高地评价了特征的重要性。因此提出了最大相关与独立分类信息最大化(MRICIM)特征选择算法，该算法以互信息衡量特征与类别之间的相关性，运用独立分类信息综合衡量特征提供的新分类信息和冗余性，结合最大最小准则构建非线性特征评价准则，来删除无关特征和冗余特征，从而获得最佳特征子集。

1 相关理论

1.1 特征选择过程

特征选择的具体执行过程如图1所示，由产生过程、评价函数、停止准则和验证过程组成。

图1 特征选择过程

上图描绘了候选子集的产生过程，其实质就是特征子集的搜索过程，通过相关评估函数对搜索结果进行评估，特征子集经过相关评估函数后再判断是否满足停止准则，若满足则进一步验证子集，若不满足返回重新开始。

对原始数据集进行搜索的过程就是产生候选特征的过程，主要策略包括：全局搜索、启发式搜索和随机搜索。其中，全局搜索策略就是从所有可能的特征组合当中选出最优特征子集。这种策略适用于特征个数较少的情况，特征维度较高时，会付出很大代价。常见的全局搜索策略包括分支限界法、广度优先搜索等。启发式搜索主要包括序列前向选择搜索、序列后向选择搜索以及双向搜索等。

评价函数的改进是特征选择的研究热点，在特征选择过程中起着重要作用，将评价准则大致分为五种：距离度量、信息度量、依赖性度量、一致性度量和分类器错误率度量。

停止准则能决定何时结束算法，停止搜索，利用合适的停止准则可以防止特征的搜索陷入无限循环，而影响停止准则的主要包括搜索算法和评价准则，其中，常见的评价准则一般包括设置特征子集的数目阈值、设置搜索循环的次数阈值、设置评价函数的目标值和搜索的特征子集已经达到最优。

为了对特征子集结果进行有效性验证，通常进行特征选择验证，具体过程就是将特征选择之后的新数据集在分类器上进行训练和测试，并与其他特征选择算法在相关测试集上进行预测对比或将预测的结果与原始数据集进行比较，得到算法的分类性能等。

1.2 互信息理论

信息熵[5]是由香农提出的用来衡量随机变量的平均不确定程度或信息量，信息熵越大表示随机变量的不确定性越大，反之越小。对于随机变量X={x1,x2,…,xm}和Y={y1,y2,…,yn}，p(xi)和p(yj)分别表示随机变量X=xi、Y=yj时的概率，信息熵H(X)定义如下：

(1)

条件熵表示的是在随机变量Y已知的条件下，随机变量X的不确定性，其定义如下：

条件熵可衡量两随机变量之间的相互依赖程度，H(X|Y)=H(X)表示两随机变量相互独立。互信息表示的是两个随机变量相互依赖的程度，即对于随机变量X和Y，其中一个随机变量已知的情况下，另一个随机变量不确定性的变化情况，随机变量X和Y之间的互信息I(X;Y)定义为：

I(X;Y)=H(X)-H(X|Y)=

(3)

I(X;Y)越大表示随机变量X和Y之间的依赖或相关性越大，反之，依赖或相关性越小。条件互信息指的是在随机变量Z={z1,z2,…,zk}已知的情况下，随机变量X和Y的互信息。条件互信息I(X;Y|Z)定义为：

I(X;Y|Z)=H(X|Z)+H(Y|Z)-H(X,Y|Z)=

(4)

交互信息是衡量三个随机变量之间共有的不确定性或信息量，X、Y和Z三个随机变量之间的交互信息I(X;Y;Z)定义为：

(5)

I(X;Y;Z)越大，随机变量X、Y和Z三者间的相关性越强，反之越弱。当I(X;Y;Z)=0时，表示随机变量X、Y和Z三者相互独立。

2 最大相关与独立分类信息最大化特征选择算法

假设特征全集为F，已选特征子集为S，Xk∈F-S，即Xk为备选特征，Xj∈S，类别为C。Xk与特征子集S的独立分类信息[14]可表示为：

ICI(C;Xk,S)=I(Xk;C|S)+I(S;C|Xk)

(6)

其中，I(Xk;C|S)是独立于特征子集S的新分类信息，称为新分类信息，I(Xk;C|S)越大说明Xk能够提供更多的辨别类别的信息，I(S;C|Xk)表示再加入Xk后，特征子集S所保留的分类信息，称为剩余分类信息。I(S;C|Xk)=I(S;C)-I(S;C;Xk)，I(S;C|Xk)越大，则I(S;C;Xk)越小，I(S;C;Xk)为Xk与特征子集S关于类别C的冗余信息。在一轮特征选择中，I(S;C)是一个定值，则I(S;C;Xk)≅I(Xk;C|S)-I(S;C;Xk)。因此，ICI平等权衡了新分类信息和特征冗余。Xj和Xk的独立分类信息表示为：

ICI(C;Xk,Xj)=I(Xk;C|Xj)+I(Xj;C|Xk)

(7)

引理：对于Xk、Xi∈F-S，若Xk与S中所有Xj的最小独立分类信息都小于Xk与S中所有Xj的独立分类信息，则ICI(C;Xk,S)>ICI(C;Xi,S)。

ICI计算时涉及到单个特征与特征子集之间的独立分类信息的度量，而该信息量求解的难度大，可操作性低。利用两两特征独立分类信息累加求和的方式计算备选特征与特征子集之间的独立分类信息，计算方法为：

(8)

为了解决累加求和方式对独立分类信息的衡量过高，运用上述最小新分类信息和最大最小准则，提出最大相关与独立分类信息最大化(MRICIM)特征选择算法，其评价准则模型为：

(9)

根据最小独立分类信息定义，xk最小独立分类信息f(Xk)可表示为：

(10)

MRICIM算法步骤如下所示：

输入：特征集合F，特征选择个数K，类别Y

输出：特征子集S

1.初始化S=∅,F={X1,X2,…,Xm},k=0;

2.计算I(Xi;Y),Xi∈F

3.S={max(I(Xi;Y)},F=F-max(I(Xi,Y),k=k+1

4.whilek

5.ForXiinF-S:

6.计算Xi与类别Y的互信息I(Xi;Y)

7.ForXjinS:

8.计算当前Xi的新分类信息I(Xi;C|Xj)、Xj的剩余分类信息I(Xj;C|Xi)

10.计算X*=argmax(I(Xi;Y)+F(Xi))

11.S=S+X*

12.F=F-S

13.k=k+1

3 实验及结果分析

为了验证该算法的有效性，将与mRMR、JMIM、MRI以及CFR四个具有代表性算法进行比较。统一实验平台配置为：操作系统为win10，处理器为Intel(R)core(TM)i5-4200U @1.6 GHz，内存为8 G，实验环境为Pycharm，语言为python。

3.1 实验数据

为了能全面地比较特征选择算法的性能，选择6个基准评测数据集，这些数据集来源于UCI和文献[15-16]，其中包含文本数据(BASEHOCK、RELATHE)、生物领域数据(TOX_171)、图像识别领域数据(COIL20、ORL)等，所选数据集包含离散和连续型数据，详细描述见表1。

表1 实验数据集

3.2 实验设置

对数据集进行预处理，使其满足分类任务。将名义变量转化为数值变量，对连续变量按照等宽法进行离散化，设置间隔数为5。在未划分的数据集上运行特征选择算法，选择前25个特征进行比较实验，选择KNN(n=3)和NB两个分类器，采用10折交叉验证的方式来检验分类效果。

利用平均分类准确率、最高分类准确率以及F-measure综合评价分类性能。其中运用配对样本的双尾T检验来验证MRICIM算法与其他算法平均准确率是否有显著性差异，置信度设置为95%。具体实验流程如图2所示。所选算法皆以贪婪策略搜索特征子集，将算法选取的前25个特征分为25组特征子集，每一组较前一组多一个特征(从第二组开始)，在6个数据集上运用NB和KNN分别评估25个特征子集的分类性能。

图2 实验流程

3.3 实验结果和分析

表2和表3分别表示在KNN和NB作为分类器时，各算法在25组特征子集上的平均分类准确率及标准差。“+/=/-”分别表示MRICIM算法在平均准确率上大于/等于/小于其他算法(T检验)，“W/T/L”分别表示MRICIM算法在平均准确率上大于/等于/小于其他算法的次数(粗体表示当前数据集上该算法平均分类准确率最高)。就平均分类准确率而言，MRICIM取得了不错的成绩，在所有数据集上平均准确率未低于其他算法，仅在BASEHOCK数据集上与其他算法平均准确率基本相同。综合考虑KNN和NB分类器的平均分类准确率，在BASEHOCK数据集上MRICIM相对于JMIM最大提升了0.7个百分点，与其他算法表现无差异。在COIL20数据集上MRICIM相对于JMIM最大提升5.4个百分点，相对于mRMR最大提升3.4个百分点，相对于CFR和MRI最大提升1个左右百分点。在Isolet数据集上，MRICIM相对于mRMR最大提升了9.7个百分点，相对于CFR最大提升了2个百分点，相对JMIM最大提升了8.1个百分点，相对于MRI最大提升了3.8个百分点。在ORL数据集上，MRICIM表现很突出，相对于mRMR最大提升了1.5个百分点，相对于CFR最大提升12.5个百分点，相对于JMIM最大提升9.5个百分点，相对于MRI最大提升8.8个百分点。在RELATHE，相对于mRMR最大提升2.3个百分点，相对于CFR最大提升3.4个百分点，相对于JMIM最大提升1.7个百分点，相对于MRI最大提升3.6个百分点。在TOX_171数据集上，相对于mRMR最大提升5.3个百分点，相对于CFR最大提升4.8个百分点，相对于JMIM最大提升4.3个百分点，相对于MRI最大提升4.7个百分点。

表2 各特征选择算法在KNN上的平均分类准确率(mean±std.)

表3 各特征选择算法在NB上的平均分类准确率(mean±std.)

图3给出了各算法在不同数据集上KNN和NB分类器的平均分类准确率的变化情况。横坐标为特征数量，纵坐标为对应特征数量的情况下，两分类器的平均分类准确率。在BASEHOCK数据集上，在特征达到一定数量后与JMIM、CFR和MRI取得差不多的效果。在其他数据集上，MRICIM在特征达到一定数量后，MRICIM在两分类器上的平均分类准确率上基本会一直高于其他方法，且保持上升趋势。这是由于随着特征数量的增加，mRMR、CFR和MRI这类用累加求和的方式评价特征会高估特征的重要性，而JMIM虽是非线性的评价准则，但其侧重于考虑新分类信息，对冗余信息关注不够。MRICIM能够很好地衡量特征相关、特征冗余和新分类信息。需要注意的是在特征选择的前期，MRICIM选择的特征可能会较其他算法表现不佳，这是运用最大最小准则无法避免的，这是由于前期用这种非线性评价准则可能会对特征的重要性评价不足，但最终的特征子集具有优秀的分类能力，能够选择出较好的特征子集。

图3 各算法在NB和KNN上的平均准确率变化情况

表4和图4分别表示NB作为分类器时，各算法在数据集上的最大分类准确度和F1-measure,显然这两个方面MRICIM都获得了很好的效果，基本上优于其他算法。

表4 各特征算法在NB上最大分类准确率(特征数量)

图4 各算法在NB上的F1-meature

4 结束语

MRICIM在特征选择过程中综合考虑了特征与类别的相关性、特征之间的冗余性，以及特征包含的新分类信息，结合最大最小准则对特征的重要性进行非线性评价。实验结果表明，MRICIM能够选择出较高类辨别能力和较低冗余性的特征。但MRICIM在特征选择的前期表现不是很出众，基于此，未来将结合其他方法构建一个动态的评价准则，在提升分类效果的同时，减少特征子集的规模。