Cos'è l'algoritmo k-nearest neighbors?

Scopri l'algoritmo k-nearest neighbors, uno dei classificatori di regressione e classificazione più popolari e più semplici utilizzati oggi nell'apprendimento automatico

Vista posteriore del codice di scrittura dello sviluppatore

Algoritmo K-Nearest Neighbors

L'algoritmo k-nearest neighbors, noto anche come KNN o k-NN, è un classificatore di apprendimento supervisionato non parametrico, che utilizza la prossimità per effettuare classificazioni o previsioni sul raggruppamento di un singolo punto dati. Sebbene possa essere utilizzato per problemi di regressione o classificazione, viene generalmente utilizzato come algoritmo di classificazione, basandosi sul presupposto che punti simili possono essere trovati l'uno vicino all'altro.


Per problemi di classificazione, un'etichetta di classe viene assegnata sulla base di un voto a maggioranza, ad es. viene utilizzata l'etichetta più frequentemente rappresentata attorno a un determinato punto dati. Sebbene questo sia tecnicamente considerato "voto pluralistico", il termine "voto a maggioranza" è più comunemente usato in letteratura. La distinzione tra queste terminologie è che il "voto a maggioranza" richiede tecnicamente una maggioranza superiore al 50%, che funziona principalmente quando ci sono solo due categorie. Quando hai di più classi, ad es. quattro categorie, non hai bisogno necessariamente del 50% dei voti per trarre una conclusione su una classe; puoi assegnare un'etichetta di classe con un voto superiore al 25%. La University of Wisconsin-Madison sintetizza bene quanto suddetto con un esempio qui (PDF, 1,2 MB) (link esterno a ibm.com). 

I problemi di regressione utilizzano un concetto simile al problema di classificazione, ma in questo caso viene presa la media dei k vicini più vicini per fare una previsione su una classificazione. La distinzione principale qui è che la classificazione viene utilizzata per i valori discreti, mentre la regressione viene utilizzata con quelli continui. Tuttavia, prima di poter effettuare una classificazione, è necessario definire la distanza. Distanza euclidea questa è anche un'altra metrica di distanza popolare, che misura il valore assoluto tra due punti.
Vale anche la pena notare che l'algoritmo KNN fa anche parte di una famiglia di modelli di "apprendimento pigro", il che significa che memorizza solo un set di dati di addestramento rispetto a una fase di addestramento. Ciò significa anche che tutto il calcolo avviene quando viene effettuata una classificazione o una previsione. Poiché fa ampiamente affidamento sulla memoria per archiviare tutti i suoi dati di addestramento, viene anche definito metodo di apprendimento basato su istanze o basato sulla memoria.
Le idee iniziali sul modello KNN sono attribuite a Evelyn Fix e Joseph Hodges in questo  articolo del 1951 (PDF, 1,1 MB) (link esterno a ibm.com) mentre Thomas Cover amplia il loro concetto nella sua ricerca (PDF 1 MB) (link esterno a ibm.com), “Nearest Neighbor Pattern Classification.” Anche se non è così popolare come una volta, è ancora uno dei primi algoritmi che si impara nella data science grazie alla sua semplicità ed accuratezza. Tuttavia, man mano che un set di dati cresce, KNN diventa sempre più inefficiente, compromettendo le prestazioni del modello. Viene comunemente utilizzato per semplici sistemi di raccomandazione, riconoscimento di modelli, data mining, previsioni dei mercati finanziari, rilevamento delle intrusioni e altro ancora. 


Calcola KNN: metriche di distanza

Per ricapitolare, 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ò, KNN ha alcuni requisiti:

Determina le tue metriche di distanza

Per determinare quali punti dati sono più vicini a una determinato punto di query, sarà necessario calcolare la distanza tra il punto di interrogazione e gli altri punti dati. Queste metriche di distanza aiutano a formare confini decisionali, che suddividono i punti di query in regioni diverse. Di solito vedrai i limiti delle decisioni visualizzati con i diagrammi di Voronoi.

