Algoritmo K-Nearest Neighbors (KNN)

Già diversi studi sono stati eseguiti, ad esempio, per decidere se effettuare la concessione del prestito da parte di istituti creditizi presso clienti, oppure, per prevedere il rating di credito di un nuovo cliente, senza dover eseguire tutti i calcoli; o ancora, nelle scienze politiche per classificare se un potenziale elettore “voterà” o “non voterà” durante le prossime elezioni.

Altri esempi avanzati includono il rilevamento della grafia (come l’OCR), il riconoscimento dell’immagine e persino il riconoscimento video.

Vista la sua diffusione nel machine learning, vediamo che cos’è il K-Nearest Neighbors, come funziona e un esempio di applicazione.

Cos’è il K-Nearest Neighbors?

KNN è un algoritmo di apprendimento supervisionato, il cui scopo è quello di predire una nuova istanza conoscendo i data points che sono separati in diverse classi.

Per capire meglio l’algoritmo, ipotizziamo di dover predire a quale classe tra frutta, verdura e grano appartiene la patata dolce (l’esempio è stato tratto dal seguente articolo).

Dentro ad ogni classe vengono associati dei data points o istanze, il cui insieme definisce il set di dati. Ad esempio possiamo avere:

• mela, uva, kiwi, banana, pera dentro la classe frutta;
• lattuga, carote, sedano, fagiolo verde dentro la classe verdura;
• mais e farina nella classe grano.

Sappiamo per esperienza che, in generale, i frutti sono più dolci delle verdure, mentre i cereali non sono né croccanti né dolci. Pertanto possiamo supporre di visualizzare suddette classi su un asse cartesiano dove l’asse delle ordinate rappresenta quanto è dolce un frutto od ortaggio mentre l’asse delle ascisse rappresenta quanto tale frutto od ortaggio è croccante.

Dolce e croccante rappresentano le caratteristiche del problema (si noti che se ne potrebbero usare anche di più di due).

In questo esempio scegliamo quattro tipi di cibo più vicini: mela, fagiolo verde, lattuga e mais. Poiché la classe verdura ha più “voti” (2 contro 1 per la classe grano e 1 per la classe frutta), e poiché vince la classe che ottiene il maggior numero di voti, la patata dolce viene assegnata alla classe verdure.

Questo semplice esempio mostra la logica di ragionamento che sta dietro l’algoritmo K-Nearest Neighbors. Il suo funzionamento si basa sulla somiglianza delle caratteristiche: più un’istanza è vicina a un data point, più il knn li considererà simili.

Solitamente la somiglianza viene calcolata tramite la distanza euclidea (o un qualche altro tipo di distanza a seconda del problema in esame). Minore sarà la distanza e maggiore sarà la somiglianza tra data point e l’istanza da prevedere.

Oltre alla distanza, l’algoritmo prevede di fissare un parametro k, scelto arbitrariamente, che identifica il numero di data points più vicini. L’algoritmo valuta le k minime distanze così ottenute. La classe che ottiene il maggior numero di queste distanze è scelta come previsione.

Il KNN è uno strumento non parametrico, ossia non fa alcuna ipotesi sulla distribuzione dei dati che analizza.

In altre parole, la struttura del modello è determinata dai dati ed è piuttosto utile, perché nel “mondo reale”, la maggior parte dei dati non obbedisce ai tipici assunti teorici fatti (come nei modelli di regressione lineare, per esempio).

Di conseguenza, KNN potrebbe e probabilmente dovrebbe essere una delle prime scelte per uno studio di classificazione quando c’è poca o nessuna conoscenza precedente sulla distribuzione dei dati.

In aggiunta, si può affermare che la fase di addestramento è piuttosto veloce. La mancanza di generalizzazione fa sì che KNN conservi tutti i dati di allenamento. Ciò significa che tutti i dati di addestramento (o la maggior parte di essi) sono necessari durante la fase di test.

Quando usare il KNN?

A seconda del problema da risolvere, si può valutare di utilizzare il KNN, considerando i seguenti 3 aspetti:

• Tipologia di problema: Il KNN può essere utilizzato sia per problemi predittivi di classificazione che di regressione.
  
  Nei problemi di classificazione, il KNN determina l’etichetta di classe prevista, valutando un tipo di distanza. Tra le più utilizzate, oltre alla distanza euclidea, si ha la distanza di Hamming, la distanza di Manhattan o la distanza Minkowsky (per maggiori informazioni si veda il seguente articolo).
  
  Dopo avere calcolato la distanza, viene restituita l’etichetta della classe di maggioranza dell’insieme delle istanze k selezionate.

  Nella regressione, invece, il KNN sceglie il valore medio dei valori dei vicini più prossimi come valore previsto.

• Tempo di calcolo: KNN può richiedere molta memoria o spazio per archiviare tutti i dati, ma esegue solo un calcolo (o impara) quando è necessaria una previsione (per questo motivo si dice che l’algoritmo è pigro). È inoltre possibile aggiornare e curare le istanze di allenamento nel tempo per mantenere accurate le previsioni.
  
  C’è comunque da dire che l’idea di distanza o vicinanza può scomporre in dimensioni molto elevate (molte variabili di input) che possono influire negativamente sulle prestazioni dell’algoritmo sul problema di interesse. Questo fatto viene chiamato la maledizione della dimensionalità (conosciuta meglio come curse of dimensionality).

• Potere predittivo: dipende dal parametro k scelto inizialmente.
  Quando k è piccolo, stiamo limitando la regione di una determinata previsione e costringendo il nostro classificatore ad essere “più cieco” rispetto alla distribuzione generale.
  
  Al contrario, un k grande riduce l’impatto della varianza causato da un errore casuale, ma corre il rischio di ignorare piccoli dettagli che potrebbero essere rilevanti.
  
  Alcuni autori suggeriscono di impostare k uguale alla radice quadrata del numero di osservazioni nel set di dati di addestramento (ciò è affermato nella seguente pubblicazione).

Come funziona?

Il funzionamento dell’algoritmo K-Nearest Neighbors può essere definito tramite i seguenti step:

1. Scegli un valore k con cui prevedere il nuovo data point;
2. Nel caso di grandezze non comparabili utilizza tecniche per rendere le misure confrontabili, come la normalizzazione. Altrimenti, nel caso di misure comparabili (metri e metri, Kg e kg, ecc.) passa allo step 3;
3. Calcola la distanza (ad esempio quella euclidea) tra la nuova istanza e i vari data points;
4. Ordina le distanze calcolate dalla più piccola alla più grande;
5. Scegli le prime K: nel caso si stia svolgendo un problema di regressione, si può restituire la media delle etichette K. Se si sta svolgendo un problema di classificazione, si sceglierà la classe che include più valori k trovati precedentemente.