logo

TechCodeview

Алгоритм K-найближчого сусіда (KNN).

The Алгоритм K-найближчих сусідів (KNN). це контрольований метод машинного навчання, який використовується для вирішення проблем класифікації та регресії. Евелін Фікс і Джозеф Ходжес розробили цей алгоритм у 1951 році, який згодом був розширений Томасом Ковером. У статті досліджуються основи, робота та реалізація алгоритму KNN.

Що таке K-алгоритм найближчих сусідів?

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

рядок у char java

Як приклад розглянемо наведену нижче таблицю точок даних, що містить дві характеристики:



Візуалізація роботи алгоритму KNN

Візуалізація роботи алгоритму KNN

Тепер, отримавши інший набір точок даних (також званих тестовими даними), розподіліть ці точки в групу, проаналізувавши навчальний набір. Зауважте, що некласифіковані точки позначені як «білі».

Інтуїція за алгоритмом KNN

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

Інтуїтивно ми бачимо, що перша точка (2.5, 7) має бути класифікована як «Зелена», а друга точка (5.5, 4.5) повинна бути класифікована як «Червона».

Навіщо нам алгоритм KNN?

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

Алгоритм K-NN працює, знаходячи K найближчих сусідів до заданої точки даних на основі метрики відстані, наприклад евклідової відстані. Клас або значення точки даних потім визначається більшістю голосів або середнім значенням K сусідів. Такий підхід дозволяє алгоритму адаптуватися до різних шаблонів і робити прогнози на основі локальної структури даних.

Показники відстані, що використовуються в алгоритмі KNN

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

Евклідова відстань

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

ext{відстань}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Манхеттенська відстань

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

dleft ( x,y ight )={sum_{i=1}^{n}left | x_i-y_i ight |}

Відстань Мінковського

Можна сказати, що евклідова, як і манхеттенська відстані, є окремими випадками Відстань Мінковського .

dleft ( x,y ight )=left ( {sum_{i=1}^{n}left ( x_i-y_i ight )^p} ight )^{frac{1}{p }}

З наведеної вище формули можна сказати, що коли p = 2, то це те саме, що формула для евклідової відстані, а коли p = 1, то ми отримуємо формулу для відстані Манхеттена.

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

Як вибрати значення k для алгоритму KNN?

Значення k дуже важливе в алгоритмі KNN для визначення кількості сусідів в алгоритмі. Значення k в алгоритмі k-найближчих сусідів (k-NN) слід вибирати на основі вхідних даних. Якщо вхідні дані мають більше викидів або шуму, краще значення k буде кращим. Рекомендується вибрати непарне значення для k, щоб уникнути зв’язків у класифікації. Перехресна перевірка методи можуть допомогти у виборі найкращого значення k для заданого набору даних.

Робота алгоритму KNN

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

Робота алгоритму KNN

Нижче наведено покрокове пояснення того, як працює KNN:

unix створити каталог

Крок 1: Вибір оптимального значення K

  • K представляє кількість найближчих сусідів, яку потрібно враховувати під час прогнозування.

Крок 2: Розрахунок відстані

  • Для вимірювання подібності між цільовими та навчальними точками даних використовується евклідова відстань. Відстань обчислюється між кожною з точок даних у наборі даних і цільовою точкою.

Крок 3: Пошук найближчих сусідів

  • K точок даних з найменшою відстанню до цільової точки є найближчими сусідами.

Крок 4: Голосування за класифікацію або визначення середнього для регресії

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

Нехай X — навчальний набір даних із n точками даних, де кожна точка даних представлена ​​d-вимірним вектором ознак X_iі Y — відповідні мітки або значення для кожної точки даних у X. За нової точки даних x алгоритм обчислює відстань між x і кожною точкою даних X_iв X з використанням метрики відстані, наприклад евклідової відстані: ext{відстань}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

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

Переваги алгоритму KNN

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

Недоліки алгоритму KNN

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

Приклад програми:

Припустимо, що 0 і 1 є двома класифікаторами (групами).

C++

