Cos'è l'algoritmo dei k-Nearest Neighbors (kNN)?

kNN (k-Nearest Neighbors) è un metodo non parametrico utilizzato per classificazione e regressione. L'idea è semplice: un oggetto viene classificato dalla maggioranza dei voti dei suoi vicini, dove l'oggetto viene assegnato alla classe più comune tra i suoi k vicini più prossimi. Per la regressione, si predice il valore medio delle etichette dei k vicini più prossimi.

Aspetti chiave:

• Parametro k: Numero di vicini considerati nella decisione. La scelta di k influisce molto sul risultato. Un k piccolo può essere sensibile al rumore, un k grande può ignorare strutture locali.
• Metrica di distanza: Usata per determinare la "prossimità" tra i punti dati. Le più comuni sono: distanza euclidea, distanza di Manhattan.
• Caratteristiche:
  • Algoritmo "pigro": nessun o minimo di apprendimento (semplicemente memorizzare i dati di addestramento). La previsione avviene solo al momento della richiesta.
  • Facile da implementare e comprendere.
  • La performance nella fase di previsione può diminuire con grandi set di dati, poiché richiede di calcolare le distanze a tutti gli esempi di addestramento.
  • Sensibile alla scala delle caratteristiche.
  • Può funzionare male con dati rumorosi.

Fasi di lavoro (per la classificazione):

1. Scegliere il valore di k.
2. Scegliere la metrica di distanza.
3. Per un nuovo oggetto, per il quale si desidera fare una previsione: a. Calcolare la distanza tra questo oggetto e tutti gli oggetti nel set di addestramento. b. Selezionare i k oggetti più vicini nel set di addestramento. c. Determinare la classe più frequente tra questi k oggetti. d. Assegnare questa classe al nuovo oggetto.

Esempio (pseudo-codice):

# Funzione per calcolare la distanza euclidea
def euclidean_distance(p1, p2):
    # ... calcolo della distanza ...

# Funzione per trovare i k vicini più prossimi e prevedere la classe
def predict(training_data, new_data_point, k, distance_metric):
    distances = []
    for data_point in training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        distances.append((dist, data_point['label']))

    # Ordinare per distanza e selezionare i k più vicini
    distances.sort(key=lambda x: x[0])
    k_nearest = distances[:k]

    # Contare i voti delle classi
    class_votes = {}
    for dist, label in k_nearest:
        class_votes[label] = class_votes.get(label, 0) + 1

    # Determinare la classe con più voti
    predicted_class = max(class_votes, key=class_votes.get)
    return predicted_class