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

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

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.

Fig.3 Il dendrogramma
Fig.3 Il dendrogramma
libro

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.

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.

Lascia un commento

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.