Lezione 20Clustering e k-means

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

Argomenti trattati

1. Clustering: raggruppare osservazioni simili, come preprocessing o come obiettivo.
2. K-means: assegnazione e aggiornamento dei centroidi, funzione obiettivo, dipendenza dall'inizializzazione.
3. Quanti cluster: metodo del gomito e gap statistic.
4. Clustering gerarchico agglomerativo e divisivo.
5. Varianti a memoria limitata: k-means online e con buffer.

Teoria

• Clustering e k-meansIl clustering raggruppa osservazioni simili senza etichette, come preprocessing (un modello per ogni cluster) o come obiettivo (segmentazione clienti, organizzazione di documenti). K-means: si sceglie $K$, si inizializzano $K$ centroidi, si alterna assegnazione di ogni punto al centroide più vicino e aggiornamento di ogni centroide alla media dei suoi punti, fino a convergenza; minimizza $\mathrm{MSE}{\text{within}}=\frac1N\sum_k\sum{x_i\in C_k}|x_i-\mu_k|^2$ ma solo fino a un minimo locale, quindi dipende dall'inizializzazione. Il numero di cluster si sceglie col metodo del gomito (la dispersione cala sempre, si cerca dove rallenta) o con la gap statistic $\mathrm{Gap}(K)=E[\log W_K^{ref}]-\log W_K$ (si prende il più piccolo $K$ con $\mathrm{Gap}(K)\ge\mathrm{Gap}(K+1)-s_{K+1}$). Il clustering gerarchico agglomerativo parte da un cluster per punto e fonde i due più vicini (linkage single, complete, average, Ward) costruendo un dendrogramma; quello divisivo parte da un solo cluster. Programma di Telecomunicazioni: clustering.Clustering e k-means →

Esercizi

• Esercizio - k-means a mano e gap statistic su cinque gruppi
• Esercizio - Clustering gerarchico agglomerativo e divisivo
• Esercizio - Regressione lineare a tratti con k-means
• Esercizio - k-means online e con buffer a memoria limitata

Lezione precedente: Lezione 19 · Apprendimento non supervisionato e anomaly detection Lezione successiva: Lezione 21 · Laboratorio anomaly detection e clustering