Uniform Manifold Approximation and Projection。

paper：UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction

一致流形近似与投影(Uniform Manifold Approximation and Projection, UMAP)是一种基于流形的非线性降维算法。UMAP的原理与t-SNE类似，即在高维样本空间中为每个样本点构建一个概率分布，用于拟合样本点之间的相对位置关系(联合概率)；在降维后的低维空间中也为其对应的样本构建一个概率分布，用于拟合降维样本点之间的位置关系。构造损失函数，通过学习降维后的样本点，使得高维样本点之间的位置关系和低维样本点之间的位置关系尽可能相似。

与t-SNE不同，UMAP的建模不是严格意义上的归一化概率分布，而是一种相似度函数。对于每一个样本点，计算它和其余样本点的相似度，并构造相似度矩阵。把降维后的低维空间中的样本点看作可学习参数，通过梯度方法使得低维空间中的样本点也具有相似的相似度矩阵。

相较于t-SNE，UMAP的主要优势如下：

可以调节每一簇样本的聚拢程度，能够更好地表达局部结构；
具有更好的优化过程，提高了在较大样本集上的运算效率和运算速度。

1. UMAP算法

记高维空间中的样本点 $X \in \Bbb{R}^{n \times d}$ ，待求的降维样本点 $Y \in \Bbb{R}^{n \times d’}$ 。

对于高维空间中的任意样本点 $x_i$ ，计算它和其他样本点 $x_j$ 之间的相似度(条件概率):

p_{i | j} = e^{- \frac{d (x_{i}, x_{j}) - ρ_{i}}{σ_{i}}}

$p_{i|j} = e^{-\frac{d(x_i, x_j)-\rho_i}{\sigma_i}}$

为了保证相似度的对称性，进一步计算联合概率：

p_{i j} = p_{i | j} + p_{j | i} - p_{i | j} p_{j | i}

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

其中距离计算可以采用任意度量。 $\rho_i$ 表示距离样本点 $x_i$ 最近的样本点对应的距离； $\sigma_i$ 是可调节参数，若指定只关注样本点附近的 $k$ 个样本，则通过 $k=2^{\sum_{i}^{j}p_{ij}}$ 求解 $\sigma_i$ 。

对于低维空间中的样本点 $y_i$ ，同样计算它和其他样本点 $y_j$ 之间的相似度:

q_{i j} = (1 + a (y_{i} - y_{j})^{2 b})^{- 1}

$q_{ij} = (1+a(y_i-y_j)^{2b})^{-1}$

优化目标是最小化 $p_{ij}$ 和 $q_{ij}$ 之间的差异，采用交叉熵损失：

C E = \sum_{i}^{} \sum_{j}^{} [p_{i j} \log (\frac{p_{i j}}{q_{i j}}) + (1 - p_{i j}) \log (\frac{1 - p_{i j}}{1 - q_{i j}})]

$CE = \sum_{i}^{} \sum_{j}^{} [p_{ij}\log(\frac{p_{ij}}{q_{ij}})+(1-p_{ij})\log(\frac{1-p_{ij}}{1-q_{ij}})]$

2. UMAP v.s. t-SNE

t-SNE和UMAP的主要不同如下：

① 高维空间中的样本关系

t-SNE用高斯分布衡量高维空间中两个样本点之间的距离，其距离采用欧氏距离进行衡量：

p_{j | i} = \frac{\exp (- | | x_{i} - x_{j} | |^{2} / 2 σ_{i}^{2})}{\sum_{k \neq i}^{} \exp (- | | x_{k} - x_{i} | |^{2} / 2 σ_{i}^{2})}

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

UMAP使用任意度量作为距离函数，并计算未归一化的概率分布：

p_{i | j} = e^{- \frac{d (x_{i}, x_{j}) - ρ_{i}}{σ_{i}}}

$p_{i|j} = e^{-\frac{d(x_i, x_j)-\rho_i}{\sigma_i}}$

相较于t-SNE，UMAP引入了 $\rho_i$ 参数。 $\rho_i$ 表示距离样本点 $x_i$ 最近的样本点对应的距离。

对于t-SNE，如果样本点 $x_i$ 距离其他样本点 $x_j$ 都很远，则计算得到的 $p_{j|i}$ 都比较小，造成最终的相似性图不具有连通性。
对于UMAP，引入 $\rho_i$ 参数使得至少存在一个 $x_j$ 满足 $p_{i|j}=1$ ，保证图的连通性。

此外，对计算的概率分布不进行归一化，能够减少计算量。

② 低维空间中的样本关系

t-SNE用t分布衡量低维空间中的两个样本点之间的相似度：

q_{i j} = \frac{(1 + | | y_{i} - y_{j} | |_{2}^{2})^{- 1}}{\sum_{k \neq l}^{} (1 + | | y_{k} - y_{l} | |_{2}^{2})^{- 1}}

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

UMAP去掉了归一化项：

q_{i j} = (1 + a | | y_{i} - y_{j} | |_{2}^{2 b})^{- 1}

$q_{ij} = (1+a||y_i-y_j||_2^{2b})^{-1}$

UMAP引入了两个超参数 $a$ 和 $b$ ，其目的是用 $q_{ij}$ 拟合以下分段函数：