Sebbene ci siano diverse misure di distanza tra cui puoi scegliere, questo articolo tratterà solo quanto segue:

Distanza euclidea (p=2):  questa è la misura della distanza più comunemente usata ed è limitata ai vettori con valori reali. Utilizzando la formula seguente, misura una linea retta tra il punto di query e l'altro punto che si sta misurando.

Distanza di Manhattan (p=1): questa è anche un'altra metrica di distanza popolare, che misura il valore assoluto tra due punti. Viene anche chiamata distanza del taxi o distanza del blocco cittadino poiché è comunemente visualizzata con una griglia, che illustra come si potrebbe andare da un indirizzo all'altro attraverso le strade della città.

Distanza di Minkowski: questa misura della distanza è la forma generalizzata delle metriche di distanza euclidea e di Manhattan. Il parametro, p, nella formula seguente, 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 tipicamente con vettori booleani o stringa, identificando i punti in cui i vettori non corrispondono. Di conseguenza, è stata anche definita metrica di sovrapposizione. Questo può essere rappresentato con la seguente formula:

Ad esempio, se avessi le seguenti stringhe, la distanza di hamming sarebbe 2 poiché solo due dei valori differiscono.


Calcola KNN: definizione di k

Il valore k nell'algoritmo k-NN definisce quanti vicini 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 neighbors più vicino. Definire k può essere un atto di bilanciamento in quanto valori diversi possono portare a overfitting o underfitting. Valori inferiori a k possono avere una variabilità elevata, ma una bassa distorsione e valori maggiori di k possono portare a una distorsione elevata e una variabilità inferiore. La scelta di k dipenderà in gran parte dai dati di input poiché i dati con più valori anomali o rumore probabilmente funzioneranno meglio con valori più elevati di k. In generale,si consiglia di avere un numero dispari per k per evitare pareggi nella classificazione e le tattiche di convalida incrociata possono aiutarti a scegliere la k ottimale per il tuo set di dati.

k-nearest neighbors e python

Per approfondire e saperne di più sull'algoritmo k-NN usando Python e scikit-learn (noto anche come sklearn)... Il nostro tutorial in Watson Studio ti aiuta ad apprendere la sintassi di base da questa libreria, che contiene anche altre librerie popolari, come NumPy, pandas e Matplotlib. Il codice seguente è un esempio di come creare e prevedere con un modello KNN:

da sklearn.neighbors import KNeighborsClassifier
model_name = 'K-Nearest Neighbor Classifier'
knnClassifier = KNeighborsClassifier(n_neighbors = 5, metric = 'minkowski', p=2)
knn_model = Pipeline(steps=[('preprocessor', preprocessorForFeatures), ('classifier' , knnClassifier)])
knn_model.fit(X_train, y_train)
y_pred = knn_model.predict(X_test)


Applicazioni di k-NN nell'apprendimento automatico

L'algoritmo k-NN è stato utilizzato all'interno di una varietà di applicazioni, in gran parte all'interno della classificazione. Alcuni di questi casi d'uso includono:

- Pre-elaborazione dei dati: I dataset hanno 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 del flusso di clic dai siti web, l'algoritmo KNN è stato utilizzato per fornire consigli automatici agli utenti su contenuti aggiuntivi. Questa ricerca (link esterno a ibm.com) mostra che un utente è assegnato a un particolare gruppo e, in base al comportamento degli utenti di quel gruppo, riceve un consiglio. Tuttavia, dati i problemi di scalabilità con KNN, questo approccio potrebbe non essere ottimale per i dataset più grandi.

- Finanza: è stato utilizzato anche in una varietà di casi di utilizzo finanziari ed economici. Ad esempio, un articolo (PDF, 391 KB)  (link esterno a ibm.com) mostra in che modo l'utilizzo di KNN sui dati di credito può aiutare le banche a valutare i rischi su un prestito a un'organizzazione o a un individuo. Viene utilizzato per determinare l'affidabilità creditizia di chi richiede il prestito. Un altro articolo (PDF, 447 KB)(link esterno a ibm.com) ne sottolinea l'uso nelle previsioni del mercato azionario, nei tassi di cambio, nel trading di futures e nelle analisi sul riciclaggio di denaro.

