Clustering: differenze tra le versioni

Versione delle 22:57, 26 dic 2013

Versione delle 22:28, 10 mar 2014

Riga 1:

Il '''Clustering''' o '''analisi dei gruppi''' (dal termine [[lingua inglese|inglese]] ''cluster analysis'' introdotto da [[Robert Tryon]] nel [[1939]]) è un insieme di tecniche di [[statistica multivariata|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 [[algoritmo|algoritmi]] di ''clustering'' raggruppano gli elementi sulla base della loro distanza reciproca, e quindi l'appartenenza o meno ad 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":

Riga 7:

* 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''.

== Tecniche di Clustering ==

Line 18 ⟶ 17:

* ''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.

=== Clustering partizionale ===

Line 35 ⟶ 34:

==== Misure utilizzate nel clustering gerarchico ====

In entrambe 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:

Line 48 ⟶ 47:

* ''Distanza tra centroidi''

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

:<math> D(C_i,C_j)=d(\hat{c_i},\hat{c_j})</math>.

Nei 4 casi precedenti, <math> d(x,y) </math> indica una qualsiasi funzione distanza su uno spazio metrico.

Line 78 ⟶ 77:

L'algoritmo è:

* L'utente sceglie un diametro massimo per i clusters;

* Costruzione di un cluster candidato per ogni punto, includendo il punto più vicino, il prossimo più vicino, e cosicosì 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.