Clustering Algorithms

Executive summary

Quando un'organizzazione dispone di grandi quantità di dati ma non di etichette che li classifichino, diventa necessario individuare raggruppamenti naturali nelle informazioni per comprenderne la struttura sottostante. Questo articolo esamina in profondità le principali famiglie di metodi matematici utilizzati per suddividere automaticamente insiemi di dati in gruppi omogenei, analizzando cinque approcci fondamentali che si differenziano per le ipotesi sulla forma e sulla densità dei raggruppamenti. L'analisi evidenzia che nessun metodo è universalmente superiore: la scelta più efficace dipende dalla geometria dei dati, dalla presenza di rumore e dalla dimensionalità dello spazio di rappresentazione. Emerge inoltre che la valutazione della qualità dei risultati resta un problema aperto, poiché le metriche disponibili catturano aspetti complementari e talvolta contraddittori della struttura dei dati. L'articolo approfondisce infine le sfide specifiche poste dai dati ad alta dimensionalità, dove le nozioni tradizionali di distanza e vicinanza perdono significato statistico.

Background

Il clustering costituisce uno dei problemi centrali dell'apprendimento non supervisionato: dato un insieme di osservazioni $X = {x_1, x_2, \ldots, x_n}$ con $x_i \in \mathbb{R}^d$, l'obiettivo è partizionare $X$ in $k$ gruppi $C_1, C_2, \ldots, C_k$ tali che le osservazioni all'interno di ciascun gruppo siano più simili tra loro rispetto a quelle appartenenti a gruppi diversi. A differenza della classificazione supervisionata, non si dispone di etichette note: la struttura deve emergere esclusivamente dalla geometria e dalla distribuzione dei dati. Questa assenza di supervisione rende il problema intrinsecamente mal definito, poiché la nozione stessa di "cluster" ammette interpretazioni diverse (compattezza, connettività, densità, distribuzione parametrica) ciascuna delle quali conduce a famiglie algoritmiche distinte [1].

La formalizzazione moderna del clustering risale almeno agli anni Sessanta, quando Ward propose un criterio gerarchico basato sulla minimizzazione della varianza intra-cluster [2], e MacQueen introdusse il termine "k-means" per l'algoritmo iterativo di partizionamento basato sui centroidi. L'algoritmo k-means nella sua forma standard, tuttavia, è attribuito a Lloyd, che lo sviluppò nel 1957 presso i Bell Labs nel contesto della quantizzazione vettoriale per la modulazione a codice di impulsi, sebbene il lavoro fu pubblicato solo nel 1982 [3]. Questi approcci operano sotto l'assunzione implicita che i cluster siano convessi e approssimativamente sferici, un'ipotesi che si rivela inadeguata per molti dataset reali.

Il riconoscimento di questa limitazione ha motivato lo sviluppo di approcci alternativi. Il clustering basato sulla densità, formalizzato da Ester et al. con DBSCAN nel 1996 [4], abbandona l'assunzione di convessità e definisce i cluster come regioni ad alta densità separate da regioni a bassa densità, consentendo l'identificazione di strutture di forma arbitraria. Il clustering spettrale, le cui basi teoriche emergono dal lavoro di Shi e Malik sui normalized cuts [5] e dalla formalizzazione di Ng, Jordan e Weiss [6], riformula il problema come partizionamento di grafi, sfruttando la struttura spettrale della matrice laplaciana per catturare relazioni non lineari. I modelli a miscela gaussiana (GMM), radicati nella teoria statistica dell'algoritmo Expectation-Maximization di Dempster, Laird e Rubin [7], offrono un framework probabilistico in cui ciascun cluster è descritto da una distribuzione parametrica, fornendo non solo assegnazioni rigide ma anche probabilità di appartenenza.

La proliferazione di approcci riflette un risultato teorico fondamentale: non esiste un algoritmo di clustering universalmente ottimale. Come osservato nelle survey recenti [8, 9], la scelta dell'algoritmo codifica implicitamente un'assunzione sulla struttura dei dati, e la violazione di tale assunzione produce risultati degradati. Comprendere le ipotesi, i meccanismi e i limiti di ciascuna famiglia algoritmica non è quindi un esercizio tassonomico, ma una competenza operativa necessaria per la progettazione di pipeline di analisi dati affidabili.

Clustering partizionale: k-means e le sue varianti

Formulazione e proprietà di convergenza

L'algoritmo k-means risolve un problema di ottimizzazione combinatoria: minimizzare la somma delle distanze euclidee al quadrato tra ciascun punto e il centroide del cluster a cui è assegnato, ovvero $\min_{C_1, \ldots, C_k} \sum_{j=1}^{k} \sum_{x_i \in C_j} |x_i - \mu_j|^2$, dove $\mu_j = \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i$ è il centroide del cluster $C_j$. Il problema è NP-hard nella sua forma generale, ma l'algoritmo iterativo di Lloyd, che alterna un passo di assegnazione (ogni punto al centroide più vicino) e un passo di aggiornamento (ricalcolo dei centroidi), converge in un numero finito di iterazioni a un minimo locale della funzione obiettivo [3]. La convergenza è garantita dal fatto che entrambi i passi riducono monotonamente il valore della funzione obiettivo, ma la soluzione trovata dipende criticamente dall'inizializzazione.

