logo

TechCodeview

K-Nearest Neighbor (KNN)-Algorithmus

Der K-Nearest Neighbors (KNN)-Algorithmus ist eine überwachte Methode des maschinellen Lernens, die zur Lösung von Klassifizierungs- und Regressionsproblemen eingesetzt wird. Evelyn Fix und Joseph Hodges entwickelten diesen Algorithmus 1951, der anschließend von Thomas Cover erweitert wurde. Der Artikel untersucht die Grundlagen, Funktionsweise und Implementierung des KNN-Algorithmus.

Was ist der K-Nearest Neighbors-Algorithmus?

KNN ist einer der grundlegendsten und zugleich wichtigsten Klassifizierungsalgorithmen im maschinellen Lernen. Es gehört zum überwachtes Lernen Domäne und findet intensive Anwendung in der Mustererkennung, Es ist in realen Szenarien weit verbreitet, da es nicht parametrisch ist, was bedeutet, dass es keine zugrunde liegenden Annahmen über die Verteilung von Daten trifft (im Gegensatz zu anderen Algorithmen wie GMM, die von a Gaußsche Verteilung der angegebenen Daten). Wir erhalten einige Vordaten (auch Trainingsdaten genannt), die Koordinaten in durch ein Attribut identifizierte Gruppen einteilen.



burak ozcivit

Betrachten Sie als Beispiel die folgende Tabelle mit Datenpunkten, die zwei Features enthalten:

Arbeitsvisualisierung des KNN-Algorithmus

Arbeitsvisualisierung des KNN-Algorithmus

Ordnen Sie nun anhand eines anderen Satzes von Datenpunkten (auch Testdaten genannt) diese Punkte einer Gruppe zu, indem Sie den Trainingssatz analysieren. Beachten Sie, dass die nicht klassifizierten Punkte als „Weiß“ markiert sind.



Intuition hinter dem KNN-Algorithmus

Wenn wir diese Punkte in einem Diagramm darstellen, können wir möglicherweise einige Cluster oder Gruppen lokalisieren. Nun können wir einen gegebenen, nicht klassifizierten Punkt einer Gruppe zuordnen, indem wir beobachten, zu welcher Gruppe seine nächsten Nachbarn gehören. Dies bedeutet, dass ein Punkt in der Nähe einer als „Rot“ klassifizierten Punktegruppe eine höhere Wahrscheinlichkeit hat, als „Rot“ klassifiziert zu werden.

Intuitiv können wir erkennen, dass der erste Punkt (2.5, 7) als „Grün“ und der zweite Punkt (5.5, 4.5) als „Rot“ klassifiziert werden sollte.

Warum brauchen wir einen KNN-Algorithmus?

Der (K-NN)-Algorithmus ist ein vielseitiger und weit verbreiteter Algorithmus für maschinelles Lernen, der vor allem wegen seiner Einfachheit und einfachen Implementierung verwendet wird. Es sind keine Annahmen über die zugrunde liegende Datenverteilung erforderlich. Es kann sowohl numerische als auch kategoriale Daten verarbeiten und ist somit eine flexible Wahl für verschiedene Arten von Datensätzen bei Klassifizierungs- und Regressionsaufgaben. Es handelt sich um eine nichtparametrische Methode, die Vorhersagen auf der Grundlage der Ähnlichkeit von Datenpunkten in einem bestimmten Datensatz trifft. K-NN reagiert im Vergleich zu anderen Algorithmen weniger empfindlich auf Ausreißer.



Der K-NN-Algorithmus funktioniert, indem er die K nächsten Nachbarn eines bestimmten Datenpunkts basierend auf einer Distanzmetrik, wie z. B. der euklidischen Distanz, findet. Die Klasse oder der Wert des Datenpunkts wird dann durch die Mehrheitsentscheidung oder den Durchschnitt der K Nachbarn bestimmt. Dieser Ansatz ermöglicht es dem Algorithmus, sich an unterschiedliche Muster anzupassen und Vorhersagen basierend auf der lokalen Struktur der Daten zu treffen.

Im KNN-Algorithmus verwendete Entfernungsmetriken

Wie wir wissen, hilft uns der KNN-Algorithmus dabei, die nächstgelegenen Punkte oder Gruppen für einen Abfragepunkt zu identifizieren. Aber um die nächstgelegenen Gruppen oder die nächstgelegenen Punkte für einen Abfragepunkt zu bestimmen, benötigen wir eine Metrik. Zu diesem Zweck verwenden wir die folgenden Distanzmetriken:

