matlab - 有人能告诉我 Matlab 使用的 kNN 搜索算法吗？

Question

我为最近邻搜索编写了一个基本的 O(n^2) 算法。与往常一样，Matlab 2013a 的 knnsearch(..) 方法运行得更快。

谁能告诉我他们在实现中使用了什么样的优化？

我可以阅读您可能指给我看的任何文档或论文。

PS:我了解到网站上的文档提到了关于 kd 树的论文作为引用。但据我所知，当列号小于 10 时，kd 树是默认选项。我的是 21。如果我错了，请纠正我。

Answer 1

MathWorks 在实现最近邻搜索方面所做的最大优化是所有困难的东西都在 MEX 文件中实现，作为编译的 C，而不是 MATLAB。

使用像 kNN 这样的算法(在我有限的理解中)是相当递归的并且难以向量化，这可能会带来这样的改进，即 O() 分析只在相当高的 n.

更详细地说，在引擎盖下，knnsearch 命令使用 createns 创建一个 NeighborSearcher 对象。默认情况下，当 X 少于 10 列时，这将是一个 KDTreeSearcher 对象，当 X 多于 10 列时，它将是ExhaustiveSearcher 对象(KDTreeSearcher 和 ExhaustiveSearcher 都是 NeighborSearcher 的子类)。

类 NeighbourSearcher 的所有对象都有一个方法 knnsearch(你很少会直接调用它，而是使用方便的命令 knnsearch 而不是这个方法)。 KDTreeSearcher 的 knnsearch 方法直接调用 MEX 文件以完成所有艰苦的工作。这位于 matlabroot\toolbox\stats\stats\@KDTreeSearcher\private\knnsearchmex.mexw64 中。

据我所知，此 MEX 文件执行的算法几乎与文档页面中引用的 Friedman、Bentely 和 Finkel 的论文中描述的算法相同，没有结构变化。正如论文标题所暗示的，该算法是 O(log(n)) 而不是 O(n^2)。遗憾的是，无法通过检查来确认 MEX 文件的内容。