La sensibilità all'inizializzazione rappresenta il principale limite pratico di k-means. Un'inizializzazione casuale uniforme può produrre centroidi iniziali concentrati in una stessa regione dello spazio, conducendo a soluzioni significativamente sub-ottimali. Arthur e Vassilvitskii hanno proposto k-means++ [10], una procedura di inizializzazione che seleziona il primo centroide uniformemente a caso e ciascun centroide successivo con probabilità proporzionale al quadrato della distanza dal centroide più vicino già selezionato. Questa strategia garantisce che la soluzione iniziale sia $O(\log k)$-competitiva rispetto all'ottimo globale, e gli esperimenti mostrano miglioramenti consistenti sia nella qualità della soluzione sia nella velocità di convergenza [10]. L'inizializzazione k-means++ è oggi lo standard de facto nelle implementazioni principali, inclusa scikit-learn [11].

Assunzioni e limiti strutturali

L'utilizzo della distanza euclidea come metrica di dissimilarità implica che k-means identifica cluster sferici e isotropi. Quando la struttura reale dei dati presenta cluster di forma allungata, con densità variabili o con dimensioni significativamente diverse, l'algoritmo produce partizionamenti che spezzano cluster allungati o assegnano punti di un cluster denso a un cluster vicino ma sparso. Inoltre, la necessità di specificare $k$ a priori costituisce un vincolo operativo rilevante: in molti contesti applicativi il numero di cluster non è noto, e tecniche euristiche come il metodo del gomito (elbow method) o il coefficiente silhouette [12] forniscono indicazioni utili ma non definitive.

Il costo computazionale dell'iterazione standard di Lloyd è $O(nkd)$ per iterazione, dove $n$ è il numero di punti, $k$ il numero di cluster e $d$ la dimensionalità. Per dataset di grande scala, varianti come mini-batch k-means riducono il costo utilizzando sottocampioni casuali per l'aggiornamento dei centroidi, con una degradazione trascurabile della qualità della soluzione. La scalabilità lineare in $n$ rende k-means applicabile a dataset con milioni di osservazioni, un vantaggio competitivo significativo rispetto ad algoritmi con complessità quadratica o superiore.

Clustering basato sulla densità: DBSCAN e HDBSCAN

DBSCAN: definizioni e meccanismo

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) definisce i cluster attraverso il concetto di densità raggiungibile [4]. Dati due parametri, $\varepsilon$ (raggio del vicinato) e $\text{minPts}$ (numero minimo di punti nel vicinato), un punto $x_i$ è classificato come core point se il suo $\varepsilon$-vicinato $N_\varepsilon(x_i) = {x_j \in X : d(x_i, x_j) \leq \varepsilon}$ contiene almeno $\text{minPts}$ punti. Un punto $x_j$ è density-reachable da $x_i$ se esiste una catena di core point $x_i = p_1, p_2, \ldots, p_m = x_j$ tale che $p_{l+1} \in N_\varepsilon(p_l)$ per ogni $l$. I cluster sono definiti come insiemi massimali di punti mutuamente density-connected, mentre i punti non raggiungibili da alcun core point sono classificati come rumore.

Questa formulazione conferisce a DBSCAN tre proprietà distintive rispetto a k-means. In primo luogo, l'algoritmo identifica cluster di forma arbitraria, poiché la nozione di connettività per densità non richiede alcuna assunzione sulla geometria dei raggruppamenti. In secondo luogo, DBSCAN determina automaticamente il numero di cluster, che emerge dalla struttura di densità dei dati anziché essere specificato a priori. In terzo luogo, i punti anomali vengono esplicitamente identificati come rumore, anziché essere forzatamente assegnati al cluster più vicino: una proprietà particolarmente utile in contesti dove la presenza di outlier è attesa e la loro identificazione ha valore analitico [4].

Limiti di DBSCAN e l'estensione gerarchica HDBSCAN

Il principale limite di DBSCAN risiede nell'assunzione di densità globale uniforme, codificata nella scelta di un singolo parametro $\varepsilon$. Quando i cluster presentano densità significativamente diverse, ad esempio un cluster denso vicino a un cluster sparso, nessun valore di $\varepsilon$ produce risultati soddisfacenti: un valore piccolo frammenta i cluster sparsi, mentre un valore grande fonde i cluster densi con le regioni circostanti. Inoltre, la scelta appropriata della coppia $(\varepsilon, \text{minPts})$ richiede conoscenza a priori della scala di densità dei dati, e il metodo euristico basato sul k-distance graph non sempre fornisce indicazioni chiare.

