stringtranslate.com

Поиск ближайшего соседа

Поиск ближайшего соседа ( NNS ), как форма поиска близости , является задачей оптимизации поиска точки в заданном наборе, которая ближе всего (или наиболее похожа) на заданную точку. Близость обычно выражается в терминах функции несходства: чем менее похожи объекты, тем больше значения функции.

Формально задача поиска ближайшего соседа (NN) определяется следующим образом: дано множество S точек в пространстве M и точка запроса q  ∈  M , найти ближайшую точку в S к q . Дональд Кнут в т. 3 книги «Искусство программирования» (1973) назвал ее задачей почтового отделения , имея в виду приложение назначения ближайшему почтовому отделению места жительства. Прямым обобщением этой задачи является поиск k -NN, где нам нужно найти k ближайших точек.

Чаще всего M является метрическим пространством , а несходство выражается как метрика расстояния , которая симметрична и удовлетворяет неравенству треугольника . Еще чаще M принимается как d -мерное векторное пространство , где несходство измеряется с помощью евклидова расстояния , манхэттенского расстояния или другой метрики расстояния . Однако функция несходства может быть произвольной. Одним из примеров является асимметричная дивергенция Брегмана , для которой неравенство треугольника не выполняется. [1]

Приложения

Задача поиска ближайшего соседа возникает во многих областях применения, в том числе:

Методы

Были предложены различные решения проблемы NNS. Качество и полезность алгоритмов определяются временной сложностью запросов, а также пространственной сложностью любых структур данных поиска, которые необходимо поддерживать. Неформальное наблюдение, обычно называемое проклятием размерности, гласит, что не существует универсального точного решения для NNS в многомерном евклидовом пространстве с использованием полиномиальной предварительной обработки и полилогарифмического времени поиска.

Точные методы

Простейшим решением проблемы NNS является вычисление расстояния от точки запроса до каждой другой точки в базе данных, отслеживая «лучшее на данный момент». Этот алгоритм, иногда называемый наивным подходом, имеет время выполнения O ( dN ), где N — мощность S , а d — размерность S . Нет структур данных поиска, которые нужно поддерживать, поэтому линейный поиск не имеет пространственной сложности за пределами хранилища базы данных. Наивный поиск может, в среднем, превосходить подходы с разделением пространства на пространствах более высокой размерности. [5]

Для сравнения расстояний не требуется абсолютное расстояние, требуется только относительное расстояние. В геометрических системах координат расчет расстояния можно значительно ускорить, исключив вычисление квадратного корня из расчета расстояния между двумя координатами. Сравнение расстояний все равно даст идентичные результаты.

Разделение пространства

С 1970-х годов к проблеме применяется метод ветвей и границ . В случае евклидова пространства этот подход охватывает пространственный индекс или методы пространственного доступа. Для решения проблемы NNS было разработано несколько методов разбиения пространства . Возможно, самым простым является дерево kd , которое итеративно делит пространство поиска на две области, содержащие половину точек родительской области. Запросы выполняются посредством обхода дерева от корня до листа путем оценки точки запроса при каждом разбиении. В зависимости от расстояния, указанного в запросе, может также потребоваться оценка соседних ветвей, которые могут содержать попадания. Для времени запроса постоянного измерения средняя сложность составляет O (log  N ) [6] в случае случайно распределенных точек, сложность в худшем случае составляет O ( kN ^(1-1/ k )) [7] В качестве альтернативы структура данных R-дерева была разработана для поддержки поиска ближайшего соседа в динамическом контексте, поскольку она имеет эффективные алгоритмы для вставок и удалений, такие как дерево R* . [8] R-деревья могут выдавать ближайших соседей не только для евклидова расстояния, но и могут использоваться с другими расстояниями.

В случае общего метрического пространства подход ветвей и границ известен как подход метрического дерева . Конкретные примеры включают методы vp-tree и BK-tree .

