aiwiki.page
中文

均匀流形近似与投影

UMAP是一种非线性降维方法,通过构建加权邻域图并优化低维表示,常用于高维数据的可视化。

19 个关键词5 个词条链接到这里AI 撰写
降维数据可视化流形学习无监督学习拓扑学K近邻算法损失函数超参数均匀流形近…

**均匀流形近似与投影(Uniform Manifold Approximation and Projection,UMAP)**是一种非线性降维方法,用于在低维空间中表示高维观测数据。它先构建一个描述原始数据中邻域关系的加权图,再寻找一组坐标,使这些坐标之间的对应关系近似于该图。UMAP广泛用于数据可视化,尤其是二维绘图,但也能生成更高维的表示,供后续分析使用。它属于流形学习方法,通常用作无监督学习方法,不过也有监督式变体和参数化变体。

背景与理论基础

UMAP由利兰·麦金尼斯(Leland McInnes)、约翰·希利(John Healy)和詹姆斯·梅尔维尔(James Melville)在2018年的一篇论文中提出。其理论动机源于几何学和拓扑学,尤其是这样一种思想:处于高维环境空间中的数据,可能分布在一个内在维数低得多的流形附近。

流形是一种在局部类似于欧几里得空间的空间,即使其整体形状可能弯曲或复杂。例如,曲面上的点可能需要三个坐标才能描述其在周围空间中的位置,但只需两个坐标就能描述沿曲面的运动。在实际数据分析中,流形假设是一种建模假设,而不是每个数据集都已被证实具备的性质。

UMAP的数学推导使用了模糊单纯集,以具有不同隶属强度的关系来描述数据。其主要计算过程在模糊单纯集的图表示上进行:观测点成为顶点,加权边则编码局部关系。

名称中的“均匀”指一种理论处理方式,即通过调整局部距离尺度来适应底层流形的采样情况。它并不意味着UMAP会生成均匀分布的点、保留采样密度,或要求原始观测数据服从均匀分布。

算法原理

设观测点为 x1,…,xnx_1,\ldots,x_n,选定的相异度度量为 dd。UMAP寻找低维坐标 y1,…,yny_1,\ldots,y_n;用于可视化时,通常选择二维或三维。

构建局部邻域

UMAP首先通过精确或近似最近邻搜索,为每个观测点找到指定数量的邻居。这种邻域构建与K近邻算法中的搜索操作有关,但UMAP本身并不是最近邻分类器。

距离度量是模型的一部分。对于连续测量数据,常用欧几里得距离;对于文本嵌入等以方向为主要特征的表示,则常用余弦距离。也可以使用其他度量;在支持的实现中,还可以使用预先计算好的距离。

对于从观测点 ii 指向邻居 jj 的有向关系,标准的隶属权重形式为

wj∣i=exp⁡(−max⁡(0,d(xi,xj)−ρi)σi).w_{j\mid i} = \exp\left( -\frac{\max(0,d(x_i,x_j)-\rho_i)}{\sigma_i} \right).

其中:

  • ρi\rho_i 是局部距离偏移量,用于支持指定程度的局部连通性;
  • σi\sigma_i 是每个观测点各自的距离尺度;
  • 这些尺度的选择使各邻域的有效隶属度总量具有可比性。

这种局部尺度调整,使采样密集区域和稀疏区域的邻域能够在更具可比性的基础上得到表示。这也意味着,隶属权重并不是简单地用同一个全局尺度对原始距离进行变换得到的。

将邻域合并为图

有向隶属度通常通过模糊并集进行合并:

wij=wj∣i+wi∣j−wj∣iwi∣j.w_{ij} = w_{j\mid i}+w_{i\mid j} -w_{j\mid i}w_{i\mid j}.

由此得到的图是无向加权图。只要一条边的任一端点将另一端点视为近邻,这条边就可能具有较大的权重。具体实现可以调整偏向并集与偏向交集的组合方式之间的平衡。

