Clustering Flashcards
Cos’è il clustering?
l clustering è una tecnica di apprendimento automatico non supervisionato che mira a suddividere un insieme di dati in gruppi omogenei, chiamati cluster, in base alle similarità o alle relazioni intrinseche tra gli elementi del dataset. L’obiettivo principale del clustering è quello di trovare strutture o pattern nascosti nei dati senza la necessità di etichette o informazioni preesistenti.
L’algoritmo di clustering analizza i dati e cerca di identificare gruppi di punti dati che sono più simili tra loro rispetto ad altri punti dati nel dataset. La similarità viene generalmente misurata utilizzando una misura di distanza o una metrica di similarità, come la distanza euclidea o la correlazione.
I punti dati all’interno di un cluster dovrebbero essere simili tra loro, mentre i punti dati in cluster diversi dovrebbero essere dissimili. L’obiettivo è quindi massimizzare la similarità all’interno di un cluster e minimizzare la similarità tra i cluster.
Cos’è il cluster gerarchico?
Il clustering gerarchico è un algoritmo di clustering che organizza i dati in una struttura gerarchica di cluster. A differenza del clustering flat (come il k-means), in cui si ottiene una partizione piatta dei dati in un numero fisso di cluster, il clustering gerarchico costruisce una gerarchia di cluster nidificati, in cui i cluster possono essere aggregati o divisi in base alle similarità tra di loro.
L’algoritmo di clustering gerarchico può essere suddiviso in due approcci principali: il clustering gerarchico agglomerativo e il clustering gerarchico divisivo.
Clustering gerarchico agglomerativo: Questo approccio inizia considerando ogni punto dati come un cluster indipendente e procede aggregando iterativamente i cluster più simili fino a quando tutti i punti dati appartengono a un unico grande cluster. L'aggregazione dei cluster viene effettuata in base alle misure di similarità o dissimilarità tra i cluster, come la distanza euclidea o la correlazione. Durante il processo, viene costruita una struttura gerarchica a dendrogramma che rappresenta i cluster nidificati. Clustering gerarchico divisivo: Questo approccio inizia con un unico grande cluster che contiene tutti i punti dati e procede suddividendo iterativamente il cluster in sotto-cluster più piccoli fino a quando ogni punto dati rappresenta un cluster separato. La divisione dei cluster viene effettuata in base alle misure di dissimilarità tra i punti dati o i sotto-cluster. Anche in questo caso, viene costruito un dendrogramma che rappresenta la gerarchia dei cluster.
La scelta tra l’approccio agglomerativo e quello divisivo dipende dalle caratteristiche dei dati e dagli obiettivi dell’analisi. L’algoritmo di clustering gerarchico offre la flessibilità di esplorare cluster di diversa dimensione e complessità, consentendo una rappresentazione grafica intuitiva dei risultati attraverso il dendrogramma.
Ogni cluster ha un centroide che è un punto che rappresenta la media dei suoi punti (dati).
Si misurano le distanze dei cluster in base alle distanze dei centroidi.
Nel caso di uno spazio non euclideo, si calcola il clustroide che è il punto esistente tra i dati più vicino agli altri punti, e si tratta come se fosse un centroide per misurare la distanza dagli altri
K-means(CLUSTERING)
Inizia selezionando “k”, il numero di cluster. Inizializza i cluster selezionando un punto per cluster.
L’algoritmo K-means funziona nel seguente modo:
Inizializzazione: Si sceglie un numero predefinito di cluster, indicato come "K", e si selezionano casualmente K punti come centroidi iniziali. Questi centroidi rappresentano i punti attorno ai quali i cluster verranno costruiti. Assegnazione: Ogni punto nel dataset viene assegnato al cluster il cui centroide è più vicino in base a una metrica di distanza, comunemente la distanza euclidea. In pratica, si calcola la distanza tra ogni punto e tutti i centroidi e si assegna il punto al cluster del centroide più vicino. Ricalcolo dei centroidi: Una volta che tutti i punti sono stati assegnati a un cluster, i centroidi dei cluster vengono ricalcolati come la media dei punti appartenenti a ciascun cluster. Questo sposta il centroide verso il "centro" del cluster. Iterazione: I passaggi 2 e 3 vengono ripetuti iterativamente fino a quando i centroidi smettono di cambiare significativamente o fino a quando è soddisfatto un criterio di convergenza predefinito, come un numero massimo di iterazioni. Risultato: Una volta che l'algoritmo ha convergito, i punti sono stati assegnati in modo definitivo ai cluster. Il risultato è una partizione dei dati in K cluster, ognuno dei quali è rappresentato dal suo centroide.
Cos’è il BFR?
È una variante di K-Means progettata per gestire set di dati molto grandi (residenti su disco).
L’obiettivo è che la memoria richiesta sia di complessità simile a O(clusters) 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 “k” punti casuali
* Si prende un piccolo campione casuale e 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 selezionato
A questo punto, abbiamo tre serie di punti di cui teniamo traccia:
* Discard set (DS): Punti abbastanza vicini a un centroide per essere riassunti. Ogni DS è riassunto
con statistiche come numero di elementi, la somma degli elementi, e la somma dei quadrati.
* Compression set (CS): Gruppi di punti vicini tra loro ma non vicini ad un centroide esistente. Questi
punti formano minicluster. Sono riassunti in minicluster, ma non assegnato a un cluster.
* Retained set (RS): Punti isolati in attesa di essere assegnati a un minicluster
I passi dell’algoritmo:
1. Si effettua un caricamento nella memoria principale di un campione di dati
2. Si trovano quei punti che sono “sufficientemente vicini” ad un centroide del cluster e si aggiungono a quel cluster ed al DS
3. Per i restanti punti si utilizza qualsiasi algoritmo di clustering per raggrupparli insieme a punti della vecchia RS.
Punti raggruppati andranno a far parte del nuovo CS.
4. Si regolano le statistiche dei cluster DS, tenendo conto dei nuovi punti
5. Il CS ora ha minicluster vecchi e nuovi. Si considera di unirli, riassumendo le loro statistiche
6. 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
7. 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 mai.
Per decidere se un punto è vicino o meno ad un cluster, il BFR suggerisce l’uso della distanza di
Mahalanobis.
Cos’è L’algoritmo CURE?
Utilizza una distanza euclidea, consente ai cluster di assumere qualsiasi forma, utilizza una raccolta di punti
per rappresentare i cluster.
Il primo passo dell’algoritmo:
1. Si sceglie un campione casuale di punti che rientrano nella memoria principale
2. Cluster iniziali: Si raggruppano questi punti in modo gerarchico
3. Si scelgono i punti più rappresentativi: Per ogni cluster, si sceglie un campione di punti, più dispersi possibile
4. Dal campione, si scelgono i punti isolati del punto 3 spostandoli del (diciamo) 20% verso il
baricentro del cluster
Il secondo passo dell’algoritmo:
1. Ora, si scansiona nuovamente l’intero set di dati e si controlla ogni punto “p” nel set di dati
2. Si posiziona nel cluster più vicino
