1. 绪论

在特征选择过程中，有一种算法叫做mRMR（Max-Relevance and Min-Redundancy）。其原理非常简单，就是在原始特征集合中找到与最终输出结果相关性最大（Max-Relevance），但是特征彼此之间相关性最小的一组特征（Min-Redundancy）。

本文主要对彭汉川老师的提出mRMR算法进行翻译解读。

Hanchuan Peng, Fuhui Long, and Chris Ding, "Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy," 

IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 8, pp.1226-1238, 2005. [PDF]

2. 具体算法解读

2.1 Max-Dependency与Max-Relevance and Min-Redundancy算法的关系

提到互信息，特征选择的目的是找到一个具有m个特征{x_{i}}的特征子集S，这些特征与目标分类c有最大的依赖性。这种方法叫做Max-Dependency，其公示表示如下：

max D(S,c), D=I({x_{i},i=1,...,m};c)

很明显，当m=1时，就是最大化互信息I(x_{j};c) (1\leq j\leq M)。当m>1时，一个简单的增量搜索策略就是每次增加一个特征：给定m-1个特征子集S_{m-1}，第m个特征选择对于互信息I(S;c)增加最大的特征，可以得到以下公式：

I(S_m;c)=\iint p(S_m,c)log\frac{p(S_m,c)}{p(S_m)p(c)} dS_m dc

=\iint p(S_{m-1},x_m,c)log\frac{p(S_{m-1},x_m,c)}{p(S_{m-1},x_m)p(c)}dS_{m-1}dx_md_c

=\int ...\int p(x_1,...,x_m,c)log\frac{p(x_1,...,x_m,c)}{p(x_1,...,x_m)p(c)}dx_1...dx_mdc

尽管最大依赖性理论上可以计算得到，但是由于在高维空间中存在两大问题，通常很难获得概率密度函数p(x_1,...,x_m)和p(x_1,...x_m,c)：1）采样的数量通常并不充分；2）要求解多变量密度估计需要计算高维相关矩阵的逆矩阵，这是一个很难求解的问题。最大相关性的另外一个缺点是计算速度慢。这些问题在在连续特征变量时更为突出。

即使针对于离散特征，在实际应用中以上问题也不能完全避免。例如，假设每个特征有三个不同的状态，共进行N次采样。K个特征具有最多min(3^K,N)个联合状态。当联合状态迅速增加到与采样数量N达到一个数量级时，则这些特征的联合概率、互信息不能被很好的估计。因此，尽管最大依赖特征选择算法在特征少并且采样多的情况下很实用，但是在特征数量多的情况下并不适用。

2.2 Max-Relevance and Min-Redundancy

由于Max-Dependency很难实现，一个替代的选择是Max-Relevance（最大相关性）。最大相关性是搜索满足以下公式的特征：

max D(S,c), D=\frac{1}{|S|}\sum_{x_i\in S}I(x_i;c)

其中采用所有特征x_i与分类c之间的互信息的平均值来近似D(S,c)

通过Max-Relevance选择的特征可能具有冗余，这些特征之间的依赖性非常大。当两个特征互相冗余，当去掉其中一个的时候，分类结果并不会有非常大的变化。因此Min-Redundancy方式可以用来剔除掉冗余特征：

min R(S), R=\frac{1}{|S|^2}\sum_{x_i,x_i\in S}I(x_i,x_j)

将最大相关性D与最小冗余度R结合起来，我们称其为minimal-redundancy-maximum-relevancy(mRMR)。我们定义算子\Phi (D,R)用来结合D与R，考虑最简单的结合方式：

max \Phi(D,R), \Phi=D-R

在实际应用中，采用定义的算子\Phi()，采用增量搜索方法可以得到近似最优解。假设已经获得S_{m-1}特征子集，需要在剩余的{X-S_{m-1}}的特征子集内选择出第m个特征。通过最大化\Phi()来进行选择特征，即最大化：