// C++ program to find groups of unknown> // Points using K nearest neighbour algorithm.> #include> using> namespace> std;> struct> Point> {> >int> val;>// Group of point> >double> x, y;>// Co-ordinate of point> >double> distance;>// Distance from test point> };> // Used to sort an array of points by increasing> // order of distance> bool> comparison(Point a, Point b)> {> >return> (a.distance } // This function finds classification of point p using // k nearest neighbour algorithm. It assumes only two // groups and returns 0 if p belongs to group 0, else // 1 (belongs to group 1). int classifyAPoint(Point arr[], int n, int k, Point p) { // Fill distances of all points from p for (int i = 0; i arr[i].distance = sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)); // Sort the Points by distance from p sort(arr, arr+n, comparison); // Now consider the first k elements and only // two groups int freq1 = 0; // Frequency of group 0 int freq2 = 0; // Frequency of group 1 for (int i = 0; i { if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (freq1>частота2 ? 0 : 1); } // Код драйвера int main() { int n = 17; // Кількість точок даних Point arr[n]; arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1].x = 2; arr[1].y = 5; arr[1].val = 0; arr[2].x = 5; arr[2].y = 3; arr[2].val = 1; arr[3].x = 3; arr[3].y = 2; arr[3].val = 1; arr[4].x = 3; arr[4].y = 6; arr[4].val = 0; arr[5].x = 1,5; arr[5].y = 9; arr[5].val = 1; arr[6].x = 7; arr[6].y = 2; arr[6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[7].val = 1; arr[8].x = 3,8; arr[8].y = 3; arr[8].val = 1; arr[9].x = 3; arr[9].y = 10; arr[9].val = 0; arr[10].x = 5,6; arr[10].y = 4; arr[10].val = 1; arr[11].x = 4; arr[11].y = 2; arr[11].val = 1; arr[12].x = 3,5; arr[12].y = 8; arr[12].val = 0; arr[13].x = 2; arr[13].y = 11; arr[13].val = 0; arr[14].x = 2; arr[14].y = 5; arr[14].val = 1; arr[15].x = 2; arr[15].y = 9; arr[15].val = 0; arr[16].x = 1; arr[16].y = 7; arr[16].val = 0; /*Точка тестування*/ Точка p; p.x = 2,5; p.y = 7; // Параметр для визначення групи точки тестування int k = 3; printf ('Значення, класифіковане до невідомої точки' ' є %d. ', classifyAPoint(arr, n, k, p)); повернути 0; }>
>
>

Java

// Java program to find groups of unknown> // Points using K nearest neighbour algorithm.> import> java.io.*;> import> java.util.*;> class> GFG {> >static> class> Point {> >int> val;>// Group of point> >double> x, y;>// Co-ordinate of point> >double> distance;>// Distance from test point> >}> >// Used to sort an array of points by increasing> >// order of distance> >static> class> comparison>implements> Comparator {> >public> int> compare(Point a, Point b)> >{> >if> (a.distance return -1; else if (a.distance>b.distance) повернення 1; повернути 0; } } // Ця функція знаходить класифікацію точки p за допомогою // k алгоритму найближчого сусіда. Він передбачає лише дві // групи та повертає 0, якщо p належить до групи 0, інакше // 1 (належить до групи 1). static int classifyAPoint(Point arr[], int n, int k, Point p) { // Заповнити відстані всіх точок від p for (int i = 0; i arr[i].distance = Math.sqrt( (arr[ i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)); // Сортування точок за відстанню від p Arrays.sort(arr, new compare()); // Розглянемо перші k елементів і тільки дві групи int freq1 = 0; // Частота групи 0 int freq2 = 0; (int i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (freq1> freq2 ? 0 : 1); } / / Код драйвера public static main(String[] args) { int n = 17; // Кількість точок даних Point[] arr = new Point[n]; for (int i = 0; i<17; i++) { arr[i] = new Point(); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1].x = 2; arr[1].y = 5; arr[1].val = 0; arr[2].x = 5; arr[2].y = 3; arr[2].val = 1; arr[3].x = 3; arr[3].y = 2; arr[3].val = 1; arr[4].x = 3; arr[4].y = 6; arr[4].val = 0; arr[5].x = 1.5; arr[5].y = 9; arr[5].val = 1; arr[6].x = 7; arr[6].y = 2; arr[6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[7].val = 1; arr[8].x = 3.8; arr[8].y = 3; arr[8].val = 1; arr[9].x = 3; arr[9].y = 10; arr[9].val = 0; arr[10].x = 5.6; arr[10].y = 4; arr[10].val = 1; arr[11].x = 4; arr[11].y = 2; arr[11].val = 1; arr[12].x = 3.5; arr[12].y = 8; arr[12].val = 0; arr[13].x = 2; arr[13].y = 11; arr[13].val = 0; arr[14].x = 2; arr[14].y = 5; arr[14].val = 1; arr[15].x = 2; arr[15].y = 9; arr[15].val = 0; arr[16].x = 1; arr[16].y = 7; arr[16].val = 0; /*Testing Point*/ Point p = new Point(); p.x = 2.5; p.y = 7; // Parameter to decide group of the testing point int k = 3; System.out.println( 'The value classified to unknown point is ' + classifyAPoint(arr, n, k, p)); } } // This code is contributed by Karandeep1234>
>
>

