UMAP (Uniform Manifold Approximation and Projection) 降维也是seurat中常用的降维可视化工具，在seurat中对应的函数是RunUMAP()，相对于TSNE降维，UMAP降维更加“快准狠”，这里简单介绍下umap降维的相关知识。
umap降维的数学推断[1]
umap算法基于数据的3个假设：
- 数据在流形（manifold）上均匀分布，此条件是为了更好更容易地捕获拓扑结构；现实中这样的数据很少，但是我们可以用黎曼度量来解决这个问题。
- 此流形结构是局部相连的。
- 保留流形结构的拓扑结果是主要目标
首先假定数据集为：
先捕获高维空间中的流形结构，通过构建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
-
1.3 构建local fuzzy simplicial sets（局部单纯形集合）
- 主要是0-单纯集合1-单纯集；0-单纯集就是X中的每个数据点的集合，1-单纯集可以理解为线的集合，即两点间相连，且权重为w，权重可以理解为此边存在的概率。
- 此时相当于构建图了G，构建的图结构为G=(V,E,w), V就是数据集X，有向边的权重就是w。
- 主要是0-单纯集合1-单纯集；0-单纯集就是X中的每个数据点的集合，1-单纯集可以理解为线的集合，即两点间相连，且权重为w，权重可以理解为此边存在的概率。
-
1.4 边权重的变换
- 因为此时两点间的权重是不对称的，因此将权重进行转换，由权重矩阵A变为B。
- 此时的B可以理解为两点间至少一个有向边存在的概率。
- 因为此时两点间的权重是不对称的，因此将权重进行转换，由权重矩阵A变为B。
1.5 我们最终得到了一个单一的模糊单纯集，可将其视为一个加权图，其捕获到了高维空间的流形。
第二步是找到一个低维空间，此低维空间需要满足：
使其能够代表高维空间的拓扑结构
通过交叉熵（cross entropy）来衡量高维和低维空间两者的简单集相对应的1-简单集的差异。
交叉熵的定义
-
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.