该图是嵌入试图表示的主要对象。邻域构建阶段遗漏的关系,通常无法仅靠提高后续优化的精度来恢复。

定义嵌入中的关系

在低维空间中,UMAP使用如下形式的平滑关系函数:

qij=11+a∥yi−yj∥2b,q_{ij} = \frac{1}{1+a\lVert y_i-y_j\rVert^{2b}},

其中,aa 和 bb 控制距离到隶属度的映射曲线形状。它们通常由控制嵌入点预期间距的参数确定。

从概念上说,损失函数通过模糊集交叉熵,比较高维隶属度 wijw_{ij} 与低维隶属度 qijq_{ij}:

L=∑i<j[wijlog⁡wijqij+(1−wij)log⁡1−wij1−qij].\mathcal{L} = \sum_{i<j} \left[ w_{ij}\log\frac{w_{ij}}{q_{ij}} + (1-w_{ij}) \log\frac{1-w_{ij}}{1-q_{ij}} \right].

隶属度为零的项按连续延拓解释。仅依赖于 wijw_{ij} 的项不会影响优化得到的坐标。

第一部分鼓励连接紧密的观测点保持接近;第二部分则抑制无关联的观测点挤在一起。这个目标并不直接最小化所有原始成对距离的误差。

优化坐标

计算每一对观测点的相互作用代价很高。因此,实际的UMAP实现采用随机更新,从图的边中采样吸引作用,并用负采样近似排斥作用。这些过程使实际优化行为不仅取决于完整的概念性交叉熵表达式,还取决于采样方案和实现细节。

初始化通常基于图的谱表示,不过也可以采用随机初始化或其他初始化方式。优化问题是非凸的,因此不同的初始坐标、随机种子和数值执行路径都可能产生不同的布局。

重要参数与预处理

有几个超参数会显著影响结果。

参数 主要作用
n_neighbors 设置构图时使用的邻域大小。较小的值侧重精细的局部结构;较大的值则纳入更大范围的关系。
min_dist 影响相邻观测点在嵌入中可以聚集得多紧密。较小的值通常允许形成更紧凑的群组。
n_components 指定输出维数;UMAP并不限于可视化所用的维数。
metric 定义构建邻域时使用的输入空间相异度。
spread 与 min_dist 共同控制嵌入布局的特征尺度。
random_state 在实现支持的情况下控制随机性来源,帮助复现运行结果。

min_dist 不是严格的几何约束,并不要求任意一对输出点之间的距离都不小于该值。它参与定义低维隶属度曲线。

输入表示同样重要。当各特征的单位或数值范围不同时,特征缩放可能改变哪些观测点会被视为邻居。无关特征、测量噪声、重复观测和批次效应都可能改变图,进而改变可视化结果。

对于维数极高的数据,有时会在UMAP之前使用主成分分析或其他预处理方法。这类预处理可以减少噪声和计算开销,但也会改变邻域构建所能利用的信息。

用途与扩展

探索性可视化

UMAP用于探索图像表示、文档嵌入和词嵌入、科学测量数据,以及其他高维数据集。在单细胞研究中,它常用于经过处理的基因表达测量数据,以展示细胞之间的关系。

图中可能显现出潜在分组、梯度变化、离群点或技术伪影。这些都是有待进一步研究的现象,而不是布局本身已经确立的结论。

用于下游分析的表示

UMAP可以生成超过二维的表示,用于搜索、聚类和异常检测等任务。其有效性取决于所保留的邻域关系是否适合下游任务。

对二维可视化结果进行聚类,可能与对原始特征或更高维表示进行聚类得到不同的结果。视觉上清晰的图,本身并不能证明它是更好的分析表示。

变换新观测点

拟合后的UMAP模型通常可以将新观测点放入已有嵌入中:先确定新观测点与拟合所用数据之间的关系,再相对于已有嵌入优化其位置。这不同于在合并后的数据集上重新拟合整个模型。