Ψ (x, y) = {\begin{cases} 1, & | | x - y | |_{2} \leq d i s t \\ e^{- | | x - y | |_{2} - d i s t}, & otherwise \end{cases}

$\Psi(x,y) = \begin{cases} 1, & ||x-y||_2\leq dist \\e^{-||x-y||_2-dist} , & \text{otherwise} \end{cases}$

观察该分段函数(上图蓝色曲线)，超参数 $dist$ 设置了一个距离的阈值。当样本点之间的距离小于该阈值时，则可认为两个样本相似度较高( $q_{ij}≈1$ )。通过调整参数 $dist$ ，可以控制投影点的聚拢程度。 $dist$ 越大，则投影后相似的点越分散； $dist$ 越小，则投影后相似的点越聚拢。

③ 损失函数

t-SNE用KL散度衡量 $p_{ij}$ 和 $q_{ij}$ 的距离：

K L (p_{i j} | | q_{i j}) = \sum_{i}^{} \sum_{j}^{} p_{i j} \log (\frac{p_{i j}}{q_{i j}})

$KL(p_{ij} || q_{ij}) = \sum_{i}^{} \sum_{j}^{} p_{ij} \log (\frac{p_{ij}}{q_{ij}})$

UMAP则用交叉熵损失：

C E = \sum_{i}^{} \sum_{j}^{} [p_{i j} \log (\frac{p_{i j}}{q_{i j}}) + (1 - p_{i j}) \log (\frac{1 - p_{i j}}{1 - q_{i j}})]

$CE = \sum_{i}^{} \sum_{j}^{} [p_{ij}\log(\frac{p_{ij}}{q_{ij}})+(1-p_{ij})\log(\frac{1-p_{ij}}{1-q_{ij}})]$

用 $X$ 表示高维点之间的距离，用 $Y$ 表示低维点之间的距离。绘制两个损失平面：

观察t-SNE的损失曲面，当 $X$ 较小时(高维点距离较近) $Y$ 也应该取较小值，此时对于较大的 $Y$ (低维点距离较远)会产生比较大的梯度，此时有利于梯度更新。但是当 $X$ 较大时(高维点距离较远)，对于较小的 $Y$ (低维点距离较近)具有比较小的梯度，此时不利于梯度更新。综上所述，t-SNE擅长把高维空间中距离较近的点投影到邻近的低维空间中；但是对于高维空间中距离较远的点，无法准确地保持投影后的距离关系。

UMAP通过调整损失函数解决了梯度消失的问题。当 $X$ 较小时(高维点距离较近)，对于较大的 $Y$ (低维点距离较远)会产生比较大的梯度；当 $X$ 较大时(高维点距离较远)，对于较小的 $Y$ (低维点距离较近)也会产生比较大的梯度；这两种情况下都有利于梯度更新。

3. UMAP的流程

由上述介绍，UMAP的一般步骤如下：

给定高维空间中的样本点 $X \in \Bbb{R}^{n \times d}$ ，降维维度 $d’$ ，近邻点超参数 $k$ 和分段超参数 $dist$ ;
通过超参数 $dist$ 寻找拟合曲线的参数 $a$ 和 $b$ ： $(1+a\|x-y\|_2^{2b})^{-1}≈\begin{cases} 1, & \|x-y\|_2\leq dist \\e^{-\|x-y\|_2-dist} , & \text{otherwise} \end{cases}$
对于每个样本点 $x_i$ ，计算距离样本点 $x_i$ 最近的样本点对应的距离 $\rho_i$ ，通过 $k=2^{\sum_{i}^{j}p_{ij}}$ 寻找 $\sigma_i$ ；
计算其余样本点的条件概率 $p_{i|j} = e^{-\frac{d(x_i, x_j)-\rho_i}{\sigma_i}}$ ；
进一步计算联合概率 $p_{ij} = p_{i|j}+p_{j|i}-p_{i|j}p_{j|i}$ ；
使用所有样本的 $p_{ij}$ 构造相似性图，通过谱聚类初始化低维数据 $Y \in \Bbb{R}^{n \times d’}$ ；
计算损失函数 $CE = \sum_{i}^{} \sum_{j}^{} [p_{ij}\log(\frac{p_{ij}}{q_{ij}})+(1-p_{ij})\log(\frac{1-p_{ij}}{1-q_{ij}})]$ ；
采用随机梯度下降更新参数。

实例：使用PCA和UMAP对手写数字数据集降维可视化

①导入相关的库：

# pip install umap-learn
from sklearn.datasets import load_digits
from sklearn.decomposition import PCA
import umap
import matplotlib.pyplot as plt

②使用PCA和t-SNE降维：

digits = load_digits()
X_pca = PCA(n_components=2).fit_transform(digits.data)
X_umap = umap.UMAP(n_neighbors=15, min_dist=0.1,
                   n_components=2,).fit_transform(digits.data)

③可视化：

plt.figure(figsize=(10, 5))
plt.subplot(121)
plt.scatter(X_umap[:, 0], X_umap[:, 1], c=digits.target, label="UMAP")
plt.legend()
plt.subplot(122)
plt.scatter(X_pca[:, 0], X_pca[:, 1], c=digits.target, label="PCA")
plt.legend()
plt.show()