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

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

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

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

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


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

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

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

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

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

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


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

Розберемо докладніше метод найближчого сусіда. Якщо запропонована навчальна вибірка виду «об'єкт-відповідь» X^m = {(x_1y_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, а також не допускати викидів серед аналізованих об'єктів. Саме тому і застосовують методику вибору еталонів, а також проводять оптимізацію метрик.