Hvad er K-Nearest Neighbors (KNN)?

Hvad er K-Nearest Neighbors (KNN)?

K-Nearest Neighbors er en maskinlærings-teknik og algoritme, der kan bruges til både regression og klassifikationsopgaver. K-Nearest Neighbors undersøger mærkerne på et valgt antal datapunkter omkring et målpunkt, for at lave en forudsigelse om den klasse, datapunktet tilhører. K-Nearest Neighbors (KNN) er et konceptuelt simpelt, men meget kraftfuldt algoritme, og derfor er det en af de mest populære maskinlæringsalgoritmer. Lad os dykke dybt ind i KNN-algoritmen og se nøjagtigt, hvordan den fungerer. At have en god forståelse af, hvordan KNN fungerer, vil give os en bedre forståelse af de bedste og værste brugsområder for KNN.

Overblik 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)

Lad os visualisere en dataset på en 2D-plan. Forestil dig en masse datapunkter på en graf, spredt ud langs grafen i små klumper. KNN undersøger fordelingen af datapunkterne og, afhængigt af de argumenter, der gives til modellen, adskiller den datapunkterne i grupper. Disse grupper tildeles derefter en mærke. Den primære antagelse, som en KNN-model gør, er, at datapunkter/eksempler, der findes i nærheden af hinanden, er meget lignende, mens hvis et datapunkt er langt væk fra en anden gruppe, er det ulignende til disse datapunkter.

En KNN-model beregner lignelse ved hjælp af afstanden mellem to punkter på en graf. Jo større afstanden mellem punkterne er, jo mindre lignende er de. Der er flere måder at beregne afstanden mellem punkter på, men den mest almindelige afstands-metode er blot den euclidiske afstand (afstanden mellem to punkter i en lige linje).

KNN er en overvåget læring-algoritme, hvilket betyder, at eksemplerne i datasettet skal have mærker tilknyttet sig/deres klasser skal være kendt. Der er to andre vigtige ting at vide om KNN. Først er KNN en ikke-parametrisk algoritme. Dette betyder, at der ikke bliver lavet nogen antagelser om datasettet, når modellen bruges. I stedet bliver modellen konstrueret helt fra den tilgængelige data. Anden, der ikke bliver lavet nogen opdeling af datasettet i trænings- og test-sæt, når KNN bruges. KNN laver ingen generaliseringer mellem et trænings- og test-sæt, så alle træningsdata bruges også, når modellen bedes om at lave forudsigelser.

Hvordan en KNN-algoritme fungerer

En KNN-algoritme går gennem tre hovedfaser, mens den udføres:

1. Indstilling af K til det valgte antal naboer.
2. Beregning af afstanden mellem et givet/test-eksempel og dataset-eksemplerne.
3. Sortering af de beregnede afstande.
4. Henting af mærkerne for de top K-indtastninger.
5. Returnering af en forudsigelse om test-eksemplet.

I den første fase vælges K af brugeren og fortæller algoritmen, hvor mange naboer (hvor mange omgivende datapunkter), der skal være med, når der laves en vurdering af, hvilken gruppe måle-eksemplet tilhører. I den anden fase bemærkes, at modellen checker afstanden mellem måle-eksemplet og hvert eksempel i datasettet. Afstandene føjes derefter til en liste og sorteres. Efterfølgende checker den sorteret liste og returnerer mærkerne for de top K-elementer. Med andre ord, hvis K er indstillet til 5, checker modellen mærkerne for de 5 nærmeste datapunkter til måle-punktet. Når der laves en forudsigelse om måle-punktet, er det vigtigt, om opgaven er en regression eller klassifikation opgave. For en regression-opgave bruges gennemsnittet af de top K-mærker, mens modus af de top K-mærker bruges i tilfælde af klassifikation.

De eksakte matematiske operationer, der bruges til at udføre KNN, afhænger af den valgte afstands-metode. Hvis du ønsker at lære mere om, hvordan metricerne beregnes, kan du læse om nogle af de mest almindelige afstands-metricer, såsom Euclidisk, Manhattan og Minkowski.

Hvorfor værdien af K betyder noget

Den primære begrænsning, når man bruger KNN, er, at en ugyldig værdi af K (forkert antal naboer at overveje) kan vælges. Hvis dette sker, kan forudsigelserne, der returneres, være afvigtende. Det er meget vigtigt, at når man bruger en KNN-algoritme, vælges den rigtige værdi for K. Du ønsker at vælge en værdi for K, der maksimerer modellens evne til at lave forudsigelser på usete data, mens fejlantal reduceres.

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

Lavere værdier af K betyder, at forudsigelserne, der returneres af KNN, er mindre stabile og pålidelige. For at få en intuition om, hvorfor det er sådan, overvej et tilfælde, hvor vi har 7 naboer omkring et måle-punkt. Lad os antage, at KNN-modellen arbejder med en K-værdi på 2 (vi beder den om at se på de to nærmeste naboer for at lave en forudsigelse). Hvis det overvældende flertal af naboerne (fem af syv) tilhører den Blå klasse, men de to nærmeste naboer tilfældigt er Rød, vil modellen forudsige, at måle-eksemplet er Rød. Trods modellens gæt er Blå dog en bedre gæt i sådant et scenarie.

Hvis dette er tilfældet, hvorfor ikke bare vælge den højeste K-værdi, vi kan? Dette er, fordi at fortælle modellen at overveje for mange naboer også vil reducere nøjagtigheden. Når radiusset, som KNN-modellen overvejer, øges, vil den til sidst begynde at overveje datapunkter, der er tættere på andre grupper end måle-punktet, og mis klassificering vil begynde at ske. For eksempel, selvom punktet, der oprindeligt blev valgt, var i en af de røde regioner ovenfor, hvis K blev sat for højt, ville modellen nå ind i andre regioner for at overveje punkter. Når man bruger en KNN-model, prøves forskellige værdier af K for at se, hvilken værdi giver modellen den bedste præstation.

KNN Fordele og Ulemper

Lad os undersøge nogle af fordelene og ulemperne ved KNN-modellen.

Fordele:

KNN kan bruges til både regression og klassifikationsopgaver, i modsætning til andre overvågede læring-algoritmer.

KNN er meget nøjagtig og simpel at bruge. Det er let at fortolke, forstå og implementere.

KNN gør ingen antagelser om data, hvilket betyder, at det kan bruges til en bred vifte af problemer.

Ulemper:

KNN gemmer det meste eller alle data, hvilket betyder, at modellen kræver meget hukommelse og er beregningskrævende. Store dataset kan også føre til, at forudsigelser tager lang tid.

KNN viser sig at være meget følsom over for skalaen af datasettet og kan let blive afledt af irrelevante funktioner i forhold til andre modeller.

Resumé af K-Nearest Neighbors (KNN)

K-Nearest Neighbors er en af de enkleste maskinlæringsalgoritmer. Trods sin enkelthed er KNN en kraftfuld algoritme, der giver en ret høj nøjagtighed på de fleste problemer. Når du bruger KNN, skal du sikre dig at eksperimentere med forskellige værdier af K for at finde det tal, der giver den højeste nøjagtighed.