Seurat知识点(2)

UMAP (Uniform Manifold Approximation and Projection) 降维也是seurat中常用的降维可视化工具，在seurat中对应的函数是RunUMAP()，相对于TSNE降维，UMAP降维更加“快准狠”，这里简单介绍下umap降维的相关知识。

umap降维的数学推断[1]

umap算法基于数据的3个假设：

数据在流形（manifold）上均匀分布，此条件是为了更好更容易地捕获拓扑结构；现实中这样的数据很少，但是我们可以用黎曼度量来解决这个问题。
此流形结构是局部相连的。
保留流形结构的拓扑结果是主要目标
首先假定数据集为：
$X={x_1,x_2,...,x_N}$

先捕获高维空间中的流形结构，通过构建fuzzy simplicial set来代表高维空间的流形结构。具体步骤如下：

1.1 对于每个点xi，找寻其最近的k个点
- 通过近似最近邻搜索ANN(Approximate Nearest Neighbor)方法来搜寻，并得到距离度量dist: X×X → R≥0。
- k的选取很重要，它控制 UMAP如何平衡数据中的局部和全局结构。例如k为10，则直接连接到第11个以上的邻居的可能性为0。
1.2 标准化dist得到d

$d(x_i,x_{ij})= \frac{max(0,dist(x_i,x_{ij})-ρ_i)}{\sigma_i}$
$其中，ρ_i= min\lbrace{d(x_i , x_{ij} ) | 1 ≤ j ≤ k, d(x_i , x_{ij}) > 0}\rbrace$
$\sigma_i可由二分搜索获取，使满足\Sigma_{j=1}^kexp(\frac{-max(0,d(x_i,x_{ij})- ρ_i)}{\sigma_i})=log2(k)$

1.3 构建local fuzzy simplicial sets（局部单纯形集合）
- 主要是0-单纯集合1-单纯集；0-单纯集就是X中的每个数据点的集合，1-单纯集可以理解为线的集合，即两点间相连，且权重为w，权重可以理解为此边存在的概率。
  $w(x_i,x_{ij})=exp(-d(x_i,x_{ij}))$
- 此时相当于构建图了G，构建的图结构为G=(V,E,w), V就是数据集X，有向边的权重就是w。
1.4 边权重的变换
- 因为此时两点间的权重是不对称的，因此将权重进行转换，由权重矩阵A变为B。
  $假定A为Graph的权重邻接矩阵，则定义 B=A+A^T-A◦A^T, ◦指点积。$
- 此时的B可以理解为两点间至少一个有向边存在的概率。
1.5 我们最终得到了一个单一的模糊单纯集，可将其视为一个加权图，其捕获到了高维空间的流形。

第二步是找到一个低维空间，此低维空间需要满足：

使其能够代表高维空间的拓扑结构
通过交叉熵（cross entropy）来衡量高维和低维空间两者的简单集相对应的1-简单集的差异。
交叉熵的定义
$两个模糊简单集 (A,\mu)和（A,\nu）交叉熵C的定义如下:$
$C((A,\mu),(A,\nu))=\Sigma_{a \in A}(\mu(a)log\frac{\mu(a)}{\nu(a)}+(1-\mu(a))log\frac{(1-\mu(a))}{(1-\nu(a))})$
2.1 初始化低维空间
- 理论上，低维空间的初始化可以是随机的，但是为了计算的速度及稳定性，我们使用spectral layout来初始化低维空间。
2.2 最小化交叉熵，输出低维空间
- 从图的角度来看，可将最小化交叉熵视为一种力有向图布局算法。

UMAP相关知识补充

流形(Manifold)
简单的说，一个拓扑空间，加上一个微分结构，称为流形(Manifold)
拓扑空间
指定了拓扑的集合叫做一个拓扑空间。
拓扑
拓扑是集合中的一个子集，且满足一定的条件，开集就是拓扑里的元素，因此开集的定义就是先验的。也就是说给一些开集，它们就能生成一个拓扑
simplicial set（单纯集）
与simplicial complexes（单纯复形）的概念有关；simplicial complexes是simplices（单纯行）的集合，能够捕获拓扑结构；simplicial set比simplicial complexes更普遍，更容易用范畴论的语言描述。

参考

[1] UMAP: Uniform Manifold Approximation and Projection forDimension Reduction.

Seurat知识点(2)