Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance, and

Feature Extraction or Selection Using Dependence Analysis with Mutual Information: A Methodology Incorporating Maximal Dependency, Maximal Relevance, and Minimal Redundancy

基于互信息的特征选择：最大依赖、最大相关、最小冗余准则

摘要

特征选择在分类系统中扮演着至关重要的角色。该研究依据互信息理论中的'最大统计依赖准则'进行了系统的特征筛选工作。引入最小冗余最大相关准则是mRMR方法，并将其与多种复杂特征选择技术相结合，构建了一个分两阶段实施的特征提取方案[算法]。将该方法与其他常用分类器如贝叶斯分类器、支持向量机和支持向量回归模型进行比较分析，并通过四个典型数据集上的实验验证其有效性。

特征冗余：特征之间相关性比较大，比如长、宽、面积，面积就是一个冗余特征。

介绍

最优的特征表示意味着在分类任务中最小化错误率。

Mutual Information（互信息）是一种用于衡量两个随机变量之间相互依赖程度的数量。它通常用来评估其中一个变量化提供了关于另一个变量化多少有用的信息，并反映了已知其中一个变量化的情况下减少另一个变量化不确定性的能力。

对于两个随机变量x,y，他们的互信息就是他们的概率密度函数。

在特征选择领域已有诸多研究发现，在第一阶段中使用mRMR方法等价于采用最大相关性策略未必能带来理想的效果

问题一：理论分析表明，在第一阶段中使用mRMR方法等价于采用最大相关性策略; 但该方法在效率方面仍有提升空间

问题二：进一步探讨了将mRMR与其他经典的特征选择方法相结合以构建双阶段筛选体系; 实验结果表明该方案可显著提高筛选效果

问题三：实验研究表明所提出的方法具有较高的效率

最大依赖，最大相关和最小冗余之间的关系

最大依赖（maximum dependency），即寻找一个特征集S，在目标类别c上具有最大的依赖关系（该类别c与特征子集之间的互信息值最大）

当m等于1时较为直观易懂；而对于m大于1的情况，则建议采用逐步引入更多变量的方法，在这一过程中所选择的变量应当能够使信息量I(S;c)达到最大值。

但存在的问题是多元密度函数的计算复杂度较高；在实际应用中往往需要处理大量高维矩阵运算，在数据规模较大的情况下容易导致计算效率下降，并且这一问题在连续变量特征方面表现得更为不足。因此，在样本数量充足而特征维度较低的情况下可能展现出较好的效果；然而其局限性主要体现在对高精度分类任务而言效果欠佳

该准测所选特征间可能存在较高程度的相关性；若两个特征高度相关，则删除其中一个并不会显著影响它们在分类任务中的表现；为了便于后续分析，在剔除这些特征时我们采用了引入最小冗余度的方法。

mRMR就是将最大相关最小冗余结合起来，定义Φ（D,R）

在实践中采用增量查找方法来识别（6）所定义的近最优特征。假设已获取m-1个特征，则需识别第m个特征（7）。

最优一阶增量搜索（证明了该准则与最大依赖一样）
证明略><

特征选择算法

问题在于如何确定特征的数量m？为此提出一种分两阶段的特征选择方法，在第一个阶段中使用基于mRMR的增量搜索方法来获得候选特征集合，在第二个阶段中采用其他成熟的优化方法来筛选出更优的特征子集。

选择候选特征集

评估大量特征的交叉验证分类误差，并确定相对稳定的较小误差范围作为集合Ω；候选集中的特征数量n是通过Ω获得的。整个过程分为三步：
1.使用mRMR逐步选择法选取一系列满足包含关系S1⊂ S2 ⊂…⊂ Sn-1⊂ Sn；
2.通过对这些特征序列进行分析来确定k值范围即为集合Ω；确保对应的交叉验证误差error ek保持较小（具有低均值和低方差）；
3.在集合Ω中找到具有最小分类误差e；这个最小误差对应的k值即为候选子集大小。

这不还就是枚举的感觉，，

进一步选择特征子集

为了更好地论证mRMR方法的有效性, 可以选择一组较为理想的候选特征, 并通过封装器wrappers来寻找更为简洁的特征子集. 每个wrapper都是一个基于分类器的特征选择工具, 通常情况下, 在控制计算复杂度的同时, 它们能够实现较高的分类精度. 这种方法与mRMR方法不同, 它们无法直接优化分类误差.

