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ù
* ''clustering esclusivo'': ogni elemento può essere assegnato ad uno e ad un solo gruppo.
* ''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,''
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
=== Clustering gerarchico ===
Le tecniche di [[clustering gerarchico]] non producono un partizionamento ''flat'' dei punti, ma una rappresentazione gerarchica ad albero. [[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
* ''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
* ''Distanza tra centroidi''
:La distanza tra i due
:<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.
* ''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
* 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;
|