The K-Tuvāko kaimiņu (KNN) algoritms ir uzraudzīta mašīnmācīšanās metode, ko izmanto, lai risinātu klasifikācijas un regresijas problēmas. Evelyn Fix un Joseph Hodges izstrādāja šo algoritmu 1951. gadā, ko vēlāk paplašināja Tomass Kovers. Rakstā ir apskatīti KNN algoritma pamati, darbība un ieviešana.

Kas ir K-tuvāko kaimiņu algoritms?

KNN ir viens no visvienkāršākajiem, taču būtiskākajiem klasifikācijas algoritmiem mašīnmācībā. Tas pieder pie uzraudzīta mācīšanās domēnu un atrod intensīvu pielietojumu modeļu atpazīšanā, Tas ir plaši izmantojams reālās dzīves scenārijos, jo tas nav parametrisks, kas nozīmē, ka tas neizdara nekādus pamatā esošos pieņēmumus par datu izplatīšanu (atšķirībā no citiem algoritmiem, piemēram, GMM, kas paredz Gausa sadalījums no dotajiem datiem). Mums tiek doti daži iepriekšējie dati (saukti arī par apmācības datiem), kas klasificē koordinātas grupās, kuras identificē ar atribūtu.

selēna pamati

Kā piemēru ņemiet vērā šo datu punktu tabulu, kurā ir iekļauti divi līdzekļi:

KNN algoritma darba vizualizācija

Tagad, ņemot vērā citu datu punktu kopu (ko sauc arī par testēšanas datiem), piešķiriet šos punktus grupai, analizējot apmācības kopu. Ņemiet vērā, ka neklasificētie punkti ir atzīmēti kā “balti”.

Intuīcija aiz KNN algoritma

Ja mēs attēlosim šos punktus grafikā, iespējams, varēsim atrast dažus klasterus vai grupas. Tagad, ņemot vērā neklasificētu punktu, mēs varam to piešķirt grupai, novērojot, kurai grupai pieder tuvākie kaimiņi. Tas nozīmē, ka punktam, kas atrodas tuvu punktu kopai, kas klasificēts kā “sarkans”, ir lielāka iespēja tikt klasificētam kā “sarkans”.

Intuitīvi redzams, ka pirmais punkts (2.5., 7.) jāklasificē kā “zaļš”, bet otrais punkts (5.5., 4.5.) jāklasificē kā “sarkans”.

Kāpēc mums ir nepieciešams KNN algoritms?

(K-NN) algoritms ir daudzpusīgs un plaši izmantots mašīnmācīšanās algoritms, ko galvenokārt izmanto tā vienkāršības un ieviešanas vienkāršības dēļ. Tam nav nepieciešami nekādi pieņēmumi par pamatā esošo datu sadalījumu. Tas var arī apstrādāt gan skaitliskos, gan kategoriskos datus, padarot to par elastīgu izvēli dažāda veida datu kopām klasifikācijas un regresijas uzdevumos. Tā ir neparametriska metode, kas veic prognozes, pamatojoties uz datu punktu līdzību noteiktā datu kopā. K-NN ir mazāk jutīgs pret novirzēm, salīdzinot ar citiem algoritmiem.

K-NN algoritms darbojas, atrodot K tuvākos kaimiņus noteiktam datu punktam, pamatojoties uz attāluma metriku, piemēram, Eiklīda attālumu. Pēc tam datu punkta klasi vai vērtību nosaka K kaimiņu vairākuma balsojums vai vidējais rādītājs. Šī pieeja ļauj algoritmam pielāgoties dažādiem modeļiem un veikt prognozes, pamatojoties uz datu lokālo struktūru.

KNN algoritmā izmantotā attāluma metrika

Kā zināms, KNN algoritms palīdz mums noteikt tuvākos punktus vai grupas vaicājuma punktam. Bet, lai noteiktu tuvākās grupas vai tuvākos punktus vaicājuma punktam, mums ir nepieciešama metrika. Šim nolūkam mēs izmantojam tālāk norādītos attāluma rādītājus.

Eiklīda attālums

Tas nav nekas cits kā taisnvirziena attālums starp diviem punktiem, kas atrodas plaknē/hiperplaknē. Eiklīda attālums var arī vizualizēt kā taisnas līnijas garumu, kas savieno divus vērā ņemamos punktus. Šī metrika palīdz mums aprēķināt neto nobīdi starp diviem objekta stāvokļiem.

Manhetenas attālums

Manhetenas attālums metriku parasti izmanto, ja mūs interesē kopējais objekta nobrauktais attālums, nevis pārvietošanās. Šo metriku aprēķina, summējot absolūto starpību starp punktu koordinātām n-dimensijās.

