Топ-100
Indietro

ⓘ Clustering



Clustering
                                     

ⓘ Clustering

In statistica, il clustering o analisi dei gruppi è 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 lappartenenza o meno ad un insieme dipende da quanto lelemento preso in esame è distante dallinsieme stesso.

                                     

1. Tecniche

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

  • Dal basso verso lalto metodi aggregativi o bottom-up
Questa filosofia prevede che inizialmente tutti gli elementi siano considerati cluster a sé, e poi lalgoritmo provvede ad unire i cluster più vicini. Lalgoritmo 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.
  • Dallalto verso il basso metodi divisivi o top-down
Allinizio tutti gli elementi sono un unico cluster, e poi lalgoritmo 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. Lalgoritmo 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.

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

  • Clustering gerarchico, in cui viene costruita una gerarchia di partizioni caratterizzate da un numero decrescente di gruppi, visualizzabile mediante una rappresentazione ad albero dendrogramma, in cui sono rappresentati i passi di accorpamento/divisione dei gruppi.
  • clustering partizionale detto anche non gerarchico, o k-clustering, in cui per definire lappartenenza 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.

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

                                     

1.1. Tecniche Clustering partizionale

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

∑ j = 1 k E C j, {\displaystyle \sum _{j=1}^{k}EC_{j},}

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. Lalgoritmo 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.

                                     

1.2. Tecniche Clustering gerarchico

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:

  • Divisivo - Questi algoritmi, invece, partono considerando lo spazio organizzato in un singolo grande cluster contenente tutti i punti, e 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.
  • 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.

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



                                     

1.3. Tecniche Misure utilizzate nel clustering gerarchico

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à 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: D C i, C j = min x ∈ C i, y ∈ C j d x, y {\displaystyle DC_{i},C_{j}=\min _{x\in C_{i},y\in C_{j}}dx,y}
  • Average-link proximity
Questa funzione calcola la distanza tra i due cluster come la media delle distanze tra i singoli elementi: D C i, C j = 1 | C i | | C j | ∑ x ∈ C i, y ∈ C j d x, y {\displaystyle DC_{i},C_{j}={\frac {1}{|C_{i}||C_{j}|}}\sum _{x\in C_{i},y\in C_{j}}dx,y}
  • Complete-link proximity
Questa funzione calcola la distanza tra i due cluster come la distanza massima tra elementi appartenenti ai due cluster: D C i, C j = max x ∈ C i, y ∈ C j d x, y {\displaystyle DC_{i},C_{j}=\max _{x\in C_{i},y\in C_{j}}dx,y}
  • Distanza tra centroidi
La distanza tra i due cluster coincide con la distanza calcolata tra i centroidi o medioidi: D C i, C j = d c i ^, c j ^ {\displaystyle DC_{i},C_{j}=d{\hat {c_{i}}},{\hat {c_{j}}}}.

Nei 4 casi precedenti, d x, y {\displaystyle dx,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: D C i = 1 | C i | | C i | − 1 ∑ x, y ∈ C i, x ≠ y d x, y {\displaystyle DC_{i}={\frac {1}{|C_{i}||C_{i}|-1}}\sum _{x,y\in C_{i},x\neq y}dx,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: D C i = max x, y ∈ C i d x, y {\displaystyle DC_{i}=\max _{x,y\in C_{i}}dx,y}
                                     

1.4. Tecniche Clustering density-based

Nel Clustering density-based, il raggruppamento avviene analizzando lintorno 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.

                                     

2.1. Algoritmi 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.

Lalgoritmo è:

  • Ricorsione col ridotto insieme di cluster.
  • 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;
  • Lutente 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;

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.

Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →