Clustering

Le tecniche di clustering si possono basare principalmente su due "filosofie":

• Dal basso verso l'alto (metodi aggregativi o bottom-up):

Questa filosofia prevede che inizialmente tutti gli elementi siano considerati cluster a sé, e poi l'algoritmo provvede ad unire i cluster più vicini. L'algoritmo continua ad unire elementi al cluster fino ad ottenere un numero prefissato di cluster, oppure fino a che la distanza minima tra i cluster non supera un certo valore, o ancora in relazione ad un determinato criterio statistico prefissato.

• Dall'alto verso il basso (metodi divisivi o top-down):

All'inizio tutti gli elementi sono un unico cluster, e poi l'algoritmo inizia a dividere il cluster in tanti cluster di dimensioni inferiori. Il criterio che guida la divisione è naturalmente quello di ottenere gruppi sempre più omogenei. L'algoritmo procede fino a che non viene soddisfatta una regola di arresto generalmente legata al raggiungimento di un numero prefissato di cluster.

Esistono varie classificazioni delle tecniche di clustering comunemente utilizzate. Una prima categorizzazione dipende dalla possibilità che un elemento possa o meno essere assegnato a più cluster:

• clustering esclusivo: ogni elemento può essere assegnato ad uno e ad un solo gruppo. Quindi i cluster risultanti non possono avere elementi in comune. Questo approccio è detto anche hard clustering.
• clustering non-esclusivo, in cui un elemento può appartenere a più cluster con gradi di appartenenza diversi. Questo approccio è noto anche con il nome di soft clustering o fuzzy clustering, dal termine usato per indicare la logica fuzzy.

Un'altra suddivisione delle tecniche di clustering tiene conto del tipo di algoritmo utilizzato per dividere lo spazio:

• clustering partizionale (detto anche non gerarchico, o k-clustering), in cui per definire l'appartenenza ad un gruppo viene utilizzata una distanza da un punto rappresentativo del cluster (centroide, medioide, ecc.), avendo prefissato il numero di gruppi della partizione risultato. Si tratta di derivazioni del più noto algoritmo di clustering, quello detto delle k-means, introdotto da MacQueen nel 1967.
• Clustering gerarchico, in cui viene costruita una gerarchia di partizioni caratterizzate da un numero (de)crescente di gruppi, visualizzabile mediante una rappresentazione ad albero (dendrogramma), in cui sono rappresentati i passi di accorpamento/divisione dei gruppi.

Queste due suddivisioni sono del tutto trasversali, e molti algoritmi nati come "esclusivi" sono stati in seguito adattati nel caso "non-esclusivo" e viceversa.

Gli algoritmi di clustering di questa famiglia creano una partizione delle osservazioni minimizzando una certa funzione di costo:

${\displaystyle \sum _{j=1}^{k}E(C_{j}),}$ 

dove ${\displaystyle k}$  è il numero dei cluster, ${\displaystyle C_{j}}$  è il ${\displaystyle j}$ -esimo cluster e ${\displaystyle E\colon C\rightarrow \mathbb {R} ^{+}}$  è la funzione di costo associata al singolo cluster. L'algoritmo più famoso appartenente a questa famiglia è il k-means, proposto da MacQueen nel 1967. Un altro algoritmo abbastanza conosciuto appartenente a questa classe è il Partitioning Around Medioid (PAM).

Le tecniche di clustering gerarchico non producono un partizionamento flat dei punti, ma una rappresentazione gerarchica ad albero.  

Questi algoritmi sono a loro volta suddivisi in due classi:

• Agglomerativo - Questi algoritmi assumono che inizialmente ogni cluster (foglia) contenga un singolo punto; ad ogni passo, poi, vengono fusi i cluster più "vicini" fino ad ottenere un singolo grande cluster. Questi algoritmi necessitano di misure per valutare la similarità tra cluster, per scegliere la coppia di cluster da fondere ad ogni passo.
• Divisivo - Questi algoritmi, invece, partono considerando lo spazio organizzato in un singolo grande cluster contenente tutti i punti, e via via lo dividono in due. Ad ogni passo viene selezionato un cluster in base ad una misura, ed esso viene suddiviso in due cluster più piccoli. Normalmente viene fissato un numero minimo di punti sotto il quale il cluster non viene ulteriormente suddiviso (nel caso estremo questo valore è 1). Questi tipi di algoritmi necessitano di definire una funzione per scegliere il cluster da suddividere.

Una rappresentazione grafica del processo di clustering è fornita dal dendrogramma.

In entrambi i tipi di clustering gerarchico sono necessarie funzioni per selezionare la coppia di cluster da fondere ("agglomerativo"), oppure il cluster da dividere ("divisivo").

Nel primo caso, sono necessarie funzioni che misurino la similarità (o, indistintamente, la distanza) tra due cluster, in modo da fondere quelli più simili. Le funzioni utilizzate nel caso agglomerativo sono:

• Single-link proximity

Calcola la distanza tra i due cluster come la distanza minima tra elementi appartenenti a cluster diversi:

${\displaystyle D(C_{i},C_{j})=\min _{x\in C_{i},y\in C_{j}}d(x,y)}$ 

• Average-link proximity

Questa funzione calcola la distanza tra i due cluster come la media delle distanze tra i singoli elementi: ${\displaystyle D(C_{i},C_{j})={\frac {1}{|C_{i}||C_{j}|}}\sum _{x\in C_{i},y\in C_{j}}d(x,y)}$ 

