34 - KNN: classificare guardando i vicini (e la maledizione della dimensionalità)

Ti trasferisci in un quartiere nuovo e vuoi sapere se il ristorante all'angolo è buono. Non hai un modello: chiedi ai cinque vicini di casa più prossimi e segui la maggioranza. Questo è K-Nearest Neighbors (KNN, «i K vicini più prossimi»): per classificare un punto nuovo, guarda i K punti di training più simili e fai votare le loro etichette. Non c'è nessuna fase di addestramento nel senso classico, nessun parametro da ottimizzare: il «modello» è il dataset stesso.

È l'algoritmo ideale per capire tre concetti che ti accompagneranno a lungo: la scelta di una distanza, il compromesso tra bias e varianza controllato da K, e la maledizione della dimensionalità, che spiega perché «più feature» non è sempre meglio.

Che cos'è una «distanza»

Per due case in una città puoi misurare la distanza in linea d'aria o quella percorrendo le strade. Per due esempi con n feature la situazione è identica: ogni esempio è un punto in uno spazio a n dimensioni, e una distanza è una regola che assegna a ogni coppia di punti un numero non negativo: zero solo per punti coincidenti, simmetrico, e che rispetta la «disuguaglianza triangolare» (andare da A a C non costa più che passare per B). La scelta della distanza è una scelta di modellazione: dice che cosa significa «simile» per il tuo problema.

L'algoritmo e la matematica

Dato un punto di test x:

