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

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

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

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

Приложения

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

в пространствах с малым

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

радиальный

В особом случае, когда данные представляют собой плотную трехмерную карту геометрических точек, геометрия проекции метода зондирования может использоваться для значительного упрощения задачи поиска.Этот подход требует, чтобы 3D-данные были организованы посредством проекции на двумерную сетку, и предполагает, что данные пространственно гладкие в соседних ячейках сетки, за исключением границ объекта.Эти предположения справедливы при работе с данными 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 ^п норма ) и n точек в этом пространстве, ближайший сосед каждой точки может быть найден за время O ( n log n ), а m ближайших соседей каждой точки могут быть найдены за время O ( mn log n ).

См. также

• Шаровое дерево
• Задача о ближайшей паре точек
• Кластерный анализ
• Поиск изображений на основе контента
• Проклятие размерности
• Цифровая обработка сигналов
• Уменьшение размеров
• Фиксированный радиус рядом с соседями
• Фурье-анализ
• Обучение на основе экземпляров
• k - алгоритм ближайшего соседа
• Линейный метод наименьших квадратов
• Хеширование с учетом местоположения
• Максимальный поиск внутреннего продукта
• Минхеш
• Многомерный анализ
• Интерполяция ближайшего соседа
• Присоединение соседа
• Анализ главных компонентов
• Поиск диапазона
• Обучение по сходству
• Разложение по сингулярным значениям
• Разреженная распределенная память
• Статистическое расстояние
• Временной ряд
• Диаграмма Вороного
• Вейвлет

Ссылки

Источники

• Эндрюс, Л. (ноябрь 2001 г.). «Шаблон задачи о ближайшем соседе» . Журнал пользователей C/C++ . 19 (11): 40–49. ISSN   1075-2838 .
• Арья, С.; Маунт, ДМ ; Нетаньяху, Н.С. ; Сильверман, Р .; Ву, А.Ю. (1998). «Оптимальный алгоритм для приблизительного поиска ближайших соседей в фиксированных измерениях». Журнал АКМ . 45 (6): 891–923. CiteSeerX   10.1.1.15.3125 . дои : 10.1145/293347.293348 . S2CID   8193729 .
• Бейер, К.; Гольдштейн, Дж.; Рамакришнан, Р.; Шафт, У. (1999). «Когда имеет смысл ближайший сосед?». Материалы 7-й МКДТ .
• Чен, Чунг-Мин; Лин, Ибэй (2002). «Оценщик на основе выборки для запросов Top-k». ИКДЕ : 617–627.
• Самет, Х. (2006). Основы многомерных и метрических структур данных . Морган Кауфманн. ISBN  978-0-12-369446-1 .
• Зезула, П.; Амато, Г.; Донал, В.; Батько, М. (2006). Поиск по сходству – подход метрического пространства . Спрингер. ISBN  978-0-387-29146-8 .

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

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

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

• «Ближайшие соседи и поиск по сходству» - веб-сайт, посвященный образовательным материалам, программному обеспечению, литературе, исследователям, открытым проблемам и событиям, связанным с поиском NN. Ведёт Юрий Лифшиц
• Wiki Search по сходству - коллекция ссылок, людей, идей, ключевых слов, статей, слайдов, кода и наборов данных о ближайших соседях.