局部邻域怎样拼成可外推的图？UMAP 的模糊边权与交叉熵

上一篇的 t-SNE 把高维邻域写成概率，再用重尾相似度把可靠邻居拉近、伪邻居推远。它很适合二维探索，但标准形式直接联合优化训练样本坐标，没有自然的 transform；困惑度又通过每点带宽间接控制尺度，图上的全局关系不宜解释。

统一流形逼近与投影（Uniform Manifold Approximation and Projection，UMAP）也从近邻出发，却先构造一张模糊近邻图（Fuzzy Neighborhood Graph）：局部距离被换成 $[0,1]$ 边权，再在低维中寻找一张边权相似的图。本文聚焦局部半径与尺度、模糊并集、交叉熵优化这条主线；拓扑理论只解释设计动机，不做百科式展开。

01 t-SNE 已能看邻居，为什么还要换成图？#

真实项目常同时需要：

局部相似样本在低维仍靠近；
数十万样本时不要构造完整 $N\times N$ 概率矩阵；
新样本能进入已有表示，供下游验证或交互查询；
能明确调节“看多大的邻域”和“低维团块压多紧”。

UMAP 用稀疏 K 近邻（K-Nearest Neighbors，KNN）图承载前两点，用训练图上的局部插值与优化近似实现第三点，用 n_neighbors 和 min_dist 分别控制后两种几何偏好。

高维样本 X
   │ KNN：只保留每点 K 条候选边
   ▼
有向局部边权 vⱼ|ᵢ
   │ 模糊并集：融合 i→j 与 j→i
   ▼
无向稀疏图 V
   │ 在低维建立边权 W(Y)，匹配 V
   ▼
低维坐标 Y ──► 新样本可相对训练邻居定位

text

“可外推”仍是近似能力，不代表学到了神经网络式的全局解析映射；远离训练流形的新点依然可能被错误安放。

02 完整数据流与张量形状#

设训练输入 $X\in\mathbb R^{N\times D}$ ，每点取 $K$ 个邻居，输出 $Y\in\mathbb R^{N\times d}$ ：

X [N,D]
  │ 近似或精确 KNN
  ▼
J [N,K]：邻居索引       R [N,K]：邻居距离
  │ 每行求局部连通半径 ρᵢ 与尺度 σᵢ
  ▼
V_dir：稀疏有向权重，最多 NK 个非零
  │ vᵢⱼ + vⱼᵢ - vᵢⱼvⱼᵢ
  ▼
V：稀疏对称高维图 [N,N]

Y₀ [N,d]（常用谱初始化）
  │ 低维相似度 wᵢⱼ(Y)
  │ 对正边采样吸引，对非边负采样排斥
  ▼
Y [N,d]

text

与 t-SNE 的密集联合概率不同，UMAP 的高维对象主要是至多 $O(NK)$ 条稀疏边。近邻搜索、图构造和随机优化仍会消耗可观时间与内存，但不必默认保存所有点对。

03 每个点为什么先减去局部半径 ρᵢ？#

对点 $x_i$ ，将第一个非零近邻距离记为局部连通半径 $\rho_i$ 。最常见的 local_connectivity=1 意味着至少最近的一个邻居应被视为完全连通。

有向边 $i\to j$ 的强度定义为：

v_{j\mid i}= \exp\left(-\frac{\max(0,d(x_i,x_j)-\rho_i)}{\sigma_i}\right)

$d(x_i,x_j)$ ：输入度量下的邻居距离；
$\rho_i\ge0$ ：点 $i$ 的局部连通半径；
$\sigma_i>0$ ：点 $i$ 的局部尺度；
$v_{j\mid i}\in(0,1]$ ：有向模糊成员强度（Membership Strength）。

只要 $d(x_i,x_j)\le\rho_i$ ，边权就是 1。这样每个点至少与一个近邻牢固连接，减少稀疏区域成为孤点的风险。

同样的绝对距离 0.4

稠密区 i：ρᵢ=0.05, σᵢ=0.10 → 权重很小
稀疏区 k：ρₖ=0.30, σₖ=0.40 → 权重较大

