K-nearest neighbors

K-Nearest Neighbors (KNN) è uno degli algoritmi di machine learning più semplici e intuitivi. Per classificare un nuovo punto dati, esamina i K esempi di addestramento più vicini ad esso e vota — vince la classe di maggioranza. Per la regressione calcola invece la media dei valori dei K vicini.

Questo capitolo tratta:

• Come funziona l'algoritmo KNN passo dopo passo
• Metriche di distanza: Euclidea, Manhattan e Minkowski
• Perché la scalatura delle feature è fondamentale per KNN
• Come scegliere il valore giusto per K
• Classificazione e regressione con scikit-learn
• Valutazione di un classificatore KNN con una matrice di confusione
• Punti di forza, limitazioni e quando usare KNN

Come funziona KNN

KNN è un lazy learner — non esegue alcun "addestramento" vero e proprio. Invece memorizza l'intero dataset e rimanda tutti i calcoli al momento della predizione.

Dato un nuovo punto, l'algoritmo:

1. Calcola la distanza dal nuovo punto a ogni punto di addestramento.
2. Seleziona i K punti di addestramento con le distanze minori (i "nearest neighbors").
3. Aggrega le loro etichette:
   • Classificazione — al nuovo punto viene assegnata l'etichetta di classe più comune.
   • Regressione — al nuovo punto viene assegnata la media (o media ponderata) dei valori target dei vicini.

Poiché non c'è nessun modello da addestrare, aggiungere nuovi dati è immediato — basta aggiungerli al dataset. Il compromesso è che la predizione è lenta per dataset grandi perché il calcolo completo delle distanze viene eseguito ogni volta.

Metriche di distanza

Il concetto di "più vicino" in KNN è definito da una funzione di distanza. Quella predefinita in scikit-learn è la distanza Euclidea, la distanza in linea retta nello spazio n-dimensionale:

d(p, q) = sqrt( (p1-q1)² + (p2-q2)² + … + (pn-qn)² )

Due alternative comuni:

Puoi cambiare la metrica in scikit-learn con il parametro metric:

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5, metric='manhattan')

Perché la scalatura delle feature è fondamentale

KNN calcola distanze grezze. Una feature misurata in migliaia (come lo stipendio) dominerà completamente una feature misurata in singole cifre (come gli anni di esperienza), anche se la feature più piccola è più informativa.

Scala sempre le feature prima di usare KNN. Consulta il capitolo sulla scalatura delle feature per una spiegazione completa; in breve:

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)   # fit on training data only
X_test_scaled  = scaler.transform(X_test)         # apply same transform to test data

Non chiamare mai fit_transform sul test set — ciò farebbe trapelare le statistiche del test set nello scaler.

Scegliere K

K controlla il compromesso bias-varianza:

• K piccolo (es. K=1) — molto flessibile, si adatta strettamente ai dati di addestramento, ma rumoroso e soggetto all'overfitting. Un singolo vicino anomalo può cambiare la predizione.
• K grande — confine decisionale più regolare, varianza minore, ma può portare all'underfitting e confondere i confini reali tra le classi.

L'approccio standard è provare un intervallo di valori di K e scegliere quello con la migliore accuratezza con validazione incrociata:

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

iris = load_iris()
X, y = iris.data, iris.target

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

k_range = range(1, 31)
cv_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_scaled, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

best_k = k_range[np.argmax(cv_scores)]
print(f"Best K: {best_k}, CV Accuracy: {max(cv_scores):.4f}")

Output atteso:

Best K: 6, CV Accuracy: 0.9667

Per ulteriori dettagli sulla validazione incrociata consulta il capitolo sulla cross-validation.

Regole pratiche:

• Preferisci un K dispari per la classificazione binaria per evitare pareggi.
• Un punto di partenza comune è K = sqrt(n) dove n è il numero di campioni di addestramento.
• Valida sempre con la validazione incrociata anziché tirare a indovinare.

Classificazione KNN con scikit-learn

L'esempio seguente usa il dataset Iris — un problema di classificazione multiclasse reale — e illustra l'intero flusso di lavoro: divisione, scalatura, addestramento, predizione, valutazione.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report

# 1. Load a real dataset
iris = load_iris()
X, y = iris.data, iris.target

# 2. Split into training and test sets
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# 3. Scale features — critical for KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled  = scaler.transform(X_test)

# 4. Train the classifier
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# 5. Predict and evaluate
y_pred = knn.predict(X_test_scaled)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.2f}")
print()
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Output atteso:

Accuracy: 0.93

              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        10
  versicolor       0.83      1.00      0.91        10
   virginica       1.00      0.80      0.89        10

    accuracy                           0.93        30
   macro avg       0.94      0.93      0.93        30
weighted avg       0.94      0.93      0.93        30

