Python 中的增量最近邻算法

Question

是否有人知道Python中实现的最近邻算法，可以进行增量更新？我发现的所有算法都是批处理的，例如这个。是否可能实现增量最近邻算法？

- Cerin

---

不确定您所说的“递增”和“批处理”是什么意思。而且您提供的链接已经失效了。 - Mark Ransom

@Mark，不确定从哪里开始。这些是常见的机器学习术语。链接在这里可以正常工作... - Cerin

是的，ML中常见的术语。链接对我也有效。 - doug

我习惯于在图像调整中使用“最近邻居”这个术语，但我不理解在那种情况下使用的术语。抱歉。 - Mark Ransom

Answer 1

这是晚了很久的答复，但为了记录：

实际上，有一种将像KD-Tree这样的批处理算法转换为增量算法的技巧，称为“静态到动态转换”。

要生成KD-Tree的增量变体，您需要存储一组树而不是仅一个树。当您的最近邻结构中有N个元素时，您的结构将具有二进制表示中每个“1”位对应的树。此外，如果树Ti对应于N的第i位，则树Ti包含2 ^ i个元素。

因此，如果您的结构中有11个元素，则N = 11，即二进制数1011，因此您有三棵树-T3，T1和T0-分别具有8个元素，2个元素和1个元素。

现在，让我们向我们的结构插入一个元素e。插入后，我们将有12个元素，即二进制数1100。比较新的和先前的二进制字符串，我们发现T3没有变化，我们有一个具有4个元素的新树T2，而树T1和T0则被删除。我们通过对T2以下所有树（即T1和T0）进行批量插入e以及所有元素来构建新的树T2。

以此方式，我们从静态基础结构创建了增量点查询结构。但是，将这样的静态结构“增量化”存在一种渐进减速，在额外的log（N）因子形式中：

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

- giogadi

---

太棒了！你知道有没有这个的Java或Python示例实现（也许在机器学习库中）？我只在谷歌搜索中看到研究论文。 - Rahul Murmuria

参考文献？实现方式？ - Jonathan H

是否有任何关于这种kd-tree的参考资料或Python实现？ - eLearner

@Sheljohn 静态到动态的转换最初是由Bentley和Saxe在1979年发明的。例如，请参阅URL http://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf。 - Ron Kaminsky

这是一个非常棒的想法！！ - Ismael EL ATIFI

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

注意：我的评论适用于高维空间。如果您在使用二维或三维空间，我的意见可能不适用。（如果您在使用非常高维的空间，则可以使用暴力搜索或近似最近邻算法。）

- RandomGuy

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实现（scipy.spatial.KDTree），但我不认为它支持节点插入，至少在文档中没有这样的函数（我还没有查看源代码）。

- doug

---

谢谢，但是那个烹饪书的例子并不真正支持增量更新。插入代码是批处理过程的一部分，并依赖于批处理过程中创建的栈。你可以想象一下修改它以允许插入单个点，但是这棵树可能会变得不平衡，从而影响查找速度。 - Cerin