Algoritmo k-NN

Algoritmo k-NN
5NN
Classe	P
Struttura dati	Albero binario (K-d tree), Ball tree
Caso peggiore temporalmente	$O(Nd)$
Caso ottimo temporalmente	$O(d\log N)$ (con kd-tree o ball tree)
Caso medio temporalmente	$O(Nd)$ (forza bruta)
Caso peggiore spazialmente	$O(Nd)$

Nell'ambito dell'apprendimento supervisionato e discipline affini, l'algoritmo k-nearest neighbors (traducibile come "algoritmo dei $k$ vicini più prossimi"), abbreviato in algoritmo k-NN, è un metodo non parametrico di classificazione o regressione che si basa direttamente sul dataset di addestramento e su una misura di similarità per decidere il valore di una variabile di output, rispettivamente categorica o continua. In entrambi i casi, per ogni nuovo esempio $\mathbf {x} ^{*}$su cui effettuare la predizione si trovano i $k$ esempi di addestramento ($k$ numero intero positivo) "più simili"/"vicini" nello spazio determinato dalle feature ossia le variabili di input utilizzate per descrivere gli esempi. L'output $y^{*}$ dipende dal problema da risolvere:

• Nella classificazione $k$-NN, l'output è l'etichetta di una classe. L'istanza $\mathbf {x} ^{*}$ viene classificata attraverso un voto di maggioranza, ossia l'istanza sarà assegnata alla classe corrispondente all'etichetta più comune tra i suoi $k$ vicini più prossimi (ossia a minore distanza).
• Nella regressione $k$-NN, l'output è il valore $y^{*}$ della variabile di output per $\mathbf {x} ^{*}$ calcolato come media dei valori dei $k$ vicini più prossimi.

Caratteristiche principali

È l'algoritmo più semplice fra quelli utilizzati nell'apprendimento automatico.

Il parametro k

Un'istanza è classificata in base alla maggioranza dei voti dei suoi $k$ vicini selezionati. Il parametro $k$ è un intero positivo tipicamente non molto grande. Se $k=1$, allora l'istanza viene assegnata alla classe del suo vicino. In caso di problema di classificazione binario, ossia in cui sono previste esclusivamente due classi, è opportuno scegliere $k$ dispari per evitare di ritrovarsi in situazioni di parità.

Questo metodo può essere utilizzato per la tecnica di regressione assegnando all'istanza la media dei valori dei suoi $k$ vicini selezionati.

Considerando solo i voti dei $k$ vicini c'è l'inconveniente dovuto alla predominanza delle classi con più esempi. In questo caso può risultare utile pesare i contributi dei vicini in modo da dare, nel calcolo della media, maggior importanza in base alla similarità rispetto all'istanza considerata.

Scelta del parametro k

La scelta di $k$ dipende dalle caratteristiche dei dati. Generalmente all'aumentare di $k$ si riduce il rumore che compromette la classificazione, ma il criterio di scelta per la classe diventa più labile. La scelta può esser presa attraverso tecniche euristiche, come ad esempio la convalida incrociata.

L'algoritmo

Fase di apprendimento

