基于KNN图层次嵌入的大规模高维数据可视化

视觉信息学5（2021）51基于KNN图层次嵌入的大规模高维数据可视化朱海洋a，朱敏峰a，冯颖超杰a，邓才a，胡远哲a，吴世龙b，向阳武c，魏晨a浙江大学CAD CG国家重点实验室，浙江省杭州市b加州大学圣克鲁兹分校，美国旧金山c中国浙江省杭州市杭州电子科技大学ar t i cl e i nf o文章历史记录：收到2021年2021年6月9日接受2021年6月26日在线提供保留字：高维数据可视化KNN图图形可视化a b st ra ct可视化高维数据的内在结构是数据分析中的一项重要任务。在过去的几十年里，已经提出了大量的方法。在所有的解决方案中，一个有前途的方式，使有效的视觉探索是构建一个k-最近邻（KNN）图和可视化的图形在一个低维空间。然而，当应用于大规模数据时，诸如LargeVis的最先进的方法仍然存在两个主要问题：（1）由于成本函数的非凸性，它们可能产生不吸引人的可视化;（2）可视化KNN图仍然是耗时的。在这项工作中，我们提出了一种新的可视化算法，利用多层次表示来实现高质量的图形布局，并采用基于聚类的近似方案来加速KNN图形布局。在各种大规模数据集上的实验表明，与LargeVis相比，我们的方法在KNN图形可视化方面实现了五倍的加速，并产生了美观的可视化结果。版权所有2021作者。由爱思唯尔公司出版我代表浙江大学和浙江大学出版社有限公司这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍可视化高维数据已被证明对医疗健康至关重要（Guo et al. ，2020）、生命科学（Mahfouz et al. ，2015）和社交网络（Kwonet al. ，2018; Chen et al. 通常，该问题表示高维数据集到低维数据集的转换。分析师可以研究数据分布并生成关于输入数据集的假设。在过去的几十年里，人们提出了大量的高维数据可视化方法。t-SNE（Maaten和Hinton，2008）是可视化具有内在非线性结构的高维数据的最成功的非线性方法之一。然而，t-SNE的计算复杂度与数据点的数量成二次方。BH- SNE（Van Der Maaten，2014）构造了一个k-最近邻（KNN）图，并通过四叉树将图可视化为O（N log N）最近，LargeVis（Tang et al. ，2016）构造近似KNN图，然后使用负采样技术（Mikolov et al. ，2013年），这减少了时间*通讯作者。电子邮件地址：hnsyzhy@zju.edu.cn（H.Zhu），minfeng_zhu@zju.edu.cn（M.Zhu），fycj@zju.edu.cn（Y.Feng），dengcai@cad.zju.edu.cn（D.Cai），cadhyz@zju.edu.cn（Y.Hu），swu97@ucsc.edu（S. Wu），wuxy@hdu.edu.cn（X. Wu），chenwei@cad.zju.edu.cn（W.陈）。https://doi.org/10.1016/j.visinf.2021.06.002算法复杂度为O（N）。然而，在可视化大规模高维数据方面仍然存在两个问题。首先，从随机初始化开始，LargeVis可能由于非凸目标函数，特别是对于大规模数据，产生不吸引人的可视化。更好的初始化能够克服LargeVis的非凸性质，并生成美观的可视化。其次，现有算法的计算复杂度仍然不低。而LargeVis（Tang et al. ，2016）大大加快了KNN图形布局过程，但对于大规模数据仍然很耗时。我们基于我们的解决方案的高维数据可视化的KNN图，并针对上述问题，包括一个多层次的表示，以实现美观的结果和梯度近似计划，以加快可视化的构建KNN图的几个改进。特别是，我们提出了一个有效的多层次表示，它构造了一系列的层次图的大小在线性时间递减，不需要额外的权重计算的新的图形。多级表示捕获KNN图的全局结构。以这种方式，通过从粗略图到精细图分配位置来递归地可视化所生成的图的序列，这可以容易地导致适当的布局初始化，从而2468- 502 X/©2021作者。由爱思唯尔公司出版代表浙江大学和浙江大学出版社。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表视觉信息学期刊主页：www.elsevier.com/locate/visinfH. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5152={}∈RR={}∈R我（）−i j2Nqijk=i产生高质量的可视化。此外，与以前单独可视化多级图的方法不同，我们将作为一个组的最好的图的子图。然后，多级表示有利于梯度近似的有效降低，即，一组（从多级结构继承的）数据点的梯度可以由一个代表的通过这种方式，我们将梯度从精细图分配在各种大规模数据集上的实验结果表明，本文提出的高维数据可视化图布局算法比LargeVis算法快5倍，在大规模数据集上的可视化效果更好.主要贡献概括如下：一种具有多级图形布局的高维数据可视化方案，能够产生美观的可视化。梯度近似方案，加速KNN图形布局过程。2. 相关工作作为高维数据分析的基本手段，可视化得到了广泛的研究和应用 （ Sorzano et al. ， 2014; Ma and Macieboski ， 2020; Ma etal. ，2018; Han et al. ，2021年）。现有的成功的可视化方法来自机器学习社区，通常分为两类：线性和非线性方法。线性方法基于线性变换投影高维数据。高维空间中的数据点之间 的 距 离 将 被 保 留 在 低 维 空 间 中 。 主 成 分 分 析 （ PCA ）（Jolliffe，1986）是最流行和最广泛使用的方法，其保留具有最大方差的尺寸。同样，Sammon映射（Sammon，1969）的目的是使距离误差在高维和低维数据之间。和边缘采样（Tang et al. ，2015）技术。LargeVis将计算复杂度显著降低到线性。UMAP（McInnes et al. ，2018）通过谱嵌入对KNN图可视化 FIt-SNE（Linder-manet al. ，2019）通过快速傅立叶变换近似每个数据点的梯度，这将计算复杂度降低到线性。AtSNE（Fu et al. ，2019）和t-SNE-CUDA（Chanet al. ，2018）专注于在GPU平台上加速t -SNE。尽管已经开发了许多方法来加速t-SNE，但它们并没有改变一次重新定位一个数据点的事实我们提出了一个基于聚类的近似方案，将子图作为一个单元，在高维数据可视化的基础上的KNN图的多级表示。多层次的概念已被广泛用于创建一个良好的可视化效果。多级表 示 由 图 聚 类 创 建 （ Meyerhenke et al. ， 2017 ） 、 图 匹 配（Veldhuizen，2007）或蒙特卡罗过程（HSNE）（Pezzottietal. ，2016年）。这些方法在降维时存在两个局限性：（1）多级表示生成的计算代价高;（2）粗图的顶点或边权值需要仔细定义和计算。因此，我们提出了一个线性的多级计划，不需要额外的权重计算。3. 我们的方法3.1. 预赛通常，该问题表示高维数据集Xx1，x2，. . . ..y1 ，y2，. . .，y N，y n2或3。 然后通过最小化高维数据P和低维数据Q的概率分布之间的Kullback-Leibler分歧来学习低维表示非线性方法采用 非线性 距离度量或局部结构，以捕获高-KL（P<$Q）=∑ ∑pijlogpij我J（一）维度空间 多维标度（MDS）（Kruskal，1964）是保持两个之间的成对距离=∑ ∑pijlogpij−pijlogqij（2）空间. Isomap（Tenenbaum et al. ，2000）估计测地线ij距离，而不是欧几里德距离，以最大限度地减少成对距离误差。其他非线性方法试图保留局部结构：高维空间中的邻近点保留注意，这个方程的第一部分是一个常数。因此，最小化低维空间附近。局部线性嵌入（LLE）（Saul and Roweis，2003）的基本思想是重构minKL（P<$Q）惠max∑ ∑pijlogqij（3）具有高i j中的邻居的线性组合的数据点最小化低维空间中的重建误差。Laplacian Eigenmap（BelkinandNiyogi，2003）和局部保持投影（LPP）（He andNiyogi，2004）都试图最小化附近点之间的距离。基于随机邻居嵌入的方法使用proba，KNN图用于近似高维空间中数据点之间的概率。由于构造精确KNN图是耗时的，LargeVis提出了一种有效的近似KNN图构造方法。数学上，概率分布P定义如下：能力而不是距离来衡量数据点之间的相似性。这些方法旨在最大限度地减少Kullbackpi|j=0expd（x，x）2/2σ2∑exp（−d（xi，xk）2/2σ2）如果j∈NNk（xi）我（四）高密度下两个概率分布之间的Leibler距离低维空间和低维空间t-SNE（Maaten和Hinton，2008; Han etal. ，2019）显示了其在生成低维嵌入方面的显著优势。但时间复杂度为O（N2）0.00否则pij=pi|j+ pj|我其中d（x， x）是x之间的欧几里得距离x，σ（五）是计算复杂度为了解决这个问题，Maaten提出了一个新的解决方案，Ji j iBarnes–Hut-SNE (BH-SNE) ( Largevis（Tang et al. ，2016）利用有效的算法来xi上高斯分布的方差，NNk（xi）表示k-xi 的最近邻，N是数据大小。采用重尾分布来测量低维空间中的概率分布Q构建KNN图，并通过利用负采样加速图可视化（Mikolov etal. ，2013年）qij=（1+d（yi，yj）2）−1k=l（1+d（yi，yj）2）−1（六）、··∑H. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5153=M∑=∈⋃L+1≤=1+d（yi，yj）2||| |=k=1d（yi，yjk）2（1+d（yi，yjk）2）V . 在这种情况下，每个顶点表示一个低维的我J我JKK我J我们随机选择一个顶点vl，并分配vl和它的kml-最近的的y1，。. . ，y n：dv =（1/n）idyi，其中yi是低维的×|| ||=i、jk=1受负采样技术（Mikolov et al. ，2013），为了计算y i的梯度，LargeVis随机选择KNN图中的一个连接点（正样本）y j和M个不连接点（负样本）y jk，k 1，2，. . . ，M.因此，目标函数重新表述如下：max∑pij[logqij+∑γlog（1−qijk）]（7）其中γ是用于平衡积极和消极的参数权重梯度由下式给出：Mdyi=−2pij（yi−yj）+∑2γpij（yi−yjk）（八）LargeVis使用边缘采样方法优化目标函数（Tang et al. ，2015）通过随机梯度下降。边缘采样方法基于概率pij对正样本（yj）进行随机采样以避免过度梯度。Fig. 1. 多层次代表性的一个例子。对于多级图可视化，较精细图的初始化从较粗糙图导出。我们计算G0的一个代表的梯度，并将梯度转发到通过负采样技术（Mikolov et al. ，2013）根据度d jk普-吉-克湖然而，LargeVis遭受两个主要缺点。第一、由于成本函数的非凸性，LargeVis可能会对大规模数据产生不吸引人的可视化LargeVis启动从数据点的初始随机配置，G1或G2中对应的顶点。在分层细化步骤中，我们从粗到细逐步细化生成的图图形粗化。给定一个KNN图G0=（V0，E0），顶点集V0 ={v0，v0，. . .，v0}和一组边E0 ⊂很多时间来收敛时，合并组具有相同的标签（见图。 3（a））。实际上，V0 0数据点：v01 2N={y i}。每条边都是两个0 0 0如果现有的方法可以找到一个合适的我顶点。 记e=（v，v）∈E如果x属于K-初始化其次，计算梯度是耗时的，为每个数据点输入以更新所有数据点的位置。给定两组数据点（例如，G1和G2），我们需要移动至少min（G1，G2）步来合并两个组，每次更新一个数据点的位置3.2. 关键的想法xi的最近邻：xj NNK（xi）。图粗化的目标是生成一个多级表示：一系列粗略的图G0，G1，G2，. . . ，GL，其中GL是粗图。给定一个图G1（V1，E1），我们将V1的顶点集划分成若干不相交的子集，从而生成一个较粗的图G1+1.每个子集都被折叠成图Gl+1中的一个新顶点.比如说，如果vl和vl被分配到vl+1，则vl+1=vlvl。在实际操作中，多层次图形可视化方案，和梯度近似-我G的一个新顶点我. 我们使用km-NN图mation scheme.我们首先讨论如何生成美观的可视化与更好的初始化。可以首先找到KNN图的全局结构的初始布局，然后稍后再完善布局我们生成一个多层次的表示（k m）K）而不是KNN图，因为一个顶点更有可能与它的近邻而不是远邻共享相似的属性。我们重复上述过程，直到所有顶点都被分配。最后，我们添加边缘（vl，vl）的两个顶点，则将El的（vl，v l）转换为El+1，如果vl和vl被分配给E l的两个顶点，i j i j以捕获全局结构，例如，一系列的KNN图。然后，我们迭代地细化KNN图的布局从粗到细的尺度，其中一个更精细的图形的初始化直接来自于一个粗糙的图形的最终布局。其次，我们提出了一个梯度近似方案，将最精细图的子图作为一个组，并将该组相似的数据点移动到一起。我们将最精细图中的一个代表的梯度转发到粗图中的组，而不是计算所有数据点的梯度 通过这种方式，我们可以显着加速KNN图形可视化过程（见图1）。① 的人。3.3. 多层次图可视化G 1+1。当V l + 1时，我们停止图粗化 > ρV l，ρ0的情况。8. 我们选择ρ0的情况。8有两个原因首先，如果ρ非常接近于1，Gl+1和Gl中的顶点数可能接近。这会显著增加多级算法的复杂度其次，如果ρ接近于0，则多级表示不能获取高级信息。基于上述考虑，我们选择ρ为0.8，以保持计算效率和全局结构提取之间的平衡分层细化。 对于粗图GL，我们看到-用随机初始化的方法使图形化。可以以较低的成本找到粗粒度图的最佳布局。一旦生成了粗略图G1的布局，则可以初始化更精细的图Gl−1由Gl导出。Gl−1的顶点vl−1设为Gl的顶点vl的位置，如果vl−1我vlinj i被分配给j多层概念已被广泛用于图可视化（Gajer and Kobourov，2000;Hu，2005）。我们提出了一个有效的多层次的计划，在线性时间构造多层次的图形，而无需额外的权重计算的新的图形。我们的方案包括两个步骤：图粗化和层次细化。图粗化步骤生成多级表示以捕获图的全局结构EFANA构建的KNN图（Fu和Cai，2016）。在图形粗化步骤。然后，我们递归地细化布局，从粗到细的尺度，直到最好的图G0完成。3.4. 梯度计算对于图G1的可视化，一组数据点v={y1，. . . ，yΣn}被计算为平均梯度J我们用于加速LargeVis的解决方案包括两个部分：H. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5154+|| ≤+--==-∑群中的随机数据点y：dv=dy <$dy，<$y∈v。我是我的朋友、、5555||=|| + + · · ·+≤| |表1数据集摘要数据集大小尺寸类别号MNIST70,00078410FMNIST70,00078410CIFAR1060,0001,02410AG120,0001004DBpedia560,00010014SVHN630,42025610答案1,400,00010010爬2,000,00030010评论3,000,0001005图二、在 两 个 数 据 之 间 共享阳性和阴性样本的 示例点（yi和yj）在同一组中。实心圆代表阳性样本虚线圆编码负样本。(a)LargeVis为yi和yj生成不同的正样本和负样本。(b)或者，我们的方法在yi和yj之间共享负样本和正样本。高维数据xi和dyi的位置是yi的梯度。但是，在O（nM）中对所有梯度求和是耗时的。我们的基本思想是把最细图的一个子图看作一个群，如果这个群的所有梯度都很接近，那么这个群就可以共享一个代表从细到粗尺度的梯度。给定由一组低维数据点y1，y2，. . .，y n，我们做出以下假设来近似梯度。我们首先假设数据点根据多级表示，组中的数据点彼此相似，这意味着它们与其他数据点具有相似的概率：答一：pik<$pjk，<$yi，yj∈v.（九）V0）5（K1）N，其中K是KNN图的大小。创建所有粗图的计算复杂度为O（KN）。对于分层细化，梯度计算由M 1个距离组成，需要O（M）时间，其中M是负样本的数量。迭代次数通常与顶点数成比例。例如，可视化Gl的迭代次数是TVl。分层加细的总计算复杂度为TV0（14（4）L）M5TV0M5TNM.因此，图形可视化的计算复杂度为O（KN+TNM），与数据点的数量N成线性关系。在我们的实验中，我们将迭代次数设置为500 N。4. 实验本节介绍定量和定性结果。所有实验是在一台装有英特尔至强处理器的台式PC上进行的然后，如图所示。2（b），yi和yj可以根据采样策略共享正样本和负样本此外，我们假设一组中的数据点彼此接近A2：yi=yj，yj∈v.（ 十）我们共享正样本yL和负样本yLk，k1，2，. . .，M在梯度计算（A1）中。 然后根据假设（A2），我们有：d（yi，yL）d（yj，yL），d（yi，yLk）d（yj，yLk）。因此，yi和yj具有相似的梯度：ME3 1245 CPU，32GB内存，安装Ubuntu 18.04。数据集。数据集的统计量总结见表1（详情见附录）。MNIST和Fashion-MNIST（FMNIST）数据集中的每个图像对于CIFAR10和SVHN数据集，我们训练强大的卷积神经网络来提取特征作为学习的表示。我们采用文本分类模型，fastText（Joulinet al. ，2016年），为AG的News、DBpedia、Yahoo Answers 和AmazonReviews数据集中的每个项目构建100维向量。Reviews数据集包含3，000，000条评论以及用户给出的星数（从1到5）。的CommonCrawl数据集由2，000，000个预训练单词组成dyi=−2piL（yi−yL）+∑2γpiL（yi−yLk）载体（Mikolov et al. ，2018年）。我们使用K-means生成1+d（yi，yL）2k=1d（yi，yLk）2（1+d（yi，yLk）2）M（十一）基于高维向量的十类。我们根据数据点的类别对数据点进行着色，以便于观察−2pjL（yj−yL）+∑2γpjL（yj−yLk）降维后的数据分布1+d（yj，yL）2=dy j，y i，y j∈ v.k=1d（yj，yLk）2（1+d（yj，yLk）2）方法和参数设置。我们将可视化结果与BH-SNE（Van Der Maaten，2014）、LargeVis（Tang etal. ，2016）、UMAP（McInnes et al. ，2018年）和FIT-SNE（林-顶点v的梯度可以看作a的梯度1n我们能够将计算复杂度从O（nM）降低到O（M）。计算一次梯度并将梯度分配给同一组中的其他数据点可以显著加速优化过程。3.5. 计算复杂度图可视化的计算复杂度包括图的粗化和层次细化。对于图粗化，创建Gl+1的最坏情况是访问-计算复杂度为O（|Vl|+的|El|）.让我们假设|Vl| ≤0。8|Vl−1|和|El|≤0。8|El−1|对于所有l=1，. . .，L，则图粗化的计算复杂度为（|e0级|+的|第0页|）（1 + 4+···+（4）L−1）≤ 5（|e0级|+的derman等，2019）。对于所有的方法，我们构建了一个100-NN图作为图形可视化的输入。 对于我们的方法，我们使用EFANNA的预设参数来构建100- NN图。在初步评估之后，迭代的总次数为500 N，并且多级方法中的参数k_ml被设置为3。对于这两种方法，困惑度γ和负样本的数量M分别被设置为50、7和5。我们采用了早期的夸张技术中使用的t-SNE找到一个更好的可视化。对于最好的图，我们将γ设为1，并将γ设为其他7个图。参数敏感性见附录。我们使用其他方法的预设参数。评估指标。在LargeVis（Tang et al. ，2016），我们采用k-NN分类器准确度作为质量度量。我们计算最近邻分类精度的基础上的2D可视化结果。H. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5155表2性能比较。我们分别显示了KNN图构建（GC）、图可视化（GV）和整个布局过程（Total）的运行时间（以秒为单位）。未填项目表示由于计算成本的原因导致相应算法的不适用性数据集阶段MNISTFMNISTCIFAR10AGDBpediaSVHN答案爬评论BH-SNEGC32157862950233811227351494（-）（-）UMAPGC11911211711163211391777（-）（-）FIT-SNEGC63651168712191131183214119756108大型VisGC6244757901371475595466471929212121我们GC31129133721711932993297690565621BH-SNEGV92110088391767145081751940982（-）（-）UMAPGV17818315330213331379713720（-）（-）FIT-SNEGV747968116142120456166859513802大型VisGV25052524227931551137512558291594230666723我们GV1031159616911011839321364917148BH-SNE总41351793378917901488914025342476（-）（-）UMAP总29729527041313963493615497（-）（-）FIT-SNE总7105907552372333516593792057019910大型Vis总31293000306932921285018512358066159878845我们总4144064333862294483261891554712769表3可视化质量。我们报告的10-NN分类器的2D可视化结果的准确性方法MNISTFMNISTCIFAR10AGDBpediaSVHN答案爬评论BH-SNE97.2082.5196.7399.3499.2397.0849.45（-）（-）UMAP96.2676.3296.3999.5499.9697.1776.64（-）（-）FIT-SNE93.1576.9294.9599.4595.2896.2949.2633.8026.06大型Vis96.7180.4996.6399.5299.9597.0077.7069.0060.44我们96.6779.1396.5399.4999.9697.0377.8367.9959.83图三. LargeVis的优化过程和我们在MNIST数据集上的方法。LargeVis在合并同一类别的组时花费大量时间。我们的方法在早期阶段生成更好的初始化4.1. 运行时间表2显示了不同数据集上的运行时间。我们分别报告了KNN图构造（GC）、图可视化（GV）和总过程（Total）的CPU时间。对于GC阶段，我们的方法在除了AG和DBpedia之外的所有数据集上的速度大约是LargeVis的两倍UMAP是KNN图构造和相似度计算中最快的方法。然而，UMAP比我们消耗更多的内存。例如，UMAP在Answers数据集上需要32 GB（我们的数据集是18GB）。对于我们的方法，我们发现GC阶段有时比图形可视化部分花费更多的时间。未来的发展方向是设计更有效的GV级是LargeVis和BH-SNE的性能瓶颈。由于我们采用梯度近似方案来减少总迭代次数，因此与LargeVis相比，我们的方法至少实现了五倍的加速。虽然FIT-SNE是小数据集上最快的方法对于总时间，我们的方法实现了至少三倍于LargeVis的加速。在小型数据集上，例如MNIST，LargeVis总共需要大约3129 s，而我们的方法只需要414s。对于像Reviews这样的大规模数据集，我们的方法比LargeVis快五倍UMAP在小数据集上比我们的稍然而，与Answers数据集上的UMAP相比，我们的方法实现了两倍的加速。综上所述，该方法在图粗化和层次细化的线性时间复杂度下，在应用于大数据集时比其他方法更有效。4.2. 可视化质量表3通过10-NN分类器评估可视化质量。当可视化近似KNN图时，具有默认学习率的 BH-SNE不稳定。由于边缘采样方法，LargeVis和我们的方法在所有数据集上的性能都是稳定的。对于FMNIST数据集，我们的方法的准确性略低。我们推测原因是多层次的方法不能捕捉到一个非常准确的结构的KNN图这个困难的数据集。此外，我们的方法在FMNIST（2.8%）和Answers（1.2%）数据集上实现了比UMAP更高的准确率。FIt-SNE的可视化可降低H. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5156见图4。 几种可视化算法的比较。对基于高维向量的K-means学习得到的相应标签或类别进行编码彩色的。质量优于其他方法。BH-SNE，LargeVis和我们的方法之间的10-NN精度差距非常小，表明我们的方法达到了相当的可视化质量。4.3. 可视化结果图 3 显 示 了 MNIST 数 据 集 上 的 图 形 可 视 化 过 程 。 对 于LargeVis，图形可视化过程的中间结果在二维空间中可视化。数字表示图形可视化的过程 图 三、LargeVis在非常早期的阶段生成组，并且在合并具有相同标签的组时收敛缓慢。我们还展示了我们的方法的多级图（从G4到G0）的可视化结果。值得注意的是，我们的方法导致了更好的初始化，并取得了可比的结果。图4比较了所获得的可视化结果，其中行指示数据集，列指示可视化方法。 每个点的颜色代表相应的标签。可视化结果的差异主要体现在聚类大小和邻域保持性上.对于具有明确类别信息的数据集H. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5157×××××××可视化结果是有意义的，并且相似的数据点被紧密地投影。例如，在CIFAR10和SVHN数据集上，十类数据点被很好地分离。Crawl数据集的单词嵌入是通过无监督学习来学习的。因此，在可视化结果中不存在明显的聚类结构所有方法在小数据集上都产生了可比的结果。然而，当处理大型数据集时，随机初始化的方法往往会收敛到局部最小值，并且无法保持最近邻。FIt-SNE在Answers and Reviews数据集上产生视觉上较差的结果。对于AG和DBpedia数据集，我们的生成了比BH-SNE和LargeVis更好的可视化。由于良好的初始化和迭代细化，相同类别的数据点被紧密地投影。另一个有趣的观察是，LargeVis在Reviews数据集上陷入了局部最优。相反，我们的结果似乎比LargeVis更合理。Reviews数据集的可视化从红色（一颗星）到紫色（五星）连续显示总之，我们的方法产生了相同或更好的可视化结果，具有更多的区别性集群。5. 结论针对大规模数据，提出了一种高效的高维数据可视化算法。在未来，我们寻求通过利用并行性来实现GPU版本。我们计划用更小的图来近似高维空间中的概率（例如，10-NN图）。此外，需要更有效的多层次表示来实现更好的可视化质量。伦理批准本研究不涉及人类受试者。研究中使用的所有数据都来自过去发布的公共数据库作者贡献朱海洋：概念化。朱敏峰：写作-初稿.英超杰丰：写作-审查和编辑。邓才：监管。胡远哲：软件。吴世龙：验证。吴向阳：监督。魏晨：监督。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作确认本文得到了国家自然科学基金（61972122，61772456）的资助.附录A.1. 数据集1. MNIST：MNIST 1数据集包括70，000个灰度手写数字图像。每个图像包含28 28 = 784像素，属于从0到9的十个数字之一。每个图像被视为784维数据点。1http://yann.lecun.com/exdb/mnist/。2. FMNIST：Fashion-MNIST2是一个由70，000张灰度图像组成的数据集，这些图像带有来自10个时尚产品类别的标签。它与MNIST数据集共享相同的图像大小。3. CIFAR10：CIFAR103数据集包括60，000个彩色图像，年龄为32 32像素。所有图像都标记有十个类。每个班级有6000张图片。我们使用强大的卷积神经网络提取特征，该网络由七个模块组成，每个模块包含一个3 - 3卷积层，然后进 行批 量 归一 化 。和ReLU 非 线性 。 我 们 添加 max-pooling2在每两个卷积层之后和第七个卷积层之后的2个贴片。具有1024个神经元的最后一层输出被馈送到用于十个类别的softmax分类器中。我们提取最后一层的输出作为每个图像的1024维特征向量。4. AG：AG来自2000多个来源的新闻。我们使用四个最大的类别，每个类别有30，000篇文章。每个文章都由文本分类模型（ fastText ） 训 练 的 100 维 向 量 表 示 （ Joulin et al. ，2016），在测试数据集上达到了92.4%的准确率。5. DBPedia5是一个公共数据基础设施，维基百科的结构化信息。DBPedia数据集由560，000篇维基百科文章组成，分为14个类。我们使用fastText为每篇文章构建一个100维向量。在测试数据集上的分类正确率为98.6%。6. SVHN：街景门牌号（SVHN）数据集6是从Google街景图像中获得的真实世界门牌号图像数据集。我们使用所有630，420个字符级格式的彩色图像，其中数字的 大小 调整 为3232 像素 的分 辨率 。 SVHN 数据 集比MNIST更难。因此，我们采用预先训练的深度神经网络来提取更好的可视化表示。神经网络架构包含七个卷积层，每个卷积层都是一个3 × 3卷积，具有批量归一化、ReLU激活和0.3的dropout。我们在每两个卷积层之后和第七个卷积层之后添加超过2 2个补丁的最大池化。然后，网络有一个最终的线性层，后面是一个用于分类的softmax。我们提取最后一个卷积层的256维输出作为学习的表示。7. 答案：我们使用Yahoo！答案综合问答1.0版。 7YahooAnswers数据集由10个班每个类包含140，000个问题，包括问题标题，问题内容和最佳答案。每个问题的特征向量也被fastText提取出来，测试准确率为72.4%.8. Crawl：Crawl数据集由2，000，000个单词向量组成，这些向量使用无监督的快速文本在Common Crawl上训练。每一个单词都由一个300维的向量表示。两个向量之间的距离是一种有效的语义相似性度量。我们采用K-means生成十个类的高维向量的基础上。2 https://github.com/zalandoresearch/fashion-mnist网站。3 https://www.cs.toronto.edu/~kriz/cifar.html网站。4 http://www.di.unipi.it/~gulli/AG_corpus_of_news_articles.html网站。5 https://wiki.dbpedia.org/develop/datasets网站。6 http://ufldl.stanford.edu/housenumbers/网站。7 https://webscope.sandbox.yahoo.com/网站。H. Zhu，M.Zhu，Y.Feng等人视觉信息学5（2021）5158=表410-NN分类器的精度相对于的大小，表710-NN分类器精度相对于参数γ。k ml-多级方法中的最近邻。kml1 3 10 50100γMNIST0.195.53196.46596.52796.691096.54MNIST96.5596.5896.4496.5696.28FMNIST73.6677.2279.1379.0179.46FMNIST79.4779.1079.1079.1479.30CIFAR1095.3696.3696.3996.4996.48CIFAR1096.5896.5996.5596.3496.37AG99.5199.4699.4999.4699.47AG99.4699.5499.4799.4599.51DBpedia99.9499.9599.9499.9599.94DBpedia99.9599.9599.9599.9699.96SVHN97.0997.0897.0497.0597.07SVHN97.0397.1097.0697.0397.10答案72.9277.0577.6677.7377.86答案77.8777.8677.8677.7077.26爬54.2665.3867.6468.0167.97爬68.0468.0768.2268.0768.19评论59.8559.8259.8459.8659.90评论59.8859.8859.8959.6859.63表510-NN分类器精度相对于负样本数 M。M135710MNIST96.3296.4096.6296.5996.76FMNIST76.1778.5079.2279.5780.01CIFAR1096.4696.4496.4796.4696.07AG99.4499.4999.5399.4999.52DBpedia99.9699.9699.9599.9499.94SVHN97.1897.1197.0597.0596.96答案77.4277.7377.8277.4877.64爬65.5067.5667.9068.0368.30评论59.8259.8359.8259.9359.87表610-NN分类器精度相对于迭代次数。TN100N300N500N1000N1500NMNIST96.2896.3896.6196.4496.50FMNIST77.2579.0579.2579.7379.43CIFAR1096.0296.4696.5096.6796.46AG99.4899.5699.5499.5499.48DBpedia99.9199.9599.9599.9499.95SVHN96.9597.0597.1097.0597.06答案76.3977.5077.8477.6877.56爬63.7167.0667.9268.5864.78评论59.7759.9059.8760.0459.959. 评 论 ： 亚 马 逊 评 论 数 据 集 来 自 斯 坦 福 网 络 分 析 项 目（Leskovec和Krevl，2014），包含3，000，000条评论以及用户给出的星数（从1到5）。采用fastText模型来用100维向量表示每个评论。该模型在亚马逊评论数据集上的测试准确率为60.3%。A.2. 参数敏感性我们报告的10-NN分类器的精度相对于我们的方法中的参数。表4示出了10-NN分类器相对于用于构造多级表示的k个最近邻的准确度。我们发现，精度保持稳定的所有kml在几乎所有的数据集上，并且小的kml实现了稍高的精度。将一个顶点与它的近邻合并而不是与它的远邻合并更合理。因此，我们采用3-最近邻来捕捉我们的多层次方法中的全局结构。表5显示了10-NN分类器相对于阴性样本数