Esercizio - Clustering gerarchico agglomerativo e divisivo

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

Testo (2° appello 2025, esercizi 4 e 6; laboratorio LAB6).

1. Scrivere lo pseudocodice del clustering gerarchico agglomerativo con la distanza media come criterio di fusione, implementarlo e applicarlo a un dataset sintetico con 4 cluster (100 punti, make_blobs(centers=4, cluster_std=0.2)).
2. Se il dataset ha $n$ campioni e si vogliono $m$ cluster, quante iterazioni servono?
3. Descrivere e implementare una versione divisiva (top-down): quale cluster dividere a ogni passo e con che criterio.
4. Eseguire a mano l'agglomerativo con linkage single, complete e average sui punti $A=1$, $B=2$, $C=6$, $D=7$, $E=15$ e la versione divisiva.

Teoria usata: 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 → (gerarchico, dendrogramma, linkage, k-means per la divisione); distanza euclidea in 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 →.

Pseudocodice agglomerativo (distanza media)

clusters = [[0], [1], ..., [n-1]]            # un cluster per campione
ripeti finché len(clusters) > m:
    per ogni coppia di cluster (Ci, Cj):
        d(Ci, Cj) = (1 / (|Ci| |Cj|)) * somma, su a in Ci e b in Cj, di ||a - b||
    scegli la coppia con d minima, unisci Ci e Cj in un solo cluster

Numero di iterazioni. Si parte con $n$ cluster e a ogni fusione ne resta uno in meno: per arrivare a $m$ cluster servono $n-m$ iterazioni. Con $n=100$ e $m=4$: 96. Per arrivare a un cluster unico: $n-1$. (Risposta esatta dell'appello: n_samples - n_clusters.)

Implementazione. Si conserva una matrice di assegnazione cmatrix con una riga per iterazione e una colonna per campione (riga $i$ = etichette dopo $i$ fusioni; la riga iniziale è $[0,1,\dots,n-1]$); le etichette finali sono cmatrix[-1]. La distanza media tra due cluster usa due cicli annidati: costo circa $O(n^3)$ in tutto (tra tutte le coppie di cluster a ogni passo).

def fit(self, X):
    clusters = [[i] for i in range(len(X))]
    for step in range(1, len(X) - self.n_clusters + 1):
        best, bd = None, np.inf
        for j in range(len(clusters)):
            for k in range(j + 1, len(clusters)):
                d = average_cluster_distance(X[clusters[j]], X[clusters[k]])
                if d < bd: best, bd = (j, k), d
        j, k = best; clusters[j] += clusters[k]; del clusters[k]      # fusione
        labels = np.zeros(len(X), int)
        for idx, cl in enumerate(clusters): labels[cl] = idx
        self.cmatrix[step] = labels

Con 4 gruppi molto compatti ($\sigma=0{,}2$) i 4 cluster finali coincidono con i gruppi veri.

Versione divisiva

Si parte da un unico cluster con tutti i punti. A ogni passo: (1) scelta del cluster da dividere: quello con la dispersione maggiore, per esempio la distanza media tra le coppie di punti del cluster, $\frac2{n(n-1)}\sum_{i<j}\lVert x_i-x_j\rVert$ (un cluster con un solo punto non si divide); (2) divisione del cluster in due con il k-means con $K=2$. Per ottenere $m$ cluster servono $m-1$ divisioni (non $n-m$).

for step in range(1, n_clusters):
    cid = max((c for c in clusters if len(clusters[c]) > 1), key=lambda c: avg_pairwise_dist(X[clusters[c]]))
    labels = KMeans(2).fit(X[clusters[cid]]).labels_
    clusters[new_id] = clusters[cid][labels == 1]; clusters[cid] = clusters[cid][labels == 0]

(Nota sulla soluzione ufficiale: nella classe KMeans dell'appello, se il ciclo di iterazioni esce alla prima iterazione per convergenza immediata, la variabile labels usata dopo il ciclo non è mai stata assegnata, mentre l'assegnazione iniziale è chiamata labels_: con inizializzazioni fortunate può dare un errore. Nel k-means del laboratorio labels è assegnato prima del ciclo e il problema non c'è.)

4. Esempio a mano: $A=1$, $B=2$, $C=6$, $D=7$, $E=15$

Distanze: $AB=1$, $AC=5$, $AD=6$, $AE=14$, $BC=4$, $BD=5$, $BE=13$, $CD=1$, $CE=9$, $DE=8$.

Single linkage (minimo): 1) $AB$ e $CD$ a distanza $1$ (si fondono; pari merito: prima $AB$, poi $CD$); 2) $\{A,B\}$-$\{C,D\}$: $\min(5,6,4,5)=4$; 3) $\{A,B,C,D\}$-$E$: $\min(14,13,9,8)=8$. Altezze del dendrogramma: $1,\ 1,\ 4,\ 8$.

