UITWERKINGEN
13.2 Memory-based learning
a In het 1-nearest neighbour algoritme wordt van het betreffende voorbeeld de Euclidische afstand berekend tot alle andere voorbeelden. Vervolgens wordt het dichtsbijliggende voorbeeld geselecteerd en de klasse van dat voorbeeld wordt ook de klasse van het te classificeren voorbeeld.
De afstand van voorbeeld 1 tot voorbeeld 2 is:
De afstanden van voorbeeld 1 tot de andere 9 voorbeelden zijn gegeven in tabel 13.2.2.
Tabel 13.2.2 Afstanden van voorbeeld 1 tot de overige voorbeelden.
voorbeeld | afstand |
2 | 0,4031 |
3 | 0,3000 |
4 | 0,6021 |
5 | 0,5000 |
6 | 0,3162 |
7 | 0,2500 |
8 | 0,9000 |
9 | 0,1118 |
10 | 0,5025 |
Voorbeeld 9 heeft de kleinste afstand tot voorbeeld 1, dus wordt de klasse van
voorbeeld 9 ook de klasse van voorbeeld 1 en is dus M.
b Bij een 3-nearest neighbour algoritme wordt het drietal voorbeelden uit de
gegevensverzameling bepaald die de kleinste afstand hebben tot voorbeeld 1. Dit zijn de
voorbeelden 9, 7 en 3, die respectievelijk geclassificeerd worden met M, M en V. Het
meest-voorkomende klasselabel is M, dus wordt ook in dit geval voorbeeld 1 geclassificeerd
als M.
a Berekening van de afstand van een voorbeeld tot een ander vereist tweemaal de
berekening van een term (a - b)2. Als er 10 voorbeelden zijn, moet de
term dus 20 maal worden berekend en zijn 20t tijdseenheden nodig.
b Met 2 attributen en 100 voorbeelden izjn er 200t tijdseenheden nodig.
c Met 4 attributen en 100 voorbeelden izjn er 400t tijdseenheden nodig.