📚 课程目录第4章 MRM算法原理

4. MRM算法原理：最大相关性、最小冗余性与目标函数数学推导

MRM（Max-Relevance and Min-Redundancy）是一种基于互信息的特征筛选框架，其核心思想是：所选特征子集既要与目标变量高度相关（最大相关性），又要彼此之间尽可能独立（最小冗余性）。本章从信息论基础出发，逐步推导MRM的数学原理与常见变体。

互信息（Mutual Information, MI）衡量两个随机变量之间的依赖程度。对于离散变量 \(X\) 和 \(Y\)，其互信息定义为：

\[ I(X;Y) = \sum_{x \in X} \sum_{y \in Y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \]

互信息具有以下关键性质：

实践提示：在连续特征场景下，通常使用核密度估计（KDE）或k近邻方法（如KSG估计器）计算互信息。scikit-learn的 mutual_info_classif 默认采用k近邻法。

最大相关性准则要求所选特征子集 \(S\) 中的每个特征 \(f_i\) 与目标变量 \(c\) 的互信息之和最大化。其数学表达式为：

\[ \max D(S, c), \quad D = \frac{1}{|S|} \sum_{f_i \in S} I(f_i; c) \]

其中 \(|S|\) 为子集大小。该准则单独使用时，容易选出高度相似的特征（例如两个强相关但彼此冗余的特征），导致模型过拟合或泛化能力下降。

最小冗余性准则要求特征子集 \(S\) 内部特征之间的互信息之和最小化，即特征之间尽可能独立：

\[ \min R(S), \quad R = \frac{1}{|S|^2} \sum_{f_i, f_j \in S} I(f_i; f_j) \]

该准则单独使用会倾向于选择彼此独立的特征，但可能忽略与目标变量的相关性，导致筛选出的特征对预测任务贡献不足。

MRM将最大相关性与最小冗余性组合为统一的目标函数。根据组合方式的不同，衍生出以下三种经典变体：

变体名称	目标函数	组合方式	适用场景
MID (Mutual Information Difference)	\(\max \left[ D - R \right]\)	差值组合	特征数量较少、冗余度较高时效果较好
MIQ (Mutual Information Quotient)	\(\max \left[ D / R \right]\)	比值组合	特征数量较多、相关性差异较大时更稳定
MIM (Mutual Information Maximization)	\(\max \left[ D \right]\)	仅最大化相关性	仅考虑相关性，忽略冗余（退化为最大相关性准则）

  数学推导要点：MID和MIQ的优化目标均为NP难问题，实际求解时采用增量搜索策略：每次从候选特征中选择使目标函数最优的特征加入子集，直到达到预设特征数。

MRM的增量前向选择算法步骤如下：

初始化：空特征子集 \(S = \emptyset\)，候选特征集 \(F\)。
第一步：从 \(F\) 中选择与目标变量 \(c\) 互信息最大的特征 \(f^*\)，加入 \(S\)。
迭代：对于 \(k = 2\) 到 \(K\)（预设特征数），执行：
- 对每个候选特征 \(f_i \in F \setminus S\)，计算目标函数值（MID或MIQ）。
- 选择使目标函数最大的特征 \(f^*\)，加入 \(S\)。
终止：当 \(|S| = K\) 或候选特征集为空时停止。

注意：增量搜索得到的解是近似最优而非全局最优。对于高维数据（如基因表达数据），增量搜索的计算复杂度为 \(O(K \cdot |F| \cdot N)\)，其中 \(N\) 为样本数，通常可接受。

给定已选子集 \(S_{k-1}\)，候选特征 \(f_i\)，MID目标函数为：

\[ J_{\text{MID}}(f_i) = I(f_i; c) - \frac{1}{|S_{k-1}|} \sum_{f_j \in S_{k-1}} I(f_i; f_j) \]

推导过程：

当前子集 \(S = S_{k-1} \cup \{f_i\}\)，则：
- 相关性项：\(D = \frac{1}{k} \left[ \sum_{f_j \in S_{k-1}} I(f_j; c) + I(f_i; c) \right]\)
- 冗余性项：\(R = \frac{1}{k^2} \left[ \sum_{f_j, f_l \in S_{k-1}} I(f_j; f_l) + 2 \sum_{f_j \in S_{k-1}} I(f_i; f_j) \right]\)
由于 \(S_{k-1}\) 已固定，最大化 \(D - R\) 等价于最大化： \[ \frac{1}{k} I(f_i; c) - \frac{2}{k^2} \sum_{f_j \in S_{k-1}} I(f_i; f_j) \]
忽略常数因子 \(\frac{1}{k}\) 和 \(\frac{2}{k^2}\)，得到简化后的增量目标函数： \[ J_{\text{MID}}(f_i) = I(f_i; c) - \frac{1}{|S_{k-1}|} \sum_{f_j \in S_{k-1}} I(f_i; f_j) \]

MIQ的推导类似，增量目标函数为：

\[ J_{\text{MIQ}}(f_i) = \frac{I(f_i; c)}{\frac{1}{|S_{k-1}|} \sum_{f_j \in S_{k-1}} I(f_i; f_j)} \]

MIM（Mutual Information Maximization）是MRM的特例，仅保留最大相关性准则：

\[ J_{\text{MIM}}(f_i) = I(f_i; c) \]

MIM的优缺点：

  经验法则：在生物信息学场景中（如基因表达数据），特征间往往存在高度共线性，此时强烈推荐使用MIQ。MIQ在冗余惩罚与相关性保留之间取得了更好的平衡，尤其适用于高维小样本数据。