• Complete-link proximity

Questa funzione calcola la distanza tra i due cluster come la distanza massima tra elementi appartenenti ai due cluster: ${\displaystyle D(C_{i},C_{j})=\max _{x\in C_{i},y\in C_{j}}d(x,y)}$ 

• Distanza tra centroidi

La distanza tra i due cluster coincide con la distanza calcolata tra i centroidi (o medioidi):

${\displaystyle D(C_{i},C_{j})=d({\hat {c_{i}}},{\hat {c_{j}}})}$ .

• Dunn Index

L'indice di Dunn mira a identificare cluster densi e ben separati. È definito come il rapporto tra la minima distanza inter-cluster e la massima distanza intra-cluster. Per ogni partizione del cluster, l'indice di Dunn può essere calcolato con la seguente formula:^[1]

${\displaystyle D(C_{i},C_{j})={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,}$ 

dove d(i,j) rappresenta la distanza tra i cluster i e j e d '(k) misura la distanza intra-cluster del cluster k. La distanza inter-cluster d(i,j) tra due cluster può essere una qualsiasi misura di distanza, come la distanza tra i centroidi dei cluster. Allo stesso modo, la distanza intra-cluster 'd '(k) può essere misurata in vari modi, come la distanza massima tra qualsiasi coppia di elementi nel cluster k. Poiché il criterio interno cerca cluster con un'alta somiglianza intra-cluster e una bassa somiglianza inter-cluster, gli algoritmi che producono cluster con un alto indice di Dunn sono più desiderabili^[2].

Nei casi precedenti, ${\displaystyle d(x,y)}$  indica una qualsiasi funzione distanza su uno spazio metrico.

Invece nel clustering divisivo è necessario individuare il cluster da suddividere in due sottogruppi. Per questa ragione sono necessarie funzioni che misurino la compattezza del cluster, la densità o la sparsità dei punti assegnati ad un cluster. Le funzioni normalmente utilizzate nel caso divisivo sono:

• Average internal similarity

Questa funzione valuta la similarità media tra i documenti interni ad un cluster: più sono tra loro dissimili (valori bassi di similarità), più il cluster è da suddividere in sottogruppi:

${\displaystyle D(C_{i})={\frac {1}{|C_{i}|(|C_{i}|-1)}}\sum _{x,y\in C_{i},x\neq y}d(x,y)}$ 

• Maximum internal distance

Questa funzione valuta la distanza massima tra due punti interni ad un cluster. Tale valore è noto anche come 'diametro del cluster': più tale valore è basso, più il cluster è compatto:

${\displaystyle D(C_{i})=\max _{x,y\in C_{i}}d(x,y)}$ 

Nel Clustering density-based, il raggruppamento avviene analizzando l'intorno di ogni punto dello spazio. In particolare, viene considerata la densità di punti in un intorno di raggio fissato.

Un esempio è il metodo di clustering Dbscan.

Algoritmi di clustering molto usati sono:

• K-means
• K-medoids
• fuzzy c-means
• qt clustering

Il QT (Quality Threshold) Clustering (Heyer et al., 1999) è un metodo alternativo di partizionare i dati, inventato per il clustering dei geni. Richiede più potenza di calcolo rispetto al K-Means, ma non richiede di specificare il numero di cluster a priori, e restituisce sempre lo stesso risultato quando si ripete diverse volte.

L'algoritmo è:

• L'utente sceglie un diametro massimo per i cluster;
• Costruzione di un cluster candidato per ogni punto, includendo il punto più vicino, il prossimo più vicino, e così via, fino a che il diametro del cluster non supera la soglia;
• Salvataggio del cluster candidato con la maggior parte dei punti come primo vero cluster, e rimozione di tutti i punti nel cluster da ulteriori considerazioni;
• Ricorsione col ridotto insieme di cluster.

La distanza tra un punto ed un gruppo di punti è calcolata usando il concatenamento completo, cioè come la massima distanza dal punto di ciascun membro del gruppo (vedi il "Clustering gerarchico agglomerativo" sulla distanza tra i cluster nella sezione clustering gerarchico).

• Roberto Todeschini, Introduzione alla chemiometria, 1ª ed., Napoli, EdiSES, 2003, ISBN 88-7959-146-0.
• G.Susinno, M.A.Miceli, Ultrametricity in Fund of Funds Diversification, Physica A 344 (1-2) (2004) 95-99

• Mean shift
• Region growing

•   Wikibooks contiene testi o manuali sul clustering
•   Wikizionario contiene il lemma di dizionario «clustering»
•   Wikimedia Commons contiene immagini o altri file sul clustering

• cluster analysis, su sapere.it, De Agostini.  
• (EN) Jorge Bacallao Gallestey, cluster analysis, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  
• (EN) Eric W. Weisstein, Clustering, su MathWorld, Wolfram Research.  
• (IT) Articolo divulgativo su Clustering e Data Mining.
• Gaetano Zazzaro, Angelo Martone, "ECF-means – Ensemble Clustering Fuzzification Means. A novel algorithm for clustering aggregation, fuzzification, and optimization" [1], Eighth International Conferenceon Advances in Information Mining and Management, IMMM 2018, Barcelona, Spain, July 22 - 26, 2018.