Clustering: differenze tra le versioni

Versione delle 21:30, 7 dic 2015

Versione delle 23:48, 27 gen 2016

Riga 29:

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 clusters, 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.

Riga 37:

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:

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