Используя набор точек, взятых из трехмерного пространства и помещенных в дерево BSP , и заданную точку запроса, взятую из того же пространства, возможное решение задачи поиска ближайшей точки облака точек к точке запроса дается в следующем описании алгоритма.

(Строго говоря, такой точки может не быть, потому что она может быть не уникальной. Но на практике обычно нас интересует только нахождение любой из подмножества всех точек облака точек, которые существуют на кратчайшем расстоянии от заданной точки запроса.) Идея состоит в том, чтобы для каждого разветвления дерева предположить, что ближайшая точка в облаке находится в полупространстве, содержащем точку запроса. Это может быть не так, но это хорошая эвристика. После рекурсивного прохождения всех трудностей решения задачи для угаданного полупространства теперь сравните расстояние, возвращаемое этим результатом, с кратчайшим расстоянием от точки запроса до плоскости разбиения. Это последнее расстояние — это расстояние между точкой запроса и ближайшей возможной точкой, которая может существовать в полупространстве, в котором не производился поиск. Если это расстояние больше, чем возвращенное в предыдущем результате, то, очевидно, нет необходимости искать в другом полупространстве. Если есть такая необходимость, то вы должны пройти через трудности решения проблемы для другого полупространства, а затем сравнить его результат с предыдущим результатом, а затем вернуть правильный результат. Производительность этого алгоритма ближе к логарифмическому времени, чем к линейному времени, когда точка запроса находится вблизи облака, потому что, поскольку расстояние между точкой запроса и ближайшей точкой облака точек приближается к нулю, алгоритму нужно только выполнить поиск, используя точку запроса в качестве ключа, чтобы получить правильный результат.

Методы аппроксимации

Приблизительный алгоритм поиска ближайшего соседа позволяет возвращать точки, расстояние которых от запроса в большинстве случаев больше расстояния от запроса до его ближайших точек. Привлекательность этого подхода заключается в том, что во многих случаях приблизительный ближайший сосед почти так же хорош, как и точный. В частности, если мера расстояния точно отражает понятие качества пользователя, то небольшие различия в расстоянии не должны иметь значения. [9]

Жадный поиск в графах соседства по близости

Методы графов близости (такие как навигационные графы малого мира [10] и HNSW [11] [12] ) считаются на данный момент передовыми методами приблизительного поиска ближайших соседей.

Методы основаны на жадном обходе в графах окрестностей близости , в которых каждая точка однозначно связана с вершиной . Поиск ближайших соседей к запросу q в множестве S принимает форму поиска вершины в графе . Основной алгоритм — жадный поиск — работает следующим образом: поиск начинается с вершины точки входа путем вычисления расстояний от запроса q до каждой вершины его окрестности , а затем находит вершину с минимальным значением расстояния. Если значение расстояния между запросом и выбранной вершиной меньше, чем между запросом и текущим элементом, то алгоритм переходит к выбранной вершине, и она становится новой точкой входа. Алгоритм останавливается, когда достигает локального минимума: вершины, окрестность которой не содержит вершины, которая ближе к запросу, чем сама вершина.

Идея графов близости соседей была использована в многочисленных публикациях, включая основополагающую работу Арьи и Маунта [13] в системе VoroNet для плоскости, [14] в системе RayNet для , [15] и в алгоритмах Navigable Small World, [10] Metrized Small World [16] и HNSW [11] [12] для общего случая пространств с функцией расстояния. Этим работам предшествовала пионерская работа Туссэна, в которой он ввел концепцию графа относительной близости . [17]

Хеширование с учетом локальности

Локальное чувствительное хеширование (LSH) — это метод группировки точек в пространстве в «корзины» на основе некоторой метрики расстояния, действующей на точки. Точки, которые находятся близко друг к другу в рамках выбранной метрики, сопоставляются с одной и той же корзиной с высокой вероятностью. [18]

Поиск ближайшего соседа в пространствах с малой внутренней размерностью

