Che cos'è l'algoritmo k-nearest neighbors (KNN)?

Sebbene l'algoritmo KNN possa essere utilizzato sia per problemi di regressione che di classificazione, solitamente viene usato come algoritmo di classificazione, partendo dal presupposto che punti simili possano essere trovati vicini l'uno all'altro.

Per i problemi di classificazione, un'etichetta di classe viene assegnata in base a un voto di maggioranza, ovvero viene utilizzata l'etichetta più frequentemente rappresentata in un determinato punto di dati. Sebbene tecnicamente questo sia considerato un “voto di pluralità”, negli scritti viene più comunemente utilizzato il termine “voto di maggioranza”. La distinzione tra queste terminologie è che il "voto di maggioranza" richiede tecnicamente una maggioranza superiore al 50%, il che funziona principalmente quando ci sono solo due categorie. Quando si hanno più classi, ad esempio quattro categorie, non è necessario il 50% dei voti per trarre una conclusione su una classe, bensì si può assegnare un'etichetta di classe con un voto superiore al 25%. L'Università del Wisconsin-Madison riassume bene questo aspetto con un esempio che si può trovare qui.

I problemi di regressione utilizzano un concetto simile a quello della classificazione, ma in questo caso viene presa in considerazione la media dei k vicini più prossimi per fare una previsione su una classificazione. La distinzione principale è che la classificazione viene utilizzata per i valori discreti, mentre la regressione viene utilizzata per quelli continui. Tuttavia, prima di poter effettuare una classificazione, è necessario definire la distanza. La distanza euclidea, che approfondiremo più avanti, è quella più comunemente utilizzata.

Vale la pena notare che l'algoritmo KNN fa anche parte di una famiglia di modelli di “apprendimento pigro”, ovvero memorizza solo un set di dati di addestramento anziché sottoporsi a una fase di addestramento. Ciò significa anche che tutti i calcoli vengono eseguiti quando si effettuano una classificazione o una previsione. Poiché si affida fortemente alla memoria per memorizzare tutti i dati di addestramento, viene anche definito un un metodo di apprendimento basato sull'istanza o sulla memoria.

A Evelyn Fix e Joseph Hodges si deve l'idea iniziale del modello KNN in questo articolo del 1951, mentre Thomas Cover espande il concetto nella sua ricerca, “Nearest Neighbor Pattern Classification.” Anche se non è più popolare come un tempo, rimane tuttora uno dei primi algoritmi che si apprendono nel campo della data science grazie alla sua semplicità e accuratezza. Tuttavia, via via che un set di dati cresce, il KNN diventa sempre più inefficiente, compromettendo le prestazioni complessive del modello. È comunemente impiegato per sistemi di raccomandazione semplici, riconoscimento di modelli, estrazione di dati, previsioni sui mercati finanziari, rilevamento delle intrusioni e molto altro.

Ricapitolando, l'obiettivo dell'algoritmo k-nearest neighbor è identificare i vicini più prossimi di un dato punto di query, in modo da poter assegnare un'etichetta di classe a quel punto. Per fare ciò, il KNN ha alcuni requisiti:

Per determinare quali punti di dati sono più vicini a un determinato punto di query, è necessario calcolare la distanza tra il punto di query e gli altri punti di dati. Queste metriche di distanza consentono di formare i confini decisionali, che partizionano i punti di query in aree diverse. I confini decisionali vengono comunemente visualizzati con i diagrammi di Voronoi.

Sebbene sia possibile scegliere tra diverse misure di distanza, in questo articolo verranno trattate solo le seguenti:

Distanza euclidea (p=2): è la misura di distanza più comunemente utilizzata ed è limitata ai vettori a valore reale. Utilizzando la seguente formula, misura una linea retta tra il punto di interrogazione e l'altro punto da misurare.

Distanza di Manhattan (p=1): si tratta di un'altra metrica di distanza molto diffusa, che misura il valore assoluto tra due punti. Viene anche chiamata geometria del taxi o distanza di isolato poiché viene comunemente visualizzata con una griglia, che illustra come si potrebbe navigare da un indirizzo all'altro attraverso le strade della città.

Distanza di Minkowski: questa misura di distanza è la forma generalizzata delle metriche di distanza Euclidea e Manhattan. Il parametro p nella formula sottostante consente la creazione di altre metriche di distanza. La distanza euclidea è rappresentata da questa formula quando p è uguale a due, e la distanza di Manhattan è indicata con p uguale a uno.

Distanza di Hamming: questa tecnica viene utilizzata in genere con vettori booleani o stringhe per identificare i punti in cui i vettori non corrispondono. Per questo motivo, è stata anche definita metrica di sovrapposizione. Può essere rappresentata con la seguente formula:

Ad esempio, se si avessero le seguenti stringhe, la distanza di Hamming sarebbe pari a 2, poiché solo due dei valori differiscono.

Il valore k nell'algoritmo k-NN definisce il numero di vicini che verranno controllati per determinare la classificazione di un punto di query specifico. Ad esempio, se k=1, l'istanza verrà assegnata alla stessa classe del suo singolo vicino più prossimo.

