
Uno degli algoritmi più conosciuti nel machine learning è il K-Nearest Neighbors (KNN) che, oltre alla sua semplicità, produce buoni risultati in un gran numero di domini.
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 (o la maggior parte) dei dati di addestramento 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:
- Scegli un valore k con cui prevedere il nuovo data point;
- 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;
- Calcola la distanza (ad esempio quella euclidea) tra la nuova istanza e i vari data points;
- Ordina le distanze calcolate dalla più piccola alla più grande;
- 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.
Esempio di KNN
Supponiamo di avere l’altezza, il peso e la taglia della maglietta di alcuni clienti e dobbiamo prevedere la taglia della t-shirt di un nuovo cliente. Di seguito sono riportati i dati di altezza, peso e dimensioni della maglietta.
Ipotizziamo:
- Di voler prevedere la taglia di una nostra cliente Martina, sapendo che essa pesa 58 kg ed è alta 160 cm;
- Di impostare k = 5.
Quindi l’algoritmo cerca i 5 clienti più vicini a Martina (nostra previsione). Se 4 di loro avevano “T-shirt medie” e 1 aveva “T-shirt L”, allora l’ipotesi migliore per il cliente è “T-shirt media”.
Avendo in questo caso due unità di misura differenti (peso in kg, e altezza in cm) occorre rappresentarle secondo un valore comune per evitare che una grandezza sia più rilevante dell’altra e quindi generi risultati ambigui.
Per fare questo e cioè per renderle comparabili è necessario ridimensionarle attraverso la seguente formula:
Xs = (X – media) / σ
Con σ deviazione standard e calcolabile nel seguente modo:
In Excel la formula per calcolare la dev. Standard per l’altezza è “=DEV.ST.C(A2:A19)”, ossia 4,32.
Quindi, ad esempio il primo valore può essere così trovato:
Altezza in cm (cella H2) = (158 – 164) / 4,32 = – 1,39
Calcolando con l’aiuto di Excel gli altri valori otteniamo il seguente risultato:
Ora possiamo procedere al calcolo della distanza euclidea, che ci permette di calcolare quali sono i punti più prossimi all’istanza da prevedere.
Mentre la formula della distanza euclidea si può così esprimere:
o tramite Excel ‘=RADQ()’
Procedendo al calcolo delle distanze euclidee dei vari data points possiamo ottenere:
Scegliendo i cinque valori più piccoli otteniamo:
Quindi a Martina, secondo le previsioni del modello e dei 5-k valori più vicini avrà bisogno di una taglia M (qua puoi vedere i calcoli proposti dal file Excel).
Come scegliamo il fattore K?
Abbiamo visto che una parte fondamentale dell’algoritmo k-Nearest Neighbors è la scelta di k. Nell’esempio proposto sopra, abbiamo utilizzato il valore 5 per k.
In questo caso, ogni nuovo data point è previsto dai 5 suoi vicini più prossimi nel set di allenamento. Tuttavia, k è un valore regolabile, possiamo impostarlo su qualsiasi valore compreso tra 1 e il numero di data points nel set di allenamento.
Come sceglierlo allora?
Tale compito è un aspetto cruciale per la buona riuscita della previsione. Tra i metodi più utilizzati troviamo il metodo della convalida incrociata o cross validation.
L’idea generale di questo metodo è quella di dividere il campione di dati in un numero k definito di sottocampioni o segmenti ad estrazione casuale, disgiunti, che serviranno come fase di allenamento (training). Si applica poi il modello KNN per fare previsioni sul segmento k-esimo (ad esempio, utilizzando i segmenti k-1 come esempi) e si valuta l’errore.
In pratica, ogni volta uno dei sottoinsiemi k viene usato come set di test, mentre gli altri sottoinsiemi k-1 sono messi insieme per formare un set di allenamento. Come si può vedere, ogni data point può trovarsi in un set di test esattamente una volta, e può trovarsi in un set di allenamento k-1 volte.
Alla fine della procedura, gli errori calcolati vengono mediati per fornire una misura della stabilità del modello (ossia quanto bene il modello prevede nuove istanze).
I passaggi precedenti vengono quindi ripetuti per vari k e il valore che raggiunge l’errore più basso (o la massima precisione di classificazione) viene così selezionato come valore ottimale per k (ottimale in un senso di convalida incrociata).
Si noti come la convalida incrociata sia dispendiosa dal punto di vista computazionale e si dovrebbe essere pronti a far funzionare l’algoritmo per un po’ di tempo, specialmente quando la dimensione del campione di esempi è ampia.
In alternativa, puoi specificare un k ragionevole qualora si conosca il problema di analisi (ad esempio, dalle precedenti analisi KNN che si è potuto condurre su dati simili).