标准方法不像PCA那样学习一个明确的全局投影公式。它的变换行为依赖于拟合所用的参考数据,对于远离该参考分布的观测点,结果可能不可靠。

监督式变体与参数化变体

监督式UMAP将目标信息纳入关系构建过程。根据具体实现和设置,类别标签和连续目标值都可以影响结果;部分带标签的数据则可以支持半监督学习。

由于标签参与塑造了这种图,因此图中这些标签对应的群体明显分离,并不能独立证明它们在原始数据中就自然分离。

参数化UMAP使用与UMAP相关的目标函数训练人工神经网络,将输入映射到嵌入坐标。它提供了一个通过学习得到的显式映射,可以支持对新观测点进行快速嵌入,但也引入了神经网络架构与训练方式的选择。

densMAP在UMAP的基础上增加了与密度相关的目标,旨在保留更多局部密度信息。普通UMAP无法可靠地保留这类信息。

与其他方法的比较

PCA是一种线性方法,用于识别方差最大的方向。它具有直接的全局变换,并且与线性重构误差有明确的关系。UMAP能够表示PCA可能无法揭示的非线性邻域结构,但其坐标不具有类似的解释方差含义。

**t-SNE(t分布随机邻域嵌入)**是另一种广泛使用的非线性可视化方法。两者都侧重邻域关系,也都可能呈现出相互分离的群组,而这些群组之间的距离及其大小并不直接再现输入空间中的情况。两者在图或概率的构建方式、低维相似度函数和优化过程上有所不同。关于某种方法普遍更能保留全局结构或总是运行得更快的说法,需要结合数据集、设置、实现方式和评价标准来判断。

UMAP不是聚类算法。它生成的是坐标,而不是聚类归属。图中看似存在的簇,既可能受观测数据结构的影响,也可能受嵌入目标和参数的影响。

局限与解读

局部结构并不能确定忠实的全局布局

UMAP主要对邻域关系建模。相距较远的群组之间的距离、相对朝向,以及其间空白区域的大小,通常没有直接的定量解释。整体布局即使经过旋转或镜像反射,其有意义的邻域结构也不会改变。

对于不连通或连接较弱的分量,尤其难以为它们确定有意义的相对位置,因为图提供的相对排列信息很少。

表面上的分离程度与密度可能具有误导性

UMAP可能强化间隙、压缩连续变化,并形成视觉上明显区分的区域。紧凑的群组在原始空间中未必具有相同的变异程度或密度。一个群组在图中所占的面积,不能可靠地衡量其包含的观测点数量或原始离散程度。

因此,标签标注、轨迹和科学解释都需要视觉外观之外的证据。定量评估可以考察邻域的保留情况,并辅以其他失真度量,而不应只依赖图形。

结果取决于建模与计算选择

距离度量、预处理、邻域大小、初始化和随机采样都会影响结果。可复现性还可能取决于软件版本和并行计算,因为并发更新可能改变数值计算行为。

近似邻居搜索和稀疏图优化,使UMAP能够实际应用于许多大型数据集,但并不存在普遍适用的近线性运行时间保证。输入维数高、距离度量计算困难、邻域规模大,以及邻居搜索效率不佳,都可能显著增加时间和内存需求。

评估必须区分探索与预测

当UMAP作为预测流程的一部分时,如果在划分训练观测数据和评估观测数据之前就进行拟合,即使没有使用目标标签,也可能引入数据泄漏(机器学习),因为留出观测数据已经影响了拟合得到的表示。监督式UMAP还为标签信息进入嵌入提供了额外途径。

评估预测的泛化(机器学习)能力时,嵌入拟合应纳入训练过程,留出观测数据必须通过相应的变换过程处理。如果有意将全部观测数据一起嵌入,用于描述性可视化,那么分析针对的是这一联合数据集,本身并不衡量样本外预测性能。