python - Python中的增量最近邻算法

Question

有人知道用 Python 实现的最近邻算法可以增量更新吗？我发现的所有这些，比如这个，似乎都是批处理。是否可以实现增量NN算法？

Answer 1

这已经很晚了，但是为了后代：

实际上有一种技术可以将 KD-Tree 等批处理算法转换为增量算法：它称为静态到动态转换。

要生成 KD-Tree 的增量变体，您需要存储一组树，而不仅仅是一棵树。当您的最近邻结构中有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被删除。我们通过批量插入e以及“位于” T_2下方的树中的所有元素（即T_1和T_0 ）来构造新树T_2。

通过这种方式，我们从静态基础结构创建了增量点查询结构。然而，像这样以额外log(N)因子的形式“递增”静态结构会出现渐近减速：

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

Answer 2

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

一个非常相似的做法是为 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 中工作，我所说的可能不合适。（如果您在非常高维空间中工作，请使用蛮力或近似最近邻。）

Answer 3

有。Scipy Cookbook 网站包含一个完整的kNN 算法实现，可以增量更新。

也许一些背景知识会对感兴趣但不熟悉该术语的人有所帮助。

kNN 引擎由两种数据表示中的任何一种提供支持——数据集中所有点之间的成对距离存储在多维数组（距离矩阵）中，或者kd-tree仅将数据点本身存储在多维二叉树。

这些只是基于 kd-tree 的 KNN 算法需要的两个操作：从数据集创建树（类似于其他 ML 算法中以批处理模式执行的训练步骤），然后搜索树以找到“最近的邻居” （类似于测试步骤）。

KNN 算法上下文中的在线或增量训练（假设它基于 kd-tree）意味着将节点插入到已经构建的 kd-tree 中。

回到 SciPy Cookbook 中的 kd-Tree 实现：负责节点插入的具体代码行出现在注释行“insert node in kd-tree”之后（实际上，该注释之后的所有代码都指向节点插入）。

最后，在 SciPy 库的空间模块（scipy.spatial模块）中有一个 kd-tree 实现，称为 KDTree（scipy.spatial.KDTree），但我不相信它支持节点插入，至少这样的功能不在文档中（我没有查看源代码）。