HDBSCAN (Hierarchical DBSCAN), proposto da Campello, Moulavi e Sander [13], supera questa limitazione costruendo una gerarchia completa di partizionamenti basati sulla densità per tutti i possibili valori di $\varepsilon$, ed estraendo i cluster più stabili attraverso un criterio di persistenza. L'algoritmo opera in quattro fasi: (1) costruzione del grafo di mutual reachability distance, definita come $d_{\text{mreach}}(x_i, x_j) = \max{\text{core}_k(x_i), \text{core}_k(x_j), d(x_i, x_j)}$, dove $\text{core}_k(x_i)$ è la distanza dal $k$-esimo vicino più prossimo; (2) costruzione del minimum spanning tree su tale grafo; (3) estrazione della gerarchia dei cluster attraverso tagli successivi del MST; (4) selezione dei cluster ottimali attraverso il criterio di excess of mass, che privilegia i cluster con maggiore stabilità relativa nella gerarchia [13].

Il vantaggio fondamentale di HDBSCAN è la capacità di identificare cluster con densità diverse senza richiedere la specificazione di $\varepsilon$, conservando come unico parametro critico $\text{min_cluster_size}$. HDBSCAN è stato integrato in scikit-learn a partire dalla versione 1.3 [11], a testimonianza della sua maturità e adozione nella comunità.

Clustering gerarchico agglomerativo

Principi e criteri di linkage

Il clustering gerarchico agglomerativo (HAC) costruisce una gerarchia di cluster attraverso un processo bottom-up: inizialmente ciascun punto costituisce un cluster singolo, e ad ogni iterazione i due cluster più simili vengono fusi, fino a ottenere un unico cluster contenente tutti i punti. La struttura gerarchica risultante è rappresentata da un dendrogramma, che consente di visualizzare le relazioni di somiglianza a diverse scale e di estrarre partizionamenti piatti tagliando il dendrogramma a un'altezza appropriata [2].

La scelta del criterio di linkage, ovvero la funzione che definisce la distanza tra cluster, determina la geometria dei cluster identificati e le proprietà del dendrogramma. I criteri principali sono:

• Single linkage: $d(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x, y)$. Definisce la distanza come il minimo tra tutte le coppie di punti inter-cluster. Tende a produrre cluster allungati e connessi (effetto chaining), ed è sensibile al rumore e agli outlier.
• Complete linkage: $d(C_i, C_j) = \max_{x \in C_i, y \in C_j} d(x, y)$. Utilizza la distanza massima, producendo cluster compatti e sferici ma con tendenza a spezzare cluster allungati.
• Average linkage: $d(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i} \sum_{y \in C_j} d(x, y)$. Media delle distanze inter-cluster. Rappresenta un compromesso tra single e complete linkage.
• Ward linkage: $\Delta(C_i, C_j) = \frac{|C_i| \cdot |C_j|}{|C_i| + |C_j|} |\mu_i - \mu_j|^2$. Minimizza l'incremento della varianza intra-cluster ad ogni fusione [2]. Produce cluster compatti e bilanciati, ed è equivalente a k-means nella struttura geometrica dei cluster identificati.

La scelta del criterio di linkage codifica un'assunzione sulla forma dei cluster. Ward linkage assume cluster sferici con varianza simile, analogamente a k-means. Single linkage cattura cluster di forma arbitraria ma è vulnerabile al rumore. L'analisi di Murtagh e Legendre [14] ha chiarito le relazioni formali tra le diverse implementazioni del criterio di Ward, evidenziando che implementazioni apparentemente equivalenti possono produrre risultati diversi a causa di differenze nella normalizzazione.

Complessità e scalabilità

Il costo computazionale standard del clustering gerarchico agglomerativo è $O(n^2 \log n)$ per i criteri basati su distanze punto-a-punto (single, complete, average) e $O(n^2)$ in spazio per la matrice delle distanze. Per il single linkage, algoritmi specializzati basati sul minimum spanning tree riducono la complessità a $O(n^2)$ nel tempo. Questi costi rendono HAC impraticabile per dataset con più di alcune decine di migliaia di punti senza approssimazioni. Approcci come BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) e varianti basate su campionamento consentono di applicare il clustering gerarchico a dataset più grandi, al prezzo di una perdita di fedeltà nella struttura gerarchica.

Il vantaggio principale del clustering gerarchico rispetto ai metodi partizionali risiede nella ricchezza informativa del dendrogramma, che consente l'esplorazione della struttura multi-scala dei dati senza fissare a priori il numero di cluster. Questa proprietà è particolarmente preziosa in contesti esplorativi (analisi filogenetica, tassonomia documentale, segmentazione gerarchica di mercati) dove la struttura naturale dei dati non è nota e la sua scoperta è l'obiettivo primario dell'analisi.

