KNN uitleg

excel machinelearning

Uitleg van de Machine Learning methode KNN aan de hand van een paar kleine voorbeelden in Excel.

Ben Welman
2022-04-04

Machine Learning is een concept waarbij via een algoritme geprobeerd wordt om patronen in gegevens te ontdekken. Een van de eenvoudigste algoritmes is KNN, wat staat voor k-Nearest-Neighbor, oftewel de \(k\) dichstbijzijnde buren. Wanneer je het voor classificatie gebruikt, dan wordt een nieuw gegevenspunt in een doelgroep (klasse) ondergebracht op basis van de kenmerken van de \(k\) dichtstbijgelegen gegevenspunten.

Nu is Excel niet echt geschikt om Machine Learning technieken toe te passen. Wel kun je het principe van sommige technieken, zoals KNN, goed met behulp van Excel uitleggen.

Voorbeeld met 1 kenmerk

Stel je hebt een groep van 8 personen, 4 mannen en 4 vrouwen, waarvan de lengte (cm) bekend is. Bij deze groep komt nu een nieuwe persoon waarvan je alleen de lengte weet, 176 cm. Kun je dan hiermee voorspellen of het een man of een vrouw is?

Lengte van de personen.

Figure 1: Lengte van de personen.

Voor een vergelijking zijn in figuur 2 de lengtes van alle personen op een denkbeeldige meetlat afgebeeld.

Afbeelding van de lengte van de personen op een denkbeeldige meetlat.

Figure 2: Afbeelding van de lengte van de personen op een denkbeeldige meetlat.

Het KNN algoritme berekent nu de afstanden van de nieuwe persoon tot alle gecategoriseerde personen, waarvan het geslacht dus bekend is. Onder afstand wordt hier dan het verschil in lengte verstaan. Deze afstanden zijn te zien in figuur 1.

Vervolgens worden deze afstanden gerangschikt van de dichtstbijzijnde (meest vergelijkbare) tot de verste (de minst vergelijkbare).

De waarde voor \(k\) in het algoritme staat voor het aantal buren waarmee je gaat vergelijken. Elk van deze \(k\) buren brengt als het ware een stem uit voor de desbetreffende categorie. De conclusie of de nieuwe persoon een man of een vrouw is wordt dan getrokken op basis van de meeste stemmen.

Voorbeeld met 2 kenmerken

Nu is van de 4 mannen en 4 vrouwen naast de lengte (cm) ook het gewicht (kg) bekend. En het gewicht van de nieuwe persoon is 68 kg.

Lengte en gewicht van de personen.

Figure 3: Lengte en gewicht van de personen.

In figuur 4 is een spreidingsdiagram van gewicht tegen lengte te zien.

Spreidingsdiagram van lengte en gewicht van de personen.

Figure 4: Spreidingsdiagram van lengte en gewicht van de personen.

Ook nu wordt weer de afstand bepaald van de nieuwe persoon tot de andere personen. Bij twee variabelen wordt de Euclidische afstand bepaald. Voor twee punten \((x_1,y_1\) en \((x_2,y_2\) kun je deze via Pythagoras uitrekenen:

\[\text{afstand } = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\]

In figuur 3 is de berekende afstand te zien. Daarna wordt weer gekeken welke de dichtstbijzijnde buren zijn.

Voorbeeld met 2 gestandaardiseerde kenmerken

Verschillende variabelen hebben verschillende schaaleenheden, zoals hier de lengte in cm en het gewicht in kg. Dat kan er voor zorgen dat variabelen die op een grotere schaal gemeten worden een groter aandeel hebben in de berekende afstand en daardoor belangrijker worden gemaakt dan variabelen die op een kleinere schaal gemeten worden. Om dit te voorkomen kun je de gegevens transformeren naar een nieuwe schaal. Een veel gebruikte techniek hiervoor is de min-max normalisatie waarbij de gegevens geschaald worden naar het bereik [0,1]. Hiervoor wordt de kleinste en de grootste waarde van de gegevens bepaald. Vervolgens worden de gegevens gewijzigd via

\(\text{genormaliseerde waarde } = \frac{x - min(x)}{max(x) - min(x)}\)

In figuur 5 zijn de variabelen lengte en gewicht genormaliseerd en is de afstand voor de genormaliseerde gegevens berekend. En in figuur 6 zie je de bijpassende grafiek.

Lengte en gewicht van de personen.

Figure 5: Lengte en gewicht van de personen.

Spreidingsdiagram van lengte en gewicht van de personen.

Figure 6: Spreidingsdiagram van lengte en gewicht van de personen.

Wanneer nu naar de dichtstbijzijnde buren gekeken wordt zijn de resultaten iets anders.

Meer dan 2 kenmerken

Voor meer attributen, bijvoorbeeld hier uitgebreid met de taillemaat, is het principe is hetzelfde. Je kunt het wat moeilijker tekenen en ook het berekenen van de adstand is wat meer werk.

\[\text{afstand} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2 + ... }\]

kNN in de praktijk

In de praktijk heb je met grotere datasets te maken. Om de beste waarde voor \(k\) te vinden wordt de dataset gesplitst in een groter deel van zo’n 70%-80% van de gegevens om het model te trainen en een resterend kleiner deel om het model te testen. Het trainen en testen gebeurt voor verschillende waarden van \(k\). Die waarde van \(k\) welke de kleinste voorspelfout geeft wordt dan als beste waarde voor het model gebruikt.

Dit alles is met Excel niet te doen. Daartoe lenen R en Python zich veel beter. Voor beide zijn veel artikelen en tutorials met voorbeelden te vinden.