Clustering: differenze tra le versioni

Versione delle 09:45, 15 apr 2015

Versione delle 14:06, 15 apr 2015

Riga 1:

IlIn [[statistica]], il '''Clusteringclustering''' 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":

* Dal basso verso l'alto (''metodi aggregativi o Bottombottom-Upup''):

: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 Toptop-Downdown''):

: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 Clusteringclustering ==

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ù clusters:

* ''Clusteringclustering esclusivo'': ogni elemento può essere assegnato ad uno e ad un solo gruppo. I clusters risultanti, quindi, non possono avere elementi in comune. Questo approccio è detto anche ''Hardhard Clusteringclustering''.

* ''Clusteringclustering non-esclusivo'', in cui un elemento può appartenere a più cluster con gradi di appartenenza diversi. Questo approccio è noto anche con il nome di ''Softsoft Clusteringclustering'' o ''Fuzzyfuzzy Clusteringclustering'' (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:

* ''Clusteringclustering 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 [[Kk-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.

Riga 20:

=== Clustering partizionale ===

Gli algoritmi di clustering di questa famiglia creano una [[Partizione (teoria degli insiemi)|partizione]] delle osservazioni minimizzando una certa funzione di costo:<br />

:<math>\sum_{j=1}^k E( C_j ),</math>

<math>\sum_{j=1}^k E( C_j )</math> <br /> dove <math>k</math> è il numero dei clusters, <math>C_j</math> è il <math>j-esimo</math>-esimo cluster e <math>E:\colon C \rightarrow \R^{+}</math> è 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)'.

=== Clustering gerarchico ===

Line 31 ⟶ 32:

* ''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 [[Dendrogrammadendrogramma]].

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