Abstract:

之前的降维技术用t-SNE等技术：计算量大
我们：LargeVis，利用K近邻算法，效率和效力都好，对不同的数据集表现稳定。

Introduction

对于散点图、热力图、网络图等可视化为二维或者三维图形时，如果数据点多，并且数据多维时，会使计算困难。
二维或者三维图布局不仅可以直观展示数据的本质结构，并且可以建立交互可视化。
高维数据以低维投影到空间是机器学习和数据挖掘的核心问题。

必要问题：保存高维数据的本质结构：在低维空间中，保持相似数据点离得近，不相似的数据点离得远。

非线性方法：虽然经验表明它们一般对于小型实验数据比较有效，对于高维真实数据无法表达高维数据的局部和全局结构。
Maaten提出了t-SNE降维，可以捕获局部和全局的结构，并且提出了加速技术通过构建数据点的KNN图，然后把图投影到低维空间基于树形算法。

T-SNE和它的变体家族所代表的思想：
1.从数据中构建相似的结构
2.把该结构投影到二维或三维空间。

Paste_Image.png

t-SNE不足：

1.KNN图有计算瓶颈，t-SNE构建图时采用vantage-point树，其性能随数据维数的递增有明显的恶化。
2.当数据量变大时，图的可视化效率明显恶化。
3.t-SNE的参数对不同数据集非常敏感。花费在调参上的时间多。

贡献：

1.提出一种新的可视化技术：可以计算带有数百维度的数百万数据点的布局；
2.提出了一种有效的算法来构建高维大尺度数据的近似KNN图；
3.提出了一个概率模型，该模型的目标函数可以随异步随机梯度得到优化。
4.用大型数据集进行试验，定量和可视化比较LargeVis 和 t-SNE 的性能。

Related work

当前对于高维数据可视化的成功研究一般来自机器学习，其方法就如t-SNE一样，计算KNN图，然后可视化到二维三维空间。我们的工作遵循这一方向并作出了重要的改进。

2.1KNN图构建

KNN的计算复杂度O(N2d) N:数据点的数量；d:维度的数量。
我们提出的技术建立在随机投影树，KNN图的准确性提高到接近100%。

2.2图可视化

图可视化的问题是降维：线性降维和非线性降维。

Largevis：

可视化高维数据的基本思想是在低维空间中保存数据的本质结构。
现有方法：计算不同数据点之间的相似性，在低维空间中保持这种相似性（计算量大）。而近期像t-SNE这样的构建KNN图来映射的会比较好，因为我们延续这种方式，不过对于KNN图的构建用了一个非常有效的算法，并且在图可视化时用了一个概率模型。

3.1 高效KNN图构建

随机投影树：

分割整个空间建立一个树。对于树的每个非叶节点，选择一个随机超平面将非叶节点的子空间分割为两个，变成那个节点的两个children.超平面是从当前子空间中随机抽取两个点选择的，然后将超平面放到与两个点距离相等的位置。一直循环此过程，直到子空间中点的数量达到极限值。
一旦随机投影树构建好，每一个数据点都可以在此树中找到对应的叶节点。叶节点所对应的子空间中的所有点都将作为该数据点的所有最近邻居点的候选。一旦所有点的最近节点被找到，那KNN图也就可以创建。

我们提出的算法：

为了使KNN图更加精确，就需要建立许多树，会造成效率低下。因此我们提出了一个邻居探索技术提高图的精确率。
此处我们不建立很多树来构建精确的KNN图，而是使用邻居探索技术。基本思想是：我的邻居的邻居也是我的邻居。具体来说，建立几个随机投影树来构建KNN图，精确性也许会降低。然后对于图的每一个节点，搜寻邻居的邻居。通过几次迭代，KNN图的精确率就达到了几乎100%。

KNN图构建算法：
1.建立NT个随机投影树；
2.搜寻最近邻居（对每个点 I , 搜索随机概率树寻找它的K个最近邻居，将结果存储在knn(i) 中 )
3.邻居探索：多次迭代。
4.根据式1,2计算边的权重。

4、实验

目的：验证算法性能

4.1数据集

4.2KNN图构建结果

性能分析

Paste_Image.png

VP树效果最差，我们的最好。（运行时间最短，准确率最高）
多少次迭代可以达到好的准确率：由1可知，迭代一次就可达到接近1的准确率，由2可知，迭代3次，就可达到高准确率。
我们提出的KNN图的构建算法非常高效，解决了数据可视化技术的计算瓶颈。

Paste_Image.png

4.3图可视化

图可视化算法：1.对称的SNE 2.t-SNE 3.LINE 4.LargeVis

4.3.1概率函数比较

Paste_Image.png

在所有概率函数中，1/(1+x^2)是最好的，因此后面的实验我们均采用该概率函数。

4.3.2不同数据集的结果

Paste_Image.png

在ab中这种小数据集中，t-SNE表现的好，但在cd这种大数据集中，LargeVis表现的好。并且LargeVis更稳定。LINE一直表现的比较糟糕，可以看出embedding学习方法在数据可视化中并不适用。

Paste_Image.png

在表二中，对于t-SNE与我们的LV相比，LV所花费的时间更少，尤其是在大数据集中。

4.3.3 关于性能和数据大小

Paste_Image.png

由ab可得出，随数据量的增加，LV的性能升高，T-SNE的性能降低。由CD可知，随数据量的增加，T-SNE运行时间也急剧增加。这是因为时间复杂度不同，T-SNE的时间复杂度为O(Nlog(N)), 而我们的为O(N)

4.3.4参数敏感性

Paste_Image.png

对于负采样样本量，只需几个就可以。对于训练样本量，当达到足够大时，性能非常稳定。

4.4可视化样例

由图8（不同颜色不同分类）可得：在AB中可知，当数据量小时，T-SNE和LV两种方法效果差不多。由cdef可知，当数据量大时，LV的可视化效果更加直观。

由图10表示DBLP中的论文的范围，颜色代表论文所属会议。CIKM有三个分支，是因为CIKM会议由三个不同的方向：信息检索，知识管理和数据库。

5.总结：

LargeVis：在低维空间中布局大尺度高维数据。
步骤：首先构建KNN图，然后把图投影到低维空间。
创新点：提出了非常有效的算法对于KNN图的构建，提出了一个概率模型对于图的可视化。
实验证明：LargeVis在图构建和可视化上表现的都比T-SNE好。