CLUSTERING Flashcards
Cos’è il clustering?
Clustering ha l’obiettivo di raggruppare all’interno dello stesso cluster elementi simili tra loro e di non avere similarità con gli altri cluster.
La similitudine tra due elementi si ottiene usando una funzione di distanza.
Ci sono 2 approcci:
- Agglomerativi: si considera un cluster per elemento e si prosegue combinando passo dopo passo i cluster più vicini
- Divisivo: si parte da un singolo cluster con tutti gli elementi e si continua a suddividere fino ad ottenere k cluster
Ogni cluster ha un centroide che è un punto che rappresenta la media dei suoi punti. Si misura la distanza tra cluster in base alla distanze dei centroidi.
Possibili significati di punto più vicino ad altri:
- La più piccola distanza massima da altri punti
- Distanza media più piccola da altri punti
- Somma minima dei quadrati delle distanze da altri punti
K-Means
Inizia selezionando k numero di cluster. Inizializza i cluster selezionando un punto per cluster.
1. Per ogni punto, posizionalo nel cluster il cui centroide è più vicino
2. Dopo aver assegnato tutti i punti, aggiorna le posizioni dei centroidi dei k cluster
3. Riassegna tutti i punti al centroide più vicino
4. Sposta i punti tra i cluster
5. Ripeti 2 e 3 fino alla convergenza
Convergenza: punti non si spostano più e i centroidi sono stabili
Per decidere il valore ottimale di k si osserva la variazione della distanza media dal centroide all’aumentare di k. La media scende rapidamente fino a che k diventa ottimale, poi cambia poco.
BFR
È una variante del k-means progettata per gestire set di dati molto grandi. L’obiettivo è che la memoria richiesta sia di complessità simile a O(cluster) piuttosto che O(dati).
La maggior parte dei punti sono riassunti da semplici statistiche.
Per iniziare, si selezionano gli iniziali k centroidi con uno dei seguenti approcci:
- Si prendono in modo casuale
- Si prende un campione casuale e lo si raggruppa in modo ottimale
- Si prende un campione, si sceglie un punto a caso, e poi k-1 punti in più, ciascuno il più lontano possibile da quello precedentemente scelto
A questo punto abbiamo tre serie di punti da tener traccia:
- Discard set DS: punti abbastanza vicini a un centroide per essere riassunti.
- Compression set CS: gruppi di punti vicini tra loro ma non vicini ad un centroide esistente. Formano minicluster. Non assegnati
- Retainde set RS: punti isolati in attesa di essere assegnati a un minicluster
I passi dell’algoritmo:
- Si effettua un caricamento in memoria di un campione di dati
- Si trovano quei punti che sono sufficientemente vicini ad un centroide del cluster e si aggiungono a quel cluster e al DS
- Per i restanti punti si utilizza qualsiasi algoritmo di clustering per raggrupparli iniseme a punti della vecchia RS, punti raggruppati faranno parte del nuovo CS
- Si regolano le statistiche dei cluster DS, tenendo conto dei nuovi punti
- Il CS ora ha minicluster vecchi e nuovi. Si considera di unirli, riassumendo le loro statistiche
- Punti assegnati a un cluster di DS o minicluster del CS vengono scartati e scritti nella memoria secondaria insieme al cluster o minicluster di appartenenza
- Se questo è l’ultimo round, unisci tutti i minicluster nel CS e tutti i punti RS nel cluster DS più vicino o trattali come valori anomali e non raggrupparli
Per decidere se un punto è vicino o meno ad un cluster. Il BFR suggerisce l’uso della distanza di Mahalsnobis.
CURE alghoritm
Utilizza la distanza euclidea, utilizza una raccolta di punti per rappresentare i cluster.
Primo passo dell’algoritmo:
- Si sceglie un campione casuale di punti che rientrano in memoria principale
- Si raggruppano questi punti in modo gerarchico
- Si scelgono i punti più rappresentativi: per ogni cluster, si sceglie un campione di punti, più dispersi possibile
- Dal campione, si scelgono i punti isolati del punti 3 spostandoli del 20% verso il centroide del cluster
Secondo passo:
- Ora si scansiona nuovamente l’intero set di dati e si controlla ogni punto nel set di dati
- Si posiziona nel cluster più vicino
