UMAP：一种流形降维方法

 流形学习Manifold Learning

     流形在数学概念中是拓扑空间的一种，具有严谨的数学定义，这里我们可以简单理解为曲线面在高维空间的扩展。而流形学习的主要思想是认为高维数据存在冗余，通过映射到低维的数据已经能够反映原高维数据的某些本质结构特征。

     如同下图左面的“色带卷”作为一个流形空间，如果我们想要确定颜色和位置的关系，根本用不到“卷曲”的信息，只需要将其展开成一条“色带”，就能发现颜色填充的规律是和其所在色带长度的位置有关。

      流形学习通过识别高维空间中的关键结构，将它们保存在低维嵌入中克服“维度诅咒”，这种降维方式是机器学习从业者可视化和理解大型高维数据集的有力工具。统一流形逼近和投影 （Uniform Manifold Approximation and Projection，UMAP）作为其中一份子，在生物信息学、时序分析层面有广泛应用。简单来看，UMAP有两部分关键内容：学习高维的流形结构和寻找低维的嵌入表示。

01

高维流形结构学习

    高维数据的拓扑表示是利用局部流形逼近（local manifold approximations）和局部模糊单纯形集表示（local fuzzy simplicial set representations）进行的。概况来讲对于流形数据的每个数据点，我们可以通过自定义KNN距离度量来保证局部流形的均匀分布假设，得到K近邻图；而对于不同的局部度量空间，距离概念可能不兼容，为了合并为一致的全局空间 ，可以通过“态射”为不同度量空间找到一个模糊单纯形集的表示（加权图），完成连通图的生成。

•  K近邻图的构建

    UMAP 首先使用 Nearest-Neighbor-Descent 算法构建K近邻图。这是通过从数据集V中点v现有的近似K近邻出发，通过探索该点邻居v'的邻居u（在当前r/2的近似K近邻中）,不断收缩迭代r=r/2完善该点的K近邻。

•  K近邻图的连接 

     对于每个数据点xi，我们可以定义K近邻域中最近距离为p_i，该距离选择源自局部连接性约束，保证xi一定能连接到数据点；通过进一步平滑，得到归一化的因子表示

。

      为了确定模糊区域，我们要对两点间的连接确定性进行度量，即两点间连接的情况的概率是在0-1之间。为衡量这个连接的确定性，对于xi作为节点V，已知边方向E的图G（V，E，W），任意两点间边的权值为：

      由于我们采用了不同距离度量的方法，因此从每个点的角度来看，不可避免地会遇到边缘权重不对齐的情况，即两点间相反方向的权值不同。为合并这两条边为无向边，考虑A为图G的加权邻接矩阵，如果将Aij的值解释为存在从xi到xj的有向边的概率，那么Bij是两条有向边（从xi到xj和从xj到xi）中至少一条边存在的概率，进而可以求出无向图G的邻接矩阵。可视化如下图所示：

         在学习了高维空间的近似流形后，要将其投影到低维空间。

02

低维嵌入表示

• 力导向布局算法  

      力导向图布局利用一组沿边施加的吸引力和一组在顶点之间施加的排斥力，通过在每个边或顶点处迭代应用吸引力和排斥力来进行。这相当于一个非凸优化问题，通过以类似于模拟退火中使用的方式缓慢降低吸引力和排斥力，可以保证收敛到局部最小值。

在UMAP中，降维后分别位于坐标yi和yj的两个顶点i和j之间的吸引力由下式确定：

      通过采样计算排斥力。每当对边施加吸引力时，该边的一个顶点就会被其他顶点的采样排斥。反作用力由下式给出：    

      我们可以使用谱布局来初始化嵌入。下图算法表示了这一过程。

      谱嵌入的关键是将矩阵分解和近邻图方法结合在一起以解决降维问题。通过对近邻图构造拉普拉斯矩阵用矩阵代数（邻接度和度矩阵）对其进行形式化，按照下式对拉普拉斯矩阵进行分解，即解决特征值分解问题。

• 最小化成本函数  

      UMAP是通过模糊集交叉熵作为最小化成本函数，来优化嵌入：

       其中，对于给定的隶属函数u、v，前项表示边的吸引力，后项为节点间的排斥力。通过对u(a)的随机采样，并对v(a)值进行更新，应用梯度下降法进行优化，具体算法过程如下：

    在最优化过程中，我们就确定了最终的低维嵌入Y。

03

总结和拓展

      上图为在经典数据集上采取不同降维方法得到的可视化结果^[1]。可以发现UMAP的方式与PCA和Laplacian Eigenmaps 相比，能够对数据进行更合理的降维聚类；相比于t-SNE和LargeVis有近似的降维结构。对于线性降维和流形降维的区别，和不同流形降维方法之间的差异点，感兴趣的同学可以进一步查阅相关资料进行深入了解。

  参考文献

1. Mcinnes L ,  Healy J . UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction[J]. The Journal of Open Source Software, 2018, 3(29):861.

2. deephub. UMAP降维算法原理详解和应用示例.[EB/OL]. [2021-11-13].https://new.qq.com/rain/a/20211113A03ATH00 

3. 邻泽居士.[译] 理解 UMAP(2): UMAP和一些误解.[EB/OL].[2020-06-26].https://zhuanlan.zhihu.com/p/352461768