|
http://blog.csdn.net/guoyilin/article/details/39668183 2014 当数据个数比较大的时候，线性搜索寻找KNN的时间开销太大，而且需要读取所有的数据在内存中，这是不现实的。因此，实际工程上，使用近似最近邻也就是ANN问题。 这里总结下常见的使用方法和相关的论文。每个方法都会有自己的优点。 第一, Tree-Based Method， 筛选候选子集。 1. Vantage-Point Tree Paper: http://www./pny/papers/vptree/vptree/ 算法的代码和说明：http:///blog/index.php?id=130 实际使用VP tree中可能回溯会比较多，特别是nearest neighbor's distance is not very small compare with farthest distance in all data. 2. K-d Tree kd tree 适用于维度比较低的情况，因为在维度高的情况下，kdtree的深度将会非常深，这样的tree的效率太低， 存储空间也大。 3. Randomized K-d tree 见lowe 的 FLANN算法，http://www.cs./research/flann/， 思想大概是用forest的思想来提升kdtree的recall 4. Random Projection Tree 采用随机投影方法将每个节点中的数据投影到一维子空间，在子空间中进行划分。该方法实践中效果比较好。算法性能比较优秀。 paper： Large-scale music similarity search with spatial trees 实验发现投影方向的选择可以限制在-1, 0,1之间，在保证效果的情况下，进一步缩小投影方向的存储空间。 第二，lsh方法 根据使用的距离度量方法，选择合适的lsh。 要注意在保证recall的情况下，该算法可能几乎是线性搜索。 第三，Product Quantization see paper: Product quantization for nearest neighbor search. 方法比较巧妙，后续有不少论文，主要思想是在子空间中进行k-means，这样划分的空间比较密集，利用k-means中心点能够对数据进行较好的近似，能够有效压缩数据。缺点是query的的时候，需要和每个数据进行比较。 当然论文提出可以先筛选初步的子集，在子集中使用该方法。实验效果比较该算法性能还不错。
可能还有更多的方法谈论该问题。后续补上。
|
|
|
