Home
topics
KNN
L'algoritmo k-nearest neighbors (KNN) è un classificatore di apprendimento supervisionato non parametrico, che utilizza la prossimità per effettuare classificazioni o previsioni sul raggruppamento di un singolo punto dati. Si tratta di uno dei classificatori di classificazione e regressione più popolari e semplici attualmente utilizzato nell'apprendimento automatico.
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 sulla base di un voto di maggioranza, cioè viene utilizzata l'etichetta più frequentemente rappresentata in un determinato punto di dati. Sebbene tecnicamente questo sia considerato “voto di pluralità”, in letteratura è 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; 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 puoi trovare qui
I problemi di regressione utilizzano un concetto simile a quello di classificazione, ma in questo caso la media dei k vicini più prossimi viene presa in considerazione 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 per quelli continui. Tuttavia, prima di poter effettuare una classificazione, è necessario definire la distanza. La distanza euclidea è quella più comunemente utilizzata (verrà approfondita più avanti).
Vale la pena notare che l'algoritmo KNN fa anche parte di una famiglia di modelli di “apprendimento pigro”, cioè memorizza solo un set di dati di addestramento invece di sottoporsi a una fase di addestramento. Ciò significa anche che tutti i calcoli vengono eseguiti quando si effettua 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, è ancora uno dei primi algoritmi che si imparano nella scienza dei dati grazie alla sua semplicità e accuratezza. Tuttavia, man mano che un dataset cresce, il KNN diventa sempre più inefficiente, compromettendo le prestazioni complessive del modello. È comunemente usato per semplici sistemi di raccomandazione, riconoscimento di modelli, data mining, previsioni sui mercati finanziari, rilevamento delle intrusioni e altro ancora.
Scopri gli elementi costitutivi e le best practice per aiutare i tuoi team ad accelerare l'AI responsabile.
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:
Determinare le metriche di distanza
Per determinare quali punti di dati sono più vicini a un determinato punto di interrogazione, è necessario calcolare la distanza tra il punto di interrogazione e gli altri punti di dati. Queste metriche di distanza consentono di formare i limiti 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.
k-nearest neighbors e python
Per approfondire ulteriormente questo tema, è possibile acquisire maggiori conoscenze sull'algoritmo k-NN utilizzando Python e scikit-learn (noto anche come sklearn). Il nostro tutorial in Watson Studio ti aiuta a imparare la sintassi di base di questa libreria, che contiene anche altre librerie popolari, come NumPy, panda e Matplotlib. Il seguente codice è un esempio di come creare e prevedere con un modello KNN:
from 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)
L'algoritmo k-NN è stato utilizzato in diverse applicazioni, soprattutto nell'ambito della classificazione. Alcuni di questi casi d'uso includono:
- Preelaborazione dei dati: i dataset 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 data 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 di utilizzo in ambito finanziario ed economico. Ad esempio, un paper 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 un richiedente di prestito. Un'altra rivista ne evidenzia l'uso nelle previsioni del mercato azionario, nei tassi di cambio, nel trading di futures e nelle analisi di riciclaggio di denaro
- Servizi sanitari: il KNN ha trovato applicazione anche nel settore sanitario, facendo previsioni sul rischio di infarto e di cancro 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. Ciò si è rivelato particolarmente utile per identificare i numeri scritti a mano che si possono trovare su moduli o buste postali.
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 imparerà.
- Si adatta facilmente: man mano che vengono aggiunti nuovi campioni di addestramento, l'algoritmo si adatta per tenere conto di tutti i nuovi dati. Questo perché tutti i dati di addestramento vengono memorizzati.
- Pochi iperparametri: il KNN richiede solo un valore k e una metrica di distanza, che è bassa rispetto ad altri algoritmi di apprendimento automatico.
- Non è la migliore opzione a livello di scalabilità: poiché il KNN è un algoritmo pigro, occupa più memoria e archiviazione dei dati rispetto ad altri classificatori. Ciò può risultare costoso sia in termini di tempo che di denaro. Una maggiore quantità di memoria e di spazio di archiviazione 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 del problema aziendale.
- Riduzione della dimensionalità: l'algoritmo KNN tende a essere soggetto alla riduzione della dimensionalità, il che significa che non funziona bene con dati ad alta dimensionalità. Questo fenomeno viene talvolta definito anche come 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 “maledizione della dimensionalità”, il KNN è anche più incline all'overfitting. Sebbene le tecniche di selezione delle caratteristiche e di riduzione della dimensionalità vengano sfruttate per evitare che ciò accada, anche il valore di k può influire 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é la media dei valori viene calcolata su un'area più ampia, o quartiere. Tuttavia, se il valore di k è troppo alto, il modello può sotto-adattarsi ai dati.
IBM Cloud Pak for Data è una piattaforma dati aperta ed estensibile che fornisce un data fabric per rendere tutti i dati disponibili per l'AI e gli analytics su qualsiasi cloud.
Sperimenta con i foundation model e crea automaticamente modelli di machine learning nel nostro studio di prossima generazione per builder AI.
Scopri di più su Db2 on Cloud, un database SQL cloud completamente gestito, configurato e ottimizzato per garantire prestazioni elevate.
Granite è la serie di punta di foundation model LLM di IBM basati su un'architettura trasformativa decoder-only. I modelli linguistici Granite sono addestrati su dati aziendali affidabili che spaziano da Internet al mondo accademico, ai codici, ai settori legale e finanziario.
Impara i concetti fondamentali dell'AI e dell'AI generativa, tra cui il prompt engineering, i modelli linguistici di grandi dimensioni e i migliori progetti open source.
Scopri i fondamenti dell'esecuzione del clustering K-means in Python utilizzando IBM Watson Studio Jupyter Notebooks su watsonx.ai.
Scopri i fondamenti dell'esecuzione del clustering K-means in R utilizzando IBM Watson Studio Jupyter Notebooks su watsonx.ai.
Esplora le nozioni di base per risolvere un problema di machine learning basato sulla classificazione e ottieni uno studio comparativo di alcuni degli algoritmi attualmente più diffusi.
Identificazione delle classi utilizzando i vicini più prossimi.