Дерево покрытия имеет теоретическую границу, которая основана на константе удвоения набора данных. Граница времени поиска составляет O ( c 12  log  n ), где c — константа расширения набора данных.

В особом случае, когда данные представляют собой плотную 3D-карту геометрических точек, проекционная геометрия метода зондирования может быть использована для значительного упрощения проблемы поиска. Этот подход требует, чтобы 3D-данные были организованы путем проекции на двумерную сетку, и предполагает, что данные пространственно гладкие по соседним ячейкам сетки, за исключением границ объектов. Эти предположения справедливы при работе с данными 3D-датчиков в таких приложениях, как геодезия, робототехника и стереозрение, но могут не выполняться для неорганизованных данных в целом. На практике этот метод имеет среднее время поиска O ( 1 ) или O ( K ) для задачи k -ближайшего соседа при применении к данным стереозрения реального мира. [4]

Файлы векторной аппроксимации

В многомерных пространствах структуры индексации деревьев становятся бесполезными, поскольку все больший процент узлов необходимо исследовать в любом случае. Для ускорения линейного поиска сжатая версия векторов признаков, хранящихся в оперативной памяти, используется для предварительной фильтрации наборов данных в первом запуске. Окончательные кандидаты определяются на втором этапе с использованием несжатых данных с диска для расчета расстояния. [19]

Подход VA-файла является особым случаем поиска на основе сжатия, где каждый компонент признака сжимается равномерно и независимо. Оптимальным методом сжатия в многомерных пространствах является векторное квантование (VQ), реализованное посредством кластеризации. База данных кластеризована, и извлекаются наиболее «многообещающие» кластеры. Были отмечены огромные преимущества по сравнению с VA-файлом, индексами на основе дерева и последовательным сканированием. [20] [21] Также обратите внимание на параллели между кластеризацией и LSH.

Варианты

Существует множество вариантов задачи NNS, и два наиболее известных — это поиск k -ближайших соседей и поиск ε-приближенных ближайших соседей .

k -ближайшие соседи

Поиск k -ближайших соседей определяет k- ближайших соседей для запроса. Этот метод обычно используется в предиктивной аналитике для оценки или классификации точки на основе консенсуса ее соседей. Графы k -ближайших соседей — это графы, в которых каждая точка связана со своими k- ближайшими соседями.

Приблизительный ближайший сосед

В некоторых приложениях может быть приемлемо получить "хорошее предположение" о ближайшем соседе. В таких случаях мы можем использовать алгоритм, который не гарантирует возврата фактического ближайшего соседа в каждом случае, в обмен на улучшение скорости или экономию памяти. Часто такой алгоритм находит ближайшего соседа в большинстве случаев, но это сильно зависит от запрашиваемого набора данных.

Алгоритмы, которые поддерживают приблизительный поиск ближайшего соседа, включают локально-чувствительное хеширование , поиск по лучшему корню и сбалансированное дерево на основе разложения ящиков. [22]

Коэффициент расстояния до ближайшего соседа

Коэффициент расстояния ближайшего соседа не применяет порог к прямому расстоянию от исходной точки до соседа-претендента, а к его отношению в зависимости от расстояния до предыдущего соседа. Он используется в CBIR для извлечения изображений через «запрос по образцу», используя сходство между локальными особенностями. В более общем плане он участвует в нескольких задачах сопоставления .

Фиксированный радиус вблизи соседей

Ближайшие соседи с фиксированным радиусом — это проблема, в которой требуется эффективно найти все заданные точки в евклидовом пространстве в пределах заданного фиксированного расстояния от указанной точки. Расстояние предполагается фиксированным, но точка запроса произвольна.

Все ближайшие соседи

Для некоторых приложений (например, оценка энтропии ) у нас может быть N точек данных и мы хотим узнать, какой из них является ближайшим соседом для каждой из этих N точек . Конечно, этого можно достичь, запустив поиск ближайшего соседа один раз для каждой точки, но улучшенной стратегией был бы алгоритм, который использует избыточность информации между этими N запросами для получения более эффективного поиска. Простой пример: когда мы находим расстояние от точки X до точки Y , это также сообщает нам расстояние от точки Y до точки X , поэтому одно и то же вычисление можно повторно использовать в двух разных запросах.

