Panoramica dell'analisi dei cluster gerarchici
Prima di andare avanti e comprendere l'analisi dei cluster gerarchici, proviamo a capire cos'è un cluster? E cos'è l'analisi dei cluster? Un cluster è una raccolta di oggetti dati; i punti dati all'interno di un cluster sono più simili tra loro e dissimili dai punti dati nell'altro cluster. L'analisi del cluster è fondamentalmente un raggruppamento di questi punti dati nel cluster. Il clustering è un tipo di algoritmo di machine learning senza supervisione, in cui non esistono set di dati con etichetta di training. Esistono vari tipi di analisi del clustering, uno di questi è il clustering gerarchico.
Il clustering gerarchico aiuterà a creare cluster in un ordine / gerarchia adeguati. Esempio: l'esempio quotidiano più comune che vediamo è il modo in cui ordiniamo i nostri file e cartelle nel nostro computer secondo una corretta gerarchia.
Tipi di cluster gerarchici
Il clustering gerarchico è ulteriormente classificato in due tipi, ad esempio cluster agglomerativo e Divisive Clustering (DIANA)
Cluster agglomerativo
In questo caso di clustering, la decomposizione gerarchica viene eseguita con l'aiuto della strategia bottom-up in cui inizia creando cluster atomici (piccoli) aggiungendo un oggetto dati alla volta e quindi li unisce per formare un grande cluster alla fine, in cui questo cluster soddisfa tutte le condizioni di terminazione. Questa procedura è iterativa fino a quando tutti i punti dati non vengono portati in un unico grande cluster.
AGNES (AGglomerative NESting) è un tipo di cluster agglomerativo che combina gli oggetti dati in un cluster in base alla somiglianza. Il risultato di questo algoritmo è un strutturato ad albero chiamato Dendrogram. Qui utilizza le metriche della distanza per decidere quali punti dati devono essere combinati con quale cluster. Fondamentalmente, costruisce una matrice di distanza e controlla la coppia di cluster con la distanza più piccola e li combina.
La figura sopra mostra il clustering Agglomerativo vs. Divisivo
Sulla base di come viene misurata la distanza tra ciascun cluster possiamo avere 3 metodi diversi
- Collegamento singolo : dove la distanza più breve tra i due punti in ciascun cluster è definita come la distanza tra i cluster.
- Collegamento completo : in questo caso, considereremo la distanza più lunga tra i punti in ciascun cluster come la distanza tra i cluster.
- Collegamento medio: qui prenderemo la media tra ciascun punto in un cluster e ogni altro punto nell'altro cluster.
Ora discutiamo dei punti di forza e di debolezza di AGNES; questo algoritmo ha una complessità temporale di almeno O (n 2 ) quindi non funziona bene nel ridimensionamento e un altro grande svantaggio è che qualsiasi cosa sia stata fatta non può mai essere annullata, cioè se raggruppiamo erroneamente un cluster nella fase precedente di l'algoritmo quindi non saremo in grado di cambiare il risultato / modificarlo. Ma questo algoritmo ha anche un lato positivo poiché ci sono molti cluster più piccoli che possono essere formati, può essere utile nel processo di scoperta e produce un ordinamento di oggetti che è molto utile nella visualizzazione.
Divisive Clustering (DIANA)
Diana in sostanza è l'acronimo di Divisive Analysis; questo è un altro tipo di clustering gerarchico in cui fondamentalmente funziona secondo il principio dell'approccio top-down (inverso di AGNES) in cui l'algoritmo inizia formando un cluster di grandi dimensioni e divide in modo ricorsivo il cluster più diverso in due e continua fino a quando ' tutti i punti di dati simili appartengono ai rispettivi cluster. Questi algoritmi di divisione generano gerarchie altamente accurate rispetto all'approccio agglomerativo, ma sono costose dal punto di vista computazionale.
La figura sopra mostra il processo di clustering Divisive passo dopo passo
Clustering gerarchico multifase
Per migliorare la qualità dei cluster generati dalle suddette tecniche di clustering gerarchico, integriamo le nostre tecniche di clustering gerarchico con altre tecniche di clustering; questo si chiama clustering multifase. I diversi tipi di clustering multifase sono i seguenti:
- BIRCH (Riduzione e clustering iterativi bilanciati mediante gerarchie)
- ROCK (RObust Clustering tramite collegamenti)
- CAMALEONTE
1. Riduzione e clustering iterativi bilanciati mediante gerarchie
Questo metodo viene utilizzato principalmente per il raggruppamento di enormi quantità di dati numerici integrando il nostro cluster gerarchico / micro nella fase iniziale e il clustering macro / il partizionamento iterativo nella fase successiva. Questo metodo aiuta a superare il problema di scalabilità riscontrato in AGNES e l'incapacità di annullare ciò che è stato fatto prima del passaggio. BIRCH utilizza due concetti importanti nel suo algoritmo
un. Funzionalità di clustering (aiuta a riepilogare il cluster)
CF è definito come (n- numero di punti dati nel cluster, la somma lineare di n punti, la somma quadrata di n punti). La memorizzazione della funzione di un cluster in questo modo aiuta a evitare la memorizzazione di informazioni dettagliate su di esso e CF è di natura additiva per diversi cluster.
CF 1 + CF 2 =
b. Clustering feature tree (aiuta a rappresentare un cluster come una gerarchia)
L'albero CF è un albero bilanciato con fattore di ramificazione B (numero massimo di figli) e soglia T (numero massimo di sottoclassi che possono essere memorizzati nei nodi foglia).
L'algoritmo funziona fondamentalmente in 2 fasi; nella fase 1 esegue la scansione del database e crea un albero CF in memoria e nella fase 2 utilizza l'algoritmo di clustering che aiuta a raggruppare i nodi foglia rimuovendo gli outlier (cluster sparsi) e raggruppa il cluster con la massima densità. L'unico inconveniente di questo algoritmo è che gestisce solo il tipo di dati numerici.
2. Clustering robusto tramite link
Il collegamento è definito come il numero di vicini comuni tra due oggetti. L'algoritmo ROCK è un tipo di algoritmo di clustering che utilizza questo concetto di collegamento con il set di dati categoriale. Come sappiamo che gli algoritmi di clustering misurati in base alla distanza non forniscono cluster di alta qualità per il set di dati categoriale, ma nel caso di ROCK, considera anche i quartieri dei punti dati, ovvero se due punti dati hanno lo stesso vicinato, allora lo sono molto probabilmente appartiene allo stesso cluster. L'algoritmo costruirà un grafico sparso nel primo passo tenendo conto della matrice di somiglianza con il concetto di vicinato e soglia di somiglianza. Nel secondo passaggio, utilizza la tecnica di raggruppamento gerarchico agglomerativo sul grafico rado.
3. Camaleonte
Questo tipo di algoritmo di clustering gerarchico utilizza il concetto di modellazione dinamica. Ti chiedi perché si chiama dinamico? Si chiama dinamico perché ha la capacità di adattarsi automaticamente alle caratteristiche interne del cluster valutando la somiglianza del cluster, ovvero quanto siano ben collegati i punti dati all'interno di un cluster e in prossimità dei cluster. Uno degli svantaggi del camaleonte è che il costo di elaborazione è troppo elevato (O (n 2 ) per n oggetti è la complessità temporale peggiore).
Fonte immagine - Google
Conclusione
In questo articolo, abbiamo imparato cos'è un cluster e cos'è l'analisi del cluster, diversi tipi di tecniche di clustering gerarchico i loro vantaggi e svantaggi. Ognuna delle tecniche di cui abbiamo discusso ha i suoi aspetti positivi e negativi, quindi prima di procedere con un algoritmo dobbiamo comprendere i nostri dati con un'adeguata analisi dei dati esplorativi e scegliere l'algoritmo con cautela.
Articoli consigliati
Questa è una guida all'analisi dei cluster gerarchici. Qui discutiamo la panoramica, il clustering agglomerativo, il clustering divisivo (DIANA) e il clustering gerarchico multifase. Puoi anche consultare i seguenti articoli per saperne di più
- Clustering gerarchico in R
- Algoritmo di clustering
- cluster
- Metodi di clustering
- Clustering in Machine Learning
- Clustering gerarchico Clustering agglomerativo e divisivo