Python3

import> math> def> classifyAPoint(points,p,k>=>3>):> >'''> >This function finds the classification of p using> >k nearest neighbor algorithm. It assumes only two> >groups and returns 0 if p belongs to group 0, else> >1 (belongs to group 1).> >Parameters -> >points: Dictionary of training points having two keys - 0 and 1> >Each key have a list of training data points belong to that> >p : A tuple, test data point of the form (x,y)> >k : number of nearest neighbour to consider, default is 3> >'''> >distance>=>[]> >for> group>in> points:> >for> feature>in> points[group]:> >#calculate the euclidean distance of p from training points> >euclidean_distance>=> math.sqrt((feature[>0>]>->p[>0>])>*>*>2> +>(feature[>1>]>->p[>1>])>*>*>2>)> ># Add a tuple of form (distance,group) in the distance list> >distance.append((euclidean_distance,group))> ># sort the distance list in ascending order> ># and select first k distances> >distance>=> sorted>(distance)[:k]> >freq1>=> 0> #frequency of group 0> >freq2>=> 0> #frequency og group 1> >for> d>in> distance:> >if> d[>1>]>=>=> 0>:> >freq1>+>=> 1> >elif> d[>1>]>=>=> 1>:> >freq2>+>=> 1> >return> 0> if> freq1>freq2>>>1> # driver function> def> main():> ># Dictionary of training points having two keys - 0 and 1> ># key 0 have points belong to class 0> ># key 1 have points belong to class 1> >points>=> {>0>:[(>1>,>12>),(>2>,>5>),(>3>,>6>),(>3>,>10>),(>3.5>,>8>),(>2>,>11>),(>2>,>9>),(>1>,>7>)],> >1>:[(>5>,>3>),(>3>,>2>),(>1.5>,>9>),(>7>,>2>),(>6>,>1>),(>3.8>,>1>),(>5.6>,>4>),(>4>,>2>),(>2>,>5>)]}> ># testing point p(x,y)> >p>=> (>2.5>,>7>)> ># Number of neighbours> >k>=> 3> >print>(>'The value classified to unknown point is: {}'>.> >format>(classifyAPoint(points,p,k)))> if> __name__>=>=> '__main__'>:> >main()> 
>
>

C#

using> System;> using> System.Collections;> using> System.Collections.Generic;> using> System.Linq;> // C# program to find groups of unknown> // Points using K nearest neighbour algorithm.> class> Point {> >public> int> val;>// Group of point> >public> double> x, y;>// Co-ordinate of point> >public> int> distance;>// Distance from test point> }> class> HelloWorld {> >// This function finds classification of point p using> >// k nearest neighbour algorithm. It assumes only two> >// groups and returns 0 if p belongs to group 0, else> >// 1 (belongs to group 1).> >public> static> int> classifyAPoint(List arr,>int> n,>int> k, Point p)> >{> >// Fill distances of all points from p> >for> (>int> i = 0; i arr[i].distance = (int)Math.Sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)); // Sort the Points by distance from p arr.Sort(delegate(Point x, Point y) { return x.distance.CompareTo(y.distance); }); // Now consider the first k elements and only // two groups int freq1 = 0; // Frequency of group 0 int freq2 = 0; // Frequency of group 1 for (int i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (freq1>частота2 ? 0 : 1); } static void Main() { int n = 17; // Кількість точок даних List arr = new List(); for(int i = 0; i arr.Add(new Point()); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1] .x = 2; arr[1].val = 0; arr[2].y = 1; arr[3].x = 3; arr[3].val = 1; arr[4].y = 6; val = 0; arr[5].y = 1; arr[6].y = 2; [6].val = 1; arr[7].y = 1; arr[8].y = 3; arr[9].x = 3; arr[9].val = 5,6; 10].y = 1; arr[11].y = 1; arr[12].x = 3.5; arr[12].val = 0; arr[13].y = 0; arr[13].val = 0; ].x = 2; arr[14].val = 1; arr[15].y = 0 arr[16].x = 7; arr[16].val = 0; p.x = 2,5; // Параметр для визначення групи точки тестування int k = 3; Console.WriteLine('Значення, класифіковане до невідомої точки, це ' + classifyAPoint(arr, n, k, p)); } } // Код створено Nidhi Goel.>
>
>