При наличии фиксированного измерения, полуопределенной положительной нормы (тем самым включающей каждую норму L p ) и n точек в этом пространстве ближайший сосед каждой точки может быть найден за время O ( n  log  n ), а m ближайших соседей каждой точки могут быть найдены за время O ( mn  log  n ). [23] [24]

Смотрите также

Ссылки

Цитаты

  1. ^ Cayton, Lawrence (2008). "Быстрый поиск ближайшего соседа для расхождений Брегмана". Труды 25-й Международной конференции по машинному обучению . С. 112–119. doi :10.1145/1390156.1390171. ISBN 9781605582054. S2CID  12169321.
  2. ^ Цю, Дэюань, Стефан Мэй и Андреас Нюхтер. «GPU-ускоренный поиск ближайшего соседа для 3D-регистрации». Международная конференция по системам компьютерного зрения. Springer, Берлин, Гейдельберг, 2009.
  3. ^ Беккер, Дукас, Гама и Лаарховен. «Новые направления в поиске ближайшего соседа с приложениями к решеточному просеиванию». Труды двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (стр. 10–24). Общество промышленной и прикладной математики.
  4. ^ ab Bewley, A.; Upcroft, B. (2013). Преимущества использования проекционной структуры для сегментации плотных трехмерных облаков точек (PDF) . Австралийская конференция по робототехнике и автоматизации.
  5. ^ Вебер, Роджер; Шек, Ханс-Дж.; Блотт, Стивен (1998). «Количественный анализ и исследование производительности методов поиска сходства в многомерных пространствах» (PDF) . Труды VLDB '98 24-й Международной конференции по сверхбольшим базам данных . С. 194–205.
  6. ^ Эндрю Мур. "Вводный учебник по деревьям KD" (PDF) . Архивировано из оригинала (PDF) 2016-03-03 . Получено 2008-10-03 .
  7. ^ Ли, Д.Т .; Вонг, К.К. (1977). «Анализ наихудшего случая для поиска регионов и частичных регионов в многомерных бинарных деревьях поиска и сбалансированных квадродеревьях». Acta Informatica . 9 (1): 23–29. doi :10.1007/BF00263763. S2CID  36580055.
  8. ^ Руссопулос, Н.; Келли, С.; Винсент, ФДР (1995). "Запросы ближайшего соседа". Труды международной конференции ACM SIGMOD 1995 года по управлению данными – SIGMOD '95 . стр. 71. doi : 10.1145/223784.223794 . ISBN 0897917316.
  9. ^ Андони, А.; Индик, П. (2006-10-01). «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерностях». 2006 47-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS'06) . стр. 459–468. CiteSeerX 10.1.1.142.3471 . doi :10.1109/FOCS.2006.49. ISBN  978-0-7695-2720-8.
  10. ^ ab Малков, Юрий; Пономаренко, Александр; Логвинов, Андрей; Крылов, Владимир (2012), Наварро, Гонсало; Пестов, Владимир (ред.), "Масштабируемый распределенный алгоритм для приближенного поиска ближайшего соседа в многомерных общих метрических пространствах", Поиск сходства и приложения , т. 7404, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 132–147, doi :10.1007/978-3-642-32153-5_10, ISBN 978-3-642-32152-8, получено 2024-01-16
  11. ^ ab Малков, Юрий; Яшунин, Дмитрий (2016). «Эффективный и надежный поиск приближенного ближайшего соседа с использованием иерархических графов Navigable Small World». arXiv : 1603.09320 [cs.DS].
  12. ^ ab Малков, Ю. А.; Яшунин, ДА (2020-04-01). «Эффективный и надежный приближенный поиск ближайших соседей с использованием иерархических навигируемых графов малого мира». Труды IEEE по анализу шаблонов и машинному интеллекту . 42 (4): 824–836. arXiv : 1603.09320 . doi : 10.1109/TPAMI.2018.2889473. ISSN  0162-8828. PMID  30602420.
  13. ^ Арья, Сунил; Маунт, Дэвид (1993). «Приблизительные запросы ближайшего соседа в фиксированных измерениях». Труды Четвертого ежегодного симпозиума {ACM/SIGACT-SIAM} по дискретным алгоритмам, 25–27 января 1993 г., Остин, Техас. : 271–280.
  14. ^ Оливье, Бомон; Кермаррек, Энн-Мари; Маршал, Лорис; Ривьер, Этьен (2006). "Voro Net: масштабируемая объектная сеть на основе тесселяций Вороного" (PDF) . 2007 IEEE International Parallel and Distributed Processing Symposium . Vol. RR-5833. pp. 23–29. doi :10.1109/IPDPS.2007.370210. ISBN 1-4244-0909-8. S2CID  8844431.
  15. ^ Оливье, Бомон; Кермаррек, Энн-Мари; Ривьер, Этьен (2007). «Многомерные одноранговые наложения: аппроксимация сложных структур». Принципы распределенных систем . Конспект лекций по информатике. Том 4878. С. 315–328. CiteSeerX 10.1.1.626.2980 . doi :10.1007/978-3-540-77096-1_23. ISBN  978-3-540-77095-4.
  16. ^ Малков, Юрий; Пономаренко, Александр; Крылов, Владимир; Логвинов, Андрей (2014). «Алгоритм приближенного ближайшего соседа на основе навигабельных графов малого мира». Информационные системы . 45 : 61–68. doi :10.1016/j.is.2013.10.006. S2CID  9896397.
  17. ^ Туссен, Годфрид (1980). «Граф относительного соседства конечного плоского множества». Pattern Recognition . 12 (4): 261–268. Bibcode : 1980PatRe..12..261T. doi : 10.1016/0031-3203(80)90066-7.
  18. ^ А. Раджараман и Дж. Ульман (2010). «Изучение массивных наборов данных, Гл. 3».
  19. ^ Вебер, Роджер; Блотт, Стивен. «Структура данных на основе аппроксимации для поиска сходства» (PDF) . S2CID  14613657. Архивировано из оригинала (PDF) 2017-03-04. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  20. ^ Рамасвами, Шарад; Роуз, Кеннет (2007). «Адаптивное ограничение кластерного расстояния для поиска сходства в базах данных изображений». ICIP .
  21. ^ Рамасвами, Шарад; Роуз, Кеннет (2010). «Адаптивное ограничение кластерного расстояния для высокоразмерной индексации». TKDE .
  22. ^ Арья, С.; Маунт, Д.М .; Нетаньяху, Н.С.; Сильверман, Р.; Ву, А. (1998). "Оптимальный алгоритм для приблизительного поиска ближайшего соседа" (PDF) . Журнал ACM . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . doi :10.1145/293347.293348. S2CID  8193729. Архивировано из оригинала (PDF) 2016-03-03 . Получено 2009-05-29 . 
  23. ^ Кларксон, Кеннет Л. (1983), «Быстрые алгоритмы для задачи всех ближайших соседей», 24-й симпозиум IEEE по основам компьютерной науки (FOCS '83) , стр. 226–232, doi :10.1109/SFCS.1983.16, ISBN 978-0-8186-0508-6, S2CID  16665268.
  24. ^ Вайдья, П. М. (1989). «Алгоритм O(n log n) для задачи всех ближайших соседей». Дискретная и вычислительная геометрия . 4 (1): 101–115. doi : 10.1007/BF02187718 .

Источники

Дальнейшее чтение

Внешние ссылки

На Викискладе есть медиафайлы по теме « Поиск ближайших соседей» .