Euklidische Entfernung

Dies ist nichts anderes als der kartesische Abstand zwischen den beiden Punkten, die in der Ebene/Hyperebene liegen. Euklidische Entfernung kann auch als Länge der Geraden dargestellt werden, die die beiden betrachteten Punkte verbindet. Diese Metrik hilft uns, die Nettoverschiebung zwischen den beiden Zuständen eines Objekts zu berechnen.

ext{Abstand}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Manhattan-Entfernung

Manhattan-Entfernung Metrik wird im Allgemeinen verwendet, wenn wir an der vom Objekt zurückgelegten Gesamtstrecke und nicht an der Verschiebung interessiert sind. Diese Metrik wird berechnet, indem die absolute Differenz zwischen den Koordinaten der Punkte in n-Dimensionen summiert wird.

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

Minkowski-Distanz

Wir können sagen, dass sowohl die Euklidische als auch die Manhattan-Distanz Sonderfälle der Distanz sind Minkowski-Distanz .

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

Aus der obigen Formel können wir sagen, dass, wenn p = 2 ist, sie mit der Formel für den euklidischen Abstand identisch ist und wenn p = 1, dann erhalten wir die Formel für den Manhattan-Abstand.

Die oben besprochenen Metriken kommen am häufigsten beim Umgang mit a vor Maschinelles Lernen Problem, aber es gibt auch andere Entfernungsmetriken wie Hamming-Distanz Dies ist praktisch bei der Lösung von Problemen, die überlappende Vergleiche zwischen zwei Vektoren erfordern, deren Inhalte sowohl boolesche Werte als auch Zeichenfolgenwerte sein können.

Was ist Maven?

Wie wählt man den Wert von k für den KNN-Algorithmus?

Der Wert von k ist im KNN-Algorithmus sehr wichtig, um die Anzahl der Nachbarn im Algorithmus zu definieren. Der Wert von k im k-NN-Algorithmus (k-nearest neighbours) sollte basierend auf den Eingabedaten ausgewählt werden. Wenn die Eingabedaten mehr Ausreißer oder Rauschen aufweisen, wäre ein höherer Wert von k besser. Es wird empfohlen, einen ungeraden Wert für k zu wählen, um Unstimmigkeiten in der Klassifizierung zu vermeiden. Kreuzvalidierung Methoden können bei der Auswahl des besten k-Werts für den gegebenen Datensatz helfen.

Funktionsweise des KNN-Algorithmus

Der K-Nearest Neighbors (KNN)-Algorithmus arbeitet nach dem Ähnlichkeitsprinzip, bei dem er die Bezeichnung oder den Wert eines neuen Datenpunkts vorhersagt, indem er die Bezeichnungen oder Werte seiner K nächsten Nachbarn im Trainingsdatensatz berücksichtigt.

Funktionsweise des KNN-Algorithmus

Im Folgenden wird Schritt für Schritt erklärt, wie KNN funktioniert:

Schritt 1: Auswahl des optimalen Werts von K

  • K stellt die Anzahl der nächsten Nachbarn dar, die bei der Vorhersage berücksichtigt werden müssen.

Schritt 2: Entfernung berechnen

  • Um die Ähnlichkeit zwischen Ziel- und Trainingsdatenpunkten zu messen, wird die euklidische Distanz verwendet. Der Abstand wird zwischen jedem Datenpunkt im Datensatz und dem Zielpunkt berechnet.

Schritt 3: Nächste Nachbarn finden

  • Die k Datenpunkte mit den geringsten Abständen zum Zielpunkt sind die nächsten Nachbarn.

Schritt 4: Für die Klassifizierung abstimmen oder den Durchschnitt für die Regression bilden

  • Beim Klassifizierungsproblem werden die Klassenbezeichnungen durch Mehrheitsentscheidung bestimmt. Die Klasse mit den meisten Vorkommen unter den Nachbarn wird zur vorhergesagten Klasse für den Zieldatenpunkt.
  • Beim Regressionsproblem wird die Klassenbezeichnung berechnet, indem der Durchschnitt der Zielwerte von K nächsten Nachbarn gebildet wird. Der berechnete Durchschnittswert wird zur vorhergesagten Ausgabe für den Zieldatenpunkt.

Sei X der Trainingsdatensatz mit n Datenpunkten, wobei jeder Datenpunkt durch einen d-dimensionalen Merkmalsvektor dargestellt wird X_iund Y seien die entsprechenden Beschriftungen oder Werte für jeden Datenpunkt in X. Bei einem neuen Datenpunkt x berechnet der Algorithmus den Abstand zwischen x und jedem Datenpunkt X_iin X unter Verwendung einer Distanzmetrik, wie z. B. der euklidischen Distanz: ext{Abstand}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Der Algorithmus wählt die K Datenpunkte von X aus, die den kürzesten Abstand zu x haben. Für Klassifizierungsaufgaben weist der Algorithmus die Bezeichnung y zu, die unter den K nächsten Nachbarn von x am häufigsten vorkommt. Für Regressionsaufgaben berechnet der Algorithmus den Durchschnitt oder gewichteten Durchschnitt der Werte y der K nächsten Nachbarn und weist ihn als vorhergesagten Wert für x zu.

Vorteile des KNN-Algorithmus

  • Einfach umzusetzen da die Komplexität des Algorithmus nicht so hoch ist.
  • Passt sich leicht an – Gemäß der Funktionsweise des KNN-Algorithmus werden alle Daten im Arbeitsspeicher gespeichert und daher passt sich der Algorithmus jedes Mal, wenn ein neues Beispiel oder ein neuer Datenpunkt hinzugefügt wird, an dieses neue Beispiel an und leistet auch seinen Beitrag zu den zukünftigen Vorhersagen.
  • Wenige Hyperparameter – Die einzigen Parameter, die beim Training eines KNN-Algorithmus erforderlich sind, sind der Wert von k und die Wahl der Distanzmetrik, die wir aus unserer Bewertungsmetrik auswählen möchten.

Nachteile des KNN-Algorithmus

  • Skaliert nicht – Da wir darüber gehört haben, wird der KNN-Algorithmus auch als Lazy-Algorithmus betrachtet. Die Hauptbedeutung dieses Begriffs besteht darin, dass dies sowohl viel Rechenleistung als auch Datenspeicher erfordert. Dies macht diesen Algorithmus sowohl zeitaufwändig als auch ressourcenintensiv.
  • Fluch der Dimensionalität – Es gibt einen Begriff, der als Peaking-Phänomen bekannt ist. Demnach wird der KNN-Algorithmus davon beeinflusst Fluch der Dimensionalität Dies bedeutet, dass es dem Algorithmus schwerfällt, die Datenpunkte richtig zu klassifizieren, wenn die Dimensionalität zu hoch ist.
  • Anfällig für Überanpassung – Da der Algorithmus vom Fluch der Dimensionalität betroffen ist, ist er auch anfällig für das Problem der Überanpassung. Daher generell Merkmalsauswahl sowie Dimensionsreduktion Es werden Techniken angewendet, um dieses Problem zu lösen.

Beispielprogramm:

Nehmen Sie 0 und 1 als die beiden Klassifikatoren (Gruppen) an.

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>freq2 ? 0 : 1); } // Treibercode int main() { int n = 17; // Anzahl der Datenpunkte 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; /*Testpunkt*/ Punkt p; p.x = 2,5; p.y = 7; // Parameter zum Bestimmen der Gruppe des Testpunkts int k = 3; printf ('Der an einen unbekannten Punkt klassifizierte Wert' ' ist %d. ', classifyAPoint(arr, n, k, p)); 0 zurückgeben; }>
>
>

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.distanz) return 1; 0 zurückgeben; } } // Diese Funktion ermittelt die Klassifizierung von Punkt p mithilfe des // k-Nächste-Nachbarn-Algorithmus. Es nimmt nur zwei // Gruppen an und gibt 0 zurück, wenn p zu Gruppe 0 gehört, andernfalls // 1 (gehört zu Gruppe 1). static int classifyAPoint(Point arr[], int n, int k, Point p) { // Abstände aller Punkte von p füllen 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)); // Sortiere die Punkte nach Entfernung von p Arrays.sort(arr, neuer Vergleich()); // Betrachten Sie nun die ersten k Elemente und nur // zwei Gruppen int freq1 = 0; // Häufigkeit von Gruppe 1 für (int i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (freq1> freq2 ? 0 : 1); } / / Treibercode public static void main(String[] args) { int n = 17; // Anzahl der Datenpunkte 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>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>freq2 ? 0 : 1); } static void Main() { int n = 17; // Anzahl der Datenpunkte 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].y = 0; arr[2].x = 3; arr[3].x = 3; arr[3].y = 1; arr[4].x = 6; val = 0; arr[5].x = 1,5; arr[5].y = 1; arr[6].x = 2; [6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[8].y = 3; arr[8].x = 3; arr[9].x = 5,6; 10].y = 4; arr[11].x = 4; arr[11].x = 3.5; arr[12].y = 0; arr[13].x = 0; arr[13].x .x = 2; arr[14].y = 5; arr[15].x = 2; arr[15].val = 0 ; arr[16].x = 1; arr[16].val = 0; /*Testing Point*/ Punkt p = 2,5; // Parameter zum Bestimmen der Gruppe des Testpunkts int k = 3; Console.WriteLine('Der als unbekannter Punkt klassifizierte Wert ist ' + classifyAPoint(arr, n, k, p)); } } // Der Code wurde von Nidhi Goel beigesteuert.>
>
>

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; } return 0; } } // Diese Funktion ermittelt die Klassifizierung von Punkt p mithilfe des // k-Nächste-Nachbarn-Algorithmus. Es nimmt nur zwei // Gruppen an und gibt 0 zurück, wenn p zu Gruppe 0 gehört, andernfalls // 1 (gehört zu Gruppe 1). function classifyAPoint(arr, n, k, p) { // Abstände aller Punkte von p füllen 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)); // Sortiere die Punkte nach Entfernung von p arr.sort(new Vergleich()); // Betrachten Sie nun die ersten k Elemente und nur zwei Gruppen. Let freq1 = 0; // Häufigkeit von Gruppe 0, let freq2 = 0; [i].val === 0) { freq1++; } else if (arr[i].val === 1) { freq2 ? 0 : 1; } // Treibercode const n = 17; // Anzahl der Datenpunkte const arr = 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.distanz) return 1; 0 zurückgeben; }); // Betrachten Sie nun die ersten k Elemente und nur zwei Gruppen let freq1 = 0; // Häufigkeit von Gruppe 0 let freq2 = 0; // Häufigkeit von Gruppe 1 for (let i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return freq1> freq2 ? 0 : 1; }>
>
>

Ausgabe: 

The value classified as an unknown point is 0.>

Zeitkomplexität: O(N * logN)
Hilfsraum: O(1)

Anwendungen des KNN-Algorithmus

  • Datenvorverarbeitung – Wenn wir uns mit einem Problem des maschinellen Lernens befassen, führen wir zunächst Folgendes durch KNN-Imputation Dies ist sehr effektiv und wird im Allgemeinen für anspruchsvolle Imputationsmethoden verwendet.
  • Mustererkennung – KNN-Algorithmen funktionieren sehr gut. Wenn Sie einen KNN-Algorithmus mithilfe des MNIST-Datensatzes trainiert und dann den Bewertungsprozess durchgeführt haben, müssen Sie feststellen, dass die Genauigkeit zu hoch ist.
  • Empfehlungsmaschinen – Die Hauptaufgabe eines KNN-Algorithmus besteht darin, einer bereits vorhandenen Gruppe, die mithilfe eines riesigen Datensatzes erstellt wurde, einen neuen Abfragepunkt zuzuweisen. Genau das ist in der gefordert K Nächste Nachbarn mit Python | ML
  • Implementierung von K-Nearest Neighbors von Grund auf mit Python
  • Mathematische Erklärung von K-Nearest Neighbor
  • Gewichtetes K-NN

Häufig gestellte Fragen (FAQs)

F. Warum ist KNN ein fauler Lerner?

Der KNN-Algorithmus erstellt während der Trainingsphase kein Modell. Der Algorithmus speichert den gesamten Trainingsdatensatz und führt zum Zeitpunkt der Klassifizierung Aktionen am Datensatz aus.

F. Warum ist KNN nichtparametrisch?

Der KNN-Algorithmus trifft keine Annahmen über die Daten, die er analysiert.

F. Was ist der Unterschied zwischen KNN und K?

  • KNN ist ein überwachtes maschinelles Lernmodell, das für Klassifizierungsprobleme verwendet wird, während K-means ein unbeaufsichtigtes maschinelles Lernmodell ist, das für Clustering verwendet wird.
  • Das K in KNN ist die Anzahl der nächsten Nachbarn, während das K in K die Anzahl der Cluster ist.