KNN per la regressione e i suoi limiti di scalabilità

KNN non è limitato alla classificazione: può anche prevedere valori continui. Nella regressione KNN, la previsione per un nuovo punto è la media dei valori target dei suoi k vicini più prossimi. Ad esempio, per prevedere il prezzo di una casa, KNN individua le k case più simili nel set di addestramento e calcola la media dei loro prezzi. In questo modo si ottiene un modello di regressione locale non parametrico, capace di catturare schemi complessi senza assumere una forma funzionale specifica per la relazione tra caratteristiche e target.

KNeighborsRegressor di scikit-learn implementa KNN per target continui con la stessa API del classificatore. Supporta gli stessi parametri: n_neighbors, metric, weights e algorithm. La regressione pesata sulla distanza (weights='distance') è spesso vantaggiosa: i vicini più prossimi contribuiscono maggiormente al valore previsto rispetto a quelli più lontani, il che è particolarmente utile ai margini della distribuzione dei dati di addestramento, dove un vicino distante potrebbe introdurre un bias significativo.

La stessa logica bias-varianza si applica alla regressione KNN: k piccolo = varianza elevata, previsioni irregolari; k grande = bias elevato, previsioni eccessivamente smussate. Può visualizzare questo effetto tracciando la funzione prevista su un intervallo di input unidimensionale. Con k=1, la linea delle previsioni raggiunge il valore esatto di ciascun punto di addestramento. All'aumentare di k, la linea diventa più uniforme. Il valore ottimale di k minimizza l'RMSE (o MAE) calcolato con la convalida incrociata. Nella regressione non esiste il problema della risoluzione dei pareggi, quindi anche i valori pari di k vanno bene.

A differenza dei modelli parametrici addestrati (regressione lineare, reti neurali), che effettuano previsioni in tempo O(d) usando i parametri memorizzati, KNN deve analizzare tutti i punti di addestramento al momento dell'inferenza. Ogni previsione richiede il calcolo delle distanze rispetto a ogni campione di addestramento: un'operazione O(N * d). Per N=1,000,000 e d=100, si tratta di 100 milioni di operazioni per previsione. Se ogni operazione richiede 1 millisecondo, una singola previsione richiede 100 secondi. Di conseguenza, il KNN ingenuo è del tutto inadatto ai sistemi di produzione in tempo reale con set di addestramento di grandi dimensioni.

Scikit-learn offre due strutture di indicizzazione spaziale per velocizzare la ricerca dei vicini. Un KD-Tree suddivide ricorsivamente lo spazio delle caratteristiche lungo la dimensione con la varianza maggiore, consentendo ricerche dei vicini in O(log N) per dati a bassa dimensionalità. Un Ball Tree suddivide i dati in ipersfere annidate, risultando più efficiente per dati ad alta dimensionalità o con metriche non euclidee. Entrambe riducono significativamente il tempo medio di previsione. Imposti il parametro algorithm di KNeighborsClassifier su 'kd_tree', 'ball_tree' o 'auto' (sceglie scikit-learn).

KNN deve conservare in memoria l'intero set di addestramento in ogni momento, perché le previsioni richiedono l'accesso ai campioni di addestramento. Per N=1 milione di campioni con d=100 caratteristiche float64, la sola matrice dei dati richiede 800 MB di RAM. Con N=10 milioni, sono 8 GB: una quantità eccessiva per molti ambienti di distribuzione. I modelli parametrici, come la regressione lineare o le reti neurali, comprimono N campioni in un numero fisso di parametri, risultando molto più efficienti in termini di memoria durante l'inferenza. Il costo in memoria di KNN è O(N * d), indipendentemente dalla complessità del problema.

Per i casi d'uso di produzione su larga scala, le librerie per la ricerca dei vicini più prossimi approssimati (ANN) riducono drasticamente il tempo di ricerca, al costo di non individuare occasionalmente il vero vicino più prossimo. FAISS (Facebook AI Similarity Search) può interrogare un miliardo di vettori in pochi millisecondi usando strutture di indicizzazione accelerate dalla GPU. Annoy (Spotify) costruisce una foresta di alberi a proiezione casuale per le ricerche approssimate. I grafi HNSW (Hierarchical Navigable Small World) consentono query in meno di un millisecondo. Queste librerie vengono usate nei sistemi di raccomandazione e nella ricerca semantica su scala di produzione.

KNN è pratico quando: N < 100,000, le previsioni vengono eseguite in batch (non in tempo reale) ed è necessaria l'interpretabilità (può mostrare gli esempi simili effettivi). KNN presenta difficoltà quando: N è molto grande, sono necessarie previsioni in tempo reale (latenza <100ms) oppure lo spazio delle caratteristiche è ad alta dimensionalità (>50 caratteristiche). Tra le alternative migliori per valori elevati di N figurano Random Forest e Gradient Boosting per i dati tabulari, e le reti neurali per immagini e testo. KNN rimane un solido modello di riferimento per i sistemi di raccomandazione e il rilevamento delle anomalie quando il dataset entra comodamente in memoria.

Confrontare KNN e la regressione lineare sullo stesso problema di regressione mette in evidenza il compromesso in termini di scalabilità. La regressione lineare viene addestrata in pochi secondi indipendentemente da N (addestramento O(N*d^2), ma previsione O(d)). L'addestramento di KNN è istantaneo (non richiede calcoli), ma la previsione scala con N. KNN è quindi un modello a calcolo differito: sostiene tutti i costi al momento della previsione. Per un'attività di previsione batch eseguita una sola volta su 100.000 righe, KNN può essere accettabile. Per un'API che gestisce 1000 richieste al secondo, la regressione lineare o una rete neurale è più veloce di diversi ordini di grandezza.

Anche quando KNN è troppo lento per essere usato direttamente in produzione, le distanze restituite possono fungere da caratteristiche informative per altri modelli. Ad esempio, calcolare la distanza media dai k vicini di addestramento più prossimi per ogni punto di test crea una singola caratteristica che misura quanto il punto sia insolito. I punti insoliti (lontani dai propri vicini) sono potenziali anomalie. Questo approccio, che usa KNN come estrattore di caratteristiche anziché come predittore finale, consente di sfruttare le informazioni sui vicini più prossimi all'interno di modelli ensemble veloci.

Per rendere KNN pratico sui dati ad alta dimensionalità, applichi PCA prima di KNeighborsRegressor, così da ridurre la dimensionalità preservando la maggior parte della varianza. In questo modo affronta simultaneamente due problemi: riduce il tempo di previsione (meno dimensioni = calcolo delle distanze più rapido) e attenua la maledizione della dimensionalità (le distanze diventano più significative nello spazio a dimensionalità ridotta). PCA + KNN all'interno di un'unica Pipeline mantiene la pre-elaborazione priva di data leakage durante la convalida incrociata.

In questa lezione ha imparato: come la regressione KNN prevede target continui calcolando la media dei valori dei vicini, il fondamentale costo di previsione O(N * d) che limita la scalabilità di KNN e come KD-Tree, Ball Tree e FAISS velocizzano la ricerca dei vicini per i dataset più grandi. Nella prossima lezione esploreremo gli alberi decisionali, un approccio fondamentalmente diverso che apprende regole esplicite attraverso il partizionamento ricorsivo dei dati.