Wat is het k-Nearest Neighbors (kNN) algoritme?

kNN (k-dichtstbijzijnde buren) is een niet-parametrische methode die wordt gebruikt voor classificatie en regressie. Het idee is eenvoudig: een object wordt geclassificeerd door de meerderheid van de stemmen van zijn buren, waarbij het object wordt toegewezen aan de meest voorkomende klasse onder zijn k dichtstbijzijnde buren. Voor regressie wordt de gemiddelde waarde van de labels van de k dichtstbijzijnde buren voorspeld.

Belangrijke aspecten:

• Parameter k: Aantal buren dat wordt meegenomen bij het nemen van een beslissing. De keuze van k beïnvloedt het resultaat sterk. Een kleine k kan gevoelig zijn voor ruis, een grote k kan lokale structuren negeren.
• Metriek van afstand: Wordt gebruikt om de "dichtbijheid" tussen datapunten te bepalen. De meest gebruikte zijn: Euclidische afstand, Manhattan afstand.
• Kenmerken:
  • "Lui" algoritme: geen of minimale training (gewoon de trainingsgegevens opslaan). Voorspelling gebeurt alleen tijdens de aanvraag.
  • Eenvoudig te implementeren en te begrijpen.
  • Prestaties tijdens de voorspelling kunnen achteruitgaan bij grote datasets, omdat het berekenen van afstanden tot alle trainingsvoorbeelden vereist is.
  • Gevoelig voor de schaal van de kenmerken.
  • Kan slecht presteren op gegevens met veel ruis.

Stappen (voor classificatie):

1. Kies de waarde van k.
2. Kies de afstandsmetriek.
3. Voor een nieuw object, waarvoor een voorspelling moet worden gedaan: a. Bereken de afstand tussen dit object en alle objecten in de trainingsset. b. Kies de k dichtstbijzijnde objecten uit de trainingsset. c. Bepaal de meest voorkomende klasse onder deze k objecten. d. Ken deze klasse toe aan het nieuwe object.

Voorbeeld (pseudocode):

# Functie om de Euclidische afstand te berekenen
def euclidean_distance(p1, p2):
    # ... afstand berekenen ...

# Functie om de k dichtstbijzijnde buren te zoeken en de klasse te voorspellen
def predict(training_data, new_data_point, k, distance_metric):
    afstanden = []
    for data_point in training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        afstanden.append((dist, data_point['label']))

    # Sorteren op afstand en de k dichtstbijzijnde selecteren
    afstanden.sort(key=lambda x: x[0])
    k_dichtstbijzijnde = afstanden[:k]

    # Stemmen tellen voor klassen
    klasse_stemmen = {}
    for dist, label in k_dichtstbijzijnde:
        klasse_stemmen[label] = klasse_stemmen.get(label, 0) + 1

    # Klasse met meeste stemmen bepalen
    voorspelde_klasse = max(klasse_stemmen, key=klasse_stemmen.get)
    return voorspelde_klasse