1 minute read

一、 NNS

  1. 介绍
    • 最近邻搜索（Nearest Neighbor Search）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题；
      高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮局；

  2. 定义
    在特征空间 M 中给定一个点集 S 和一个目标点 q ∈ M，在 S 中找到与 q 相似度最高的 K 个点；
    M 一般为多维的欧几里得空间，相似度为欧几里得距离或曼哈顿距离；

  3. 应用
    模式识别，特别是光学字符识别；
    统计分类，参见KNN（k-nearest neighbor algorithm）；
    计算机视觉，如图像检索；
    数据库，如基于内容的检索；
    编码理论，见最大似然编码；
    数据压缩，见MPEG-2标准；
    向导系统；
    网络营销；
    DNA测序；
    拼写检查，建议正确拼写；
    剽窃侦查；
    相似比分算法，用来推断运动员的职业表现；

二、实现

1. 线性查找

最简单的最邻近搜索便是遍历整个点集，计算它们和目标点之间的距离，同时记录目前的最近点。这样的算法较为初级，可以为较小规模的点集所用，但是对于点集的尺寸和空间的维数稍大的情况不适用。线性查找所需时间为O(Nd)，其中 N 是 S 中的样本数，d 是单个样本点的维度；由于不需要建立数据结构，所以线性查找没有存储空间复杂度的问题；

2. 空间分割

最简单的就是 K-d 树，它递归地将查找空间分为相邻的两部分，每部分包含原来区域中的一半点怕；求解时，从根节点开始在每个分叉点上对目标点进行计算，直到叶节点；对于给定的维度，查找时间复杂度为O(logN)；
R 树能高效插入和删除节点，用来解决动态环境下的最邻近搜索；
R* 树；
VP 树；
Bk 树；
metric 树；
Ball 树；
cover 树；
MVP 树；

3. LSH

LSH（Locality sensitive hashing）通过对点进行某种度量操作后将点分组散列在不同的次点集中；在这种度量下相互间距离较近的点被分在同一个次点集的可能性较高；

三、NNS 变种

最著名的是 KNN（K-nearest neighbor algorithm）和 ε 近似最邻近查找（ε-approximate nearest neighbor search）；

  1. KNN
    KNN 查找最邻近的 K 个点；这种方法常被用在预测分析中，用某点的一些临近点来对它估计和分类；
  2. 近似最邻近查找
    通过减低准确度来提高运算速度或节约存储空间，其准确度大都取决于采用点集的分布；
    代表算法有 Best Bin First 和 Balanced Box-Decomposition Tree，ε近似最邻近查找；
    其中ε近似最邻近查找是目前解决维数灾难最好的工具；
  3. 最邻近距离比
    最邻近距离比不直接用目标点和邻近点的距离作为阈值，而是将与到前一个邻近点的距离相关的比值来作为阈值；这被用在基于内容的图像检索中，用于找到相似图像；跟直接用距离有啥区别啊
  4. 全局最近点
    有时，我们需要找到在整个点集中距离所有点都最近的那个点。把最邻近搜索在所有点上运行一次自然能解决问题，但改进的策略能避免点集中距离信息的冗余，从而更高效地查找。比如：当我们算出了X到Y的距离，我们也同时得到了Y到X的距离，于是结果就能被以后的一次求解直接利用；

四、 实践

五、 思考

:o: NNS 和 KNN 有啥区别呀
硬分呢这是

TOP

附录

A. 资料

  1. Nearest Neighbors and Similarity Search - a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits.
  2. Metric Spaces Library - An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez.
  3. ANN - A Library for Approximate Nearest Neighbor Searching by David M. Mount and Sunil Arya.
  4. STANN - A Simple Threaded Approximate Nearest Neighbor Search Library in C++ by Michael Connor and Piyush Kumar.
  5. MESSIF - Metric Similarity Search Implementation Framework by Michal Batko and David Novak.
  6. OBSearch - Metric Similarity Search（distributed, GPL）. Implementation by Arnoldo Muller, developed during Google Summer of Code 2007.
  7. Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 8. Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN：0-387-29146-6.
  8. kd-tree 和 ball-tree https://www.zhihu.com/question/30957691
  9. 图像检索：再叙ANN Search

Comments

You May Also Enjoy