kNN在高朦度空间动态插入

我正在寻找一种方法来做高维点（通常〜11-13维）的快速最近邻（有希望O（log n））。在初始化结构后，我希望它在插入期间表现最佳。 KD树出现在我的脑海里，但如果你不做批量加载但是做动态插入，那么kd树不再是平衡的，而且afaik平衡是一个昂贵的操作。kNN在高朦度空间动态插入

所以，我想知道什么样的数据结构，你喜欢这种设置。你有高维点，你想插入和查询最近的邻居。

来源

2012-04-02 I J

Curse of Dimensionality阻碍了这里。您可能会考虑应用主成分分析（PCA）来降低维度，但据我所知，没有人对此有很好的答案。

我在处理这种类型的问题之前（在音频和视频指纹识别中），有时最多有30个维度。分析通常显示某些维度没有包含搜索相关信息（实际上是模糊搜索，我的主要目标），所以我从用于访问数据的索引结构中省略了它们，但将它们包含在逻辑中以确定来自搜索过程中找到的候选人列表。这有效地将维度降低到易于理解的水平。

我通过严格量化其余维度来进一步简化事情，使整个多维空间被映射为一个32位整数。我用它作为STL地图（红黑树）中的关键字，尽管我可以使用散列表。我能够在一两分钟内动态地将数百万条记录动态地添加到这种结构（当然是基于RAM）中，并且搜索平均花费了大约1毫秒，尽管数据并不是均匀分布的。搜索需要仔细枚举映射到32位密钥的维度中的值，但其可靠性足以用于商业产品。如果我的消息来源正确，我相信它在iTunes Match中用到了这一天。 :)

底线是，我建议你看看你的数据，并做一些自定义的利用它的功能，使快速索引和搜索。找出变化最大的维度，并且彼此最独立。将这些量化并将它们用作索引中的关键字。索引中的每个存储桶都包含共享该密钥的所有项目（可能会有多个）。要查找最近的邻居，请查看“附近”键并在每个桶内查找附近的值。祝你好运。

p.s.我写了一篇关于我的技术的论文，可用here。抱歉关于付费墙。也许你可以在别处找到免费的副本。如果您对此有任何疑问，请告知我们。

来源

2012-04-02 07:25:09

谢谢，但我不想降低数据的维数，因为我想在原始空间中使用精确的kNN。 – 2012-04-03 01:37:59

够公平的，尽管我从未看到在不同距离搜索固定数量的邻居的价值。在固定距离搜索可变数量的邻居对我来说似乎更实用。 – 2012-04-03 06:18:24

@Randall，很好。 “STL地图中的32位密钥”是指完全匹配，还是32个1位nighhbors？任何想法[bit-string-nearest-neighbor-searching]（http://stackoverflow.com/questions/9959728/bit-string-nearest-neighbour-searching） - 看起来是NP完全的？ – denis 2012-04-15 10:31:11

想到的另一个数据结构是封面树。与最初开发用于回答范围查询的KD树不同，此数据结构对于最近邻查询是最佳的。它已被用于涉及计算所有数据点的k个最近邻居的n体问题。在密度估算方案（Parzen窗口）中也会出现这样的问题。我不太了解您的具体问题，但我确实知道这个数据结构有在线版本。查看Alexander Gray的页面，并且这个link

来源

2012-04-02 19:47:55 killogre

谢谢。将检查出 – 2012-04-04 01:51:14

我不知道封面树。感谢您的提示，@ killogre。 – 2012-04-10 22:36:02

如果您使用具有相当大的桶大小的桶Kd树，它可以让树更好地了解当叶子太满时分割的位置。 Robocode中的家伙在极其苛刻的时间限制下做到了这一点，随机插入发生在飞行中，kNN在1ms以下k> 80，d> 10和n> 30k。看看这个kD-Tree Tutorial，它解释了一堆kD-Tree增强功能以及如何实现它们。

来源

2012-10-23 20:44:42 jkflying

根据我的经验，11-13尺寸不是太差 - 如果你批量加载。批量加载的R树（与k-d树相比保持平衡！）和k-d树应该仍然比线性扫描更好。

一旦你完全充满活力，我的经验会变得更糟。粗略地说：对于批量加载的树木，我看到20倍的加速，增量式构建R树只有7倍。所以它确实还清经常重建树。取决于你如何组织你的数据，它可能比你想象的要快得多。我使用的k-d-tree的批量负载是O(n log n)，我读到也有O(n log log n)变体。低常数因子。对于R-tree，Sort-Tile-Recursive是目前为止我见过的最好的批量加载，并且也是O(n log n)，具有低常数因子。

所以是的，在高维度，我会考虑不时重新加载树。

来源

2012-12-23 23:01:47

kNN在高朦度空间动态插入

回答

相关问题