Clustering: differenze tra le versioni

Versione delle 02:09, 25 apr 2020

Versione attuale delle 20:52, 29 mar 2025

(12 versioni intermedie di 10 utenti non mostrate)

Riga 1:

In [[statistica]], 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 [[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 ==

Line 14 ⟶ 16:

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

* ''clustering 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 [[k-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.

Line 22 ⟶ 24:

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

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

dove <math>k</math> è il numero dei cluster, <math>C_j</math> è il <math>j</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 ===

Line 50 ⟶ 52:

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

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.

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:

Line 83 ⟶ 94:

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

Line 93 ⟶ 107:

== Altri progetti ==

{{interprogetto|preposizione=sul|wikt=clustering}}

== Collegamenti esterni ==