Vad är en KNN (K-Nearest Neighbors)?

Vad är K-Nearest Neighbors (KNN)?

K-Nearest Neighbors är en maskininlärningsteknik och algoritm som kan användas för både regressions- och klassificeringsuppgifter. K-närmaste grannar undersöker etiketterna för ett valt antal datapunkter kring en måldatapunkt, för att göra en förutsägelse om klassen som datapunkten faller in i. K-Nearest Neighbors (KNN) är en konceptuellt enkel men mycket kraftfull algoritm, och av dessa skäl är det en av de mest populära maskininlärningsalgoritmerna. Låt oss ta en djupdykning i KNN-algoritmen och se exakt hur den fungerar. Att ha en god förståelse för hur KNN fungerar kommer att låta dig uppskatta de bästa och sämsta användningsfallen för KNN.

Översikt över K-Nearest Neighbors (KNN)

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

Låt oss visualisera en datauppsättning på ett 2D-plan. Föreställ dig ett gäng datapunkter på en graf, utspridda längs grafen i små kluster. KNN undersöker fördelningen av datapunkterna och, beroende på de argument som ges till modellen, delar den upp datapunkterna i grupper. Dessa grupper tilldelas sedan en etikett. Det primära antagandet som en KNN-modell gör är att datapunkter/instanser som finns i närheten av varandra är mycket lika, medan om en datapunkt är långt borta från en annan grupp är den olik dessa datapunkter.

En KNN-modell beräknar likhet med avståndet mellan två punkter på en graf. Ju större avståndet är mellan punkterna, desto mindre lika är de. Det finns flera sätt att beräkna avståndet mellan punkter, men det vanligaste avståndsmåttet är bara euklidiskt avstånd (avståndet mellan två punkter i en rät linje).

KNN är en övervakad inlärningsalgoritm, vilket innebär att exemplen i datamängden måste ha etiketter tilldelade dem/deras klasser måste vara kända. Det finns två andra viktiga saker att veta om KNN. För det första är KNN en icke-parametrisk algoritm. Detta innebär att inga antaganden om datamängden görs när modellen används. Snarare är modellen helt konstruerad från den tillhandahållna data. För det andra finns det ingen uppdelning av datamängden i tränings- och testset när du använder KNN. KNN gör inga generaliseringar mellan ett tränings- och testset, så all träningsdata används också när modellen ombeds göra förutsägelser.

Hur en KNN-algoritm fungerar

En KNN-algoritm går igenom tre huvudfaser när den utförs:

1. Ställ in K till det valda antalet grannar.
2. Beräknar avståndet mellan ett tillhandahållet/testexempel och datasetexemplen.
3. Sortering av de beräknade avstånden.
4. Hämta etiketterna för de bästa K-posterna.
5. Returnerar en förutsägelse om testexemplet.

I det första steget väljs K av användaren och det talar om för algoritmen hur många grannar (hur många omgivande datapunkter) som ska beaktas när man gör en bedömning av den grupp som målexemplet tillhör. I det andra steget, notera att modellen kontrollerar avståndet mellan målexemplet och varje exempel i datamängden. Avstånden läggs sedan till i en lista och sorteras. Efteråt kontrolleras den sorterade listan och etiketterna för de översta K-elementen returneras. Med andra ord, om K är satt till 5, kontrollerar modellen etiketterna för de 5 närmaste datapunkterna till måldatapunkten. När du gör en förutsägelse om måldatapunkten spelar det roll om uppgiften är en regression or klassificering uppgift. För en regressionsuppgift används medelvärdet för de översta K-etiketterna, medan läget för de översta K-etiketterna används vid klassificering.

De exakta matematiska operationerna som används för att utföra KNN skiljer sig beroende på det valda avståndsmåttet. Om du vill lära dig mer om hur måtten beräknas kan du läsa om några av de vanligaste avståndsmåtten, som t.ex. euklidisk, Manhattanoch Minkowski.

Varför K-värdet är viktigt

Den huvudsakliga begränsningen när du använder KNN är att ett felaktigt värde på K (fel antal grannar som ska beaktas) kan väljas. Om detta händer kan de förutsägelser som returneras vara avsevärt avstängda. Det är mycket viktigt att, när du använder en KNN-algoritm, det korrekta värdet för K väljs. Du vill välja ett värde för K som maximerar modellens förmåga att göra förutsägelser på osynliga data samtidigt som antalet fel den gör.

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

Lägre värden på K betyder att de förutsägelser som KNN ger är mindre stabila och tillförlitliga. För att få en intuition om varför det är så, överväg ett fall där vi har 7 grannar runt en måldatapunkt. Låt oss anta att KNN-modellen arbetar med ett K-värde på 2 (vi ber den att titta på de två närmaste grannarna för att göra en förutsägelse). Om den stora majoriteten av grannarna (fem av sju) tillhör klassen Blå, men de två närmaste grannarna bara råkar vara Röda, kommer modellen att förutsäga att frågeexemplet är Röd. Trots modellens gissning skulle Blue i ett sådant scenario vara en bättre gissning.

Om så är fallet, varför inte bara välja det högsta K-värdet vi kan? Detta beror på att om man säger till modellen att ta hänsyn till för många grannar kommer det också att minska noggrannheten. När radien som KNN-modellen anser ökar kommer den så småningom att börja överväga datapunkter som ligger närmare andra grupper än de är måldatapunkten och felklassificering kommer att börja inträffa. Till exempel, även om den punkt som ursprungligen valdes var i en av de röda regionerna ovan, om K sattes för högt, skulle modellen nå in i de andra regionerna för att överväga punkter. När man använder en KNN-modell prövas olika värden på K för att se vilket värde som ger modellen bäst prestanda.

KNN För- och nackdelar

Låt oss undersöka några av för- och nackdelarna med KNN-modellen.

Alla tillgångar på ett och samma ställe

KNN kan användas för både regressions- och klassificeringsuppgifter, till skillnad från vissa andra övervakade inlärningsalgoritmer.

KNN är mycket exakt och enkel att använda. Det är lätt att tolka, förstå och implementera.

KNN gör inga antaganden om data, vilket innebär att den kan användas för en mängd olika problem.

Nackdelar:

KNN lagrar det mesta eller all data, vilket innebär att modellen kräver mycket minne och är beräkningsmässigt dyr. Stora datamängder kan också göra att förutsägelser tar lång tid.

KNN visar sig vara mycket känsligt för datauppsättningens skala och det kan ganska enkelt kastas bort av irrelevanta funktioner i jämförelse med andra modeller.

Sammanfattning av K-Närmaste Grannar (KNN)

K-Nearest Neighbors är en av de enklaste maskininlärningsalgoritmerna. Trots hur enkelt KNN är i konceptet är det också en kraftfull algoritm som ger ganska hög noggrannhet på de flesta problem. När du använder KNN, se till att experimentera med olika värden på K för att hitta det tal som ger den högsta noggrannheten.