Generated enhanced dendrograms and tanglegrams. Inspired by the amazing dendextend by Tal Galili.
- dendrograms with additional features compared to scipy: cluster colouring, leaf annotation tracks, collapsed clades, radial layouts
- tanglegrams of two or more dendrograms, stacked or circular, with shared cluster colours
- alluvial view of how cluster membership changes between clusterings
- measures of how similar two trees are, independent of how they are drawn
matplotliborplotlyas plotting backend
First, get PIP and then run in terminal:
pip3 install tanglegram -U
To install the bleeding-edge version from Github you can run:
pip3 install git+https://github.com/schlegelp/tanglegram@master
Installing via PIP should install all external dependencies. You may run into problems on Windows though. In that case, you need to install dependencies manually, here is a list of dependencies (check out dependencies in pyproject.toml for version info):
tanglegram exposes these functions:
tanglegram.dendrogramplots a simple dendrogamtanglegram.tanglegramplots a side-by-side tanglegram for two dendrogamstanglegram.tanglegram_manyplots a tanglegram for two or more dendrogams as rowstanglegram.entanglementmeasures the entanglement between two linkagestanglegram.crossingscounts how many pairs of edges crosstanglegram.untanglerotates dendrograms to minimize entanglement or crossingstanglegram.alignment_qualityjudges an alignment against what the trees allowtanglegram.cophenetic_correlationandtanglegram.baker_gammameasure how similar two trees aretanglegram.cluster_flowshows how cluster membership moves between clusteringstanglegram.cluster_color_mapbuilds one colour mapping shared across plots
import tanglegram as tg
import matplotlib.pyplot as plt
import pandas as pd
# Generate two distance matrices and just switch labels in one
labelsA= ['A', 'B', 'C', 'D']
labelsB= ['B', 'A', 'C', 'D']
data = [[ 0, .1, .4, .3],
[.1, 0, .5, .6],
[.4, .5, 0, .2],
[.3, .6, .2, 0]]
mat1 = pd.DataFrame(data,
columns=labelsA,
index=labelsA)
mat2 = pd.DataFrame(data,
columns=labelsB,
index=labelsB)
# Plot tanglegram
fig, dn1, dn2 = tg.tanglegram(mat1, mat2, sort=False)
plt.show() # Plot again but this time try minimizing cross-over
fig, dn1, dn2 = tg.tanglegram(mat1, mat2, sort=True)
plt.show()See more elaborate examples below!
tanglegram.dendrogram takes the same keyword arguments as scipy's own
dendrogram and passes them straight through, so you can treat it as a drop-in
replacement. It returns (dn, ax) - the dendrogram dictionary scipy would have
given you, plus the axis (or, with backend="plotly", the figure).
All the examples below share this setup - four groups of six samples with enough overlap that clustering does not recover the groups perfectly:
import matplotlib.pyplot as plt
import numpy as np
import scipy.cluster.hierarchy as sch
import tanglegram as tg
rng = np.random.default_rng(4)
centers = np.array([[0, 0], [3, 0.5], [1.5, 3], [4.5, 3.5]], dtype=float)
groups = np.repeat(np.arange(4), 6)
X = centers[groups] + rng.normal(0, 0.9, (24, 2))
Z = sch.linkage(X, method="ward")
group_names = np.array(["A", "B", "C", "D"])[groups]scipy can only colour a dendrogram by cutting it at a single height
(color_threshold). clusters instead takes one label per observation, so the
colouring can come from anywhere - known sample categories, a non-uniform cut,
or any other assignment:
fig, axes = plt.subplots(1, 2, figsize=(11, 3.6), sharey=True)
sch.dendrogram(Z, color_threshold=0.7 * Z[:, 2].max(), ax=axes[0])
tg.dendrogram(Z, clusters=group_names, ax=axes[1])On the left, scipy's threshold produces contiguous blocks by construction. On
the right the colours follow the known group of each sample, which the tree
only partly recovers - so several groups show up in more than one place, and
the links that span more than one group are drawn in above_threshold_color.
Each branch is coloured by the group it leads to, which is why the stem above a
group is coloured too. This also means a group of a single leaf still gets its
own colour, which is not something color_threshold can express.
Note that clusters is indexed like your observations, not in leaf order,
and that colours are handed out in order of each cluster's first appearance -
so they stay stable between runs.
Leafs whose cluster is None or NaN are left unassigned, which makes it easy
to pull out just the clades you care about. above_threshold_ls styles
everything else out of the way:
cut = sch.fcluster(Z, 4, criterion="maxclust")
highlight = np.where(np.isin(cut, [1, 3]), cut, None)
dn, ax = tg.dendrogram(
Z,
clusters=highlight,
cluster_colors={1: "#d62728", 3: "#1f77b4"},
above_threshold_color="lightgrey",
above_threshold_ls="--",
)hanging shortens the leaf links so they hang off their parent instead of
reaching all the way down to the baseline, and leaf_marker marks the tips.
Marker colours default to each leaf's own branch colour:
fig, axes = plt.subplots(2, 1, figsize=(9, 6), sharex=True)
tg.dendrogram(Z, clusters=group_names, hanging=True, leaf_marker="o", ax=axes[0])
tg.dendrogram(Z, clusters=group_names, hanging=0.02, leaf_marker="o", ax=axes[1])hanging=True drops each leaf by 5% of the tree height. Pass a fraction to
tune it: smaller values hug the parent more closely, larger ones drop the leafs
further until they hit the baseline. Leafs never fall below zero.
small = sch.linkage(X[:8], method="ward")
dn, ax = tg.dendrogram(small, label_dist=True, dist_fmt="{:.2f}")leaf_annot draws one or more metadata tracks as a colour strip beside the
leafs, like row_colors in seaborn's clustermap. Pass a DataFrame (one column
per track), a {name: values} dict, or a flat sequence for a single track:
import pandas as pd
metadata = pd.DataFrame({
"group": group_names,
"batch": np.tile(["b1", "b2", "b3"], 8),
"qc": np.where(rng.random(24) > 0.25, "pass", "fail"),
})
dn, ax = tg.dendrogram(
Z,
clusters=group_names,
leaf_annot=metadata,
annot_colors={"pass": "#4caf50", "fail": "#e53935"},
)Values are per observation. Anything that already looks like a colour is used
as-is; everything else is treated as a category and coloured for you.
annot_colors only has to cover the values you care about - here it fixes the
two qc values and leaves group and batch to colour themselves. The leaf
labels move onto the strip so the two do not fight over the same space, and
annot_legend=True adds a legend.
Past a few hundred leafs a dendrogram stops being readable. collapse draws
whole clades as a single wedge instead:
big = sch.linkage(rng.random((150, 4)), method="ward")
big_clusters = sch.fcluster(big, 6, criterion="maxclust")
tg.dendrogram(big, clusters=big_clusters, no_labels=True)
tg.dendrogram(big, clusters=big_clusters, collapse="clusters", collapse_width=3)collapse accepts three things:
| value | collapses |
|---|---|
"clusters" |
each cluster that forms a clade of its own (needs clusters) |
| a number | every clade no taller than that height |
| a callable | every clade for which f(observations) is true, e.g. lambda lv: len(lv) <= 10 |
Only the topmost matching clade on each path is collapsed, so a predicate
should describe a clade that is small or uniform enough to fold away. The
returned dict gains a "collapsed" entry mapping each wedge to the
observations behind it:
dn, ax = tg.dendrogram(big, collapse=lambda leaves: len(leaves) <= 10)
{node: len(members) for node, members in dn["collapsed"].items()}Note that with collapse the dict's "leaves" and "ivl" describe what is
drawn rather than every leaf, so per-observation arguments (leaf_annot, a
per-leaf leaf_color, hover_info) no longer have anything to attach to and
are rejected.
polar=True wraps the tree around a circle, leafs on the rim and the root at
the centre. If you pass your own ax it has to use a polar projection:
fig = plt.figure(figsize=(5.5, 5.5))
dn, ax = tg.dendrogram(Z, clusters=group_names, polar=True,
leaf_marker="o", leaf_size=20)backend="plotly" renders the same tree as an interactive figure, and
hover_info attaches a note to each leaf:
dn, fig = tg.dendrogram(
Z,
clusters=group_names,
hover_info=[f"sample {i}" for i in range(len(X))],
leaf_marker="o",
hanging=0.02,
backend="plotly",
)
fig.show()To draw onto a specific subplot of an existing figure, pass a dict:
from plotly.subplots import make_subplots
fig = make_subplots(rows=1, cols=2)
tg.dendrogram(Z, backend="plotly", fig={"fig": fig, "row": 1, "col": 2})| argument | what it does |
|---|---|
clusters |
Cluster assignment per observation. Unlike color_threshold it need not follow a single cut, and a cluster of one leaf is coloured too. None/NaN means unassigned. |
cluster_colors |
A {cluster: color} mapping, or a sequence cycled in order of first appearance. Defaults to matplotlib's colour cycle. |
above_threshold_color / above_threshold_ls |
Colour and line style for links that span more than one cluster. |
label_dist / dist_fmt |
Label every link with its distance. |
leaf_marker / leaf_color / leaf_size |
Mark the leafs; colours default to each leaf's own branch colour. |
hanging |
Shorten the leaf links so they hang off their parent. True drops them by 5% of the tree height, or pass a fraction. |
leaf_annot / annot_colors / annot_size / annot_legend |
Metadata tracks drawn as a colour strip beside the leafs. matplotlib only. |
collapse / collapse_width / collapse_label |
Draw whole clades as a wedge to make a large tree readable. |
polar |
Draw the tree radially. matplotlib only. |
backend / hover_info / fig |
"matplotlib" (default) or "plotly"; per-leaf hover text and the target figure for the latter. |
clusters cannot be combined with scipy's truncate_mode (truncation collapses
leafs, so the assignments no longer line up with what is drawn), and no_plot
and link_color_func are managed internally.
The images above are generated by docs/make_readme_images.py.
clusters_left/clusters_right colour the two dendrograms, and both sides
draw from one palette - so a cluster that turns up in both is the same
colour in both, which is the whole point when you are comparing them.
color_edges_by then carries that colouring onto the connecting edges:
import scipy.spatial.distance as ssd
# The same 24 samples, clustered twice with a little noise between the two
labels = [f"s{i}" for i in range(24)]
dist_a = pd.DataFrame(ssd.squareform(ssd.pdist(X)), index=labels, columns=labels)
dist_b = pd.DataFrame(
ssd.squareform(ssd.pdist(X + rng.normal(0, 0.6, X.shape))),
index=labels, columns=labels,
)
fig, dn1, dn2 = tg.tanglegram(
dist_a, dist_b,
sort=True,
clusters_left=group_names,
clusters_right=group_names,
color_edges_by="left", # or "right"
)Colouring the edges by cluster turns "did this group stay together?" into
something you can read off the picture. Pass cluster_colors to pin the
colours yourself. tanglegram_many takes the same treatment via clusters=,
which expects one assignment per dendrogram.
If you need the same colours somewhere else, cluster_color_map builds the
shared mapping on its own:
colors = tg.cluster_color_map(group_names, group_names)tanglegram_many stacks any number of dendrograms as rows and connects each
one to the next. It takes clusters as a list with one assignment per
dendrogram, and - like tanglegram - draws them all from a single palette, so
a cluster keeps its colour the whole way down:
# Half the samples, so the connecting lines stay readable across three panels
few = X[::2]
few_names = group_names[::2]
few_labels = [f"s{i}" for i in range(len(few))]
def view(noise, seed):
jittered = few + np.random.default_rng(seed).normal(0, noise, few.shape)
return pd.DataFrame(ssd.squareform(ssd.pdist(jittered)),
index=few_labels, columns=few_labels)
fig, dns = tg.tanglegram_many(
[view(0, 0), view(0.5, 1), view(1.0, 2)],
sort=True,
clusters=[few_names] * 3,
figsize=(8, 8),
)Three views of the same twelve samples with increasing noise, so the trees agree less and less as you go down. Sorting is done pairwise from the top: the first pair is untangled two-sided, and every pair after that has its upper dendrogram already pinned, so only the lower one can still rotate.
It returns the figure plus one dendrogram per input, in the same order, so
dns[1]["ivl"] gives you the leaf order of the middle tree.
Every tree here has its leafs along the bottom, so a connector has to cross the panel below it - keep the number of leafs modest or the lines become hard to follow.
The stacked layout has a limit that no amount of tweaking fixes: a tree has one leaf row, at one end, so a middle tree can never sit next to both its neighbours and some connector always has to cross a tree.
layout="circular" sidesteps it. Point the trees outwards from a shared inner
ring and every leaf row lands on the same circle, so a connector is just a
chord across the middle and crosses nothing at all:
fig, dns = tg.tanglegram_many(
[view(0, 0), view(0.5, 1), view(1.0, 2)],
sort=True,
clusters=[few_names] * 3,
layout="circular",
color_edges_by="source",
names=["baseline", "noise 0.5", "noise 1.0"],
figsize=(7.5, 7.5),
)color_edges_by colours each chord by the cluster it leaves ("source") or
arrives at ("target"), which is what makes the middle readable - without it you
get a grey thicket. inner_radius trades room for the trees against room for
the chords, and bow sets how far the chords dip towards the centre.
The layout also works for exactly two trees, and unlike the stacked version it has no preferred pair: any two sectors are equally close.
Past a few hundred leafs, one line per leaf is hopeless whatever the layout.
But usually the question is not "where did this leaf go" - it is "did this
cluster survive", which is a question about groups. cluster_flow answers that
with ribbons whose width is the number of observations moving between clusters:
flow_rng = np.random.default_rng(7)
truth_centers = np.array([[0, 0], [4, 0], [2, 4], [6, 4], [8, 0]], dtype=float)
flow_X = np.repeat(truth_centers, 60, axis=0) + flow_rng.normal(0, 0.8, (300, 2))
truth = np.repeat([f"g{i + 1}" for i in range(5)], 60)
def cluster_at(noise, seed):
jittered = flow_X + np.random.default_rng(seed).normal(0, noise, flow_X.shape)
return sch.fcluster(sch.linkage(jittered, "ward"), 5, criterion="maxclust")
flows, ax = tg.cluster_flow(
[truth, cluster_at(0.8, 1), cluster_at(1.6, 2), cluster_at(2.4, 3)],
names=["true groups", "noise 0.8", "noise 1.6", "noise 2.4"],
share_colors=False,
figsize=(9, 5),
)Five well separated groups, re-clustered at rising noise. The first transition is almost straight across; by the last one the groups have shredded. That is 300 observations - a tanglegram of the same data would be a solid block of lines.
It returns the counts as well as the axis, so the picture and the numbers agree:
[f for f in flows if f["step"] == 0][:3]A few things worth knowing:
- Blocks are ordered to sit near where their members came from, which keeps the
ribbons from crossing more than they have to.
sort=Falsefalls back to order of first appearance. - Ribbons take the colour of the cluster they leave;
color_by="target"flips that. share_colors=Falseis used above becausefclusternumbers each cut on its own, so "cluster 1" at one noise level has nothing to do with "cluster 1" at the next. Leave it on when your labels genuinely mean the same thing in every column, and a cluster keeps one colour throughout.- Observations with a
None/NaN assignment are dropped from that column's blocks and from any ribbon touching them, so a block that loses members to missing data visibly fails to fill.
Both dendrogram and tanglegram take backend="plotly":
fig, dn1, dn2 = tg.tanglegram(dist_a, dist_b, sort=True, backend="plotly")
fig.show()Hovering an edge tells you which pair of labels it connects, which is the easiest way to read a tanglegram whose labels are too small to print.
entanglement and crossings score a drawing - rotate a dendrogram and they
change. To ask how similar the two hierarchies actually are, use:
Z_ward = sch.linkage(X, method="ward")
Z_single = sch.linkage(X, method="single")
tg.cophenetic_correlation(Z_ward, Z_single)
tg.baker_gamma(Z_ward, Z_single)Both compare how far apart each pair of leafs sits in one tree against the other, so rotating a tree leaves them untouched. They return 1 for identical hierarchies and 0 for unrelated ones.
| function | based on | use it when |
|---|---|---|
cophenetic_correlation |
the merge heights themselves | the two linkages are on the same scale |
baker_gamma |
the rank of those heights | the linkages use different methods or scales |
Baker's gamma ignores any monotonic rescaling of the merge heights, which makes
it the fairer of the two when comparing, say, a ward tree against a single
one. cophenetic_distances(link) returns the underlying leaf-by-leaf matrix if
you want to do something else with it.
Labels are optional - without them the observations are matched by index - and
edges lets you spell out the pairing explicitly.
sort=True uses dp2side, but you can name the method explicitly:
fig = tg.tanglegram(mat1, mat2, sort="dp2side")
# Two-sided untangling can settle in a local optimum - `restarts` re-runs it
# from randomly rotated copies and keeps the best result
fig = tg.tanglegram(mat1, mat2, sort="dp2side",
sort_kwargs=dict(restarts=20, seed=0))| method | objective | memory | notes |
|---|---|---|---|
dp2side |
displacement | O(n^2) |
Default. Alternates exact dp1side solves. |
dp1side |
displacement | O(n^2) |
Rotates the first dendrogram only. |
cross2side |
crossings | O(n) |
Alternates exact cross1side solves. Use on large trees. |
cross1side |
crossings | O(n) |
Rotates the first dendrogram only. |
random |
displacement | O(n) |
Legacy. Shuffles R times, keeps the best. |
step1side |
displacement | O(n) |
Legacy greedy hinge-by-hinge sweep. |
step2side |
displacement | O(n) |
Legacy greedy sweep on both trees. |
All four dp*/cross* methods solve their one-sided problem exactly -
they find the provably best of all 2**(n-1) rotations rather than searching
greedily. Two structural facts make this possible: every subtree occupies a
contiguous block of leaf slots, and a rotation only decides the order of a
node's two child blocks.
- Displacement (
entanglement(),sum(abs(pos1 - pos2)**L)) is a sum of independent per-leaf terms, so a dynamic program over(node, start slot)solves it inO(n^2). - Crossings (
crossings()) are what a reader actually sees. The crossings between a node's two child blocks depend only on which child comes first, not on where the block sits - so there is no start-slot dimension at all and the memory drops toO(n). Atn = 8000that is 5 MB versus 710 MB.
The two objectives produce near-identical layouts in practice, so use
cross2side when n is large enough that an n x n table hurts, and
dp2side otherwise. Both beat the legacy greedy methods on speed (25x at
n = 1600, and the gap widens) while never producing a worse result.
Entanglement has no natural scale, so a value of 0.43 could mean either a
failed untangling or two trees that genuinely disagree. alignment_quality
tells you which:
link1, link2 = tg.untangle(link1, link2, labels, labels, edges, restarts=20)
print(tg.alignment_quality(link1, link2, labels, labels, edges))Alignment quality (800 leafs, 800 edges)
entanglement 0.4301 (random layout: 0.5763 +/- 0.0443, z = -3.3)
crossings 128,279
better than random 25%
displacement median 172, max 735 slots; 17% of edges within 40
verdict at the structural floor - the trees themselves disagree
It compares your alignment against a uniformly random layout (how much did
untangling buy?) and against a fresh optimisation (is anything left on the
table?). When the verdict is at the structural floor, no amount of extra
rotation will help - the dendrograms simply have incompatible topologies.
- layout does not scale well, i.e. small dendrograms look weird
This code is under GNU GPL V3