第11章：特征选择与稀疏学习 — 西瓜书学习笔记

本文是周志华《机器学习》（西瓜书）第11章 特征选择与稀疏学习（Feature Selection）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

01. 特征选择概述

为什么需要选特征？

🎯 特征选择的目的

现实数据集中往往包含成百上千个特征，但并非所有特征都对学习有用。特征可分为三类：

✅ 相关特征

对当前学习任务有用的特征，应当保留。

❌ 无关特征

与学习任务无关（不相关特征），应当删除。

⚠️ 冗余特征

包含的信息可由其他特征推出（多余），可以删除但有时有辅助作用。

🍎 通俗理解

你要根据一个人的信息预测他的收入：
✅ 相关特征：学历、工作年限、所在城市——明显有用
❌ 无关特征：鞋码、头发颜色——基本没用
⚠️ 冗余特征：月薪和年薪——一个可以由另一个算出来

特征选择就是保留相关特征，删除无关和冗余特征，让模型更高效准确。

🔑 特征选择 vs 降维

• 特征选择：从原始特征中挑选出一个子集，特征的含义不变
• 降维（如PCA）：将原始特征变换为新的低维特征（如主成分），失去原始含义
• 两者都能减少特征维度，但特征选择保留了可解释性

🎯 三大类特征选择方法

02. 子集搜索与评价

特征子集的搜索策略

🔍 子集搜索的挑战

如果有 $n$ 个特征，所有可能的特征子集有 $2^n$ 个——当 $n=100$ 时，穷举是不可能的。因此需要启发式搜索策略。

➕ 前向搜索（Forward）

从空集开始，每次添加一个最优特征，直到满足停止条件。
贪心策略，计算代价较低。

➖ 后向搜索（Backward）

从全集开始，每次删除一个贡献最小的特征，直到满足停止条件。
适合初始特征数量不太大的情况。

🔑 子集评价准则

给定特征子集 $A$，用信息增益（Information Gain）来评价：

$$\text{Gain}(A) = \text{Ent}(D) - \sum_{v} \frac{|D^v|}{|D|} \text{Ent}(D^v)$$

其中 $\text{Ent}(D)$ 是数据集 $D$ 的信息熵，$D^v$ 是按特征子集 $A$ 划分后的各分支数据集。信息增益越大，特征子集的区分能力越强。

03. 过滤式选择：Relief

用近邻样本评估特征重要性

🌊 Relief 算法思想

Relief 是一种过滤式特征选择算法，它为每个特征设计一个相关统计量来衡量其重要性，不依赖于具体的学习器。

🍎 通俗理解

对每个样本 $x_i$，找两类邻居：
👥 同类最近邻（Near Hit）：与 $x_i$ 同类且距离最近的样本
👤 异类最近邻（Near Miss）：与 $x_i$ 不同类且距离最近的样本

好的特征应该让你和同类邻居更近，和异类邻居更远。
如果某特征上 $x_i$ 和同类邻居差异小、和异类邻居差异大，这个特征很有用！

📐 相关统计量 δ 的计算

对每个特征属性 $j$，统计量 $\delta^j$ 的更新规则：

$$\delta^j = \delta^j - \frac{\text{diff}(j, x_i, x_{i,\text{nh} })}{m} + \frac{\text{diff}(j, x_i, x_{i,\text{nm} })}{m}$$

  - {% _internal_math_placeholder 305 %}：{% _internal_math_placeholder 306 %} 的同类最近邻（Near Hit）

• $x_{i,\text{nm} }$：$x_i$ 的异类最近邻（Near Miss）
• $\text{diff}(j, x_a, x_b)$：在第 $j$ 个属性上 $x_a$ 和 $x_b$ 的差值（数值属性取归一化差的平方，离散属性取0或1）
• 直觉：与同类近邻差距大 → $\delta^j$ 减小（该特征让同类分散，不好）；与异类近邻差距大 → $\delta^j$ 增大（该特征能区分异类，好！）

Relief Algorithm（二分类版本）
输入：数据集 D = {(x₁,y₁),...,(xₘ,yₘ)}，采样次数 m₀，阈值 τ
输出：各特征的相关统计量

初始化 δʲ = 0 (j = 1,...,n)
for i = 1, 2, ..., m₀ do
  从 D 中随机选取样本 xᵢ
  找 xᵢ 的同类最近邻 x_{i,nh}（Near Hit）
  找 xᵢ 的异类最近邻 x_{i,nm}（Near Miss）
  for j = 1, 2, ..., n do
    δʲ = δʲ - diff(j, xᵢ, x_{i,nh})/m₀ + diff(j, xᵢ, x_{i,nm})/m₀
  end for
end for
return 统计量 δ  // δʲ ≥ τ 的特征被选中

💡 Relief-F（多分类扩展）

