K-Nearest Neighbors

L’algoritmo dei k-nearest neighbors (KNN) è un algoritmo di apprendimento supervisionato non parametrico utilizzato per compiti di classificazione e regressione nel machine learning. Si basa sul concetto di prossimità, assumendo che punti dati simili siano localizzati vicino tra loro. KNN è un algoritmo di apprendimento pigro, cioè non richiede una fase di addestramento e fa previsioni memorizzando l’intero dataset di addestramento e utilizzandolo per determinare la classe o il valore di nuovi punti dati. L’algoritmo predice il risultato per un punto dato di test identificando i ‘k’ punti di addestramento più vicini al dato di test e deduce l’output in base a questi vicini. Questo metodo è altamente intuitivo e imita strategie di percezione umana che si basano sul confronto di nuovi dati con esempi noti.

Come Funziona KNN

KNN opera identificando i ‘k’ punti dati più vicini a un determinato punto di query e usando questi vicini per fare una previsione.

• Nei compiti di classificazione, l’algoritmo assegna il punto di query alla classe più comune tra i suoi ‘k’ vicini più prossimi, noto come votazione di maggioranza. La votazione di maggioranza in KNN può essere intesa come “votazione di pluralità” quando si gestiscono più classi, dove il punto di query viene assegnato alla classe con il maggior numero di rappresentanti tra i vicini, anche se non costituisce una maggioranza assoluta.
• Nei compiti di regressione, predice il valore facendo la media dei valori dei ‘k’ vicini più prossimi.

I principi di prossimità e somiglianza, fondamentali per la percezione umana, sono anche centrali per il funzionamento di KNN, poiché si assume che punti dati vicini nello spazio delle caratteristiche siano più simili e quindi probabilmente avranno esiti simili.

Metriche di Distanza

Per determinare i vicini più prossimi, KNN utilizza diverse metriche di distanza, che sono fondamentali per le sue prestazioni:

• Distanza Euclidea: La distanza in linea retta tra due punti in uno spazio multidimensionale, comunemente utilizzata per variabili continue. È la metrica di distanza più comune per KNN ed è particolarmente utile quando i dati sono densi e continui.
• Distanza Manhattan: Nota anche come distanza “taxicab”, calcola la distanza sommando le differenze assolute tra le coordinate di due punti. È utile in scenari con percorsi a griglia dove i movimenti sono vincolati a direzioni ortogonali.
• Distanza Minkowski: Una forma generalizzata sia della distanza Euclidea che di quella Manhattan, parametrizzata da ‘p’. Se p=1 diventa la distanza Manhattan, se p=2 diventa la distanza Euclidea. Questa metrica di distanza offre flessibilità a seconda del valore di ‘p’ scelto.
• Distanza di Hamming: Utilizzata per dati categorici, conta il numero di bit diversi tra due vettori binari. È particolarmente utile nei problemi di classificazione binaria dove gli attributi hanno valori binari.

Scelta del Valore ‘k’ Ottimale

Il parametro ‘k’ in KNN rappresenta il numero di vicini da considerare. Scegliere il giusto ‘k’ è cruciale:

• Un ‘k’ piccolo può portare a overfitting, dove il modello è troppo sensibile al rumore nei dati di addestramento, cogliendo pattern spuri che non si generalizzano.
• Un ‘k’ grande può portare a underfitting, dove il modello diventa troppo generalizzato e ignora pattern importanti, portando a scarse prestazioni predittive.
• Tipicamente, ‘k’ viene scelto tramite cross-validation e dovrebbe essere un numero dispari per evitare pareggi nelle decisioni di classificazione. La scelta di ‘k’ può influenzare significativamente l’accuratezza del modello ed è spesso determinata empiricamente.

Vantaggi e Svantaggi

Vantaggi

• Semplice e Intuitivo: Facile da comprendere e implementare, quindi adatto ai principianti. La semplicità di KNN sta nel suo approccio diretto di confronto tra istanze di test ed esempi memorizzati.
• Nessuna Fase di Addestramento: KNN non richiede una fase esplicita di addestramento, in quanto fa previsioni utilizzando il dataset memorizzato. Questo significa che il modello può essere aggiornato semplicemente aggiungendo nuovi punti dati al dataset.
• Versatile: Può essere usato sia per classificazione che per regressione, e la sua applicazione è ampia in diversi domini. È utile anche per problemi di classificazione multi-etichetta.