La definizione di k può essere un atto di equilibrio, poiché valori diversi possono portare a un overfitting o a un underfitting. Valori bassi di k possono avere un'alta varianza, ma un basso bias, mentre valori più alti di k possono portare a un alto bias e a una varianza più bassa. La scelta di k dipenderà in larga misura dai dati di input, poiché i dati con un maggior numero di outlier o di rumore avranno probabilmente un rendimento migliore con valori di k più elevati. In generale, è consigliabile avere un numero dispari per k, per evitare errori di classificazione, e le tattiche di convalida incrociata possono aiutare a scegliere il k ottimale per il proprio set di dati.

Per approfondire ulteriormente questo tema, si consiglia di studiare l'algoritmo k-NN utilizzando Python e scikit-learn (noto anche come sklearn). Il nostro tutorial in Watson Studio aiuta a imparare la sintassi di base di questa libreria, che contiene anche altre librerie molto utilizzate, come NumPy, panda e Matplotlib. Il seguente codice è un esempio di come si possa creare e prevedere con un modello KNN:

L'algoritmo k-NN è stato utilizzato in diverse applicazioni, soprattutto nell'ambito della classificazione. Alcuni di questi casi d'uso includono:

• Pre-elaborazione dei dati: i set di dati presentano spesso valori mancanti, ma l'algoritmo KNN può stimare tali valori in un processo noto come imputazione dei dati mancanti.
  
  
• Motori di raccomandazione: utilizzando i dati clickstream dei siti web, l'algoritmo KNN è stato utilizzato per fornire agli utenti raccomandazioni automatiche su ulteriori contenuti. Questa ricerca mostra che un utente viene assegnato a un particolare gruppo e, in base al comportamento dell'utente di quel gruppo, gli viene fornita una raccomandazione. Tuttavia, dati i problemi di scalabilità con il KNN, questo approccio potrebbe non essere ottimale per set di dati più grandi.
  
  
• Finanza: è stato utilizzato anche in diversi casi d'uso in ambito finanziario ed economico. Ad esempio, uno studio mostra come l'utilizzo del KNN sui dati di credito possa aiutare le banche a valutare il rischio di un prestito a un'organizzazione o a un individuo. Viene utilizzato per determinare l'affidabilità creditizia di chi richiede un prestito. Un'altra pubblicazione ne evidenzia l'utilizzo nelle previsioni del mercato azionario, nei tassi di cambio, nel trading di futures e nelle analisi sul riciclaggio di denaro.
  
  
• Servizi sanitari: il KNN ha trovato applicazione anche nel settore sanitario, con previsioni sul rischio di infarto e di tumore alla prostata. L'algoritmo funziona calcolando le espressioni geniche più probabili.
  
  
• Riconoscimento dei modelli: il KNN ha anche contribuito all'identificazione di modelli, ad esempio nella classificazione di testi e cifre. Questo si è dimostrato particolarmente utile per identificare i numeri scritti a mano che si potrebbero trovare su moduli o buste.

Proprio come qualsiasi algoritmo di apprendimento automatico, anche il k-NN ha i suoi punti di forza e di debolezza. A seconda del progetto e dell'applicazione, può essere o meno la scelta giusta.

• Facile da implementare: data la semplicità e l'accuratezza dell'algoritmo, è uno dei primi classificatori che un nuovo data scientist apprenderà.
  
• Facilmente adattabile: via via che vengono aggiunti nuovi campioni di addestramento, l'algoritmo si adatta per tenere conto di tutti i nuovi dati, poiché tutti i dati di addestramento vengono memorizzati.
  
  
• Pochi iper-parametri: il KNN richiede solo un valore k e una metrica di distanza, che è bassa rispetto ad altri algoritmi di machine learning.

• Poco scalabile: poiché il KNN è un algoritmo pigro, occupa più memoria e data storage rispetto ad altri classificatori. Ciò può risultare costoso in termini di tempo e denaro. Una maggiore quantità di memoria e di storage fa aumentare le spese aziendali e l'elaborazione di un maggior numero di dati può richiedere più tempo. Sebbene siano state create diverse strutture di dati, come Ball-Tree, per affrontare le inefficienze computazionali, un classificatore diverso può essere l'ideale a seconda della problematica aziendale.
  
  
• Riduzione della dimensionalità: l'algoritmo KNN tende a essere soggetto alla riduzione della dimensionalità, il che significa che non funziona bene con gli input di dati ad alta dimensionalità. Questo fenomeno viene talvolta definito anche "fenomeno del picco", per cui dopo che l'algoritmo ha raggiunto il numero ottimale di caratteristiche, l'aggiunta di altre caratteristiche aumenta la quantità di errori di classificazione, soprattutto quando la dimensione del campione è minore.
  
  
• Incline all'overfitting: a causa della riduzione della dimensionalità, il KNN è anche più incline all'overfitting. Sebbene vengano utilizzate tecniche di selezione delle caratteristiche e di riduzione della dimensionalità per evitare che ciò accada, il valore di k può anche avere un impatto sul comportamento del modello. I valori più bassi di k possono adattarsi eccessivamente ai dati, mentre i valori più alti di k tendono a "smussare" i valori di predizione, poiché i valori vengono mediati su un'area più ampia (neighborhood). Tuttavia, se il valore di k è troppo alto, può causare l'underfitting dei dati.