KNN con K=5 raggiunge il 93% di accuratezza su questo test set di 30 campioni. Setosa viene classificata perfettamente perché è linearmente separabile dalle altre due; versicolor e virginica si sovrappongono in parte, causando alcune classificazioni errate.

Nota l'argomento stratify=y in train_test_split — questo preserva le proporzioni delle classi in ciascuna divisione, il che è particolarmente importante per dataset sbilanciati. Consulta train/test split per i dettagli.

Valutazione con una matrice di confusione

Una matrice di confusione mostra esattamente quali classi il modello confonde tra loro:

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import confusion_matrix

iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_s, y_train)
y_pred = knn.predict(X_test_s)

cm = confusion_matrix(y_test, y_pred)
print(cm)

Output atteso:

[[10  0  0]
 [ 0 10  0]
 [ 0  2  8]]

Ogni riga è una classe reale; ogni colonna è una classe predetta. I valori sulla diagonale sono predizioni corrette; i valori fuori dalla diagonale sono classificazioni errate. Qui 2 campioni di virginica sono stati classificati erroneamente come versicolor. Consulta il capitolo sulla matrice di confusione per una spiegazione più approfondita.

Regressione KNN con scikit-learn

Per la regressione, KNN predice la media dei valori target dei K vicini più prossimi. Sostituisci KNeighborsClassifier con KNeighborsRegressor:

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np

# Load a real regression dataset (a subset for speed)
housing = fetch_california_housing()
X, y = housing.data[:2000], housing.target[:2000]

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_reg = KNeighborsRegressor(n_neighbors=5)
knn_reg.fit(X_train_s, y_train)
y_pred = knn_reg.predict(X_test_s)

rmse = np.sqrt(mean_squared_error(y_test, y_pred))
r2   = r2_score(y_test, y_pred)
print(f"RMSE: {rmse:.4f}")
print(f"R²:   {r2:.4f}")

Output atteso:

RMSE: 0.4217
R²:   0.8053

L'RMSE è espresso nelle stesse unità del target (valore mediano delle abitazioni in $100k). Un R² di 0,81 significa che il modello spiega circa l'81% della varianza su questo sottoinsieme di 2.000 campioni — un risultato notevole per un baseline KNN non ottimizzato.

KNN ponderato

Per impostazione predefinita, tutti i K vicini hanno lo stesso peso indipendentemente da quanto siano vicini. Impostando weights='distance' i vicini più prossimi contano di più:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score

iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_uniform  = KNeighborsClassifier(n_neighbors=5, weights='uniform')
knn_distance = KNeighborsClassifier(n_neighbors=5, weights='distance')

knn_uniform.fit(X_train_s, y_train)
knn_distance.fit(X_train_s, y_train)

print(f"Uniform weights accuracy:  {accuracy_score(y_test, knn_uniform.predict(X_test_s)):.2f}")
print(f"Distance weights accuracy: {accuracy_score(y_test, knn_distance.predict(X_test_s)):.2f}")

Output atteso:

Uniform weights accuracy:  0.93
Distance weights accuracy: 0.97

La ponderazione per distanza migliora l'accuratezza da 0,93 a 0,97 — i vicini più prossimi hanno maggiore influenza, il che aiuta a risolvere i casi ambigui ai confini.

Punti di forza e limitazioni

Quando usare KNN

• Il dataset è di piccole o medie dimensioni (decine di migliaia di campioni).
• Hai bisogno di un baseline rapido e interpretabile — KNN è facile da spiegare e da analizzare.
• Hai feature ben scalate e a bassa dimensionalità.
• Il confine decisionale è complesso e non lineare.

Quando evitare KNN

• Dataset grandi. Il tempo di predizione scala con il numero di campioni di addestramento (O(n·d) per query). Per milioni di campioni, considera librerie per nearest-neighbor approssimato (Faiss, Annoy) o passa a un algoritmo più veloce.
• Dati ad alta dimensionalità. In molte dimensioni, tutti i punti diventano approssimativamente equidistanti — la "maledizione della dimensionalità". KNN degrada rapidamente oltre le ~20 feature. Applica prima una riduzione della dimensionalità (PCA, selezione delle feature).
• Feature irrilevanti. Ogni feature partecipa al calcolo della distanza. Feature rumorose o irrilevanti diluiscono il segnale. Rimuovile o riducile prima dell'addestramento.
• Ambienti con memoria limitata. KNN memorizza l'intero set di addestramento; un dataset con milioni di righe occupa una quantità significativa di RAM.

Riepilogo

Capitoli correlati:

• Scalatura delle feature — perché e come scalare prima di KNN
• Train/test split — suddividere correttamente i dati
• Cross-validation — scegliere K con k-fold CV
• Matrice di confusione — interpretare i risultati della classificazione
• Grid search — ottimizzazione sistematica degli iperparametri