In statistica, il clustering o analisi dei gruppi (dal termine inglese cluster analysis, introdotto da Robert Tryon nel 1939) è un insieme di tecniche di analisi multivariata dei dati volte alla selezione e raggruppamento di elementi omogenei in un insieme di dati.
Le tecniche di clustering si basano su misure relative alla somiglianza tra gli elementi. In molti approcci questa similarità, o meglio, dissimilarità, è concepita in termini di distanza in uno spazio multidimensionale. La bontà delle analisi ottenute dagli algoritmi di clustering dipende molto dalla scelta della metrica, e quindi da come è calcolata la distanza. Gli algoritmi di clustering raggruppano gli elementi sulla base della loro distanza reciproca, e quindi l'appartenenza o meno a un insieme dipende da quanto l'elemento preso in esame è distante dall'insieme stesso.
Le tecniche di clustering si possono basare principalmente su due "filosofie":
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:
Un'altra suddivisione delle tecniche di clustering tiene conto del tipo di algoritmo utilizzato per dividere lo spazio:
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:
dove k {\displaystyle k} è il numero dei cluster, C j {\displaystyle C_{j}} è il j {\displaystyle j} -esimo cluster e E : C → R + {\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 Medoids (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:
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:
Nei casi precedenti, d ( x , y ) {\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:
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:
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 è:
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).
Altri progetti