Minkovska attālums

Var teikt, ka Eiklīda, kā arī Manhetenas attālums ir īpaši gadījumi Minkovska distance .

No iepriekš minētās formulas mēs varam teikt, ka, ja p = 2, tad tā ir tāda pati kā Eiklīda attāluma formula un, ja p = 1, tad iegūstam Manhetenas attāluma formulu.

Iepriekš apspriestie rādītāji ir visizplatītākie, strādājot ar a Mašīnmācība problēma, bet ir arī citi attāluma rādītāji, piemēram Haminga attālums kas noder, risinot problēmas, kas prasa salīdzinājumus starp diviem vektoriem, kuru saturs var būt Būla, kā arī virknes vērtības.

Kā izvēlēties k vērtību KNN algoritmam?

K vērtība ir ļoti svarīga KNN algoritmā, lai definētu kaimiņu skaitu algoritmā. K vērtība k-tuvāko kaimiņu (k-NN) algoritmā jāizvēlas, pamatojoties uz ievades datiem. Ja ievades datiem ir vairāk novirzes vai trokšņu, labāka būtu lielāka k vērtība. Ieteicams izvēlēties nepāra vērtību k, lai izvairītos no sakritības klasifikācijā. Savstarpēja validācija metodes var palīdzēt izvēlēties labāko k vērtību dotajai datu kopai.

KNN algoritma darbi

K-Tuvāko kaimiņu (KNN) algoritms darbojas pēc līdzības principa, kur tas paredz jauna datu punkta etiķeti vai vērtību, ņemot vērā tā K tuvāko kaimiņu etiķetes vai vērtības apmācības datu kopā.

Soli pa solim skaidrojums par to, kā darbojas KNN, ir apspriests zemāk:

1. darbība: optimālās K vērtības izvēle

• K apzīmē tuvāko kaimiņu skaitu, kas jāņem vērā, veicot prognozes.

2. darbība: attāluma aprēķināšana

• Lai izmērītu līdzību starp mērķa un apmācības datu punktiem, tiek izmantots Eiklīda attālums. Attālums tiek aprēķināts starp katru datu punktu datu kopā un mērķa punktu.

3. darbība. Tuvāko kaimiņu atrašana

• K datu punkti ar vismazāko attālumu līdz mērķa punktam ir tuvākie kaimiņi.

4. solis: balsošana par klasifikāciju vai vidējā regresijas noteikšana

• Klasifikācijas uzdevumā klašu marķējumi tiek noteikti, veicot balsu vairākumu. Klase ar visvairāk sastopamo gadījumu starp kaimiņiem kļūst par paredzamo klasi mērķa datu punktam.
• Regresijas uzdevumā klases apzīmējumu aprēķina, ņemot vidējo no K tuvāko kaimiņu mērķa vērtībām. Aprēķinātā vidējā vērtība kļūst par paredzamo mērķa datu punkta izvadi.

Pieņemsim, ka X ir apmācības datu kopa ar n datu punktiem, kur katrs datu punkts ir attēlots ar d-dimensiju pazīmju vektoru un Y ir atbilstošās etiķetes vai vērtības katram X datu punktam. Ja ir jauns datu punkts x, algoritms aprēķina attālumu starp x un katru datu punktu. X, izmantojot attāluma metriku, piemēram, Eiklīda attālumu:

Algoritms atlasa K datu punktus no X, kuriem ir mazākais attālums līdz x. Klasifikācijas uzdevumiem algoritms piešķir apzīmējumu y, kas ir visizplatītākā starp K tuvākajiem x kaimiņiem. Regresijas uzdevumiem algoritms aprēķina vidējo vai vidējo svērto K tuvāko kaimiņu vērtību y un piešķir to kā paredzamo vērtību x.

KNN algoritma priekšrocības

• Viegli īstenojams jo algoritma sarežģītība nav tik augsta.
• Viegli pielāgojas - Saskaņā ar KNN algoritma darbību tas saglabā visus datus atmiņas krātuvē, un līdz ar to ikreiz, kad tiek pievienots jauns piemērs vai datu punkts, algoritms pielāgojas šim jaunajam piemēram, un tam ir arī savs ieguldījums nākotnes prognozēs.
• Daži hiperparametri – Vienīgie parametri, kas ir nepieciešami KNN algoritma apmācībā, ir k vērtība un attāluma metrikas izvēle, kuru mēs vēlētos izvēlēties no mūsu vērtēšanas metrikas.

KNN algoritma trūkumi

