Skip to content
Torna ai risultati

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

Dimensione del carattere

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

1

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}
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.

3

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

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    Apri il riferimento DOI
    Copiato.