logo

TechCodeview

K-dichtstbijzijnde buuralgoritme (KNN).

De K-Nearest Neighbours (KNN)-algoritme is een machine learning-methode onder toezicht die wordt gebruikt om classificatie- en regressieproblemen aan te pakken. Evelyn Fix en Joseph Hodges ontwikkelden dit algoritme in 1951, dat vervolgens werd uitgebreid door Thomas Cover. Het artikel onderzoekt de grondbeginselen, werking en implementatie van het KNN-algoritme.

Wat is het K-Nearest Neighbours-algoritme?

KNN is een van de meest basale maar essentiële classificatie-algoritmen in machine learning. Het behoort tot de leren onder toezicht domein en vindt intensieve toepassing in patroonherkenning, Het is breed inzetbaar in praktijkscenario's, omdat het niet-parametrisch is, wat betekent dat er geen onderliggende aannames worden gedaan over de distributie van gegevens (in tegenstelling tot andere algoritmen zoals GMM, die uitgaan van een Gaussische verdeling van de opgegeven gegevens). We krijgen een aantal eerdere gegevens (ook wel trainingsgegevens genoemd), die coördinaten classificeren in groepen die worden geïdentificeerd door een attribuut.

git alles toevoegen

Beschouw als voorbeeld de volgende tabel met gegevenspunten die twee kenmerken bevat:



KNN-algoritme werkvisualisatie

KNN-algoritme werkvisualisatie

Gegeven een andere set datapunten (ook wel testgegevens genoemd), wijst u deze punten nu toe aan een groep door de trainingsset te analyseren. Merk op dat de niet-geclassificeerde punten zijn gemarkeerd als ‘Wit’.

Intuïtie achter het KNN-algoritme

Als we deze punten in een grafiek weergeven, kunnen we mogelijk enkele clusters of groepen lokaliseren. Nu we een niet-geclassificeerd punt hebben gegeven, kunnen we het aan een groep toewijzen door te observeren tot welke groep de dichtstbijzijnde buren behoren. Dit betekent dat een punt dat dicht bij een cluster van punten ligt dat als ‘Rood’ is geclassificeerd, een grotere kans heeft om als ‘Rood’ te worden geclassificeerd.

Intuïtief kunnen we zien dat het eerste punt (2,5, 7) als ‘Groen’ moet worden geclassificeerd, en het tweede punt (5,5, 4,5) als ‘Rood’.

Waarom hebben we een KNN-algoritme nodig?

(K-NN)-algoritme is een veelzijdig en veelgebruikt machine learning-algoritme dat vooral wordt gebruikt vanwege zijn eenvoud en implementatiegemak. Er zijn geen aannames nodig over de onderliggende gegevensverdeling. Het kan ook zowel numerieke als categorische gegevens verwerken, waardoor het een flexibele keuze is voor verschillende soorten datasets bij classificatie- en regressietaken. Het is een niet-parametrische methode die voorspellingen doet op basis van de gelijkenis van datapunten in een bepaalde dataset. K-NN is minder gevoelig voor uitschieters in vergelijking met andere algoritmen.

Het K-NN-algoritme werkt door de K te vinden die het dichtst bij een bepaald gegevenspunt ligt op basis van een afstandsmetriek, zoals de Euclidische afstand. De klasse of waarde van het datapunt wordt vervolgens bepaald door de meerderheid van stemmen of het gemiddelde van de K-buren. Dankzij deze aanpak kan het algoritme zich aanpassen aan verschillende patronen en voorspellingen doen op basis van de lokale structuur van de gegevens.

Afstandsstatistieken gebruikt in het KNN-algoritme

Zoals we weten helpt het KNN-algoritme ons bij het identificeren van de dichtstbijzijnde punten of de groepen voor een vraagpunt. Maar om de dichtstbijzijnde groepen of de dichtstbijzijnde punten voor een vraagpunt te bepalen, hebben we een metriek nodig. Voor dit doel gebruiken we onderstaande afstandsstatistieken:

Euclidische afstand