UMAP 比较的是“相对本地尺度有多近”，不是统一半径下的绝对距离

text

这能适应采样密度，却也弱化了低维团块面积对原始密度的直接解释。需要显式保留密度时，应验证 densMAP 等扩展，而不是从普通 UMAP 的点团大小下结论。

04 σᵢ 怎样让每个局部邻域可比较？#

UMAP 为每一行寻找 $\sigma_i$ ，使邻居边权总量接近一个与 $K$ 有关的目标，常写成：

\sum_{j=1}^{K} \exp\left(-\frac{\max(0,d_{ij}-\rho_i)}{\sigma_i}\right) \approx\log_2K

这一步叫平滑 K 近邻距离（Smooth K-Nearest-Neighbor Distance）。 $\sigma_i$ 小会让权重快速衰减， $\sigma_i$ 大会让更多邻居保留明显边权；实现通过单调二分搜索求解。

n_neighbors=K 因而不只是“图里有几条边”：

小 $K$ 只观察很局部的片段，细节多但图易断；
大 $K$ 让局部尺度覆盖更广，更强调宏观连续性但可能抹掉细粒度结构；
同一个 $K$ 在不同数据规模、噪声和密度下含义不同，必须做稳定性扫描。

05 四条距离怎样手算有向边权？#

假设点 $i$ 的三个近邻距离为：

[0.2,\ 0.5,\ 1.0]

为便于手算，取 $\rho_i=0.2,\sigma_i=0.3$ 。三条有向边为：

v_{1\mid i}=e^0=1

v_{2\mid i}=e^{-(0.5-0.2)/0.3}=e^{-1}\approx0.368

v_{3\mid i}=e^{-(1.0-0.2)/0.3}\approx0.069

最近邻被完全连接，之后按超出本地半径的距离指数衰减。这里的 $\sigma_i$ 是演示给定值；真实算法会二分搜索，让边权总量达到目标。

若反方向 $v_{i\mid2}=0.4$ ，怎样融合 $i\to2$ 和 $2\to i$ ？UMAP 使用模糊集合并集：

v_{i2}=v_{2\mid i}+v_{i\mid2}-v_{2\mid i}v_{i\mid2}

v_{i2}\approx0.368+0.4-0.368\times0.4=0.621

只要任一方向很强，无向边就会较强；两边都弱时，并集仍弱。它等价于“至少一条方向关系成立”的软逻辑或概率和。

06 模糊并集怎样把局部视角拼成全局图？#

令有向权重矩阵为 $V^{\rightarrow}$ ，转置代表反向视角。默认模糊并集为逐元素：

V=V^{\rightarrow}+(V^{\rightarrow})^\top -V^{\rightarrow}\odot(V^{\rightarrow})^\top

$V\in[0,1]^{N\times N}$ 对称但稀疏。每一条边表示两个局部邻域对“这对样本相连”的综合信心。

图并不自动忠实：错误度量会连错边，近似近邻会漏边，过大的 $K$ 会跨越流形折叠或不同群体。UMAP 后面的优化只能尽量表现这张图，不能修复图构造阶段的语义错误。

工程上至少检查：

近邻距离的中位数、长尾与异常小值；
图的连通分量、孤立点和节点度分布；
不同 $K$ 下边集合的重合率；
已知成对约束或领域近邻的召回率；
标准化、余弦距离、领域距离改变了哪些关键邻居。

07 低维边权怎样由 min_dist 控制？#

在低维中，UMAP 用一条重尾曲线把距离映射为边权：

w_{ij}(Y)=\frac{1}{1+a\lVert y_i-y_j\rVert_2^{2b}}

$a,b>0$ 由用户指定的 min_dist 和 spread 拟合得到。spread 控制嵌入的有效尺度，min_dist 控制近邻在低维允许压得多紧：

min_dist 小                         min_dist 大

   ●●●       ●●                      ●  ●      ●  ●
  ●●●●      ●●●       对比          ●   ●    ●   ●
   紧密团块、细小丝状结构             更均匀展开、局部留白更多

text

它不是所有点对都必须满足的硬性最小欧氏距离，而是通过目标曲线改变“多近仍算强边”的有效尺度。将 min_dist=0.1 解释成图上任意两点至少相距 0.1 是错误的。

n_neighbors 主要改变高维图看多大范围，min_dist 主要改变低维如何打包强边。二者职责不同，应交叉扫描而不是互相替代。

08 交叉熵怎样同时吸引边与排斥非边？#

把高维边权记为 $v_{ij}$ ，低维边权记为 $w_{ij}$ ，UMAP 最小化二元交叉熵形式：

C=\sum_{i<j} \left[ v_{ij}\log\frac{v_{ij}}{w_{ij}} +(1-v_{ij})\log\frac{1-v_{ij}}{1-w_{ij}} \right]

第一部分让高权重真边在低维也有高 $w_{ij}$ ，形成吸引；第二部分让高维非边保持低 $w_{ij}$ ，形成排斥。

所有非边数量接近 $N^2$ ，无法逐对计算。UMAP 采用随机梯度下降（Stochastic Gradient Descent，SGD）：按边权频率采样正边，再为每条正边抽取若干负样本近似排斥项。

一次随机更新

正边 (i,j), vᵢⱼ 高：    yᵢ ←──→ yⱼ  吸引
随机非边 (i,k)：        yᵢ ──←  yₖ  排斥
随机非边 (i,l)：        yᵢ ──←  yₗ  排斥

重复多个 epoch，边采样频率与 vᵢⱼ 相关

text

负采样让算法可扩展，也引入随机性。二维图是一个随机优化结果，不是图的唯一精确解；多种子和重采样仍是必需诊断。

09 不调用 UMAP，写出可检查的模糊图#

下面用 scikit-learn 只做近邻搜索，手动计算 $\rho_i$ 、 $\sigma_i$ 、有向边权和模糊并集。它省略了重复点插值、局部连通度非整数处理与近似近邻优化，适合小数据验证公式：

import numpy as np
from sklearn.neighbors import NearestNeighbors

def _solve_sigma(distances, rho, target, steps=64):
    lo, hi = 1e-6, 1.0

    def mass(sigma):
        return np.exp(-np.maximum(0.0, distances - rho) / sigma).sum()

    while mass(hi) < target:
        hi *= 2.0
    for _ in range(steps):
        mid = (lo + hi) / 2.0
        if mass(mid) < target:
            lo = mid
        else:
            hi = mid
    return (lo + hi) / 2.0

def fuzzy_knn_graph(X, n_neighbors=15):
    X = np.asarray(X, dtype=float)                         # [N,D]
    n = len(X)
    if not 2 <= n_neighbors < n:
        raise ValueError('需要 2 <= n_neighbors < N')

    search = NearestNeighbors(n_neighbors=n_neighbors + 1)
    distances, indices = search.fit(X).kneighbors(X)      # [N,K+1]
    distances, indices = distances[:, 1:], indices[:, 1:] # 排除自身

    directed = np.zeros((n, n))                           # 教学用稠密矩阵
    rhos = np.zeros(n)
    sigmas = np.zeros(n)
    target = np.log2(n_neighbors)

    for i in range(n):
        positive = distances[i][distances[i] > 0]
        rhos[i] = positive[0] if len(positive) else 0.0
        sigmas[i] = _solve_sigma(distances[i], rhos[i], target)
        weights = np.exp(
            -np.maximum(0.0, distances[i] - rhos[i]) / sigmas[i]
        )
        directed[i, indices[i]] = weights

    graph = directed + directed.T - directed * directed.T
    np.fill_diagonal(graph, 0.0)
    assert np.all((0.0 <= graph) & (graph <= 1.0))
    return graph, indices, distances, rhos, sigmas

python

官方实现将图保存为稀疏矩阵，并使用近邻下降（Nearest Neighbor Descent，NN-descent）等近似近邻机制。教学版的 $N\times N$ 稠密数组只适合几十或几百个点，不能用于生产规模。

10 用 UMAP 0.5.8 当前官方 API 落地#

