“Se cammina come un’anatra e starnazza come un’anatra, allora probabilmente è un’anatra.”
Data una regione locale dello spazio delle feature centrata in e di volume , la massa di probabilità contenuta in è approssimabile come e può essere stimata in modo non parametrico da un campione di dimensione tramite:
dove indica il numero di osservazioni di training che cadono in .
Un classificatore K-Nearest Neighbors (KNN) richiede quattro elementi:
- Un insieme di osservazioni etichettate;
- Una metrica di distanza o prossimità per calcolare la similarità tra istanze;
- L’iperparametro , ovvero il numero di vicini più prossimi;
- Una regola di decisione per combinare le etichette dei vicini (es. voto di maggioranza semplice o pesato per l’inverso del quadrato della distanza).
Voting KNN
Fissando il volume locale e contando quanti punti di ciascuna classe cadono nella regione, possiamo inserire la stima di densità e la probabilità a priori nella regola di decisione di Bayes:
Semplificando i termini si ottiene la classica regola di maggioranza:
Volumetric KNN
Viceversa, fissando il numero di vicini per ciascuna classe e lasciando variare il volume dell’ipersfera centrata in che racchiude i vicini della classe , si ha :
Poiché il volume di un’ipersfera è monotono crescente rispetto al raggio (la distanza dal -esimo vicino della classe ):
Considerazioni Pratiche
- Scelta della metrica: Per documenti o vettori sparsi ad alta dimensionalità, la cosine similarity è preferibile alla distanza Euclidea.
- Preprocessing e Scaling: La standardizzazione (media zero e deviazione standard unitaria) è indispensabile per evitare che le feature con scala numerica maggiore dominino il calcolo delle distanze.
- Scelta di : Se è troppo piccolo il classificatore è molto sensibile al rumore locale (alta varianza); se è troppo grande l’intorno include osservazioni di altre classi (alto bias).
- Costo computazionale: Essendo un algoritmo lazy (memory-based), KNN non ha costo di training parametrico e genera confini decisionali non lineari arbitrari, ma la predizione naive richiede tempo .
Migliorare l’Efficienza di KNN
- Indicizzazione Spaziale e Ricerca Approssimata: Strutture dati multidimensionali (-d trees, ball trees), Fast Approximate Nearest Neighbors (ANN) o Locality-Sensitive Hashing (LSH).
- Condensing: Selezionare un sottoinsieme ridotto di prototipi che mantenga invariata la frontiera decisionale.
- Editing: Rimuovere i punti rumorosi o sovrapposti per accelerare l’inferenza e regolarizzare i confini tra classi.