logo

TechCodeview

K-Närmaste Granne(KNN) Algoritm

De K-Nearest Neighbors (KNN) algoritm är en övervakad maskininlärningsmetod som används för att hantera klassificerings- och regressionsproblem. Evelyn Fix och Joseph Hodges utvecklade denna algoritm 1951, som sedan utökades av Thomas Cover. Artikeln utforskar grunderna, funktionerna och implementeringen av KNN-algoritmen.

Vad är K-Nearest Neighbors-algoritmen?

KNN är en av de mest grundläggande men väsentliga klassificeringsalgoritmerna inom maskininlärning. Den tillhör övervakat lärande domän och finner intensiv tillämpning i mönsterigenkänning, Det är allmänt tillgängligt i verkliga scenarier eftersom det är icke-parametriskt, vilket innebär att det inte gör några underliggande antaganden om distributionen av data (i motsats till andra algoritmer som GMM, som antar en Gaussisk fördelning av de givna uppgifterna). Vi får vissa tidigare data (även kallade träningsdata), som klassificerar koordinater i grupper som identifieras av ett attribut.

nätverkstopologier

Som ett exempel, betrakta följande tabell över datapunkter som innehåller två funktioner:



KNN Algoritm arbetar visualisering

KNN Algoritm arbetar visualisering

Nu, givet en annan uppsättning datapunkter (även kallad testdata), allokera dessa poäng till en grupp genom att analysera träningsuppsättningen. Observera att de oklassificerade punkterna är markerade som 'Vita'.

Intuition bakom KNN-algoritmen

Om vi ​​plottar dessa punkter på en graf kan vi kanske hitta några kluster eller grupper. Nu, givet en oklassificerad punkt, kan vi tilldela den till en grupp genom att observera vilken grupp dess närmaste grannar tillhör. Detta betyder att en punkt nära ett kluster av punkter som klassificeras som 'röda' har en högre sannolikhet att bli klassificerade som 'röda'.

Intuitivt kan vi se att den första punkten (2.5, 7) ska klassificeras som 'Grön' och den andra punkten (5.5, 4.5) ska klassificeras som 'röd'.

Varför behöver vi en KNN-algoritm?

(K-NN)-algoritmen är en mångsidig och allmänt använd maskininlärningsalgoritm som främst används för sin enkelhet och enkla implementering. Det kräver inga antaganden om den underliggande datadistributionen. Den kan också hantera både numerisk och kategorisk data, vilket gör den till ett flexibelt val för olika typer av datamängder i klassificerings- och regressionsuppgifter. Det är en icke-parametrisk metod som gör förutsägelser baserade på likheten mellan datapunkter i en given datamängd. K-NN är mindre känslig för extremvärden jämfört med andra algoritmer.

K-NN-algoritmen fungerar genom att hitta de K närmaste grannarna till en given datapunkt baserat på ett avståndsmått, såsom euklidiskt avstånd. Klassen eller värdet för datapunkten bestäms sedan av majoriteten av rösterna eller genomsnittet av K-grannarna. Detta tillvägagångssätt gör det möjligt för algoritmen att anpassa sig till olika mönster och göra förutsägelser baserat på den lokala strukturen för data.

Avståndsmått som används i KNN-algoritmen

Som vi vet hjälper KNN-algoritmen oss att identifiera de närmaste punkterna eller grupperna för en frågepunkt. Men för att bestämma de närmaste grupperna eller de närmaste punkterna för en frågepunkt behöver vi något mått. För detta ändamål använder vi nedanstående avståndsmått:

Euklidiskt avstånd

Detta är inget annat än det kartesiska avståndet mellan de två punkterna som är i planet/hyperplanet. Euklidiskt avstånd kan också visualiseras som längden på den raka linjen som förenar de två punkter som är i beaktande. Detta mått hjälper oss att beräkna nettoförskjutningen mellan de två tillstånden för ett objekt.

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

Manhattan avstånd

Manhattan avstånd metrisk används vanligtvis när vi är intresserade av den totala sträckan som objektet tillryggalagt istället för förskjutningen. Detta mått beräknas genom att summera den absoluta skillnaden mellan punkternas koordinater i n-dimensioner.

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

Minkowski Avstånd

Vi kan säga att det euklidiska, såväl som avståndet från Manhattan, är specialfall av Minkowski avstånd .

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

Från formeln ovan kan vi säga att när p = 2 så är det samma som formeln för det euklidiska avståndet och när p = 1 får vi formeln för Manhattanavståndet.

De ovan diskuterade måtten är vanligast när man hanterar en Maskininlärning problem men det finns även andra avståndsmått som Hamming Distans som kommer väl till pass när man hanterar problem som kräver överlappande jämförelser mellan två vektorer vars innehåll kan vara såväl booleska som strängvärden.