Clustering spettrale

Fondamenti nel partizionamento di grafi

Il clustering spettrale riformula il problema di raggruppamento come un problema di partizionamento di grafi. Dato un grafo pesato $G = (V, E, W)$ dove i vertici rappresentano i punti dati e i pesi $w_{ij}$ codificano la similarità tra le coppie $(x_i, x_j)$, l'obiettivo è partizionare $V$ in sottoinsiemi tali da minimizzare il peso degli archi tagliati (inter-cluster) e massimizzare il peso degli archi interni (intra-cluster). Il criterio di minimum cut naive, ossia minimizzare $\text{cut}(A, B) = \sum_{i \in A, j \in B} w_{ij}$, tende a produrre partizioni sbilanciate, isolando singoli punti o piccoli gruppi [5].

Shi e Malik hanno introdotto il criterio di normalized cut, definito come $\text{Ncut}(A, B) = \frac{\text{cut}(A, B)}{\text{vol}(A)} + \frac{\text{cut}(A, B)}{\text{vol}(B)}$, dove $\text{vol}(A) = \sum_{i \in A} \sum_j w_{ij}$ è il volume del cluster [5]. La normalizzazione per il volume previene le partizioni degeneri e favorisce cluster bilanciati rispetto alla connettività. La minimizzazione esatta del normalized cut è NP-hard, ma la sua rilassazione continua conduce a un problema agli autovalori generalizzato sulla matrice laplaciana del grafo.

L'algoritmo di Ng, Jordan e Weiss

L'algoritmo proposto da Ng, Jordan e Weiss [6] formalizza il clustering spettrale nella forma oggi più diffusa. I passi fondamentali sono:

1. Costruzione della matrice di affinità $W$ con $w_{ij} = \exp(-|x_i - x_j|^2 / 2\sigma^2)$ per $i \neq j$ e $w_{ii} = 0$.
2. Calcolo della matrice laplaciana normalizzata $L_{\text{sym}} = D^{-1/2}(D - W)D^{-1/2}$, dove $D$ è la matrice diagonale dei gradi.
3. Estrazione dei primi $k$ autovettori di $L_{\text{sym}}$ corrispondenti ai $k$ autovalori più piccoli, formando la matrice $U \in \mathbb{R}^{n \times k}$.
4. Normalizzazione delle righe di $U$ a norma unitaria, ottenendo la matrice $T$.
5. Applicazione di k-means alle righe di $T$ nello spazio $\mathbb{R}^k$.

L'intuizione fondamentale è che la proiezione spettrale mappa i dati in uno spazio dove cluster non convessi o non lineari nello spazio originale diventano separabili da k-means. Von Luxburg [15] ha fornito un tutorial sistematico sulle basi teoriche del clustering spettrale, dimostrando la connessione tra gli autovettori della matrice laplaciana e le proprietà di connettività del grafo: in un grafo con $k$ componenti connesse, i primi $k$ autovettori della laplaciana hanno autovalore zero, e le corrispondenti coordinate identificano esattamente le componenti.

Limiti e parametri critici

Il clustering spettrale presenta due limiti operativi significativi. Il primo è la complessità computazionale: il calcolo della matrice di affinità richiede $O(n^2)$ in tempo e spazio, e la decomposizione spettrale $O(n^3)$ nel caso peggiore. Queste complessità rendono l'algoritmo impraticabile per dataset con più di alcune decine di migliaia di punti, a meno di utilizzare approssimazioni come la matrice di affinità sparsa o il metodo di Nyström per l'approssimazione degli autovettori. Il secondo limite è la scelta del parametro di scala $\sigma$, che controlla la larghezza del kernel gaussiano e influenza criticamente la struttura del grafo di similarità. Un valore troppo piccolo produce un grafo disconnesso; un valore troppo grande appiattisce le differenze di similarità. Tecniche adattive che variano $\sigma$ localmente, come proposto nella survey recente di Berahmand et al. [16], rappresentano una direzione attiva di ricerca.

Gaussian Mixture Models

Formulazione probabilistica

I Gaussian Mixture Models (GMM) adottano un approccio fondamentalmente diverso rispetto ai metodi geometrici: assumono che i dati siano generati da una miscela di $k$ distribuzioni gaussiane, ciascuna caratterizzata da un vettore media $\mu_j$, una matrice di covarianza $\Sigma_j$ e un peso di miscelazione $\pi_j$, con $\sum_{j=1}^k \pi_j = 1$. La densità del modello è $p(x) = \sum_{j=1}^{k} \pi_j \mathcal{N}(x | \mu_j, \Sigma_j)$, dove $\mathcal{N}(x | \mu_j, \Sigma_j) = \frac{1}{(2\pi)^{d/2} |\Sigma_j|^{1/2}} \exp\left(-\frac{1}{2}(x - \mu_j)^T \Sigma_j^{-1} (x - \mu_j)\right)$ è la densità gaussiana multivariata [7, 17].

