logo

TechCodeview

Algorytm K-najbliższego sąsiada (KNN).

The Algorytm K-najbliższych sąsiadów (KNN). to nadzorowana metoda uczenia maszynowego stosowana do rozwiązywania problemów związanych z klasyfikacją i regresją. Evelyn Fix i Joseph Hodges opracowali ten algorytm w 1951 roku, który został następnie rozszerzony przez Thomasa Covera. W artykule omówiono podstawy, działanie i implementację algorytmu KNN.

Co to jest algorytm K-najbliższych sąsiadów?

KNN to jeden z najbardziej podstawowych, ale niezbędnych algorytmów klasyfikacyjnych w uczeniu maszynowym. Należy do Nadzorowana nauka dziedzinę i znajduje szerokie zastosowanie w rozpoznawaniu wzorców, Można go powszechnie stosować w rzeczywistych scenariuszach, ponieważ jest nieparametryczny, co oznacza, że ​​nie przyjmuje żadnych podstawowych założeń dotyczących rozkładu danych (w przeciwieństwie do innych algorytmów, takich jak GMM, które zakładają Rozkład Gaussa podanych danych). Otrzymujemy pewne dane wstępne (zwane także danymi treningowymi), które klasyfikują współrzędne w grupy identyfikowane przez atrybut.

typy drzew binarnych

Jako przykład rozważ poniższą tabelę punktów danych zawierającą dwie cechy:



Wizualizacja działania algorytmu KNN

Wizualizacja działania algorytmu KNN

Teraz, mając inny zestaw punktów danych (zwanych także danymi testowymi), przydziel te punkty grupie, analizując zbiór uczący. Należy pamiętać, że niesklasyfikowane punkty są oznaczone jako „białe”.

Intuicja za algorytmem KNN

Jeśli naniesiemy te punkty na wykres, być może uda nam się zlokalizować pewne skupienia lub grupy. Teraz, mając niesklasyfikowany punkt, możemy przypisać go do grupy, obserwując, do jakiej grupy należą jego najbliżsi sąsiedzi. Oznacza to, że punkt znajdujący się w pobliżu grupy punktów sklasyfikowanych jako „czerwony” ma większe prawdopodobieństwo, że zostanie sklasyfikowany jako „czerwony”.

Intuicyjnie widzimy, że pierwszy punkt (2.5, 7) należy sklasyfikować jako „zielony”, a drugi punkt (5.5, 4.5) jako „czerwony”.

Dlaczego potrzebujemy algorytmu KNN?

(K-NN) to wszechstronny i szeroko stosowany algorytm uczenia maszynowego, używany przede wszystkim ze względu na prostotę i łatwość implementacji. Nie wymaga żadnych założeń dotyczących rozkładu danych bazowych. Może także obsługiwać zarówno dane liczbowe, jak i kategorialne, co czyni go elastycznym wyborem w przypadku różnych typów zbiorów danych w zadaniach klasyfikacji i regresji. Jest to metoda nieparametryczna, która dokonuje prognoz na podstawie podobieństwa punktów danych w danym zbiorze danych. K-NN jest mniej wrażliwy na wartości odstające w porównaniu z innymi algorytmami.

Algorytm K-NN działa poprzez znalezienie K najbliższych sąsiadów danego punktu danych na podstawie metryki odległości, takiej jak odległość euklidesowa. Klasa lub wartość punktu danych jest następnie określana większością głosów lub średnią K sąsiadów. Takie podejście umożliwia algorytmowi dostosowywanie się do różnych wzorców i dokonywanie przewidywań w oparciu o lokalną strukturę danych.

Metryki odległości stosowane w algorytmie KNN

Jak wiemy, algorytm KNN pomaga nam zidentyfikować najbliższe punkty lub grupy dla punktu zapytania. Aby jednak określić najbliższe grupy lub najbliższe punkty punktu zapytania, potrzebujemy pewnej metryki. W tym celu używamy poniższych wskaźników odległości:

Odległość euklidesowa

Jest to nic innego jak odległość kartezjańska pomiędzy dwoma punktami znajdującymi się na płaszczyźnie/hiperpłaszczyźnie. Odległość euklidesowa można również przedstawić jako długość linii prostej łączącej dwa brane pod uwagę punkty. Ta metryka pomaga nam obliczyć przemieszczenie netto pomiędzy dwoma stanami obiektu.

ext{odległość}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Odległość Manhattanu

Odległość Manhattanu metryka jest powszechnie używana, gdy interesuje nas całkowita odległość przebyta przez obiekt, a nie przemieszczenie. Metrykę tę oblicza się poprzez zsumowanie bezwzględnej różnicy między współrzędnymi punktów w n-wymiarach.

