最近的邻居搜索

最近的邻居搜索（NNS），作为接近搜索的一种形式，是寻找给定集合中与给定点最接近（或最相似）的点的优化问题。紧密性通常用一个相似度函数来表示：对象越不相似，函数值越大。从形式上看，最近邻居（NN）搜索问题定义如下：给定空间M中的点集合S和查询点q∈M，找到S中离q最近的点。DonaldKnuth在《计算机编程艺术》（1973）第三卷中称其为邮局问题，指的是给住宅分配最近的邮局的应用。这个问题的一个直接概括是k-NN搜索，我们需要找到k个最近的点。最常见的是，M是一个度量空间，异质性被表示为距离度量，它是对称的并满足三角形不等式。更常见的是，M被认为是d维矢量空间，其中的异同性是用欧氏距离、曼哈顿距离或其他距离度量来衡量。然而，异同度函数可以是任意的。一个例子是不对称的布雷格曼发散，对它来说，三角形不等式不成立。

最近的邻居搜索问题出现在许多应用领域，包括模式识别–特别是光学字符识别统计分类–见k-近邻算法计算机视觉–用于点云注册计算几何–见最接近的一对点问题数据库–如基于内容的图像检索编码理论–见xxx似然解码语义搜索数据压缩–见MPEG-2标准机器人感应推荐系统，如见协作过滤网络营销–见上下文广告和行为定位DNA测序拼写检查–建议正确的拼写剽窃检测预测专业运动员职业道路的相似度分数聚类分析–将一组观测值分配到子集（称为聚类）中，使同一聚类中的观测值在某种意义上相似，通常基于欧氏距离化学相似度基于采样的运动规划方法已经提出了NNS问题的各种解决方案。算法的质量和实用性由查询的时间复杂性以及必须维护的任何搜索数据结构的空间复杂性决定。通常被称为”维度诅咒”的非正式观察指出，在高维欧几里得空间中，没有通用的精确解决NNS问题的方法，需要使用多项式的预处理和多项式的搜索时间。

线性搜索NNS问题最简单的解决方案是计算从查询点到数据库中每一个其他点的距离，并跟踪到目前为止的最佳结果。这种算法，有时被称为天真方法，其运行时间为O(dN)，其中N是S的cardinality，d是S的维度。没有搜索数据结构需要维护，所以线性搜索除了数据库的存储之外没有空间复杂性。平均而言，天真搜索在高维空间上可以胜过空间划分方法。

在距离比较中不需要xxx距离，只需要相对距离。在几何坐标系中，通过省略两个坐标之间的距离计算中的平方根计算，可以xxx加快距离计算的速度。距离比较仍然会产生相同的结果。

自20世纪70年代以来，分支和边界方法已被应用于该问题。在欧氏空间的情况下，这种方法包含了空间索引或空间访问方法。为了解决NNS问题，已经开发了几种空间划分方法。也许最简单的是k-d树，它反复地将搜索空间分成两个区域，其中包含父区域的一半的点。查询是通过从根到叶的树的遍历来进行的，在每个分割处评估查询点。根据查询中指定的距离，可能包含命中的相邻分支也需要被评估。对于恒定维度的查询时间，在随机分布点的情况下，平均复杂度为O(logN)，最坏的情况下复杂度为O(kN(1-1/k))另外，R树数据结构被设计为支持动态背景下的最近邻搜索，因为它有高效的插入和删除算法，如R*树。R-树不仅可以产生欧氏距离的最近邻，而且还可以用于其他距离。在一般公制空间的情况下，分支和约束的方法被称为公制树方法。特别的例子包括vp-tree和BK-tree方法。使用一组点