1. Calcola la distanza tra x e ogni punto di training.
2. Prendi i K punti con distanza minima (l'insieme N_K(x)).
3. Classificazione: restituisci la classe più frequente tra quei K. Regressione: restituisci la media dei loro valori.

Il costo sta quasi tutto nel primo passo, perché ogni previsione richiede la distanza da ogni punto di training. Ordinare e votare sono passi economici al confronto. Passare dalla classificazione alla regressione cambia solo il terzo passo (voto contro media), ed è per questo che tutto ciò che segue sulle distanze e su K vale per entrambi i compiti.

La distanza più comune è la distanza di Minkowski di ordine p:

d(x, z) = ( Σ_j |x_j − z_j|^p )^(1/p)

p = 2  →  euclidea  √(Σ (x_j − z_j)²)     "in linea d'aria"
p = 1  →  Manhattan Σ |x_j − z_j|         "per le strade a griglia"

Il voto può essere pesato: un vicino vicinissimo conta più di uno che sta al limite dei K. Con peso w_i = 1/d(x, x_i), il punteggio della classe c è

punteggio(c) = Σ_{i ∈ N_K(x)} w_i · [y_i = c]       ŷ = argmax_c punteggio(c)

dove [y_i = c] vale 1 se il vicino i è di classe c e 0 altrimenti. KNN è un lazy learner (apprendista pigro): tutto il lavoro è rimandato alla previsione. Costo per una previsione: O(n·d) confronti con n punti di training e d feature, e bisogna tenere in memoria l'intero training set.

Implementazione a mano

Lavoriamo con il dataset Wine (178 vini, 13 misure chimiche, 3 cultivar). La parte delicata è calcolare tutte le distanze in forma vettoriale, senza cicli, e tenere sotto controllo le shape:

import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

class KNNDaZero:
    def __init__(self, k=5, pesato=False):
        self.k, self.pesato = k, pesato

    def fit(self, X, y):
        self.X, self.y = X, y
        self.classi = np.unique(y)
        return self

    def predict(self, X):
        # X: (m, d)   self.X: (n, d)   ->  d2: (m, n)
        d2 = ((X[:, None, :] - self.X[None, :, :]) ** 2).sum(axis=2)
        idx = np.argsort(d2, axis=1)[:, :self.k]            # (m, k) indici dei k vicini
        etichette = self.y[idx]                              # (m, k)
        dist = np.sqrt(np.take_along_axis(d2, idx, axis=1))  # (m, k)
        w = 1.0 / (dist + 1e-9) if self.pesato else np.ones_like(dist)
        punteggi = np.stack([(w * (etichette == c)).sum(axis=1) for c in self.classi], axis=1)
        return self.classi[punteggi.argmax(axis=1)]

Xw, yw = load_wine(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xw, yw, test_size=0.3, stratify=yw, random_state=0)

mio = KNNDaZero(k=5).fit(Xtr, ytr)
lib = KNeighborsClassifier(n_neighbors=5).fit(Xtr, ytr)
print("senza scaling  a mano: %.3f   sklearn: %.3f" % ((mio.predict(Xte) == yte).mean(), lib.score(Xte, yte)))
print("previsioni identiche:", bool((mio.predict(Xte) == lib.predict(Xte)).all()))

senza scaling  a mano: 0.722   sklearn: 0.722
previsioni identiche: True

Il disegno mostra l'algoritmo con K = 5: il punto nuovo (stella verde) ha dentro il cerchio 3 vicini blu e 2 rossi, quindi vince il blu. Il cerchio non è un raggio fisso: ha la dimensione necessaria per contenere esattamente K punti.

Cosa fa il codice. Nel metodo predict la riga delle distanze usa il broadcasting di NumPy: X[:, None, :] ha forma (m, 1, d) e self.X[None, :, :] ha forma (1, n, d); sottraendoli NumPy «allarga» le dimensioni di lunghezza 1 e produce un tensore (m, n, d) con tutte le differenze coordinata per coordinata; elevando al quadrato e sommando sull'asse delle feature si ottiene la matrice (m, n) delle distanze al quadrato fra ogni punto di test e ogni punto di training. Non serve la radice per ordinare, perché la radice è crescente. np.argsort restituisce gli indici ordinati dal più vicino; si tengono i primi K. self.y[idx] recupera le etichette dei vicini (forma (m, K)). Infine per ogni classe si sommano i pesi dei vicini di quella classe e si sceglie la classe con punteggio massimo.

Le previsioni coincidono con quelle della libreria, ma l'accuratezza è solo 0.722. Il motivo è la trappola più comune di KNN, ed è sotto gli occhi di tutti: la scala delle feature.

Trappola n. 1: se le feature hanno scale diverse, vince la più grande

Nel dataset Wine la feature «proline» ha valori nell'ordine delle centinaia o migliaia, mentre altre stanno tra 0 e 1. Nella distanza euclidea la differenza su «proline» domina tutto: i vicini sono scelti guardando praticamente solo quella colonna. Standardizzare (sottrarre la media e dividere per la deviazione standard, con i parametri calcolati solo sul training) rimette tutte le feature sullo stesso piano:

print("range per feature (min..max) delle prime 3 e di 'proline' (ultima):")
print(np.round(Xtr.min(axis=0)[[0, 1, 2, 12]], 2), np.round(Xtr.max(axis=0)[[0, 1, 2, 12]], 2))

scaler = StandardScaler().fit(Xtr)                  # media e std SOLO dal training
Ztr, Zte = scaler.transform(Xtr), scaler.transform(Xte)
mio_s = KNNDaZero(k=5).fit(Ztr, ytr)
print("con scaling    a mano: %.3f" % (mio_s.predict(Zte) == yte).mean())

range per feature (min..max) delle prime 3 e di 'proline' (ultima):
[ 11.41   0.74   1.7  278.  ] [  14.83    5.8     3.23 1680.  ]
con scaling    a mano: 0.963

Le prime due righe del listato stampano minimi e massimi di quattro colonne, per far vedere la differenza di scala. Poi StandardScaler().fit(Xtr) impara media e deviazione standard solo dal training, e transform applica la stessa trasformazione a training e test: il test viene scalato con i parametri del training, mai con i propri, altrimenti è data leakage (se non hai presente il problema, il processo di un progetto di ML lo spiega).

Stesso algoritmo, stessi dati: l'accuratezza passa da 0.722 a 0.963, e la differenza è tutta nella scala («proline» va da 278 a 1680, la seconda feature da 0.74 a 5.8). Le distanze sono il cuore di KNN; se non hanno senso, non ha senso niente.

A = ( 3,  4)   argilloso
B = ( 5,  1)   sabbioso
C = (-4,  2)   argilloso
D = ( 1,  6)   sabbioso

La scelta di K: il compromesso bias-varianza

K controlla la complessità del modello, in modo opposto a quanto potresti aspettarti:

• K = 1: il confine segue ogni singolo punto, compresi i rumorosi. Varianza alta, bias basso: overfitting. Sul training l'accuratezza è sempre 1.0, perché il vicino più prossimo di un punto di training è sé stesso.
• K grande: il voto si media su regioni ampie e il confine diventa liscio. Varianza bassa, bias alto: underfitting. Nel caso estremo K = n si predice sempre la classe più frequente.

I due estremi disegnano una curva a U dell'errore di test: a sinistra il modello è troppo flessibile e insegue il rumore, a destra è troppo liscio per vedere la struttura. Il valore giusto sta in mezzo e dipende dal rumore del problema, non c'è un K universale. L'esperimento sotto mette in fila otto valori di K sullo stesso dataset per vedere la U con i numeri.

Il ciclo addestra un modello per ciascun K sul dataset standardizzato (Ztr, Zte sono training e test già scalati) e stampa l'accuratezza su entrambi. L'ultimo valore, len(Ztr), è il caso estremo K = n.

for k in (1, 3, 5, 9, 15, 31, 61, len(Ztr)):
    m = KNeighborsClassifier(n_neighbors=k).fit(Ztr, ytr)
    print("k=%3d  train %.3f   test %.3f" % (k, m.score(Ztr, ytr), m.score(Zte, yte)))

k=  1  train 1.000   test 1.000
k=  3  train 0.944   test 0.963
k=  5  train 0.968   test 0.963
k=  9  train 0.952   test 0.963
k= 15  train 0.952   test 0.981
k= 31  train 0.976   test 0.981
k= 61  train 0.952   test 0.963
k=124  train 0.403   test 0.389

Con K = 1 l'accuratezza di training è 1.000 per costruzione: guardarla non dice nulla. L'ultima riga usa K = numero di campioni di training (124): ogni previsione è il voto di tutto il training, cioè sempre la classe più frequente, e l'accuratezza crolla (underfitting estremo). Attenzione anche alla lettura del test: sono 54 campioni, quindi un solo campione in più o in meno sposta l'accuratezza di 0.019. Differenze di quell'ordine tra un K e l'altro (0.963 contro 0.981) sono rumore, non una classifica. Il valore giusto si sceglie con la validazione incrociata sul training (GridSearchCV su n_neighbors), mai sul test set. Per la classificazione binaria conviene K dispari, per evitare i pareggi nel voto.

Trappola n. 2: la maledizione della dimensionalità

KNN si basa sull'idea che «vicino» abbia un significato. In molte dimensioni, la geometria lo rovina. Per vederlo senza fidarti di me, misura: genera 1000 punti casuali uniformi in d dimensioni, prendi un punto di riferimento e calcola la distanza dal più vicino e dal più lontano.

Il generatore ha seme fisso (default_rng(0)), quindi i numeri sono ripetibili. Il rapporto (max − min)/min è la quantità che interessa: se è grande, «il più vicino» è molto più vicino degli altri; se tende a zero, i punti sono tutti quasi equidistanti.

rng = np.random.default_rng(0)
for d in (2, 10, 100, 1000):
    P = rng.uniform(size=(1000, d))
    q = rng.uniform(size=(1, d))
    dist = np.sqrt(((P - q) ** 2).sum(axis=1))
    print("d=%4d  vicino più prossimo %.2f   più lontano %.2f   (max-min)/min = %.2f" % (
        d, dist.min(), dist.max(), (dist.max() - dist.min()) / dist.min()))

d=   2  vicino più prossimo 0.01   più lontano 1.33   (max-min)/min = 134.62
d=  10  vicino più prossimo 0.47   più lontano 2.11   (max-min)/min = 3.48
d= 100  vicino più prossimo 3.35   più lontano 4.65   (max-min)/min = 0.39
d=1000  vicino più prossimo 12.17   più lontano 13.55   (max-min)/min = 0.11

Con d = 2 il rapporto (max − min)/min vale 134.6, con d = 1000 vale 0.11: il più lontano è solo l'11% più distante del più vicino. Al crescere di d il rapporto si schiaccia verso zero: il punto più vicino e il più lontano sono quasi alla stessa distanza, quindi «il più vicino» perde significato. Questo fenomeno si chiama concentrazione delle distanze. L'altro lato del problema è che i dati diventano radi: per coprire uno spazio a 100 dimensioni con la stessa densità di uno a 2 dimensioni servirebbero quantità di campioni esponenziali.

L'effetto pratico più insidioso è l'aggiunta di feature irrilevanti. Ogni colonna di rumore contribuisce alla distanza quanto una informativa. Aggiungiamo al dataset Wine (già standardizzato) colonne di rumore gaussiano e misuriamo il test:

Per ogni quantità di rumore il listato concatena (np.hstack) al dataset standardizzato altrettante colonne di numeri gaussiani indipendenti dalla classe, sia sul training sia sul test, e riaddestra KNN con K = 5. L'unica cosa che cambia da una riga all'altra è il numero di colonne inutili.

for rumore in (0, 10, 50, 200, 1000):
    r = np.random.default_rng(1)
    Atr = np.hstack([Ztr, r.normal(size=(len(Ztr), rumore))])
    Ate = np.hstack([Zte, r.normal(size=(len(Zte), rumore))])
    m = KNeighborsClassifier(n_neighbors=5).fit(Atr, ytr)
    print("colonne di rumore aggiunte: %4d  ->  test %.3f" % (rumore, m.score(Ate, yte)))

colonne di rumore aggiunte:    0  ->  test 0.963
colonne di rumore aggiunte:   10  ->  test 0.944
colonne di rumore aggiunte:   50  ->  test 0.796
colonne di rumore aggiunte:  200  ->  test 0.648
colonne di rumore aggiunte: 1000  ->  test 0.519

Le 13 colonne informative sono sempre le stesse, ma man mano che le colonne inutili aumentano l'accuratezza scende da 0.963 a 0.944 con 10 colonne, 0.796 con 50, 0.648 con 200 fino a 0.519 con 1000 (la sola classe più frequente varrebbe 0.389). Rimedi: selezione delle feature, riduzione di dimensionalità (PCA, che trovi in riduzione di dimensionalità), distanze apprese, oppure semplicemente un altro algoritmo meno sensibile.

Come si rende veloce: indici spaziali

Il confronto con tutti i punti (brute force) costa O(n·d) per previsione. Strutture come il KD-tree e il ball tree organizzano i punti per saltare intere regioni lontane: in poche dimensioni la ricerca scende verso O(log n), ma in molte dimensioni il vantaggio svanisce per la stessa ragione di prima: la guida di scikit-learn indica il KD-tree come molto veloce sotto circa 20 dimensioni e, oltre, anche più lento della forza bruta. scikit-learn sceglie da solo con algorithm="auto". Per milioni di vettori ad alta dimensione si usano librerie di ricerca approssimata dei vicini, che rinunciano a una piccola parte di precisione in cambio di molta velocità.

Trade-off

• Pro: concettualmente semplice, nessun addestramento, confini arbitrariamente complessi, funziona sia per classificazione sia per regressione, si aggiorna aggiungendo semplicemente punti.
• Contro: previsione lenta e memoria proporzionale al training set; sensibile alla scala e alle feature irrilevanti; soffre l'alta dimensionalità; con classi sbilanciate i vicini della classe maggioritaria sono statisticamente più numerosi.
• Usalo come baseline rapida su dataset piccoli e a poche dimensioni con feature scalate; evitalo con molte feature, tanti campioni o requisiti di latenza stretti.

I pro e i contro hanno una sola radice: KNN non impara nulla e tiene i dati. Per questo è semplice da capire e da aggiornare, e per questo è pesante in previsione e fragile quando i dati sono scalati male o hanno colonne inutili. Come baseline è difficile da battere in semplicità; come modello da mettere in produzione richiede di aver verificato latenza e memoria.

Altre trappole reali

• Valutare KNN sul training set con K = 1 dà 1.0: il punto è vicino di sé stesso. Valuta sempre su dati esclusi.
• Duplicati tra train e test: con KNN sono letali, perché il duplicato nel training è il vicino perfetto e l'accuratezza è gonfiata.
• Feature categoriche codificate con numeri arbitrari (rosso = 1, verde = 2, blu = 3) inventano una distanza che non esiste. Servono one-hot o distanze apposite.
• Scaler fit su tutto il dataset: stesso data leakage visto nelle lezioni precedenti. Lo scaler appartiene alla Pipeline (vedi il processo di un progetto di ML).
• Accuratezza sulle classi sbilanciate: con K grande il voto tende alla classe maggioritaria; controlla recall e precision.

Le cinque trappole si dividono in due gruppi. Le prime tre (valutazione sul training, duplicati, scaler sul dataset intero) gonfiano il numero che misuri; le altre due (categoriche, sbilanciamento) rendono la distanza o il voto privi di senso. In entrambi i casi il modello gira senza errori e dà un'accuratezza plausibile: nessun messaggio ti avvisa.

La scelta della distanza: quattro metriche su due dataset

La distanza è l'unico «iperparametro di modellazione» di KNN: definisce che cosa vuol dire «simile». Confrontiamo quattro scelte. La euclidea (lunghezza del segmento). La Manhattan (somma delle differenze assolute: meno sensibile ai valori anomali di una singola feature). La Chebyshev (la differenza massima su una sola feature: due punti sono vicini solo se lo sono su tutte le feature). Il coseno (misura l'angolo tra i vettori, ignorando la lunghezza: tipica per testi o per vettori di conteggi). Per avere numeri affidabili usiamo la validazione incrociata ripetuta: 5 gruppi ripetuti 3 volte, quindi 15 stime per metrica, delle quali si riportano media e deviazione.

