机器学习笔记：稀疏学习与特征学习

内容来源：西瓜书（周志华《机器学习》）

核心观点

机器学习最重要的并不是模型，而是**数据**。模型上 XGBoost 能够干碎大部分花里胡哨的操作，经济学更是线性回归绝对优势，基本上都是具体问题具体分析再针对性地有所操作。

关键在于**信息**，在于**数据**。机器学习与数据科学的强绑定也来自于此。

这主要还是因为机器学习的特性：维数爆炸。要想把握现实中各个事物的关系，其实要考虑很多的变量，将其打包成一个 $x$ 之后，就很自然的发现这个 $x$ 是一个维数很高的向量。但归根到底，一个事物往往没有想象中的复杂，变量之所以多，是因为有噪声干扰。

有两种操作可以减小影响： 1. 降维：直接合成看似复杂的数据 2. 特征选取：去掉不重要的部分

一、降维

降维实际上就是减少数据的自由度，因为在空间中分布的高维数据很多维度其实是相关的（例如身高与体重、身高与父母身高等）。虽然说形式上写成多个维度而且很多时候是非线性关系，但是确实又是相关的，有一些更本质的内容蕴含在其中。

直接把数据中不重要的维度丢掉就行了吧，但是如何找一个很好的映射，以至于保持其分布不会发生改变。我们希望经过这样一个变换，数据的分布不发生改变——高维空间中隔得远的点也还是那么远，因为原始的高维空间数据分布就代表它们有很大的差距。

甚至我们有时不但要降维，反而还要把原始的数据给投影到高维潜空间之中，目的就是把数据的信息分离出来。当然，我们此时需要做到的，就是平衡信息和计算效率。

1.1 MDS 算法（多维缩放）

算法步骤：

计算距离矩阵 $D$
对 $D$ 进行变换，得到内积矩阵 $B$，$B$ 需满足列和、行和、$\text{tr}(B)$ 均为零：

