Python中的增量最近邻算法

15 投票

3 回答

8428 浏览

数据工程师

提问于 2025-04-16 07:35

有没有人知道在Python中有没有可以逐步更新的最近邻算法？我找到的那些，比如这个，似乎都是一次性处理的。有没有可能实现一个可以逐步更新的最近邻算法呢？

数据结构算法优化机器学习最近邻算法增量学习

3 个回答

确实有这样的东西。Scipy Cookbook 网站上有一个完整的 kNN 算法的实现，可以逐步更新。

为了帮助那些对这个话题感兴趣但不太了解相关术语的人，可能需要一些背景知识。

kNN 引擎主要依赖两种数据表示方式：一种是存储在多维数组中的所有数据点之间的距离（称为 距离矩阵），另一种是 kd-tree，它将数据点本身存储在一个多维的二叉树中。

基于 kd-tree 的 KNN 算法只需要进行两个操作：首先，从数据集中创建树（这类似于其他机器学习算法中的训练步骤），然后搜索这棵树以找到“最近邻居”（这类似于测试步骤）。

在 KNN 算法中，如果是基于 kd-tree 的在线或增量训练，意味着要往已经建好的 kd-tree 中 插入节点。

回到 SciPy Cookbook 中的 kd-Tree 实现：负责节点插入的具体代码出现在注释“插入节点到 kd-tree”之后（实际上，所有在这个注释之后的代码都是与节点插入相关的）。

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

回答于 2025-04-16 由 Python大师

分享举报

这内容虽然来得有点晚，但为了后人留个记录：

其实有一种方法可以把像KD树这样的批处理算法变成增量算法，这个方法叫做 静态到动态转换。

要生成一个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 被删除了。我们通过批量插入 e 以及所有在 T_2 “下面”的元素（也就是 T_1 和 T_0）来构建新的树 T_2。

通过这种方式，我们从一个静态的基础结构创建了一个增量的点查询结构。不过，将静态结构“增量化”时会有一个渐进的减速，表现为额外的 log(N) 因子：