Dit is niets anders dan de cartesiaanse afstand tussen de twee punten die zich in het vlak/hypervlak bevinden. Euclidische afstand kan ook worden gevisualiseerd als de lengte van de rechte lijn die de twee punten verbindt die in beschouwing worden genomen. Deze metriek helpt ons bij het berekenen van de netto verplaatsing tussen de twee toestanden van een object.

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

Manhattan-afstand

Manhattan-afstand Metriek wordt over het algemeen gebruikt als we geïnteresseerd zijn in de totale afstand die het object heeft afgelegd in plaats van in de verplaatsing. Deze metriek wordt berekend door het absolute verschil tussen de coördinaten van de punten in n-dimensies op te tellen.

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

Minkowski-afstand

We kunnen zeggen dat zowel de Euclidische als de Manhattan-afstand speciale gevallen zijn van de Minkowski-afstand .

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

Uit de bovenstaande formule kunnen we zeggen dat als p = 2 dit hetzelfde is als de formule voor de Euclidische afstand en als p = 1 we de formule voor de Manhattan-afstand verkrijgen.

De hierboven besproken statistieken komen het meest voor bij het omgaan met a Machinaal leren probleem, maar er zijn ook andere afstandsmetrieken zoals Hamming-afstand die van pas komen bij het omgaan met problemen die overlappende vergelijkingen vereisen tussen twee vectoren waarvan de inhoud zowel Booleaanse als stringwaarden kan zijn.

Hoe kies je de waarde van k voor het KNN-algoritme?

De waarde van k is zeer cruciaal in het KNN-algoritme om het aantal buren in het algoritme te definiëren. De waarde van k in het algoritme k-dichtstbijzijnde buren (k-NN) moet worden gekozen op basis van de invoergegevens. Als de invoergegevens meer uitschieters of ruis bevatten, zou een hogere waarde van k beter zijn. Het wordt aanbevolen om een ​​oneven waarde voor k te kiezen om gelijkspel in de classificatie te voorkomen. Kruisvalidatie methoden kunnen helpen bij het selecteren van de beste k-waarde voor de gegeven dataset.

Werking van het KNN-algoritme

Het K-Nearest Neighbours (KNN)-algoritme werkt volgens het principe van gelijkenis, waarbij het het label of de waarde van een nieuw datapunt voorspelt door de labels of waarden van zijn K dichtstbijzijnde buren in de trainingsdataset te beschouwen.

Werking van het KNN-algoritme

Hieronder wordt stap voor stap uitgelegd hoe KNN werkt:

Stap 1: Het selecteren van de optimale waarde van K

  • K vertegenwoordigt het aantal naaste buren waarmee rekening moet worden gehouden bij het maken van voorspellingen.

Stap 2: Afstand berekenen

  • Om de gelijkenis tussen doel- en trainingsgegevenspunten te meten, wordt de Euclidische afstand gebruikt. De afstand wordt berekend tussen elk van de gegevenspunten in de gegevensset en het richtpunt.

Stap 3: Het vinden van dichtstbijzijnde buren

  • De k datapunten met de kleinste afstanden tot het richtpunt zijn de dichtstbijzijnde buren.

Stap 4: Stemmen voor classificatie of het gemiddelde nemen voor regressie

  • In het classificatieprobleem worden de klassenlabels bepaald door meerderheidsstemming uit te voeren. De klasse met de meeste voorvallen onder de buren wordt de voorspelde klasse voor het doelgegevenspunt.
  • In het regressieprobleem wordt het klassenlabel berekend door het gemiddelde te nemen van de doelwaarden van K naaste buren. De berekende gemiddelde waarde wordt de voorspelde uitvoer voor het doelgegevenspunt.

