最邻近搜索

✍ dations ◷ 2025-04-04 11:48:56 #人工智能,算法

最邻近搜索(Nearest Neighbor Search, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间中给定一个点集和一个目标点 ∈ ,在中找到距离最近的点。很多情况下,为多维的欧几里得空间,距离由欧几里得距离或曼哈顿距离决定。

高德纳在《计算机程序设计艺术》(1973)一书的第三章中称之为邮局问题,即居民寻找离自己家最近的邮局。

最邻近搜索问题在很多领域中都有应用,包括:

最邻近搜索问题有若干种解决方案,这些算法的优劣决定于他们求解的时间复杂度和用来查找的数据结构的空间复杂度。一种通常的说法表述为“维数灾难”(curse of dimensionality),指对于在大维数的欧几里得空间里用最邻近搜索的话,无法找到多项式的算法和多对数的查找时间。

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

从七十年代起分支限界方法被应用于这个问题。对欧几里得空间来说,这个方法被称为空间索引或者空间访问方法。目前已发展出好几种分支限界方法。恐怕最简单的当属K-d树,它将查找空间不断将父节点包含的区域分为相邻的两部分,每部分包含原来区域中的一半点。求解时,从根节点开始在每个分叉点上对目标点进行计算,直到叶节点。对于给定的维度,查找时间复杂度为O(log )。R树数据结构能高效插入和删除节点,用来解决动态环境下的最邻近搜索。

对于一般的度量空间,分支限界方法被称为度量树,特别的例子有VP树和Bk树。

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

覆盖树有一个基于点集倍常量的理论界限。这个查找时间的界限是O(c12 log n),其中是点集的膨胀常数。

在最邻近搜索的几个变化中,最著名的是KNN(K-nearest neighbor algorithm)和ε近似最邻近查找(ε-approximate nearest neighbor search)。

KNN查找最邻近的K个点。这种方法常被用在预测分析中,用某点的一些临近点来对它估计和分类。

在一些应用中指需要有个对最邻近的猜测。这种情况下,我们可以用一个不保证能每次都返回绝对正确的最近点的算法,用来提高运算速度或节约存储空间。常常这样的算法大都能找到正确的最近点,但这大大取决于采用点集的分布。

采用近似查找的算法包括Best Bin First和Balanced Box-Decomposition Tree。

ε近似最邻近查找是目前流行的打破维数灾难的工具。

最邻近距离比不直接用目标点和邻近点的距离作为阈值,而是将与到前一个邻近点的距离相关的比值来作为阈值。这被用在基于内容的图像检索中,通过基于本地特征的相似性的“例子查找”来得到图像。更广泛的用途是在一些匹配问题中。

有时,我们需要找到在整个点集中距离所有点都最近的那个点。把最邻近搜索在所有点上运行一次自然能解决问题,但改进的策略能避免点集中距离信息的冗余,从而更高效地查找。比如:当我们算出了X到Y的距离,我们也同时得到了Y到X的距离,于是结果就能被以后的一次求解直接利用。

相关

  • 乙醇燃料燃料乙醇(英语:Ethanol fuel),也称乙醇燃料,又称生质酒精,是一种被广泛用于运输业的生物燃料。它和酒精饮料中的乙醇是同一类型的醇类。燃料乙醇由富含糖类物质的农作物酿制产生,可
  • 浑天说浑天说是中国古代的一种宇宙学说,同盖天说和宣夜说并称为“论天三家”。浑天说最早起源于战国时期,之后经过不断的发展和补充,逐渐完善。直至唐朝时亦有方炯著浑天赋驳斥宣天说
  • 新类尼古丁新烟碱(英语:Neonicotinoid,又称为类尼古丁)是一类和尼古丁相关的神经活性杀虫剂的总称。2013年4月29日,欧盟鉴于其对蜜蜂的巨大潜在危害(可能导致蜂群崩坏症候群的原因之一)而同意
  • 酬劳报酬(英语术语:remuneration,英语俗称:employment compensation),(工资和实物工资的合成),泛指雇员作出有偿劳动而获得的回报,包括工资及其他项目(例如津贴、保险、退休金),以及非现金的
  • 提格利尼亚语提格雷尼亚语(ትግርኛ, tigriññā)是一种闪语族的语言,主要是位于厄立特里亚中部的提格雷-提格雷尼亚语族(英语:Tigray-Tigrinya people),一般被称为“提格雷尼亚人”的族群使用
  • 军令部军令部 (日语假名:ぐんれいぶ,英文:Imperial Japanese Navy General Staff)为大日本帝国海军的参谋部,并为天皇直属单位。职掌为辅佐统帅,以及海军之作战与指挥。军令部始建于1884
  • 夏威夷并吞 (1898)纽兰兹决议(英语:Newlands Resolution)是美国国会于1898年7月4日通过的一项联合决议案,旨在吞并独立的夏威夷共和国。1900年,美国国会创建了夏威夷领地,它由民主党内华达州的国会
  • 2019冠状病毒病广西壮族自治区疫情2019冠状病毒病广西壮族自治区疫情,介绍2019冠状病毒病疫情中,在中华人民共和国广西壮族自治区发生的情况。以下数据皆由广西壮族自治区卫生健康委员会通报。2020年1月21日早
  • 建楠路建楠路(Jiannan Rd.)为高雄市楠梓区的东西向主要市区道路。起端楠梓车站,沿途跨越楠梓溪,末端于楠梓路口,续行兴楠路接国道一号楠梓交流道和往大社区。本道路连结楠梓车站与国道
  • 托隆尼亚家族托隆尼亚家族(意大利语:Torlonia),是一个起源于法国,发迹于罗马的贵族家族,该家族于18-19世纪透过协助梵谛冈进行财务管理而获得了巨大财富,由于其惊人的财富,在意大利语流行辞典中,