Python中的增量最近邻算法

Question

是否有人知道在Python中实现的最近邻居算法可以逐步更新？我发现的所有这些,例如这个,似乎都是批处理过程.是否可以实现增量NN算法？

Answer 1

这是迟到的,但对后人来说:

实际上有一种技术可以将批量处理的算法(如KD-Tree)转换为增量算法:它被称为静态到动态转换.

要生成KD树的增量变体,您需要存储一组树而不是一棵树.当你的最近邻结构中有N个元素时,你的结构将在N的二进制表示中为每个"1"位有一个树.此外,如果树T_i对应于N的第i位,则树T_i包含2 ^ i个元素.

因此,如果您的结构中有11个元素,那么N = 11或1011为二进制,因此您有三个树 - T_3,T_1和T_0 - 分别包含8个元素,2个元素和1个元素.

现在,让我们在我们的结构中插入一个元素e.插入后,我们将有12个元素,或二进制1100.比较新的和前一个二进制字符串,我们看到T_3没有改变,我们有一个新的树T_2有4个元素,树T_1和T_0被删除.我们构建新树T_2做的批量插入ê所有的树"下面"的元素一起T_2,这是T_1和T_0.

通过这种方式,我们从静态基础结构创建增量点查询结构.但是,以额外的log(N)因子的形式"增量化"这样的静态结构的渐近减速:

• 在结构中插入N个元素:O(N log(N)log(n))
• 具有N个元素的结构的最近邻查询:O(log(n)log(n))

Answer 2

我认为增量构建 KD 树或 KNN 树的问题是，正如您在评论中提到的那样，树最终会变得不平衡，并且您无法进行简单的树旋转来解决平衡问题并保持一致性。至少，重新平衡任务并不是微不足道的，人们肯定不想在每次插入时都这样做。通常，人们会选择使用批处理方法构建一棵树，插入一堆新点并允许树在某个点上变得不平衡，然后重新平衡它。

一个非常相似的事情是为 M 个点批量构建数据结构，将其用于 M' 个点，然后用 M+M' 个点批量重新构建数据结构。由于重新平衡不是我们熟悉的树的正常快速算法，因此相比之下，重建不一定很慢，并且在某些情况下可能会更快（取决于进入增量算法的点的顺序）。

话虽这么说，如果您采用重建方法，您编写的代码量、调试难度以及其他人理解您的代码的难易程度可能会大大减少。如果这样做，您可以使用批处理方法并保留尚未插入树中的点的外部列表。可以使用强力方法来确保这些都不比树中的更接近。

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

http://www.scipy.org/Cookbook/KDTree

http://cgi.di.uoa.gr/~compgeom/pycgalvisual/kdppython.shtml

http://sites.google.com/site/mikescoderama/Home/kd-tree-knn

http://en.wikipedia.org/wiki/Kd-tree

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