降维算法

1. 降维问题概述

降维是将高维数据映射到低维空间，同时尽可能保留原始数据的重要信息。

1.1 降维动机

1.2 降维方法分类

2. PCA主成分分析

2.1 数学推导

目标：找到正交变换 $\mathbf{W}$，使投影后的方差最大化：

$\mathbf{Z} = \mathbf{X}\mathbf{W}$

第一步：数据中心化

$\mathbf{X}_{centered} = \mathbf{X} - \bar{\mathbf{X}}$

第二步：最大化投影方差

第一个主成分 $\mathbf{w}_1$：

$\max_{\mathbf{w}_1} \text{Var}(\mathbf{X}\mathbf{w}_1) = \max_{\mathbf{w}_1} \mathbf{w}_1^T \mathbf{S} \mathbf{w}_1 \quad \text{s.t.} \quad \|\mathbf{w}_1\| = 1$

其中 $\mathbf{S} = \frac{1}{n}\mathbf{X}^T\mathbf{X}$ 为协方差矩阵。

第三步：拉格朗日乘子法

$\mathbf{S}\mathbf{w}_1 = \lambda_1 \mathbf{w}_1$

即 $\mathbf{w}_1$ 是 $\mathbf{S}$ 的特征向量，$\lambda_1$ 是对应特征值。

结论：PCA 的主成分就是协方差矩阵的特征向量，按特征值从大到小排列。

2.2 方差解释比

第 $k$ 个主成分的方差解释比：

$\text{Ratio}_k = \frac{\lambda_k}{\sum_{j=1}^d \lambda_j}$

累计方差解释比：

$\text{CumRatio}(m) = \frac{\sum_{k=1}^m \lambda_k}{\sum_{j=1}^d \lambda_j}$

通常选择 $m$ 使累计解释比达到 $85\% \sim 95\%$。

2.3 PCA计算方法

SVD方法：

$\mathbf{X} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$

• $\mathbf{V}$ 的列即为主成分方向
• $\boldsymbol{\Sigma}$ 的对角元素与特征值的关系：$\lambda_k = \sigma_k^2 / n$

2.4 PCA应用

from sklearn.decomposition import PCA

pca = PCA(n_components=0.95)  # 保留95%方差
X_reduced = pca.fit_transform(X)

print(f"原始维度: {X.shape[1]}")
print(f"降维后维度: {X_reduced.shape[1]}")
print(f"方差解释比: {pca.explained_variance_ratio_}")

3. t-SNE

3.1 算法原理

t-SNE（t-Distributed Stochastic Neighbor Embedding）通过保持局部邻域结构实现降维可视化。

高维空间相似度（高斯分布）：

$p_{j|i} = \frac{\exp(-\|x_i - x_j\|^2 / 2\sigma_i^2)}{\sum_{k \neq i}\exp(-\|x_i - x_k\|^2 / 2\sigma_i^2)}$

对称化：

$p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}$

低维空间相似度（Student-t分布，自由度1即柯西分布）：

$q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{\sum_{k \neq l}(1 + \|y_k - y_l\|^2)^{-1}}$

目标：最小化KL散度：

$C = \text{KL}(P \| Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$

3.2 为什么用t分布？

• 高维空间中，高斯分布的短尾导致中等距离的点在低维中被挤压
• t分布的长尾允许中等距离的点在低维中推得更远
• 缓解拥挤问题

3.3 困惑度（Perplexity）

$\text{Perp}(P_i) = 2^{H(P_i)}$

其中 $H(P_i) = -\sum_j p_{j|i} \log_2 p_{j|i}$ 为信息熵。

• 困惑度可理解为”有效近邻数”
• 典型值：5~50
• 困惑度越大，关注越全局的结构

3.4 t-SNE注意事项

• 不可用于特征工程：t-SNE不保持全局距离和簇间关系
• 不可增量：新数据需要重新运行
• 随机性：不同运行可能产生不同结果
• 超参数敏感：困惑度、学习率、迭代次数影响结果
• 簇大小不可比较：t-SNE会膨胀密集簇、压缩稀疏簇

4. UMAP

4.1 算法原理

UMAP（Uniform Manifold Approximation and Projection）基于拓扑数据分析和黎曼几何。

步骤1：构建模糊拓扑表示

高维空间中的局部相似度：

$p_{j|i} = \exp\left(-\frac{d(x_i, x_j) - \rho_i}{\sigma_i}\right)$

其中 $\rho_i = \min_j d(x_i, x_j)$ 为最近邻距离。

步骤2：对称化

$p_{ij} = p_{j|i} + p_{i|j} - p_{j|i} \cdot p_{i|j}$

步骤3：优化低维嵌入

最小化交叉熵：

$C = \sum_{(i,j)} \left[-p_{ij}\log q_{ij} - (1-p_{ij})\log(1-q_{ij})\right]$

4.2 UMAP vs t-SNE

4.3 UMAP参数

5. 降维方法选择指南