基于信息论的特征选择算法综述

特征选择的目标是从样本数据集的原始特征F中寻找一个子集S，使得它包含尽可能多的类区分信息，即包含更多与类别C有关的知识，同时又使得子集内部的冗余程度尽量小。定义信息度量函数J(f)，其目的是在原始特征集F内选择子集S，保证其与类别C之间相关性程度最大，同时又保证子集S内部的冗余性最小。

为了方便起见，下面先对几个常用的符号做一简单约定：符号F和S分别表示未选的和已选的特征子集，C表示分类类别，和分别表示候选和已选的特征。

不失一般性候选特征f的信息度量函数J(f)可表示为如下形式：

其中函数为候选特征f、类别C和已选子集S之间的信息量。它主要用来表示f加入S后，S与C之间的相关程度，即f能给S带来关于C的信息量。通常情况下，为互信息或条件互信息的形式。α是调控系数，它主要用于调节f所带来信息量的程度，δ是惩罚因子，用于惩罚候选特征f给已选子集S带来的冗余程度。他经常以f、C和单个已选特征s之间的互信息的形式出现。

由上式可知，倘若候选特征f能给S带来更多信息（即上式中第一项越大），并且S产生较小的冗余性（即上市中第二项越大），那么他就是一个较好的特征（上式中J(f)越大），该特征将被优先选择。

BIF(Best Individual Feature)[3]是一种最简单也是最直观的特征选择算法，他的评估函数J(f)就是互信息本身，即J(f)=I(C;f)。BIF选择算法的思想很简单，他首先对所有候选特征f计算其评价函数J(f)，并根据函数值按降序顺序排序，然后选择前k个特征组成选择子集S。BIF算法的优点是效率高，因此他适合于高维数据情况，如文本分类等。他也经常用于混合选择方法的预处理步骤中，以预先过滤不重要的特征。BIF的缺点也很明显，比如他没有考虑特征之间的相互关联和冗余性等。

由于BIF算法未考虑特征的冗余性，如果S已经包含了特征f的信息量，所以f相对于S来说是无用的。另外，多个单独最优的特征组合在一起时，其性能也未必是最优的。Battiti R.于1994提出基于互信息的特征选择算法MIFS[4]。MIFS算法使用互信息度量候选特征与类别之间的相关性，以及与已选特征集合直接按的冗余性，以贪心策略选择与类别相关性强且已选特征冗余度低的特征集合。

其中β 为惩罚因子，当β 取不同值时，MIFS算法性能波动较大，当β∈[0.5, 1] 时，算法性能较优。

与MIFS算法类似，mRMR算法[5]也采用互信息作为候选特征f与类别C之间相关性以及与已选特征集合S之间冗余性的度量标准，并且针对MIFS算法惩罚因子β 难以确定的问题，mRMR算法采用候选特征与已选特征的平均互信息作为冗余度的估值，即惩罚因子为1/|S| 。mRMR算法于2005年由Peng等人提出，评价函数为：

通过于单个已知特征s的相关性衡量f的重要性程度。

Kwak和Choi指出MIFS选择算法中评价函数J(f)的惩罚因子并不能准确地表达冗余程度的增长量。为此，他们在MIFS-U算法[6]中使用不确定性系数CU(f,s)描述f与s之间的相关冗余程度，其中CU(f,s)=I(f,s)/H(s)。另外，他们还将已选择特征s与类别C之间的相关程度也纳入惩罚因子中。总之，MIFS-U算法的特征度量标准是：

与mRMR的做法类似，Huang等将公式中的β 替换为1/|S|，并结合遗传算法生成候选子集，然后利用支持向量机获取较好的分类效果。

与MIFS算法类似，MIFS-U算法中参数β 的取值将影响算法性能，而β 具体取什么值是件很棘手的事情。为了解决这个问题，Novovicova等提出MIFS-U的一种改进算法，称做mMIFS-U。它并不是利用f与s相关程度值和作为f与S的冗余程度，而实将f与S中单个已选特征相关程度最大的s作为他们之间的冗余程度。简言之，mMIFS-U就是采用max函数取代求和操作，即：

FCBF是Yu和Liu提出的一种基于相关性的特征选择算法。它借助Markov blanket技术判定特征间的相似性，从而达到快速消除冗余特征的目的。在FCBF算法中，特征之间冗余性和特征与类别之间的相关程度都是通过对称不确定性(Symmetrical Uncertainty, SU)度量的。对称不确定性是互信息的一种归一化表示形式，用于客服互信息固有的缺点，即互信息标准倾向于哪些具有多值的特征。给定类别C，特征f与C的对称不确定性为：

这个函数就是FCBF算法的评价标准J(f)，只不过在确定候选特征f是否冗余时，还需判断SU(s,f)