python - 在 scikit-learn 中将 t-SNE 扩展到数百万次观察

Question

t-SNE 据说可以扩展到数百万次观察(参见 here)，但我很好奇这怎么可能是真的，至少在 Sklearn 实现中是这样。

我正在一个包含约 10 万个项目的数据集上进行尝试，每个项目都有约 190 个特征。现在，我知道我可以进行第一次降维，例如PCA，但问题似乎更根本。

t-SNE 计算并存储为输入观测值计算的完整、密集的相似矩阵(
我已经通过查看 source 确认了这一点。 )。就我而言，这是一个 100 亿元素密集矩阵，它本身需要 80 GB 以上的内存。将其推断为仅 100 万次观察，您正在查看 8 TB 的 RAM 来存储距离矩阵(更不用说计算时间了......)

那么，我们如何才能在 sklearn 实现中将 t-SNE 扩展到数百万个数据点？我错过了什么吗？ sklearn docs至少暗示这是可能的:

By default the gradient calculation algorithm uses Barnes-Hut approximation running in O(NlogN) time. method=’exact’ will run on the slower, but exact, algorithm in O(N^2) time. The exact algorithm should be used when nearest-neighbor errors need to be better than 3%. However, the exact method cannot scale to millions of examples.

这是我的重点，但我肯定会读到这意味着 Barnes-hut 方法可以扩展到数百万个示例，但我要重申，代码需要在我们得到任何实际 t- sne 转换(有或没有 Barnes-hut)。

所以我错过了什么吗？是否可以将其扩展到数百万个数据点？

Answer 1

Barnes-Hut 不需要您计算和存储为输入观测值计算的完整、密集的相似度矩阵。
另外，请查看文档中提到的引用资料。特别是this one .引用该页面:

The technique can be implemented via Barnes-Hut approximations, allowing it to be applied on large real-world datasets. We applied it on data sets with up to 30 million examples.

该页面还链接到有关近似如何工作的讨论: Visualizing Data Using t-SNE .