Il listato valuta ciascuna metrica con cross_val_score sulla validazione incrociata ripetuta cv, su due dataset: Wine, standardizzato dentro la Pipeline, e Digits, i cui pixel hanno già tutti la stessa scala. algorithm="brute" è necessario perché non tutte le metriche sono supportate dagli alberi.

from sklearn.datasets import load_digits
from sklearn.model_selection import cross_val_score, RepeatedStratifiedKFold
from sklearn.pipeline import make_pipeline

cv = RepeatedStratifiedKFold(n_splits=5, n_repeats=3, random_state=0)
X_dg, y_dg = load_digits(return_X_y=True)

print("metrica      wine (standardizzato)    digits (pixel grezzi)")
for metric in ("euclidean", "manhattan", "chebyshev", "cosine"):
    wine = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(5, metric=metric, algorithm="brute")), Xw, yw, cv=cv)
    digits = cross_val_score(KNeighborsClassifier(5, metric=metric, algorithm="brute"), X_dg, y_dg, cv=cv)
    print("%-11s   %.3f +- %.3f           %.3f +- %.3f" % (metric, wine.mean(), wine.std(), digits.mean(), digits.std()))

metrica      wine (standardizzato)    digits (pixel grezzi)
euclidean     0.961 +- 0.017           0.986 +- 0.006
manhattan     0.966 +- 0.023           0.983 +- 0.006
chebyshev     0.927 +- 0.033           0.973 +- 0.008
cosine        0.959 +- 0.027           0.984 +- 0.005

