K-Nearest Neighbors

K-NN (K-Nearest Neighbors) è un algoritmo di riconoscimento dei pattern basato sulla vicinanza dei dati. Se un oggetto A ha caratteristiche simili a un oggetto B, probabilmente A appartiene alla stessa classe (categoria) di B. E' usato nei problemi di classificazione.

Nota. L'algoritmo è molto semplice e la fase di addestramento non richiede troppe risorse. Tuttavia, non è sempre efficace nella classificazione.

Come funziona l'algoritmo K-NN

Si tratta di un algoritmo di apprendimento supervised ML perché necessita di un gruppo di esempi di training già classificati ( training set ).

Quando l'algoritmo analizza i nuovi dati (non classificati) li classifica in base alla distanza rispetto agli esempi del training set.

Per il calcolo della distanza si possono adottare diversi criteri: la distanza euclidea o la distanza Manhattan per i dati numerici, distanza di Hamming per le stringhe.

Esempio

Se le caratteristiche sono soltanto due, l'algoritmo prende in considerazione i K esempi di training più vicini all'esempio da classificare.

La classe più frequente nei K esempi più vicini determina la classificazione del nuovo esempio.

Esempio. In questo caso l'esempio da classificare (nero). Utilizzo il parametro K=3 per prendere i tre esempi di training più vicini. Sono tutti esempi di colore blu. Pertanto, anche il nuovo esempio è classificabile con il colore blu.

Nell'algoritmo K-NN la configurazione del parametro K è fondamentale.

• Se K è troppo piccolo, l'esempio è assegnato in base ai pochi esempi più vicini. La classificazione è influenzata dal rumore nei dati.
• Se K è troppo grande, l'esempio viene classificato nella categoria più numerosa nella popolazione. Inoltre, la complessità computazionale dell'algoritmo aumenta perché il calcolo della distanza è un'operazione molto onerosa in termini di risorse e tempo.

Nota. Se le classi sono due è consigliabile assegnare al parametro k un valore dispari per evitare di trovarsi in una situazione di parità.