官方 UMAP API ↗ 来自 umap-learn 包，使用 scikit-learn 风格接口：

import numpy as np
import umap
from sklearn.manifold import trustworthiness
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)           # [N,D]

reducer = umap.UMAP(
    n_neighbors=15,
    n_components=2,
    metric='euclidean',
    min_dist=0.1,
    spread=1.0,
    init='spectral',
    n_epochs=None,              # 让实现按数据规模选择
    learning_rate=1.0,
    low_memory=True,
    random_state=42,
    transform_seed=42,
)
Y_train = reducer.fit_transform(X_train_scaled)          # [N,2]

assert reducer.embedding_.shape == (len(X_train), 2)
assert reducer.graph_.shape == (len(X_train), len(X_train))
assert np.isfinite(Y_train).all()
print(trustworthiness(X_train_scaled, Y_train, n_neighbors=15))

X_valid_scaled = scaler.transform(X_valid)               # [Q,D]
Y_valid = reducer.transform(X_valid_scaled)               # [Q,2]
assert Y_valid.shape == (len(X_valid), 2)

python

metric 定义原空间的“近”。文本嵌入常需比较 cosine，非负计数、二元向量、地理坐标和混合特征也可能需要不同度量；不要把默认欧氏距离当无假设选择。

设置 random_state 有利于复现，但官方复现说明指出，多线程随机优化的执行顺序本身可能不确定；要求精确复现通常会牺牲并行速度。探索阶段可使用并行，最终报告固定种子、线程策略、版本与坐标产物。

11 transform 如何安放新样本？#

对新样本 $X_{new}\in\mathbb R^{Q\times D}$ ，UMAP 大致执行：

在训练样本中寻找近邻；
用训练时的局部尺度形成新点到旧点的边权；
由旧邻居低维坐标初始化新点；
保持训练嵌入不变，对新点坐标做有限优化。

训练图：   A────B────C
                 ╲
新点 x：          x  在高维最像 B、C

低维：     yA──yB──yC
                 ╲
                 yx  由 B、C 的旧坐标定位，旧点不重排

text

这使 UMAP 能进入管线，但不消除泄漏：若先在全部数据上 fit_transform，验证样本已经改变近邻图和训练坐标。正确流程是在每个训练折内拟合缩放器与 UMAP，再对验证折调用 transform。

若新点到训练邻居的距离远超训练分布，仍会被迫分给“最不远”的旧邻居。上线时应监控新点最近邻距离、图边权总量和特征漂移，并设置拒绝或回退逻辑。

12 n_neighbors 与 min_dist 怎样联合选择？#

`n_neighbors`	`min_dist`	常见视觉倾向	主要风险
小	小	很紧的微小岛与细丝	放大噪声、连通性差
小	大	局部片段分散展开	宏观关系仍断裂
大	小	较大尺度连续，但局部仍可压成团	跨群体错误连边
大	大	更平滑、均匀、强调整体轮廓	细粒度类别被抹平

可靠选择不应只追求“图更漂亮”。建议扫描二维网格，同时记录：

原空间 K 近邻召回率和低维信任度；
高维模糊图的连通分量、度分布与边稳定性；
不同种子/重采样后近邻重合率与 Procrustes 对齐误差；
若用于下游任务，严格交叉验证后的分数与方差；
拟合、transform 时间，峰值内存和模型产物大小。

n_components 不必等于 2。可视化用 2 或 3 维；下游表示可验证更高维，但维数越高越不能凭二维直觉选择参数。

13 常见错误与最短调试路径#