I risultati (K = 5, 15 stime per cella): su Wine euclidea 0,961, Manhattan 0,966, coseno 0,959, Chebyshev 0,927; su Digits 0,986, 0,983, 0,984 e 0,973. Le prime tre sono indistinguibili (le differenze di mezzo punto sono più piccole delle deviazioni, 0,017-0,027 su Wine e 0,005-0,006 su Digits). Chebyshev è peggiore su entrambi i dataset in modo netto: ha senso, perché guarda una sola feature (la più diversa) e butta via l'informazione delle altre. La conclusione pratica: la metrica euclidea è un buon default, Manhattan merita una prova quando ci sono outlier o molte feature, il coseno quando la lunghezza dei vettori è irrilevante, e i confronti vanno fatti con più ripetizioni.

Pesi e K con la validazione incrociata ripetuta

Nella sezione sulla scelta di K avevamo guardato un singolo test di 54 campioni, e avevamo avvertito che differenze di 0,019 sono rumore. Rifacciamo l'analisi come andrebbe fatta, con 15 stime per ogni valore di K e confrontando il voto uniforme con il voto pesato per l'inverso della distanza.

Il doppio ciclo calcola, per ogni K e per i due schemi di voto (weights="uniform" e "distance", quest'ultimo proporzionale all'inverso della distanza come nella nostra classe a mano), media e deviazione su 15 stime con la stessa cv di prima.

