K-Nearest Neighbors
- Introdotto da
- Cover, T.M. & Hart, P.E.
- Anno
- 1967
- Tipo
- Instance-based (non-parametric) learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
K-Nearest Neighbors (KNN), formalizzato da Cover e Hart nel 1967, è un metodo non parametrico basato su istanze che classifica o predice una nuova osservazione esaminando i k esempi più vicini nei dati di addestramento.
Per la classificazione adotta un voto a maggioranza tra questi vicini; per la regressione ne calcola la media dei valori.
L’intuizione alla base del metodo
L'idea è semplice: input simili tendono ad avere output simili. Per etichettare un nuovo punto, il KNN trova la manciata di esempi di addestramento che gli sono più vicini nello spazio delle feature e lascia che siano loro a decidere. Non viene adattata alcuna equazione in anticipo — i dati di addestramento stessi costituiscono il modello, e una previsione viene fatta solo quando arriva un nuovo punto.
Storia
La classificazione di pattern basata sui vicini più prossimi ha ricevuto il suo fondamento statistico formale da Thomas Cover e Peter Hart nel loro articolo del 1967 sull'IEEE Transactions on Information Theory, che analizzava il tasso di errore della regola del vicino più prossimo. Il KNN è diventato uno dei metodi di apprendimento basati su istanze più antichi e duraturi e rimane un classificatore di riferimento standard.
Quando usarlo
Utilizzare il KNN per la classificazione o la previsione su dati tabulari con feature continue, binarie o ordinali e almeno circa 30 osservazioni. Non assume alcuna distribuzione particolare, ma richiede che le feature siano normalizzate e che il numero di feature rimanga piccolo rispetto alla dimensione del campione (è preferibile p molto minore di n). In campioni piccoli o ad alta dimensionalità domina la maledizione della dimensionalità — le distanze tra i vicini diventano non informative — e un modello parametrico come la regressione logistica o Naive Bayes è la scelta migliore.
Limiti e considerazioni
- Sensibile alla scalatura delle feature; senza standardizzazione, le feature su larga scala dominano la distanza.
- Degrada rapidamente in alte dimensioni (maledizione della dimensionalità), dove le distanze tra i vicini perdono significato.
- Ogni previsione richiede la scansione dell'intero set di addestramento, il che è lento in fase di previsione su grandi quantità di dati.
- Richiede almeno una dimensione campionaria moderata; in campioni piccoli le distanze tra i vicini più prossimi non sono significative.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Concettualmente semplice e facile da spiegare: nessuna equazione in fase di addestramento, i dati sono il modello.
- Non parametrico — non fa alcuna assunzione sulla distribuzione sottostante.
- Gestisce naturalmente problemi multi-classe e confini decisionali complessi e non lineari.
- Funziona sia per la classificazione che per la regressione con la stessa idea di base.
Applicazioni
- Classificazione di dati tabulari in due o più categorie.
- Previsione numerica (regressione) mediante la media degli esempi più vicini.
- Una base di riferimento semplice e interpretabile prima di provare modelli più complessi.
- Riconoscimento di pattern in cui la somiglianza con esempi noti guida la decisione.
Come funziona
Come funziona
Per una nuova osservazione, il KNN misura la sua distanza da ogni esempio di addestramento, tipicamente usando la distanza euclidea tra le feature. Poiché la distanza è sensibile alla scala, le feature devono essere standardizzate per prime — altrimenti una variabile misurata su una grande scala numerica dominerebbe il calcolo e distorcerebbe quali vicini sono considerati i più vicini.
Formula
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}I k punti di addestramento con le distanze più piccole dalla nuova osservazione vengono selezionati come suoi vicini. Il valore di k controlla quanto sia locale la decisione: un k piccolo segue da vicino i dati ma è sensibile al rumore, mentre un k più grande leviga il confine. k dovrebbe essere scelto tramite cross-validazione (ad esempio, il metodo del gomito) piuttosto che stimato.
I vicini decidono la previsione: per la classificazione il nuovo punto assume la classe più comune tra i suoi k vicini (un voto a maggioranza), e per la regressione assume la media dei loro valori. Questo rende il metodo facile da capire, ma ogni previsione richiede la scansione del set di addestramento.
Formula
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}Errori comuni
- Saltare la standardizzazione delle feature, in modo che una variabile su larga scala controlli silenziosamente la distanza.
- Scegliere k a mano invece di selezionarlo con la cross-validazione.
- Applicare il KNN con molte feature e poche osservazioni, dove il rapporto dimensione/campione lo rende inefficace.
- Riportare solo l'accuratezza invece di precisione, richiamo, F1 e una matrice di confusione.
Domande frequenti
Come scelgo il valore di k?
k dovrebbe essere selezionato tramite cross-validazione piuttosto che stimato — ad esempio provando un intervallo di valori e usando il metodo del gomito per trovare dove l'errore smette di migliorare. Un k piccolo segue da vicino i dati ma è sensibile al rumore, mentre un k più grande leviga il confine decisionale.
Perché devo standardizzare le feature?
Il KNN decide chi è il 'più vicino' usando la distanza, che è sensibile alla scala. Se una feature è su una scala numerica molto più grande delle altre, domina la distanza e distorce l'insieme dei vicini. La standardizzazione delle feature (ad esempio con uno StandardScaler) è necessaria affinché ogni feature contribuisca equamente.
Perché il KNN ha difficoltà con molte feature?
Negli spazi ad alta dimensionalità tutti i punti diventano approssimativamente equidistanti — la maledizione della dimensionalità — quindi i vicini 'più vicini' non sono più significativamente vicini. Le prestazioni del KNN diminuiscono rapidamente, e un modello parametrico come Naive Bayes o la regressione logistica è solitamente preferibile. Mantenere p molto più piccolo di n aiuta.
C'è una fase di addestramento?
Non nel senso usuale. Il KNN è basato su istanze (lazy): memorizza semplicemente i dati di addestramento e svolge tutto il lavoro in fase di previsione, quando calcola le distanze per trovare i vicini più prossimi di un nuovo punto.
Metodi correlati
Fonti
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Apri il riferimento DOICopiato.