名字

没想好

FAST APPROXIMATE NEAREST NEIGHBORS(FLANN)

| Comments

最近需要使用最近友邻对高纬度的数据进行查询。在实验的过程中发现相对于高纬度的数据，kd树的查找速度其实没有线性查找来的快的，但是在大数据面前，线性查找的开销是很大的。我在网上找了一些相关资料，最后发现有个叫flann的库很不错，这个库可以让根据用户设置的查找准确性确定性和用户提供的数据自动生成一个合理高效的数据结构，让每次搜索的速度比线性查找快几个数量级，同时丢失一些准确度。程序上自动的对参数和数据结构的设置，让使用者不用担心该使用什么样的方法来解决问题。

网上有各类优化的最近友邻查找方法的论文，很多时候针对每个问题，用的方法不一样能产生不同的优化。通过论文实验报告，有2个方法是在比较不错的:

  • Randomized kd-tree algorithm: 不同于普通的kd-tree，这个方法是通过生成一组(大于等于1)的kd树来储存数据。该方法是通过在最之前的D次随机数据分割从而获得方差最大的分割(D=5)。当搜索的时候所有树会根据和数据的距离进行排列，距离近的树先被排查，只会查找固定数目的leaf。
  • Hierarchical k-means tree algorithm: 这个算法就是每次把数据进行k组分割(k-means) 每分割完的小组继续进行k组分割，直至每组数据小于K。这里随机部分是:首先查询数据会在树里过一遍，到达叶子的时候会生成一个优先队列，在队列里，查询数据到达最有叶子里的路径里的所有节点里没有访问过的branch, 队列的排列方式根据他们的中心位置和查询数据的距离从小到达排列。每次会从优先队列里提取一个节点从那里一直到树叶进行查找最近友邻，并同时在优先队列里插入新的未访问branch。查找的次数根据用户的提供的准确率百分比。

最有参数的自动选择没有怎么整明白(刻意关系)，貌似是使用10%的数据做一个检测，参数的选择会在固定的几个之中进行选择。用户使用的时候往往需要提供一些使用场景的参数，比如: 查找速度，建表速度，内存使用速度，更具这几个参数，他会自动给你找到最优的方法和方法参数。只提供使用场景的这些参数更直观的让不是怎么了解算法本身的人能够用最合适的算法做最合适的事了。具体cost计算方程在论文的程式1中。

使用的感脚良好，很简单，速度也靠谱。有python matlab 等的binding，opencv里还自带了这个库！在mac上安装matlab上安装的时候碰到几个小问题。安装步骤可以参考http://www.cs.uky.edu/~jacobs/tips/flann_matlab.html。当中需要装一个patch让matlab里的mex可以能编译。地址在这里装完之后更新下配置文件就能在matlab上编译c++文件了！

这个库的使用也是很容易的: 

[index, search_params, speedup] = flann_build_index(mat_train_data(:,:), struct('algorithm','autotuned', 'target_precision',0.95, 'build_weight',0.01, 'memory_weight',0))
%这里表示无所谓内存开销，建立索引开销重视一般。
%搜索        
[result, ndists] = flann_search(index, mat_train_data(:,1), 5, search_params);
%保存
flann_save_index(index,'train.idx')

不过还是有很蛋疼的地方，比如，有时候你得save一下再重新load之后才能搜索, 还有就是里面数据和matlab的数据表现形式不一样啊，让我废了好久才弄明白，一般数据分析总是会把数据一行行保存，每个row是一条数据。但是这里他是反人类的反过来了！使用的时候要非常注意。

参考:

  • 1 FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
  • 2 http://www.cs.uky.edu/~jacobs/tips/flann_matlab.html
  • 3 http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN

Comments