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

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

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

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

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

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

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

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

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

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

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

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

Розберемо детальніше метод найближчого сусіда. Якщо запропоновано навчальну вибірку виду «об'єкт-відповідь» X^m = \; якщо безлічі об'єктів задають функцію відстані \rho(x,x'), яка представлена як адекватної моделі подібності об'єктів, зі збільшенням значення цієї функції знижується подібність між об'єктами x, x'.

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

\rho(u,x_) \leq \rho(u,x_) \leq \cdots \leq \rho(u,x_),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Висновок

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

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

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