Поиск ближайшего соседа ( 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 (журнал N ) [4] в случае случайно распределенных точек, в худшем случае сложность O ( кН ^ (1-1 / к )) [5] В качестве альтернативы в R-дерево данных Структура была разработана для поддержки поиска ближайшего соседа в динамическом контексте, поскольку она имеет эффективные алгоритмы для вставки и удаления, такие как дерево R * . [6] R-деревья могут давать ближайших соседей не только для евклидова расстояния, но также могут использоваться с другими расстояниями.
В случае общего метрического пространства подход ветвей и границ известен как подход метрического дерева . Конкретные примеры включают методы vp-tree и BK-tree .
Используя набор точек, взятых из трехмерного пространства и помещенных в дерево BSP , и учитывая точку запроса, взятую из того же пространства, дается возможное решение проблемы поиска ближайшей точки облака точек к точке запроса. в следующем описании алгоритма. (Строго говоря, такой точки не может быть, потому что она не может быть уникальной. Но на практике обычно мы заботимся только о поиске любого из подмножества всех точек облака точек, которые существуют на кратчайшем расстоянии от заданной точки запроса. Идея состоит в том, чтобы для каждого ветвления дерева предположить, что ближайшая точка в облаке находится в полупространстве, содержащем точку запроса. Возможно, это не так, но это хорошая эвристика. После рекурсивного решения проблемы для предполагаемого полупространства теперь сравните расстояние, возвращаемое этим результатом, с кратчайшим расстоянием от точки запроса до плоскости разделения. Последнее расстояние - это расстояние между точкой запроса и ближайшей возможной точкой, которая может существовать в полупространстве, в котором не ведется поиск. Если это расстояние больше, чем то, что было возвращено в предыдущем результате, то очевидно, что нет необходимости искать другое полупространство. Если есть такая необходимость, то вы должны решить проблему для другого полупространства, а затем сравнить его результат с первым результатом, а затем вернуть правильный результат. Производительность этого алгоритма ближе к логарифмическому времени, чем к линейному времени, когда точка запроса находится рядом с облаком, потому что, поскольку расстояние между точкой запроса и ближайшей точкой облака точек приближается к нулю, алгоритму нужно только выполнить поиск, используя точка запроса в качестве ключа для получения правильного результата.
Методы приближения
Алгоритм приблизительного поиска ближайшего соседа может возвращать точки, расстояние от которых до запроса не превышает умноженное на расстояние от запроса до ближайших точек. Привлекательность этого подхода заключается в том, что во многих случаях приблизительный ближайший сосед почти так же хорош, как и точный. В частности, если мера расстояния точно отражает понятие качества пользователя, то небольшие различия в расстоянии не должны иметь значения. [7]
Жадный поиск в графах близких окрестностей
Методы графа близости (такие как HNSW [8] ) считаются современным уровнем техники для приблизительного поиска ближайших соседей. [8] [9] [10]
Методы основаны на жадном обходе графов близких окрестностей. в котором каждая точка однозначно ассоциирован с вершиной . Поиск ближайших соседей к запросу q в множестве S принимает форму поиска вершины в графе. Основной алгоритм - жадный поиск - работает следующим образом: поиск начинается с вершины точки входа. путем вычисления расстояний от запроса q до каждой вершины его окрестности , а затем находит вершину с минимальным значением расстояния. Если значение расстояния между запросом и выбранной вершиной меньше, чем расстояние между запросом и текущим элементом, то алгоритм переходит к выбранной вершине, и она становится новой точкой входа. Алгоритм останавливается, когда достигает локального минимума: вершины, окрестность которой не содержит вершину, которая находится ближе к запросу, чем сама вершина.
Идея графов близости соседства использовалась во многих публикациях, включая основополагающую статью Арьи и Маунта [11] в системе VoroNet для плоскости, [12] в системе RayNet для, [13] и в алгоритмах Metrized Small World [14] и HNSW [8] для общего случая пространств с функцией расстояния. Этим работам предшествовала новаторская статья Туссена, в которой он ввел понятие графа относительных окрестностей . [15]
Хеширование с учетом местоположения
Хеширование с учетом местоположения (LSH) - это метод группировки точек в пространстве в «корзины» на основе некоторой метрики расстояния, действующей на точки. Точки, которые находятся близко друг к другу при выбранной метрике, с большой вероятностью отображаются в один и тот же сегмент. [16]
Поиск ближайшего соседа в пространствах с малой внутренней размерностью
Дерево крышки имеет теоретический предел , который основан на набор данные удвоения постоянная . Ограничение времени поиска составляет O ( c 12 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]
Смотрите также
- Шаровое дерево
- Проблема ближайшей пары точек
- Кластерный анализ
- Поиск изображений на основе содержимого
- Проклятие размерности
- Цифровая обработка сигналов
- Уменьшение размеров
- Фиксированный радиус рядом с соседями
- Фурье-анализ
- Обучение на основе экземпляров
- k- алгоритм ближайшего соседа
- Линейный метод наименьших квадратов
- Хеширование с учетом местоположения
- MinHash
- Многомерный анализ
- Интерполяция ближайшего соседа
- Присоединение к соседу
- Анализ главных компонентов
- Поиск по диапазону
- Изучение подобия
- Разложение по сингулярным числам
- Редкая распределенная память
- Статистическое расстояние
- Временная последовательность
- Диаграмма Вороного
- Вейвлет
Рекомендации
Цитаты
- ^ Cayton, Lawerence (2008). «Быстрый поиск ближайшего соседа для расхождений Брегмана». Материалы 25-й Международной конференции по машинному обучению : 112–119. DOI : 10.1145 / 1390156.1390171 . ISBN 9781605582054.
- ^ а б Bewley, A .; Апкрофт, Б. (2013). Преимущества использования структуры проекции для сегментации плотных трехмерных облаков точек (PDF) . Австралийская конференция по робототехнике и автоматизации.
- ^ Вебер, Роджер; Schek, Hans-J .; Блотт, Стивен (1998). «Количественный анализ и исследование эффективности методов поиска подобия в пространствах большой размерности» (PDF) . VLDB '98 Труды 24-й Международной конференции по очень большим базам данных : 194–205.
- ^ Эндрю Мур. «Вводное руководство по деревьям KD» (PDF) . Архивировано из оригинального (PDF) 03 марта 2016 года . Проверено 3 октября 2008 .
- ^ Ли, Д.Т .; Вонг, СК (1977). «Анализ наихудшего случая для поиска области и части области в многомерных двоичных деревьях поиска и сбалансированных деревьях квадратов». Acta Informatica . 9 (1): 23–29. DOI : 10.1007 / BF00263763 .
- ^ Roussopoulos, N .; Kelley, S .; Винсент, Рузвельт (1995). «Запросы ближайшего соседа». Материалы международной конференции ACM SIGMOD 1995 года по управлению данными - SIGMOD '95 . п. 71. DOI : 10,1145 / 223784,223794 . ISBN 0897917316.
- ^ Андони, А .; Индик, П. (01.10.2006). Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерах . 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.
- ^ а б в Мальков, Юрий; Яшунин, Дмитрий (2016). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графов малого мира». Arxiv : 1603.09320 [ cs.DS ].
- ^ «Новые ориентировочные ориентиры ближайшего соседа» .
- ^ «Примерные ближайшие соседи для рекомендательных систем» .
- ^ Арья, Сунил; Маунт, Дэвид (1993). «Запросы приблизительного ближайшего соседа в фиксированных размерах». Материалы четвертого ежегодного симпозиума {ACM / SIGACT-SIAM} по дискретным алгоритмам, 25–27 января 1993 г., Остин, Техас. : 271–280.
- ^ Оливье, Бомон; Кермаррек, Анн-Мари; Маршал, Лорис; Ривьер, Этьен (2006). «Воронец: масштабируемая сеть объекта на основе Вороного мозаика» (PDF) . INRIA . RR-5833 (1): 23–29. DOI : 10.1109 / IPDPS.2007.370210 .
- ^ Оливье, Бомон; Кермаррек, Анн-Мари; Ривьер, Этьен (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.
- ^ Мальков, Юрий; Пономаренко, Александр; Крылов, Владимир; Логвинов, Андрей (2014). «Алгоритм приближенного ближайшего соседа, основанный на навигационных графах маленького мира». Информационные системы . 45 : 61–68. DOI : 10.1016 / j.is.2013.10.006 .
- ^ Туссен, Годфрид (1980). «Граф относительной окрестности конечного плоского множества». Распознавание образов . 12 (4): 261–268. DOI : 10.1016 / 0031-3203 (80) 90066-7 .
- ^ А. Раджараман и Дж. Ульман (2010). «Майнинг массивных наборов данных, глава 3» .
- ^ Вебер, Роджер; Блотт, Стивен. «Структура данных на основе аппроксимации для поиска подобия» (PDF) . S2CID 14613657 . Архивировано из оригинального (PDF) 04 марта 2017 года. Цитировать журнал требует
|journal=
( помощь ) - ^ Рамасвами, Шарад; Роуз, Кеннет (2007). «Адаптивное ограничение кластерного расстояния для поиска сходства в базах данных изображений». ICIP .
- ^ Рамасвами, Шарад; Роуз, Кеннет (2010). «Адаптивное ограничение кластерного расстояния для многомерного индексирования». ТКДЕ .
- ^ Arya, S .; Mount, DM ; Нетаньяху, NS ; Silverman, R .; Ву, А. (1998). «Оптимальный алгоритм приблизительного поиска ближайшего соседа» (PDF) . Журнал ACM . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . DOI : 10.1145 / 293347.293348 . Архивировано из оригинального (PDF) 03 марта 2016 года . Проверено 29 мая 2009 .
- ^ Кларксон, Кеннет Л. (1983), «Быстрые алгоритмы для задачи всех ближайших соседей», 24-й симпозиум IEEE. Основы компьютерных наук, (FOCS '83) , стр. 226–232, DOI : 10.1109 / SFCS.1983.16 , ISBN 978-0-8186-0508-6.
- ^ Вайдья, П.М. (1989). « Алгоритм O ( n log n ) для задачи всех ближайших соседей» . Дискретная и вычислительная геометрия . 4 (1): 101–115. DOI : 10.1007 / BF02187718 .
Источники
- Эндрюс, Л. (ноябрь 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 поиска по подобию - собрание ссылок, людей, идей, ключевых слов, статей, слайдов, кода и наборов данных о ближайших соседях.