mRMR或最大相关性也被认为是一种过滤器，在机器学习领域常被视为一种有效的特征筛选方法。与Wrapper类算法相比其计算复杂度显著低于Wrapper方法同时筛选出的特征还具有良好的泛化能力并且通常适用于大多数分类模型。在实际应用中个人认为不同机器学习算法选择特征时会有一定的类别偏好而基于统计的方法则避免了这一问题。

在第一阶段中采用mRMR特征选择方法获取最小候选属性集合S_{k}, 从而使得第二阶段基于该候选集合的选择过程具有较低计算复杂度。
本文所采用的两种分类器分别为后向剔除法与前向添加法。

1. 后向剔除法的具体实现过程如下：
   每次从候选特征集中移除一个特征并计算分类错误率, 比较移除后的错误率e_{k-1}与原错误率e_{k}之间的差异, 对于包含k个特征的情况, 显然存在k种可能的移除方式, 即分别对应于每一个可能被剔除掉的单个属性. 对于每一种可能的情况都需要重新计算对应的e_{k-1}值. 如果发现移除某一个特定属性之后错误率有所降低, 则该属性应被保留; 否则应予以剔除. 当所有可选属性均无法通过上述方式有效减少错误率时, 则认为当前所有候选属性均对分类任务具有积极作用, 程序终止。
2. 前向添加法的基本思路是逐步添加特征以寻求最简子集：
   首先随机选取一个初始属性并计算其对应的错误率e_{1}. 接着依次增加一个新属性并评估当前子集下的错误率e_{k}. 重复上述过程直到新增任何一个新的属性都会导致错误率上升为止. 需要注意的是, 在某些特殊情况下可能会出现多个新属性均不改变当前错误率的情况（即既不降低也不提高），此时算法仍会继续尝试添加更多的属性直至满足终止条件.

更具有特征性的特征空间(RM-characteristic)

对于两个均具备n个特征的特征集合Sₙ₁、Sₙ₂以及分类器Γ，在Sₙ₁上的分类误差较小的情况下，则称Sₙ₁较具有特征性地先于Sₙ₂；这一概念还可扩展至Sₙ₁与Sₙ₂的子集中。假设有特征选择方法F，在Sₙ₁上满足：S₁₁⊂S₂₁⊂…⊂Sk₁⊂…⊂S_{n-1}¹⊂Sₙ¹，在Sₙ₂上满足：S₁²⊂S₂²⊂…⊂Sk²⊂…⊂S_{n-1}²⊂Sₙ²。若对于任意k∈Ω区间内（其中k满足下界值klower与上界值kupper之间的关系：1≤klower<kupper≤n），Sk₁上的分类误差持续小于Sk₂，则在区间Ω=[klower, kupper]（k的取值范围为[ klower, kupper ]且满足 ）上所述述述述述述述述述述述述述述），称在该区间内比较而言，
Sₙ₁较具有比
Sₙ₂更高的递归
特征性（即RM-
characteristic特性）。为了确定哪一个特征集合更为优秀，
不能仅依据特定大小子集上的分类误差来进行判断。
最佳的方式是在合理的Ω区间范围内考察哪一个特征集合具备RM-
characteristic特性。
在极端实例中，
令Ω=[1,n]，
假设有两个特征选择方法F₁与F₂，
若通过F₁获得的特征子集较具有相对于F₂划分出的特征子集更高的RM-
特征性，
则称采用F₁的方法优于采用F₂的方法。