- Assistenza sanitaria: KNN ha avuto applicazioni anche nel settore dell'assistenza sanitaria, facendo previsioni sul rischio di infarto e cancro alla prostata. L'algoritmo funziona calcolando le espressioni geniche più probabili.

- Riconoscimento dei pattern: KNN ha anche aiutato a identificare i pattern, come nel testo e nella classificazione digitale (link esterno a ibm.com). Ciò è stato particolarmente utile per identificare i numeri scritti a mano che potresti trovare su moduli o buste postali. 


Vantaggi e svantaggi dell'algoritmo KNN

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

Vantaggi

- Facile da implementare: data la semplicità e l'accuratezza dell'algoritmo, è uno dei primi classificatori che un data scientist alle prime armi apprenderà.

- Si adatta facilmente: quando vengono aggiunti nuovi campioni di addestramento, l'algoritmo si adatta per tenere conto di eventuali nuovi dati poiché tutti i dati di addestramento vengono archiviati in memoria.

- Pochi iperparametri: KNN ha bisogno solo di un valore k e una metrica di distanza, il che è poco rispetto ad altri algoritmi di machine learning.

Svantaggi

- Non ha una buona scalabilità: poiché KNN è un algoritmo pigro, occupa più memoria e spazio di storage dei dati rispetto ad altri classificatori. Questo può essere costoso sia dal punto di vista del tempo che del denaro. Più memoria e spazio di archiviazione aumenteranno le spese aziendali e l'elaborazione di più dati può richiedere più tempo. Sebbene diverse strutture di dati, come Ball-Tree, siano state create per affrontare le inefficienze computazionali, un classificatore diverso potrebbe essere ideale a seconda del problema di business.

- Maledizione della dimensionalità: l'algoritmo KNN tende a cadere vittima della maledizione della dimensionalità, il che significa che non funziona bene con input di dati ad alta dimensionalità. Questo è a volte indicato anche come il fenomeno del picco (PDF, 340 MB) (link esterno a ibm.com), dove dopo che l'algoritmo raggiunge l'ottimale numero di funzioni, le funzioni aggiuntive aumentano la quantità di errori di classificazione, soprattutto quando la dimensione del campione è inferiore.

- Propenso al sovradimensionamento dei dati: a causa della "maledizione della dimensionalità", KNN è anche più propenso al sovradimensionamento dei dati. Sebbene le tecniche di selezione delle caratteristiche e di riduzione della dimensionalità vengano sfruttate per evitare che ciò accada, il valore di k può anche influire sul comportamento del modello. Valori più bassi di k possono sovraalimentare i dati, mentre valori più alti di k tendono a "smussare" i valori di previsione poiché sta facendo la media dei valori su un'area o un neighborhood più grande. Tuttavia, se il valore di k è troppo alto, può essere inferiore ai dati. 


Soluzioni correlate

IBM Cloud Pak for Data

Cloud IBM Pak for Data è una piattaforma di dati aperta ed estensibile che fornisce una struttura di dati per rendere tutti i dati disponibili per l'AI e l'analytics, su qualsiasi cloud.


IBM Watson Studio

Sviluppa, esegui e gestisci i modelli AI. Prepara i dati e crea modelli su qualsiasi cloud utilizzando la modellazione visiva o il codice open source. Prevedi e ottimizza i risultati.


IBM Db2 on Cloud

Scopri Db2 on Cloud, un database cloud SQL completamente gestito e ottimizzato per prestazioni solide.



Fasi successive

k-NN Node e Cloud IBM Pak for Data

Il Cloud Pak for Data è un set di strumenti che aiuta a preparare i dati per l'implementazione dell'IA Il nodo k-NN è un metodo di modellazione disponibile in IBM Cloud Pak for Data, che semplifica lo sviluppo di modelli predittivi. Il plug-in si distribuisce su qualsiasi cloud e si integra perfettamente nella tua infrastruttura cloud esistente.