Wat is K-Nearest Neighbors (KNN)?

Wat is K-Nearest Neighbors (KNN)?

K-Nearest Neighbors is een machine learning-techniek en algoritme dat zowel voor regressie- als classificatietaken gebruikt kan worden. K-Nearest Neighbors onderzoekt de labels van een gekozen aantal datapunten rondom een doeldatapunt, om een voorspelling te doen over de klasse waarin het datapunt valt. K-Nearest Neighbors (KNN) is een conceptueel eenvoudig, maar zeer krachtig algoritme, en om die reden is het een van de meest populaire machine learning-algoritmes. Laten we een diepe duik nemen in het KNN-algoritme en zien hoe het precies werkt. Een goed begrip van hoe KNN werkt, zal je helpen om de beste en slechtste gebruikscases voor KNN te waarderen.

Overzicht van K-Nearest Neighbors (KNN)

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

Laten we een dataset visualiseren op een 2D-vlak. Stel je een aantal datapunten voor op een grafiek, verspreid over de grafiek in kleine clusters. KNN onderzoekt de verdeling van de datapunten en, afhankelijk van de argumenten die aan het model zijn gegeven, splitst het de datapunten in groepen. Deze groepen worden vervolgens een label toegewezen. De primaire veronderstelling die een KNN-model maakt, is dat datapunten/instances die in de buurt van elkaar bestaan, zeer vergelijkbaar zijn, terwijl als een datapunt ver weg is van een andere groep, het ongelijk is aan die datapunten.

Een KNN-model berekent de gelijkenis met behulp van de afstand tussen twee punten op een grafiek. De grotere de afstand tussen de punten, hoe minder vergelijkbaar ze zijn. Er zijn meerdere manieren om de afstand tussen punten te berekenen, maar de meest voorkomende afstandsmaat is de Euclidische afstand (de afstand tussen twee punten in een rechte lijn).

KNN is een supervised learning-algoritme, wat betekent dat de voorbeelden in de dataset labels moeten hebben die aan hen zijn toegewezen/ hun klassen moeten bekend zijn. Er zijn twee andere belangrijke dingen om te weten over KNN. Ten eerste is KNN een niet-parametrisch algoritme. Dit betekent dat er geen veronderstellingen over de dataset worden gemaakt wanneer het model wordt gebruikt. In plaats daarvan wordt het model volledig opgebouwd uit de verstrekte gegevens. Ten tweede wordt de dataset niet gesplitst in een trainings- en testset wanneer KNN wordt gebruikt. KNN maakt geen generalisaties tussen een trainings- en testset, dus alle trainingsgegevens worden ook gebruikt wanneer het model wordt gevraagd om voorspellingen te doen.

Hoe een KNN-algoritme werkt

Een KNN-algoritme gaat door drie hoofdfasen als het wordt uitgevoerd:

1. Instellen van K op het gekozen aantal buren.
2. Berekenen van de afstand tussen een verstrekt/testvoorbeeld en de voorbeelden in de dataset.
3. Sorteren van de berekende afstanden.
4. Opvragen van de labels van de top K-entries.
5. Teruggeven van een voorspelling over het testvoorbeeld.

In de eerste stap wordt K door de gebruiker gekozen en vertelt het de algoritme hoeveel buren (hoeveel omliggende datapunten) moeten worden overwogen bij het maken van een voorspelling over de groep waartoe het doelvoorbeeld behoort. In de tweede stap wordt de afstand tussen het doelvoorbeeld en elk voorbeeld in de dataset berekend. De afstanden worden vervolgens toegevoegd aan een lijst en gesorteerd. Vervolgens wordt de gesorteerde lijst gecontroleerd en worden de labels van de top K-elementen geretourneerd. Met andere woorden, als K is ingesteld op 5, controleert het model de labels van de 5 dichtstbijzijnde datapunten bij het doelvoorbeeld. Bij het maken van een voorspelling over het doelvoorbeeld, maakt het uit of de taak een regressie of classificatietaak is. Voor een regressietaken wordt het gemiddelde van de top K-labels gebruikt, terwijl de modus van de top K-labels wordt gebruikt in het geval van classificatie.

