Python中增量最近邻算法

有人知道在Python中实现的可以增量更新的最近邻算法吗？我找到的所有算法，比如这个，似乎都是批处理方式。是否有可能实现一个增量NN算法？

回答：

我认为你提到的问题是，增量构建KD树或KNN树时，树最终会变得不平衡，你无法通过简单的树旋转来解决平衡问题并保持一致性。至少，重新平衡的任务并不简单，人们肯定不希望在每次插入时都进行。通常，人们会选择用批处理方法构建树，插入一批新点，让树在一定程度上变得不平衡，然后再重新平衡它。

一个非常相似的方法是为M个点批量构建数据结构，使用它处理M’个点，然后用M+M’个点批量重建数据结构。由于重新平衡不是我们熟悉的树的常规、快速算法，与之相比，重建不一定慢，在某些情况下甚至可能更快（取决于进入增量算法的点的序列）。

尽管如此，如果你采用重建方法，你编写的代码量、调试难度以及其他人理解你的代码的难度都会显著降低。如果你这样做，你可以使用批处理方法，并保持一个外部列表，记录尚未插入树中的点。可以使用暴力方法来确保这些点中没有一个比树中的点更近。

下面是一些Python实现/讨论的链接，但我没有找到任何明确声称是增量的。祝你好运。

注意：我的评论适用于高维空间。如果你在2D或3D中工作，我所说的话可能不适用。（如果你在非常高维的空间中工作，使用暴力法或近似最近邻。）

学技术