print("K      voto uniforme        voto pesato (1/distanza)")
for k in (1, 5, 15, 31, 61):
    row = []
    for weights in ("uniform", "distance"):
        s = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(k, weights=weights)), Xw, yw, cv=cv)
        row.append("%.3f +- %.3f" % (s.mean(), s.std()))
    print("%-5d  %s       %s" % (k, row[0], row[1]))

K      voto uniforme        voto pesato (1/distanza)
1      0.953 +- 0.036       0.953 +- 0.036
5      0.961 +- 0.017       0.963 +- 0.020
15     0.966 +- 0.023       0.966 +- 0.025
31     0.979 +- 0.019       0.981 +- 0.017
61     0.949 +- 0.028       0.962 +- 0.025

Con K = 1 le due colonne coincidono (un solo vicino: il peso non conta) a 0,953 ± 0,036. L'accuratezza cresce con K fino a un massimo intorno a K = 31 (0,979-0,981 ± 0,02) e poi cala: con K = 61 il voto include troppi vicini di altre classi, su un dataset di 178 esempi. Le due colonne sono praticamente identiche, perché con feature standardizzate e classi ben separate i vicini più prossimi concordano comunque. Rispetto al singolo test da 54 campioni, la validazione ripetuta indica una zona migliore verso K grandi; ma la deviazione è 0,02 e la differenza tra K = 15 e K = 31 (1,3 punti) è ancora dello stesso ordine, quindi leggila come una tendenza e non come una classifica.

