Simone De Bonis
Simone De Bonis
← Torna al Blog
Data Science27 gennaio 2023· 5 min di lettura

K-Nearest Neighbors (KNN): Intuizione Probabilistica e Geometrica

Derivazione di Voting KNN e Volumetric KNN a partire dalla stima non parametrica di densità e dal classificatore di Bayes, con tecniche di ottimizzazione.

#Data Science#Machine Learning#Teoria#Classificazione

“Se cammina come un’anatra e starnazza come un’anatra, allora probabilmente è un’anatra.”

Data una regione locale dello spazio delle feature L(X)L(X) centrata in XX e di volume vv, la massa di probabilità contenuta in L(X)L(X) è approssimabile come p(X)vp(X)v e può essere stimata in modo non parametrico da un campione di dimensione NN tramite:

p^(X)v=k(X)N  ⟹  p^(X)=k(X)Nv\hat{p}(X)v = \frac{k(X)}{N} \implies \hat{p}(X) = \frac{k(X)}{Nv}

dove k(X)k(X) indica il numero di osservazioni di training che cadono in L(X)L(X).

Un classificatore K-Nearest Neighbors (KNN) richiede quattro elementi:

  1. Un insieme di osservazioni etichettate;
  2. Una metrica di distanza o prossimità per calcolare la similarità tra istanze;
  3. L’iperparametro kk, ovvero il numero di vicini più prossimi;
  4. Una regola di decisione per combinare le etichette dei kk vicini (es. voto di maggioranza semplice o pesato per l’inverso del quadrato della distanza).

Voting KNN

Fissando il volume locale vv e contando quanti punti di ciascuna classe ωi\omega_i cadono nella regione, possiamo inserire la stima di densità p^(X∣ωi)=k(X∣ωi)Niv\hat{p}(X|\omega_i) = \frac{k(X|\omega_i)}{N_i v} e la probabilità a priori p(ωi)=NiNp(\omega_i) = \frac{N_i}{N} nella regola di decisione di Bayes:

g(X)={ω1se N1Nk(X∣ω1)N1v>N2Nk(X∣ω2)N2vω2se N1Nk(X∣ω1)N1v<N2Nk(X∣ω2)N2vg(X) = \begin{cases} \omega_1 & \text{se } \frac{N_1}{N}\frac{k(X|\omega_1)}{N_1 v} > \frac{N_2}{N}\frac{k(X|\omega_2)}{N_2 v} \\ \omega_2 & \text{se } \frac{N_1}{N}\frac{k(X|\omega_1)}{N_1 v} < \frac{N_2}{N}\frac{k(X|\omega_2)}{N_2 v} \end{cases}

Semplificando i termini si ottiene la classica regola di maggioranza:

g(X)={ω1se k(X∣ω1)>k(X∣ω2)ω2se k(X∣ω1)<k(X∣ω2)g(X) = \begin{cases} \omega_1 & \text{se } k(X|\omega_1) > k(X|\omega_2) \\ \omega_2 & \text{se } k(X|\omega_1) < k(X|\omega_2) \end{cases}

Volumetric KNN

Viceversa, fissando il numero di vicini kk per ciascuna classe e lasciando variare il volume vi(X)v_i(X) dell’ipersfera centrata in XX che racchiude i kk vicini della classe ωi\omega_i, si ha p^(X∣ωi)=kNivi(X)\hat{p}(X|\omega_i) = \frac{k}{N_i v_i(X)}:

g(X)={ω1se N1NkN1v1(X)>N2NkN2v2(X)ω2se N1NkN1v1(X)<N2NkN2v2(X)g(X) = \begin{cases} \omega_1 & \text{se } \frac{N_1}{N}\frac{k}{N_1 v_1(X)} > \frac{N_2}{N}\frac{k}{N_2 v_2(X)} \\ \omega_2 & \text{se } \frac{N_1}{N}\frac{k}{N_1 v_1(X)} < \frac{N_2}{N}\frac{k}{N_2 v_2(X)} \end{cases}

Poiché il volume vi(X)v_i(X) di un’ipersfera è monotono crescente rispetto al raggio d(X,KNNi)d(X, \text{KNN}_i) (la distanza dal kk-esimo vicino della classe ii):

g(X)={ω1se v2(X)>v1(X)  ⟺  d(X,KNN2)>d(X,KNN1)ω2se v2(X)<v1(X)  ⟺  d(X,KNN2)<d(X,KNN1)g(X) = \begin{cases} \omega_1 & \text{se } v_2(X) > v_1(X) \iff d(X, \text{KNN}_2) > d(X, \text{KNN}_1) \\ \omega_2 & \text{se } v_2(X) < v_1(X) \iff d(X, \text{KNN}_2) < d(X, \text{KNN}_1) \end{cases}

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 kk: Se kk è troppo piccolo il classificatore è molto sensibile al rumore locale (alta varianza); se kk è 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 O(Nd)O(Nd).

Migliorare l’Efficienza di KNN

  1. Indicizzazione Spaziale e Ricerca Approssimata: Strutture dati multidimensionali (kk-d trees, ball trees), Fast Approximate Nearest Neighbors (ANN) o Locality-Sensitive Hashing (LSH).
  2. Condensing: Selezionare un sottoinsieme ridotto di prototipi che mantenga invariata la frontiera decisionale.
  3. Editing: Rimuovere i punti rumorosi o sovrapposti per accelerare l’inferenza e regolarizzare i confini tra classi.
← Torna al Blog
Condividi articolo: