降维算法

1. 降维问题概述

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

1.1 降维动机

1.2 降维方法分类

2. PCA主成分分析

2.1 数学推导

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

$\mathbf{Z}=\mathbf{XW}$

第一步：数据中心化

${\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\text{s.t.}\Vert {\mathbf{w}}_1\Vert =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}\mathbf{\Sigma }{\mathbf{V}}^T$

• $\mathbf{V}$ 的列即为主成分方向
• $\mathbf{\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 (-\Vert x_i-x_j{\Vert }^2/2{\sigma }_i^2)}{{\sum }_{k\ne i}\exp (-\Vert x_i-x_k{\Vert }^2/2{\sigma }_i^2)}$

对称化：

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

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

$q_{ij}=\frac{(1+\Vert y_i-y_j{\Vert }^2{)}^{-1}}{{\sum }_{k\ne l}(1+\Vert y_k-y_l{\Vert }^2{)}^{-1}}$

目标：最小化KL散度：

$C=\text{KL}(P\Vert Q)={\sum }_{i\ne 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. 降维方法选择指南