Clustering: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Aggiunto collegamento esterno
m Corretto plurale di parole straniere: in italiano sono invarianti.
Riga 9:
 
== Tecniche di clustering ==
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:
* ''clustering 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 ''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 fuzzy]]).
 
Un'altra suddivisione delle tecniche di clustering tiene conto del tipo di algoritmo utilizzato per dividere lo spazio:
Riga 22:
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 clusterscluster, <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 [[Partitioning Around Medioid]] (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.
 
Line 46 ⟶ 45:
: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>.
 
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 78 ⟶ 77:
 
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 così 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;