Svantaggi

• Computazionalmente Intensivo: Poiché richiede di memorizzare e confrontare ogni nuovo punto dati con l’intero dataset, può essere lento e richiedere molte risorse, specialmente con grandi dataset. La complessità temporale di KNN è O(n), dove n è il numero di campioni di addestramento.
• Sensibile agli Outlier: La presenza di outlier può influenzare significativamente le previsioni, poiché questi punti anomali possono alterare i risultati, soprattutto quando ‘k’ è piccolo.
• Maledizione della Dimensionalità: In spazi ad alta dimensionalità, le prestazioni dell’algoritmo possono peggiorare poiché le distanze tra i punti dati diventano meno significative. All’aumentare della dimensionalità, il volume dello spazio cresce, rendendo i dati più sparsi. Questa scarsità rende difficile per KNN trovare vicini prossimi in modo efficace.

Casi d’Uso

KNN viene applicato in diversi ambiti grazie alla sua semplicità ed efficacia:

• Sistemi di Raccomandazione: Utilizzato per raccomandare prodotti o contenuti agli utenti in base alle preferenze di utenti simili. KNN può aiutare a identificare utenti o oggetti simili valutando la somiglianza delle caratteristiche.
• Riconoscimento di Pattern: Impiegato nel riconoscimento della scrittura a mano e in altri compiti di riconoscimento di pattern, dove può classificare immagini in base alla somiglianza dei valori dei pixel.
• Imputazione dei Dati: Utile per riempire valori mancanti nei dataset stimandoli in base a punti dati simili, mantenendo così l’integrità del dataset.
• Finanza e Sanità: Applicato nelle previsioni di borsa, valutazione del rischio e diagnosi mediche analizzando le somiglianze nei dati storici. In ambito sanitario, può prevedere diagnosi confrontando i sintomi con casi noti.

Implementazione in Python

KNN può essere implementato usando librerie come scikit-learn in Python. Ecco un esempio di base di utilizzo di KNN per la classificazione:

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

# Carica il dataset
iris = load_iris()
X, y = iris.data, iris.target

# Suddividi i dati in set di addestramento e test
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Inizializza il classificatore KNN con k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Allena il modello
knn.fit(X_train, y_train)

# Fai previsioni
y_pred = knn.predict(X_test)

# Valuta l'accuratezza
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-Nearest Neighbors (KNN) nella Ricerca Scientifica

K-Nearest Neighbors (KNN) è un algoritmo fondamentale utilizzato in vari settori come il recupero di informazioni multimediali, il data mining e il machine learning, soprattutto nel contesto di grandi dataset.

Articoli di Ricerca Rilevanti:

• “Approximate k-NN Graph Construction: a Generic Online Approach” di Wan-Lei Zhao et al.:
  Presenta un metodo efficace sia per la ricerca approssimata dei k-nearest neighbor che per la costruzione di grafi. L’articolo dimostra una soluzione dinamica e praticabile per la gestione di diversi livelli di scala e dimensione dei dati, supportando aggiornamenti online che non sono possibili in molti metodi esistenti. Leggi di più.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” di Magdalen Dobson e Guy Blelloch:
  Introduce algoritmi paralleli che combinano kd-tree e ordinamento Morton in una struttura zd-tree, ottimizzata per dati a bassa dimensionalità. Gli autori dimostrano che il loro approccio è più veloce rispetto agli algoritmi esistenti, ottenendo notevoli accelerazioni con l’elaborazione parallela. Lo zd-tree supporta in modo esclusivo aggiornamenti batch-dinamici paralleli, una novità nelle strutture dati per k-nearest neighbor. Leggi di più.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” di Sebastian J. Wetzel:
  Esplora un nuovo approccio alla regressione k-nearest neighbor utilizzando reti neurali gemelle. Questo metodo si concentra sulla previsione delle differenze tra obiettivi di regressione, portando a prestazioni migliori rispetto alle reti neurali tradizionali e alle tecniche di regressione k-nearest neighbor su dataset di piccole e medie dimensioni. Leggi di più.