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

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

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

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

Приложения [ править ]

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

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

Методы [ править ]

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

Точные методы [ править ]

Линейный поиск [ править ]

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

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

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

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

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

Методы приближения [ править ]

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

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

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

Методы основаны на жадном обходе графов соседей близости, в которых каждая точка однозначно связана с вершиной . Поиск ближайших соседей к запросу 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 \}}$, а затем находит вершину с минимальным значением расстояния. Если значение расстояния между запросом и выбранной вершиной меньше, чем расстояние между запросом и текущим элементом, то алгоритм переходит к выбранной вершине, и она становится новой точкой входа. Алгоритм останавливается, когда достигает локального минимума: вершины, окрестность которой не содержит вершину, которая находится ближе к запросу, чем сама вершина.

Идея близости окрестностей графов была использована в нескольких публикациях, в том числе и семенная статьи Arya и горой, ^[11] в системе Воронца на плоскость, ^[12] в системе Raynet для , ^[13] и в Метризованном малом Алгоритмы World ^[14] и HNSW ^[8] для общего случая пространств с функцией расстояния. Этим работам предшествовала новаторская статья Туссена, в которой он ввел понятие графа относительных окрестностей . ^[15]${\ displaystyle \ mathbb {E} ^ {n}}$

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

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

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

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

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

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

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

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

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

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

Варианты [ править ]

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

k- Ближайшие соседи [ править ]

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

Примерный ближайший сосед [ править ]

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

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

Отношение расстояния до ближайшего соседа [ править ]

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

Фиксированный радиус рядом с соседями [ править ]

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

Все ближайшие соседи [ править ]

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

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

См. Также [ править ]

Ссылки [ править ]

Цитаты [ править ]

Источники [ править ]

• Эндрюс, Л. (ноябрь 2001 г.). «Шаблон для задачи ближайшего соседа» . Журнал пользователей C / C ++ . 19 (11): 40–49. ISSN  1075-2838 .
• Arya, S .; Mount, DM ; Нетаньяху, NS ; Сильверман, Р .; Ву, AY (1998). «Оптимальный алгоритм для приближенного поиска ближайшего соседа в фиксированных размерах». Журнал ACM . 45 (6): 891–923. CiteSeerX  10.1.1.15.3125 . DOI : 10.1145 / 293347.293348 .
• Beyer, K .; Goldstein, J .; Ramakrishnan, R .; Вал, У. (1999). «Когда имеет значение ближайший сосед?». Труды 7-го ICDT .
• Чен, Чжун-Мин; Линг, Ибэй (2002). "Оценщик на основе выборки для запросов Top-k". ICDE : 617–627.
• Самет, Х. (2006). Основы многомерных и метрических структур данных . Морган Кауфманн. ISBN 978-0-12-369446-1.
• Zezula, P .; Amato, G .; Dohnal, V .; Батько, М. (2006). Поиск подобия - подход в метрическом пространстве . Springer. ISBN 978-0-387-29146-8.

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с поиском ближайших соседей .

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