dlewo ( x,y prawo )={sum_{i=1}^{n}lewo | x_i-y_i ight |}

Odległość Minkowskiego

Można powiedzieć, że zarówno odległość euklidesowa, jak i odległość manhattańska są szczególnymi przypadkami Odległość Minkowskiego .

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

różnica między lodem a śniegiem

Z powyższego wzoru możemy powiedzieć, że gdy p = 2 to jest to samo co wzór na odległość euklidesową, a gdy p = 1 to otrzymujemy wzór na odległość Manhattanu.

Omówione powyżej metryki są najczęściej spotykane w przypadku a Nauczanie maszynowe problem, ale istnieją również inne wskaźniki odległości Odległość Hamminga które są przydatne przy rozwiązywaniu problemów wymagających nakładających się porównań między dwoma wektorami, których zawartość może być wartością logiczną lub ciągiem znaków.

Jak wybrać wartość k dla algorytmu KNN?

Wartość k jest bardzo istotna w algorytmie KNN przy określaniu liczby sąsiadów w algorytmie. Wartość k w algorytmie k-najbliższych sąsiadów (k-NN) należy dobierać na podstawie danych wejściowych. Jeśli dane wejściowe mają więcej wartości odstających lub szumów, lepsza będzie wyższa wartość k. Zaleca się wybranie nieparzystej wartości k, aby uniknąć remisów w klasyfikacji. Walidacja krzyżowa Metody mogą pomóc w wyborze najlepszej wartości k dla danego zbioru danych.

Działanie algorytmu KNN

Algorytm K-Nearest Neighbours (KNN) działa na zasadzie podobieństwa, gdzie przewiduje etykietę lub wartość nowego punktu danych, biorąc pod uwagę etykiety lub wartości K najbliższych sąsiadów w zbiorze danych uczących.

Działanie algorytmu KNN

Poniżej omówiono szczegółowe wyjaśnienie działania KNN:

Krok 1: Wybór optymalnej wartości K

  • K reprezentuje liczbę najbliższych sąsiadów, które należy wziąć pod uwagę podczas przewidywania.

Krok 2: Obliczanie odległości

  • Aby zmierzyć podobieństwo między punktami danych docelowych i treningowych, używana jest odległość euklidesowa. Odległość jest obliczana pomiędzy każdym punktem danych w zestawie danych a punktem docelowym.

Krok 3: Znajdowanie najbliższych sąsiadów

  • K punktów danych o najmniejszej odległości od punktu docelowego to najbliżsi sąsiedzi.

Krok 4: Głosowanie na klasyfikację lub przyjęcie średniej do regresji

  • W problemie klasyfikacyjnym etykiety klas są określane w drodze głosowania większościowego. Klasa z największą liczbą wystąpień wśród sąsiadów staje się klasą przewidywaną dla docelowego punktu danych.
  • W problemie regresji etykieta klasy jest obliczana poprzez średnią wartości docelowych K najbliższych sąsiadów. Obliczona średnia wartość staje się przewidywanym wynikiem dla docelowego punktu danych.

Niech X będzie zbiorem danych szkoleniowych z n punktami danych, gdzie każdy punkt danych jest reprezentowany przez d-wymiarowy wektor cech X_ii Y będą odpowiednimi etykietami lub wartościami dla każdego punktu danych w X. Mając nowy punkt danych x, algorytm oblicza odległość między x a każdym punktem danych X_iw X przy użyciu metryki odległości, takiej jak odległość euklidesowa: ext{odległość}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Algorytm wybiera K punktów danych spośród X, które mają najkrótszą odległość do x. W przypadku zadań klasyfikacyjnych algorytm przypisuje x etykietę y, która występuje najczęściej wśród K najbliższych sąsiadów. W przypadku zadań regresyjnych algorytm oblicza średnią lub średnią ważoną wartości y K najbliższych sąsiadów i przypisuje ją jako przewidywaną wartość dla x.

Zalety algorytmu KNN

  • Łatwe do wdrożenia ponieważ złożoność algorytmu nie jest zbyt duża.
  • Łatwo się dostosowuje – Zgodnie z działaniem algorytmu KNN przechowuje on wszystkie dane w pamięci i dlatego za każdym razem, gdy dodawany jest nowy przykład lub punkt danych, algorytm dostosowuje się zgodnie z tym nowym przykładem i ma również swój wkład w przyszłe przewidywania.
  • Niewiele hiperparametrów – Jedynymi parametrami wymaganymi przy szkoleniu algorytmu KNN jest wartość k i wybór metryki odległości, którą chcielibyśmy wybrać z naszej metryki ewaluacyjnej.

