Che cos'è l'algoritmo K-Nearest Neighbors (KNN) nel Machine Learning?
Ultimo aggiornamento: 1 marzo 2025
Alla fine di questo articolo, sarai in grado di:
Spiegare i principi fondamentali alla base di KNN e come funziona
Selezionare metriche di distanza appropriate per diversi tipi di dati
Implementare KNN sia per attività di classificazione sia di regressione
Ottimizzare i modelli KNN selezionando il valore ideale di k
Comprendere i limiti di KNN e quando utilizzare approcci alternativi
Applicare KNN a problemi reali con Python
Introduzione: la somiglianza nel processo decisionale quotidiano
Immagina di cercare di decidere quale ristorante visitare in una nuova città. Cosa fai di solito? Potresti chiedere consigli ad amici con gusti simili ai tuoi, confidando nel fatto che, se persone con preferenze simili alle tue hanno apprezzato un ristorante, probabilmente piacerà anche a te.
Questo concetto intuitivo—secondo cui elementi o entità simili tra loro spesso condividono caratteristiche importanti—è esattamente ciò che alimenta l’algoritmo K-Nearest Neighbors (KNN). KNN formalizza questa intuizione in una potente tecnica di machine learning che trova applicazione in numerosi ambiti, dai sistemi di raccomandazione alla diagnosi medica.
L’algoritmo knn è un algoritmo di machine learning supervisionato che può risolvere sia problemi di classificazione sia di regressione. Stima la probabilità che un punto dati appartenga a un gruppo o a un altro in base a quali punti dati esistenti sono più vicini a esso. A differenza di molti algoritmi ml che costruiscono modelli complessi, l’eleganza di KNN risiede nella sua semplicità: l’algoritmo si limita a memorizzare i dati di addestramento ed effettua previsioni trovando gli esempi più simili.
Definizione di KNN
L’algoritmo K-nearest neighbor è un algoritmo di machine learning supervisionato che sfrutta la prossimità per effettuare classificazioni o previsioni sul raggruppamento di un singolo punto dati. In quanto algoritmo non parametrico di lazy learning, KNN memorizza l’intero dataset di addestramento ed esegue i calcoli solo al momento della classificazione. Ciò significa che, invece di costruire un modello durante una fase di addestramento, KNN effettua previsioni confrontando direttamente nuovi punti dati con i dati di addestramento memorizzati. L’algoritmo è versatile, essendo utilizzato sia per attività di classificazione sia di regressione, e le sue prestazioni sono influenzate dalla scelta di K (il numero di vicini più prossimi considerati) e dalla metrica di distanza utilizzata per misurare la somiglianza.
Importanza di KNN nella Data Science
L’algoritmo KNN occupa un posto significativo nell’ambito del ml e della data science grazie alla sua semplicità, facilità di interpretazione e costo computazionale relativamente basso per dataset di dimensioni piccole o medie. Il suo approccio lineare lo rende un eccellente punto di partenza per i principianti nella data science, mentre la sua efficacia fa sì che rimanga uno strumento prezioso per i professionisti esperti. KNN è ampiamente applicato in vari ambiti, tra cui classificazione di immagini, classificazione di testi e sistemi di raccomandazione. Ad esempio, può prevedere l’abbandono degli utenti in un servizio di streaming, assistere nella diagnosi medica e supportare le previsioni finanziarie. La sua capacità di gestire relazioni non lineari e la sua robustezza rispetto agli outlier ne aumentano ulteriormente l’attrattiva, rendendolo una scelta popolare nel settore.
Concetti fondamentali
Apprendimento supervisionato vs. non supervisionato
KNN appartiene alla famiglia degli algoritmi di apprendimento supervisionato, il che significa che richiede dati di addestramento etichettati per effettuare previsioni. Nell’apprendimento supervisionato, l’algoritmo impara da esempi in cui le risposte corrette (etichette) sono fornite, in contrasto con l’apprendimento non supervisionato, in cui l’algoritmo deve trovare pattern in dati non etichettati.
Lazy Learning vs. Eager Learning
Ciò che rende KNN unico tra molti algoritmi ml è il fatto che è considerato un "lazy learner". La maggior parte degli algoritmi attraversa una fase di addestramento esplicita per costruire un modello prima di effettuare previsioni. KNN, tuttavia, non ha una fase di addestramento distinta: si limita a memorizzare il dataset di addestramento e rimanda tutti i calcoli al momento della previsione. Questo è il motivo per cui KNN è anche chiamato:
Apprendimento basato sulle istanze
Apprendimento basato sulla memoria
Apprendimento non parametrico
Poiché KNN non fa ipotesi sulla distribuzione dei dati sottostante (non parametrico) e non riassume i dati di addestramento in un modello compatto, può catturare confini decisionali complessi che i modelli parametrici potrebbero non rilevare.
Classificazione vs. Regressione con KNN
KNN può essere utilizzato sia per compiti di classificazione sia di regressione:
Classificazione KNN: Predice l'etichetta di classe di una nuova istanza trovando la classe più comune tra i suoi k vicini più prossimi. La classificazione di un nuovo punto dati si basa sulla classe più comune tra i suoi k vicini più prossimi (KNN).
Regressione KNN: Predice il valore numerico di una nuova istanza facendo la media dei valori dei suoi k vicini più prossimi.
Spazio delle caratteristiche e somiglianza
Il fondamento di KNN è il concetto di somiglianza o distanza nello spazio delle caratteristiche. Ogni punto dati è rappresentato come un vettore in uno spazio multidimensionale, dove ogni dimensione corrisponde a una caratteristica. La somiglianza tra due punti dati è inversamente correlata alla distanza tra essi in questo spazio delle caratteristiche: più due punti sono vicini, più sono considerati simili.
Metriche di distanza in dettaglio
La scelta della metrica di distanza è cruciale in KNN poiché influisce direttamente su quali punti sono considerati "più prossimi" tra loro. Diverse metriche di distanza sono appropriate per diversi tipi di dati e domini di problema.
Distanza euclidea
La distanza euclidea è la vera distanza in linea retta tra due punti nello spazio euclideo. È la metrica di distanza più comunemente utilizzata in KNN.
Formula matematica:
Dove x e y sono due punti in uno spazio n-dimensionale.
Quando usarla: La distanza euclidea funziona bene quando i dati sono continui e hanno relazioni significative in tutte le dimensioni. È particolarmente appropriata quando le caratteristiche sono misurate su scale simili.
Distanza di Manhattan
Nota anche come distanza city block o L1, la distanza di Manhattan calcola la somma delle differenze assolute tra le coordinate di due punti. Nell'algoritmo KNN, le distanze di Manhattan vengono utilizzate per misurare la prossimità dei punti dati in strutture a griglia, rendendola particolarmente adatta a tali ambienti.
Formula matematica:
Quando usarla: La distanza di Manhattan è utile quando le caratteristiche rappresentano attributi discreti o binari, oppure quando lo spazio delle caratteristiche è simile a una griglia. Può essere meno sensibile agli outlier rispetto alla distanza euclidea.
Similarità coseno
La similarità coseno misura il coseno dell'angolo tra due vettori, concentrandosi sull'orientamento piuttosto che sulla magnitudine.
Formula matematica:
Quando usarla: La similarità coseno è particolarmente utile per l'analisi del testo e per dati sparsi ad alta dimensionalità, dove la magnitudine dei vettori potrebbe non essere importante quanto la loro direzione.
Distanza di Hamming
La distanza di Hamming conta il numero di posizioni in cui gli elementi corrispondenti differiscono in due sequenze di uguale lunghezza.
Formula matematica: Per due stringhe di uguale lunghezza, la distanza di Hamming è il numero di posizioni in cui i simboli corrispondenti differiscono.
Quando usarla: La distanza di Hamming è ideale per dati categoriali o quando si lavora con caratteristiche binarie. È comunemente utilizzata nella teoria dell'informazione, nella teoria dei codici e per confrontare stringhe o vettori di bit.
Linee guida per la scelta delle metriche di distanza
Distanza euclidea: Dati continui con scale simili
Distanza di Manhattan: Spazi simili a griglie, indipendenza delle caratteristiche
Similarità del coseno: Dati testuali, dati sparsi ad alta dimensionalità
Distanza di Hamming: Dati categoriali, caratteristiche binarie
Ricorda che, indipendentemente dalla metrica di distanza scelta, il ridimensionamento delle caratteristiche è spesso necessario per evitare che le caratteristiche con scale più grandi dominino i calcoli della distanza.
L'algoritmo KNN: passo dopo passo
Ora che comprendiamo il concetto di distanza, esaminiamo l'algoritmo KNN passo dopo passo.
Requisiti di pre-elaborazione dei dati
Prima di applicare KNN, sono essenziali diversi passaggi di pre-elaborazione:
Ridimensionamento delle caratteristiche: Poiché i calcoli della distanza sono direttamente influenzati dalla scala delle caratteristiche, la normalizzazione o la standardizzazione è cruciale. In genere, le caratteristiche vengono ridimensionate nell'intervallo [0, 1] o standardizzate per avere una media di 0 e una deviazione standard di 1.
Gestione dei valori mancanti: KNN non può gestire direttamente i valori mancanti, quindi dovrebbero essere applicate tecniche di imputazione.
Riduzione della dimensionalità: I dati ad alta dimensionalità possono soffrire della "maledizione della dimensionalità," in cui le metriche di distanza diventano meno significative. Tecniche come PCA possono aiutare a ridurre la dimensionalità.
Selezione dei parametri
Il parametro più critico in KNN è k, il numero di vicini da considerare. La scelta di k ha un impatto significativo sulle prestazioni del modello:
k piccolo (ad es., k=1 o k=3): Il modello può avere un'elevata varianza (overfitting), essendo sensibile al rumore nei dati di training.
k grande (ad es., k=20): Il modello può avere un elevato bias (underfitting), potenzialmente perdendo pattern importanti nei dati.
Il valore ottimale di k viene tipicamente determinato tramite cross-validation, spesso utilizzando tecniche come il metodo del gomito o la grid search, che discuteremo più in dettaglio più avanti.
Fase di training (o sua assenza)
Come menzionato in precedenza, KNN non ha una fase di training tradizionale. Invece, memorizza semplicemente l'intero dataset di training in memoria. Questa caratteristica rende KNN rapido da "addestrare" ma potenzialmente lento durante la predizione, soprattutto con dataset di grandi dimensioni.
Processo di predizione
Come calcolare l'algoritmo K-Nearest Neighbor
Per determinare la classe di un punto dati non osservato in base all'osservazione, il K-Nearest Neighbor utilizza essenzialmente un meccanismo di voto a maggioranza. Il voto a maggioranza è un processo fondamentale in KNN, in cui l'algoritmo classifica un punto dati determinando la categoria a cui appartiene la maggior parte dei suoi vicini più prossimi. Indica che la classe che riceve il maggior numero di voti sarà la classe per il punto dati rilevante. L'algoritmo KNN classifica un determinato punto dati in base alla prossimità dei suoi vicini più prossimi.
Se K è uguale a 1, considereremo solo il vicino più prossimo di un punto dati quando ne determineremo la classe. Verranno utilizzati i 10 vicini più prossimi se K è uguale a 10, e così via. Il punto di test viene classificato in base al valore di 'k' e alla prossimità ai punti dati di training.
Considera due classi: A e B. L'algoritmo esamina gli stati dei punti dati vicini per determinare se un punto dati appartiene alla Classe A o alla Classe B. Se la maggior parte dei punti dati è nel gruppo A, è quasi certo che il punto dati in questione appartenga al gruppo A.
Per le attività di classificazione, KNN effettua predizioni utilizzando questi passaggi:
Calcolare la distanza tra la nuova istanza e tutte le istanze nel dataset di training.
Selezionare le k istanze dal dataset di training più vicine alla nuova istanza.
Per la classificazione: Effettuare un voto a maggioranza dei knn per determinare la classe della nuova istanza.
Per la regressione: Calcolare la media (o media ponderata) dei valori dei k vicini più prossimi.
Come funziona KNN tra due classi. Fonte: https://www.ibm.com/in-en/topics/knn
Esempio di KNN in azione
Un classico esempio di KNN in azione è un sistema di raccomandazione per un servizio di streaming di film. Immagina una piattaforma che utilizza l'algoritmo KNN per suggerire film agli utenti in base alla loro cronologia di visione e alle valutazioni passate. L'algoritmo identifica i K vicini più prossimi a un determinato utente, dove i vicini sono altri utenti con abitudini di visione simili. Analizzando le preferenze di questi vicini, il sistema può raccomandare film che sono molto apprezzati da loro ma non ancora visti dall'utente target. Questo approccio di raccomandazione personalizzata non solo migliora l'esperienza utente, ma aumenta anche il coinvolgimento e la soddisfazione degli utenti, mostrando la potenza pratica dell'algoritmo KNN.
Varianti di KNN ponderato
Il KNN standard tratta tutti i vicini allo stesso modo, ma questo potrebbe non essere ideale, poiché i vicini più prossimi dovrebbero logicamente avere maggiore influenza sulle previsioni. Il KNN ponderato affronta questo aspetto assegnando pesi ai vicini in base alla loro distanza:
Il peso di ciascun vicino è tipicamente l'inverso della sua distanza dal punto di query.
Per la classificazione, viene eseguito un voto ponderato.
Per la regressione, viene calcolata una media ponderata.
La formula per un semplice approccio ponderato in base alla distanza potrebbe apparire così:
weighti=1d(x,xi)2\text{weight}_i = \frac{1}{d(x, x_i)^2}weighti=d(x,xi)21
Dove d(x, xi) è la distanza tra il punto di query x e il vicino xi.
Ottimizzazione delle prestazioni di KNN
Strategie di convalida incrociata per trovare il k ottimale
La convalida incrociata K-fold è comunemente usata per determinare il valore ottimale di k. Il processo prevede:
Suddividere il dataset in k fold (da non confondere con la k in KNN).
Per ciascun valore di k in KNN (ad es., da k=1 a k=20):
Addestrare e valutare il modello k volte, usando ogni volta un fold diverso come set di test.
Calcolare la prestazione media su tutti i k fold.
Selezionare il valore di k che fornisce la migliore prestazione media.
Metodo del gomito
Il metodo del gomito consiste nel tracciare le prestazioni del modello (ad es., accuratezza o tasso di errore) rispetto a diversi valori di k e nel cercare un "punto di gomito" in cui il tasso di miglioramento diminuisce significativamente. Questo punto indica spesso un buon compromesso tra bias e varianza.
Implementazione della ricerca a griglia
La ricerca a griglia è un modo sistematico per provare diverse combinazioni di iperparametri (inclusi k ed eventualmente metriche di similarità) e selezionare la combinazione che offre le migliori prestazioni su un set di validazione.
Gestione dello squilibrio tra classi
KNN può essere sensibile allo squilibrio tra classi, quando alcune classi hanno molti più esempi di altre. Le strategie per affrontare questo problema includono:
Ricampionamento: Oversampling delle classi minoritarie o undersampling delle classi maggioritarie.
Metriche di valutazione diverse: Uso di metriche come F1-score o AUC invece dell'accuratezza.
Voto ponderato: Assegnazione di pesi diversi alle classi in base alla loro frequenza.
Considerazioni sulla dimensionalità e la maledizione della dimensionalità
All'aumentare del numero di dimensioni (feature), il volume dello spazio aumenta esponenzialmente. Questo fenomeno, noto come "maledizione della dimensionalità", può rendere le metriche di distanza meno significative e KNN meno efficace. Negli spazi ad alta dimensionalità:
I punti dati tendono a essere equidistanti tra loro.
Il concetto di "più vicino" diventa meno chiaro.
Il modello richiede una quantità di dati esponenzialmente maggiore.
Per contrastare questo problema, considera:
Selezione delle feature per rimuovere le feature irrilevanti
Tecniche di riduzione della dimensionalità come PCA
Uso di strutture dati specializzate come KD-trees per una ricerca efficiente dei vicini più prossimi
Implementazione pratica
Implementiamo KNN per un'attività di classificazione usando Python e scikit-learn.
Importazione dei moduli
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
Dataset
Scikit-learn può essere utilizzato per creare campioni di addestramento generando dataset sintetici, ottimi a scopo dimostrativo.
X, y = make_blobs(n_samples = 4000, n_features = 3, centers = 3 ,cluster_std = 2, random_state = 80)
X
array([[ 7.60190561, 4.86336321, 6.97616573],
[ 5.97809745, 7.69910922, 2.77419701],
[-4.36024844, -2.23247572, -5.29113293],
...,
[-8.22252297, -6.88609334, -6.52102135],
[-3.96254707, -5.27559922, -2.70880022],
[-4.25865881, -1.67791521, -3.70523373]])
y
array([1, 1, 2, ..., 2, 2, 2])
Grafico
plt.figure(figsize = (6,6))
plt.scatter(X[:,0], X[:,1], c=y, marker= '.', s=10, edgecolors='blue')
plt.show()
df = pd.DataFrame(X)
df.head()
plt.rcParams['figure.figsize']=(10,15)
df.plot(kind='hist', bins=100, subplots=True, layout=(5,2), sharex=False, sharey=False)
plt.show()
Implementazione del classificatore K-Nearest Neighbors
Il primo passo consiste nel determinare il valore ottimale per k. Il calcolo del valore di K varia molto a seconda della situazione. Il valore predefinito di K quando si utilizza la libreria Scikit-Learn è 5 e la metrica di distanza predefinita utilizzata è quella euclidea.
Ottimizzazione del modello per ottenere un'elevata accuratezza K Nearest Neighbor
from sklearn.model_selection import GridSearchCV
param_grid = {'n_neighbors':np.arange(1,4)}
knn = KNeighborsClassifier()
knn_cv= GridSearchCV(knn,param_grid,cv=5)
knn_cv.fit(X,y)
print(knn_cv.best_params_)
print(knn_cv.best_score_)
{'n_neighbors': 3}
0.9887499999999999
#train-test split
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state = 80)
# instantiate the model
knn = KNeighborsClassifier(n_neighbors=3)
# fit the model to the training set
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)
print('Model accuracy score: {0:0.4f}'. format(accuracy_score(y_test, y_pred)))
Punteggio di accuratezza del modello: 0.9890.
Abbiamo ottenuto un tasso di accuratezza del 98,90%, considerato molto buono. Abbiamo aumentato il numero di vicini da 1 a 4 e il modello ha ottenuto le prestazioni migliori con k=3.
Il modello K Nearest Neighbor non prevede alcun periodo di addestramento, poiché i dati stessi costituiscono un modello che sarà il riferimento per la previsione nella futura fase di addestramento. Di conseguenza, è efficiente in termini di tempo, consentendo una rapida improvvisazione per la modellazione casuale sui dati disponibili.
KNN richiede solo due iperparametri, un valore K e una metrica di distanza, il che lo rende più semplice da ottimizzare rispetto ad altri algoritmi di machine learning.
La maggior parte degli algoritmi classificatori è facile da implementare per problemi di classificazione binaria, ma richiede uno sforzo aggiuntivo per essere implementata in problemi multi-classe. Al contrario, KNN si adatta ai problemi multi-classe senza alcuno sforzo aggiuntivo.
Meccanismo principale
Il meccanismo principale dell'algoritmo KNN consiste nell'identificare i K vicini più prossimi a un determinato punto dati e nell'utilizzare le loro etichette di classe per effettuare una previsione. Per le attività di classificazione, l'algoritmo assegna la classe più comune tra i K vicini più prossimi. Per le attività di regressione, calcola la media dei valori dei K vicini più prossimi per prevedere il valore del nuovo punto dati. Questo approccio è ampiamente utilizzato in vari ambiti grazie alla sua semplicità ed efficacia, consentendogli di gestire con facilità sia problemi di classificazione sia di regressione.
Valutazione delle metriche di prestazione
Quando si valutano i modelli KNN, considera più metriche oltre alla sola accuratezza:
Accuratezza: La proporzione di previsioni corrette.
Precisione: La proporzione di identificazioni positive che erano effettivamente corrette.
Richiamo: La proporzione di positivi effettivi identificati correttamente.
F1-score: La media armonica di precisione e richiamo.
Matrice di confusione: Una tabella che mostra le classificazioni corrette e incorrectte per ciascuna classe.
Curva ROC e AUC: Per la classificazione binaria, mostra il compromesso tra tasso di veri positivi e tasso di falsi positivi.
Suggerimenti per scalare a dataset più grandi
KNN può diventare computazionalmente costoso con dataset di grandi dimensioni. Ecco alcune strategie per migliorare l'efficienza:
Usare algoritmi di approximate nearest neighbor: Algoritmi come il locality-sensitive hashing (LSH) possono trovare vicini più prossimi approssimati molto più rapidamente rispetto ai metodi esatti.
Implementare varianti di KNN per l'efficienza: Strutture dati come KD-trees e ball trees organizzano i dati per rendere più efficiente la ricerca del vicino più prossimo:
KD-trees: Partizionano lo spazio usando iperpiani, consentendo una rapida eliminazione di ampie porzioni dello spazio di ricerca.
Ball trees: Partizionano lo spazio usando ipersfere, che possono essere più efficaci dei KD-trees in spazi ad alta dimensionalità.
Campionare i dati di training: Per dataset molto grandi, l'uso di un campione rappresentativo può ridurre significativamente il tempo di calcolo con un impatto minimo sull'accuratezza.
Elaborazione parallela: Utilizzare processori multi-core o calcolo distribuito per accelerare i calcoli delle distanze.
Applicazioni nel mondo reale
KNN è ampiamente utilizzato in vari domini grazie alla sua semplicità ed efficacia:
Sistemi di raccomandazione
KNN è la base del filtraggio collaborativo nei sistemi di raccomandazione. Trovando utenti con preferenze simili (vicini più prossimi), il sistema può consigliare elementi che quegli utenti simili hanno apprezzato ma che l'utente target non ha ancora visto.
Caso di studio: Raccomandazione di film
Un servizio di streaming potrebbe usare KNN per consigliare film agli utenti in base alla loro cronologia di visione. L'algoritmo troverebbe utenti con schemi di visione simili e consiglierebbe film che questi utenti simili hanno apprezzato ma che l'utente target non ha ancora guardato.
Diagnosi medica
KNN può aiutare nella diagnosi medica trovando pazienti con sintomi o risultati di test simili e usando le loro diagnosi per prevedere la diagnosi di un nuovo paziente.
Caso di studio: Predizione del diabete
Usando caratteristiche come livello di glucosio, BMI, età e pressione sanguigna, KNN può classificare se un paziente è probabile che abbia il diabete confrontando le sue metriche con quelle di pazienti con diagnosi note.
Riconoscimento delle immagini
Nella computer vision, KNN può essere usato per la classificazione delle immagini confrontando vettori di caratteristiche estratti dalle immagini.
Progetto di esempio: Riconoscimento di cifre scritte a mano
Usando il dataset MNIST, possiamo implementare KNN per riconoscere cifre scritte a mano. Ogni immagine è rappresentata come un vettore di valori dei pixel e l'algoritmo classifica nuove immagini in base alla somiglianza con le immagini di training.
Rilevamento di anomalie
KNN può identificare anomalie o outlier trovando punti che sono lontani dai loro vicini più prossimi.
Esempio di implementazione: Rilevamento di frodi con carte di credito
Calcolando la distanza media dal knn per ciascuna transazione, quelle con distanze insolitamente grandi possono essere contrassegnate come potenziali frodi.
Ricerca di similarità vettoriale
In spazi vettoriali ad alta dimensionalità come quelli usati in NLP e computer vision, KNN può trovare efficientemente elementi simili. Questo è particolarmente prezioso in applicazioni come:
Ricerca di similarità delle immagini
Clustering di documenti
Corrispondenza di entità
Per queste applicazioni, database vettoriali specializzati possono migliorare significativamente le prestazioni rispetto ai database tradizionali, soprattutto quando si lavora con dati ad alta dimensionalità in cui il calcolo della similarità è computazionalmente intensivo.
Limitazioni e alternative
Quando KNN fallisce
Nonostante la sua semplicità ed efficacia, KNN presenta diverse limitazioni:
Computazionalmente costoso: Per dataset di grandi dimensioni, calcolare le distanze tra tutte le coppie di punti può essere proibitivamente costoso.
La maledizione della dimensionalità: In spazi ad alta dimensionalità, il concetto di distanza diventa meno significativo, rendendo KNN meno efficace.
Dati sbilanciati: KNN può essere distorto verso la classe maggioritaria nei dataset sbilanciati.
Sensibile al rumore e alle caratteristiche irrilevanti: Poiché KNN si basa sui calcoli di distanza, caratteristiche rumorose o irrilevanti possono influire significativamente sulle sue prestazioni.
Intensivo in memoria: KNN richiede di memorizzare l'intero dataset di training in memoria.
Vantaggi di KNN
Nonostante queste limitazioni, KNN offre diversi vantaggi:
Nessun periodo di addestramento: Il modello KNN non prevede alcun periodo di addestramento poiché i dati stessi sono il modello. Questo lo rende efficiente in termini di tempo, consentendo una rapida improvvisazione per modellazioni casuali sui dati disponibili.
Semplice ottimizzazione degli iperparametri: KNN richiede solo due iperparametri principali: un valore k e una metrica di similarità, rendendolo più semplice da ottimizzare rispetto a molti altri algoritmi di machine learning.
Supporto multi-classe naturale: A differenza di molti algoritmi di classificazione che richiedono uno sforzo aggiuntivo per essere implementati per problemi multi-classe, KNN si adatta ai problemi multi-classe senza alcuna complessità aggiuntiva.
Natura non parametrica: KNN non fa assunzioni sulla distribuzione dei dati sottostante, permettendogli di catturare pattern complessi che i modelli parametrici potrebbero non rilevare.
Considerazioni sulla complessità computazionale
Complessità temporale per la previsione: O(MN log(k)) per ogni previsione, dove M è la dimensione dei dati (numero di caratteristiche) e N è la dimensione o il numero di istanze nel dataset di training. Questo perché:
Calcolo delle distanze tra il punto di query e tutti i punti di training: O(MN)
Individuazione dei knn (tipicamente usando un ordinamento parziale): O(N log(k))
Complessità spaziale: O(MN) per memorizzare il dataset di training.
Questa complessità computazionale può rendere KNN impraticabile per dataset di grandi dimensioni senza ottimizzazione. Tuttavia, esistono strutture dati e algoritmi specializzati che possono rendere KNN più efficiente anche per dataset di grandi dimensioni.
Algoritmi alternativi
Quando KNN non è adatto, considera queste alternative:
Decision Trees e Random Forests: Gestiscono meglio le caratteristiche irrilevanti e possono fornire l'importanza delle caratteristiche.
Support Vector Machines (SVM): Più efficaci in spazi ad alta dimensionalità e con confini decisionali complessi.
Naive Bayes: Computazionalmente efficiente e funziona bene con dati ad alta dimensionalità.
Neural Networks: Capaci di apprendere pattern complessi, ma richiedono più dati e risorse computazionali.
Approcci ibridi
Combinare KNN con altri algoritmi può superare alcune delle sue limitazioni:
KNN con selezione/estrazione delle caratteristiche: Applica tecniche di selezione delle caratteristiche prima di usare KNN per ridurre la dimensionalità.
Metodi ensemble: Combina KNN con altri algoritmi tramite voting o stacking.
Regressione locale ponderata: Usa KNN per identificare quartieri locali, quindi applica la regressione all'interno di ciascun quartiere.
Conclusione e ulteriori risorse
K-Nearest Neighbors è un algoritmo potente e intuitivo che sfrutta il semplice concetto secondo cui istanze simili tendono ad avere esiti simili. Nonostante la sua semplicità, KNN può essere molto efficace se implementato correttamente, con preprocessing appropriato, selezione dei parametri e tecniche di ottimizzazione.
Punti chiave
KNN è un algoritmo di apprendimento non parametrico, basato su istanze, che può essere utilizzato sia per compiti di classificazione sia di regressione.
La scelta della metrica di similarità e il valore di k sono cruciali per le prestazioni di KNN.
Il ridimensionamento delle caratteristiche è essenziale prima di applicare KNN per garantire che tutte le caratteristiche contribuiscano equamente ai calcoli di distanza.
KNN può soffrire della maledizione della dimensionalità e può essere computazionalmente costoso per dataset di grandi dimensioni.
Implementazioni efficienti che utilizzano KD-trees o ball trees possono migliorare significativamente le prestazioni.
Direzioni future per la ricerca su KNN
Nonostante la sua semplicità ed efficacia, l'algoritmo KNN presenta diverse limitazioni, come la sensibilità al rumore e agli outlier, l'elevato costo computazionale e la necessità di una notevole memoria per archiviare i dati di addestramento. Le direzioni future della ricerca su KNN includono lo sviluppo di algoritmi più efficienti per gestire dataset di grandi dimensioni, il miglioramento della robustezza al rumore e agli outlier e l'esplorazione di nuove metriche di similarità e schemi di ponderazione. Inoltre, i ricercatori stanno studiando l'integrazione di KNN con tecnologie emergenti come il deep learning, l'elaborazione del linguaggio naturale e la computer vision. Affrontando queste sfide ed espandendone le applicazioni, il continuo sviluppo dell'algoritmo KNN avrà un impatto significativo sul campo della data science, garantendone la rilevanza e l'utilità nella risoluzione di problemi complessi.
Articoli accademici e risorse
Per coloro che sono interessati ad approfondire KNN e le sue varianti, considerate queste risorse:
Cover, T. M., & Hart, P. E. (1967). "Classificazione dei pattern del vicino più prossimo." IEEE Transactions on Information Theory, 13(1), 21-27.
Altman, N. S. (1992). "Un'introduzione alla regressione non parametrica kernel e nearest-neighbor." The American Statistician, 46(3), 175-185.
Weinberger, K. Q., & Saul, L. K. (2009). "Apprendimento delle metriche di distanza per la classificazione nearest neighbor a margine ampio." Journal of Machine Learning Research, 10, 207-244.
Corsi online e tutorial
Coursera: Machine Learning di Andrew Ng
Kaggle: Feature Engineering e KNN
Documentazione di scikit-learn: Nearest Neighbors
Comprendendo a fondo l'algoritmo KNN, i dettagli di implementazione e le tecniche di ottimizzazione, aggiungerai al tuo toolkit di machine learning uno strumento versatile e potente che può essere applicato in numerosi domini.
Continua a leggere
Why We Built Vector Lakebase: Rethinking Unstructured Data Architecture for AI
Vector Lakebase: a unified, lake-native data foundation for AI workloads — and an answer to what happens after vector databases succeed.
Zilliz Cloud On-Demand Compute: Pay Only for What You Use
The customer case behind Zilliz Cloud On-Demand: how a $10K vector search bill came down to under $500, and the engineering changes that made it possible.
Zilliz Cloud Enterprise Vector Search Powers High-Performance AI on AWS
Zilliz Cloud on AWS powers secure, scalable, ultra-fast vector search for enterprise AI apps, with BYOC, sub-10ms latency, and zero-DevOps simplicity.