Velocità: quando gli alberi spaziali aiutano e quando no

Sopra abbiamo detto che KD-tree e ball tree accelerano la ricerca in poche dimensioni e perdono vantaggio in molte. Misuriamolo: 20 000 punti casuali, 500 interrogazioni, in 3 e in 50 dimensioni, con i tre algoritmi.

Il listato costruisce, per 3 e per 50 dimensioni, 20 000 punti gaussiani e 500 interrogazioni, crea un indice per ciascun algoritmo e cronometra solo la chiamata a kneighbors. Le etichette sono tutte zero: qui conta la ricerca dei vicini, non la classificazione.

import time
rng = np.random.default_rng(0)
print("dimensioni   forza bruta   KD-tree    ball tree   (secondi per 500 interrogazioni)")
for d in (3, 50):
    X_big, queries = rng.normal(size=(20000, d)), rng.normal(size=(500, d))
    times = []
    for algorithm in ("brute", "kd_tree", "ball_tree"):
        index = KNeighborsClassifier(5, algorithm=algorithm).fit(X_big, np.zeros(len(X_big), dtype=int))
        t0 = time.time(); index.kneighbors(queries); times.append(time.time() - t0)
    print("%10d   %11.3f   %8.3f   %9.3f" % ((d,) + tuple(times)))

# Uscita di una esecuzione; i tempi cambiano a ogni esecuzione
# dimensioni   forza bruta   KD-tree    ball tree   (secondi per 500 interrogazioni)
#          3         0.007      0.002       0.012
#         50         0.053      0.733       0.443