Wady algorytmu KNN

  • Nie skaluje się – Jak już o tym słyszeliśmy, algorytm KNN jest również uważany za algorytm leniwy. Główne znaczenie tego terminu polega na tym, że wymaga to dużej mocy obliczeniowej i przechowywania danych. To sprawia, że ​​algorytm ten jest zarówno czasochłonny, jak i wyczerpujący zasoby.
  • Przekleństwo wymiarowości – Istnieje termin znany jako zjawisko szczytowe, zgodnie z którym na algorytm KNN wpływa przekleństwo wymiarowości co oznacza, że ​​algorytmowi trudno jest poprawnie sklasyfikować punkty danych, gdy wymiarowość jest zbyt wysoka.
  • Skłonny do nadmiernego dopasowania – Ponieważ na algorytm wpływa klątwa wymiarowości, jest on również podatny na problem nadmiernego dopasowania. Stąd ogólnie wybór funkcji jak również redukcja wymiarowości stosowane są techniki radzenia sobie z tym problemem.

Przykładowy program:

Załóżmy, że 0 i 1 są dwoma klasyfikatorami (grupami).

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>częstotliwość2? 0:1); } // Kod sterownika int main() { int n = 17; // Liczba punktów danych Punkt arr[n]; tablica[0].x = 1; tablica[0].y = 12; tablica[0].val = 0; tablica[1].x = 2; tablica[1].y = 5; tablica[1].val = 0; tablica[2].x = 5; tablica[2].y = 3; arr[2].val = 1; tablica[3].x = 3; tablica[3].y = 2; arr[3].val = 1; tablica[4].x = 3; tablica[4].y = 6; tablica[4].val = 0; tablica[5].x = 1,5; tablica[5].y = 9; arr[5].val = 1; tablica[6].x = 7; tablica[6].y = 2; arr[6].val = 1; tablica[7].x = 6; tablica[7].y = 1; tablica[7].val = 1; tablica[8].x = 3,8; tablica[8].y = 3; tablica[8].val = 1; tablica[9].x = 3; tablica[9].y = 10; tablica[9].val = 0; tablica[10].x = 5,6; tablica[10].y = 4; arr[10].val = 1; tablica[11].x = 4; tablica[11].y = 2; arr[11].val = 1; tablica[12].x = 3,5; tablica[12].y = 8; tablica[12].val = 0; tablica[13].x = 2; tablica[13].y = 11; tablica[13].val = 0; tablica[14].x = 2; tablica[14].y = 5; arr[14].val = 1; tablica[15].x = 2; tablica[15].y = 9; tablica[15].val = 0; tablica[16].x = 1; tablica[16].y = 7; tablica[16].val = 0; /*Punkt testowy*/ Punkt p; p.x = 2,5; p.y = 7; // Parametr decydujący o grupie punktów testowych int k = 3; printf ('Wartość sklasyfikowana w nieznanym punkcie' ' to %d. ', classifyAPoint(arr, n, k, p)); zwróć 0; }>
>
>

Jawa