La stima dei parametri avviene attraverso l'algoritmo Expectation-Maximization (EM), introdotto nella sua forma generale da Dempster, Laird e Rubin [7]. L'algoritmo alterna due passi: nel passo E (Expectation), si calcolano le responsabilità $\gamma_{ij} = P(z_i = j | x_i, \theta^{(t)})$, ovvero la probabilità a posteriori che il punto $x_i$ sia stato generato dalla $j$-esima componente, dati i parametri correnti $\theta^{(t)}$; nel passo M (Maximization), si aggiornano i parametri $\mu_j$, $\Sigma_j$ e $\pi_j$ massimizzando la log-likelihood attesa rispetto alle responsabilità calcolate. L'algoritmo EM garantisce che la log-likelihood non decresca ad ogni iterazione, ma, analogamente a k-means, converge a un massimo locale che dipende dall'inizializzazione [7, 17].

Vantaggi e relazione con k-means

La formulazione probabilistica dei GMM offre tre vantaggi distinti. Il primo è il soft clustering: anziché assegnare rigidamente ciascun punto a un cluster, le responsabilità $\gamma_{ij}$ quantificano l'incertezza dell'assegnazione, una proprietà cruciale quando i cluster si sovrappongono significativamente. Il secondo è la flessibilità nella geometria dei cluster: attraverso la matrice di covarianza $\Sigma_j$, ciascuna componente può modellare cluster ellissoidali con orientamento e eccentricità diversi, superando la limitazione dei cluster sferici imposta da k-means. Il terzo è la disponibilità di un framework rigoroso per la selezione del modello: criteri come il Bayesian Information Criterion (BIC) e l'Akaike Information Criterion (AIC) consentono di confrontare modelli con diverso numero di componenti penalizzando la complessità [17].

Si può dimostrare formalmente che k-means è un caso limite dei GMM: quando tutte le matrici di covarianza sono proporzionali all'identità $\Sigma_j = \sigma^2 I$ e $\sigma^2 \to 0$, le responsabilità del modello convergono a assegnazioni rigide e l'obiettivo dei GMM diventa equivalente a quello di k-means. Questa relazione chiarisce il ruolo delle assunzioni: k-means assume implicitamente cluster isotropi con uguale varianza, mentre i GMM estendono questa assunzione consentendo anisotropia e varianza eterogenea tra le componenti.

Limiti e sfide computazionali

I GMM presentano limiti significativi in alta dimensionalità. Il numero di parametri di ciascuna matrice di covarianza $\Sigma_j$ cresce come $O(d^2)$, rendendo la stima instabile quando $d$ è grande rispetto a $n$. Tecniche di regolarizzazione come la restrizione a matrici diagonali (riducendo i parametri a $O(d)$) o l'uso di modelli fattoriali mitigano il problema, al prezzo di una riduzione della flessibilità. Un secondo limite è la sensibilità al numero di componenti: un modello con troppe componenti produce overfitting, mentre uno con troppo poche non cattura la struttura dei dati. L'utilizzo di BIC come criterio di selezione fornisce una guida pratica, ma richiede la stima di modelli per ciascun valore candidato di $k$, con costo computazionale lineare nel numero di candidati.

Metriche di valutazione del clustering

Il problema della valutazione non supervisionata

La valutazione del clustering è intrinsecamente più complessa di quella della classificazione supervisionata. In assenza di etichette di riferimento, non esiste un criterio oggettivo di correttezza: la qualità di un partizionamento dipende dalla definizione operativa di "cluster buono", e definizioni diverse conducono a metriche diverse con comportamenti potenzialmente contraddittori. Si distinguono due categorie di metriche: interne, che valutano il partizionamento basandosi esclusivamente sulla struttura dei dati, ed esterne, che confrontano il partizionamento con una partizione di riferimento nota [12].

Metriche interne

Il coefficiente silhouette, introdotto da Rousseeuw [12], è la metrica interna più diffusa. Per ciascun punto $x_i$, si definisce $a(i)$ come la distanza media dagli altri punti nel proprio cluster e $b(i)$ come la distanza media dai punti del cluster più vicino diverso dal proprio. Il coefficiente silhouette del punto è $s(i) = \frac{b(i) - a(i)}{\max{a(i), b(i)}}$, con valori in $[-1, 1]$. Valori prossimi a $+1$ indicano un punto ben assegnato; valori prossimi a $0$ indicano un punto al confine tra cluster; valori negativi suggeriscono un'assegnazione errata. La media dei coefficienti silhouette su tutti i punti fornisce una valutazione globale del partizionamento. Il costo computazionale è $O(n^2)$, dominato dal calcolo delle distanze tra tutte le coppie di punti.

