Roy*_*Roy 4 matlab machine-learning knn
我为最近邻搜索编写了一个基本的O(n ^ 2)算法.像往常一样,Matlab 2013a的knnsearch(..)方法工作得更快.
有人能告诉我他们在实施中使用了哪种优化方法？
我可以阅读您可能指向我的任何文档或论文.
PS:我理解网站上的文档提到了关于kd树的论文作为参考.但据我所知,当列数小于10时,kd树是默认选项.我的是21.如果我错了,请纠正我.
MathWorks在实现最近邻搜索时所做的最大优化是所有硬件都在MEX文件中实现,如编译C,而不是MATLAB.
使用诸如kNN之类的算法(在我有限的理解中)是非常递归的并且难以向量化,这可能会给出这样的改进,即O()分析仅与相当高的相关n.
更详细地说,该knnsearch命令用于createns创建NeighborSearcher对象.默认情况下,当X具有小于10组的列,这将是一个KDTreeSearcher对象,并且当X有超过10列这将是一个ExhaustiveSearcher对象(包括KDTreeSearcher和ExhaustiveSearcher是的子类NeighborSearcher).
类的所有对象NeighbourSearcher都有一个方法knnsearch(你很少直接调用它,而是使用方便命令knnsearch而不是这个方法).该knnsearch方法KDTreeSearcher调用直出为所有辛勤工作的MEX文件.它位于matlabroot\toolbox\stats\stats\@KDTreeSearcher\private\knnsearchmex.mexw64中.
据我所知,这个MEX文件几乎执行文档页面中引用的Friedman,Bentely和Finkel文章中描述的算法,没有任何结构变化.正如本文的标题所暗示的,该算法是O(log(n))而不是O(n ^ 2).遗憾的是,MEX文件的内容无法进行检查以确认.