Lezione 11Classificazione e k-nearest neighbors

Settimana: 4 · Fonte: slide del corso Machine Learning, Ingegneria dell'Automazione UniPD (lezione 11)

Argomenti trattati

1. Il problema di classificazione: classi, caso binario, bordo di decisione.
2. k-nearest neighbors: voto di maggioranza tra i $k$ vicini, distanza euclidea e di Manhattan, scelta di $k$ (bordi frastagliati contro underfitting), standardizzazione delle feature.
3. Maledizione della dimensionalità, ingressi categorici con one-hot encoding, kNN per la regressione.
4. Approfondimento: non nel programma di Telecomunicazioni.

Teoria

• 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 →

Lezione precedente: Lezione 10 · LASSO e discesa del gradiente Lezione successiva: Lezione 12 · Laboratorio di regolarizzazione