Come realizzare un dendrogramma con la libreria D3 (parte 1)

Post Views: 47.967

In questa serie di articoli impareremo a realizzare un dendrogramma su web utilizzando la libreria grafica D3.

D3 - come realizzare un dendrogramma parte 1

I dendrogrammi sono uno strumento grafico molto utile per l’analisi dei gruppi (cluster analysis o clustering). Il dendrogramma è essenzialmente un grafo ad albero.

Si parte da un punto di origine, la radice, (root) da cui si dipartono dei rami (links) che terminano in nodi (nodes); da questi nodi, a loro volta, si dipartiranno altri rami che termineranno anch’essi in nodi, e così via, fino ad arrivare a dei nodi terminali, da cui non si dipartirà alcun ramo, dette foglie(leaves).

tree-structure — Fig.1: struttura ad albero

(Note: per semplicità ho usato delle frecce, in realtà l’albero è un grafo non orientato).

Queste strutture ad albero rappresentano delle strutture a livelli gerarchici, dove a partire dalla radice, che definiremo a livello 0, ogni generazione di nodi definirà un livello successivo (livello 1, livello 2, fino ad arrivare al livello n-1 delle foglie, dove n è detta altezza (depth) del grafo.

tree-structure2 — Fig.2: livelli di una struttura ad albero

Il dendrogramma, in particolare, è il risultato di un algoritmo o metodo gerarchico, in cui oltre alla struttura gerarchica, con le successive ripartizioni nei vari livelli in n unità, viene riportato anche il livello di distanza ultrametrica.

Ogni ramo del dendrogramma corrisponde ad un gruppo o cluster mentre i nodi di dipartizione in due o più rami individuano il livello di distanza al quale i vari cluster si fondono.

Ci sono varie metodologie per il calcolo delle distanze tra i vari raggruppamenti, tra cui il metodo del centroide, che ho trattato nel libro Beginning Javascript Charts with jqPlot, D3 and Highcharts, (2013) Apress. Altre metodologie sono:

metodo del legame singolo
metodo del legame completo
metodo del legame medio
metodo di Ward
metodo del centroide (già citato)

Molto probabilmente, in futuri articoli tratterò nel dettaglio questi vari metodi. Comunque è possibile trovare in rete (abbastanza facilmente) algoritmi già implementati in diversi linguaggi di programmazione.

Come punto di partenza ho fatto riferimento al dendrogramma di esempio di M. Bostock (l’ideatore della libreria D3) #4063570 (http://bl.ocks.org/mbostock/4063570).

dendrogr_bostock1 — Fig.4: esempio di Bostock

In realtà se fate attenzione l’esempio riportato non è affatto un dendrogramma, bensì una semplice struttura ad albero. Infatti i nodi per ciascun livello sono tutti allineati sulla stessa verticale e quindi le distanze ultrametriche non vengono affatto contemplate. Negli esempi che svilupperemo in questa serie di articoli, implementeremo tutto il codice necessario per poter realizzare dei reali dendrogrammi in cui anche le distanze siano contemplate nella visualizzazione.

dendrogr_bostock2 — Fig.5: i nodi dello stesso livello sono allineati verticalmente

Quindi la rappresentazione effettuata nell’esempio di Bostock riporta solo le informazioni gerarchiche e di raggruppamento dei cluster (approccio qualitativo), senza però tenere conto delle distanze con cui questi cluster si distanziano l’uno dall’altro (approccio quantitativo).

Ma non finisce qui, nell’ultimo esempio, introdurremo un’ulteriore distanza, che quantifica in un modo alternativo (e supplementare) la distanza tra i vari elementi clusterizzati, cioè le foglie. In questo caso le foglie del dendrogramma non saranno più rappresentate uniformemente tutte alla stessa distanza, così come le dipartizioni dei rami per ogni nodo genitore non saranno più simmetriche.

dendrogrammaXY — Fig.6: dendrogramma a due distanze

Tenendo conto di questa ulteriore particolarità è possibile ottenere anche dei rami sovrapposti. Probabilmente in questo caso la clusterizzazione non è stata fatta in base alla distribuzione delle foglie lungo la distanza x (dato che la clusterizzazione dovrebbe basarsi sulla similarità dei campioni).

dendrogrammaXY2 — Fig.7: dendrogramma in cui i rami si sovrappongono

Ma adesso cominciamo con il primo esempio di dendrogramma. Per prima cosa implementeremo una struttura ad albero in tutto e per tutto simile a quella dell’esempio di Bostock, ma molto più semplice, in modo da focalizzare meglio gli aspetti basilari di quello che stiamo sviluppando.

dendrogram_es01 — Fig.8: struttura ad albero

Come possiamo vedere la struttura è a due livelli (più quello di root) e ho opportunamente etichettato ciascun nodo con il corrispettivo ruolo all’interno della struttura ad albero.

Questa stuttura ad albero dovrà essere scritta in uno specifico formato, in modo da poter essere leggibile dal codice JavaScript che stiamo per implementare. Quale miglior formato se non JSON?

Quindi con un editor di testo qualsiasi, scriviamo la struttura ad albero nella Fig.8 nel formato JSON e poi salviamolo come dendrogram01.json.

{   "name": "root",   
    "children": [     
            {"name": "parent A",      
             "children": [        
                   {"name": "child A1"},        
                   {"name": "child A2"},        
                   {"name": "child A3"}      
             ]     
            },{"name": "parent B",      
             "children": [        
                  {"name": "child B1"},        
                  {"name": "child B2"}      
             ]     
            }   ] 
}

Nel prossimo articolo concluderemo questo esempio, sviluppando all’interno di una pagina HTML il codice necessario per leggere correttamente i dati contenuti nel file JSON appena scritto, e a rappresentare una struttura ad albero in base ai dati immessi.

Prossimo articolo:

Come realizzare un dendrogramma con la libreria D3 (parte 2)

Lascia un commento Annulla risposta