Complete linkage (massimo): $AB=1$, $CD=1$; $\{A,B\}$-$\{C,D\}$: $\max(5,6,4,5)=6$; con $E$: $\max(14,13,9,8)=14$. Altezze $1,1,6,14$.

Average linkage (media): $AB=1$, $CD=1$; $\{A,B\}$-$\{C,D\}$: $\frac{5+6+4+5}4=5$; $\{C,D\}$-$E=\frac{9+8}2=8{,}5$ e $\{A,B\}$-$E=\frac{14+13}2=13{,}5$; il minimo tra $5$, $8{,}5$ e $13{,}5$ è $5$, quindi si fondono $\{A,B\}$ e $\{C,D\}$; ultima fusione $\{A,B,C,D\}$-$E$: $\frac{14+13+9+8}4=11$. Altezze $1,1,5,11$.

I tre linkage danno la stessa gerarchia (gruppi $\{A,B\}$, $\{C,D\}$, $\{E\}$ poi $\{A,B,C,D\}$) e diverse altezze. Il salto grande prima dell'ultima fusione ($5\to11$ in average, $4\to8$ in single) suggerisce $2$ cluster oltre a $\{A,B,C,D\}$ e $\{E\}$, o $3$ cluster ($\{A,B\}$, $\{C,D\}$, $\{E\}$) se si taglia prima.

Matrice di assegnazione (average, $n=5$, $m=1$): riga 0: $[0,1,2,3,4]$; dopo la fusione $AB$: $[0,0,1,2,3]$; dopo $CD$: $[0,0,1,1,2]$; dopo $\{AB\}\{CD\}$: $[0,0,0,0,1]$; finale: $[0,0,0,0,0]$ (sono $n-1=4$ fusioni).

Divisivo. Si parte con $\{A,B,C,D,E\}$; la distanza media tra coppie è $\frac{1+5+6+14+4+5+13+1+9+8}{10}=6{,}6$. Il k-means con $K=2$ divide in $\{A,B,C,D\}$ e $\{E\}$ (dispersione $W=26$: $\{1,2,6,7\}$ ha media $4$ e $W=9+4+4+9=26$; l'alternativa $\{A,B\}$, $\{C,D,E\}$ ha $W\approx49$). Poi il cluster con la dispersione maggiore è $\{A,B,C,D\}$ (distanza media $\frac{1+5+6+4+5+1}6=3{,}67$; $\{E\}$ ha un solo punto): si divide in $\{A,B\}$ e $\{C,D\}$. La gerarchia coincide con quella agglomerativa; in generale i due approcci possono dare risultati diversi.

Verifica

import numpy as np
x = np.array([1, 2, 6, 7, 15.]); D = np.abs(x[:, None] - x[None])
# average: (D[0,2]+D[0,3]+D[1,2]+D[1,3]) / 4 = 5 ; single: min = 4 ; complete: max = 6