Пошук найближчого сусіда

Задача пошуку найближчого сусіда є задачею оптимізації, яка полягає у відшуканні у множині елементів, розташованих у багатовимірному метричному просторі, елементів, близьких до заданого, відповідно до заданої функції близькості. Формально ця задача ставиться наступним чином: надано множину точок S у просторі M та точку q ∈ M, необхідно знайти найближчу до q точку в S. Дональд Кнут в Мистецтві програмування (том 3, 1973) назвав це проблемою поштового відділення, посилаючись на застосування цієї задачі до пошуку найближчого поштового відділення. Прямим узагальненням задачі пошуку найближчого сусіда є алгоритм пошуку k-NN, який призначений для пошуку k найближчих точок.

Найчастіше M є метричним простором і запроваджується функція близькості, що визначається як метрика, яка є симетричною і задовольняє нерівності трикутника. Ще загальніше, M — це d-вимірний векторний простір, в якому близькість береться як Евклідова метрика, вулична метрика або інші метрики. Однак функція близькості може бути довільною. Одним з прикладів може бути метрика Брегмана^[en], для якої нерівність трикутника не виконується.^[1]

Застосування ред.

Задача пошуку найближчого сусіда зустрічається у багатьох областях, наприклад:

розпізнавання образів;
класифікація документів;
рекомендаційні і експертні системи;
динамічне розміщення реклами в Інтернеті.

Моделі даних ред.

Перед вирішенням прикладної задачі необхідно обрати форму подання об'єктів і функцію близькості. У більшості випадків об'єкти подаються у вигляді багатовимірних векторів, а як функція близькості використовується скалярний добуток векторів, але можуть бути й інші форми подання даних, наприклад:

множини — розмір перетину множин;
рядки — відстань Левенштейна;
граф — відповідність структур.

Споріднені задачі ред.

Існують численні варіанти задачі пошуку найближчих сусідів. Окрім класичної задачі знаходження найближчої до заданої точки, можуть бути поставлені задачі:

знайти близьких сусідів (не обов'язково найближчого);
знайти найближчого сусіда для групи елементів;
знайти кількох найближчих сусідів;
знайти усі пари елементів, відстань між якими менша за деяку задану;
знайти найближчих сусідів у середі, що динамічно змінюється.

Одним з найбільш відомих варіантів є k-NN пошук.

Алгоритм k-NN ред.

Див. також: Метод k-найближчих сусідів

Алгоритм k-NN — це алгоритм автоматичної класифікації об'єктів. Він визначає k сусідів, найближчих до заданої точки (об'єкту). Цей метод широко використовується у прогностичній аналітиці для оцінки або класифікації точки на основі узгодженості її сусідів. k-NN граф є графом, в якому кожна точка з'єднана з її k найближчими сусідами.

Алгоритми ред.

Було запропоновано багато алгоритмів вирішення задачі пошуку найближчого сусіда. Якість та корисність алгоритмів визначається часовою складністю запитів, а також складністю усіх структур пошуку інформації, що мають підтримуватися. Не існує загального вирішення задачі у багатовимірному Евклідовому просторі, яке б використовувало поліноміальний час попередньої обробки та полілогаріфмічній час пошуку даних.

Послідовний пошук ред.

Найпростішим способом розв'язання задачі, є обчислення відстані від заданої точки до кожної іншої точки в наборі даних, постійно відстежуючи найкращий результат на даний момент. Цей алгоритм називають прямими методом, і його складність виконання становить O(dN), де N — це потужність множини точок S, а d — це розмірність простору M. Для реалізації не потрібні ніякі додаткові структуру для пошуку даних, тому лінійний пошук не потребує додаткового простору даних крім початкового набору даних.^[2]

Розбиття простору ред.

Зворотній індекс ред.

Метод рідкісних точок.

Інші ред.

Див. також ред.

Примітки ред.

↑ Cayton, Lawerence (2008). Fast nearest neighbor retrieval for bregman divergences. Proceedings of the 25th international conference on Machine learning: 112—119.
↑ Weber, Roger; Schek, Hans-J.; Blott, Stephen. A quantitative analysis and performance study for similarity search methods in high dimensional spaces (PDF).

Посилання ред.

Yury Lifshits. Algorithms for Nearest Neighbors: Theoretical Aspects

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[Cayton2008-1] Cayton, Lawerence (2008). Fast nearest neighbor retrieval for bregman divergences. Proceedings of the 25th international conference on Machine learning: 112—119.

[2] Weber, Roger; Schek, Hans-J.; Blott, Stephen. A quantitative analysis and performance study for similarity search methods in high dimensional spaces (PDF).

[1]

[2]