Clustering: differenze tra le versioni

Versione delle 22:57, 26 dic 2013

Versione attuale delle 20:52, 29 mar 2025

(35 versioni intermedie di 26 utenti non mostrate)

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 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 [[Distanza (matematica)|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 a un [[insieme]] dipende da quanto l'elemento preso in esame è distante dall'insieme stesso.

== Tecniche di Clustering ==

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

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

== Tecniche di Clustering ==

* ''Clusteringclustering esclusivo'': ogni elemento può essere assegnato ad uno e ad un solo gruppo. IQuindi clustersi risultanti,cluster quindi,risultanti non possono avere elementi in comune. Questo approccio è detto anche ''Hardhard 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 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 [[Logicalogica fuzzy|fuzzy]]).

* ''Clustering 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 ''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 [[Logica fuzzy|fuzzy]]).

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

* ''Clusteringclustering partitizionalepartizionale (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.

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

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 clusterscluster, <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 '[[K-medoids|Partitioning Around MedioidMedoids]] (PAM)'.

=== Clustering gerarchico ===

Le tecniche di [[clustering gerarchico]] non producono un partizionamento ''flat'' dei punti, ma una rappresentazione gerarchica ad albero. [[File:hierarchical1.jpg]]

[[File:hierarchical1.jpg]]

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 clusterscluster, 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 [[Dendrogrammadendrogramma]].

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

In entrambeentrambi 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:
:<math> D(C_i,C_j)=\min_{x \in C_i, y \in C_j} d(x,y)</math>

[[File:Singlelink.jpg|right]]

* ''Average-link proximity''

:Questa funzione calcola la distanza tra i due cluster come la media delle distanze tra i singoli elementi: <math> D(C_i,C_j)= \frac{1}{|C_i| |C_j|} \sum_{x \in C_i,y \in C_j} d(x,y) </math>

* ''Complete-link proximity''

:Questa funzione calcola la distanza tra i due cluster come la distanza massima tra elementi appartenenti ai due clusterscluster: <math> D(C_i,C_j)=\max_{x \in C_i, y \in C_j} d(x,y)</math>

* ''Distanza tra centroidi''

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

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

* ''Dunn Index''

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

: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:<ref>{{Cita pubblicazione|cognome= Dunn |nome=J.|titolo=Well separated clusters and optimal fuzzy partitions|rivista=Journal of Cybernetics|anno=1974| volume = 4|pp=95-104| doi = 10.1080/01969727408546059}}</ref>

::<math>

Nel clustering divisivo, invece, è 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:

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)} \,,

</math>

: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<ref>{{cita web|titolo=Dunn index in Python|url=https://python.engineering/dunn-index-and-db-index-cluster-validity-indices-set/|sito=Python.Engineering|lingua=en|data=13 dicembre 2022}}</ref>.

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

NelInvece nel clustering divisivo, invece, è 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:

Line 63 ⟶ 74:

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|DBSCAN]].

== Algoritmi ==

Algoritmi di clustering molto usati sono:

* [[K-means|K-Means]]

* [[K-medoids|K-Medoids]]

* [[fuzzy c-means|Fuzzy C-Means]]

* [[qt clustering|QT Clustering]]

=== QT clustering ===

Line 77 ⟶ 88:

L'algoritmo è:

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

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

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|clustering gerarchico]]).

==Note==

<references/>

== Bibliografia ==

*{{cita libro|Roberto|Todeschini|Introduzione alla chemiometria|2003|EdiSES|Napoli|ed=1}}ISBN |isbn=88-7959-146-0}}

* G.Susinno, M.A.Miceli, ''Ultrametricity in Fund of Funds Diversification'', Physica A 344 (1-2) (2004) 95-99

== Voci correlate ==

* [[Mean shift]]

* [[Region growing]]

== Altri progetti ==

{{interprogetto|commonspreposizione=Cluster analysissul|wikt=clustering}}

== Collegamenti esterni ==

* {{ThesaurusCollegamenti BNCFesterni}}

* [http://www.matematicamente.it/il_magazinerivista-il-magazine/numero_9%3a_aprile_2009numero-9-aprile-2009/112._data_mining%3a_esplorando_le_miniere_alla_ricerca_della_conoscenza_nascosta_clustering_200905305380-data-mining-esplorando-le-miniere-alla-ricerca-della-conoscenza-nascosta-clustering/ (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" [https://www.thinkmind.org/index.php?view=article&articleid=immm_2018_2_10_50010], Eighth International Conferenceon Advances in Information Mining and Management, IMMM 2018, Barcelona, Spain, July 22 - 26, 2018.

{{Apprendimento automatico}}

{{Portale|matematica}}

{{Controllo di autorità}}

{{Portale|matematica|informatica}}

[[Categoria:Intelligenza artificiale]]

[[Categoria:Algoritmi]]

[[Categoria:Apprendimento automatico]]

[[Categoria:Analisi dei cluster| ]]

[[Categoria:Geostatistica]]

[[Categoria:Statistica]]