L'algoritmo k-nearest neighbors, noto anche come KNN o k-NN, è un classificatore di apprendimento supervisionato non parametrico, che utilizza la prossimità per effettuare classificazioni o previsioni sul raggruppamento di un singolo punto dati. Sebbene possa essere utilizzato per problemi di regressione o classificazione, viene generalmente utilizzato come algoritmo di classificazione, basandosi sul presupposto che punti simili possono essere trovati l'uno vicino all'altro.

Per problemi di classificazione, un'etichetta di classe viene assegnata sulla base di un voto a maggioranza, ad es. viene utilizzata l'etichetta più frequentemente rappresentata attorno a un determinato punto dati. Sebbene questo sia tecnicamente considerato "voto pluralistico", il termine "voto a maggioranza" è più comunemente usato in letteratura. La distinzione tra queste terminologie è che il "voto a maggioranza" richiede tecnicamente una maggioranza superiore al 50%, che funziona principalmente quando ci sono solo due categorie. Quando hai di più classi, ad es. quattro categorie, non hai bisogno necessariamente del 50% dei voti per trarre una conclusione su una classe; puoi assegnare un'etichetta di classe con un voto superiore al 25%. La University of Wisconsin-Madison sintetizza bene quanto suddetto con un esempio qui (PDF, 1,2 MB) (link esterno a ibm.com). 

I problemi di regressione utilizzano un concetto simile al problema di classificazione, ma in questo caso viene presa la media dei k vicini più vicini per fare una previsione su una classificazione. La distinzione principale qui è che la classificazione viene utilizzata per i valori discreti, mentre la regressione viene utilizzata con quelli continui. Tuttavia, prima di poter effettuare una classificazione, è necessario definire la distanza. Distanza euclidea questa è anche un'altra metrica di distanza popolare, che misura il valore assoluto tra due punti.
Vale anche la pena notare che l'algoritmo KNN fa anche parte di una famiglia di modelli di "apprendimento pigro", il che significa che memorizza solo un set di dati di addestramento rispetto a una fase di addestramento. Ciò significa anche che tutto il calcolo avviene quando viene effettuata una classificazione o una previsione. Poiché fa ampiamente affidamento sulla memoria per archiviare tutti i suoi dati di addestramento, viene anche definito metodo di apprendimento basato su istanze o basato sulla memoria.
Le idee iniziali sul modello KNN sono attribuite a Evelyn Fix e Joseph Hodges in questo  articolo del 1951 (PDF, 1,1 MB) (link esterno a ibm.com) mentre Thomas Cover amplia il loro concetto nella sua ricerca (PDF 1 MB) (link esterno a ibm.com), “Nearest Neighbor Pattern Classification.” Anche se non è così popolare come una volta, è ancora uno dei primi algoritmi che si impara nella data science grazie alla sua semplicità ed accuratezza. Tuttavia, man mano che un set di dati cresce, KNN diventa sempre più inefficiente, compromettendo le prestazioni del modello. Viene comunemente utilizzato per semplici sistemi di raccomandazione, riconoscimento di modelli, data mining, previsioni dei mercati finanziari, rilevamento delle intrusioni e altro ancora. 

Per ricapitolare, l'obiettivo dell'algoritmo k-nearest neighbor è identificare i vicini più prossimi di un dato punto di query, in modo da poter assegnare un'etichetta di classe a quel punto. Per fare ciò, KNN ha alcuni requisiti:

Determina le tue metriche di distanza

Per determinare quali punti dati sono più vicini a una determinato punto di query, sarà necessario calcolare la distanza tra il punto di interrogazione e gli altri punti dati. Queste metriche di distanza aiutano a formare confini decisionali, che suddividono i punti di query in regioni diverse. Di solito vedrai i limiti delle decisioni visualizzati con i diagrammi di Voronoi.

Sebbene ci siano diverse misure di distanza tra cui puoi scegliere, questo articolo tratterà solo quanto segue:

Distanza euclidea (p=2):  questa è la misura della distanza più comunemente usata ed è limitata ai vettori con valori reali. Utilizzando la formula seguente, misura una linea retta tra il punto di query e l'altro punto che si sta misurando.

Distanza di Manhattan (p=1): questa è anche un'altra metrica di distanza popolare, che misura il valore assoluto tra due punti. Viene anche chiamata distanza del taxi o distanza del blocco cittadino poiché è comunemente visualizzata con una griglia, che illustra come si potrebbe andare da un indirizzo all'altro attraverso le strade della città.

Distanza di Minkowski: questa misura della distanza è la forma generalizzata delle metriche di distanza euclidea e di Manhattan. Il parametro, p, nella formula seguente, consente la creazione di altre metriche di distanza. La distanza Euclidea è rappresentata da questa formula quando p è uguale a due e la distanza di Manhattan è indicata con p uguale a uno.

Distanza di Hamming: questa tecnica viene utilizzata tipicamente con vettori booleani o stringa, identificando i punti in cui i vettori non corrispondono. Di conseguenza, è stata anche definita metrica di sovrapposizione. Questo può essere rappresentato con la seguente formula:

Ad esempio, se avessi le seguenti stringhe, la distanza di hamming sarebbe 2 poiché solo due dei valori differiscono.

Proprio come qualsiasi algoritmo di apprendimento automatico, k-NN ha i suoi punti di forza e di debolezza. A seconda del progetto e dell'applicazione, potrebbe essere o meno la scelta giusta.

- Facile da implementare: data la semplicità e l'accuratezza dell'algoritmo, è uno dei primi classificatori che un data scientist alle prime armi apprenderà.

- Si adatta facilmente: quando vengono aggiunti nuovi campioni di addestramento, l'algoritmo si adatta per tenere conto di eventuali nuovi dati poiché tutti i dati di addestramento vengono archiviati in memoria.

- Pochi iperparametri: KNN ha bisogno solo di un valore k e una metrica di distanza, il che è poco rispetto ad altri algoritmi di machine learning.

- Non ha una buona scalabilità: poiché KNN è un algoritmo pigro, occupa più memoria e spazio di storage dei dati rispetto ad altri classificatori. Questo può essere costoso sia dal punto di vista del tempo che del denaro. Più memoria e spazio di archiviazione aumenteranno le spese aziendali e l'elaborazione di più dati può richiedere più tempo. Sebbene diverse strutture di dati, come Ball-Tree, siano state create per affrontare le inefficienze computazionali, un classificatore diverso potrebbe essere ideale a seconda del problema di business.

- Maledizione della dimensionalità: l'algoritmo KNN tende a cadere vittima della maledizione della dimensionalità, il che significa che non funziona bene con input di dati ad alta dimensionalità. Questo è a volte indicato anche come il fenomeno del picco (PDF, 340 MB) (link esterno a ibm.com), dove dopo che l'algoritmo raggiunge l'ottimale numero di funzioni, le funzioni aggiuntive aumentano la quantità di errori di classificazione, soprattutto quando la dimensione del campione è inferiore.

- Propenso al sovradimensionamento dei dati: a causa della "maledizione della dimensionalità", KNN è anche più propenso al sovradimensionamento dei dati. Sebbene le tecniche di selezione delle caratteristiche e di riduzione della dimensionalità vengano sfruttate per evitare che ciò accada, il valore di k può anche influire sul comportamento del modello. Valori più bassi di k possono sovraalimentare i dati, mentre valori più alti di k tendono a "smussare" i valori di previsione poiché sta facendo la media dei valori su un'area o un neighborhood più grande. Tuttavia, se il valore di k è troppo alto, può essere inferiore ai dati.