我正在寻找一种方法来为高维点（通常为~11-13 维）做快速最近邻（希望是 O(log n)）。我希望它在初始化结构后的插入过程中表现最佳。我想到了 KD 树，但是如果您不进行批量加载而是进行动态插入，那么 kd 树就不再是平衡的，并且 afaik 平衡是一项昂贵的操作。
所以，我想知道对于这种设置，您更喜欢哪种数据结构。你有高维点，你想插入和查询最近的邻居。
问问题
646 次
4 回答
5
维度的诅咒在这里阻碍了。您可能会考虑应用主成分分析 ( PCA ) 来降低维度，但据我所知，没有人对此有很好的答案。
我以前处理过这类问题（在音频和视频指纹识别中），有时多达 30 个维度。分析通常会发现某些维度不包含搜索的相关信息（实际上是模糊搜索，我的主要目标），因此我在用于访问数据的索引结构中省略了它们，但将它们包含在逻辑中以从在搜索过程中找到的候选人名单。这有效地将维度降低到一个易于处理的水平。
我通过严格量化剩余维度进一步简化了事情，以便将整个多维空间映射到一个 32 位整数。我使用它作为 STL 映射（红黑树）中的键，尽管我可以使用哈希表。我能够在一两分钟内将数百万条记录动态地添加到这样的结构（当然是基于 RAM 的）中，并且搜索平均花费大约一毫秒，尽管数据绝不是均匀分布的。搜索需要仔细枚举映射到 32 位密钥的维度中的值，但其可靠性足以在商业产品中使用。如果我的来源是正确的，我相信它在今天的 iTunes Match 中被使用。:)
最重要的是，我建议您查看您的数据并进行一些自定义操作，利用其中的功能进行快速索引和搜索。找出变化最大且彼此最独立的维度。量化它们并将它们用作索引中的键。索引中的每个存储桶都包含共享该键的所有项目（可能不止一个）。要查找最近的邻居，请查看“附近”键并在每个桶中查找附近的值。祝你好运。
ps 我写了一篇关于我的技术的论文，可以在这里找到。对付费墙感到抱歉。也许您可以在其他地方找到免费副本。如果您对此有任何疑问，请告诉我。
于 2012-04-02T07:25:09.683 回答
5
另一个想到的数据结构是覆盖树。与最初为回答范围查询而开发的 KD 树不同，这种数据结构最适合最近邻查询。它已被用于涉及计算所有数据点的 k 个最近邻的 n 体问题。此类问题也出现在密度估计方案（Parzen windows）中。我对您的具体问题知之甚少，但我知道这个数据结构有在线版本。查看 Alexander Gray 的页面和此链接
于 2012-04-02T19:47:55.210 回答
3
如果您使用具有相当大桶大小的桶 Kd 树，它可以让树更好地了解当叶子太满时在哪里分裂。Robocode 中的人在极其苛刻的时间约束下执行此操作，随机插入发生在运行中，kNN 在 1ms 内 k>80、d>10 和 n>30k。查看这个kD-Tree 教程，它解释了一系列 kD-Tree 增强以及如何实现它们。
于 2012-10-23T20:44:42.423 回答
1
以我的经验，11-13 尺寸并不算太糟糕——如果你批量加载的话。批量加载的 R-trees（与 kd-trees 相比，它们保持平衡！）和 kd-trees 仍然应该比线性扫描更好地工作。
一旦你完全充满活力，我的经历就会变得更糟。粗略地说：对于批量加载的树，我看到了 20 倍的加速，而增量构建的 R-树只有 7 倍。因此，经常重建树确实是有回报的。根据您组织数据的方式，它可能比您想象的要快得多。我正在使用的 kd-tree 的大容量负载是O(n log n)，我读到也有一个O(n log log n)变体。具有较低的常数因子。对于 R-tree，Sort-Tile-Recursive 是迄今为止我见过的最好的批量加载，而且O(n log n)常数因子也很低。
所以是的，在高维中，我会考虑不时重新加载树。
于 2012-12-23T23:01:47.903 回答