我正在尝试使用 t-sne 根据它们的视觉相似性来排列图像，类似于这个很酷的表情符号示例（来源）：
但是 t-sne 的输出只是一个“点云”，而我的目标是以规则的、接近正方形的、密集的网格来显示图像。所以我需要以某种方式将 t-sne 的输出转换为网格上的 (x,y) 位置。
到目前为止，我已经遵循了这篇很棒的博客文章中的建议：我将其表述为线性分配问题，以找到最佳嵌入到规则网格中。我对结果很满意，例如：
我的问题是“捕捉到网格”阶段结果是一个巨大的瓶颈，我需要我的方法来很好地扩展大量图像（10K）。为了解决线性分配问题，我使用了 Jonker-Volgenant 算法的 Java 实现，其时间复杂度为 O(n^3)。所以虽然 t-sne 是 nlogn 并且可以很好地扩展到 10K 图像，但对齐到规则网格的部分最多只能处理 2K 图像。
潜在的解决方案，在我看来：
- 从总共 10K 中随机抽取 2K 图像
- 将 10K 图像分成 5 个并创建 5 个地图。这是有问题的，因为有一个“鸡和蛋”的问题，我该如何做好划分？
- 以准确性换取性能：大约在接近线性的时间内解决线性分配问题。我想试试这个，但我找不到任何现有的实现供我使用。
- 以不同的、更有效的方式实施“对齐网格”部分。
我正在使用 Java，但 cpp 中的解决方案也很好。我猜我不是第一个尝试这个的人。有什么建议么？想法？
谢谢！