L'indice di Calinski-Harabasz [18], noto anche come Variance Ratio Criterion (VRC), è definito come $\text{CH} = \frac{\text{BCSS} / (k-1)}{\text{WCSS} / (n-k)}$, dove BCSS (Between-Cluster Sum of Squares) misura la dispersione tra i centroidi dei cluster e WCSS (Within-Cluster Sum of Squares) misura la dispersione interna. Valori più alti indicano cluster compatti e ben separati. A differenza del coefficiente silhouette, l'indice di Calinski-Harabasz è computazionalmente efficiente, $O(nd)$, ma assume implicitamente cluster sferici, il che lo rende inadeguato per valutare partizionamenti basati sulla densità o su strutture non convesse.

L'indice di Davies-Bouldin misura la similarità media tra ciascun cluster e il suo cluster più simile, definita come rapporto tra la dispersione intra-cluster e la distanza inter-cluster. Per ciascun cluster $C_i$, si identifica il cluster $C_j$ che massimizza il rapporto $R_{ij} = (s_i + s_j) / d(\mu_i, \mu_j)$, dove $s_i$ è la dispersione media intra-cluster e $d(\mu_i, \mu_j)$ la distanza tra centroidi; l'indice è la media dei massimi $R_{ij}$ su tutti i cluster. Valori più bassi indicano partizionamenti migliori. Come l'indice di Calinski-Harabasz, assume cluster convessi e penalizza strutture allungate o irregolari, rendendolo inadeguato come unico criterio di valutazione per algoritmi density-based.

Metriche esterne

Quando è disponibile una partizione di riferimento (ground truth), le metriche esterne misurano la concordanza tra il partizionamento prodotto dall'algoritmo e la partizione nota. L'Adjusted Rand Index (ARI) corregge per il caso l'indice di Rand, ovvero la frazione di coppie di punti su cui i due partizionamenti concordano, producendo valori attesi pari a zero per partizionamenti casuali e pari a uno per concordanza perfetta. La Normalized Mutual Information (NMI) quantifica l'informazione condivisa tra i due partizionamenti, normalizzata per l'entropia marginale, ed è meno sensibile al numero di cluster rispetto all'ARI. L'omogeneità e la completezza misurano rispettivamente se ciascun cluster contiene solo elementi di una singola classe e se tutti gli elementi di una classe sono assegnati allo stesso cluster.

Limiti delle metriche e implicazioni pratiche

Nessuna metrica interna è universalmente affidabile. Il coefficiente silhouette privilegia cluster sferici e tende a penalizzare strutture allungate o concentriche; l'indice di Calinski-Harabasz è influenzato dalla dimensione relativa dei cluster; entrambi possono indicare un numero ottimale di cluster diverso dal reale quando la struttura dei dati viola le rispettive assunzioni. Nella pratica operativa, la raccomandazione consolidata nella letteratura è l'utilizzo di metriche multiple e complementari, accompagnate da ispezione visiva quando la dimensionalità lo consente [8, 9]. La valutazione del clustering resta in ultima analisi un problema dominio-dipendente: la qualità di un partizionamento si misura anche, e spesso primariamente, dalla sua utilità per il compito applicativo a valle.

Clustering in alta dimensionalità

La degradazione delle metriche di distanza

L'applicazione degli algoritmi di clustering a dati ad alta dimensionalità introduce sfide fondamentali che vanno oltre il semplice aumento del costo computazionale. Aggarwal, Hinneburg e Keim [19] hanno dimostrato un risultato contro-intuitivo: al crescere della dimensionalità $d$, la differenza relativa tra la distanza massima e la distanza minima tra punti converge a zero sotto la norma $L_p$, con velocità che dipende da $p$. Formalmente, $\lim_{d \to \infty} \frac{D_{\max}^d - D_{\min}^d}{D_{\min}^d} \to 0$ per distribuzioni con varianza finita. Questo fenomeno, noto come concentrazione delle distanze, implica che le nozioni di vicinanza e lontananza, su cui tutti gli algoritmi di clustering basano le proprie decisioni, perdono potere discriminante.

L'analisi di Aggarwal et al. [19] ha inoltre evidenziato che la gravità del fenomeno dipende dalla norma utilizzata: la norma $L_1$ (Manhattan) preserva meglio la discriminabilità rispetto alla norma $L_2$ (euclidea) in alta dimensionalità, e norme frazionarie $L_p$ con $p < 1$ offrono risultati ancora migliori. Questa osservazione ha implicazioni pratiche dirette: in spazi ad alta dimensionalità, la scelta della metrica di distanza non è un dettaglio implementativo ma una decisione che influenza la significatività stessa dei risultati.

Strategie di mitigazione

