UMAP 工作原理
适应真实世界数据
上面描述的方法为基于邻域图的方法在进行降维时应如何捕捉流形结构提供了一个很好的理论。问题往往出现在将理论付诸实践时。第一个明显的困难（即使在我们上面的例子中也能看到）是，为构成开覆盖的球选择合适的半径很困难。如果选择得太小，生成的单纯复形会分裂成许多连通分量。如果选择得太大，单纯复形会变成少数几个非常高维的单纯形（及其面等），并且不再能捕捉流形结构。该如何解决这个问题？
这个困境部分是由于提供我们理由证明这个过程捕捉拓扑结构的定理（称为Nerve 定理）。具体来说，该定理说单纯复形与覆盖的并集是（同伦）等价的。在我们的情况下，处理有限数据时，对于某些半径，覆盖并未覆盖我们想象中支撑数据的整个流形——正是这种覆盖不足导致了不连通分量。同样，在点过于密集的地方，我们的覆盖确实覆盖了“太多”，最终得到比理想情况更高维度的单纯形。如果数据在流形上是*均匀分布的*，那么选择合适的半径就很容易——点之间的平均距离就能很好地工作。此外，在均匀分布的情况下，我们可以保证我们的覆盖会实际覆盖整个流形，没有“间隙”，也没有不必要的断开连接的分量。同样，我们也无需遭受那些不幸的聚集效应，这些效应会导致不必要的高维度单纯形。
如果我们考虑沿着同一流形均匀分布的数据，那么选择一个好的半径（略高于点之间平均距离的一半）并不困难，得到的开覆盖看起来相当不错。
均匀分布数据上的开球
由于数据均匀分布，我们实际上覆盖了潜在的流形，并且不会出现聚集。换句话说，所有这些理论都很好地工作，前提是假设数据在流形上是均匀分布的。
不足为奇的是，这种均匀分布的假设在流形学习的其他地方也屡屡出现。拉普拉斯特征映射之所以效果好，其证明需要数据在流形上均匀分布的假设。显然，如果数据在流形上均匀分布，一切都会好得多——但事实并非如此！真实世界的数据根本没有那么好的表现。我们如何解决这个问题？通过逆向思维：假设数据在流形上均匀分布，然后问这告诉我们关于流形本身什么。如果数据*看起来*不像均匀分布的，那一定仅仅是因为距离的概念在流形上是变化的——空间本身正在扭曲：根据数据显得稀疏或密集的地方而伸展或收缩。
通过假设数据均匀分布，我们可以利用一些标准黎曼几何，实际计算出每个点的局部距离概念（或其近似）。在实践中，一旦您深入数学推导，这最终意味着点周围的单位球会拉伸到该点的第 *k* 个最近邻，其中 *k* 是我们用来近似局部距离感的样本大小。每个点都有自己独特的距离函数，我们可以简单地根据该局部距离函数选择半径为一的球！
局部度量变化的半径为一的开球
这个理论推导的结果与许多传统的基于图的算法很好地契合：这些算法的标准方法是使用 *k*-邻域图，而不是使用具有固定半径的球来定义连通性。这意味着数据集中每个点都与其 *k* 个最近邻之间建立一条边——这是我们使用半径为一的局部变化度量的有效结果。然而，现在我们可以从单纯复形和 Nerve 定理的角度解释它为什么有效。
当然，我们用选择球的半径换来了选择 *k* 值。然而，通常更容易根据邻居数量来选择分辨率尺度，而不是正确选择距离。这是因为选择距离很大程度上取决于数据集：需要查看数据集中距离的分布才能开始选择一个好的值。相比之下，虽然 *k* 值在一定程度上仍然取决于数据集，但存在合理的默认选择，例如 10 个最近邻，这对于大多数数据集来说都是可以接受的。
同时，这一切的拓扑解释为我们提供了对 *k* 更具意义的解释。选择 *k* 决定了我们希望在多大程度上局部估计黎曼度量。选择小的 *k* 意味着我们想要一个非常局部的解释，这将更准确地捕捉黎曼度量的精细细节结构和变化。选择大的 *k* 意味着我们的估计将基于更大的区域，因此，虽然会遗漏一些精细的细节结构，但它们在整个流形上将更广泛地准确，因为有更多的数据可用于估计。
这种基于黎曼度量的方法还带来了另一个好处：我们实际上为每个点关联了一个局部度量空间，并且可以有意义地测量距离，因此我们可以根据边上的点（在局部度量方面）相距多远来为可能生成的图的边加权。用稍微更数学化的术语来说，我们可以将这视为在模糊拓扑中工作，其中位于覆盖中的开集不再是二元的“是”或“否”，而是一个介于零和一之间的模糊值。显然，点位于给定半径球中的确定性会随着我们远离球心而衰减。我们可以将这种模糊覆盖可视化为这样子：
局部度量变化的半径为一的模糊开球
这些都不是非常具体或正式的——它仅仅是我们希望发生的事情的一个直观图像。事实证明，我们可以通过借用代数拓扑中的奇异集和几何实现函子，然后将它们应用于度量空间和模糊单纯集，来实际形式化这一切。其中涉及的数学超出了本文的范围，但对于有兴趣的人，可以查看David Spivak 关于此的原始工作以及我们的论文。只需说存在一些数学工具可以让我们以明确的方式实现这种直觉。
这解决了一些问题，但当我们将此类过程应用于真实数据（特别是在高维度数据）时，又出现了一个新问题：许多点基本上完全孤立了。人们可能会想，如果数据采样来源的流形不是病态的，就不应该发生这种情况。那么，我们期望该流形具备而当前方法某种程度上遗漏了什么属性呢？我们需要添加的是局部连通性的概念。
请注意，这并非要求整个流形是连通的——它可以由许多连通分量组成。相反，它要求在流形上的任何点，其某个足够小的邻域是*连通的*（这个“在足够小的邻域中”就是“局部”部分的含义）。对于我们正在处理的实际问题，即我们只有流形的有限近似，这意味着任何点都不应该是*完全*孤立的——它应该至少连接到另一个点。就模糊开集而言，这意味着我们应该完全确信开集会扩展到每个点的最近邻。我们可以通过简单地让模糊置信度根据与第一最近邻的距离*以外*的距离衰减来实现这一点。我们可以再次用我们的示例数据集来可视化结果。
局部连通性和模糊开集
同样，这可以用前面提到的代数拓扑数学工具来形式化。从实践角度来看，这对高维数据起着重要作用——在高维度中，距离往往更大，但也彼此更相似（参见维度诅咒）。这意味着到第一最近邻的距离可能相当大，但到第十最近邻的距离通常只稍微大一点（相对而言）。局部连通性约束确保我们关注最近邻之间距离的差异，而不是绝对距离（它在邻居之间显示出很少的区分）。
就在我们以为快要解决真实世界数据的一些问题时，又遇到了新的障碍：我们的局部度量不兼容！每个点都有其关联的局部度量，从点 *a* 的角度来看，点 *a* 到点 *b* 的距离可能是 1.5，但从点 *b* 的角度来看，点 *b* 到点 *a* 的距离可能只有 0.6。哪个点是对的？我们如何决定？回到我们基于图的直觉，我们可以将这视为具有不同权重的有向边，如下图所示。
权重不兼容的边
在任意两点之间，我们可能有多达两条边，并且这些边的权重彼此不一致。对于两个不一致的权重，有多种处理方法——我们可以取最大值、最小值、算术平均值、几何平均值，或者其他完全不同的方法。我们真正想要的是一个有原则的方式来做出决定。正是在这一点上，我们构建的数学工具发挥作用了。从数学上看，我们实际上有一族模糊单纯集，并且显而易见的选项是取它们的并集——这是一个明确定义的操作。有几种方法可以定义模糊并集，取决于所涉及逻辑的性质，但在本文中，我们有相对清晰的概率语义，这使得选择变得简单明了。用图的术语来说，我们得到的是：如果我们要合并两条权重分别为 *a* 和 *b* 的不一致的边，那么我们应该得到一条合并权重为 \(a + b - a \cdot b\) 的单条边。理解这一点的方式是，权重实际上是边（1-单纯形）存在的概率。合并后的权重就是至少一条边存在的概率。
如果我们应用这个过程将所有模糊单纯集并集起来，最终会得到一个单一的模糊单纯复形，我们可以再次将其视为一个加权图。在计算术语中，我们只是将边权重组合公式应用于整个图（没有边的权重为 0）。最终我们得到了类似这样的东西。
具有合并边权重的图
因此，从某种意义上说，最终我们只是简单地构建了一个加权图（尽管如果愿意，我们可以利用更高维度的单纯形，但这会带来显著的额外计算成本）。潜藏在背景中的数学理论为我们做的是确定我们*为什么*应该构建*这个*图。它还帮助我们决定具体*如何*进行计算，并提供了对这个图*意味着什么*的具体解释。所以，尽管最终我们只是构建了一个一个图，但数学回答了引导我们到这里的重要问题，并可以帮助我们决定下一步做什么。
那么，既然我们现在有了数据的模糊拓扑表示（数学表明这会捕捉数据潜在流形的拓扑结构），我们如何将其转换为低维表示呢？
