▤ Data visualization

Dendrogram

덴드로그램

A tree-shaped diagram whose branch heights show which items get grouped together, and how dissimilar they were when they merged.

Also known as: Cluster treeHierarchical clustering tree

···

html

<div class="viz">
  <svg id="svg"></svg>
</div>

css

body{display:block}
.viz{position:relative;width:100%;height:100%}
svg{display:block;width:100%;height:100%;overflow:visible}

js

var svg = document.getElementById('svg');
var NS = 'http://www.w3.org/2000/svg';
function se(t){ return document.createElementNS(NS,t); }
function sa(e,o){ for (var k in o) e.setAttribute(k,o[k]); }
function R(a,b){ return a + Math.random()*(b-a); }

var LEAVES = ['A','B','C','D','E','F','G','H'];
var cur = { h1:[30,30,30,30], h2:[55,55], h3:75 };
var W=300, H=200;

function measure(){
  var r = svg.getBoundingClientRect();
  W = Math.max(r.width,10); H = Math.max(r.height,10);
  sa(svg,{ viewBox: '0 0 ' + W + ' ' + H });
}

function draw(){
  svg.innerHTML = '';
  var padL=14,padR=14,padT=14,padB=20;
  var pw=W-padL-padR, ph=H-padT-padB;
  var n=LEAVES.length;
  var leafX = LEAVES.map(function(_,i){ return padL + pw*(i+0.5)/n; });
  var baseline = padT+ph;
  function yFor(hpct){ return baseline - (hpct/100)*ph; }

  LEAVES.forEach(function(name,i){
    var t = se('text');
    sa(t,{ x:leafX[i], y:baseline+13, 'text-anchor':'middle', fill:'var(--muted)', 'font-size':Math.max(7,Math.min(10,W/50)), 'font-weight':600 });
    t.textContent = name;
    svg.appendChild(t);
  });

  function link(xA,yA,xB,yB,yP){
    var d = 'M'+xA.toFixed(1)+','+yA.toFixed(1)+'V'+yP.toFixed(1)+'H'+xB.toFixed(1)+'V'+yB.toFixed(1);
    var p = se('path');
    sa(p,{ d:d, fill:'none', stroke:'var(--accent)', 'stroke-width':1.6, 'stroke-linecap':'round' });
    svg.appendChild(p);
  }

  var level1X=[];
  for (var k=0;k<4;k++){
    var a=2*k, b=2*k+1;
    var yP = yFor(cur.h1[k]);
    link(leafX[a], baseline, leafX[b], baseline, yP);
    level1X.push((leafX[a]+leafX[b])/2);
  }
  var level2X=[];
  for (var k2=0;k2<2;k2++){
    var a2=2*k2, b2=2*k2+1;
    var yA = yFor(cur.h1[a2]), yB = yFor(cur.h1[b2]);
    var yP2 = yFor(cur.h2[k2]);
    link(level1X[a2], yA, level1X[b2], yB, yP2);
    level2X.push((level1X[a2]+level1X[b2])/2);
  }
  var yA3 = yFor(cur.h2[0]), yB3 = yFor(cur.h2[1]), yP3 = yFor(cur.h3);
  link(level2X[0], yA3, level2X[1], yB3, yP3);
}

function animate(target){
  var fromH1 = cur.h1.slice(), fromH2 = cur.h2.slice(), fromH3 = cur.h3;
  var t0 = performance.now();
  function step(t){
    var p = Math.min(1,(t-t0)/750);
    var e = 1-Math.pow(1-p,3);
    cur = {
      h1: fromH1.map(function(v,i){ return v+(target.h1[i]-v)*e; }),
      h2: fromH2.map(function(v,i){ return v+(target.h2[i]-v)*e; }),
      h3: fromH3+(target.h3-fromH3)*e
    };
    draw();
    if (p<1) requestAnimationFrame(step);
  }
  requestAnimationFrame(step);
}

function nextTarget(){
  return { h1: [R(18,38),R(18,38),R(18,38),R(18,38)], h2: [R(45,62),R(45,62)], h3: R(70,90) };
}

new ResizeObserver(function(){ measure(); draw(); }).observe(svg);
measure();
draw();
animate(nextTarget());
setInterval(function(){ animate(nextTarget()); }, 3800);

A direct picture of the output of hierarchical clustering. Each leaf is an original item, and the height where two branches merge represents "how dissimilar these two were when they got grouped" — an early merge at low height means they're similar; a merge only reached at high height means they're quite different.

The most common misreading is the horizontal order. The left-to-right arrangement of leaves is just one arbitrary layout chosen to draw the tree — being next to each other doesn't mean two items are more similar. Actual similarity is judged only by the height at which two items' branches meet. Flip a branch left-to-right and the leaf order changes completely, yet the tree still carries the exact same information (what merges at what height).

When cutting the tree horizontally to decide on a number of clusters, the cut height shouldn't be picked arbitrarily — look for an unusually large gap between consecutive merge heights and cut inside that gap, so the cut lands on a real separation in the data rather than an arbitrary one.

When to use

Use it to show the result of hierarchically clustering items or their similarity relationships. With very many items, leaves overlap and become unreadable — trim to a subset or use a different clustering view.