Clustering gerarchico: differenze tra le versioni

Versione delle 09:48, 3 mag 2009

Versione attuale delle 12:53, 29 mag 2025

(43 versioni intermedie di 26 utenti non mostrate)

Riga 1:

In [[statistica]] e [[apprendimento automatico]], il '''clustering gerarchico''' è un approccio di [[clustering]] che mira a costruire una [[gerarchia]] di [[Computer cluster|cluster]]. Le strategie per il clustering gerarchico sono tipicamente di due tipi:

*'''Agglomerativo''': si tratta di un approccio "bottom up" (dal basso verso l'alto) in cui si parte dall'inserimento di ciascun elemento in un cluster differente e si procede quindi all'accorpamento graduale di cluster a due a due.

*'''Divisivo''': si tratta di un approccio "top down" (dall'alto verso il baccobasso) in cui tutti gli elementi si trovano inizialmente in un singolo cluster che viene via via suddiviso ricorsivamente in sotto-cluster.

Il risultato di un clustering gerarchico è rappresentato in un [[dendrogramma]].

== Dissimilarità tra cluster ==

Per decidere quali cluster devono essere combinati (approccio agglomerativo) o quale cluster deve essere suddiviso (approccio divisivo) è necessario definire una misura di dissimilarità tra cluster. Nella maggior parte dei metodi di clustering gerarchico si fa uso di [[metrica (matematica)|metriche]] specifiche che quantificano la distanza tra coppie di elementi e di un criterio di linkagecollegamento che specifica la dissimilarità di due insiemi di elementi (cluster) come funzione della distanza a coppie tra elementi nei due insiemi.

Per decidere quali cluster devono essere combinati (approccio agglomerativo) o quale cluster deve essere suddiviso (approccio divisivo) è necessario definire una misura di dissimilarità tra cluster. Nella maggior parte dei metodi di clustering gerarchico si fa uso di [[metrica (matematica)|metriche]] specifiche che quantificano la distanza tra coppie di elementi e di un criterio di linkage che specifica la dissimilarità di due insiemi di elementi (cluster) come funzione della distanza a coppie tra elementi nei due insiemi.

=== Metriche ===

Riga 15 ⟶ 14:

La scelta di una metrica appropriata influenza la forma dei cluster, poiché alcuni elementi possono essere più "vicini" utilizzando una distanza e più "lontani" utilizzandone un'altra. Per esempio, in uno spazio a 2 dimensioni, la distanza tra il punto (1, 1) e l'origine (0, 0) è 2, <math>\sqrt{2}</math> or 1 se si utilizzando rispettivamente le norme 1, 2 o infinito.

Metriche comuni sono le seguenti:<ref>{{citecita web |lingua=en title|titolo=The DISTANCE Procedure: Proximity Measures | url=httphttps://support.sas.com/documentation/cdl/en/statug/59654/HTML/default/statug_distance_sect016.htm | worksito=SAS/STAT 9.2 Users Guide | publishereditore= [[SAS Institute]] | datedata= | accessdateaccesso=2009-04-26 aprile 2009 |urlmorto=sì }}</ref>

* La [[distanza euclidea]] (chiamata anche norma 2)

* La [[distanza di Manhattan]] (chiamata anche norma 1)

* La [[norma uniforme]]

Riga 23 ⟶ 22:

* La [[distanza di Hamming]], che misura il minimo numero di sostituzioni richieste per cambiare un membro nell'altro.

=== Criteri di collegamento ===

==Voci correlate==

Il criterio di collegamento (''linkage criterion'') specifica la distanza tra insiemi di elementi come funzione di distanze tra gli elementi negli insiemi.

* [[Clustering]]

* [[Dendrogramma]]

Dati due insiemi di elementi ''A'' e ''B'' alcuni criteri comunemente utilizzati sono:<ref>{{cita web |lingua=en |titolo=The CLUSTER Procedure: Clustering Methods |url=https://support.sas.com/documentation/cdl/en/statug/59654/HTML/default/statug_cluster_sect012.htm |sito=SAS/STAT 9.2 Users Guide |editore=[[SAS Institute]] |data= |accesso=26 aprile 2009 |urlarchivio=https://web.archive.org/web/20080707081702/http://support.sas.com/documentation/cdl/en/statug/59654/HTML/default/statug_cluster_sect012.htm |dataarchivio=7 luglio 2008 |urlmorto=sì }}</ref>

{|class="wikitable"

! Nome del criterio

! Formula

|-

| Complete linkage

| <math> \max \, \{\, d(a,b) : a \in A,\, b \in B \,\}. </math>

|-

| Minimum o single-linkage

| <math> \min \, \{\, d(a,b) : a \in A,\, b \in B \,\}. </math>

|-

| Average linkage

| <math> \frac{1}{|A| |B|} \sum_{a \in A }\sum_{ b \in B} d(a,b). </math>

|}

dove ''d'' è la metrica prescelta per determinare la similarità tra coppie di elementi.

Vi è anche il criterio di Ward, che valuta il cambiamento di varianza intra-cluster quando questi si uniscono e seleziona la coppia che dà luogo a un cluster avente la minima varianza al suo interno. Questo criterio punta a creare cluster compatti e omogenei, con una dispersione simile.<ref>{{Cita web|url=http://www.r-project.it/_book/clustering-gerarchico-agglomerativo-hc.html|titolo=Clustering Gerarchico}}</ref>

==Note==

Riga 31 ⟶ 48:

==Bibliografia==

*{{en}}Cita {{cite booklibro|last1autore-capitolo-cognome=Hastie|first1autore-capitolo-nome=Trevor|last2autore-capitolo-cognome2=Tibshirani|first2autore-capitolo-nome2=Robert|last3autore-capitolo-cognome3=Friedman|first3autore-capitolo-nome3=Jerome |yearanno=2001 |titletitolo=The Elements of Statistical Learning |url=https://archive.org/details/elementsofstatis0000hast|ISBN=0-387-95284-5 |publishereditore=Springer |___locationcittà=New York |chaptercapitolo=14.3.12 Hierarchical clustering |pagespagine=272&ndash;280272–280|lingua=en}}

== Voci correlate ==

*{{en}} {{cite book|last1=Hastie|first1=Trevor|last2=Tibshirani|first2=Robert|last3=Friedman|first3=Jerome |year=2001 |title=The Elements of Statistical Learning |ISBN=0-387-95284-5 |publisher=Springer |___location=New York |chapter=14.3.12 Hierarchical clustering |pages=272&ndash;280}}

* [[Clustering]]

* [[Dendrogramma]]

== Altri progetti ==

[[Categoria:Apprendimento automatico]]

{{interprogetto|preposizione=sul}}

[[Categoria:Statistica]]

== Collegamenti esterni ==

[[en:Hierarchical clustering]]

*{{cita web |1=https://www.unirc.it/documentazione/materiale_didattico/599_2008_93_1623.pdf |2=(IT) Articolo Il Clustering dell'Unirc |accesso=21 febbraio 2023 }}

{{Apprendimento automatico}}

{{Controllo di autorità}}

{{Portale|statistica|informatica}}

[[Categoria:Apprendimento automatico]]

[[Categoria:Intelligenza artificiale]]

[[Categoria:StatisticaAnalisi dei cluster]]