安装错包：PyPI 包名是 umap-learn，导入名是 umap；不要误装另一个同名包。
全数据拟合造成泄漏：将“缩放 → UMAP → 下游模型”放入训练折，验证折只调用已拟合变换。
把颜色标签传给 fit_transform：监督 UMAP 会让标签参与图构造；若目标是无监督探索，不要传 y。
认为图轴有固定语义：坐标可旋转、反射、缩放；解释邻域，不解释“横轴增加代表什么”。
把点团当真实类别：回到原空间检查组内距离、可分性、重采样稳定性和领域意义。
只固定种子却改变线程与版本：记录 umap-learn、NumPy、Numba、scikit-learn 版本及线程设置。
忽略断开顶点警告：检查度为 0 的点、最大距离、重复点和 disconnection_distance，不要只隐藏警告。
对稀疏高维数据先转稠密：会瞬间耗尽内存；保留稀疏表示并选择兼容度量与预降维。
相信 inverse_transform 精确重构：低维压缩本来就丢信息，逆变换只是近似，应报告重构误差和适用范围。

最短调试路径：验证输入与距离 → 检查近邻和图连通性 → 扫 $K$ /min_dist 与种子 → 检查训练外距离 → 最后才解释颜色和团块。

14 失败场景与相近方法边界#

方法	高维目标	优化/求解	训练外能力与主要边界
PCA	全局线性重构与方差	SVD/特征分解	精确线性变换；不能展开非线性流形
Isomap	图测地距离	最短路 + 经典 MDS	近似外推；怕短路和断图
LLE	局部线性重构权重	局部线性系统 + 谱分解	局部外推；怕病态邻域
t-SNE	高低维邻域联合概率	KL + 吸引/排斥优化	标准形式无变换；局部图强
UMAP	模糊近邻图边权	交叉熵 + 负采样 SGD	有近似变换；结果依赖图与随机优化
自编码器	参数化重构或自定义目标	神经网络反向传播	快速前向；需更多数据与训练设计

UMAP 仍假设局部近邻有意义，且数据可由某种局部流形结构近似。离散组合对象、相交流形、强批次效应、极不均匀采样、严重噪声或领域距离错误都会让模糊图先天失真。它不是聚类器，也不会自动给坐标赋予可解释因子。

15 今天真正需要记住什么？#

UMAP 先为每个点用 $\rho_i$ 保证局部连通，再用 $\sigma_i$ 把 K 近邻距离变成有向模糊边权；通过模糊并集合并双向关系，得到稀疏高维图。低维用重尾边权和交叉熵匹配这张图，正边吸引、负采样排斥。n_neighbors 控制观察尺度，min_dist 控制低维打包；transform 提供有边界的训练外定位，而非对分布外样本的保证。

16 思考题与小练习#

延续手算例，把 $\sigma_i$ 从 0.3 增到 0.6，重新计算三条有向边权。哪条边变化比例最大？这说明局部尺度怎样影响远邻？
构造两个月牙外加 5% 均匀噪声，扫描 n_neighbors={5,15,50} 与 min_dist={0.0,0.3,0.8}，同时报告图连通分量和信任度，不看颜色先判断哪些结构稳定。
将数据按时间划分，只在早期数据上拟合 UMAP，对晚期数据 transform。比较新点最近邻距离与低维位置，设计一个“超出训练流形则拒绝解释”的阈值规则。

17 下一篇预告#

PCA、Isomap、LLE、t-SNE 与 UMAP 都在无标签条件下寻找表示，但它们没有通过任务误差学习多层特征。下一阶段将进入神经网络：先从一个人工神经元讲清线性变换、激活函数和计算图，再追踪多层感知机怎样用反向传播把输出误差分配到每一层参数。

01 t-SNE 已能看邻居，为什么还要换成图？#

02 完整数据流与张量形状#

03 每个点为什么先减去局部半径 ρᵢ？#

04 σᵢ 怎样让每个局部邻域可比较？#

05 四条距离怎样手算有向边权？#

06 模糊并集怎样把局部视角拼成全局图？#

07 低维边权怎样由 min_dist 控制？#

08 交叉熵怎样同时吸引边与排斥非边？#

09 不调用 UMAP，写出可检查的模糊图#

10 用 UMAP 0.5.8 当前官方 API 落地#

11 transform 如何安放新样本？#

12 n_neighbors 与 min_dist 怎样联合选择？#

13 常见错误与最短调试路径#

14 失败场景与相近方法边界#

15 今天真正需要记住什么？#

16 思考题与小练习#

相关工作#

17 下一篇预告#