- Je berekent de k dichtstbijzijnde trainingsvoorbeelden.
- Je maakt een classifier met expliciete regels voor gelijke afstanden en stemmen.
Je wilt een onbekende vrucht indelen op basis van twee metingen. In plaats van een lijn te leren, zoek je eerder gemeten vruchten die erop lijken. k-nearest neighbors (k-NN) laat de k dichtstbijzijnde trainingsvoorbeelden stemmen over het nieuwe label.
Het model bewaart voorbeelden, en het voorspellen doet het zoekwerk. Met één buur kan een enkel afwijkend punt alles bepalen; met meer buren telt een groter gebied mee. Wat “dichtbij” betekent, hangt af van de gekozen kenmerken en hun schaling.
1. Vergelijk metingen in dezelfde ruimte
Onze speelgoeddata gebruiken twee al vergelijkbaar geschaalde kenmerken. Het nieuwe punt, de query, is [1,0]. Vergelijk dat eerst met trainingspunt [0,2]: de verschillen zijn 1 en −2, de kwadraten 1 en 4, samen 5.
a en b zijn twee featurevectoren; j wijst één kenmerk aan. Het somteken telt over alle kenmerken. We gebruiken de gekwadrateerde Euclidische afstand: de wortel is voor de rangorde niet nodig, omdat grotere niet-negatieve kwadraten ook grotere wortels hebben.
def afstand2(a, b):
if len(a) != len(b):
raise ValueError("Ongelijke vormen")
totaal = 0
for j in range(len(a)):
verschil = a[j] - b[j]
totaal = totaal + verschil ** 2
return totaal
print(afstand2([1, 0], [0, 2])) # 5
Maak deze functie voor kleine eindige metingen. Verschillende lengtes geven ValueError; twee lege vectoren hebben volgens deze som afstand nul. Veelgemaakte fout: ruwe centimeters en millimeters mengen; pas een eerder op training geleerde schaal ook op de query toe.
012. Selecteer punten met een duidelijke gelijkspelregel
We bewaren vier voorbeelden. De index is hun plaats in de oorspronkelijke trainingslijst; label 0 en 1 zijn twee vruchtsoorten, geen kwaliteitscijfers. Voor onze query [1,0] krijg je:
| Index | Punt | Afstand² | Label |
|---|---|---|---|
| 0 | [0,0] | 1 | 0 |
| 1 | [2,0] | 1 | 1 |
| 2 | [0,2] | 5 | 1 |
| 3 | [3,3] | 13 | 0 |
De eerste twee punten liggen even ver weg. Spreek af dat de kleinste oorspronkelijke index dan voorgaat. Met k = 1 kies je index 0; met k = 3 de indices [0,1,2].
train = [[0, 0], [2, 0], [0, 2], [3, 3]]
labels = [0, 1, 1, 0]
query = [1, 0]
paren = []
for i in range(len(train)):
afstand = afstand2(train[i], query)
paren.append((afstand, i))
paren = sorted(paren)
gekozen = []
for j in range(3):
gekozen.append(paren[j][1])
print(gekozen) # [0, 1, 2]
Een paar (afstand,index) is een tuple. sorted vergelijkt eerst de eerste waarde en bij gelijkheid de tweede; paren[j][1] haalt daarna de index uit het j-de paar. Daardoor sorteer je de afgeleide paren en blijft de trainingslijst intact.
Maak naaste_indices(train,query,k) met deze aanpak voor een geheel aantal buren. Weiger k kleiner dan 1 of groter dan het aantal trainingsrijen, en niet-gehele k, met ValueError. afstand2 bewaakt de afmetingen van iedere trainingsrij tegenover de query.
Het diagram gebruikt een andere vaste puntenwolk. Zet query x en y op 0 en k op 1: het dichtstbijzijnde punt [1,1] heeft label 1. Voorspel daarna de uitkomst voor k = 3: [−1,−2] en [2,−1] komen erbij, dus tweemaal klasse 1 en eenmaal klasse 0.
Groene cirkels: klasse 0. Oranje vierkanten: klasse 1. Beide features gebruiken dezelfde schaal. Lijnen verbinden de geselecteerde buren.
De cirkel reikt tot de verste gekozen buur. Andere punten op die rand kunnen door de indexregel buiten de selectie vallen. Niet de cirkelrand, maar de daadwerkelijk verbonden punten bepalen de stemmen.
3. Tel stemmen zonder labels te middelen
Terug bij onze tabel: de drie gekozen labels zijn [0,1,1]. Klasse 1 krijgt twee stemmen en wint. Met k = 2 is het 1 tegen 1; onze tweede gelijkspelregel kiest dan het kleinste label, dus 0.
counts = {}
for j in range(len(gekozen)):
label = labels[gekozen[j]]
if label not in counts:
counts[label] = 0
counts[label] = counts[label] + 1
volgorde = sorted(counts)
winnaar = volgorde[0]
for j in range(len(volgorde)):
label = volgorde[j]
if counts[label] > counts[winnaar]:
winnaar = label
print(counts, winnaar) # {0: 1, 1: 2} 1
De dictionary bewaart een teller per label. sorted(counts) sorteert de labels; alleen een strikt groter aantal vervangt de winnaar, zodat een gelijkspel het kleinste label houdt. Gebruik integerlabels: ook bijvoorbeeld 2 en 3 mogen voorkomen.
Maak knn_voorspel(train,labels,query,k) en hergebruik je buurselectie. Ongelijke aantallen rijen en labels geven ValueError. Een oneven k voorkomt niet ieder gelijkspel: bij drie verschillende klassen kan k = 3 drie losse stemmen opleveren.
Wat neem je mee?
- Afstand hangt af van kenmerken en schaal; irrelevante kenmerken kunnen de selectie verstoren.
- Afstandsgelijkheid en gelijke stemmen hebben elk hun eigen expliciete regel.
- Kies k met validatiedata en meet het definitieve model daarna pas op testdata.
Hierna onderzoek je welke soorten fouten een classifier maakt, ongeacht hoe hij zijn voorspelling berekent.