• Nesamēro – Kā esam dzirdējuši par to, KNN algoritms tiek uzskatīts arī par slinko algoritmu. Šī termina galvenā nozīme ir tā, ka tas aizņem daudz skaitļošanas jaudas, kā arī datu glabāšanas. Tas padara šo algoritmu gan laikietilpīgu, gan resursus nogurdinošu.
• Dimensijas lāsts – Ir termins, kas pazīstams kā maksimuma parādība, saskaņā ar šo KNN algoritmu ietekmē dimensijas lāsts Tas nozīmē, ka algoritmam ir grūti pareizi klasificēt datu punktus, ja dimensijas ir pārāk augstas.
• Nosliece uz pārmērīgu komplektēšanu – Tā kā algoritms ir ietekmēts dimensiju lāsta dēļ, tas ir pakļauts arī pārmērīgas pielāgošanas problēmai. Līdz ar to kopumā funkciju izvēle kā arī izmēru samazināšana Šīs problēmas risināšanai tiek izmantotas metodes.

Programmas piemērs:

Pieņemsim, ka 0 un 1 ir divi klasifikatori (grupas).

C++

>

>

Java

>

>

Python3

>

>

C#

>                      
 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.attālums) {atgriešanās 1;  } return 0;  } } // Šī funkcija atrod punkta p klasifikāciju, izmantojot // k tuvākā kaimiņa algoritmu. Tas pieņem tikai divas // grupas un atgriež 0, ja p pieder grupai 0, else // 1 (pieder 1. grupai). funkcija classifyAPoint(arr, n, k, p) { // Aizpildiet visu punktu attālumus no p for (lai 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) } // Kārtot punktus pēc attāluma no p arr.sort(new Salīdzinājums () // Tagad apsveriet pirmos k elementus un tikai divas grupas, lai frekv.1 = 0 // Grupas frekvence 2 = 0 // 1. grupas biežums (lai i = 0; i, ja (arr [i].val === 0) { freq1++ } else if (arr[i].val === 1) { freq2++ } return freq1> freq2 } // Draivera kods const n; 17 // Datu punktu skaits const arr = new Masīvs(n) (lai 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.attālums) atgriešanās 1;  atgriezties 0;  });  // Tagad apsveriet pirmos k elementus un tikai divas grupas ļaujiet freq1 = 0; // Grupas 0 frekvence let freq2 = 0; // 1. grupas biežums (lai i = 0; i if (arr[i].val == 0) freq1++; else if (arr[i].val == 1) freq2++; } return freq1> freq2 ? 0 : 1 }>
    
>
    
>
 
    Izvade:    
 
The value classified as an unknown point is 0.>
    Laika sarežģītība:    O(N * logN)  
    Palīgtelpa:    O(1)
 
KNN algoritma pielietojumi
    Datu priekšapstrāde    - Risinot jebkuru mašīnmācīšanās problēmu, mēs vispirms veicam KNN Impute kas ir diezgan efektīva reklāma, ko parasti izmanto sarežģītām imputācijas metodoloģijām.
    Rakstu atpazīšana    – KNN algoritmi darbojas ļoti labi, ja esat apmācījis KNN algoritmu, izmantojot MNIST datu kopu, un pēc tam veicis novērtēšanas procesu, tad noteikti esat saskāries ar faktu, ka precizitāte ir pārāk augsta.
    Ieteikums Dzinēji    – Galvenais uzdevums, ko veic KNN algoritms, ir piešķirt jaunu vaicājuma punktu jau esošai grupai, kas izveidota, izmantojot milzīgu datu kopu korpusu. Tas ir tieši tas, kas tiek prasīts   K Tuvākie kaimiņi ar Python | ML  
  K-Nearest Neighbors ieviešana no nulles, izmantojot Python  
  K-Tuvākā Kaimiņa matemātiskais skaidrojums  
  Svērtais K-NN  
 Bieži uzdotie jautājumi (FAQ) 
 J. Kāpēc KNN ir slinks skolēns? 
 
 KNN algoritms neveido modeli apmācības fāzē. Algoritms atceras visu apmācības datu kopu un veic darbības ar datu kopu klasifikācijas laikā. 
   
 J. Kāpēc KNN ir neparametrisks? 
 
 KNN algoritms neizdara pieņēmumus par datiem, ko tas analizē. 
jquery noklikšķinot
   
 J. Kāda ir atšķirība starp KNN un K nozīmē? 
 
 KNN ir uzraudzīts mašīnmācīšanās modelis, ko izmanto klasifikācijas problēmām, savukārt K-means ir neuzraudzīts mašīnmācīšanās modelis, ko izmanto klasterēšanai. 
 K KNN ir tuvāko kaimiņu skaits, savukārt K nozīmē K ir klasteru skaits.