K-Nearest Neighbors (KNN)

L'algoritmo dei k vicini più prossimi (KNN) è un algoritmo di apprendimento supervisionato che prevede l'etichetta di un nuovo esempio in base ai k esempi etichettati più vicini: per la classificazione usa il voto di maggioranza tra i vicini, mentre per la regressione ne calcola la media. KNN è non parametrico e «pigro»: non apprende pesi, si limita a memorizzare i dati di training ed esegue tutte le operazioni quando viene richiesta una previsione. Evelyn Fix e Joseph Hodges introdussero il metodo nel 1951 e, nel 1967, Thomas Cover e Peter Hart dimostrarono che, con dati illimitati, la regola del singolo vicino più prossimo ha un tasso di errore al massimo doppio rispetto al miglior classificatore possibile. La stessa ricerca dei vicini più prossimi viene oggi eseguita su larga scala nei database vettoriali e nei sistemi di recupero delle immagini che confrontano gli embedding delle reti neurali.

Come KNN esegue una previsione#

Per ogni punto di query, KNN esegue tre passaggi:

1. Misura la distanza: calcola la distanza tra la query e ogni esempio memorizzato. La distanza euclidea è quella predefinita; le distanze di Manhattan e Minkowski sono alternative comuni, mentre la similarità coseno è lo standard per gli embedding, nei quali il significato di un vettore è determinato dalla sua direzione.
2. Seleziona i vicini: mantiene i k esempi con le distanze minori.
3. Combina le etichette: nella classificazione sceglie la classe più frequente tra i vicini, mentre nella regressione calcola la media dei loro valori. Con la ponderazione in base alla distanza (weights="distance" in scikit-learn), i vicini più prossimi hanno un peso maggiore.

Ogni caratteristica contribuisce alla distanza, quindi quelle con valori su scale più ampie prevalgono: il reddito in dollari avrebbe un peso molto maggiore dell'età in anni. Per questo le pipeline KNN standardizzano prima le caratteristiche oppure confrontano gli embedding prodotti da un modello di estrazione delle caratteristiche, in modo che ogni dimensione contribuisca su una scala comparabile.

Scelta di k#

Il valore di k determina il compromesso tra overfitting e underfitting. Con k = 1, ogni punto di training, compresi quelli rumorosi o etichettati in modo errato, si appropria di una propria regione e il confine decisionale diventa frastagliato. Con un valore di k molto grande, ogni voto arriva da molto lontano dalla query e sfuma i confini reali tra le classi. Per due classi, un valore dispari di k evita i pareggi; la convalida incrociata è il metodo standard per scegliere k. Nel rumoroso dataset two-moons di scikit-learn, il compromesso emerge da tre valori:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

Con k = 1, il classificatore memorizza i punti di training e ottiene un punteggio di 1.00 su questi punti e di 0.83 sui punti di test. Con k = 15 ottiene 0.90 e 0.89, il miglior risultato di test dei tre; k = 300, quasi la metà dei 700 punti di training, rende il confine così uniforme che entrambi i punteggi scendono a 0.84 e 0.81.

Velocizzare la ricerca dei vicini#

Una ricerca a forza bruta confronta la query con tutti gli n punti memorizzati in d dimensioni, quindi il costo di ogni previsione è proporzionale a n × d operazioni e la memoria necessaria cresce con il dataset. Le strutture di partizionamento dello spazio, come gli alberi k-d e gli alberi ball, saltano la maggior parte dei confronti in poche dimensioni; algorithm="auto" di scikit-learn sceglie tra forza bruta, albero k-d e albero ball. In molte dimensioni, la maledizione della dimensionalità fa sì che le distanze tra i punti siano quasi uguali, la potatura degli alberi smette di essere efficace e i sistemi di grandi dimensioni passano a indici approssimati dei vicini più prossimi (ANN), come i grafi HNSW e gli indici inverted-file (IVF) con quantizzazione del prodotto, implementati in librerie come FAISS. Questi indici restituiscono la maggior parte dei veri vicini più prossimi confrontando la query con una piccola parte dei vettori memorizzati:

KNN e metodi correlati#

• Clustering k-means: algoritmo non supervisionato che raggruppa punti senza etichetta in k gruppi attorno a centroidi appresi. La lettera in comune è una coincidenza: in k-means, k indica il numero di gruppi.
• Ricerca vettoriale: forma di recupero della stessa operazione: restituisce gli elementi memorizzati più vicini a un embedding di query, di solito tramite un indice approssimato, e l'applicazione usa direttamente questi elementi.
• Macchine a vettori di supporto e regressione logistica: modelli parametrici che apprendono un confine decisionale durante il training, perciò il costo della previsione rimane costante all'aumentare del set di training.

Applicazioni nel mondo reale#

• Sistemi di raccomandazione: il filtraggio collaborativo basato sugli elementi consiglia prodotti i cui vettori di valutazioni o acquisti sono più vicini a quelli degli elementi già apprezzati dall'utente.
• Rilevamento delle anomalie: la distanza di un punto dal suo k-esimo vicino più prossimo funge da punteggio di anomalia, mettendo in evidenza le transazioni o le letture dei sensori lontane da ogni esempio normale.
• Imputazione dei valori mancanti: KNNImputer di scikit-learn riempie ogni lacuna con la media di quella caratteristica nelle k righe più simili.
• Recupero delle immagini e re-identificazione: i sistemi confrontano l'embedding di un'immagine con una galleria per trovare lo stesso prodotto, volto o persona ripresi da un'altra telecamera. La soluzione Ultralytics per la ricerca per similarità genera gli embedding di una cartella di immagini con CLIP di OpenAI, calcola il punteggio di ogni immagine indicizzata rispetto a una query testuale come «auto rossa» usando la similarità coseno in una ricerca esatta a forza bruta e restituisce quelle più vicine, fino a un massimo di 30 per impostazione predefinita.