Поиск ближайшего соседа - Nearest neighbor search

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

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

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

Приложения

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

Распознавание образов - в частности, для оптического распознавания символов
Статистическая классификация - см. Алгоритм k-ближайшего соседа
Компьютерное зрение
Вычислительная геометрия - см. Задачу о ближайшей паре точек
Базы данных - например, поиск изображений на основе содержимого
Теория кодирования - см. Декодирование максимального правдоподобия
Сжатие данных - см. Стандарт MPEG-2
Роботизированное зондирование
Системы рекомендаций , например, см. Совместная фильтрация.
Интернет-маркетинг - см. Контекстную рекламу и поведенческий таргетинг.
Секвенирование ДНК
Проверка орфографии - предложение правильного написания
Обнаружение плагиата
Оценки подобия для прогнозирования карьерного роста профессиональных спортсменов.
Кластерный анализ - распределение набора наблюдений в подмножества (называемые кластерами), чтобы наблюдения в одном кластере были в некотором смысле похожими, обычно на основе евклидова расстояния.
Химическое сходство
Планирование движения на основе выборки

Методы

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

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

Линейный поиск

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

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

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

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

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

Методы приближения

Алгоритм приблизительного поиска ближайшего соседа может возвращать точки, расстояние от которых до запроса максимально превышает расстояние от запроса до ближайших точек. Привлекательность этого подхода заключается в том, что во многих случаях приблизительный ближайший сосед почти так же хорош, как и точный. В частности, если мера расстояния точно отражает понятие качества пользователя, то небольшие различия в расстоянии не должны иметь значения. ${\ displaystyle c}$

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

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

Методы основаны на жадном обходе графов соседних окрестностей, в которых каждая точка однозначно связана с вершиной . Поиск ближайших соседей к запросу q во множестве S принимает форму поиска вершины в графе . Основной алгоритм - жадный поиск - работает следующим образом: поиск начинается с вершины точки входа , вычисляя расстояния от запроса q до каждой вершины его окрестности , а затем находит вершину с минимальным значением расстояния. Если значение расстояния между запросом и выбранной вершиной меньше, чем расстояние между запросом и текущим элементом, то алгоритм переходит к выбранной вершине, и она становится новой точкой входа. Алгоритм останавливается, когда достигает локального минимума: вершины, окрестность которой не содержит вершину, которая находится ближе к запросу, чем сама вершина. ${\ Displaystyle G (V, E)}$ ${\ displaystyle x_ {i} \ in S}$ ${\ displaystyle v_ {i} \ in V}$ ${\ Displaystyle G (V, E)}$ ${\ displaystyle v_ {i} \ in V}$ ${\ displaystyle \ {v_ {j} :( v_ {i}, v_ {j}) \ in E \}}$

Идея графов близости соседства использовалась во многих публикациях, включая основополагающую статью Арьи и Маунта, в системе VoroNet для плоскости, в системе RayNet для и в алгоритмах Metrized Small World и HNSW для общего случая пространства с функцией расстояния. Этим работам предшествовала новаторская статья Туссена, в которой он ввел понятие графа относительных окрестностей . ${\ displaystyle \ mathbb {E} ^ {n}}$

Хеширование с учетом местоположения

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

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

Дерево крышки имеет теоретический предел , который основан на набор данные удвоения постоянная . Ограничение времени поиска составляет O ( c ¹² log n ), где c - константа расширения набора данных.

Прогнозируемый радиальный поиск

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

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

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

Поиск на основе сжатия / кластеризации

Подход VA-файла - это частный случай поиска на основе сжатия, когда каждый компонент функции сжимается равномерно и независимо. Оптимальным методом сжатия в многомерных пространствах является векторное квантование (VQ), реализованное посредством кластеризации. База данных кластеризована, и извлекаются наиболее "многообещающие" кластеры. Наблюдается огромный выигрыш по сравнению с VA-File, древовидными индексами и последовательным сканированием. Также обратите внимание на параллели между кластеризацией и LSH.

Варианты

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

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

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

Примерный ближайший сосед

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

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

Отношение расстояния ближайшего соседа

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

Фиксированный радиус рядом с соседями

Фиксированный радиус вблизи соседей - это проблема, когда нужно эффективно найти все точки, заданные в евклидовом пространстве, на заданном фиксированном расстоянии от заданной точки. Предполагается, что расстояние фиксировано, но точка запроса произвольна.

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

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

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

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

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

Шаша, Деннис (2004). Открытие высокой производительности во временных рядах . Берлин: Springer. ISBN 978-0-387-00857-8.

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

Nearest Neighbours and Similarity Search - сайт, посвященный учебным материалам, программному обеспечению, литературе, исследователям, открытым проблемам и событиям, связанным с поиском NN. Ведущий Юрий Лифшиц
Wiki поиска по подобию - коллекция ссылок, людей, идей, ключевых слов, статей, слайдов, кода и наборов данных о ближайших соседях.

Languages

In other projects