In 3 dimensioni il KD-tree è nettamente il più veloce (circa 0,002-0,003 s contro 0,007-0,033 s della forza bruta e 0,011-0,014 s del ball tree): salta intere regioni dello spazio. In 50 dimensioni il quadro si ribalta: la forza bruta impiega 0,05-0,10 s, il KD-tree 0,56-1,6 s (da 10 a 20 volte di più) e il ball tree 0,39-0,63 s (da 5 a 8 volte di più). Sono i minimi e i massimi di sette esecuzioni su un PC a 12 thread logici, Python 3.14.4, scikit-learn 1.8.0; i valori cambiano tra esecuzioni, l'ordine delle colonne no. La documentazione di scikit-learn spiega il meccanismo: per dimensioni grandi il costo del KD-tree si avvicina a quello della forza bruta e il sovraccarico della struttura lo rende più lento. È la maledizione della dimensionalità applicata alle strutture di ricerca: quando le distanze si concentrano, l'albero non riesce a escludere nessuna regione. algorithm="auto" sceglie già in base ai dati; per milioni di vettori servono librerie di ricerca approssimata.

KNN per la regressione, e il limite dell'estrapolazione

KNN funziona anche per prevedere un numero: si restituisce la media dei valori dei K vicini. Il bilanciamento tra bias e varianza è lo stesso: K piccolo insegue il rumore, K grande liscia troppo. Lo vediamo su 200 punti rumorosi di una sinusoide, con l'errore quadratico misurato rispetto alla funzione vera (possiamo, perché i dati sono sintetici). Poi interroghiamo il modello fuori dall'intervallo dei dati.

Il listato genera 200 punti di una sinusoide con rumore gaussiano di deviazione 0,3, addestra regressori con K diversi e misura l'errore quadratico medio contro np.sin su una griglia fitta, non contro i dati rumorosi. L'ultima parte chiede una previsione a x = 7 e x = 10, fuori dall'intervallo [0, 6] dei dati.

from sklearn.neighbors import KNeighborsRegressor

x = rng.uniform(0, 6, 200)
y = np.sin(x) + rng.normal(0, 0.3, 200)                          # sinusoide + rumore (deviazione 0,3)
x_grid = np.linspace(0, 6, 300)

print("K      errore quadratico medio rispetto alla funzione vera")
for k in (1, 5, 20, 100):
    model = KNeighborsRegressor(k).fit(x[:, None], y)
    print("%-5d  %.3f" % (k, ((model.predict(x_grid[:, None]) - np.sin(x_grid)) ** 2).mean()))

model = KNeighborsRegressor(5).fit(x[:, None], y)
outside = np.array([[7.0], [10.0]])
print("\nprevisioni fuori dall'intervallo (x = 7 e 10):  %s   valori veri sin(x): %s" % (np.round(model.predict(outside), 3), np.round(np.sin([7, 10]), 3)))

K      errore quadratico medio rispetto alla funzione vera
1      0.106
5      0.018
20     0.006
100    0.062

previsioni fuori dall'intervallo (x = 7 e 10):  [-0.376 -0.376]   valori veri sin(x): [ 0.657 -0.544]

Il profilo a «U» è quello atteso: K = 1 fa 0,106 (insegue il rumore: la deviazione del rumore è 0,3, varianza 0,09, e il modello ne eredita quasi tutta); K = 5 scende a 0,018; K = 20 al minimo, 0,006; K = 100 risale a 0,062 perché la media su 100 vicini, in un intervallo di ampiezza 6 con 200 punti, copre quasi un terzo del dominio e appiattisce la curva. Il punto più importante è nell'ultima riga: fuori dall'intervallo dei dati, KNN non estrapola. Per x = 7 e per x = 10 la previsione è la stessa, −0,376: la media dei cinque punti più vicini, che sono sempre gli ultimi dell'intervallo (intorno a x = 6). I valori veri sono 0,657 e −0,544. Come gli alberi, KNN predice «costanti a tratti» e, oltre i dati, una costante: è un modello di interpolazione, non di estrapolazione. Per fenomeni che continuano oltre l'intervallo osservato (trend, crescita) serve un modello con struttura, come una regressione.

KNN e classi sbilanciate

Con una classe rara (qui il 5% di positivi), il voto di maggioranza tra K vicini penalizza la minoranza: perché un positivo venga previsto, la maggior parte dei suoi K vicini deve essere positiva, e i positivi sono per definizione pochi. Misuriamo come cambiano recall e precision al crescere di K.

