第11章 特征选择与稀疏学习

🎯 学习目标

• 理解特征选择的意义和方法分类
• 掌握过滤式、包裹式和嵌入式特征选择
• 理解L1正则化如何实现稀疏性
• 了解稀疏表示和字典学习

11.1 子集搜索与评价

🎯 特征选择的必要性

在实际应用中，数据往往包含大量特征，但并非所有特征都对学习任务有用。特征选择（Feature Selection） 的目标是从原始特征集中选择一个有效的特征子集。

• 降低维度：减少特征数量，缓解维度灾难
• 提高性能：去除无关和冗余特征，提高模型泛化能力
• 增强可解释性：保留重要特征，模型更易理解
• 降低计算开销：减少训练和预测时间

子集搜索策略

• 前向搜索（Forward Selection）：从空集开始，逐步加入特征
• 后向搜索（Backward Elimination）：从全集开始，逐步删除特征
• 双向搜索：结合前向和后向搜索
• 全局搜索：枚举所有可能的子集（计算量大，通常不可行）

子集评价准则

如何评价一个特征子集的好坏？

• 信息增益：特征能够提供多少关于类别的信息
• 基尼指数：衡量数据纯度，常用于决策树
• 相关系数：特征与标签的线性相关程度
• 模型性能：在验证集上的准确率、AUC等指标

💡 特征子集搜索是NP难问题

$d$ 个特征有 $2^d$ 个可能的子集，当 $d$ 很大时无法穷举。实际中常用启发式搜索策略，虽然不保证最优，但能在合理时间内找到较好的解。

11.2 过滤式选择

过滤式方法 先对数据集进行特征选择，然后再训练学习器。特征选择过程与后续学习器无关，通常基于统计量或信息论指标。

Relief算法

Relief是一种著名的过滤式特征选择方法，为每个特征设计一个"相关统计量"，评估特征区分同类和异类样本的能力。

1. 随机选择样本 $x$
2. 找到 $x$ 的同类最近邻（near-hit）和异类最近邻（near-miss）
3. 如果特征在 $x$ 和near-hit上差异小、在 $x$ 和near-miss上差异大，则该特征重要
4. 更新特征权重统计量
5. 重复1-4多次，选择权重最大的k个特征

Relief-F（多分类扩展）：

$${\delta }^i={\delta }^i-\sum _{x_j\in \text{near-hit}}diff(x^i,x^j{)}^2+\sum _{c\ne y}\sum _{x_k\in \text{near-miss}(c)}diff(x^i,x^k{)}^2$$

其中 ${\delta }^i$ 是第 $i$ 个特征的统计量，$diff$ 是特征差异度量。

• 优点：计算效率高、与学习器无关通用性强、易于理解和实现
• 缺点：忽略特征间的相互作用、独立评价每个特征、可能选出冗余特征

11.3 包裹式选择

包裹式方法 直接把学习器的性能作为特征子集的评价准则。将特征选择和学习器训练结合在一起。

LVW（Las Vegas Wrapper）

LVW是一种典型的包裹式特征选择方法，采用随机策略进行子集搜索。

1. 随机产生一个特征子集
2. 在该子集上训练学习器，评估性能
3. 如果性能优于当前最优子集，则更新
4. 重复1-3直到达到停止条件（如最大迭代次数或时间限制）
5. 返回验证集上性能最好的特征子集

其他包裹式方法

• 递归特征消除（RFE）：反复训练模型，每次删除权重最小的特征

• 遗传算法：用进化策略搜索特征子集空间

• 序列前向/后向选择：基于学习器性能逐步添加/删除特征

• 优点：直接针对学习器优化、考虑特征间的交互、通常性能更好

• 缺点：计算开销大（需多次训练）、容易过拟合到验证集、与学习器强相关

11.4 嵌入式选择与L1正则化

嵌入式方法 将特征选择过程与学习器训练过程融为一体，在学习器训练过程中自动进行特征选择。

基于L1正则化的特征选择

L1正则化会产生 稀疏解，即许多特征的权重变为0，从而实现特征选择。

$$min\sum _{i}L(y_i,f(x_i))+\lambda \parallel w{\parallel }_1$$

L1范数：$\parallel w{\parallel }_1=\sum _j|w_j|$

LASSO回归

LASSO（Least Absolute Shrinkage and Selection Operator）是L1正则化线性回归：

$$min\parallel y-Xw{\parallel }^2+\lambda \parallel w{\parallel }_1$$

当 $\lambda$ 足够大时，部分 $w_j$ 会被压缩到0，相应特征被自动剔除。

💡 为什么L1产生稀疏性？

L1正则项在原点不可导，梯度下降容易将权重压缩到0。而L2正则项（$\parallel w{\parallel }^2$）是平滑的，只会让权重变小但不会变为0。

其他嵌入式方法

• 决策树的特征选择：在树生长过程中自动选择最优特征

• 神经网络的剪枝：训练后移除不重要的连接或神经元

• Elastic Net：结合L1和L2正则化（$\alpha \parallel w{\parallel }_1+\beta \parallel w{\parallel }^2$）