接下来展开了基于RM-characteristic的mRMR和最大相关方法的对比。同时在序列和非序列特征上进行。
1.直接对比了mRMR序列特征集和最大相关序列特征集。用两种方法获得S1⊂S2⊂…⊂Sk⊂…⊂Sn-1⊂Sn，并分别计算分类误差，如果说对于大部分k∈[1,n]，mRMR划分的子集上的误差都小于最大相关的，我们就说对于序列特征mRMR的方法优于最大相关方法。
2.对于非序列特征，在第二阶段用不同的wrappers验证了，mRMR产生的候选子集是否优于最大相关方法。具体略
3.对于wrappers，考虑了很多不同分类器，用mRMR和最大相关选择了大小相同的候选特征集，然后用wrappers进行进一步的特征选择，并对比其分类误差。如果所有的结果都表明mRMR的特征选择方法是RM-characteristic的，我们就说mRMR是一种更好的特征选择方法。
4.对于两个特征集Sn1,Sn2，如果Sn1比Sn2具有RM-characteristic，则这这两个数据集上对比分类误差是令人信服的。
显然，对于拥有相同特征数目额特征空间，wrappers在RM-characteristic上的效率会更高。所以说，通过提高特征的特征性减少预先选择的特征，这是有利wrapper运行代价更低啊，

特征选择的作用是什么？它是否有助于降低实际工程中的计算复杂度或是时间复杂度？

在实际情况下难以获取全部k值的ek符号。为此我们定义一个参数ρ（介于0到1之间），当ρ=0.9时意味着约90%的k值参与计算。研究表明该方法对其RM-characteristic的影响并未受影响。

实施问题

两个问题
1.连续和离散数据的互信息计算
2.介绍实验用的多种分类器

互信息计算

易于计算如式（1），对于连续变量的互信息计算则较为复杂。一种方法是将连续数据进行离散化处理以简化运算；然而目前尚未找到有效的解决方案。另一种方法则是采用密度估计技术来估算I(x;y)。此前已开展相关研究工作。

其中δ(.)被定义为Parzen窗函数，在统计学中用于估计概率密度函数p(x)；根据理论分析，在适当选择δ(.)与窗口宽度h的情况下，在样本数量N趋于无穷大时，则密度估计值p^(x)能够收敛至真实密度函数p(x)；通常情况下，默认使用高斯核作为δ(.)

z = x - x^{(i)} ，其中d代表x的空间维度，并且\Sigma代表z的协方差矩阵。当d = 1时（如方程17所示），该表达式对应于边际密度估计；而当d = 2时（如方程17所示），它用于建模两个变量x和y之间的联合密度函数p(x, y)。为了确保估计的有效性，在d \geq 2的情况下（如方程17所示），通常会采用\Sigma矩阵的对角线元素来进行近似。

分类器

朴素贝叶斯NB
支持向量机SVM
主成分分析LDA

实验

在两个离散和两个连续数据集上进行实验。

数据集

如下图

mRMR和最大依赖对比（选择特征的cost对比）

从算法复杂度和特征分类准确性两个维度对两者进行比较分析。在离散数据集中的模型具有较高的准确率优势，在连续数据集中，则分别计算两种模型选择50个特征所需的时间成本。通过实验结果表明，在时间成本方面显著优于最大依赖法的mRMR方法。

特征分类准确性对比

研究表明mRMR在性能上要优于最大依赖方法

mRMR和最大相关选择候选特征的对比

两种方法在复杂度上相差不大；其中mRMR略微高出一点；暂且忽略不计；本文重点考察两者在特征分类准确性方面的差异。

简洁特征选择的对比

阐述了基于最大相关性的候选特征选择与mRMR方法的选择过程之后，在候选特征求解过程中将候选特征的数量设定为50个。通过后向消元法与前向选择法相结合的方式筛选最优子集，在此前提下若采用基于mRMR的方法所选中的候选特性能更好地体现RM-characteristic特性，则系统的分类精度预期会更加优异。

图5所示的结果表明，在mRMR算法所定义的特征候选集合中筛选出了一组精确对应的特征子集。值得注意的是，在引入第18个特征后，wrappers算法停止进一步选择新的特征原因是因为新增的特征开始显著提升分类误差水平。

下图是最终结果（应该是简洁特征集选出来之后，各个分类器的分类误差）

总结

研究表明，在多种分类器上测试后发现mRMR方法所选出的候选特征均展现出良好的泛化能力，并且这一方法在处理大规模数据时表现尤为突出

（6）不是mRMR的唯一形式，也可以修改为系数形式等，

思考：该方法主要应用于处理大规模数据集中的特征选择问题。
对于小规模的数据集而言，
是否存在通过调节mRMR方法来实现特征选择的可能性？
或者采用其他不同的特征选择方法来解决这一问题？

互信息的估计在高维空间可信度更高