Le strategie per il clustering in alta dimensionalità si articolano lungo tre direttrici principali. La prima è la riduzione della dimensionalità come pre-processing: tecniche come PCA (Principal Component Analysis) proiettano i dati in un sottospazio a dimensionalità ridotta preservando la varianza massima, mentre metodi non lineari come t-SNE e UMAP costruiscono embedding a bassa dimensionalità che preservano la struttura locale dei dati. Assent [20] ha analizzato sistematicamente le implicazioni dell'alta dimensionalità per i diversi paradigmi di clustering, evidenziando che le tecniche di riduzione dimensionale introducono compromessi specifici: PCA preserva la struttura globale ma proietta linearmente, penalizzando cluster su varietà non lineari; metodi non lineari come UMAP preservano meglio la struttura locale dei cluster ma introducono distorsioni nelle distanze globali che possono penalizzare algoritmi sensibili alla scala come k-means. La combinazione ottimale tra riduzione dimensionale e algoritmo di clustering è dominio-dipendente e richiede validazione sperimentale.

La seconda direttrice è il subspace clustering, che identifica cluster in sottospazi diversi dello spazio delle feature, riconoscendo che cluster diversi possono essere definiti da sottoinsiemi diversi di dimensioni. La terza è il deep clustering [21], che utilizza reti neurali (tipicamente autoencoder o variational autoencoder) per apprendere rappresentazioni a bassa dimensionalità ottimizzate congiuntamente per la ricostruzione dei dati e la separabilità dei cluster. Zhou et al. [21] propongono una tassonomia che distingue tra metodi che separano la fase di rappresentazione da quella di clustering e metodi che le integrano end-to-end, evidenziando che l'approccio integrato tende a produrre risultati superiori ma richiede una progettazione attenta della funzione obiettivo per evitare il collasso delle rappresentazioni.

Analisi comparativa e criteri di scelta

La scelta dell'algoritmo di clustering per un'applicazione specifica dipende dall'interazione tra le proprietà dei dati e le assunzioni dell'algoritmo. La tabella seguente sintetizza le caratteristiche discriminanti:

L'analisi rivela un trade-off sistematico tra espressività e scalabilità. K-means offre la massima scalabilità ma le assunzioni più restrittive; il clustering spettrale e i GMM offrono flessibilità superiore ma costi computazionali che limitano l'applicabilità a dataset di media scala; HDBSCAN rappresenta un compromesso efficace tra flessibilità e scalabilità per molte applicazioni pratiche [8, 13].

Un principio operativo consolidato nella pratica del machine learning è iniziare con k-means come baseline computazionalmente economico, verificare la validità dell'assunzione di cluster sferici attraverso il coefficiente silhouette e l'ispezione visiva (su proiezioni 2D), e procedere con algoritmi più espressivi solo quando le evidenze suggeriscono che la struttura dei dati viola le assunzioni di k-means. Questo approccio incrementale bilancia il costo dell'esplorazione con il rischio di risultati sub-ottimali.

Direzioni future e problemi aperti

Il clustering resta un'area di ricerca attiva con problemi aperti significativi su molteplici fronti. L'integrazione tra deep learning e clustering, il cosiddetto deep clustering [21], rappresenta la direzione più dinamica, con l'obiettivo di apprendere simultaneamente rappresentazioni a bassa dimensionalità e partizionamenti ottimali. La survey di Zhou et al. [21] identifica tre sfide aperte in questo ambito: la progettazione di funzioni obiettivo che bilancino la qualità della rappresentazione con la separabilità dei cluster senza causare il collasso delle rappresentazioni (mode collapse); la definizione di protocolli di valutazione standardizzati che consentano confronti rigorosi tra metodi; e lo sviluppo di architetture che integrino informazione strutturale (grafi, gerarchie) con le rappresentazioni apprese dalle reti neurali. Nonostante i progressi, la valutazione rigorosa di questi metodi è complicata dalla sensibilità ai dettagli di implementazione e dalla mancanza di benchmark universalmente accettati.

L'apprendimento della struttura del grafo per il clustering spettrale [16] offre una direzione complementare per superare la dipendenza dal parametro di scala $\sigma$. L'approccio consiste nell'apprendere la matrice di affinità congiuntamente al partizionamento, anziché costruirla come passo di pre-processing separato. Tecniche recenti basate su grafi adattivi e ipergrafi estendono questo paradigma a dati multi-vista e a relazioni di ordine superiore, ma introducono nuovi iperparametri e costi computazionali che ne limitano l'applicabilità pratica.

La scalabilità resta una sfida per tutti gli algoritmi con complessità super-lineare. L'applicazione del clustering a dataset con miliardi di punti, come nel caso della segmentazione di utenti in piattaforme digitali o del raggruppamento di embedding in sistemi di retrieval, richiede approssimazioni che bilancino accuratezza e costo computazionale. Tecniche come il clustering distribuito, l'uso di strutture di indicizzazione approssimate (approximate nearest neighbor search) e le varianti mini-batch di algoritmi classici rappresentano soluzioni pratiche, ma la teoria che ne garantisce la qualità è ancora in fase di sviluppo.

