La cluster analysis raggruppa osservazioni simili senza etichette predefinite (apprendimento non supervisionato). Misura la somiglianza con una distanza e forma gruppi (cluster) compatti e separati. Questa scheda allena le distanze, l’algoritmo k-means e il clustering gerarchico.
1. Distanza euclidea
Esercizio. Calcolare la distanza euclidea tra i punti A=(1,2) e B=(4,6).
d_E(A,B)=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2}=\sqrt{(4-1)^2+(6-2)^2}=\sqrt{9+16}=\sqrt{25}=5.
La distanza euclidea è la lunghezza del segmento “in linea d’aria”: la misura di dissimilarità più usata nel clustering.
2. Distanza di Manhattan
Esercizio. Calcolare la distanza di Manhattan tra gli stessi punti A=(1,2) e B=(4,6).
La distanza di Manhattan somma le differenze assolute delle coordinate:
d_M(A,B)=|x_B-x_A|+|y_B-y_A|=|4-1|+|6-2|=3+4=7.
È il percorso “a isolati” (solo movimenti ortogonali). Diversa dall’euclidea (5): la scelta della distanza cambia i cluster ottenuti.
3. Assegnazione ai centroidi (k-means)
Esercizio. Con centroidi C_1=(1,1) e C_2=(5,5), assegnare il punto P=(2,3) al cluster più vicino (distanza euclidea).
d(P,C_1)=\sqrt{(2-1)^2+(3-1)^2}=\sqrt{1+4}=\sqrt5=2{,}24, d(P,C_2)=\sqrt{(2-5)^2+(3-5)^2}=\sqrt{9+4}=\sqrt{13}=3{,}61.
P è più vicino a C_1 → assegnato al cluster 1. Nel k-means ogni punto va al centroide più vicino: è il passo di assegnazione.
4. Aggiornamento del centroide
Esercizio. Un cluster contiene i punti (2,3), (4,5), (3,4). Calcolare il nuovo centroide.
Il centroide è la media delle coordinate dei punti del cluster:
C=\left(\dfrac{2+4+3}{3},\ \dfrac{3+5+4}{3}\right)=\left(\dfrac{9}{3},\ \dfrac{12}{3}\right)=(3,\ 4).
Nel k-means, dopo l’assegnazione si ricalcolano i centroidi come media dei punti. Assegnazione e aggiornamento si alternano fino a convergenza.
5. Convergenza del k-means
Esercizio. Descrivere il ciclo del k-means e quando si ferma.
Il k-means itera due passi:
- assegnazione: ogni punto al centroide più vicino;
- aggiornamento: ogni centroide = media dei suoi punti.
Si ripete finché le assegnazioni non cambiano più (centroidi stabili). Il k-means converge sempre, ma a un minimo locale: l’esito dipende dai centroidi iniziali, perciò si ripete con inizializzazioni diverse e si tiene la migliore.
6. Scelta del numero di cluster
Esercizio. Come si sceglie k nel k-means con il metodo del gomito?
Si calcola la dispersione interna (somma dei quadrati intra-cluster, WCSS) per vari k:
\text{WCSS}(k)=\sum_{\text{cluster}}\sum_{\text{punti}}d^2(\text{punto},\text{centroide}).
La WCSS cala sempre all’aumentare di k, ma con rendimenti decrescenti. Il “gomito” della curva — dove la diminuzione rallenta bruscamente — indica il k ottimale: oltre, aggiungere cluster non migliora molto. È un criterio euristico ma molto usato.
7. Una iterazione completa di k-means
Esercizio. Dati i punti:
e i centroidi iniziali:
eseguire un passo di assegnazione e aggiornamento.
Calcoliamo le distanze euclidee.
Per A:
Quindi A va nel cluster 1.
Per B:
Quindi B va nel cluster 1.
Per C:
Quindi C va nel cluster 2.
Per D:
Quindi D va nel cluster 2.
Aggiorniamo i centroidi:
Risultato:
Questo esempio mostra l’alternanza essenziale del k-means: prima si assegnano i punti, poi si ricalcolano i centroidi. Fermarsi dopo l’assegnazione non conclude l’iterazione.
8. Silhouette di un punto
Esercizio. Per un punto P, la distanza media dai punti del proprio cluster è a(P)=2 e la distanza media dal cluster più vicino è b(P)=5. Calcolare il coefficiente di silhouette.
La silhouette è:
Sostituendo:
Risultato:
Il valore è positivo e abbastanza alto: il punto è più vicino al proprio cluster che agli altri. In generale:
- s\approx 1 indica assegnazione molto coerente;
- s\approx 0 indica punto di confine;
- s<0 suggerisce possibile assegnazione errata.
La silhouette è utile perché valuta compattezza e separazione nello stesso indice.
9. Linkage gerarchico
Esercizio. Tre cluster hanno punti:
sulla retta reale. Calcolare la distanza tra A e B con single, complete e average linkage.
Le distanze punto-punto tra A e B sono:
Single linkage: distanza minima:
Complete linkage: distanza massima:
Average linkage: media delle distanze:
Risultato:
La scelta del linkage cambia la forma dei cluster: single tende a catene sottili, complete preferisce cluster compatti, average è un compromesso.
10. Standardizzazione prima delle distanze
Esercizio. Due osservazioni sono:
Perché la distanza euclidea grezza può essere fuorviante?
La distanza non standardizzata è:
La prima variabile domina quasi completamente la distanza. Se la prima variabile è misurata in euro e la seconda è un punteggio da 1 a 5, la scala numerica determina il cluster più del contenuto informativo.
Dopo standardizzazione:
ogni variabile contribuisce in unità di deviazione standard. La distanza diventa una misura di differenza relativa, non una conseguenza delle unità di misura.
Regola pratica: k-means, clustering gerarchico e metodi basati su distanza richiedono quasi sempre standardizzazione quando le variabili hanno scale diverse.
11. Outlier e k-means
Esercizio. Perché un outlier può spostare molto il centroide di un cluster?
Il centroide è una media. Se un cluster contiene:
il centroide è:
Se si aggiunge un outlier 100:
Il centroide si sposta lontano dalla zona densa dei dati. Per questo k-means è sensibile agli outlier: minimizza distanze quadratiche e usa medie. In presenza di outlier conviene valutare preprocessing robusto, k-medoids o metodi density-based.
Errori comuni
- Non standardizzare le variabili. Come in PCA, scale diverse distorcono le distanze: una variabile con range ampio domina il clustering.
- Confondere euclidea e Manhattan. Danno valori e cluster diversi; la scelta della metrica è parte del modello.
- Fidarsi di una sola inizializzazione del k-means. Converge a minimi locali: vanno provate più inizializzazioni.
- Scegliere k massimizzando la compattezza. Aumentare k riduce sempre la WCSS; serve il gomito o altri criteri, non il minimo assoluto.
- Ignorare outlier e linkage. Medie, distanze e regole di fusione possono cambiare molto il risultato anche a parità di dati.