Che cos’è KNN (K-Nearest Neighbors)?

Che cos’è K-Nearest Neighbors (KNN)?

K-Nearest Neighbors è una tecnica di apprendimento automatico e un algoritmo che può essere utilizzato per entrambi i compiti di regressione e classificazione. K-Nearest Neighbors esamina le etichette di un numero scelto di punti dati che circondano un punto dati di destinazione, al fine di effettuare una previsione sulla classe a cui appartiene il punto dati. K-Nearest Neighbors (KNN) è un algoritmo concettualmente semplice ma molto potente, e per queste ragioni, è uno degli algoritmi di apprendimento automatico più popolari. Facciamo un’analisi approfondita dell’algoritmo KNN e vediamo esattamente come funziona. Avere una buona comprensione di come funziona KNN ci permetterà di apprezzare i migliori e i peggiori casi d’uso per KNN.

Panoramica di K-Nearest Neighbors (KNN)

Foto: Antti Ajanki AnAj via Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Immaginiamo di visualizzare un set di dati su un piano 2D. Immaginiamo una serie di punti dati su un grafico, sparsi lungo il grafico in piccoli cluster. KNN esamina la distribuzione dei punti dati e, a seconda degli argomenti forniti al modello, separa i punti dati in gruppi. Questi gruppi vengono quindi assegnati a un’etichetta. La principale ipotesi che un modello KNN fa è che i punti dati/istanze che esistono in prossimità l’uno dell’altro sono molto simili, mentre se un punto dati è lontano da un altro gruppo, è dissimile da quei punti dati.

Un modello KNN calcola la somiglianza utilizzando la distanza tra due punti su un grafico. La maggiore la distanza tra i punti, la minore la somiglianza. Ci sono diversi modi per calcolare la distanza tra i punti, ma la metrica di distanza più comune è la distanza euclidea (la distanza tra due punti in linea retta).

KNN è un algoritmo di apprendimento supervisionato, il che significa che gli esempi nel set di dati devono avere etichette assegnate. Ci sono due altre cose importanti da sapere su KNN. In primo luogo, KNN è un algoritmo non parametrico. Ciò significa che non vengono fatte ipotesi sul set di dati quando si utilizza il modello. Invece, il modello viene costruito interamente dai dati forniti. In secondo luogo, non c’è una divisione del set di dati in set di addestramento e di test quando si utilizza KNN. KNN non fa generalizzazioni tra un set di addestramento e un set di test, quindi tutti i dati di addestramento vengono utilizzati anche quando il modello viene chiesto di effettuare previsioni.

Come funziona un algoritmo KNN

Un algoritmo KNN passa attraverso tre fasi principali mentre viene eseguito:

1. Impostazione di K sul numero di vicini scelto.
2. Calcolo della distanza tra un esempio/test fornito e gli esempi del set di dati.
3. Ordinamento delle distanze calcolate.
4. Ottenimento delle etichette dei primi K elementi.
5. Ritorno di una previsione sull’esempio di test.

Nel primo passaggio, K viene scelto dall’utente e indica all’algoritmo quanti vicini (quanti punti dati circostanti) considerare quando si rende un giudizio sul gruppo a cui appartiene l’esempio di destinazione. Nel secondo passaggio, si noti che il modello controlla la distanza tra l’esempio di destinazione e ogni esempio nel set di dati. Le distanze vengono quindi aggiunte a una lista e ordinate. Successivamente, la lista ordinata viene controllata e le etichette degli elementi superiori K vengono restituite. In altre parole, se K è impostato su 5, il modello controlla le etichette dei 5 punti dati più vicini all’esempio di destinazione. Quando si rende una previsione sull’esempio di destinazione, è importante se il compito è una regressione o classificazione. Per un compito di regressione, viene utilizzata la media delle etichette superiori K, mentre nel caso della classificazione viene utilizzata la modalità delle etichette superiori K.

Le esatte operazioni matematiche utilizzate per eseguire KNN differiscono a seconda della metrica di distanza scelta. Se si desidera saperne di più su come vengono calcolate le metriche, è possibile leggere alcune delle metriche di distanza più comuni, come Euclidean, Manhattan e Minkowski.

Perché il valore di K è importante

La principale limitazione dell’utilizzo di KNN è che un valore improprio di K (il numero sbagliato di vicini da considerare) potrebbe essere scelto. Se questo accade, le previsioni restituite potrebbero essere sostanzialmente diverse. È molto importante che, quando si utilizza un algoritmo KNN, venga scelto il valore appropriato per K. Si desidera scegliere un valore per K che massimizzi la capacità del modello di effettuare previsioni su dati non visti mentre riduce il numero di errori che commette.

Foto: Agor153 via Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

I valori più bassi di K significano che le previsioni rese da KNN sono meno stabili e affidabili. Per capire perché, consideriamo un caso in cui abbiamo 7 vicini intorno a un punto dati di destinazione. Supponiamo che il modello KNN stia lavorando con un valore K di 2 (gli stiamo chiedendo di considerare i due vicini più vicini per effettuare una previsione). Se la maggior parte dei vicini (cinque su sette) appartengono alla classe Blu, ma i due vicini più vicini sono Rossi, il modello predirà che l’esempio di destinazione sia Rosso. Nonostante la previsione del modello, in un tale scenario Blu sarebbe una previsione migliore.

Se è così, perché non scegliere semplicemente il valore K più alto possibile? Ciò è perché dire al modello di considerare troppi vicini ridurrà anche l’accuratezza. Man mano che il raggio che il modello KNN considera aumenta, inizierà a considerare punti dati che sono più vicini ad altri gruppi che al punto dati di destinazione e si verificheranno errori di classificazione. Ad esempio, anche se il punto inizialmente scelto era in una delle regioni rosse sopra, se K è impostato troppo alto, il modello raggiungerà altri punti per considerarli. Quando si utilizza un modello KNN, vengono provati diversi valori di K per vedere quale valore dà al modello le migliori prestazioni.

Vantaggi e svantaggi di KNN

Esaminiamo alcuni dei vantaggi e svantaggi del modello KNN.

Vantaggi:

KNN può essere utilizzato per entrambi i compiti di regressione e classificazione, a differenza di altri algoritmi di apprendimento supervisionato.

KNN è molto preciso e semplice da utilizzare. È facile da interpretare, capire e implementare.

KNN non fa ipotesi sui dati, il che significa che può essere utilizzato per una vasta gamma di problemi.

Svantaggi:

KNN memorizza la maggior parte o tutti i dati, il che significa che il modello richiede molta memoria e il suo costo computazionale è elevato. I grandi set di dati possono anche causare ritardi nelle previsioni.

KNN si rivela molto sensibile alla scala del set di dati e può essere facilmente influenzato da caratteristiche irrilevanti rispetto ad altri modelli.

Riepilogo di K-Nearest Neighbors (KNN)

K-Nearest Neighbors è uno degli algoritmi di apprendimento automatico più semplici. Nonostante la sua semplicità, KNN è anche un algoritmo potente che fornisce un’accuratezza abbastanza alta nella maggior parte dei problemi. Quando si utilizza KNN, è importante sperimentare con diversi valori di K per trovare il numero che fornisce l’accuratezza più alta.