高效降维的分层最近邻图嵌入方法

to preserve the global distances among all samples in thedata.Whereas more recent popular methods such as t-SNE [35,36], LargeVis [33], and UMAP [26,30] seek to ad-ditionally preserve the local structure e.g. by preserving thedistance relations in the k-neighborhood of each data sam-ple. To retain such relations, these methods generally haveto solve an optimization problem with the goal of matchingthe distribution of distances in the target space with theirdistribution in the original space. For instance, t-SNE min-imizes the Kullback-Leibler divergence between distribu-tions of k-nearest neighbor (k-NN) distances fitted in thehigh and low-dimensional space. Similarly, the more recentmethod UMAP optimizes the embedding in the target spacewith the goal of preserving the 1-skeleton of fuzzy simpli-cial sets constructed in the original space. Such optimiza-tions are computationally expensive in nature and account3360用于高效降维的分层最近邻图嵌入0M. Saquib Sarfraz � 1, 2, Marios Koulakis � 1, Constantin Seibold 1, Rainer Stiefelhagen 101 卡尔斯鲁厄理工学院，2 梅赛德斯-奔驰技术创新0� 相等贡献0摘要0降维对于可视化和预处理高维数据以进行机器学习至关重要。我们介绍了一种基于原始空间中构建的1-最近邻图的层次结构的新方法，该方法用于在多个级别上保留数据分布的分组属性。该方法的核心是一种无需优化的投影，其在性能和可视化质量上与最新版本的t-SNE和UMAP相媲美，同时运行时间快一个数量级。此外，它的可解释机制、投影新数据的能力以及可视化中数据簇的自然分离使其成为一种通用的无监督降维技术。在本文中，我们论证了所提出方法的合理性，并在样本数量从1K到11M，维度从28到16K的多个数据集上进行了评估。我们使用多个指标和目标维度与其他最先进的方法进行比较，突出了其效率和性能。代码可在https://github.com/koulakis/h-nne上获得。01.引言0降维技术现在在许多科学领域中越来越广泛地使用，并且必须应对不断增长的现实世界数据集的规模。它在可视化和处理高维数据方面起着重要作用。当前研究的重点是寻找既适用于大规模数据又能在较低维度中保留数据结构的无监督算法。其中大部分尝试通过在目标空间中优化成对距离来保留数据的局部或全局结构。关于当前降维技术的两个主要方向可以通过如何保留这种局部或全局邻域的距离来确定。例如，PCA [15]、MDS[18]和Sammom映射[31]等方法试图保留数据中所有样本之间的全局距离。而最近流行的方法，如t-SNE [35, 36]、LargeVis [33]和UMAP [26,30]，则试图额外保留局部结构，例如通过保持每个数据样本的k-邻域中的距离关系。为了保留这样的关系，这些方法通常必须解决一个优化问题，目标是使目标空间中的距离分布与原始空间中的距离分布相匹配。例如，t-SNE最小化高维空间中拟合的k-最近邻（k-NN）距离的分布与低维空间中的分布之间的Kullback-Leibler散度。类似地，最近的方法UMAP通过优化目标空间中的嵌入来保留在原始空间中构建的模糊单纯集的1-骨架。这样的优化在性质上是计算昂贵的，并且占据了大量的计算时间。0图1.整个ImageNet数据集的可视化。降维方法的速度和嵌入质量。3370对于这些算法的主要复杂性，限制了它们在大规模数据集上的运行性能。在本文中，我们提出了一种不同的方法，不再依赖于点级别的优化，而是捕捉数据的多阶段神经网络属性，并使用这些属性以一种简单的算法方式对点进行投影。构建这种结构的主要工具是最近邻图（NNGs），这些图已经得到了很好的研究。在[12]中，Epstein等人表明，对于一个1-NNG，当边缘放置在单调逻辑网格上时，其NN关系在低维空间中得到很好的保留。将NNG嵌入到l维网格中的一种有效策略是分别嵌入图的各个组件。NNG的连通分量捕捉了样本的聚类。在先前获得的连通分量上递归地构建1-NNG，可以提供样本如何在连续级别上逐步合并在一起的层次视图。将每个连通分量视为层次结构中的一个节点，可以确定这些节点及其关联样本如何从底部到顶部逐步合并在一起的完整路径。这样的层次节点图以高维空间中的局部邻域如何分布的方式提供了数据的视图。在对高维数据进行廉价的初步投影到所需的低维空间之后，我们可以使用目标空间中的原始层次节点图直接强制执行局部结构。我们通过一种快速的自上而下的递归方法来实现这一点，通过将样本的聚类从顶层开始向这些节点移动，逐渐向下移动到达底部，即更细的级别。由于我们的提议是基于获取基于Hierarchical1-NearestNeighbor图的嵌入，因此我们将该方法称为h-NNE。图1显示了对完整ImageNet数据集的ResNet-50特征进行嵌入的示例。如图所示，与当前最先进的方法相比，我们不仅实现了具有竞争力的嵌入质量（由可信度指标表示），而且运行时间显著更快。总之，我们的主要贡献是一种不依赖于昂贵的优化方法的替代降维和可视化方法。这使得它的操作速度比现有方法快一个数量级，无需超参数调整，并且保持类似的性能。在下面的章节中，在深入讨论所提出的方法之前，我们将讨论相关工作，以将其置于上下文中，并在多个数据集的实验和比较中进行评估。02. 相关工作0目前大部分先进的无监督降维技术旨在保持投影流形中的局部成对距离。Hinton和0Roweis[14]引入了随机邻域嵌入（SNE），通过将较低维度中的条件概率（欧几里得距离转换为相似性）与较高维度中的概率相似来创建低维嵌入。这是通过对样本拟合高斯分布并将其与较低维度中的分布匹配来实现的。在SNE的基础上，t分布随机邻域嵌入（t-SNE）[36]用长尾t分布替代了低维空间中使用的高斯分布。t-SNE在计算上是非常昂贵的。t-SNE的后续工作，如Barnes-Hut t-SNE [35]，viSNE[2]，FIt-SNE [20, 21]和opt-SNE[6]，进一步改进了t-SNE，使其能够更快地收敛并更好地适应更大的数据集。许多后续工作都沿着同样的方向进行。例如，LargeVis [33]和当前的先进方法，如UMAP[26]和PaCMAP[38]，都有基于t-SNE的目标函数。这些方法侧重于提高效率和保留更多的全局结构和局部结构。这通常是通过构建和操作加权图来实现的。通常在原始空间中构建k-NN图，然后用它来在初步投影空间中强制每个样本点的k-邻域。所有当前的先进方法，如t-SNE [36]，LargeVis [33]，UMAP[26]和PaCMAP[38]，在这个基本过程上都有很大的关联性。McInnes等人在[26]中提供了更详细的关于这个k-NN图优化视角的讨论，比较了t-SNE、LargeVis和UMAP在这个背景下的优化方程。这些技术之间的差异来自于用于优化投影嵌入的目标函数的变化。例如，优化的一个常见目标是将处于相同k-邻域的样本吸引在一起，并将其与远离的样本分开。如果从k-NN图布局的角度来看，这相当于定义和使用沿边施加的一组吸引力和沿顶点施加的一组排斥力。这是一个非凸优化问题，通过通过基于梯度下降的学习仔细改变吸引力和排斥力来实现收敛。实际上，它是通过使用k-邻域中的样本作为当前数据点的正样本，并从其余样本中采样负样本进行对比学习。为了降低成本，UMAP采用负采样来选择一部分样本用于排斥力，而最近的PaCMAP则定义了高权重的近对和中近对来帮助保留更多的结构。类似的策略也被三元组约束方法（如TriMap[1]）所使用，它使用高维表示中的一组精心选择的三元组来初始化低维PCA嵌入。然后，通过修改这个嵌入来实现。最后，t-SNE和UMAP方法具有3380提取最近邻0基于图的层次结构0强制聚类0一致性0在下一个层次级别上重复01-最近邻图嵌入初步投影0图2. h-NNE投影方法的概述。0它们的参数化版本[30,34]中，它们使用类似的目标函数训练MLP。参数化方法简化了新数据点的投影。这些方法中的另一个重要考虑因素是它们对用户提供的超参数的依赖。除了指定构建图的邻居数k之外，还需要指定其他几个与优化特定参数有关的参数。我们的方法与这些当前方法相比是一个重大转变。我们不是构建加权的k-NN图，而是通过递归地构建具有静态边链接的1-NN图来创建一个聚类层次结构。然后，我们使用这个层次结构在较低维度空间中移动样本，而无需使用基于梯度下降的优化。同时，这也消除了对特定超参数的依赖。这为我们提供了一种高效且可扩展的降维方法。03. h-NNE算法0我们的投影算法包括三个主要步骤：基于1-NNG构建树层次结构，使用近似的PCA计算初步投影，并根据构建的树调整投影点位置。可以使用可选的膨胀步骤增强调整后的投影点位置，以改善可视化效果。在接下来的几节中，我们将详细介绍每个步骤，并提供一些证据证明它们的有效性。图2概述了该方法。03.1.基于最近邻图的层次结构0几种投影方法的起点是定义一个结构，该结构编码了点的相对位置，然后以保持该结构的方式进行投影。例如，UMAP依赖于编码近邻关系的加权图。0t-SNE使用基于最近邻关系的一组局部分布，而我们的方法则旨在捕捉点的局部邻居属性和全局聚类属性的结构。为了以较低的计算成本实现这一目标，并同时保持方法简单和无参数，我们基于1-NN关系构建了一个层次结构。这种方法受到了最近邻图的经典工作（例如[12]）和FINCH聚类方法[32]的启发。0假设我们的数据集是X = {xi}i ≤ N，其中xi ∈RD。构建层次结构的第一步是构建NNG（X），它是一个将每个点连接到其最近邻的有向图。可以使用任何最近邻或近似最近邻算法来执行此操作。接下来，我们确定NNG（X）的连通分量，记为{NNGi（X）}i ≤g0，它们形成具有所有边指向单个双根的有向图。对于每个图NNGi（X），我们计算其质心c（0）i = 1 g0 �0x ∈ NNGi（X）x，从而形成一个新的点集C（0）=0{c（0）i}i ≤g0。然后，我们重复相同的计算过程，计算NNG（C（0））及其组件的质心，得到C（1），并继续直到达到至少包含三个点的最小质心集C（l）。NNG层次结（X）= � �0i ≤ l0其中每个质心与其对应的NNG组件的每个点相连。图3显示了此迭代过程的单个步骤。0与k >1的k-NNG相比，1-NNG的大小相当小，这使它们非常适合构建具有多个层次的细粒度层次结构。3390一个经验法则是，每一步中点的数量平均减少0.31倍。这可以从以下定理中提取出来，假设至少在局部上，较高层次的数据和质心是均匀分布的。尽管很难验证该假设的有效性，但我们注意到该规则适用于所有观察到的数据集。0定理1（Eppstein，Paterson，Yao[12]）。在单位正方形中的均匀随机点集X的NNG（X）中的组件数的期望值渐近地接近于0.31|X|。03.2.初步线性嵌入0尽管聚类树结构足以在不同层次上保持原始数据集的分区，但需要确定图组件NNGi（X）和NNGi（C（k））中的点的相对位置。可以使用随机投影，甚至从随机点开始，但是使用一些有意义的初始投影可以在保持分数和视觉质量方面获得额外的收益。我们选择使用PCA并加速其计算，我们使用预定义层次的质心C（i）来估计数据的协方差矩阵。也可以对原始点集X进行子采样，但我们注意到使用质心可以增加稳定性并避免初始化在运行之间的偏差。我们通过实验证明，这种主成分的近似产生的结果与在完整数据上使用PCA相当。我们在补充材料中提供了这个分析。我们选择质心的层次是层次结构中最低的层次，使得所有上层的基数小于1000。这意味着如果数据集很小，即对于所有i，|C（i）| <1000，则PCA将直接在X上计算。这种近似的优点是可以将PCA的计算成本从O（N∙D^2）降低到O（D^2），其中N用1000的因子替换。一旦计算出PCA的特征向量，例如在矩阵V中，那么X和所有质心Ci的所有点都可以通过与这个单一共享矩阵相乘来从较高的维度D投影到较低的维度d。我们用波浪符上标表示这些点的投影，例如˜c（k）i表示质心的投影，˜xi表示数据集的点的投影。0图 3. 构建 T NNG ( X ) 中的归纳步骤。所有 1-NNG组件都被映射到它们的质心，这些质心是下一步的基础。03.3. 分层点移动03 d ( l ) i 。这个距离保证了属于相邻质心的点不会形成跨质心的最近邻关系，从而保持了 T NNG ( X )中编码的分离。图 4 说明了这个过程。一旦 ˜ C ( l − 1) 的点被放置在 ˜ C ( l ) 的点周围，我们使用它们将 ˜C ( l − 2) 的点围绕它们平移，与之前的方式相同。这个步骤重复进行，直到达到形成最终投影的 X级别。还有一个问题我们需要解决。即使半径 10这是算法的核心部分，目标是按照树 T NNG ( X ) 的方式分层移动点，使其占据投影空间R d ，并在所有级别上保持 1-NN关系。一旦我们对所有点和质心进行了初步投影，我们从 C ( l ) 开始，并考虑其投影质心{ ˜ c ( l ) i } i ≤ g l 。这些质心形成了一个 Voronoi 图0引理 1. 给定以质心为中心的 d-球 B ( c ( k ) i , r ) ，属于 c ( k ) i 的所有点在使用 h-03 d ( l ) i可以保证一步中相邻质心的分离，但可能会出现在迭代的后续步骤中移动的点穿过该 d-球的边界的情况（再次参见图 4）。下面我们计算一个缩小系数，使得该半径仍然对后续步骤中移动的点保持这种保证。05 ，位于 B ( c ( k ) i , r ) 内。((.34003 sr ，因为 d ( c ( k ) 1 ,  c ( k ) 2 ) = 2 sr。这意味着这些点中任何一个到 c ( k ) i 的最大距离是 sr  + 20证明。假设在h-NNE的每一步中都使用因子 s来减小计算出的半径。在第一步中，所有较低级别的质心都被平移和缩放，使它们位于半径为 sr 的 d-球内。下一步的最坏情况是有两个互对点 c ( k ) 1 , c ( k ) 2是最近邻。在这种情况下，下一步属于 c ( k ) 1 的点将被放置在以它为中心的d-球内，半径为 20�03 s 2 r。通过递归计算这些最坏情况，我们得到对于算法的无限步骤，最远的点将被放置在距离最多03 ) j sj +1 r =  sr�03 s ) j  = sr03 s (1)03 s  ≤  r，由此得到0因此，为了使所有点都位于原始球 B ( c ( k ) i , r ) 内，我们需要 sr0那就是 ≤ 30上述界限保证，如果我们将新点放置在半径为 303 = 0 . 2 乘以最近邻距离的距离，那么点的最近邻将受限于 NNG层次结构中形成的聚类。在实践中，互对点的最坏情况并不经常发生。即使在点更密集的低维空间中，也可以使用 1-NN 距离的 1 3 或更大的半径，而不会明显降低 k-NN保持度。这对于可视化特别有用，因为它可以帮助使图在平面或三维空间上更加分散。用于可视化目的的点聚类膨胀。对于所有点使用单一线性投影可能导致点聚类混乱，当它们与用于投影的全局主成分不太对齐时。尽管这对性能影响很小，但会导致可视化效果较差，其中包含来自初始投影的伪影。为了增强图像的形状而不牺牲速度并且不添加新的超参数，我们添加了通过六个局部旋转来膨胀可能被挤压的点聚类的选项，这些旋转角度在区间 [0 , π02]，然后进行缩放和逆旋转。这样可以得到一个几乎等同于将云旋转到其PCA主成分、缩放它们，然后再旋转回原始方向的输出，但计算成本要低得多。投影新点。可以通过重复相同的算法来执行新点的投影，只需针对单个点并仅下降到层次结构的第二层。如果x是新点，我们0图4. MNIST中顶层质心的Voronoi单元。圆的半径为103与最近邻的距离，点通过缩小因子为1的因子进行投影03.可以注意到最终的点穿过了圆的边界。然而，数据在2D中的密度导致了没有严重重叠的情况。0首先，使用我们选择的ANN算法在C(1)中识别最近的质心。然后，通过缩放、应用预计算的PCA和归一化点的位置来转换点，相对于相应的半径。如果在原始投影中使用了点聚类膨胀，则在最终归一化步骤之前还要执行相应的旋转和缩放。03.4.计算复杂性0h-NNE的复杂性由三个步骤组成：构建T_NNG(X)树、预处理的PCA投影和分层点转换。由于NNG图的每个组件至少包含两个点，T_NNG(X)的高度为O(logN)。这意味着，假设计算近似1-NN至少需要O(N)的时间，无论使用哪种方法，总复杂度等于单个近似最近邻(ANN)步骤的复杂度，包括对数据集的任何准备工作(例如构建索引树)和对数据集中所有点的查询。我们用O(ANN(N,D))表示ANN的复杂度。PCA投影步骤需要O(Dd^2)，假设我们将使用的样本数固定为一个常数。最后，点转换步骤的复杂度为O(NlogNd + ANN(N,d))，这是因为树的对数高度、groupby操作的使用以及我们需要计算最近邻来找到扩展聚类的d-球的半径。因此，总体而言，该算法的复杂度为O(ANN(N,D) + Dd^2 + NlogNd)。ANN(N)的复杂度不容易计算。j3410Higgs [3] Google News [27] COIL 20 [28] CIFAR-10 [17] F-MNIST [39] ImageNet [10] BBT [5] Buffy [5] MNIST [19, 23]0类型 传感器 文本 对象 视频 数字 类别数 2-20 10 10 1000 5 6 10 样本数 1100万 300万 1440 6万 7万 120万 20万 20.6万 7万 800万 维度 28 300 16384 3072 784 20482048 2048 784 784 特征 测量 Word2Vec 像素 像素 像素 ResNet50 ResNet50 ResNet50 像素 像素0表1.实验中使用的不同大小的数据集，样本数从1400到1100万，维度从28到16384。0最坏情况下，使用线性搜索时，复杂度可能为N^2。一些旧的精确方法[7,29]在复杂度上达到了NlogN的水平，但不幸的是在D上呈指数级增长。近似方法，如HNSW [24]，NNDescent[11]和ScaNN[13]在真实数据集上表现良好，但只有实验证据，没有复杂度界限。在我们目前的实现中，我们使用了PyNNDescent[25]，它是NNDescent的调整版本。NNDescent的经验复杂度对于具有小内在维度的数据集约为O(N^1.14)。最后，一项有趣的分析[4]提供了NNDescent在合成数据集中达到O(N^2)和O(NlogN)复杂度的情况。04. 实验0我们在不同大小的多样化数据集上展示了h-NNE的性能。这些数据集涵盖了传感器数据、文本、数字、视频和物体等领域。我们首先介绍数据集和性能指标，然后对所提出的方法与当前最先进算法进行了全面比较。04.1. 评估0数据集。表1总结了数据集。除了一些常用数据集外，我们还包括一些用于测试大小和维度的数据集。总共，我们使用了9个数据集，样本数量从1440到1100万，维度从28到16384。我们在补充材料中提供了每个数据集的更多细节。指标。在降维中，一个经过深入研究的问题是如何平衡局部和全局结构的保持[9,16]。像t-SNE这样的方法以其保持局部结构的特性而闻名。最近的方法，如0h-NNE t-SNE fIt-SNE UMAP PaCMAP0COIL20 0.994 0.998 0.998 0.996 0.985 MNIST 0.983 0.9890.991 0.958 0.950 F-MNIST 0.981 0.991 0.992 0.977 0.966CIFAR10 0.907 0.927 0.932 0.829 0.818 BBT 0.982 0.99 0.990.966 0.958 Buffy 0.976 0.988 0.99 0.954 0.952 ImageNet0.928 − 0.956 0.895 0.822 HIGGS 0.849 − 0.979 0.909 0.899MNIST 8M 0.967 − 0.956 − 0.9450表2. 局部结构保持：可信度0UMAP [26, 30]和PaCMAP[38]都致力于保持局部和全局结构。因此，我们在这两个方面评估所有方法在考虑的数据集上的表现。0局部结构保持：通常使用留一交叉验证和k-NN分类器来衡量。k-NN准确率是一种标准的降维方法评估方法，它衡量基于邻域的分类准确率是否保持接近原始空间中的准确率。与之前的研究一样，我们使用10折分层交叉验证来测量不同k值下的k-NN准确率。另一个与局部结构保持密切相关的指标是可信度。可信度[37]对于每个点，通过其在嵌入空间中的排名超过k的数量来惩罚其每个最近邻。可信度定义为0T ( k ) = 1 − 20nk (2 n  −  3 k  −  1)0n �0i =10�0max(0 ,  ( r ( i, j ) − k ))0并且在0到1之间进行缩放，其中1表示更可信赖。我们使用scikit-learn的实现，其中k = 5。0全局结构保持：为了衡量全局结构即原始空间中类中心之间的相对位置的保持程度，Wang等人[38]提出了一种度量方法，该方法计算质心并形成所有可能的三元组。度量指标三元组质心准确度衡量了在高维和低维空间中，百分之多少的三元组的相对距离保持了它们的相对顺序。0h-NNE t-SNE fIt-SNE UMAP PaCMAP0COIL20 0.799 0.778 0.769 0.705 0.758 MNIST 0.671 0.7110.748 0.804 0.713 F-MNIST 0.925 0.784 0.848 0.848 0.866CIFAR10 0.911 0.921 0.929 0.927 0.932 BBT 0.644 0.6000.711 0.556 0.666 Buffy 0.857 0.571 0.543 0.657 0.704ImageNet 0.604 − 0.639 0.605 0.646 MNIST 8M 0.774 −0.744 − 0.7350表3. 全局结构保持：质心三元组准确度3420图5. 不同维度的投影：2、4、8、32和64维的KNN准确率。04.2. 与最先进技术的比较0我们与目前最佳的无监督降维和可视化方法进行比较。t-SNE[36]由于其显著的局部结构保持特性和长期的后续工作，是2D可视化的默认选择。然而，它的计算开销很大。我们在比较中使用了其优化版本Barnes-Hut t-SNE[35]。由于这仍然不能轻松扩展到超过200K大小的数据，我们还包括了一个更快和可扩展的变体FFt-acceleratedInterpolation-based t-SNE (FIt-SNE)[22]。FIt-SNE是目前速度和性能最好的t-SNE方法。值得注意的是，t-SNE的运行时间随着维度的增加呈指数增长，虽然FIt-SNE原则上可以支持更高的维度，但官方实现不支持。在其他最近的方法中，我们包括了流行的UMAP[26]和最近的方法PaCMAP[38]，它建立在t-SNE和UMAP的优势之上。表2提供了所有方法在数据集上的可信度得分。t-SNE和FIt-SNE在保持局部结构方面都非常好。h-NNE在保持局部结构方面与t-SNE方法非常接近。UMAP和PaCMAP的表现与h-NNE相当，稍微差一些。我们在补充材料中提供了k-NN分类器准确率和比较。根据表3中的全局结构保持指标，h-NNE嵌入的质心三元组准确度在所有数据集上都相当。由于这些指标需要数据集的真实标签，因此无法计算GoogleNews数据集的结果。同样，由于HIGGS只有两个类别，无法评估其质心三元组指标。这些结果表明，总体而言，h-NNE在保持局部和全局结构方面与这些当前方法具有很高的竞争力。不同维度的投影。对于h-NNE，目标维度没有限制。图5展示了不同维度的投影。对于这个实验，我们包括了7个数据集，并与UMAP和0由于只有这些方法支持更高维度，因此我们选择了PaCMAP。在不同数据集上的k-NN（k =1）准确率显示，当维度增加时，h-NNE的性能呈现出一致的上升趋势。0计算性能比较。所有数据集上的基准测试是在一台配备AMD Ryzen Threadripper 2990X 32核处理器和128 GBRAM的工作站上进行的。表4提供了每个算法的总运行时间的比较。如预期的，t-SNE无法在大规模数据上进行扩展，UMAP在800万维度的数据上内存不足。PaCMAP和FIt-SNE（t-SNE的快速替代方法，是一个高度优化和并行化的C++实现）都在所有数据集上运行。在速度方面，h-NNE具有明显的优势，并且在数据集的规模上具有良好的扩展性，大型数据集上的加速比超过十倍。我们方法的时间效率来自于方法本身（即不依赖于昂贵的基于梯度下降的嵌入优化）并且可以通过类似的并行化实现进一步加速。在HIGGS数据集上，h-NNE花费约13分钟，而FIt-SNE花费近3小时，UMAP和PaCMAP花费4-5小时。由于所有这些现有方法都需要构建加权k-NN图，并要求存储和访问它们的优化所需的成对距离浮点数，它们的内存需求非常高。例如，与h-NNE相反，这些方法中的任何一个都无法在具有64 GBRAM的机器上运行百万级别的数据。有关计算复杂性的更多细节，请参阅第3.4节。0探索无标签数据。我们看到h-NNE在探索无标签数据方面具有优势，因为它具有分层的特性。一方面，数据的不同聚类在视觉上是分离的，另一方面，我们在层次结构的所有层级上生成了聚类标签。在图6中，我们使用这些聚类标签对GoogleNews数据集的投影进行着色，并展示了一个缩放过程，其中我们隔离了一个相似词向量的聚类。0局限性。我们算法的一个局限性是它依赖于我们构建的分层NNG结构。这3430数据集 #S Dim h-NNE (我们的) t-SNE UMAP PaCMAP FIt-SNE0COIL20 1440 16384 00:01 00:08 00:18 00:02 00:07 MNIST 70K 784 00:09 05:28 00:54 00:3701:24 F-MNIST 70K 784 00:07 05:37 00:58 00:38 01:20 CIFAR10 60K 3072 00:14 08:35 01:0200:39 02:24 BBT 200K 2048 00:58 57:32 04:08 01:38 04:50 Buffy 206K 2048 00:50 01:01:0004:18 01:42 05:07 Google News 3M 300 03:34 - 01:19:05 01:14:04 52:16 ImageNet 1.2M2048 05:11 - 49:10 30:20 39:29 HIGGS 11M 28 12:25 - 03:53:04 05:07:34 02:49:280MNIST 8M 8M 784 21:52 - - 03:08:47 02:56:140框架 Python Python Python Python C++0h-NNE的运行时间比较：我们报告运行时间以HH:MM:SS和MM:SS表示。-表示内存不足。0图6. 无标签GoogleNews嵌入的h-NNE可视化。在左侧，我们可以看到层次结构的顶层上的聚类标签。在中间，我们放大到一个位置，并使用较早层次的聚类标签隔离一个小的聚类。0结构聚类将数据在每个层级上进行聚类，最终的投影是基于这些聚类的。这意味着在这些聚类中可能发生的任何错误都会直接转化为全局结构的质量降低和点的定位的质量降低。好的一面是，这些分类错误可以反映原始空间中类别的差异较小，这是使用h-NNE来检查为数据集生成的特征质量时所期望的属性。0第二个限制是我们的方法在设计上不保留原始空间的拓扑结构。我们使用1-NN来构建层次结构意味着只有当某个形状同胚于S1时，它才会被保留，前提是它包含在树的最低层的单个1-NN图组件中，并且PCA投影保持其圆形形式。由于1-NNG组件的大小通常很小，这种情况很少发生。为了消除这个限制，需要保留更多数据的局部属性。这在更高维度上是可能的，但在非常低的维度（如2或3）上，它与捕获更全局结构的分层NNG数据分区相冲突。因此，在这种情况下，我们将这个限制视为一种权衡。05. 结论0我们提出了一种高效的降维算法，利用最近邻图及其点的分层分组。使用层次树节点作为初步投影空间中的锚点位置，我们设计了一种快速机制，直接将点移动到嵌入空间中，以保持它们的局部邻域。嵌入过程无需优化，也不依赖于指定超参数。这导致了一种明显快速和可扩展的技术，能够很好地保持数据的全局和局部结构。我们的方法除了速度和质量之外，最大的优势是能够在原始空间和目标空间中同时展示数据的聚类结构。这可能使得在数据的不同层次分组水平上进行分析成为可能。更快的运行时间和提供聚类标签的能力对于可视化大规模未标记数据可能特别有用。我们期望我们的工作能够在合理的时间消耗下实现大规模数据的分析，并希望引起对数据集全局结构性质的基于层次的研究的兴趣。3440参考文献0[1] Ehsan Amid和Manfred K Warmuth. Trimap:使用三元组的大规模降维。arXiv预印本arXiv:1910.00204，2019.20[2] El-ad David Amir, Kara L Davis, Michelle D Tadmor, Erin FSimonds, Jacob H Levine, Sean C Bendall, Daniel K Shenfeld,Smita Krishnaswamy, Garry P Nolan, and Dana Pe'er.visne使得高维单细胞数据可视化，并揭示了白血病的表型异质性。自然生物技术，31(6):545–552, 2013. 20[3] Pierre Baldi, Peter Sadowski和Daniel Whiteson.使用深度学习在高能物理中搜索异域粒子。自然通讯，5(1):1–9,2014. 60[4] Jacob D. Baron和R. W. R. Darling.利用“朋友的朋友”原理的k最近邻近似。arXiv:组合学，2019. 60[5] Martin Bäuml, Makarand Tapaswi和Rainer Stiefelhagen.基于约束的半监督学习用于多媒体数据中的人物识别。在CVPR，2013. 60[6] Anna C Belkina, Christopher O Ciccolella, Rina Anno,Richard Halpert, Josef Spidlen, and Jennifer ESnyder-Cappione.自动优化的t分布随机邻居嵌入参数改进了大数据集的可视化和分析。自然通讯，10(1):1–12, 2019. 20[7] Jon Louis Bentley.用于关联搜索的多维二叉搜索树。Commun.ACM，18(9):509–517，1975年9月。60[8] Jay Boris.一种使用单调逻辑网格的n阶矢量化“最近邻”算法。计算物理学杂志，66(1):1–20, 1986. 20[9] Vin De Silva和Joshua B Tenenbaum.非线性降维中的全局与局部方法。在NIPS，卷15，页705–712，2002. 60[10] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, andLi Fei-Fei. ImageNet:一个大规模的分层图像数据库。在2009年IEEE计算机视觉和模式识别会议上，页码248–255。IEEE，2009. 60[11] Wei Dong, Charikar Moses和Kai Li.用于通用相似度度量的高效k最近邻图构建。在第20届国际万维网会议上的论文集，页码577–586。计算机协会，2011. 60[12] David Eppstein, Michael S Paterson, and F Frances Yao.关于最近邻图的研究。离散与计算几何学，17(3):263–282, 1997.2, 3, 40[13] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, DavidSimcha, Felix Chern和Sanjiv Kumar.使用各向异性矢量量化加速大规模推理。在第37届国际机器学习大会上的论文集，卷119，页3887–3896。PMLR，2020年7月13–18日。60[14] Geoffrey Hinton和Sam T Roweis. 随机邻居嵌入.在NIPS，卷15，页码833-840。Citeseer，2002年。20[15] Harold Hotelling. 将一组统计变量分析为主成分.教育心理学杂志，24(6):417，1933年。10[16] Dmitry Kobak和George C Linderman.初始化对于保持t-sne和umap的全局数据结构至关重要.自然生物技术，39(2):156-157，2021年。60[17] Alex Krizhevsky，Geoffrey Hinton等.从小图像中学习多层特征. 2009年。60[18] Joseph B Kruskal.通过优化对非度量假设的拟合优度进行多维缩放.心理测量学，29(1):1-27，1964年。10[19] Y. LeCun，L. Bottou，Y. Bengio和P. Haffner.基于梯度的学习应用于文档识别. IEEE会议录，1998年。60[20] George C Linderman，Manas Rachh，Jeremy GHoskins，Stefan Steinerberger和Yuval Kluger.用于t分布随机邻域嵌入的高效算法.arXiv预印本arXiv:1712.09005，2017年。20[21] George C Linderman，Manas Rachh，Jeremy GHoskins，Stefan Steinerberger和Yuval Kluger.基于快速插值的t-sne用于改进单细胞rna-seq数据的可视化.自然方法，16(3):243-245，2019年。20[22] George