// 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.odległość) powrót 1; zwróć 0; } } // Ta funkcja znajduje klasyfikację punktu p przy użyciu // algorytmu najbliższego sąsiada k. Zakłada tylko dwie // grupy i zwraca 0, jeśli p należy do grupy 0, w przeciwnym razie // 1 (należy do grupy 1). static int classifyAPoint(Point arr[], int n, int k, Point p) { // Wypełnij odległości wszystkich punktów od p for (int i = 0; i arr[i].distance = Math.sqrt( (arr[ i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - py) * (arr[i].y - p.y)); // Sortuj punkty według odległości od p Arrays.sort(arr, nowe porównanie()); // Teraz rozważmy k pierwszych elementów i // dwie grupy int freq1 = 0; // Częstotliwość grupy 0 int freq2 = 0; (int i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (częstotliwość1> częstotliwość2 ? 0:1); } / / Kod sterownika public static void main(String[] args) { int n = 17; // Liczba punktów danych Point[] arr = nowy 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>częstotliwość2>else> 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>częstotliwość2? 0:1); } statyczne void Main() { int n = 17; // Liczba punktów danych Lista arr = new List(); for(int i = 0; i arr.Add(nowy punkt()); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1] .x = 2; tablica[1].y = 5; tablica[1].val = 0; tablica[2].y = 3; tablica[3].x = 3; tablica[3].y = 2; tablica[4].x = 3; tablica[4].y = 6; val = 0; arr[5].x = 1,5; arr[5].y = 9; arr[6].x = 7; arr[6].y = 2; [6].val = 1; arr[7].x = 6; arr[7].val = 1; arr[8].x = 3,8; = 3; tablica[8].val = 1; tablica[9].x = 3; tablica[9].val = 0; tablica[10].x = 5,6; 10].y = 4; tablica[10].val = 1; tablica[11].x = 4; tablica[11].val = 1; 3,5; tablica[12].y = 8; tablica[12].val = 0; tablica[13].y = 11; tablica[13].val = 0; .x = 2; tablica[14].y = 5; tablica[14].val = 1; tablica[15].y = 9; ; arr[16].x = 1; arr[16].val = 0; /*Punkt testowy*/ Punkt p = nowy punkt(); p.x = 2,5; // Parametr decydujący o grupie punktów testowych int k = 3; Console.WriteLine('Wartość sklasyfikowana w nieznanym punkcie to ' + classifyAPoint(arr, n, k, p)); } } // Kod został napisany przez Nidhi goela.>
>
>

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.odległość) { powrót 1; } zwróć 0; } } // Ta funkcja znajduje klasyfikację punktu p przy użyciu // algorytmu najbliższego sąsiada k. Zakłada tylko dwie // grupy i zwraca 0, jeśli p należy do grupy 0, w przeciwnym razie // 1 (należy do grupy 1). funkcja classifyAPoint(arr, n, k, p) { // Wypełnij odległości wszystkich punktów od p dla (let i = 0; i arr[i].distance = Math.sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - py) * (arr[i].y - p.y)); } // Sortuj punkty według odległości od p arr.sort(new Comparison()); // Teraz rozważmy k pierwszych elementów i tylko dwie grupy niech freq1 = 0; // Częstotliwość grupy 0 niech freq2 = 0; // Częstotliwość grupy 1 dla (let i = 0; i if (arr [i].val === 0) { freq1++; } else if (arr[i].val === 1) { freq2++; } } return freq1> freq2 ? 0 : 1 } // Kod sterownika n = 17; // Liczba punktów danych const arr = new Array(n); for (let i = 0; tj<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.odległość) powrót 1; zwróć 0; }); // Teraz rozważmy k pierwszych elementów i tylko dwie grupy niech freq1 = 0; // Częstotliwość grupy 0 niech freq2 = 0; // Częstotliwość grupy 1 for (let i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return freq1> freq2 ? 0 : 1; }>
>
>

Wyjście: 

The value classified as an unknown point is 0.>

Złożoność czasowa: O(N * logN)
Przestrzeń pomocnicza: O(1)

Zastosowania algorytmu KNN

  • Wstępne przetwarzanie danych – Zajmując się jakimkolwiek problemem uczenia maszynowego, najpierw wykonujemy Przypis KNN co jest dość skuteczną reklamą powszechnie stosowaną w wyrafinowanych metodologiach imputacji.
  • Rozpoznawanie wzorców – Algorytmy KNN działają bardzo dobrze, jeśli wytrenowałeś algorytm KNN na zbiorze danych MNIST, a następnie przeprowadziłeś proces ewaluacji, to musiałeś spotkać się z faktem, że dokładność jest zbyt duża.
  • Silniki rekomendacji – Głównym zadaniem algorytmu KNN jest przypisanie nowego punktu zapytania do już istniejącej grupy, która została utworzona z wykorzystaniem ogromnego korpusu zbiorów danych. To jest dokładnie to, czego wymaga się w K Najbliżsi sąsiedzi z Pythonem | ML
  • Implementacja K-Nearest Neighbours od podstaw przy użyciu języka Python
  • Matematyczne wyjaśnienie K-najbliższego sąsiada
  • Ważona K-NN

Często zadawane pytania (FAQ)

P. Dlaczego KNN jest leniwym uczniem?

Algorytm KNN nie buduje modelu w fazie uczenia. Algorytm zapamiętuje cały zbiór uczący i wykonuje na nim działania w momencie klasyfikacji.

P. Dlaczego KNN jest nieparametryczny?

Algorytm KNN nie przyjmuje założeń dotyczących danych, które analizuje.

P. Jaka jest różnica między KNN i K?

  • KNN to nadzorowany model uczenia maszynowego używany do rozwiązywania problemów klasyfikacyjnych, podczas gdy K-średnie to model nienadzorowanego uczenia maszynowego używany do grupowania.
  • K w KNN to liczba najbliższych sąsiadów, podczas gdy K w K oznacza liczbę klastrów.