Il listato crea 4 000 esempi con il 5% di positivi (weights=[0.95, 0.05]), li divide in modo stratificato e, per quattro valori di K, stampa accuratezza, recall e precision della classe rara. Lo scaler sta di nuovo dentro la Pipeline.

from sklearn.datasets import make_classification
from sklearn.metrics import recall_score, precision_score

X_im, y_im = make_classification(n_samples=4000, n_features=6, n_informative=4, weights=[0.95, 0.05], class_sep=1.2, random_state=0)
X_im_tr, X_im_te, y_im_tr, y_im_te = train_test_split(X_im, y_im, test_size=0.3, stratify=y_im, random_state=0)

print("K     accuratezza   recall   precision      (quota di positivi nel test: %.3f)" % y_im_te.mean())
for k in (1, 5, 15, 45):
    m = make_pipeline(StandardScaler(), KNeighborsClassifier(k)).fit(X_im_tr, y_im_tr)
    pred = m.predict(X_im_te)
    print("%-5d %9.3f    %.3f    %.3f" % (k, m.score(X_im_te, y_im_te), recall_score(y_im_te, pred), precision_score(y_im_te, pred)))

K     accuratezza   recall   precision      (quota di positivi nel test: 0.055)
1         0.967    0.606    0.741
5         0.973    0.515    0.971
15        0.968    0.424    1.000
45        0.960    0.273    1.000

L'accuratezza resta alta e quasi costante (0,960-0,973), come sempre con classi sbilanciate; sono recall e precision a raccontare la storia. Con K = 1 la recall è 0,606 e la precision 0,741. Aumentando K la precision sale (0,971 con K = 5, 1,000 con K = 15 e 45: ogni positivo previsto è davvero tale) ma la recall crolla (0,515, 0,424, 0,273): con K = 45 il modello trova meno di un positivo su tre. Il compromesso è la soglia di decisione, già vista, nascosta: per il voto di maggioranza il modello dichiara positivo se più della metà dei K vicini lo è, ma si può cambiare con predict_proba (la frazione di vicini positivi) e una soglia più bassa, per esempio 0,2. Un altro rimedio è bilanciare il training (oversampling della classe rara, con attenzione a non contaminare la validazione). Il messaggio è quello di il processo di un progetto di ML: con classi sbilanciate l'accuratezza mente, e un K scelto per massimizzarla porta il modello verso il «non trovare mai la classe rara».

Tre prove da fare

Esercizio 1. Sul problema sbilanciato usa predict_proba con K = 15 e una soglia 0,2 al posto della maggioranza: come cambiano recall e precision? Esercizio 2. Aggiungi a Wine dieci colonne di rumore (come nella sezione sulla maledizione della dimensionalità) e ripeti il confronto tra metriche: Manhattan resiste meglio dell'euclidea? Esercizio 3. Per la regressione, prova weights="distance" con K = 1 e K = 5: perché con K = 1 non cambia nulla?

Per allenarti sul dominio dei suoli agricoli dell'esercizio 1 c'è uno scheletro di esercizi in Python con tre parti da completare: le metriche di Minkowski con i pareggi, la quota di volume sul bordo di un ipercubo e il coefficiente di variazione delle distanze confrontato con una verifica Monte Carlo. Finché i punti da completare sono vuoti, stampa quali esercizi mancano.

Che cosa sai fare adesso

Sai scrivere KNN in NumPy e riconoscere quando la sua accuratezza è un artefatto di scala o di valutazione sul training. Sai misurare la concentrazione delle distanze e l'effetto delle colonne inutili, sai scegliere K e metrica con una validazione ripetuta, e sai dire quando un indice spaziale aiuta e quando è più lento della forza bruta. Nella lezione successiva, gli alberi decisionali, il modello diventa una sequenza di domande sì/no.

Fonti

Lezione precedente del percorso: Support Vector Machine: il margine massimo e il trucco del kernel. Nella stessa serie rimandano a questa lezione anche: Clustering: K-Means e DBSCAN senza etichette.