De exacte wiskundige bewerkingen die worden gebruikt om KNN uit te voeren, verschillen afhankelijk van de gekozen afstandsmaat. Als je meer wilt leren over hoe de metrics worden berekend, kun je lezen over enkele van de meest voorkomende afstandsmaatstaven, zoals Euclidische, Manhattan en Minkowski.

Waarom de waarde van K ertoe doet

De belangrijkste beperking bij het gebruik van KNN is dat een onjuiste waarde van K (het verkeerde aantal buren om te overwegen) kan worden gekozen. Als dit gebeurt, kunnen de voorspellingen die worden geretourneerd aanzienlijk afwijken. Het is heel belangrijk dat, wanneer je een KNN-algoritme gebruikt, de juiste waarde voor K wordt gekozen. Je wilt een waarde voor K kiezen die het vermogen van het model om voorspellingen te doen op ongezien gegevens maximaliseert, terwijl het aantal fouten dat het maakt, wordt verminderd.

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

Lagere waarden van K betekenen dat de voorspellingen die door KNN worden gedaan, minder stabiel en betrouwbaar zijn. Om een idee te krijgen van waarom dit zo is, laten we een geval overwegen waarin we 7 buren rondom een doeldatapunt hebben. Laten we aannemen dat het KNN-model werkt met een K-waarde van 2 (we vragen het om naar de twee dichtstbijzijnde buren te kijken om een voorspelling te doen). Als de overgrote meerderheid van de buren (vijf van de zeven) tot de Blauwe klasse behoort, maar de twee dichtstbijzijnde buren toevallig Rood zijn, zal het model voorspellen dat het queryvoorbeeld Rood is. Ondanks de voorspelling van het model, zou Blauw in een dergelijk scenario een betere voorspelling zijn.

Als dit het geval is, waarom niet gewoon de hoogste K-waarde kiezen die we kunnen? Dit is omdat het model vertellen om te veel buren te overwegen, de nauwkeurigheid ook zal verminderen. Naarmate de straal die het KNN-model overweegt toeneemt, zal het uiteindelijk beginnen met het overwegen van datapunten die dichter bij andere groepen zijn dan bij het doeldatapunt en zal misclassificatie beginnen te gebeuren. Bijvoorbeeld, zelfs als het punt dat aanvankelijk werd gekozen in een van de rode regio’s boven was, als K te hoog was ingesteld, zou het model reiken in andere regio’s om punten te overwegen. Wanneer je een KNN-model gebruikt, worden verschillende waarden van K geprobeerd om te zien welke waarde het model de beste prestaties geeft.

Voor- en nadelen van KNN

Laten we enkele van de voor- en nadelen van het KNN-model onderzoeken.

Voordelen:

KNN kan zowel voor regressie- als classificatietaken worden gebruikt, in tegenstelling tot sommige andere supervised learning-algoritmes.

KNN is zeer nauwkeurig en eenvoudig te gebruiken. Het is gemakkelijk te interpreteren, te begrijpen en te implementeren.

KNN maakt geen veronderstellingen over de gegevens, wat betekent dat het kan worden gebruikt voor een breed scala aan problemen.

Nadelen:

KNN slaat de meeste of alle gegevens op, wat betekent dat het model veel geheugen nodig heeft en het computationeel duur is. Grote datasets kunnen ook ervoor zorgen dat voorspellingen lang duren.

KNN blijkt zeer gevoelig te zijn voor de schaal van de dataset en kan gemakkelijk worden misleid door irrelevante kenmerken in vergelijking met andere modellen.

Samenvatting van K-Nearest Neighbors (KNN)

K-Nearest Neighbors is een van de eenvoudigste machine learning-algoritmes. Ondanks hoe eenvoudig KNN is in concept, is het ook een krachtig algoritme dat redelijk hoge nauwkeurigheid geeft op de meeste problemen. Wanneer je KNN gebruikt, zorg er dan voor dat je experimenteert met verschillende waarden van K om de waarde te vinden die de hoogste nauwkeurigheid geeft.