Esercizio - k-means online e con buffer a memoria limitata

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

Testo (1° appello 2025, parte 3). Il k-means richiede di conservare in memoria tutti i punti per ricalcolare i centroidi. Si vogliono versioni più leggere.

1. K-means con buffer. Budget di memoria $M=m\times K$ ($m$ regolabile, per esempio $10$; $K$ numero di cluster): si tengono solo $M$ punti. Quando un nuovo punto è assegnato a un cluster, si ricampionano $M$ punti da tenere nel buffer tra i $M$ esistenti più il nuovo, e si aggiorna il centroide con i soli punti del buffer. Progettare la strategia di campionamento e addestrare sul dataset dell'esercizio sulla regressione a tratti (900 lotti).
2. K-means online. Si possono memorizzare solo i $K$ centroidi (e dei contatori). Quando arriva un punto assegnato a un cluster, aggiornare il centroide senza avere i punti del cluster.

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 → (aggiornamento dei centroidi, media incrementale, versioni a memoria limitata); la media come stima in Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →; dataset in Esercizio - Regressione lineare a tratti con k-means.

2. K-means online: la media incrementale

Un cluster ha $n$ punti con media $\mu$; arriva $x$ e viene assegnato. La nuova media è $$\mu_{\text{new}}=\frac{n\mu+x}{n+1}=\mu+\frac{x-\mu}{n+1}$$ (infatti $n\mu$ è la somma dei punti precedenti, a cui si aggiunge $x$ e si divide per il nuovo numero $n+1$). Si tengono solo $K$ centroidi $\mu_k$ e $K$ contatori $n_k$; il contatore si incrementa a ogni punto assegnato. È la regola della media incrementale: media pesata tra il vecchio centroide, con peso $n$, e il punto nuovo, con peso $1$.

Esempio. Centroide $(1;1)$ con $n=3$ punti e nuovo punto $(5;5)$: $\mu_{\text{new}}=\frac{3\cdot(1;1)+(5;5)}4=\frac{(8;8)}4=(2;2)$; alternativamente $(1;1)+\frac{(5;5)-(1;1)}4=(1;1)+(1;1)=(2;2)$.

Algoritmo. Inizializzazione: $K$ punti a caso come centroidi, contatori a $0$. Per ogni punto $x$ (e per più passate sui dati): $j=\arg\min_k\lVert x-\mu_k\rVert$; $\mu_j\leftarrow\frac{n_j\mu_j+x}{n_j+1}$; $n_j\leftarrow n_j+1$. Con $n_j=0$ il centroide diventa $x$ (il punto iniziale è dimenticato).

def update(centroids, counts, x):
    j = np.argmin(((centroids - x) ** 2).sum(axis=1))             # centroide più vicino
    centroids[j] = (counts[j] * centroids[j] + x) / (counts[j] + 1)
    counts[j] += 1

Risultato sui 900 lotti con $K=3$ e 10 passate (4 inizializzazioni diverse): i centroidi trovati sono $(29{,}95;\ 28{,}92)$, $(50{,}00;\ 35{,}30)$, $(70{,}02;\ 28{,}95)$, uguali (alla seconda cifra decimale) a quelli del k-means standard, con la stessa dispersione $W=21\,506$. Memoria: $3$ centroidi e $3$ contatori invece di $900$ punti. Il metodo è però più sensibile all'ordine in cui arrivano i punti e alle prime assegnazioni (i primi punti, quando i centroidi sono ancora lontani, vengono mediati nel centroide e lo spostano; per questo servono più passate o un tasso di aggiornamento che decresce).

1. K-means con buffer

Strategia di campionamento. L'obiettivo è che il buffer sia un campione rappresentativo (non distorto verso i punti recenti) del cluster. Il metodo corretto è il campionamento uniforme senza rimpiazzo dei $M$ punti tra i $M+1$ disponibili (buffer più nuovo punto): così ogni punto visto ha la stessa probabilità di restare nel buffer. (Il reservoir sampling generalizza questa idea in modo che dopo $t$ punti ciascuno sia nel buffer con probabilità $M/t$.) Ricampionare dando più peso ai punti recenti farebbe sbilanciare il centroide verso gli ultimi arrivati.

Procedura.

1. Si addestra il k-means standard sui dati iniziali (o si inizializza a caso) e per ogni cluster si tiene un buffer di al più $M=m\cdot K$ punti campionati a caso (con $m=10$ e $K=3$: $M=30$).
2. Per ogni nuovo punto $x$: cluster più vicino $j$; $x$ si aggiunge al buffer $j$; se il buffer supera $M$, se ne ricampionano $M$ a caso; il centroide $j$ diventa la media dei punti del buffer (i centroidi degli altri cluster non cambiano).

def update_with_point(self, x):
    j = np.argmin(((self.centroids - x) ** 2).sum(axis=1))
    buf = np.vstack([self.buffers[j], x])
    if len(buf) > self.M: buf = buf[np.random.choice(len(buf), self.M, replace=False)]   # campione uniforme
    self.buffers[j] = buf; self.centroids[j] = buf.mean(axis=0)

(Attenzione nella soluzione ufficiale: usare np.random.choice direttamente su una lista di vettori non funziona; si campionano gli indici e poi si indicizza.)

Risultato. Dopo l'inizializzazione, ciascun buffer contiene $30$ punti e i centroidi coincidono con quelli di prima (stesso k-means iniziale). Aggiungendo un flusso di $200$ nuovi punti (punti del dataset perturbati con rumore gaussiano di deviazione standard $0{,}3$) i centroidi si spostano un po' ($(29{,}91;\ 29{,}64)$, $(50{,}15;\ 35{,}83)$, $(70{,}16;\ 29{,}87)$): con soli $30$ punti nel buffer la media è più rumorosa di quella su centinaia di punti, ed è il prezzo della memoria ridotta: più grande è $m$, più il metodo si avvicina al k-means standard.

Confronto