Hva er KNN (K-Nearest Neighbors)?

Hva er K-Nearest Neighbors (KNN)?

K-Nearest Neighbors er en maskinlærings-teknikk og algoritme som kan brukes både for regresjon og klassifisering . K-Nearest Neighbors undersøker labelene på et valgt antall datapunkter rundt et målpunkt, for å gjøre en prediksjon om klassen datapunktet tilhører. K-Nearest Neighbors (KNN) er et konseptuelt enkelt, men svært kraftig algoritme, og av den grunn er det en av de mest populære maskinlærings-algoritmer. La oss dykke dypt inn i KNN-algoritmen og se hvordan den fungerer. Å ha en god forståelse av hvordan KNN opererer, vil la deg verdsette de beste og verst brukstilfellene for KNN.

Oversikt over K-Nearest Neighbors (KNN)

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

La oss visualisere en dataset på en 2D-plane. Forestill deg en mengde datapunkter på en graf, spredt ut langs grafen i små klaser. KNN undersøker distribusjonen av datapunktene og, avhengig av argumentene gitt til modellen, skiller datapunktene inn i grupper. Disse gruppene blir deretter tildelt en label. Den primære antakelsen som en KNN-modell gjør, er at datapunkter/eksempler som eksisterer i nærheten 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 hjelp av avstanden mellom to punkter på en graf. Jo større avstanden mellom punktene, jo mindre like er de. Det finnes flere måter å beregne avstanden mellom punkter, men den vanligste avstands-metrikken er bare euklidisk avstand (avstanden mellom to punkter i en rett linje).

KNN er en overvåket lærings-algoritme, hvilket betyr at eksemplene i datasett må ha labeler tildelt dem/deres klasser må være kjent. Det finnes to andre viktige ting å vite om KNN. Først er KNN en ikke-parametrisk algoritme. Dette betyr at ingen antakelser om datasett gjøres når modellen brukes. I stedet er modellen konstruert helt fra den tilgjengelige dataen. For det andre, er det ingen splitting av datasett i trening- og testsett når KNN brukes. KNN gjør ingen generaliseringer mellom et trening- og testsett, så all treningdata brukes når modellen blir bedt om å gjøre prediksjoner.

Hvordan en KNN-algoritme opererer

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

1. Sett K til det valgte antallet naboer.
2. Beregne avstanden mellom et gitt/test-eksempel og datasett-eksemplene.
3. Sorter de beregnede avstandene.
4. Hent labelene til de øverste K-innlegg.
5. Returner en prediksjon om test-eksemplet.

I den første fasen, velges K av brukeren og det forteller algoritmen hvor mange naboer (hvor mange omgivende datapunkter) som skal vurderes når en dom blir rendt om gruppen målpunktet tilhører. I den andre fasen, merk at modellen sjekker avstanden mellom målpunktet og hvert eksempel i datasett. Avstandene blir deretter lagt til i en liste og sortert. Deretter sjekkes den sorterte listen og labelene for de øverste K-elementene returneres. Med andre ord, hvis K er satt til 5, sjekker modellen labelene til de 5 nærmeste datapunktene til målpunktet. Når en prediksjon om målpunktet blir rendt, har det betydning hvis oppgaven er en regresjon eller klassifisering-oppgave. For en regresjonsoppgave, brukes gjennomsnittet av de øverste K-labelene, mens modusen av de øverste K-labelene brukes i tilfelle klassifisering.

De eksakte matematiske operasjonene som brukes til å utføre KNN, varierer avhengig av den valgte avstands-metrikken. Hvis du ønsker å lære mer om hvordan metrikker beregnes, kan du lese om noen av de vanligste avstands-metrikker, som euklidisk, Manhattan og Minkowski.

Hvorfor verdien av K betyr noe

Den viktigste begrensningen når KNN brukes, er at en ugyldig verdi for K (feil antall naboer som skal vurderes) kan bli valgt. Hvis dette skjer, kan prediksjonene som returneres, være ganske feil. Det er veldig viktig at, når en KNN-algoritme brukes, den riktige verdien for K blir valgt. Du ønsker å velge en verdi for K som maksimerer modellens evne til å gjøre prediksjoner på usette data, mens den reduserer antallet feil den gjør.

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

Lavere verdier for K betyr at prediksjonene som rendes av KNN, er mindre stabile og pålitelige. For å få en forståelse av hvorfor dette er så, betrakt et tilfelle hvor vi har 7 naboer rundt et målpunkt. La oss anta at KNN-modellen arbeider med en K-verdi på 2 (vi ber den om å se på de to nærmeste naboene for å gjøre en prediksjon). Hvis de fleste naboene (fem av syv) tilhører Blue-klassen, men de to nærmeste naboene tilfeldigvis er Red, vil modellen predikere at eksemplet er Red. Til tross for modellens gjetning, ville Blue være en bedre gjetning i et slikt scenario.

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 til slutt begynne å vurdere datapunkter som er nærmere andre grupper enn de er målpunktet, og feilklassifisering vil begynne å skje. For eksempel, selv om punktet som opprinnelig ble valgt, var i en av de røde regionene ovenfor, hvis K var satt for høyt, ville modellen nå inn i andre regioner for å vurdere punkter. Når en KNN-modell brukes, prøves forskjellige verdier av K for å se hvilken verdi som gir modellen den beste ytelsen.

KNN Fordeler og Ulemper

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

Fordeler:

KNN kan brukes både for regresjon og klassifisering, i motsetning til noen andre overvåkede lærings-algoritmer.

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

KNN gjør ingen antakelser om dataen, hvilket betyr at den kan brukes for en bred variasjon av problemer.

Ulemper:

KNN lagrer mest eller all dataen, hvilket betyr at modellen krever mye minne og er komputasjonskrevet. Store datasett kan også føre til at prediksjonene tar lang tid.

KNN er svært følsom for skalaen på datasett og kan lett bli avledet av irrelevante egenskaper i sammenligning med andre modeller.

Oppsummering av K-Nearest Neighbors (KNN)

K-Nearest Neighbors er en av de enkleste maskinlærings-algoritmer. Til tross for hvor enkelt KNN er i konsept, er det også en svært kraftig algoritme som gir ganske høy nøyaktighet på de fleste problemer. Når du bruker KNN, må du eksperimentere med forskjellige verdier av K for å finne verdien som gir den høyeste nøyaktigheten.