Метод найближчого сусіда: приклад роботи

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

Відео: Math for Liberal Studies: Using the Nearest-Neighbor Algorithm

Аналізований об`єкт відносять до класу, до якого належать предмети навчальної вибірки. З`ясуємо, що представляє собою метод найближчого сусіда. Спробуємо розібратися в цьому складному питанні, привести приклади різних методик.

гіпотеза методу

Метод найближчого сусіда можна вважати найпоширенішим алгоритмом, використовуваним для класифікації. Об`єкт, що піддається класифікації належить до того класу y_i, до якого належить найближчий об`єкт навчальної вибірки x_i.

Специфіка методики найближчих сусідів

Метод k найближчих сусідів дозволяє підвищувати достовірність класифікації. Аналізований об`єкт належить до того самого класу, що й основна маса його сусідів, тобто k близьких до нього об`єктів аналізованої вибірки x_i. При вирішенні завдань з двома класами кількість сусідів буде непарних, щоб виключити ситуацію неоднозначності, якщо одне і те ж число сусідів буде належати різним класам.

Методика зважених сусідів

Аналізований postgresql-метод найближчих сусідів tsvector використовується, коли кількість класів не менш трьох, і не можна скористатися непарні. Але неоднозначність виникає навіть у цих випадках. Тоді i-й сусід отримує вагу w_i, який убуває зі збільшенням рангу сусіда i. Відноситься об`єкт до класу, який буде мати максимальний сумарний вага серед близьких сусідів.

гіпотеза компактності

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

Відео: R - kNN - k nearest neighbor (part 1)

Основна формула

Розберемо докладніше метод найближчого сусіда. Якщо запропонована навчальна вибірка виду «об`єкт-відповідь» X ^ m = {(x_1, y_1), dots, (x_m, y_m) } - якщо для безлічі об`єктів задають функцію відстані rho (x, x `), яка представлена у вигляді адекватної моделі подібності об`єктів, при збільшенні значення даної функції знижується схожість між об`єктами x, x `.

Для будь-якого об`єкта u вибудуємо об`єкти навчальної вибірки x_i в міру зростання відстаней до u:

Rho (u, x_ {1 u}) leq rho (u, x_ {2- u}) leq cdots leq rho (u, x_ {m- u}),

де x_ {i- u} характеризує об`єкт навчальної вибірки, що є i-м сусідом вихідного об`єкта u. Подібне позначення використовуємо і для відповіді на i-м сусіда: y_ {i- u}. У підсумку отримуємо, що довільний об`єкт u провокує зміну нумерації власної вибірки.

Визначення числа сусідів k

Метод найближчого сусіда при k = 1 здатний давати помилкову класифікацію, причому не тільки на об`єктах-викидах, а й для інших класів, які розташовані поблизу.

Якщо взяти k = m, алгоритм буде максимально стійким і виродиться в постійну величину. Саме тому для достовірності важливо не допускати крайніх показників k.

На практиці в якості оптимального показника k застосовують критерій змінного контролю.

відсів викидів

Об`єкти навчання в основному є нерівноцінними, але серед них є такі, які мають характерними ознаками класу і називаються еталонами. При близькості розглянутого предмета до ідеального зразка висока ймовірність його приналежності до даного класу.

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

Потрапити в таку вибірку може бути кілька шумових викидів, які знаходяться «в гущі» іншого класу. Видалення в основному позитивно відбивається на якості проведеної класифікації.

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

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

Застосування надвеликих вибірок

Метод найближчих сусідів базується на реальному зберіганні навчальних об`єктів. Для створення надвеликих вибірок використовують технічні проблеми. Ставиться завдання не просто зберегти суттєвий обсяг інформації, але і в мінімальний часовий проміжок встигати знаходити довільний об`єкт u серед найближчих k сусідів.

Для того щоб впоратися з поставленим завданням, застосовують два способи:

• проріджують вибірку за допомогою викидання неінформаційних об`єктів;
• застосовують спеціальні ефективні структури і індекси даних для моментального пошуку найближчих сусідів.

Правила підбору методики

Вище була розглянута класифікація. Метод найближчого сусіда застосовують при вирішенні практичних завдань, в яких відома заздалегідь функція відстані rho (x, x `). При описі об`єктів числовими векторами використовують евклидову метрику. Подібний вибір не має спеціального обґрунтування, але має на увазі вимір всіх ознак «в єдиному масштабі». Якщо не врахувати цей фактор, то в метриці переважатиме ознака, що має найбільші числові значення.

При наявності істотної кількості ознак, обчисленні відстані у вигляді суми відхилень по конкретним ознаками з`являється серйозна проблема розмірності.

У просторі високої розмірності далекими один від одного виявляться всі об`єкти. В кінцевому підсумку довільній буде вибірка найближчих для досліджуваного об`єкта k сусідів. Для усунення подібної проблеми відбирається невелика кількість інформативних ознак. Алгоритми розрахунку оцінок вибудовують на основі різних наборів ознак, причому для кожного окремого вибудовують свою функцію близькості.

висновок

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

В експертних системах необхідно не просто класифікувати об`єкти, але і показувати користувачеві пояснення даної класифікації. В даному методі пояснення подібного явища виражаються відношенням об`єкта до певного класу, а також розташуванням його відносно використовуваної вибірки. Фахівці юридичної галузі, геологи, медики, приймають цю «прецедентну» логіку, активно користуються нею в своїх дослідженнях.

Для того щоб аналізований метод був максимально достовірним, ефективним, давав бажаний результат, необхідно брати мінімальний показник k, а також не допускати викидів серед аналізованих об`єктів. Саме тому і застосовують методику вибору еталонів, а також проводять оптимізацію метрик.