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()来进行选择特征,即最大化: mRMR(Max-Relevance and Min-Redundancy)算法实现:http://www.youerw.com/fanwen/lunwen_61938.html