• 优点：计算效率高于包裹式、考虑特征间的交互、与学习器结合紧密

• 缺点：依赖特定学习器、超参数 $\lambda$ 需要调节、可能不如包裹式准确

LASSO正则化路径演示

可视化L1正则化如何随着 $\lambda$ 增大逐步将特征系数压缩至0，实现自动特征选择。

正则化参数 λ: 0.50

无正则化 (λ=0)强正则化 (λ=1)

当前系数值

非零系数: 0 / 10

特征 1

0.00

特征 2

0.00

特征 3

0.00

特征 4

0.00

特征 5

0.00

特征 6

0.00

特征 7

0.00

特征 8

0.00

特征 9

0.00

特征 10

0.00

系数大小（特征重要性）

特征 10.00

特征 20.00

特征 30.00

特征 40.00

特征 50.00

特征 60.00

特征 70.00

特征 80.00

特征 90.00

特征 100.00

LASSO稀疏性原理：

目标函数：min ||y - Xw||² + λ||w||₁

为什么产生稀疏性？

• L1范数在原点不可导
• 梯度下降容易将权重压缩到0
• λ越大，零系数越多

应用场景

• 高维数据特征选择
• 去除不相关特征
• 提高模型可解释性

11.5 稀疏表示与字典学习

稀疏表示

稀疏表示（Sparse Representation） 试图用少量"基向量"的线性组合来表示样本，即表示系数中大部分为0。

$$min\parallel \alpha {\parallel }_0\text{subject to}x=D\alpha$$

其中 $D$ 是字典矩阵，$\alpha$ 是稀疏系数，$\parallel \alpha {\parallel }_0$ 表示 $\alpha$ 中非零元素个数。

L0范数最小化是NP难问题，实践中通常用L1范数作为凸松弛：

$$min\parallel \alpha {\parallel }_1\text{subject to}x=D\alpha \text{或}min\parallel x-D\alpha {\parallel }^2+\lambda \parallel \alpha {\parallel }_1$$

字典学习

字典学习（Dictionary Learning） 旨在为数据集学习一个合适的字典 $D$，使得所有样本都能用该字典稀疏表示。

字典学习目标：

$$min\parallel X-DA{\parallel }_F^2+\lambda \sum _i\parallel {\alpha }_i{\parallel }_1$$

其中 $X=[x_1,\dots ,x_m]$，$A=[{\alpha }_1,\dots ,{\alpha }_m]$。需要同时学习字典 $D$ 和稀疏系数 $A$，这是一个非凸优化问题。

💡 K-SVD算法

K-SVD是经典的字典学习算法，采用交替优化策略：

1. 稀疏编码：固定字典 $D$，求解稀疏系数 $A$（用OMP、LASSO等方法）
2. 字典更新：固定 $A$，逐个更新字典中的原子（用SVD）
3. 重复1-2直到收敛

💡 应用场景

• 图像去噪：学习干净图像的字典，稀疏表示去除噪声
• 图像超分辨率：学习低分辨率-高分辨率图像对的字典
• 人脸识别：用同类样本的字典稀疏表示测试样本
• 压缩感知：从少量测量值重构稀疏信号

11.6 压缩感知

压缩感知（Compressed Sensing） 是一种信号采样理论，指出：如果信号在某个域是稀疏的，那么可以用远少于奈奎斯特采样定理要求的测量次数来恢复信号。

🎯 核心思想

• 稀疏性：信号 $x$ 在某个变换域（如小波、傅里叶）中是稀疏的
• 测量：通过测量矩阵 $\mathrm{\Phi }$ 进行随机投影，得到 $y=\mathrm{\Phi }x$（维度 $m<n$）
• 重构：从欠定方程 $y=\mathrm{\Phi }x$ 恢复稀疏信号 $x$

重构问题：

$$min\parallel x{\parallel }_0\text{subject to}y=\mathrm{\Phi }x$$

实践中用L1松弛：$min\parallel x{\parallel }_1\text{subject to}y=\mathrm{\Phi }x$

RIP条件

限制等距性质（Restricted Isometry Property, RIP）保证了测量矩阵 $\mathrm{\Phi }$ 能够保持稀疏信号的结构。满足RIP的测量矩阵（如高斯随机矩阵）可以以高概率准确重构稀疏信号。

💡 应用领域

• 医学成像：MRI快速成像，减少扫描时间
• 单像素相机：用少量随机测量重构图像
• 无线通信：频谱感知、信道估计
• 雷达成像：合成孔径雷达（SAR）成像

压缩感知打破了传统采样理论的限制，在信号本身稀疏或可稀疏表示时，能以少量测量实现高质量重构，具有重要的理论和应用价值。

📝 本章小结

总结

• ✅ 特征选择可分为过滤式、包裹式和嵌入式三大类
• ✅ 过滤式方法效率高但忽略特征交互，包裹式方法准确但计算开销大
• ✅ L1正则化（LASSO）通过产生稀疏解实现自动特征选择
• ✅ 稀疏表示和字典学习用少量基向量表示数据，广泛应用于图像处理
• ✅ 压缩感知利用信号的稀疏性，从少量测量中重构原始信号