Hva er en KNN (K-Nærmeste Naboer)?

Hva er K-Nearest Neighbors (KNN)?

K-Nearest Neighbors er en maskinlæringsteknikk og algoritme som kan brukes til både regresjons- og klassifiseringsoppgaver. K-nærmeste naboer undersøker etikettene til et valgt antall datapunkter som omgir et måldatapunkt, for å lage en prediksjon om klassen som datapunktet faller inn i. K-Nearest Neighbors (KNN) er en konseptuelt enkel, men veldig kraftig algoritme, og av disse grunnene er den en av de mest populære maskinlæringsalgoritmene. La oss ta et dypdykk i KNN-algoritmen og se nøyaktig hvordan den fungerer. Å ha en god forståelse av hvordan KNN opererer vil la deg sette pris på de beste og verste brukssakene for KNN.

Oversikt over K-Nærmeste Naboer (KNN)

Foto: Antti Ajanki AnAj via Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

La oss visualisere et datasett på et 2D-plan. Se for deg en haug med datapunkter på en graf, spredt utover grafen i små klynger. KNN undersøker fordelingen av datapunktene og, avhengig av argumentene som gis til modellen, deler den datapunktene inn i grupper. Disse gruppene blir deretter tildelt en etikett. Den primære antagelsen som en KNN-modell gjør, er at datapunkter/forekomster som eksisterer i umiddelbar nærhet av hverandre er svært like, mens hvis et datapunkt er langt unna en annen gruppe, er det ulikt disse datapunktene.

En KNN-modell beregner likhet ved å bruke avstanden mellom to punkter på en graf. Jo større avstanden er mellom punktene, jo mindre like er de. Det er flere måter å beregne avstanden mellom punkter på, men den vanligste avstandsmetrikken er bare euklidisk avstand (avstanden mellom to punkter i en rett linje).

KNN er en overvåket læringsalgoritme, noe som betyr at eksemplene i datasettet må ha etiketter tildelt dem/klassene deres må være kjent. Det er to andre viktige ting å vite om KNN. For det første er KNN en ikke-parametrisk algoritme. Dette betyr at det ikke gjøres noen forutsetninger om datasettet når modellen brukes. Snarere er modellen konstruert utelukkende fra de oppgitte dataene. For det andre er det ingen oppdeling av datasettet i trenings- og testsett ved bruk av KNN. KNN gjør ingen generaliseringer mellom et trenings- og testsett, så alle treningsdataene brukes også når modellen blir bedt om å gjøre spådommer.

Hvordan en KNN-algoritme fungerer

En KNN-algoritme går gjennom tre hovedfaser når den utføres:

1. Innstilling K til det valgte antall naboer.
2. Beregner avstanden mellom et gitt/testeksempel og datasetteksemplene.
3. Sortering av de beregnede avstandene.
4. Få etikettene til de beste K-oppføringene.
5. Returnerer en prediksjon om testeksemplet.

I det første trinnet velges K av brukeren, og den forteller algoritmen hvor mange naboer (hvor mange omkringliggende datapunkter) som skal tas i betraktning når man avgir en dom om gruppen måleksemplet tilhører. I det andre trinnet, merk at modellen sjekker avstanden mellom måleksemplet og hvert eksempel i datasettet. Avstandene legges deretter inn i en liste og sorteres. Etterpå blir den sorterte listen sjekket og etikettene for de øverste K-elementene returneres. Med andre ord, hvis K er satt til 5, sjekker modellen etikettene til de 5 nærmeste datapunktene til måldatapunktet. Når du gjengir en prediksjon om måldatapunktet, er det viktig om oppgaven er en regresjon or klassifisering oppgave. For en regresjonsoppgave brukes gjennomsnittet av de øverste K-etikettene, mens modusen til de øverste K-etikettene brukes ved klassifisering.

De nøyaktige matematiske operasjonene som brukes til å utføre KNN varierer avhengig av den valgte avstandsmetrikken. Hvis du vil lære mer om hvordan beregningene beregnes, kan du lese om noen av de vanligste avstandsmålene, som f.eks. euklidsk, Manhattanog Minkowski.

Hvorfor verdien av K er viktig

Hovedbegrensningen ved bruk av KNN er at en uriktig verdi på K (feil antall naboer som skal vurderes) kan velges. Hvis dette skjer, kan spådommene som returneres, være vesentlig avslått. Det er veldig viktig at når du bruker en KNN-algoritme, velges riktig verdi for K. Du vil velge en verdi for K som maksimerer modellens evne til å lage spådommer på usynlige data samtidig som den reduserer antall feil.

Foto: Agor153 via Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Lavere verdier av K betyr at spådommene gitt av KNN er mindre stabile og pålitelige. For å få en intuisjon om hvorfor det er slik, vurder et tilfelle der vi har 7 naboer rundt et måldatapunkt. La oss anta at KNN-modellen jobber med en K-verdi på 2 (vi ber den om å se på de to nærmeste naboene for å gi en prediksjon). Hvis det store flertallet av naboene (fem av syv) tilhører den blå klassen, men de to nærmeste naboene tilfeldigvis er røde, vil modellen forutsi at spørringseksemplet er rødt. Til tross for modellens gjetning, i et slikt scenario ville blå være en bedre gjetning.

Hvis dette er tilfelle, hvorfor ikke bare velge den høyeste K-verdien vi kan? Dette er fordi å fortelle modellen om å vurdere for mange naboer også vil redusere nøyaktigheten. Ettersom radiusen som KNN-modellen vurderer øker, vil den etter hvert begynne å vurdere datapunkter som er nærmere andre grupper enn de er måldatapunktet, og feilklassifisering vil begynne å forekomme. For eksempel, selv om punktet som først ble valgt var i et av de røde områdene ovenfor, hvis K ble satt for høyt, ville modellen nå inn i de andre områdene for å vurdere punkter. Ved bruk av en KNN-modell forsøkes ulike verdier av K for å se hvilken verdi som gir modellen best ytelse.

KNN fordeler og ulemper

La oss undersøke noen av fordelene og ulempene med KNN-modellen.

Pros:

KNN kan brukes til både regresjons- og klassifiseringsoppgaver, i motsetning til noen andre veiledede læringsalgoritmer.

KNN er svært nøyaktig og enkel å bruke. Det er enkelt å tolke, forstå og implementere.

KNN gjør ingen antagelser om dataene, noe som betyr at de kan brukes til en rekke problemer.

Cons:

KNN lagrer de fleste eller alle dataene, noe som betyr at modellen krever mye minne og at den er beregningsmessig dyr. Store datasett kan også føre til at spådommer tar lang tid.

KNN viser seg å være veldig følsom for skalaen til datasettet, og det kan ganske enkelt bli kastet ut av irrelevante funksjoner sammenlignet med andre modeller.

Sammendrag av K-Nærmeste Naboer (KNN)

K-Nearest Neighbors er en av de enkleste maskinlæringsalgoritmene. Til tross for hvor enkelt KNN er i konseptet, er det også en kraftig algoritme som gir ganske høy nøyaktighet på de fleste problemer. Når du bruker KNN, sørg for å eksperimentere med ulike verdier av K for å finne tallet som gir høyest nøyaktighet.