Infine, la valutazione del clustering in assenza di ground truth rimane un problema fondamentalmente aperto. Le metriche interne catturano proprietà geometriche specifiche (compattezza, separazione, densità) ma non la rilevanza del partizionamento per il compito applicativo a valle. La comunità non ha ancora raggiunto un consenso su come integrare la valutazione quantitativa con la validazione dominio-specifica, e questa lacuna metodologica rappresenta un ostacolo tanto per la ricerca quanto per l'adozione industriale di nuovi algoritmi.

Riferimenti

[1] H. Yin et al., "A Rapid Review of Clustering Algorithms," arXiv:2401.07389, 2024. https://arxiv.org/abs/2401.07389

[2] J. H. Ward, "Hierarchical Grouping to Optimize an Objective Function," Journal of the American Statistical Association, vol. 58, no. 301, pp. 236–244, 1963.

[3] S. Lloyd, "Least Squares Quantization in PCM," IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982.

[4] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise," in Proc. KDD, 1996, pp. 226–231.

[5] J. Shi and J. Malik, "Normalized Cuts and Image Segmentation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888–905, 2000.

[6] A. Y. Ng, M. I. Jordan, and Y. Weiss, "On Spectral Clustering: Analysis and an Algorithm," in Proc. NeurIPS, 2002. https://ai.stanford.edu/~ang/papers/nips01-spectral.pdf

[7] A. P. Dempster, N. M. Laird, and D. B. Rubin, "Maximum Likelihood from Incomplete Data via the EM Algorithm," Journal of the Royal Statistical Society: Series B, vol. 39, no. 1, pp. 1–38, 1977.

[8] A. Ahmad and S. S. Khan, "A Comprehensive Survey of Clustering Algorithms: State-of-the-Art Machine Learning Applications, Taxonomy, Challenges, and Future Research Prospects," Engineering Applications of Artificial Intelligence, vol. 110, 2022. https://www.sciencedirect.com/science/article/abs/pii/S095219762200046X

[9] P. Mirzaei et al., "Comprehensive Analysis of Clustering Algorithms: Exploring Limitations and Innovative Solutions," PeerJ Computer Science, 2024. https://pmc.ncbi.nlm.nih.gov/articles/PMC11419652/

[10] D. Arthur and S. Vassilvitskii, "k-means++: The Advantages of Careful Seeding," in Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 1027–1035.

[11] Scikit-learn Developers, "Clustering: scikit-learn Documentation," 2026. https://scikit-learn.org/stable/modules/clustering.html

[12] P. J. Rousseeuw, "Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis," Journal of Computational and Applied Mathematics, vol. 20, pp. 53–65, 1987.

[13] R. J. G. B. Campello, D. Moulavi, and J. Sander, "Density-Based Clustering Based on Hierarchical Density Estimates," in Proc. PAKDD, Springer, 2013, pp. 160–172. https://link.springer.com/chapter/10.1007/978-3-642-37456-2_14

[14] F. Murtagh and P. Legendre, "Ward's Hierarchical Agglomerative Clustering Method: Which Algorithms Implement Ward's Criterion?," Journal of Classification, vol. 31, pp. 274–295, 2014. https://link.springer.com/article/10.1007/s00357-014-9161-z

[15] U. von Luxburg, "A Tutorial on Spectral Clustering," Statistics and Computing, vol. 17, no. 4, pp. 395–416, 2007. https://arxiv.org/abs/0711.0189

[16] K. Berahmand et al., "A Comprehensive Survey on Spectral Clustering with Graph Structure Learning," arXiv:2501.13597, 2025. https://arxiv.org/abs/2501.13597

[17] G. J. McLachlan and D. Peel, Finite Mixture Models, Wiley Series in Probability and Statistics, John Wiley & Sons, 2000.

[18] T. Caliński and J. Harabasz, "A Dendrite Method for Cluster Analysis," Communications in Statistics: Theory and Methods, vol. 3, no. 1, pp. 1–27, 1974.

[19] C. C. Aggarwal, A. Hinneburg, and D. A. Keim, "On the Surprising Behavior of Distance Metrics in High Dimensional Space," in Proc. ICDT, Springer, 2001, pp. 420–434. https://link.springer.com/chapter/10.1007/3-540-44503-X_27

[20] I. Assent, "Clustering High Dimensional Data," WIREs Data Mining and Knowledge Discovery, vol. 2, no. 4, pp. 340–350, 2012. https://wires.onlinelibrary.wiley.com/doi/10.1002/widm.1062

[21] H. Zhou et al., "A Comprehensive Survey on Deep Clustering: Taxonomy, Challenges, and Future Directions," ACM Computing Surveys, vol. 56, 2024. https://dl.acm.org/doi/10.1145/3689036