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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритми[ред.ред. код]

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


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

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

Інші[ред.ред. код]

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

Примітки[ред.ред. код]

  1. Fast nearest neighbor retrieval for bregman divergences. // Proceedings of the 25th international conference on Machine learning, (2008) С. 112–119.

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