Hva er K-Nearest Neighbors (KNN)?

Hva er K-Nearest Neighbors (KNN)?

K-Nearest Neighbors er en maskinlærings-teknikk og algoritme som kan brukes for både regresjon og klassifisering . K-Nearest Neighbors undersøker etikettene 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 meget kraftig algoritme, og derfor er det en av de mest populære maskinlærings-algoritmene. 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 dårligste bruksområdene 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å kluster. KNN undersøker fordelt på datapunktene og, avhengig av argumentene gitt til modellen, skiller datapunktene inn i grupper. Disse gruppene blir deretter tildelt en etikett. Den primære antakelsen 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 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-målet 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 etiketter tilknyttet dem/deres klasser må være kjent. Det er 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 det tilgjengelige data. For det andre, er det ingen splitting av datasett inn i trenings- og testsett når KNN brukes. KNN gjør ingen generaliseringer mellom et trenings- og testsett, så all treningsdata brukes også når modellen skal 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 antall naboer.
2. Beregne avstanden mellom et gitt/test-eksempel og datasett-eksemplene.
3. Sorter de beregnede avstandene.
4. Hent etikettene på de øverste K-innlegg.
5. Returner en prediksjon om test-eksemplet.

I den første fasen, velges K av brukeren og forteller algoritmen hvor mange naboer (hvor mange omgivende datapunkter) som skal vurderes når det gjelder å avgjøre hvilken gruppe målpunktet tilhører. I den andre fasen, merker man at modellen sjekker avstanden mellom målepunktet og hvert eksempel i datasett. Avstandene legges deretter til en liste og sorteres. Deretter sjekkes den sorterte listen og etikettene for de øverste K-elementene returneres. Med andre ord, hvis K er satt til 5, sjekker modellen etikettene på de 5 nærmeste datapunktene til målepunktet. Når det gjelder å rendre en prediksjon om målepunktet, har det betydning om oppgaven er en regresjon eller klassifisering-oppgave. For en regresjonsoppgave, brukes gjennomsnittet av de øverste K-etikettene, mens modus av de øverste K-etikettene brukes i klassifiseringstilfeller.

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

Hvorfor verdien av K betyr noe

Den viktigste begrensningen ved å bruke KNN, er at en ugyldig verdi for K (feil antall naboer som skal vurderes) kan velges. 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 velges. Du ønsker å velge en verdi for K som maksimerer modellens evne til å gjøre prediksjoner på usette data, samtidig som feilene den gjør, reduseres.

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 KNN gir, er mindre stabile og pålitelige. For å få en forståelse av hvorfor dette er så, kan man tenke på et tilfelle der 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 Blå-klassen, men de to nærmeste naboene tilfeldigvis er Røde, vil modellen predikere at målepunktet er Rødt. Til tross for modellens gjetning, ville Blå være en bedre gjetning i en slik situasjon.

Hvis dette er tilfelle, hvorfor ikke bare velge den høyeste K-verdien vi kan? Dette er fordi å fortelle modellen å 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 målepunktet, og feilklassifisering vil begynne å skje. For eksempel, selv om punktet som 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 du bruker en KNN-modell, 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 ulemperne med KNN-modellen.

Fordeler:

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

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

KNN gjør ingen antakelser om data, hvilket betyr at det kan brukes for en rekke problemer.

Ulemper:

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

KNN viser seg å være svært følsom for skalaen på datasett og kan lett bli feilledet av irrelevante egenskaper i forhold til andre modeller.

Oppsummering av K-Nearest Neighbors (KNN)

K-Nearest Neighbors er en av de enkleste maskinlærings-algoritmene. Til tross for hvor enkelt KNN er i konsept, er det også en 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 nummeret som gir den høyeste nøyaktigheten.