Python中的增量式最近邻算法

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

一个非常类似的做法是,为M个点批量构建数据结构,并将其用于M个点,然后使用M+M个点批量重新构建数据结构。由于重新平衡不是我们熟悉的树的正常、快速算法,因此与之相比,重建并不一定慢,在某些情况下可能更快(取决于输入增量算法的点序列)。

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

下面是一些到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

注:我在这里的评论适用于高维空间。如果你是在二维或三维工作,我说的可能不合适。(如果你在非常高的维度空间中工作,使用蛮力或近似最近邻)。

这已经很晚了,但是对于后代来说:

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

要生成KD树的增量变体,需要存储一组树而不是一棵树。如果有的话 N个 元素在最近邻结构中,结构的二进制表示中的每个“1”位都有一个树 N个 . 此外,如果树 图伊 对应于 我 -第位 N个 ,然后是树 图伊 包含2个^ 我 元素。

所以,如果你的结构中有11个元素,那么 N个 =11或1011(二进制),因此有三棵树- 图3 , 图1 ,和 图0 -分别有8个元素、2个元素和1个元素。

现在,我们插入一个元素 e类 进入我们的结构。插入之后,我们将有12个元素,或者1100个二进制元素。比较新的和以前的二进制字符串,我们看到 图3 没变,我们有棵新树 图2 有4种元素和树 图1 和 图0 被删除。我们建造新的树 图2 通过批量插入 e类 以及“下面”树中的所有元素 图2 ,它们是 图1 和 图0 .

这样,我们从静态基结构创建一个增量点查询结构。然而,像这样的“渐进式”静态结构以额外的 对数(N) 因素:

• 插入 N个 结构元素: O(N log(N)log(N))
• 结构的最近邻查询 N个 元素: O(对数(n)对数(n))

有。Scipy Cookbook网站包含一个完整的 kNN algorithm 可以增量更新的。

也许几行背景对任何感兴趣但不熟悉术语的人都有帮助。

kNN引擎由两种数据表示之一提供动力——多维数组(A)中存储的数据集中所有点之间的成对距离 距离矩阵 ),或 kd树 ,它将数据点本身存储在多维二叉树中。

基于kd树的KNN算法只需要两个操作:从数据集中创建树(类似于 训练 在其他ML算法中以批处理模式执行的步骤),然后搜索树以查找“最近的邻居”(类似于 测试 步骤)。

在KNN算法的上下文中进行在线或增量训练(前提是它基于kd树)意味着 插入节点 一棵已经建好的kd树。

回到SciPy食谱中的kd树实现:负责节点插入的特定代码行出现在注释行“insert node in kd Tree”之后(实际上,该注释之后的所有代码都指向节点插入)。

最后,在SciPy库的空间模块中实现了kd树( 坐姿空间 模块)调用KDTree( scipy.space.KDTree空间树 )但我不相信它支持节点插入,至少这样的函数不在文档中(我没有查看源代码)。