Esercizio - k-nearest neighbors da zero sul dataset breast cancer

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (laboratorio LAB4, esercizio sul k-NN binario). Dataset breast cancer (569 campioni, 30 feature numeriche, target target $\in\{0,1\}$ con $212$ classi 0 e $357$ classi 1):

1. caricare i dati, costruire $X$ e $y$ e dividere con campionamento stratificato in training ($80\%$) e test;
2. scrivere una funzione k-NN che restituisca, oltre alla classe più frequente, la distanza media dai vicini, usando solo la distanza euclidea;
3. fare le previsioni sul test con $k=20$;
4. calcolare da zero accuracy, specificità, precision e recall e commentare; ripetere con feature standardizzate.

Teoria usata: Classificazione e k-nearest neighborsNella classificazione l'uscita $y$ è una categoria (con $C$ classi; $C=2$ è il caso binario). Il classificatore più semplice è il k-nearest neighbors: una nuova osservazione prende la classe più frequente (voto di maggioranza) tra i suoi $k$ vicini più prossimi nel training, con distanza euclidea $\sqrt{\sum(A_i-B_i)^2}$ o di Manhattan $\sum|A_i-B_i|$ (per la regressione si fa la media dei vicini). $k$ è un iperparametro: $k$ piccolo dà bordi frastagliati e overfitting, $k$ grande underfitting. È un metodo basato su istanze e «pigro» (nessun addestramento, costo alla predizione), sensibile a scala e feature irrilevanti e alla maledizione della dimensionalità; gli ingressi categorici si codificano con one-hot. Approfondimento: non nel programma di Telecomunicazioni.Classificazione e k-nearest neighbors → (algoritmo, distanza, scala delle feature); 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 →; standardizzazione in 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 →.

1. Divisione stratificata

Per ogni classe si mescolano gli indici e si prende l'$80\%$ per il training e il $20\%$ per il test, poi si ricompongono i due insiemi e si rimescolano: così in entrambi la proporzione tra le classi è quella del dataset (circa $37{,}3\%$ di classe 0). Con np.random.seed(0): training $454$ campioni ($169$ di classe 0 e $285$ di classe 1), test $115$ ($43$ e $72$).

2. k-NN con distanza media

Per ogni punto di test: (a) distanza euclidea $\sqrt{\sum_j(x_j-x'_j)^2}$ da tutti i punti di training; (b) indici dei $k$ più piccoli (np.argsort); (c) classe più frequente tra i loro target; (d) media delle $k$ distanze.

import numpy as np
def knn_with_dist(X_train, y_train, X_test, k):
    d = np.sqrt(((X_test[:, None] - X_train[None]) ** 2).sum(axis=2))   # (n_test, n_train)
    nearest = np.argsort(d, axis=1)[:, :k]
    labels = np.array([np.bincount(y_train[row]).argmax() for row in nearest])   # voto di maggioranza
    avg_dist = np.take_along_axis(d, nearest, axis=1).mean(axis=1)
    return labels, avg_dist

La distanza media dai vicini può servire come misura di confidenza: un punto lontano da tutti i suoi vicini (distanza media grande) è un caso incerto o un possibile outlier.

3-4. Risultati con $k=20$

Matrice di confusione (classe positiva $=1$): $TP=69$, $TN=37$, $FP=6$, $FN=3$ (totale $115$).

(Sono gli stessi valori del laboratorio.) Il classificatore trova il $96\%$ dei casi positivi (pochi falsi negativi), ma è meno sicuro sui negativi ($14\%$ dei negativi è classificato come positivo): con 30 feature su scale diverse le distanze sono dominate dalle poche feature con valori grandi.

Con standardizzazione. Le deviazioni standard delle feature vanno da $0{,}003$ a $569$ (area): la distanza euclidea dipende quasi solo da mean area e worst area. Standardizzando con media e deviazione standard del solo training: $TP=71$, $TN=39$, $FP=4$, $FN=1$, accuracy $0{,}9565$, specificità $0{,}907$, precision $0{,}947$, recall $0{,}986$. Tutte le metriche migliorano. Variando $k$ (standardizzato): accuracy $0{,}948$ per $k=1$, $0{,}957$ per $k=5$, $20$ e $50$: con feature standardizzate il risultato è poco sensibile a $k$ in questo intervallo.

Commento. Il k-NN è semplice ma sensibile alla scala; la scelta di $k$ e la standardizzazione sono parte del modello e vanno decise 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 →). Con un solo test di 115 punti una differenza di 1-2 punti percentuali non è significativa. L'esercizio successivo del laboratorio usa la regressione logistica sullo stesso dataset (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 →).