Laat X de trainingsgegevensset zijn met n gegevenspunten, waarbij elk gegevenspunt wordt weergegeven door een d-dimensionale kenmerkvector X_ien Y zijn de overeenkomstige labels of waarden voor elk datapunt in X. Gegeven een nieuw datapunt x, berekent het algoritme de afstand tussen x en elk datapunt X_iin X met behulp van een afstandsmetriek, zoals de Euclidische afstand: ext{afstand}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Het algoritme selecteert de K-gegevenspunten uit X die de kortste afstanden tot x hebben. Voor classificatietaken kent het algoritme het label y toe dat het meest voorkomt onder de K die het dichtst bij x liggen. Voor regressietaken berekent het algoritme het gemiddelde of gewogen gemiddelde van de waarden y van de K naaste buren en wijst dit toe als de voorspelde waarde voor x.

Lijst sorteer Java

Voordelen van het KNN-algoritme

  • Eenvoudig te implementeren omdat de complexiteit van het algoritme niet zo hoog is.
  • Past zich gemakkelijk aan – Volgens de werking van het KNN-algoritme slaat het alle gegevens op in geheugenopslag en dus wanneer een nieuw voorbeeld of datapunt wordt toegevoegd, past het algoritme zichzelf aan volgens dat nieuwe voorbeeld en levert het ook zijn bijdrage aan de toekomstige voorspellingen.
  • Weinig hyperparameters – De enige parameters die vereist zijn bij de training van een KNN-algoritme zijn de waarde van k en de keuze van de afstandsmetriek die we willen kiezen uit onze evaluatiemetriek.

Nadelen van het KNN-algoritme

  • Schaalt niet – Zoals we hierover hebben gehoord, wordt het KNN-algoritme ook als een lui algoritme beschouwd. De belangrijkste betekenis van deze term is dat dit zowel veel rekenkracht als gegevensopslag vergt. Dit maakt dit algoritme zowel tijdrovend als vermoeiend.
  • Vloek van de dimensionaliteit – Er is een term die bekend staat als het peaking-fenomeen, waarbij het KNN-algoritme wordt beïnvloed door de vloek van de dimensionaliteit wat impliceert dat het algoritme moeite heeft om de datapunten correct te classificeren als de dimensionaliteit te hoog is.
  • Gevoelig voor overfitting – Omdat het algoritme wordt beïnvloed door de vloek van de dimensionaliteit, is het ook gevoelig voor het probleem van overfitting. Vandaar in het algemeen functie selectie net zoals dimensionaliteitsreductie technieken worden toegepast om dit probleem aan te pakken.

Voorbeeldprogramma:

