Classificazione e k-nearest neighbors

Dopo la regressione (Regressione lineareNell'apprendimento supervisionato si impara una funzione $F(x)$ dagli esempi $(x,y)$: regressione se $y$ è continua, classificazione se è categorica. Il modello lineare è $F_\beta(x)=\beta_0+\beta_1x_1+\dots+\beta_px_p=X\beta$ (con una colonna di uni per $\beta_0$) e i parametri si scelgono minimizzando l'errore quadratico medio $\mathrm{MSE}=\frac1n\sum_i(y_i-F_\beta(x_i))^2$, funzione convessa dei parametri. Annullando il gradiente di $J(\beta)=|y-X\beta|^2$ si ottengono le equazioni normali $X^TX\beta=X^Ty$ e la soluzione dei minimi quadrati ordinari $\beta=(X^TX)^{-1}X^Ty$. Il coefficiente di determinazione $R^2=1-SS_{res}/SS_{tot}$ misura la qualità del fit (0 = come la media, negativo = peggio della media). Un modello va valutato su un test set mai usato per addestrare: l'errore sul training è ottimistico e un polinomio di grado alto lo azzera senza generalizzare.Regressione lineare →) si passa al secondo tipo di problema supervisionato, la classificazione. La si introduce con il metodo più semplice, il k-nearest neighbors (k-NN), che non ha parametri da addestrare e mostra bene i concetti di iperparametro, underfitting e overfitting già visti in Overfitting, ridge regression e cross-validationUna buona prestazione sul training non basta: serve stimare quella su dati nuovi. La cross-validation (K-fold: $k$ parti, ciascuna a turno come test, errore medio; Monte Carlo: $k$ divisioni casuali con quota di test $q$; leave-one-out se $k=n$) evita di dipendere da una sola divisione casuale. L'errore atteso si scompone in $\text{bias}^2+\text{varianza}+\sigma^2$: i modelli semplici fanno underfitting (bias alto), quelli complessi overfitting (varianza alta). La regolarizzazione aggiunge alla perdita una penalità: la ridge regression minimizza $|y-X\beta|^2+\lambda\sum_{j\ge1}\beta_j^2$ e ha soluzione $\beta=(X^TX+\lambda\tilde I)^{-1}X^Ty$ (l'intercetta non si penalizza, le feature si standardizzano): riduce i coefficienti, rende l'inversa stabile con feature collineari, e $\lambda$ è un iperparametro scelto con la validazione (cross-validation annidata per non contaminare il test).Overfitting, ridge regression e cross-validation →. Le metriche di valutazione sono approfondite in Metriche di classificazioneIn classificazione binaria ogni previsione è vero positivo (TP), vero negativo (TN), falso positivo (FP, errore di tipo I) o falso negativo (FN, errore di tipo II). Da queste quattro quantità: accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità $=\frac{TN}{TN+FP}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, e la loro media armonica $F_1=\frac{2PR}{P+R}$. Con dati sbilanciati l'accuracy inganna (un modello che predice sempre la classe maggioritaria ha 99%): si usano precision, recall, F1, ROC-AUC, la cross-validation stratificata e il riequilibrio con undersampling o oversampling (non SMOTE). Cambiando la soglia sulla probabilità si ottiene la curva ROC (TPR contro FPR) e l'area AUC. Approfondimento: non nel programma di Telecomunicazioni.Metriche di classificazione →; il modello probabilistico più usato è in Regressione logistica e softmaxLa regressione lineare non è adatta alla classificazione (valori fuori da [0,1], retta tirata dai punti lontani). La regressione logistica passa il predittore lineare dalla sigmoide $\sigma(z)=1/(1+e^{-z})$ e interpreta $\hat y=\sigma(x^T\beta)$ come $P(y=1\mid x)$: si predice la classe 1 se $\hat y\ge0{,}5$, cioè $x^T\beta\ge0$ (bordo lineare). L'errore quadratico dà una funzione non convessa; si usa la log-verosimiglianza negativa $-\sum[y\log\hat y+(1-y)\log(1-\hat y)]$, convessa, con gradiente $X^T(\hat y-y)$ e nessuna formula chiusa (discesa del gradiente). Per più classi: one-vs-one ($C(C-1)/2$ classificatori, voto), one-vs-all ($C$ classificatori, massima probabilità), o la softmax $p_c=e^{z_c}/\sum_ke^{z_k}$ con cross-entropia. Si può regolarizzare (ridge, LASSO, Elastic Net) e la cross-validation si fa stratificata. Approfondimento: non nel programma di Telecomunicazioni.Regressione logistica e softmax →. L'implementazione da zero è in Esercizio - k-nearest neighbors da zero sul dataset breast cancer.

Il problema di classificazione

Definizione (classificazione). Problema supervisionato in cui l'uscita $y$ è una variabile categorica: ogni osservazione appartiene a una di $C$ classi. Se $C=2$ la classificazione è binaria (per esempio spam o non spam); se $C>2$ è multiclasse (per esempio $C=3$ per le specie di iris: setosa, versicolor, virginica).

Esempio. Iris: ingressi $x$ = lunghezza e larghezza di sepali e petali; uscita $y\in\{\text{setosa},\text{versicolor},\text{virginica}\}$. Un caso estremo è Shazam: riconoscere una canzone da 3-4 secondi di audio, con $C\approx10^8$ classi; la soluzione è diventata possibile grazie a un forte lavoro di feature engineering (un'«impronta digitale» $x$ del segnale).

Finora i metodi di regressione (OLS, ridge, LASSO, Elastic Net) avevano tutti la stessa forma $F(x)=\beta_0+\beta_1x_1+\dots+\beta_px_p$. La classificazione serve a mostrare la varietà degli approcci: k-NN, modelli lineari con funzione sigmoide, SVM, alberi e foreste, reti neurali.

Valutare un classificatore

Le metriche di regressione (RMSE, $R^2$) non hanno senso per categorie. La più semplice è il tasso di classificazione (classification rate o accuracy): $$\text{accuracy}=\frac{\text{numero di previsioni corrette}}{\text{numero totale di previsioni}}.$$ Vale $1$ per un classificatore perfetto e circa $1/C$ per uno che sceglie a caso (in binaria $0{,}5$). La matrice di confusione ha una riga per classe vera (actual) e una colonna per classe prevista (predicted): la diagonale contiene le previsioni corrette.

Esempio. Con classi Cat, Dog, Horse: i gatti veri sono previsti 8 Cat, 1 Dog, 1 Horse; i cani 2 Cat, 10 Dog, 0 Horse; i cavalli 0 Cat, 2 Dog, 8 Horse. La diagonale vale $8+10+8=26$ su $10+12+10=32$ casi: accuracy $=26/32=0{,}8125$.

Nel caso binario una classe è la positiva (la condizione di interesse: malattia presente, mail spam, transazione fraudolenta) e l'altra la negativa, e le previsioni si dividono in vero positivo (TP), vero negativo (TN), falso positivo (FP, falso allarme, errore di tipo I) e falso negativo (FN, mancata rilevazione, errore di tipo II). Da qui nascono accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità, precision e recall, trattate in Metriche di classificazioneIn classificazione binaria ogni previsione è vero positivo (TP), vero negativo (TN), falso positivo (FP, errore di tipo I) o falso negativo (FN, errore di tipo II). Da queste quattro quantità: accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità $=\frac{TN}{TN+FP}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, e la loro media armonica $F_1=\frac{2PR}{P+R}$. Con dati sbilanciati l'accuracy inganna (un modello che predice sempre la classe maggioritaria ha 99%): si usano precision, recall, F1, ROC-AUC, la cross-validation stratificata e il riequilibrio con undersampling o oversampling (non SMOTE). Cambiando la soglia sulla probabilità si ottiene la curva ROC (TPR contro FPR) e l'area AUC. Approfondimento: non nel programma di Telecomunicazioni.Metriche di classificazione →, dove si vede anche perché l'accuracy può ingannare.

k-nearest neighbors

Definizione (k-NN). «Una nuova osservazione viene assegnata alla classe più frequente tra i suoi $k$ vicini più prossimi nel training.» Algoritmo:

1. si sceglie il numero di vicini $k$;
2. si calcola la distanza tra il nuovo punto e tutti i punti del training (di solito la distanza euclidea);
3. si selezionano i $k$ punti più vicini;
4. si predice: per la classificazione la classe più frequente tra i $k$ (voto di maggioranza); per la regressione la media (o la media pesata) dei valori $y$ dei $k$ vicini.

Esempio. Si abbiano 8 punti nel piano: classe R in $(0{,}5;\,0)$, $(0;\,0{,}8)$, $(3;\,3)$, $(-3;\,2)$; classe B in $(-1;\,0)$, $(0;\,-1{,}2)$, $(1{,}3;\,0)$, $(-2;\,-3)$. Il nuovo punto è $q=(0,0)$. Le distanze euclidee dai primi cinque punti più vicini sono: $(0{,}5;0)\to0{,}5$ (R), $(0;0{,}8)\to0{,}8$ (R), $(-1;0)\to1$ (B), $(0;-1{,}2)\to1{,}2$ (B), $(1{,}3;0)\to1{,}3$ (B). Le altre tre distanze sono molto più grandi: $(3;3)\to\sqrt{9+9}=\sqrt{18}=4{,}24$ (R), $(-3;2)\to\sqrt{9+4}=\sqrt{13}=3{,}61$ (R), $(-2;-3)\to\sqrt{4+9}=\sqrt{13}=3{,}61$ (B), e non entrano in nessuno dei casi seguenti. Ogni distanza è calcolata con Pitagora: per esempio $(0{,}5;0)\to\sqrt{0{,}5^2+0^2}=0{,}5$ e $(0;-1{,}2)\to\sqrt{0^2+1{,}2^2}=1{,}2$. Ordinando le distanze $0{,}5<0{,}8<1<1{,}2<1{,}3<\dots$ si leggono i vicini in ordine. Quindi: con $k=1$ il vicino è R e $q$ è R; con $k=3$ i vicini sono R, R, B e vince R (2 voti contro 1); con $k=5$ sono R, R, B, B, B e vince B (3 contro 2). Il risultato dipende da $k$.

(Rossi: colore 1; blu: colore 2.)

Le distanze

La distanza è la misura di «vicinanza»; la più usata è la euclidea, la lunghezza del segmento tra due punti (Prodotto scalare, norma e angoliIl prodotto scalare aggiunge a uno spazio vettoriale lunghezze e angoli: norma, disuguaglianza di Cauchy-Schwarz, angolo tra vettori in R^n, ortogonalità, proiezione su una retta, aree e volumi con il determinante della matrice dei prodotti scalari.Prodotto scalare, norma e angoli →): $$d(A,B)=\sqrt{\sum_i(A_i-B_i)^2}\quad\text{(euclidea)},\qquad d(A,B)=\sum_i|A_i-B_i|\quad\text{(Manhattan, percorso a griglia)}.$$ Per testi si usa la similarità del coseno. Con altre metriche si estende il k-NN a dati particolari: per le serie temporali una scelta comune è il 1-NN con la Dynamic Time Warping (DTW), un algoritmo che confronta sequenze di lunghezza o frequenza di campionamento diverse allineandole, e fornisce un indice di somiglianza (solo teoria).

Esempio. Tra $A=(1,2)$ e $B=(4,6)$: euclidea $\sqrt{3^2+4^2}=\sqrt{25}=5$; Manhattan $|3|+|4|=7$.

Da dove vengono (norme). Un punto di $\mathbb R^p$ è un vettore e la distanza tra $A$ e $B$ è la norma del vettore differenza, $d(A,B)=\|A-B\|$ (Norma, distanza e prodotto scalare in RnIn Rⁿ la norma è |x| = √(x₁² + … + xₙ²) e la distanza tra x e y è |x − y|. Valgono la disuguaglianza triangolare |x + y| ≤ |x| + |y| e quella di Cauchy-Schwarz |x·y| ≤ |x||y|, con uguaglianza solo per vettori paralleli. Palle B(p,r] e cubi Q(p,r] si contengono a vicenda: B(p,r] ⊆ Q(p,r] ⊆ B(p,r√n]. Rette, piani, ellissi e cilindri si riconoscono dall'equazione (completando i quadrati).Norma, distanza e prodotto scalare in Rn →). Nel piano la norma euclidea $\|v\|_2=\sqrt{v_1^2+v_2^2}$ è il teorema di Pitagora sui cateti $|v_1|$ e $|v_2|$ (qui $3$ e $4$, ipotenusa $5$); in generale $\|v\|_2=\sqrt{v\cdot v}$, radice del prodotto scalareIl prodotto scalare aggiunge a uno spazio vettoriale lunghezze e angoli: norma, disuguaglianza di Cauchy-Schwarz, angolo tra vettori in R^n, ortogonalità, proiezione su una retta, aree e volumi con il determinante della matrice dei prodotti scalari.Prodotto scalare, norma e angoli → del vettore con sé stesso. La distanza di Manhattan è la norma $\|v\|_1=\sum_i|v_i|$ (somma dei valori assoluti, Valore assoluto (modulo)Il valore assoluto è la distanza di un numero da zero: definizione, proprietà, disuguaglianza triangolare e disequazioni con i moduli.Valore assoluto (modulo) →): è il cammino di chi può muoversi solo lungo gli assi, come in una città a griglia. Le due sono i casi $p=1$ e $p=2$ della norma $\|v\|_p=\big(\sum_i|v_i|^p\big)^{1/p}$; per $p\to\infty$ si ottiene $\|v\|_\infty=\max_i|v_i|$ (la differenza più grande). In ogni caso $d$ soddisfa le proprietà di una distanza: $d\ge0$, $d(A,B)=d(B,A)$, e la disuguaglianza triangolare $d(A,C)\le d(A,B)+d(B,C)$. Cambiare distanza cambia chi è «vicino»: l'insieme dei punti a distanza $1$ dall'origine è un cerchio per la norma 2, un quadrato ruotato (un rombo) per la norma 1, un quadrato con i lati paralleli agli assi per la norma $\infty$.

Il coseno serve per i testi perché ignora la lunghezza dei vettori e guarda solo la direzione: $\cos\theta=\dfrac{u\cdot v}{\|u\|\,\|v\|}$ (Prodotto scalare, norma e angoliIl prodotto scalare aggiunge a uno spazio vettoriale lunghezze e angoli: norma, disuguaglianza di Cauchy-Schwarz, angolo tra vettori in R^n, ortogonalità, proiezione su una retta, aree e volumi con il determinante della matrice dei prodotti scalari.Prodotto scalare, norma e angoli →). Due documenti con le stesse proporzioni tra le parole ma di lunghezza diversa danno $\cos\theta=1$ (stesso orientamento), anche se la loro distanza euclidea è grande.

La scala conta. Le distanze sommano differenze di feature con unità diverse: quella con numeri più grandi domina. Esempio: nuovo individuo $q=(30\text{ anni};\,40\,000\ \text{euro})$, $A=(31;\,60\,000)$ e $B=(60;\,40\,500)$. Distanze non scalate: $d(q,A)=\sqrt{1^2+20\,000^2}\approx20\,000$ e $d(q,B)=\sqrt{30^2+500^2}\approx501$: il più vicino è $B$, anche se ha 30 anni di differenza. Standardizzando (deviazioni standard $10$ anni e $10\,000$ €, Statistica per il machine learningI dati di un problema ML si organizzano nella matrice di progetto $X$ ($n$ osservazioni, $p$ variabili). La statistica serve a capirli, ripulirli e prepararli: i momenti (media $\mu$, varianza $\sigma^2$, asimmetria, curtosi), i quartili con lo scarto interquartile $\mathrm{IQR}=Q_3-Q_1$ (all'esame senza interpolazione), la moda per i dati categorici. Con queste quantità si imputano i dati mancanti (media o mediana), si eliminano le variabili costanti e si standardizza con lo z-score $z=(x-\mu)/\sigma$, usando sempre media e deviazione standard del solo training set.Statistica per il machine learning →): ogni differenza si divide per la deviazione standard della sua variabile, così diventa «quante deviazioni standard di distanza». $A$: $\frac{31-30}{10}=0{,}1$ e $\frac{60\,000-40\,000}{10\,000}=2$, distanza $\sqrt{0{,}1^2+2^2}=\sqrt{4{,}01}\approx2{,}00$. $B$: $\frac{60-30}{10}=3$ e $\frac{40\,500-40\,000}{10\,000}=0{,}05$, distanza $\sqrt{3^2+0{,}05^2}=\sqrt{9{,}0025}\approx3{,}00$. Ora il più vicino è $A$ (l'ordine si è invertito perché prima la differenza in euro, in numero, valeva 20 000 e quella in anni 1: la distanza era in pratica solo una differenza di stipendio). Le feature vanno quindi scalate (e quelle irrilevanti eliminate) prima di usare il k-NN.

$k$ è un iperparametro: underfitting e overfitting

Il numero di vicini $k$ non si impara dai dati, si sceglie (iperparametro) e cambia il comportamento del modello:

• $k=1$: il bordo tra le classi segue ogni punto, anche quelli rumorosi: modello molto flessibile, errore di training minimo ma varianza alta (overfitting).
• $k$ molto grande: ogni previsione è la classe più frequente di un intorno enorme (al limite $k=n$ si predice sempre la classe maggioritaria): bordo liscio, bias alto (underfitting).

Perché $k$ grande riduce la varianza (passaggi, caso della regressione). La previsione è la media dei $k$ valori vicini, $\hat y=\frac1k\sum_{j=1}^ky_j$. Supponiamo che ciascun $y_j$ sia il valore vero della funzione più un rumore con media $0$ e varianza $\sigma^2$, e che i rumori dei vari vicini siano indipendenti. Il valore atteso della media è la media dei valori attesi (Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →, linearità). La varianza della media è, per variabili indipendenti, $\operatorname{Var}\big(\frac1k\sum y_j\big)=\frac1{k^2}\sum\operatorname{Var}(y_j)=\frac{k\sigma^2}{k^2}=\frac{\sigma^2}{k}$ (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →: una costante $a$ esce dalla varianza come $a^2$). Quindi con $k=1$ la previsione ha tutta la varianza $\sigma^2$ del rumore (segue il rumore del singolo vicino), con $k=30$ solo $\sigma^2/30$. Il prezzo è il bias: i $k$ vicini sono più lontani da $x$, quindi i loro valori veri differiscono da quello in $x$ e la media è sistematicamente spostata. Il compromesso bias-varianza decide il $k$ migliore.

Si sceglie $k$ con la validazione (Overfitting, ridge regression e cross-validationUna buona prestazione sul training non basta: serve stimare quella su dati nuovi. La cross-validation (K-fold: $k$ parti, ciascuna a turno come test, errore medio; Monte Carlo: $k$ divisioni casuali con quota di test $q$; leave-one-out se $k=n$) evita di dipendere da una sola divisione casuale. L'errore atteso si scompone in $\text{bias}^2+\text{varianza}+\sigma^2$: i modelli semplici fanno underfitting (bias alto), quelli complessi overfitting (varianza alta). La regolarizzazione aggiunge alla perdita una penalità: la ridge regression minimizza $|y-X\beta|^2+\lambda\sum_{j\ge1}\beta_j^2$ e ha soluzione $\beta=(X^TX+\lambda\tilde I)^{-1}X^Ty$ (l'intercetta non si penalizza, le feature si standardizzano): riduce i coefficienti, rende l'inversa stabile con feature collineari, e $\lambda$ è un iperparametro scelto con la validazione (cross-validation annidata per non contaminare il test).Overfitting, ridge regression e cross-validation →). Esempio (dal laboratorio, iris con due sole variabili: lunghezza e larghezza del sepalo). Tasso di errata classificazione medio su 200 divisioni casuali $80\%/20\%$ stratificate:

L'errore scende, ha il minimo vicino a $k=30$ e poi risale, come nelle slide. (Con $k=100$ ci sono 120 punti di training: ogni previsione si basa su quasi tutto il training.)

Caratteristiche del k-NN

• Apprendimento basato su istanze (instance-based, memory-based): non c'è un modello esplicito, le nuove osservazioni si confrontano con le istanze memorizzate. Perciò è poco adatto a dispositivi con poca memoria.
• Apprendimento «pigro» (lazy): non c'è una vera fase di addestramento; il costo computazionale è tutto nella predizione. Ottimo per soluzioni adattive e quando si parte con pochi dati (basta aggiungere punti), poco adatto quando la previsione deve essere veloce.
• Lento sui dataset grandi (calcola le distanze per ogni nuova previsione): con $n$ punti di training e $p$ feature, ogni distanza costa $O(p)$ operazioni, quindi $O(np)$ per tutte; per scegliere i $k$ più piccoli si può ordinare (costo $O(n\log n)$, Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →) o scandire una sola volta tenendo i $k$ migliori, $O(nk)$ (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →, Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →). Il costo cresce linearmente col training e si paga a ogni predizione, non una volta sola; sensibile a feature irrilevanti (selezione o scala delle feature essenziali); debole in alta dimensione.

La maledizione della dimensionalità

Definizione (curse of dimensionality). L'insieme dei problemi che compaiono in spazi con molte dimensioni: aumentando il numero di feature i dati si comportano in modo inatteso e molti metodi diventano meno efficienti.

Un modo per vederlo: i punti del training sono distribuiti uniformemente in un cubo unitario di dimensione $d$. Per catturare una frazione $r$ dei punti con un cubo (un «intorno») bisogna prendere uno spigolo di lunghezza $r^{1/d}$ (perché il volume di un cubo di spigolo $\ell$ è $\ell^d$, e si impone $\ell^d=r$). Per $r=10\%$:

Il calcolo, passo per passo, per $d=10$: si impone $\ell^{10}=0{,}1$; si prende la radice decima, $\ell=0{,}1^{1/10}=e^{\ln(0{,}1)/10}=e^{-2{,}3026/10}=e^{-0{,}23026}=0{,}794$ (si passa dal logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo → perché la radice $d$-esima di un numero minore di $1$ è comoda da calcolare come esponenziale di $\ln(r)/d$). Per $d\to\infty$ l'esponente $\ln(0{,}1)/d\to0$ e quindi $\ell\to e^0=1$ (Limiti di successioniUna successione ha limite l se, da un certo indice in poi, i suoi termini stanno vicini a l quanto si vuole; definizioni con epsilon, limiti infiniti e unicità.Limiti di successioni →): lo spigolo tende a coprire l'intera coordinata. Già a $d=10$ per avere il 10% dei punti serve un intorno che copre quasi l'80% di ogni coordinata: i «vicini» non sono più locali, e la distanza perde significato (tutti i punti sono lontani quasi allo stesso modo).

Per questo il k-NN si accompagna a selezione delle feature o riduzione della dimensione (Analisi delle componenti principali (PCA)Con $p>3$ variabili non si può disegnare il dataset. La PCA (analisi delle componenti principali) lo proietta su pochi assi ortogonali, le componenti principali: dopo aver centrato (e di solito standardizzato) i dati, le direzioni sono gli autovettori della matrice di covarianza $S=\frac1{n-1}X_c^TX_c$ ordinati per autovalore $\lambda_1\ge\lambda_2\ge\dots$; $\lambda_k$ è la varianza lungo la componente $k$ e $\lambda_k/\sum\lambda_j$ la frazione spiegata (scree plot). Trovare la retta che minimizza le distanze dai punti equivale a massimizzare la varianza delle proiezioni (Pitagora). È lineare e conserva la struttura globale, non quella locale; t-SNE e UMAP sono alternative non lineari solo per visualizzare. Approfondimento: non nel programma di Telecomunicazioni.Analisi delle componenti principali (PCA) →).

Ingressi categorici: one-hot encoding

Oltre alle uscite, anche gli ingressi possono essere categorici. Codificarli con numeri interi (label encoding: Apple $=1$, Chicken $=2$, Broccoli $=3$) introduce un ordine e distanze inventate: Apple e Broccoli risulterebbero distanti $2$, Apple e Chicken $1$. Con l'one-hot encoding ogni categoria diventa un vettore binario con un solo $1$: Apple $=[1,0,0]$, Chicken $=[0,1,0]$, Broccoli $=[0,0,1]$ (ciascuna diventa una nuova colonna), e tutte le coppie di categorie hanno la stessa distanza euclidea $\sqrt2$. Con $m$ categorie si ottengono $m$ colonne (o $m-1$ eliminandone una, perché la somma è sempre $1$: drop_first=True in pandas).

Classificare un target continuo

A volte conviene passare da un problema di regressione a uno di classificazione: si discretizza il target continuo in intervalli, ciascuno dei quali è una classe (per esempio prezzi a, b, c per fasce di valori).

Codice

import numpy as np
def knn_predict(X_train, y_train, x, k):
    d = np.linalg.norm(X_train - x, axis=1)        # distanze euclidee da x a tutti i punti
    nearest = np.argsort(d)[:k]                    # indici dei k più vicini
    values, counts = np.unique(y_train[nearest], return_counts=True)
    return values[np.argmax(counts)]               # classe più frequente

# con scikit-learn: KNeighborsClassifier(n_neighbors=5).fit(X_train, y_train).predict(X_test)

Con np.argmax sui conteggi un pareggio tra classi si risolve in favore della prima in ordine alfabetico: con $C=2$ conviene scegliere $k$ dispari.

Errori tipici

• Usare il k-NN senza standardizzare le feature: la variabile con la scala più grande decide tutto.
• Standardizzare con media e deviazione standard calcolate sul dataset intero invece che sul solo training.
• Scegliere $k$ guardando l'errore sul training: per $k=1$ è sempre (quasi) zero.
• Usare il label encoding per categorie senza ordine.
• Dimenticare che il k-NN non ha training ma ha un costo alto in predizione e occupa la memoria di tutto il training.