Hur väljer man värdet på k för KNN Algorithm?

Värdet på k är mycket avgörande i KNN-algoritmen för att definiera antalet grannar i algoritmen. Värdet på k i algoritmen för k-närmaste grannar (k-NN) bör väljas baserat på indata. Om indata har fler extremvärden eller brus, skulle ett högre värde på k vara bättre. Det rekommenderas att välja ett udda värde för k för att undvika olikheter i klassificeringen. Korsvalidering metoder kan hjälpa till att välja det bästa k-värdet för den givna datamängden.

Funktioner av KNN-algoritmen

Algoritmen K-Nearest Neighbors (KNN) arbetar på principen om likhet, där den förutsäger etiketten eller värdet för en ny datapunkt genom att beakta etiketterna eller värdena för dess K närmaste grannar i träningsdatauppsättningen.

Funktioner av KNN-algoritmen

Steg-för-steg förklaring av hur KNN fungerar diskuteras nedan:

Steg 1: Välj det optimala värdet för K

  • K representerar antalet närmaste grannar som måste beaktas när man gör förutsägelser.

Steg 2: Beräkna avstånd

  • För att mäta likheten mellan mål- och träningsdatapunkter används euklidiskt avstånd. Avståndet beräknas mellan var och en av datapunkterna i datamängden och målpunkten.

Steg 3: Hitta närmaste grannar

  • De k datapunkterna med de minsta avstånden till målpunkten är de närmaste grannarna.

Steg 4: Rösta för klassificering eller ta medelvärde för regression

  • I klassificeringsproblemet bestäms klassmärkningarna av genom majoritetsomröstning. Klassen med flest förekomster bland grannarna blir den förutsagda klassen för måldatapunkten.
  • I regressionsproblemet beräknas klassetiketten genom att ta medelvärdet av målvärdena för K närmaste grannar. Det beräknade medelvärdet blir den förutsagda utsignalen för måldatapunkten.

Låt X vara träningsdatauppsättningen med n datapunkter, där varje datapunkt representeras av en d-dimensionell funktionsvektor X_ioch Y är motsvarande etiketter eller värden för varje datapunkt i X. Givet en ny datapunkt x beräknar algoritmen avståndet mellan x och varje datapunkt X_ii X med hjälp av ett avståndsmått, som euklidiskt avstånd: ext{avstånd}(x, X_i) = sqrt{sum_{j=1}^{d} (x_j - X_{i_j})^2} ]

Algoritmen väljer de K datapunkter från X som har kortast avstånd till x. För klassificeringsuppgifter tilldelar algoritmen den etikett y som är vanligast bland de K närmaste grannarna till x. För regressionsuppgifter beräknar algoritmen medelvärdet eller det viktade medelvärdet av värdena y för de K närmaste grannarna och tilldelar det som det förutsagda värdet för x.

Fördelar med KNN-algoritmen

  • Lätt att implementera eftersom komplexiteten i algoritmen inte är så hög.
  • Anpassar sig lätt – Enligt hur KNN-algoritmen fungerar lagrar den all data i minneslagring, och när ett nytt exempel eller datapunkt läggs till så justerar algoritmen sig själv enligt det nya exemplet och har också sitt bidrag till framtida förutsägelser.
  • Få hyperparametrar – De enda parametrarna som krävs i träningen av en KNN-algoritm är värdet på k och valet av avståndsmåttet som vi skulle vilja välja från vårt utvärderingsmått.

Nackdelar med KNN-algoritmen

  • Skalar inte – Som vi har hört talas om detta att KNN-algoritmen också anses vara en Lazy-algoritm. Den huvudsakliga betydelsen av denna term är att detta kräver mycket datorkraft samt datalagring. Detta gör denna algoritm både tidskrävande och resursutmattande.
  • Dimensionalitetens förbannelse – Det finns en term som kallas peaking-fenomenet enligt detta påverkas KNN-algoritmen av dimensionalitetens förbannelse vilket innebär att algoritmen har svårt att klassificera datapunkterna ordentligt när dimensionaliteten är för hög.
  • Benägen att överanpassa – Eftersom algoritmen påverkas på grund av dimensionalitetens förbannelse är den också utsatt för problemet med överanpassning. Därför generellt funktionsval såväl som dimensionsreduktion tekniker används för att hantera detta problem.

Exempel på program:

Antag 0 och 1 som de två klassificerarna (grupperna).

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); } // Drivrutinskod int main() { int n = 17; // Antal datapunkter Punkt 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 för att bestämma grupp av testpunkten int k = 3; printf ('Värdet klassificerat till okänd punkt' ' är %d. ', classifyAPoint(arr, n, k, p)); returnera 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.distans) retur 1; returnera 0; } } // Denna funktion hittar klassificering av punkt p med // k närmaste granne algoritm. Den antar endast två //-grupper och returnerar 0 om p tillhör grupp 0, annars // 1 (tillhör grupp 1). statisk int klassificeraAPoint(Punkt arr[], int n, int k, Punkt p) { // Fyll avstånden för alla punkter från p för (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) // Sortera punkterna efter avstånd från p Arrays.sort(arr, new comparison()); // Betrakta nu de första k elementen och endast // två grupper int freq1 = 0; (int i = 0; i if (arr[i].val == 0) freq1++; annars if (arr[i].val == 1) freq2++; } return (freq1> freq2 ? 0 : 1); } / / Driver code public static void main(String[] args) { int n = 17; // Antal datapunkter Point[] arr = new Point[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*/ 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; // Antal datapunkter 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 = 5; arr[2].x = 5; arr[3].x = 3; arr[3].y = 1; arr[4].y = 6; val = 0; arr[5].x = 1.5; arr[5].val = 1; arr[6] [6].val = 1; arr[7].x = 6; arr[7].val = 1, arr[8] = 3; arr[8].val = 1; arr[9].y = 10; 10].y = 4; arr[10].val = 1; arr[11].y = 2; 3,5; arr[12] .y = 8; arr[13] ].x = 2; arr[14].y = 5; arr[15].x = 2; arr[15].val = 0; arr[16].x = 1; arr[16].val = 0; // Parameter för att bestämma grupp av testpunkten int k = 3; Console.WriteLine('Värdet klassificerat till okänd punkt är ' + classifyAPoint(arr, n, k, p)); } } // Koden är bidragit av 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) { retur 1; } returnera 0; } } // Denna funktion hittar klassificering av punkt p med // k närmaste granne algoritm. Den antar endast två //-grupper och returnerar 0 om p tillhör grupp 0, annars // 1 (tillhör grupp 1). function classifyAPoint(arr, n, k, p) { // Fyll avstånden för alla punkter från p för (låt 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) } // Sortera poängen efter avstånd från p arr.sort(new Comparison()); // Betrakta nu de första k elementen och bara två grupper låt freq1 = 0; // Frekvens för grupp 0 låt freq2 = 0; [i].val === 0) { freq1++ } else if (arr[i].val === } } return freq1> freq2 } // Driver code const n = 17; // Antal datapunkter const arr = new Array(n) för (låt 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.distans) retur 1; returnera 0; }); // Betrakta nu de första k elementen och endast två grupper låter freq1 = 0; // Frekvens för grupp 0 låt freq2 = 0; // Frekvens för grupp 1 för (låt i = 0; i if (arr[i].val == 0) freq1++; annars if (arr[i].val == 1) freq2++; } returnera freq1> freq2 ? 0 : 1; }>
>
>

Produktion: 

The value classified as an unknown point is 0.>

Tidskomplexitet: O(N * logN)
Hjälputrymme: O(1)

Tillämpningar av KNN-algoritmen

  • Dataförbehandling – När vi hanterar maskininlärningsproblem utför vi först KNN Impute som är ganska effektiv annons som vanligtvis används för sofistikerade imputeringsmetoder.
  • Mönsterigenkänning – KNN-algoritmer fungerar väldigt bra om du har tränat en KNN-algoritm med hjälp av MNIST-dataset och sedan utfört utvärderingsprocessen då måste du ha stött på att noggrannheten är för hög.
  • Rekommendation Motorer – Huvuduppgiften som utförs av en KNN-algoritm är att tilldela en ny frågepunkt till en redan existerande grupp som har skapats med hjälp av en enorm mängd datauppsättningar. Detta är precis vad som krävs i K Närmaste grannar med Python | ML
  • Implementering av K-Nearest Neighbors från grunden med Python
  • Matematisk förklaring av K-Närmaste Granne
  • Viktad K-NN

Vanliga frågor (FAQs)

F. Varför KNN är lat lärande?

KNN-algoritmen bygger ingen modell under träningsfasen. Algoritmen minns hela träningsdatasetet och utför åtgärder på datasetet vid tidpunkten för klassificeringen.

np prick

F. Varför är KNN icke-parametrisk?

KNN-algoritmen gör inga antaganden om data den analyserar.

F. Vad är skillnaden mellan KNN och K betyder?

  • KNN är en övervakad maskininlärningsmodell som används för klassificeringsproblem medan K-means är en oövervakad maskininlärningsmodell som används för klustring.
  • K i KNN är antalet närmaste grannar medan K i K betyder antalet kluster.