Lo spazio viene partizionato in regioni in base alle posizioni e alle caratteristiche delle istanze di addestramento. Questo partizionamento (e le strutture per l'ottimizzazione della ricerca ad esso collegate) può essere considerato come l'input per l'algoritmo, anche se esso non è esplicitamente richiesto dalle condizioni iniziali.

Calcolo della distanza

Ai fini del calcolo della similarità le istanze sono rappresentate attraverso vettori di posizione in uno spazio multidimensionale. Di solito viene usata la distanza euclidea, ma anche altri tipi di distanza sono ugualmente utilizzabili, ad esempio la distanza Manhattan, le Minkowski o la Mahalanobis. Nel caso in cui si debbano manipolare stringhe e non numeri si possono usare altre misure quali ad esempio la distanza di Hamming. L'algoritmo è sensibile alla "struttura locale" dei dati.

Fase di classificazione

Un punto (che rappresenta un'istanza) è assegnato alla classe $c\in \{1,\ldots ,C\}$ se questa è la più frequente fra i $k$ esempi più vicini all'istanza sotto esame, la vicinanza si misura in base alla distanza fra punti. I vicini sono presi da un insieme di addestramento supervisionato per cui è nota la classificazione corretta. Nel caso della regressione per il calcolo della media (classificazione) si usa il valore della proprietà considerata.

Esempio di utilizzo

Esempio di problema di classificazione risolto via k-NN

In figura è rappresentato un esempio di classificazione mediante $k$-NN. Il punto sotto osservazione è il pallino verde. Le classi sono due:

• quella dei triangolini rossi;
• quella dei quadratini blu.

Se $k=3$ (cioè vengono considerate le 3 istanze più vicine), allora il pallino verde viene inserito nella stessa classe dei triangolini rossi perché sono presenti 2 triangolini e 1 quadratino. Se $k=5$, allora viene inserito nella stessa classe dei quadratini blu perché sono presenti 3 quadratini e 2 triangolini.

Valutazione: vantaggi e svantaggi

Al tendere della quantità di dati all'infinito l'algoritmo non supera mai di due volte l'errore di Bayes (il minimo errore dovuto alla distribuzione dei dati). Per alcuni valori di $k$, con $k$ che cresce in funzione della mole di dati, l'algoritmo raggiunge l'errore di Bayes.

Prestazioni ottimali si raggiungono utilizzando alberi di ricerca ad hoc come k-d tree, ball tree e, in generale, metric tree.

Il calcolo delle distanze è computazionalmente oneroso e proporzionale alla taglia dell'insieme di dati sotto esame. Gli algoritmi proposti che migliorano questo inconveniente cercano principalmente di diminuire il numero di distanze da calcolare per la decisione. In alcuni casi si cerca di partizionare lo spazio vettoriale e si calcolano solo le distanze tra volumi dello spazio vettoriale.

Algoritmi simili

Di seguito sono elencati alcuni algoritmi della tipologia $k$-NN:

• Agglomerative Nearest-Neighbour;
• Finestre di Parzen;
• k-Most Similar Neighbour (k-MSN);
• Large Margin Nearest Neighbor;
• Linear scan
• Locality-sensitive hashing (LSH)
• Redundant Bit Vectors (RBV).

Variabili continue

L'algoritmo $k$-NN può essere utilizzato, con opportuni adattamenti, per stimare variabili continue. Questo tipo di implementazione utilizza una media pesata basata sull'inverso della distanza.

Bibliografia

• (EN) Belur V. Dasarathy (a cura di), Nearest neighbor (NN) norms: nn pattern classification techniques, IEEE Computer Society Press ; IEEE Computer Society Press Tutorial, 1991, ISBN 978-0-8186-8930-7.
• (EN) G. Shakhnarovish, T. Darrell, P. Indyk (a cura di), Nearest-neighbor methods in learning and vision: theory and practice, collana Neural information processing series, MIT Press, 2005, ISBN 978-0-262-19547-8.
• Trevor Hastie, Robert Tibshirani e Jerome Friedman, 13. Prototype Methods and Nearest-Neighbors, in The Elements of Statistical Learning, collana Springer Series in Statistics, Springer New York, 2009, DOI:10.1007/978-0-387-84858-7, ISBN 978-0-387-84857-0.

Collegamenti esterni

• Eda Kavlakoglu, Che cos'è l'algoritmo KNN?, su ibm.com, IBM. URL consultato l'8 aprile 2026.
• (EN) Bharani Kumar, KNN Classifier, su 360digitmg.com, 360DigiTMG, 17 luglio 2024. URL consultato l'8 aprile 2026.
• (EN) Paul Lammertsma, K-nearest neighbour algorithm in Visual Basic and Java, su paul.luminos.nl (archiviato dall'url originale il 29 settembre 2007).
• (EN) Roberto Paredes Palacios, CPW: Class and Prototype Weights learning, su dsic.upv.es (archiviato dall'url originale il 15 dicembre 2007).