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 (Lezione 11 · Classificazione e k-nearest neighbors). 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 (Lezione 15 · Laboratorio kNN e regressione logistica).

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). 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$.

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{€})$, $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 →): $A\to(0{,}1;\,2)$, distanza $\approx2{,}00$; $B\to(3;\,0{,}05)$, distanza $\approx3{,}00$: ora il più vicino è $A$. 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).

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); 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\%$:

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.