Veronderstel 0 en 1 als de twee classificatoren (groepen).

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>frequentie2? 0: 1); } // Stuurprogrammacode int main() { int n = 17; // Aantal datapunten Punt 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; /*Testpunt*/ Punt p; p.x = 2,5; p.y = 7; // Parameter om de groep van het testpunt te bepalen int k = 3; printf ('De waarde geclassificeerd als onbekend punt' ' is %d. ', classifyAPoint(arr, n, k, p)); retour 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.afstand) retour 1; retour 0; } } // Deze functie vindt de classificatie van punt p met behulp van // k dichtstbijzijnde buuralgoritme. Er wordt uitgegaan van slechts twee // groepen en wordt 0 geretourneerd als p tot groep 0 behoort, anders // 1 (behoort tot groep 1). static int classifyAPoint(Punt arr[], int n, int k, Punt p) {// Vul de afstanden van alle punten vanaf p voor (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) // Sorteer de punten op afstand vanaf p Arrays.sort(arr, nieuwe vergelijking()); // Beschouw nu de eerste k-elementen en alleen // twee groepen int freq1 = 0; // Frequentie van groep 0 int freq2 = 0 // Frequentie van groep 1 voor (int i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return (freq1> freq2 ? 0: 1); } / / Stuurprogrammacode public static void main(String[] args) { int n = 17; // Aantal datapunten Point[] arr = new Point[n] (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>frequentie2? 0: 1); } statische leegte Main() { int n = 17; // Aantal datapunten Lijst arr = new List(); for(int i = 0; i arr.Add(nieuw punt()); } 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[3].x = 3; arr[3].y = 2; arr[3].val = 1; arr[4].y = 6; waarde = 0; arr[5].x = 1,5; arr[5].y = 9; arr[5].x = 7; [6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[7].x = 3,8; = 3; arr[8].val = 1; arr[9].x = 3; arr[9].val = 0; 10].y = 4; arr[10].val = 1; arr[11].x = 4; arr[11].val = 1; 3,5; arr[12].y = 8; arr[12].val = 0; arr[13].y = 11; ].x = 2; arr[14].y = 5; arr[14].val = 1; arr[15].x = 2; ; arr[16].x = 1; arr[16].y = 7; arr[16].val = 0 /*Testpunt*/ Punt p = nieuw punt(); // Parameter om de groep van het testpunt te bepalen int k = 3; Console.WriteLine('De waarde geclassificeerd als onbekend punt is ' + classifyAPoint(arr, n, k, p)); } } // De code is bijgedragen door 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.afstand) { retour 1; } retourneer 0; } } // Deze functie vindt de classificatie van punt p met behulp van // k dichtstbijzijnde buuralgoritme. Er wordt uitgegaan van slechts twee // groepen en wordt 0 geretourneerd als p tot groep 0 behoort, anders // 1 (behoort tot groep 1). function classifyAPoint(arr, n, k, p) {// Vul afstanden van alle punten vanaf p voor (laat 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) } // Sorteer de punten op afstand vanaf p arr.sort(new Comparison()); // Beschouw nu de eerste k-elementen en slechts twee groepen, laat freq1 = 0; // Frequentie van groep 0, laat freq2 = 0; // Frequentie van groep 1 voor (laat i = 0; i if (arr [i].val === 0) { freq1++; } else if (arr[i].val === 1) { freq2++ } } return freq1> freq2 } // Stuurprogrammacode const n = 17; // Aantal datapunten const arr = new Array(n);<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.afstand) retour 1; retour 0; }); // Beschouw nu de eerste k-elementen en slechts twee groepen laten freq1 = 0; // Frequentie van groep 0 laat freq2 = 0; // Frequentie van groep 1 voor (let i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return freq1> freq2 ? 0 : 1; }>
>
>

Uitgang: 

The value classified as an unknown point is 0.>

Tijdcomplexiteit: O(N * logN)
Hulpruimte: O(1)

Toepassingen van het KNN-algoritme

  • Voorverwerking van gegevens – Bij het omgaan met elk Machine Learning-probleem voeren we eerst de KNN toeschrijven Dat is behoorlijk effectief en wordt over het algemeen gebruikt voor geavanceerde imputatiemethoden.
  • Patroonherkenning – KNN-algoritmen werken heel goed als je een KNN-algoritme hebt getraind met behulp van de MNIST-dataset en vervolgens het evaluatieproces hebt uitgevoerd, dan ben je vast wel eens tegengekomen dat de nauwkeurigheid te hoog is.
  • Aanbeveling motoren – De belangrijkste taak die door een KNN-algoritme wordt uitgevoerd, is het toewijzen van een nieuw zoekpunt aan een reeds bestaande groep die is gemaakt met behulp van een enorm corpus aan datasets. Dit is precies wat er nodig is in de K Dichtstbijzijnde buren met Python | ml
  • Implementatie van K-Nearest Neighbours from Scratch met behulp van Python
  • Wiskundige verklaring van K-dichtstbijzijnde buur
  • Gewogen K-NN

Veelgestelde vragen (FAQ's)

V. Waarom is KNN een luie leerling?

Het KNN-algoritme bouwt geen model tijdens de trainingsfase. Het algoritme onthoudt de volledige trainingsdataset en voert actie uit op de dataset op het moment van classificatie.

V. Waarom is KNN niet-parametrisch?

Het KNN-algoritme doet geen aannames over de gegevens die het analyseert.

V. Wat is het verschil tussen KNN en K-middelen?

  • KNN is een machine learning-model onder toezicht dat wordt gebruikt voor classificatieproblemen, terwijl K-means een machinaal leermodel zonder toezicht is dat wordt gebruikt voor clustering.
  • De K in KNN is het aantal dichtstbijzijnde buren, terwijl de K in K betekent het aantal clusters.