К-Найближчих Сусідів: Класифікація за Тиском Однодумців

Весь алгоритм можна описати однією фразою

Щоб класифікувати нову точку, знайти k розмічених навчальних точок найближчих до неї та дозволити їм проголосувати: більшість серед цих k сусідів стає прогнозом. Це і є весь алгоритм – немає фази навчання в звичайному сенсі, жодних ваг для підгонки, жодної функції втрат для мінімізації. Алгоритм k-NN просто зберігає розмічені дані та відкладає кожне рішення на час запиту, що й пояснює, чому його називають «байдужим учнем», на відміну від «ехичного учня», як логістична регресія або нейронна мережа, які виконують свою роботу заздалегідь.

classify(query, k):
  distances = [ (dist(query, x_i), label_i) for each training point x_i ]
  neighbours = k points with smallest distance
  return the majority label among neighbours    // ties broken by smallest k or nearest

k=1 та викривлений Вороновий діаметр

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

Вибір k: регулювання балансу між упередженням і дисперсією

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

Важливість метрик відстаней, так само, як і k

"Найближчі" повністю залежать від функції відстаней. Евклідова відстань є стандартною, але вона безшумно припускає, що всі ознаки мають порівнянний масштаб – ознака, виміряна тисячами, домінуватиме над тією, що вимірюється десятками, якщо дані не стандартизовані спочатку. Манхеттенська відстань більш стійка до викидів вздовж окремих осей, а відстань Мінковського узагальнює обидві параметри експоненти. Масштабування ознак є обов’язковим для k-NN так само, як і для деяких інших алгоритмів; якщо це зробити неправильно, "найближчі" сусіди насправді є лише ті пункти, які найближче розташовані вздовж будь-якої ознаки, яка має найбільший розмах у свій час.

Прокляття розмірності та пришвидшення пошуку

Руйнівний запит перевіряє відстань до кожного збереженого пункту, що займає O(n) на кожне передбачення – це нормально для невеликих наборів даних, але болісно у великих масштабах. Структури просторового індексування, такі як kd-дерева та дерева кулевих, зменшують це до приблизно O(log n) у низьких розмірностях шляхом рекурсивного розділення простору так, щоб цілі області можна було відкинути без перевірки кожного пункту всередині них окремо. Ця швидкість знижується зі збільшенням кількості ознак, через прокляття розмірності: у багатовимірних просторах об’єм росте експоненціально, тому точки даних стають розсіяними та майже на однаковій відстані один від одного, і сама ідея «близького» сусіда починає руйнуватися, а індекси простору знову підходять за продуктивністю brute-force. Зменшення розмірності або вибір ознак перед запуском k-NN є стандартним рішенням.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте k-Nearest Neighbours і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.