Relief 只适用于二分类。Relief-F 扩展到多分类：对每个类别分别找异类最近邻，然后按各类别的比例加权求平均差值。

04. 包裹式选择：LVW

把学习器当做”黑盒”来评估特征

📦 包裹式选择思想

包裹式特征选择将最终要使用的学习器的性能作为特征子集的评价标准。即：直接把学习器训练在不同的特征子集上，看哪个子集效果最好。

🍎 通俗理解

过滤式：用固定标准（信息增益）预先筛选特征，再给学习器用——就像HR初筛简历。

  包裹式：每个特征子集都让学习器实际"上岗试用"，看效果——就像直接让候选人做实习测试。

  包裹式效果更好，但计算开销大得多！

LVW (Las Vegas Wrapper) Algorithm
输入：数据集 D，学习算法 A，控制参数 T
输出：特征子集 A*

初始化 A* = 所有特征，err* = 用 A 在 A* 上交叉验证的误差
d* = |A*|，t = 0
repeat
  t = t + 1
  随机产生特征子集 A'
  用学习算法 A 在特征子集 A' 上交叉验证，得误差 err'
  if err' < err*，或 (err' == err* 且 |A'| < d*) then
    A* = A'，err* = err'，d* = |A'|
until t > T  // 或其他停止条件
return A*

⚠️ LVW 的缺点

• 计算开销极大——每个候选特征子集都需要训练学习器
• 随机搜索不保证找到全局最优
• T 的选择影响结果

05. 嵌入式选择与正则化

L1正则化（Lasso）：最优雅的特征选择

🔗 嵌入式选择的思想

嵌入式特征选择将特征选择过程融入学习器的训练过程中，在训练时自动完成特征选择。最经典的方法是通过正则化使得模型权重稀疏。

L1 正则化（Lasso）

📐 Lasso 目标函数

在最小化损失函数的同时，加入 L1 范数惩罚项：

$$\min_w \sum_{i=1}^m \ell(f(x_i;w), y_i) + \lambda \|w\|_1$$

其中 $\|w\|_1 = \sum_j |w_j|$ 是 L1 范数，$\lambda > 0$ 是正则化参数。

✅ L1 正则化会使许多权重精确等于 0，从而自动完成特征选择！

L1 vs L2 正则化

📐 L2 正则化（Ridge）

$$\min_w \sum_{i=1}^m \ell(f(x_i;w), y_i) + \lambda \|w\|_2^2$$

L2 正则化使权重趋向于小但不为零，不产生稀疏解，不能做特征选择。

几何直觉：L1的菱形约束域有顶点，最优解倾向于落在顶点（坐标轴上），产生稀疏解；L2的圆形约束域没有顶点，解不会自然归零。

🔑 L1 vs L2 核心区别

性质	L1（Lasso）	L2（Ridge）
稀疏性	✅ 产生稀疏解（很多权重=0）	❌ 权重趋小但不为0
特征选择	✅ 隐式完成特征选择	❌ 不能直接做特征选择
几何意义	菱形约束域（顶点处解稀疏）	圆形约束域（解在弧上不稀疏）
求解	非光滑，需次梯度/坐标下降	有闭合解，易求
共线性	倾向于只保留其中一个特征	同等缩小相关特征的权重

决策树的嵌入式特征选择

💡 决策树天然地做特征选择

决策树在每次节点分裂时选择信息增益最大的特征——这个过程本身就是特征选择！特征如果从未被用于分裂，则说明对当前任务无关紧要。因此决策树是天然的嵌入式特征选择方法，也是随机森林特征重要性的来源。

06. 稀疏表示与字典学习

用少量”基”来表示数据

📚 稀疏表示的动机

如果数据样本可以用少数基向量（字典原子）的稀疏线性组合来表示，则可以去除噪声、压缩信息。这种思想在信号处理、图像压缩和计算机视觉中广泛应用。

🍎 通俗理解

一首歌的乐谱可以用钢琴、小提琴、鼓等乐器（字典原子）演奏，但通常只需要少数几种乐器（稀疏表示）就能还原大部分旋律。

字典学习就是从数据中学出这些”乐器”（原子），再用尽量少的原子组合来表示每首”歌”（数据样本）。

📐 稀疏表示问题

给定数据矩阵 $X \in \mathbb{R}^{d \times m}$，寻找字典 $B \in \mathbb{R}^{d \times k}$（$k$ 个原子，$k \gg d$）和稀疏系数矩阵 $A \in \mathbb{R}^{k \times m}$，使得：

$$\min_{B, A} \|X - BA\|_F^2 \quad \text{s.t.} \quad \forall i, \|a_i\|_0 \le s_0$$

其中 $\|a_i\|_0$ 是第 $i$ 个样本系数向量的非零元素个数（L0范数），$s_0$ 是稀疏度约束。

由于 L0 约束组合优化问题 NP-hard，实践中常用 L1 范数松弛代替 L0：