\[ b_{ij} = -\frac{1}{2}\left(\text{dist}_{ij}^2 - \text{dist}_{i\cdot}^2 - \text{dist}_{\cdot j}^2 + \text{dist}_{\cdot\cdot}^2\right) 其中： - $\text{dist}_{i\cdot}^2 = \frac{1}{m}\sum_{j=1}^m \text{dist}_{ij}^2$ - $\text{dist}_{\cdot j}^2 = \frac{1}{m}\sum_{i=1}^m \text{dist}_{ij}^2$ - $\text{dist}_{\cdot\cdot}^2 = \frac{1}{m^2}\|D\|_F^2$ 3. 对 $B$ 进行特征值分解：$B = V^T \Sigma V$ 4. 选取最大的前 $k$ 个特征值构成：$Z = \Sigma^{1/2} \tilde{V}$ $Z$ 即为所求的降维结果。 ### 1.2 PCA 主成分分析 PCA 是降维界"最高的山"。核心思想：找一个超平面，使得所有样本点尽可能在这个超平面上，而且点在超平面上的投影分得特别开。这与 SVM 不同：SVM 想要把样本点"隔"开来，而 PCA 是想要把向量放在这个平面上，而且这些点分得尽可能开。 **算法推导：** 对样本点进行归一化，得到样本 $\{x_n\}$。假设经过坐标变换得到新坐标系 $\{\omega_i\}$，共 $d$ 个向量。投影坐标：$x_i = \sum_{j=1}^d z_{ji} \omega_j$ 取前 $d'$ 个分量：$x_i' = \sum_{j=1}^{d'} z_{ji} \omega_j$ 目标：让 $\sum_{i=1}^n \|x_i' - x_i\|_2^2$ 尽可能小设 $W = [w_1, w_2, \ldots, w_{d'}]$，$z = [z_1, z_2, \ldots, z_{d'}]^T$ ```math \|Wz - x\|_2^2 = z^T W^T W z - 2x_i^T W z + \|x_i\|^2 \]

去掉常数，即最小化：$\sum_{i=1}^n z_i^T z_i - 2\sum_{i=1}^n x_i^T W z_i$

由 $z_i = W x_i$，原式化为：

\[ \min -\text{tr}(W^T X X^T W) 其中 $X = [x_1, x_2, \ldots, x_n]$，且 $W^T W = I$（正交约束）。 **结论**：选取 $X X^T$ 的最大特征值，$w$ 依次选取特征向量。 **PCA 的局限**： - 高维投影或许本身具有特定的结构 - 损失了一维的信息 - 低维嵌入是线性的近似，维度之间可能没有线性关系 ### 1.3 核 PCA 采用非线性映射 $\phi$，将非线性分布的数据投影到超平面上： ```math \min -\text{tr}(W^T X X^T W), \quad X = [\phi(x_1), \phi(x_2), \ldots, \phi(x_n)] \]

1.4 流形学习

非线性问题主要解决：将高维数据投影到低维平面，所生成的很多路径实际上是"不可达的"。就像是一根螺旋线，投影到地面上就是重叠，但是在三维上仍有信息，但毕竟这根线依然是一维的，我们实际上可以"贴地走"，把这种距离信息保留下来。

等度量嵌入（Isomap）：

采取**局部欧式假设**：假设样本点周围的几个点是符合欧式距离的，大致处于同一个低维平面之中。

算法步骤：

计算任意两点 $x, y$ 的距离：
计算 $x$ 的 $k$ 邻域
邻域内的点按欧式距离计算
邻域外的两点通过最短路径计算（使用 Dijkstra 算法）—— 这是一种"测地线"的度量
使用 MDS 算法，压缩维度后保持这种距离性质

局部线性嵌入（LLE）：

假设数据被前 $k$ 个数据线性表示，即需要得到一组权重：

\[ \min_w \sum_{i=1}^n \left\|x_i - \sum_{j=1}^n w_{ij} x_j\right\| 其中 $w_{ij}$ 满足稀疏性条件，仅在离 $x_i$ 最近的 $k$ 个点处赋值，且 $\sum_{j \in Q_i} w_{ij} = 1$。降维后依然能被线性表示： ```math \min_z \sum_{i=1}^n \left\|z_i - \sum_{j=1}^n w_{ij} z_j\right\|, \quad Z^T Z = I \]

转化为：$\min \text{tr}(Z^T M Z)$，其中 $M = (I - W^T)(I - W)$。

1.5 度量学习

降维的目的是正确认识数据，用更简单的方法衡量之间的关系。这实际上就是要靠**度量**。

k-近邻算法（KNN）：

假设数据仅仅与周围的 $k$ 个数据点有关。给定训练数据集，对于新加入的点，找出离它最近的 $K$ 个元素，哪个类别多就选哪个。

两个关键： 1. 如何衡量"远近" —— 选取度量 2. $k$ 的大小 —— $k$ 越大，误差越大，方差相对减小；$k$ 越小，模型越"复杂"，越容易捕获复杂边界

近邻成分分析（NCA）：

兼听则明，不均等听取少数人的建议：

\[ p_{ij} = \frac{\exp(-\|x_i - x_j\|_M)}{\sum_{l=1}^m \exp(-\|x_i - x_l\|_M)} 第 $i$ 个样本分类正确的概率： ```math p_i = \sum_{j \in \Omega_i} p_{ij} \]

目标：$\arg\min_M 1 - \sum_{i=1}^n \sum_{j \in \Omega_i} p_{ij}$

即适当选取度量：$\|x\|_M = \sqrt{x^T M x}$。

二、特征筛选

特征筛选分为两种： 1. 一个个把重要的特征挑出来 2. 一个个把不重要的特征筛掉

这是一种贪心的策略，因为 $n$ 个数据中找最优的 $k$ 个是 NP-hard 操作。

信息增益：

\[ \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v} \frac{|D^v|}{|D|} \text{Ent}(D^v) ### 2.1 特征筛选策略 | 策略 | 说明 | |------|------| | Filter | 过滤式，先特征选择再训练 | | Wrapper | 包裹式，用学习器性能作为评价 | | Embedding | 嵌入式，训练过程中自动选择 | ### 2.2 嵌入式特征选择（L1 正则化）通过直接采取某种损失函数的操作间接实现"减少特征数目"的效果。采取 $L^1$ 正则会让最终选取的结果落在边界上，实现减小特征的操作。对于线性回归问题： ```math \min \|y_i - w x_i\|_2^2 + \lambda \|w\|_1 \]

几乎任何问题都可以塞入一个 $L_1$ 正则项，但问题会变得难解很多。

近端梯度下降（Proximal Gradient Descent）：

考虑光滑项的极小化：$z_t = w_t - \eta \nabla f(w_t)$
在 $w$ 的领域内选取极小化：

\[ w_{t+1} = \arg\min_w \frac{1}{2\eta} \|w - z_t\|_2^2 + \lambda \|w\|_1 转化为一个一维的问题，每个 $w$ 的分量都是独立的。 ### 2.3 稀疏表示与字典学习预先假定数据分布是"稀疏"的，只有少数几个 basis 组成。 **模型**： ```math \min_{B, \alpha} \|x_i - B \alpha_i\|_2^2 + \lambda_i \|\alpha_i\|_1 \]

其中： - $B \in \mathbb{R}^{d \times k}$ 是字典矩阵 - 每个 $n$ 维向量 $x_i$ 由 $B$ 的 $k$ 个字符线性组合而成 - 每个元素只由少数几个元素稀疏表示

这是一个复合优化问题： 1. 固定字典 $B$，为每个样本找到合适的 $\alpha_i$ 2. 固定 $\alpha_i$，依次更新每一列的字典 $b_i$

使用 KSVD 保证稀疏性不会被破坏。

总结

方法	核心思想	适用场景
MDS	保持距离结构	距离已知
PCA	最大方差投影	线性降维
核 PCA	非线性映射	非线性结构
Isomap	测地线距离	流形结构
LLE	局部线性表示	局部线性流形
度量学习	学习距离度量	分类任务
L1 正则化	稀疏约束	特征选择
字典学习	稀疏表示	信号处理

归档时间：2026-03-09
来源：知乎文章
分类：数据科学 / 机器学习 / 降维与特征选择