Що таке KNN (K-найближчі сусіди)?

Що таке K-Nearest Neighbors (KNN)?

K-Nearest Neighbors – це техніка та алгоритм машинного навчання, які можна використовувати як для завдань регресії, так і для класифікації. K-найближчі сусіди оглядає мітки вибраної кількості точок даних навколо цільової точки даних, щоб зробити прогноз щодо класу, до якого відноситься точка даних. K-Nearest Neighbors (KNN) — це концептуально простий, але дуже потужний алгоритм, і з цих причин він є одним із найпопулярніших алгоритмів машинного навчання. Давайте глибше зануримося в алгоритм KNN і побачимо, як саме він працює. Гарне розуміння того, як працює KNN, дозволить вам оцінити найкращі та найгірші випадки використання KNN.

Огляд K-Nearest Neighbors (KNN)

Фото: Antti Ajanki AnAj через Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

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

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

KNN — це контрольований алгоритм навчання, що означає, що приклади в наборі даних повинні мати мітки, призначені їм/їхні класи повинні бути відомі. Є ще дві важливі речі, які слід знати про KNN. По-перше, KNN є непараметричним алгоритмом. Це означає, що під час використання моделі не робляться припущення щодо набору даних. Швидше, модель побудована повністю з наданих даних. По-друге, під час використання KNN набір даних не розбивається на набори для навчання та тестування. KNN не робить узагальнень між навчальним і тестовим набором, тому всі навчальні дані також використовуються, коли модель просять зробити прогнози.

Як працює алгоритм KNN

Алгоритм KNN проходить три основні фази під час виконання:

1. Встановлення K на вибрану кількість сусідів.
2. Обчислення відстані між наданим/тестовим прикладом і прикладами набору даних.
3. Сортування обчислених відстаней.
4. Отримання міток найпопулярніших K записів.
5. Повернення передбачення щодо тестового прикладу.

На першому кроці K вибирається користувачем, і він повідомляє алгоритму, скільки сусідів (скільки оточуючих точок даних) слід враховувати під час винесення судження про групу, до якої належить цільовий приклад. На другому кроці зверніть увагу, що модель перевіряє відстань між цільовим прикладом і кожним прикладом у наборі даних. Потім відстані додаються до списку та сортуються. Після цього відсортований список перевіряється, і повертаються мітки для верхніх K елементів. Іншими словами, якщо K встановлено на 5, модель перевіряє мітки 5 найближчих точок даних до цільової точки даних. Під час візуалізації прогнозу щодо цільової точки даних має значення, чи є завдання a регресія or класифікація завдання. Для задачі регресії використовується середнє значення верхніх K міток, тоді як режим верхніх K міток використовується у випадку класифікації.

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

Чому значення K має значення

Основним обмеженням під час використання KNN є те, що може бути обрано неправильне значення K (неправильна кількість сусідів, які слід враховувати). Якщо це станеться, прогнози, які повертаються, можуть бути суттєво відхиленими. Дуже важливо, щоб під час використання алгоритму KNN вибрано правильне значення K. Ви хочете вибрати значення для K, яке максимізує здатність моделі робити прогнози на невидимих ​​даних, одночасно зменшуючи кількість помилок, які вона робить.

Фото: Agor153 через Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Нижчі значення K означають, що прогнози, зроблені KNN, менш стабільні та надійні. Щоб інтуїтивно зрозуміти, чому це так, розглянемо випадок, коли ми маємо 7 сусідів навколо цільової точки даних. Припустімо, що модель KNN працює зі значенням K, рівним 2 (ми просимо її переглянути двох найближчих сусідів, щоб зробити прогноз). Якщо переважна більшість сусідів (п’ять із семи) належать до класу Blue, але двоє найближчих сусідів просто червоні, модель передбачить, що приклад запиту червоний. Незважаючи на припущення моделі, у такому сценарії синій був би кращим припущенням.

Якщо це так, чому б просто не вибрати найвище значення K, яке ми можемо? Це тому, що вказівка ​​моделі враховувати занадто багато сусідів також зменшить точність. Оскільки радіус, який розглядає модель KNN, збільшується, вона зрештою почне розглядати точки даних, які ближче до інших груп, ніж вони є цільовими точками даних, і почне відбуватися неправильна класифікація. Наприклад, навіть якщо початково вибрана точка була в одній із червоних областей вище, якщо K було встановлено занадто високо, модель досягне інших областей, щоб розглянути точки. При використанні моделі KNN пробуються різні значення K, щоб побачити, яке значення забезпечує найкращу продуктивність моделі.

Плюси і мінуси KNN

Давайте розглянемо деякі переваги та недоліки моделі KNN.

Плюси:

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

KNN є високоточним і простим у використанні. Його легко інтерпретувати, зрозуміти та реалізувати.

KNN не робить жодних припущень щодо даних, тобто їх можна використовувати для вирішення багатьох проблем.

Мінуси:

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

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

Короткий опис K-найближчих сусідів (KNN)

K-Nearest Neighbors — один із найпростіших алгоритмів машинного навчання. Незважаючи на те, наскільки простим є KNN, за концепцією, це також потужний алгоритм, який забезпечує досить високу точність у більшості проблем. Коли ви використовуєте KNN, обов’язково експериментуйте з різними значеннями K, щоб знайти число, яке забезпечує найвищу точність.