$$\min_{B, A} \|X - BA\|_F^2 + \lambda \|A\|_1$$

📚 字典学习（K-SVD）

字典学习（Dictionary Learning）目标：同时学习字典 $B$ 和稀疏表示 $A$，交替优化：

字典学习（交替优化框架）
输入：数据矩阵 X，字典大小 k，稀疏度 s₀
初始化：字典 B（如用随机样本初始化）
repeat
// 第一步：固定字典 B，求稀疏系数 A
for i = 1, ..., m do
    求解稀疏编码问题：min ‖xᵢ - Baᵢ‖² + λ‖aᵢ‖₁
  end for
// 第二步：固定稀疏系数 A，更新字典 B
for k = 1, ..., K do
    找使用了第k个原子的样本集合 Ωₖ
    用 SVD 同时更新第k个字典原子和对应系数
  end for
until 收敛
return 字典 B，稀疏系数 A

💡 字典学习 vs PCA

• PCA：字典是正交的（主成分正交），每个样本用 $d'$ 个成分（非稀疏）
• 字典学习：字典是过完备的（$k > d$，冗余），但每个样本用很少的原子（稀疏）
• 字典学习更灵活，适合信号的稀疏分析

07. 压缩感知

用少量观测恢复稀疏信号

🎵 压缩感知的革命性思想

传统信号处理（奈奎斯特采样定理）：采样率至少是信号最高频率的2倍才能无损恢复。压缩感知打破了这一限制：如果信号是稀疏的（在某个字典下的系数大多为0），则可以用远少于奈奎斯特的随机观测来恢复原始信号！

🍎 通俗理解

一幅 1000×1000 像素的图片，传统需要存储100万个像素值。但如果这幅图片在某个变换域（如傅里叶、小波）下只有1000个非零系数，那么理论上只需要存储远少于100万的随机观测，也能恢复完整图片！这就是压缩感知的奇妙之处——信号的稀疏性等于信息量其实很少，可以大幅压缩。

📐 压缩感知模型

原始信号 $x \in \mathbb{R}^n$ 在字典 $\Psi$ 下有稀疏表示 $s$（$x = \Psi s$，$\|s\|_0 \ll n$）。

用观测矩阵 $\Phi \in \mathbb{R}^{m \times n}$（$m \ll n$）获得观测 $y = \Phi x = \Phi \Psi s = A s$。

从 $y = As$（严重欠定方程组）中恢复 $s$：

$$\min_s \|s\|_0 \quad \text{s.t.} \quad As = y$$

用 L1 松弛（基追踪，Basis Pursuit）：

$$\min_s \|s\|_1 \quad \text{s.t.} \quad As = y$$

在**限制等距性（RIP）**条件下，此 L1 问题能精确恢复稀疏信号 $s$。

🔑 限制等距性（RIP 条件）

矩阵 $A$ 满足 RIP 条件，即对所有 $s$-稀疏向量 $s$，存在 $\delta_s \in (0, 1)$：

$$（1-\delta_s）\|s\|_2^2 \le \|As\|_2^2 \le （1+\delta_s）\|s\|_2^2$$

RIP 条件保证了 $A$ 不会把不同的稀疏信号压缩到同一个观测，从而保证可恢复性。随机高斯矩阵以极高概率满足 RIP 条件。

✅ 压缩感知的条件

• 信号在某个字典下是稀疏的
• 观测矩阵满足 RIP 条件（如随机矩阵）
• 观测数 $m \ge O(s \log(n/s))$ 即可恢复（$s$ 为稀疏度）

• MRI 医学成像（减少扫描时间）
• 图像压缩与恢复
• 无线通信中的信道估计
• 雷达信号处理

08. 对比总结

方法	类型	核心思想	特点
Relief	过滤式	同类邻居近、异类邻居远	快速，不依赖学习器，适合二/多分类
LVW	包裹式	用学习器评估特征子集性能	效果好，计算开销大
L1/Lasso	嵌入式	L1惩罚使权重稀疏化	在训练时自动选择特征，高效
决策树	嵌入式	分裂时自动选信息增益最大的特征	天然特征选择，可解释性强
字典学习	无监督稀疏	学习过完备字典+稀疏系数	信号稀疏表示，过完备字典
压缩感知	信号恢复	稀疏信号用少量随机观测恢复	打破奈奎斯特限制，需满足RIP

🔑 考试高频考点

• 📌 三类特征选择方法的区别（过滤式/包裹式/嵌入式）和各自代表算法
• 📌 Relief 的相关统计量计算公式：同类近邻差小好，异类近邻差大好
• 📌 L1 vs L2 正则化：为什么 L1 产生稀疏解（几何直觉！）
• 📌 字典学习的目标函数和交替优化框架
• 📌 压缩感知的基本原理：稀疏性 + RIP 条件 → 少量观测可恢复