Javascript

class Point {> >constructor(val, x, y, distance) {> >this>.val = val;>// Group of point> >this>.x = x;>// X-coordinate of point> >this>.y = y;>// Y-coordinate of point> >this>.distance = distance;>// Distance from test point> >}> }> // Used to sort an array of points by increasing order of distance> class Comparison {> >compare(a, b) {> >if> (a.distance return -1; } else if (a.distance>b.distance) { return 1; } повернути 0; } } // Ця функція знаходить класифікацію точки p за допомогою // k алгоритму найближчого сусіда. Він передбачає лише дві // групи та повертає 0, якщо p належить до групи 0, інакше // 1 (належить до групи 1). function classifyAPoint(arr, n, k, p) { // Заповнити відстані всіх точок від p for (let i = 0; i arr[i].distance = Math.sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)); // Сортування точок за відстанню від p arr.sort(new Comparison()); // Розглянемо перші k елементів і тільки дві групи, let freq1 = 0; // Частота групи 1, let freq2 = 0; [i].val === 0) { freq1++; } else if (arr[i].val === 1) { freq2++; } return freq1> freq2 ? 0 : 1; } // Код драйвера const n = 17; // Кількість точок даних const = new Array(n); for (let i = 0; i<17; i++) { arr[i] = new Point(); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1].x = 2; arr[1].y = 5; arr[1].val = 0; arr[2].x = 5; arr[2].y = 3; arr[2].val = 1; arr[3].x = 3; arr[3].y = 2; arr[3].val = 1; arr[4].x = 3; arr[4].y = 6; arr[4].val = 0; arr[5].x = 1.5; arr[5].y = 9; arr[5].val = 1; arr[6].x = 7; arr[6].y = 2; arr[6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[7].val = 1; arr[8].x = 3.8; arr[8].y = 3; arr[8].val = 1; arr[9].x = 3; arr[9].y = 10; arr[9].val = 0; arr[10].x = 5.6; arr[10].y = 4; arr[10].val = 1; arr[11].x = 4 arr[11].y = 2; arr[11].val = 1; arr[12].x = 3.5; arr[12].y = 8; arr[12].val = 0; arr[13].x = 2; arr[13].y = 11; arr[13].val = 0; arr[14].x = 2; arr[14].y = 5; arr[14].val = 1; arr[15].x = 2; arr[15].y = 9; arr[15].val = 0; arr[16].x = 1; arr[16].y = 7; arr[16].val = 0; // Testing Point let p = { x: 2.5, y: 7, val: -1, // uninitialized }; // Parameter to decide group of the testing point let k = 3; console.log( 'The value classified to unknown point is ' + classifyAPoint(arr, n, k, p) ); function classifyAPoint(arr, n, k, p) { // Fill distances of all points from p for (let i = 0; i arr[i].distance = Math.sqrt( (arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y) ); } // Sort the Points by distance from p arr.sort(function (a, b) { if (a.distance return -1; else if (a.distance>b.distance) повернення 1; повернути 0; }); // Тепер розглянемо перші k елементів і лише дві групи, нехай freq1 = 0; // Частота групи 0 let freq2 = 0; // Частота групи 1 для (let i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return freq1> freq2 ? 0 : 1;>
>
>

Вихід: 

The value classified as an unknown point is 0.>

Часова складність: O(N * logN)
Допоміжний простір: О(1)

Застосування алгоритму KNN

  • Попередня обробка даних – Маючи справу з будь-якою проблемою машинного навчання, ми спочатку виконуємо Імпутація KNN який є досить ефективним і зазвичай використовується для складних методологій імпутації.
  • Розпізнавання образів – Алгоритми KNN працюють дуже добре, якщо ви навчили алгоритм KNN за допомогою набору даних MNIST, а потім виконали процес оцінки, тоді ви, мабуть, зіткнулися з фактом, що точність надто висока.
  • Рекомендовані двигуни – Основним завданням, яке виконує алгоритм KNN, є призначення нової точки запиту для попередньо існуючої групи, яка була створена за допомогою величезного корпусу наборів даних. Це саме те, що потрібно в K Найближчі сусіди з Python | ML
  • Реалізація K-Nearest Neighbors з нуля за допомогою Python
  • Математичне пояснення K-найближчого сусіда
  • Зважений K-NN

Часті запитання (FAQ)

З. Чому KNN ледачий учень?

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

З. Чому KNN є непараметричним?

Алгоритм KNN не робить припущень щодо даних, які він аналізує.

Q. Яка різниця між KNN і K означає?

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