"""Hastie, Tibshirani and Friedman (2009), Chapter 14: Unsupervised Learning (part A, Sections 14.1-14.5.1).

Reproduces the figures of Sections 14.2-14.5.1 of T. Hastie, R. Tibshirani and J. Friedman, The Elements
of Statistical Learning (2nd edition, Springer, 2009), pp. 485-523, written from scratch with numpy, scipy
and matplotlib, to be read next to the lecture notes (../ch14-unsupervised-learning.html). Part B
(ch14_unsupervised_learning_b.py) covers Sections 14.5.2-14.10.

* Association rules, Section 14.2: market_dummies() codes the demographics data of Table 14.1 into 50
  dummy variables; apriori() is the Apriori algorithm (one pass per item-set size, candidates whose
  subsets are all frequent); association_rules() forms the rules A => b with support, confidence and lift
  (14.5)-(14.9). density_by_classification() is Section 14.2.4: data against a uniform reference sample,
  logistic regression (logistic_irls(), Newton's method) on a tensor product of natural splines
  (ns_basis()), and g_hat = g0 mu/(1 - mu) (14.12). market_tree() is Exercises 14.3-14.4 (CART against
  the product-of-marginals reference).
* Clustering, Section 14.3: kmeans() is Lloyd's algorithm (Algorithm 14.1, (14.32)-(14.34)) with random
  starts; within_ss() the criterion; em_spherical() the EM algorithm for spherical Gaussian mixtures
  (Exercise 14.2, soft K-means); vq_compress() block vector quantisation (Section 14.3.9); kmedoids()
  Algorithm 14.2 on a dissimilarity matrix and pam_swap() the exchange search for (14.38);
  gap_statistic() the gap statistic and rule (14.39); agglomerate() agglomerative clustering with
  single, complete and group-average linkage (14.41)-(14.43) by the Lance-Williams updates (it agrees
  with scipy.cluster.hierarchy); cophenetic() and cophenetic_correlation() (14.40);
  tight_first_linkage() the leaf-ordering rule of Figure 14.14.
* Self-organising maps, Section 14.4: som_init() (prototypes on the principal component plane),
  som_online() (the online update (14.46) with a shrinking neighbourhood), som_batch() (the batch
  update (14.48), box or Gaussian neighbourhood), som_error() (reconstruction error).
* Principal components and Procrustes, Section 14.5.1: pca() (the SVD (14.54)), procrustes() ((14.56)-
  (14.58)), procrustes_average() ((14.59), with scaling (14.115)), affine_average() ((14.60), Exercise
  14.10), cmdscale() (classical scaling, Exercise 14.11).
* Data: the demographics (marketing.data), human tumour microarray (nci.data.csv, nci.label.txt),
  zip-code digits and signature data from the book's website; the country dissimilarities of Table 14.3
  typed in from the book (countries()); a photograph shipped with matplotlib (vq_image()); and the
  simulations half_sphere() (Section 14.4 and Exercise 14.5), three_clusters() (Figure 14.4),
  standardisation_data() (Figure 14.5) and u_shaped() (Figure 14.3).

Figures reproduced: 14.2-14.18 and 14.20-14.26 (Figure 14.14 as PNG and PDF only, its SVG is too large).
Also printed: Table 14.2 (fig_14_8). Run `python3 ch14_unsupervised_learning_a.py --list`,
`python3 ch14_unsupervised_learning_a.py` (all, about two minutes the first time, then under a minute)
or `python3 ch14_unsupervised_learning_a.py --fig 14.6`. Files go to ../img/ch14/.

Figures not reproduced: 14.1 (a schematic of rectangles in the plane: nothing is computed) and 14.19
(the WEBSOM map of 12,088 newsgroup articles: the corpus and the fitted map are not available).
Figure 14.9 needs the photograph of R. A. Fisher used in the book, which is not available: the same
2 x 2 block vector quantisation is applied to the public-domain photograph of Grace Hopper that ships
with matplotlib (central 512 x 512 pixels).

Settings chosen where the book gives none:
* Figure 14.2: ordinal inputs cut at the median (x <= median against x > median; for years in the Bay
  Area, whose median is the top category, x < median against x >= median); Apriori with support >= 10%,
  item sets of at most 5 items, rules with one consequent item and confidence >= 80% (6343 rules, the
  book reports 6288); bars are each dummy's share of all item occurrences.
* Figure 14.3: 200 points with X1 ~ N(0.2, 0.8^2), X2 = 1.1 X1^2 - 0.4 + N(0, 0.9^2) (numpy seed 143);
  tensor product of natural cubic splines with 5 knots per input at quantiles of the pooled data, a ridge
  of 10^-3 for stability; contours of mu_hat at 0.2, 0.3, ..., 0.9.
* Figures 14.4, 14.6, 14.11: three Gaussian groups (30 + 30 + 100 points, numpy seed 140); Figure 14.6
  starts K-means from the three centres shown; Figure 14.11 uses B = 20 uniform reference sets and 10
  K-means starts per fit.
* Figure 14.5: two groups at X1 = -3 and 3 (sd 1.2), X2 = +-1 + N(0, 0.35^2) independent of the group.
* Figure 14.8 and Table 14.2: K-means with 300 random starts for each K.
* Figure 14.9: K = 200 (one start) and K = 4 (five starts).
* Figures 14.12-14.14: Euclidean distances between the 64 samples (and between the 6830 genes).
* Figures 14.15-14.18: noise standard deviation 0.1 (Exercise 14.5 prints 0.6; see the notes), a 5 x 5
  SOM grid on the principal component plane spanning +-1.5 sd, R = 2, alpha from 1 to 0, 40 passes in
  random order (numpy seed 1416); K-means with 25 centres and 50 starts.
* Figure 14.20: 20 Gaussian points (numpy seed 1420). Figure 14.22: 130 threes drawn at random (seed 1422).
* Figure 14.25: the second S is rotated by 0.6 radians and translated before matching, for visual effect.
"""
import json
import math
import os

import numpy as np
from scipy import linalg

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig

CH = 14
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)


# =========================================================================== data
def zip_digits():
    """Zip-code digits: (Xtr, gtr, Xte, gte); each row is a 16 x 16 image stored row by row, grey
    levels in [-1, 1] (-1 white, +1 black)."""
    tr = np.loadtxt(common.esl_file("zip.train.gz"))
    te = np.loadtxt(common.esl_file("zip.test.gz"))
    return tr[:, 1:], tr[:, 0].astype(int), te[:, 1:], te[:, 0].astype(int)


_ZIP = {}


def zip_class(digit, train=True):
    """All training (or test) images of one digit, N x 256 in [-1, 1] (658 threes in the training set)."""
    key = (digit, train)
    if key not in _ZIP:
        Xtr, gtr, Xte, gte = zip_digits()
        X, g = (Xtr, gtr) if train else (Xte, gte)
        _ZIP[key] = X[g == digit].copy()
    return _ZIP[key]


def zip_threes():
    return zip_class(3)


def nci():
    """Human tumour microarray data (Chapter 1): X is 64 x 6830 (samples in rows, genes in columns),
    labels the 64 cancer types (stripped strings)."""
    X = np.loadtxt(common.esl_file("nci.data.csv"), delimiter=",", skiprows=1, usecols=range(1, 65)).T
    with open(common.esl_file("nci.label.txt")) as f:
        labels = [s.strip() for s in f.read().split("\n") if s.strip()]
    return X, np.array(labels)


def half_sphere(seed=145, n=30, sd=0.1):
    """The half-sphere data of Section 14.4 and Exercise 14.5: three clusters of n points near the unit
    sphere, around (0, 0, 1) (class 0, the tight 'red' cluster: theta ~ U(-pi/8, pi/8), phi ~ U(0, 2 pi)),
    (1, 0, 0) (class 1: theta ~ U(pi/4, 3 pi/4), phi ~ U(-pi/4, pi/4)) and (0, 1, 0) (class 2:
    theta, phi ~ U(pi/4, 3 pi/4)), plus Gaussian noise of standard deviation sd in each coordinate.
    Exercise 14.5 prints sd = 0.6, but the reconstruction errors of Figure 14.18 need sd close to 0.1
    (see the notes); sd = 0.1 is the default. Returns (X 3n x 3, labels)."""
    r = np.random.default_rng(seed)
    q = np.pi / 4
    ranges = [((-np.pi / 8, np.pi / 8), (0, 2 * np.pi)), ((2 * q - q, 2 * q + q), (-q, q)),
              ((2 * q - q, 2 * q + q), (2 * q - q, 2 * q + q))]
    X, g = [], []
    for k, (tr, pr) in enumerate(ranges):
        th, ph = r.uniform(*tr, n), r.uniform(*pr, n)
        X.append(np.c_[np.sin(th) * np.cos(ph), np.sin(th) * np.sin(ph), np.cos(th)])
        g += [k] * n
    X = np.vstack(X)
    return X + sd * r.standard_normal(X.shape), np.array(g)


HS_COLOURS = (RED, GREEN, BLUE)   # pole cluster red (as in Figure 14.15), the other two green and blue


def three_clusters(seed=140):
    """Simulated data of Figure 14.4: three Gaussian groups in the plane, two of them close together
    (top left and top right) and one large group below. Returns (X 160 x 2, true group)."""
    r = np.random.default_rng(seed)
    a = r.normal([-1.8, 5.0], 0.5, size=(30, 2))
    b = r.normal([1.2, 4.8], 0.5, size=(30, 2))
    c = r.normal([0.0, 0.0], [1.0, 0.75], size=(100, 2))
    return np.vstack([a, b, c]), np.repeat([0, 1, 2], [30, 30, 100])


# =========================================================================== K-means (Algorithm 14.1)
def within_ss(X, labels, centres=None):
    """W(C) of (14.31) halved, i.e. sum_k sum_{C(i)=k} ||x_i - xbar_k||^2 (the K-means criterion)."""
    s = 0.0
    for k in np.unique(labels):
        Xk = X[labels == k]
        m = Xk.mean(0) if centres is None else centres[k]
        s += ((Xk - m) ** 2).sum()
    return float(s)


def kmeans(X, K, n_init=10, seed=0, init=None, max_iter=300, history=False):
    """Lloyd's algorithm (Algorithm 14.1): alternate (14.32) (means of the clusters) and (14.34)
    (nearest mean). Starts: K distinct observations chosen at random (n_init times), or the given
    initial centres. Returns dict(centres, labels, W, n_iter[, path of (centres, labels)]) of the best
    start, where W = sum_k sum_{C(i)=k} ||x_i - m_k||^2."""
    X = np.asarray(X, float)
    rng = np.random.default_rng(seed)
    starts = [np.asarray(init, float)] if init is not None else \
        [X[rng.choice(len(X), K, replace=False)] for _ in range(n_init)]
    best = None
    xx = (X * X).sum(1)
    for m in starts:
        m = m.copy()
        lab = None
        path = []
        for it in range(max_iter):
            d2 = xx[:, None] - 2 * X @ m.T + (m * m).sum(1)[None, :]
            new = d2.argmin(1)
            if history:
                path.append((m.copy(), new.copy()))
            if lab is not None and np.array_equal(new, lab):
                break
            lab = new
            for k in range(K):
                if np.any(lab == k):
                    m[k] = X[lab == k].mean(0)
        W = within_ss(X, lab, m)
        if best is None or W < best["W"] - 1e-9:
            best = dict(centres=m, labels=lab, W=W, n_iter=it + 1)
            if history:
                best["path"] = path
    return best


# =========================================================================== principal components (14.49)-(14.54)
def pca(X):
    """Centred SVD X - xbar = U D V^T (14.54). Returns (xbar, U, d, V) with V p x r (columns v_j)."""
    xbar = X.mean(0)
    U, d, Vt = linalg.svd(X - xbar, full_matrices=False)
    # fix signs: largest |loading| of each v_j positive, so runs are reproducible
    s = np.sign(Vt[np.arange(len(d)), np.abs(Vt).argmax(1)])
    s[s == 0] = 1
    return xbar, U * s, d, (Vt * s[:, None]).T


def cmdscale(D, k=2):
    """Classical scaling of a dissimilarity matrix D: double-centre -D^2/2 and keep the k leading
    eigenvectors scaled by the square roots of their eigenvalues (Exercise 14.11)."""
    D = np.asarray(D, float)
    n = len(D)
    J = np.eye(n) - 1.0 / n
    B = -0.5 * J @ (D ** 2) @ J
    w, V = linalg.eigh(B)
    idx = np.argsort(w)[::-1][:k]
    Z = V[:, idx] * np.sqrt(np.maximum(w[idx], 0))
    s = np.sign(Z[np.abs(Z).argmax(0), np.arange(k)])
    return Z * s, w[np.argsort(w)[::-1]]


# =========================================================================== 14.2 association rules
MARKET_NAMES = ["income", "sex", "marital", "age", "educ", "occup", "yrs-BA", "dual inc", "perhous",
                "peryoung", "house", "typehome", "ethnic", "language"]
MARKET_ORDINAL = (0, 3, 4, 6, 8, 9)   # income, age, education, years in Bay Area, household size, children


def marketing():
    """The demographics data of Table 14.1 (marketing.data): the 6876 complete questionnaires as an
    integer array (14 columns in the order of MARKET_NAMES)."""
    import pandas as pd
    D = pd.read_csv(common.esl_file("marketing.data"), sep=r"\s+", header=None, na_values="NA")
    return D.dropna().astype(int).values


def market_dummies(D=None):
    """Dummy coding of Section 14.2.3: each ordinal input cut at its median into two dummies
    (x <= median and x > median; for 'years in the Bay Area', whose median is the top category, the cut
    is x < median and x >= median), each categorical input with k observed categories into k dummies.
    Returns (Z boolean 6876 x 50, list of (variable index, description))."""
    D = marketing() if D is None else D
    cols, info = [], []
    for j in range(D.shape[1]):
        x = D[:, j]
        if j in MARKET_ORDINAL:
            m = np.median(x)
            lo = x <= m if (x > m).any() else x < m
            op = "<=" if (x > m).any() else "<"
            cols += [lo, ~lo]
            info += [(j, "%s %s %g" % (MARKET_NAMES[j], op, m)), (j, "%s %s %g" % (MARKET_NAMES[j], ">" if op == "<=" else ">=", m))]
        else:
            for v in np.unique(x):
                cols.append(x == v)
                info.append((j, "%s = %d" % (MARKET_NAMES[j], v)))
    return np.array(cols).T, info


def apriori(Z, t=0.10, max_size=5):
    """The Apriori algorithm (Section 14.2.2, Agrawal et al. 1995): all item sets K with support
    T(K) >= t and |K| <= max_size, one pass over the data per size. A candidate of size m is counted
    only if all its m subsets of size m - 1 are frequent (support is anti-monotone). Returns a dict
    {sorted item tuple: support}."""
    Z = np.asarray(Z, bool)
    freq = {}
    single = [(j,) for j in range(Z.shape[1]) if Z[:, j].mean() >= t]
    for s in single:
        freq[s] = float(Z[:, s[0]].mean())
    cur = single
    while cur and len(cur[0]) < max_size:
        cs = set(cur)
        cand = set()
        for a in cur:
            for (b,) in single:
                if b > a[-1]:
                    c = a + (b,)
                    if all(c[:i] + c[i + 1:] in cs for i in range(len(c))):
                        cand.add(c)
        nxt = []
        for c in sorted(cand):
            s = float(Z[:, list(c)].all(1).mean())
            if s >= t:
                freq[c] = s
                nxt.append(c)
        cur = nxt
    return freq


def association_rules(freq, c=0.8):
    """Rules A => B with a single consequent item, formed from the frequent item sets (14.7), with
    confidence C = T(A => B)/T(A) >= c (14.8)-(14.9). Returns a list of (A, b, support, confidence,
    lift)."""
    rules = []
    for S, s in freq.items():
        if len(S) < 2:
            continue
        for i in range(len(S)):
            A = S[:i] + S[i + 1:]
            conf = s / freq[A]
            if conf >= c:
                rules.append((A, S[i], s, conf, conf / freq[(S[i],)]))
    return rules


def market_rules(t=0.10, c=0.8, max_size=5):
    path = os.path.join(CACHE_DIR, "ch14_market_rules.json")
    if os.path.exists(path):
        with open(path) as f:
            d = json.load(f)
        return [(tuple(r[0]), r[1], r[2], r[3], r[4]) for r in d["rules"]], d["nfreq"]
    Z, _ = market_dummies()
    freq = apriori(Z, t, max_size)
    rules = association_rules(freq, c)
    with open(path, "w") as f:
        json.dump({"rules": rules, "nfreq": len(freq)}, f)
    return rules, len(freq)


def fig_14_2(out_dir=None):
    """Relative frequency of each dummy variable in the data and in the association rules."""
    import matplotlib.pyplot as plt
    Z, info = market_dummies()
    rules, nfreq = market_rules()
    cnt = np.zeros(Z.shape[1])
    for A, b, *_ in rules:
        for j in A + (b,):
            cnt[j] += 1
    f_data = Z.mean(0) / Z.mean(0).sum()
    f_rule = cnt / cnt.sum()
    fig, axes = plt.subplots(2, 1, figsize=(7.2, 6.4))
    var = np.array([v for v, _ in info])
    first = [int(np.where(var == j)[0][0]) for j in range(14)]
    for ax, f, lab in [(axes[0], f_data, "Relative frequency in data"), (axes[1], f_rule, "Relative frequency in association rules")]:
        ax.bar(np.arange(1, 51), f, width=0.8, color="#33cc33", edgecolor="#1a801a", lw=0.4)
        ax.set_xlim(0, 51)
        ax.set_ylabel(lab, fontsize=9)
        ax.set_xlabel("Attribute (dummy variable)")
        top = f.max() * 1.18
        ax.set_ylim(0, top * 1.25)
        for j, k in enumerate(first):
            ax.text(k + 0.6, top * 1.02, MARKET_NAMES[j], rotation=90, fontsize=7, va="bottom", ha="center")
            ax.axvline(k + 0.5, color=GREY, lw=0.4, ls=":")
    fig.tight_layout()
    savefig(fig, CH, "fig14-2", out_dir)
    print("  %d frequent item sets, %d rules (support >= 10%%, confidence >= 80%%, at most 5 items)" % (nfreq, len(rules)))


def describe_rule(rule, info):
    A, b, s, c, lift = rule
    return "{%s} => {%s}: support %.1f%%, confidence %.1f%%, lift %.2f" % (
        ", ".join(info[j][1] for j in A), info[b][1], 100 * s, 100 * c, lift)


def book_rule_examples():
    """Our versions of the book's three example rules (Section 14.2.3)."""
    Z, info = market_dummies()
    rules, _ = market_rules()
    name = {d: j for j, (_, d) in enumerate(info)}
    want = [
        ({name["perhous <= 3"], name["peryoung <= 0"]} | set(), name["language = 1"]),
    ]
    out = []
    for A, b, s, c, l in rules:
        for wa, wb in want:
            if set(A) == wa and b == wb:
                out.append(describe_rule((A, b, s, c, l), info))
    # rule 2: consequent income > median, ranked by confidence among rules with support >= 13%
    inc = name["income > 6"]
    r2 = sorted([r for r in rules if r[1] == inc], key=lambda r: -r[3])[:3]
    return out, [describe_rule(r, info) for r in r2]


# =========================================================================== 14.2.4 unsupervised as supervised
def ns_basis(x, knots):
    """Natural cubic spline basis (5.4)-(5.5) with the given knots (first and last are boundary
    knots); returns N x len(knots) including the constant column."""
    K = len(knots)

    def dk(k):
        return (np.maximum(x - knots[k], 0) ** 3 - np.maximum(x - knots[-1], 0) ** 3) / (knots[-1] - knots[k])
    cols = [np.ones_like(x), x] + [dk(k) - dk(K - 2) for k in range(K - 2)]
    return np.column_stack(cols)


def logistic_irls(H, y, ridge=1e-6, maxit=100):
    """Logistic regression by Newton-Raphson (IRLS, Section 4.4.1) with a tiny ridge for stability."""
    b = np.zeros(H.shape[1])
    for _ in range(maxit):
        eta = H @ b
        p = common.sigmoid(eta)
        w = p * (1 - p)
        g = H.T @ (y - p) - ridge * b
        Hs = (H * w[:, None]).T @ H + ridge * np.eye(len(b))
        step = linalg.solve(Hs, g, assume_a="pos")
        b += step
        if np.abs(step).max() < 1e-10:
            break
    return b


def u_shaped(n=200, seed=143):
    r = np.random.default_rng(seed)
    x1 = r.normal(0.2, 0.8, n)
    x2 = 1.1 * x1 ** 2 - 0.4 + r.normal(0, 0.9, n)
    return np.c_[x1, x2]


def density_by_classification(X, seed=1430, df=5):
    """Section 14.2.4: pool the data (y = 1) with a sample of the same size from the uniform density
    g0 on the bounding rectangle (y = 0) and fit a logistic regression on a tensor product of natural
    splines (df per input). Returns a function x -> (mu_hat(x), g_hat(x)) with g_hat = g0 mu/(1 - mu)
    (14.12)."""
    r = np.random.default_rng(seed)
    lo, hi = X.min(0), X.max(0)
    X0 = r.uniform(lo, hi, size=X.shape)
    P = np.vstack([X, X0])
    y = np.r_[np.ones(len(X)), np.zeros(len(X0))]
    knots = [np.quantile(P[:, j], np.linspace(0, 1, df)) for j in range(2)]

    def basis(Q):
        B1, B2 = ns_basis(Q[:, 0], knots[0]), ns_basis(Q[:, 1], knots[1])
        return np.einsum("ij,ik->ijk", B1, B2).reshape(len(Q), -1)
    b = logistic_irls(basis(P), y, ridge=1e-3)
    g0 = 1.0 / np.prod(hi - lo)

    def f(Q):
        mu = common.sigmoid(basis(Q) @ b)
        return mu, g0 * mu / (1 - mu)
    return f, X0, (lo, hi)


def fig_14_3(out_dir=None):
    """Density estimation via classification against a uniform reference sample."""
    import matplotlib.pyplot as plt
    X = u_shaped()
    f, X0, (lo, hi) = density_by_classification(X)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 4.0))
    g1, g2 = np.meshgrid(np.linspace(lo[0], hi[0], 200), np.linspace(lo[1], hi[1], 200))
    mu, _ = f(np.c_[g1.ravel(), g2.ravel()])
    for k, ax in enumerate(axes):
        if k == 1:
            ax.scatter(X0[:, 0], X0[:, 1], s=9, color="#5ab4e6", lw=0)
            ax.contour(g1, g2, mu.reshape(g1.shape), levels=np.arange(0.2, 0.95, 0.1), colors=GREY, linewidths=0.7)
        ax.scatter(X[:, 0], X[:, 1], s=9, color="#f0a030", lw=0)
        ax.set_xlabel("$X_1$")
        ax.set_ylabel("$X_2$")
        ax.set_xlim(lo[0] - 0.1, hi[0] + 0.1)
        ax.set_ylim(lo[1] - 0.3, hi[1] + 0.3)
    fig.tight_layout()
    savefig(fig, CH, "fig14-3", out_dir)


# =========================================================================== 14.3 clustering figures
KM_COLS = ("#f0a030", "#1f5fbf", "#18a878")


def fig_14_4(out_dir=None):
    """Simulated data in the plane, clustered into three groups by K-means."""
    import matplotlib.pyplot as plt
    X, _ = three_clusters()
    km = kmeans(X, 3, n_init=20, seed=4)
    order = np.argsort([-km["centres"][k, 1] * 10 + km["centres"][k, 0] for k in range(3)])
    col = {order[0]: KM_COLS[2], order[1]: KM_COLS[1], order[2]: KM_COLS[0]}
    fig, ax = plt.subplots(figsize=(4.4, 4.4))
    ax.scatter(X[:, 0], X[:, 1], s=10, c=[col[k] for k in km["labels"]], lw=0)
    ax.set_xlabel("$X_1$")
    ax.set_ylabel("$X_2$")
    ax.set_xticks([])
    ax.set_yticks([])
    savefig(fig, CH, "fig14-4", out_dir)


def standardisation_data(seed=145, n=40):
    """Data of Figure 14.5: two groups far apart in X1 (centres -3 and 3, sd 1.2); X2 = +-1 + N(0, 0.35^2)
    independently of the group, so after standardising X1 the split in X2 is the tighter one."""
    r = np.random.default_rng(seed)
    g = np.repeat([0, 1], n)
    x1 = np.where(g == 0, -3.0, 3.0) + r.normal(0, 1.2, 2 * n)
    x2 = r.choice([-1.0, 1.0], 2 * n) + r.normal(0, 0.35, 2 * n)
    return np.c_[x1, x2], g


def fig_14_5(out_dir=None):
    """K-means (K = 2) on raw and on standardised features."""
    import matplotlib.pyplot as plt
    X, _ = standardisation_data()
    Xs = (X - X.mean(0)) / X.std(0)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 4.0))
    for ax, Y in zip(axes, [X, Xs]):
        km = kmeans(Y, 2, n_init=20, seed=5)
        lab = km["labels"] if km["centres"][0].sum() < km["centres"][1].sum() else 1 - km["labels"]
        ax.scatter(Y[:, 0], Y[:, 1], s=12, c=[KM_COLS[0] if l == 0 else KM_COLS[1] for l in lab], lw=0)
        ax.set_aspect("equal", adjustable="datalim")
        ax.set_xlabel("$X_1$")
        ax.set_ylabel("$X_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig14-5", out_dir)


def _voronoi(ax, m, xlim, ylim):
    g1, g2 = np.meshgrid(np.linspace(*xlim, 500), np.linspace(*ylim, 500))
    d = ((np.c_[g1.ravel(), g2.ravel()][:, None, :] - m[None]) ** 2).sum(2).argmin(1).reshape(g1.shape)
    ax.contour(g1, g2, d, levels=np.arange(len(m) - 1) + 0.5, colors="#333333", linewidths=0.8)


def fig_14_6(out_dir=None):
    """Successive iterations of K-means on the data of Figure 14.4."""
    import matplotlib.pyplot as plt
    X, _ = three_clusters()
    init = np.array([[-0.4, 3.9], [0.6, 3.5], [0.3, 1.4]])
    km = kmeans(X, 3, init=init, history=True, max_iter=100)
    path = km["path"]
    xlim, ylim = (X[:, 0].min() - 0.5, X[:, 0].max() + 0.5), (X[:, 1].min() - 0.5, X[:, 1].max() + 0.5)
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 7.2))
    show = [("Initial centroids", init, None), ("Initial partition", init, path[0][1]),
            ("Iteration number 2", path[min(2, len(path) - 1)][0], path[min(2, len(path) - 1)][1]),
            ("Iteration number %d (converged)" % len(path), path[-1][0], path[-1][1])]
    for ax, (title, m, lab) in zip(axes.ravel(), show):
        if lab is None:
            ax.scatter(X[:, 0], X[:, 1], s=8, color=GREY, lw=0)
        else:
            ax.scatter(X[:, 0], X[:, 1], s=8, c=[KM_COLS[k] for k in lab], lw=0)
            _voronoi(ax, m, xlim, ylim)
        ax.scatter(m[:, 0], m[:, 1], s=110, c=list(KM_COLS), edgecolors="k", lw=1.2, zorder=5)
        ax.set_xlim(*xlim)
        ax.set_ylim(*ylim)
        ax.set_title(title)
    fig.tight_layout()
    savefig(fig, CH, "fig14-6", out_dir)
    print("  K-means from the plotted start converged after %d assignment steps" % len(path))


def fig_14_7(out_dir=None):
    """Responsibilities of two Gaussian components for one point, sigma = 1 and 0.2."""
    import matplotlib.pyplot as plt
    from scipy.stats import norm
    x = np.linspace(-3, 3, 600)
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 5.4))
    for row, s in enumerate([1.0, 0.2]):
        g0, g1 = norm.pdf(x, -1, s), norm.pdf(x, 1, s)
        ax = axes[row, 0]
        ax.plot(x, g0, color=BLUE)
        ax.plot(x, g1, color="#f0a030")
        ax.plot([-1], [0], "s", color=BLUE, ms=5)
        ax.plot([1], [0], "s", color="#f0a030", ms=5)
        ax.plot([0.5], [0], "o", color=GREEN, ms=7, zorder=5)
        ax.set_title(r"$\sigma=%.1f$" % s)
        ax.set_yticks([])
        ax = axes[row, 1]
        r1 = g1 / (g0 + g1)
        ax.plot(x, 1 - r1, color=BLUE)
        ax.plot(x, r1, color="#f0a030")
        ax.axvline(0.5, color=GREEN, ls=":", lw=1)
        ax.plot([0.5], [0], "o", color=GREEN, ms=7, zorder=5, clip_on=False)
        ax.set_ylim(0, 1)
        ax.set_ylabel("Responsibilities")
        ax.set_title(r"$\sigma=%.1f$" % s)
        p = norm.pdf(0.5, 1, s) / (norm.pdf(0.5, 1, s) + norm.pdf(0.5, -1, s))
        print("  sigma = %.1f: responsibilities at x = 0.5 are %.3f and %.3f" % (s, 1 - p, p))
    fig.tight_layout()
    savefig(fig, CH, "fig14-7", out_dir)


def nci_kmeans_path(Kmax=10, n_init=300):
    path = os.path.join(CACHE_DIR, "ch14_nci_kmeans.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    X, lab = nci()
    out = {"W": [], "labels3": None}
    for K in range(1, Kmax + 1):
        km = kmeans(X, K, n_init=n_init, seed=100 + K)
        out["W"].append(km["W"])
        if K == 3:
            out["labels3"] = km["labels"].tolist()
    with open(path, "w") as f:
        json.dump(out, f)
    return out


def table_14_2():
    """Cancer types against the three K-means clusters (Table 14.2). Returns (types, counts 3 x T)."""
    X, lab = nci()
    r = nci_kmeans_path()
    l3 = np.array(r["labels3"])
    types = sorted(set(lab))
    T = np.array([[np.sum((l3 == k) & (lab == t)) for t in types] for k in range(3)])
    # order clusters by size of their first type column pattern: largest cluster first is not needed;
    # order by the smallest sample index in each cluster, for reproducibility
    order = np.argsort([np.where(l3 == k)[0].min() for k in range(3)])
    return types, T[order]


def fig_14_8(out_dir=None):
    """Total within-cluster sum of squares for K-means on the microarray samples, K = 1..10."""
    import matplotlib.pyplot as plt
    r = nci_kmeans_path()
    fig, ax = plt.subplots(figsize=(4.6, 4.2))
    ax.plot(range(1, 11), r["W"], "o--", color=RED, ms=5)
    ax.set_xlabel("Number of clusters K")
    ax.set_ylabel("Sum of squares")
    ax.set_xticks(range(2, 11, 2))
    savefig(fig, CH, "fig14-8", out_dir)
    types, T = table_14_2()
    print("  W_K:", " ".join("%.0f" % w for w in r["W"]))
    print("  Table 14.2:", types)
    print(T)


# --------------------------------------------------------------------------- 14.3.9 vector quantisation
def vq_image():
    """A grey-level photograph shipped with matplotlib (Grace Hopper, a public-domain portrait), cropped
    to its central 512 x 512 pixels, values 0..255."""
    import matplotlib.cbook as cbook
    from PIL import Image
    im = np.asarray(Image.open(cbook.get_sample_data("grace_hopper.jpg", asfileobj=False)).convert("L"), float)
    return im[44:556, :512]


def vq_compress(im, K, seed=0, n_init=1, max_iter=200):
    """2 x 2 block vector quantisation by K-means (Lloyd's algorithm) in R^4. Returns the decoded image,
    the rate log2(K)/4 bits per pixel, the entropy rate -sum p log2 p / 4, and the distortion (mean
    squared error per pixel)."""
    n = im.shape[0] // 2
    B = im.reshape(n, 2, n, 2).transpose(0, 2, 1, 3).reshape(-1, 4)
    km = kmeans(B, K, n_init=n_init, seed=seed, max_iter=max_iter)
    dec = km["centres"][km["labels"]].reshape(n, n, 2, 2).transpose(0, 2, 1, 3).reshape(im.shape)
    p = np.bincount(km["labels"], minlength=K) / len(B)
    p = p[p > 0]
    return dec, math.log2(K) / 4, float(-(p * np.log2(p)).sum() / 4), float(((dec - im) ** 2).mean())


def vq_results():
    path = os.path.join(CACHE_DIR, "ch14_vq.npz")
    if os.path.exists(path):
        z = np.load(path)
        return z["im"], z["d200"], z["d4"], z["stats"]
    im = vq_image()
    d200, r200, e200, D200 = vq_compress(im, 200, seed=9)
    d4, r4, e4, D4 = vq_compress(im, 4, seed=9, n_init=5)
    stats = np.array([[r200, e200, D200], [r4, e4, D4]])
    np.savez_compressed(path, im=im, d200=d200, d4=d4, stats=stats)
    return im, d200, d4, stats


def fig_14_9(out_dir=None):
    """Block vector quantisation of a photograph with 200 and 4 code vectors."""
    import matplotlib.pyplot as plt
    im, d200, d4, st = vq_results()
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.4))
    for ax, a, t in zip(axes, [im, d200, d4], ["Original, 8 bits per pixel",
                                               "K = 200: %.2f bits per pixel" % st[0, 0],
                                               "K = 4: %.2f bits per pixel" % st[1, 0]]):
        ax.imshow(a, cmap="gray", vmin=0, vmax=255, interpolation="nearest")
        ax.set_title(t, fontsize=9)
        ax.axis("off")
    fig.tight_layout()
    savefig(fig, CH, "fig14-9", out_dir)
    print("  VQ: rate, entropy rate, distortion: K=200 %.3f %.3f %.2f; K=4 %.3f %.3f %.2f" % tuple(st.ravel()))


# --------------------------------------------------------------------------- 14.3.10 K-medoids
COUNTRIES = ["BEL", "BRA", "CHI", "CUB", "EGY", "FRA", "IND", "ISR", "USA", "USS", "YUG", "ZAI"]
_COUNTRY_LOWER = [
    [5.58], [7.00, 6.50], [7.08, 7.00, 3.83], [4.83, 5.08, 8.17, 5.83], [2.17, 5.75, 6.67, 6.92, 4.92],
    [6.42, 5.00, 5.58, 6.00, 4.67, 6.42], [3.42, 5.50, 6.42, 6.42, 5.00, 3.92, 6.17],
    [2.50, 4.92, 6.25, 7.33, 4.50, 2.25, 6.33, 2.75], [6.08, 6.67, 4.25, 2.67, 6.00, 6.17, 6.17, 6.92, 6.17],
    [5.25, 6.83, 4.50, 3.75, 5.75, 5.42, 6.08, 5.83, 6.67, 3.67],
    [4.75, 3.00, 6.08, 6.67, 5.00, 5.58, 4.83, 6.17, 5.67, 6.50, 6.92]]


def countries():
    """The 12 x 12 matrix of average dissimilarities of Table 14.3 (Kaufman and Rousseeuw 1990)."""
    D = np.zeros((12, 12))
    for i, row in enumerate(_COUNTRY_LOWER, start=1):
        D[i, :i] = row
    return D + D.T


def kmedoids(D, K, init, max_iter=100):
    """Algorithm 14.2 on a dissimilarity matrix: alternate (14.35) (in each cluster, the member with
    the smallest total dissimilarity to the others) and (14.37) (assign each object to its nearest
    medoid). Returns (medoid indices, labels, criterion (14.38))."""
    med = np.array(init)
    lab = None
    for _ in range(max_iter):
        new = D[:, med].argmin(1)
        if lab is not None and np.array_equal(new, lab):
            break
        lab = new
        med = np.array([np.where(lab == k)[0][D[np.ix_(lab == k, lab == k)].sum(1).argmin()] for k in range(K)])
    lab = D[:, med].argmin(1)
    return med, lab, float(D[np.arange(len(D)), med[lab]].sum())


def pam_swap(D, med):
    """Kaufman and Rousseeuw's exchange strategy for (14.38): try every swap of a medoid with a
    non-medoid and make the best improving one, until none improves."""
    med = list(med)
    cost = D[:, med].min(1).sum()
    while True:
        best = (cost, None)
        for a in range(len(med)):
            for h in range(len(D)):
                if h in med:
                    continue
                trial = med[:a] + [h] + med[a + 1:]
                c = D[:, trial].min(1).sum()
                if c < best[0] - 1e-12:
                    best = (c, trial)
        if best[1] is None:
            return np.array(med), D[:, med].argmin(1), float(cost)
        cost, med = best


def country_medoids():
    """3-medoid clustering of the country data: best of Algorithm 14.2 from every one of the 220 starts,
    then the swap search; also the global minimum by enumeration."""
    import itertools
    D = countries()
    best = None
    for init in itertools.combinations(range(12), 3):
        r = kmedoids(D, 3, init)
        if best is None or r[2] < best[2] - 1e-12:
            best = r
    swap = pam_swap(D, best[0])
    glob = min((D[:, list(c)].min(1).sum(), c) for c in itertools.combinations(range(12), 3))
    return best, swap, glob


def fig_14_10(out_dir=None):
    """Country dissimilarities: matrix reordered by 3-medoid clusters, and a classical MDS map."""
    import matplotlib.pyplot as plt
    D = countries()
    (med, lab, crit), swap, glob = country_medoids()
    # order clusters as in the book's figure (first the cluster of USA/BEL/FRA...), members by distance to medoid
    order = []
    for k in np.argsort([-D[med[k]].sum() for k in range(3)])[::-1]:
        mem = np.where(lab == k)[0]
        order += list(mem[np.argsort(D[med[k], mem])])
    Z, _ = cmdscale(D, 2)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 4.2))
    ax = axes[0]
    M = D[np.ix_(order, order)].copy()
    M[np.triu_indices(12)] = np.nan
    from matplotlib.colors import LinearSegmentedColormap
    cmap = LinearSegmentedColormap.from_list("reds", ["#3a0000", "#a00000", "#ff3030", "#ffd0d0"])
    ax.imshow(M, cmap=cmap, vmin=2, vmax=8.2)
    ax.set_xticks(range(12))
    ax.set_xticklabels([COUNTRIES[i] for i in order], rotation=90, fontsize=7)
    ax.set_yticks(range(12))
    ax.set_yticklabels([COUNTRIES[i] for i in order], fontsize=7)
    ax.set_xlabel("Reordered dissimilarity matrix")
    for s in ax.spines.values():
        s.set_visible(False)
    ax = axes[1]
    cols = [GREEN, BLUE, RED]
    for i in range(12):
        ax.text(Z[i, 0], Z[i, 1], COUNTRIES[i], color=cols[lab[i]], ha="center", va="center", fontsize=8)
    ax.set_xlim(Z[:, 0].min() - 0.7, Z[:, 0].max() + 0.7)
    ax.set_ylim(Z[:, 1].min() - 0.7, Z[:, 1].max() + 0.7)
    ax.set_xlabel("First MDS coordinate")
    ax.set_ylabel("Second MDS coordinate")
    fig.tight_layout()
    savefig(fig, CH, "fig14-10", out_dir)
    print("  medoids:", [COUNTRIES[i] for i in med], "criterion %.2f; swap %.2f; global %.2f %s" % (
        crit, swap[2], glob[0], [COUNTRIES[i] for i in glob[1]]))
    for k in range(3):
        print("   cluster", k, [COUNTRIES[i] for i in np.where(lab == k)[0]])


# --------------------------------------------------------------------------- 14.3.11 gap statistic
def log_wk(X, Ks, n_init=10, seed=0):
    return np.array([math.log(kmeans(X, K, n_init=n_init, seed=seed + K)["W"]) for K in Ks])


def gap_statistic(X, Kmax=8, B=20, seed=1411, n_init=10):
    """Tibshirani, Walther and Hastie (2001): log W_K for the data and for B uniform samples on the
    bounding rectangle; Gap(K) = mean of the reference log W_K minus the observed one; s'_K = sd_K
    sqrt(1 + 1/B); K* = smallest K with Gap(K) >= Gap(K+1) - s'_{K+1} (14.39)."""
    r = np.random.default_rng(seed)
    Ks = np.arange(1, Kmax + 1)
    obs = log_wk(X, Ks, n_init, seed)
    lo, hi = X.min(0), X.max(0)
    ref = np.array([log_wk(r.uniform(lo, hi, X.shape), Ks, n_init, seed + 100 * (b + 1)) for b in range(B)])
    gap = ref.mean(0) - obs
    s = ref.std(0) * math.sqrt(1 + 1 / B)
    kstar = next(int(K) for i, K in enumerate(Ks[:-1]) if gap[i] >= gap[i + 1] - s[i + 1])
    return dict(K=Ks, obs=obs, ref=ref.mean(0), gap=gap, s=s, kstar=kstar)


def fig_14_11(out_dir=None):
    """Gap statistic for the data of Figure 14.4."""
    import matplotlib.pyplot as plt
    X, _ = three_clusters()
    g = gap_statistic(X)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.9))
    ax = axes[0]
    ax.plot(g["K"], g["obs"] - g["obs"][0], "o-", color=GREEN, ms=4, label="observed")
    ax.plot(g["K"], g["ref"] - g["ref"][0], "o-", color=BLUE, ms=4, label="expected (uniform)")
    ax.set_xlabel("Number of clusters")
    ax.set_ylabel(r"$\log W_K$ (minus its value at $K=1$)")
    ax.legend(frameon=False)
    ax = axes[1]
    ax.errorbar(g["K"], g["gap"], yerr=g["s"], fmt="o-", color=RED, ms=4, capsize=3)
    ax.axvline(g["kstar"], color=GREY, ls=":")
    ax.set_xlabel("Number of clusters")
    ax.set_ylabel("Gap")
    fig.tight_layout()
    savefig(fig, CH, "fig14-11", out_dir)
    print("  gap:", np.round(g["gap"], 3), "K* =", g["kstar"])
    return g


# =========================================================================== 14.3.12 hierarchical clustering
def agglomerate(D, linkage="average"):
    """Agglomerative clustering from a dissimilarity matrix, written out: at each of the N - 1 steps merge
    the two closest groups under (14.41) single, (14.42) complete or (14.43) group-average linkage, and
    update the group dissimilarities by the Lance-Williams formulas (min, max, size-weighted mean).
    Returns a scipy-style linkage matrix (rows: cluster a, cluster b, height, size)."""
    D = np.array(D, float)
    n = len(D)
    active = list(range(n))
    ids = list(range(n))
    size = [1] * n
    M = D.copy()
    np.fill_diagonal(M, np.inf)
    Z = []
    for step in range(n - 1):
        sub = M[np.ix_(active, active)]
        a, b = np.unravel_index(np.argmin(sub), sub.shape)
        i, j = active[a], active[b]
        h = M[i, j]
        Z.append([min(ids[i], ids[j]), max(ids[i], ids[j]), h, size[i] + size[j]])
        for k in active:
            if k in (i, j):
                continue
            if linkage == "single":
                v = min(M[i, k], M[j, k])
            elif linkage == "complete":
                v = max(M[i, k], M[j, k])
            else:
                v = (size[i] * M[i, k] + size[j] * M[j, k]) / (size[i] + size[j])
            M[i, k] = M[k, i] = v
        size[i] += size[j]
        ids[i] = n + step
        active.remove(j)
        M[j, :] = M[:, j] = np.inf
    return np.array(Z)


def tight_first_linkage(Z):
    """Reorder the two children of every merge so that the subtree with the smaller merge height (the
    tighter cluster) comes first; two single leaves keep index order. Plotting the result with its
    children left to right gives the leaf order used for Figure 14.14."""
    Z = np.array(Z, float)
    n = len(Z) + 1
    minleaf = list(range(n)) + [0] * (n - 1)
    for s_, (a, b, h, _) in enumerate(Z):
        a, b = int(a), int(b)
        ha = 0.0 if a < n else Z[a - n, 2]
        hb = 0.0 if b < n else Z[b - n, 2]
        if hb < ha or (ha == hb and minleaf[b] < minleaf[a]):
            Z[s_, 0], Z[s_, 1] = b, a
        minleaf[n + s_] = min(minleaf[a], minleaf[b])
    return Z


def tight_first_order(Z):
    """Leaf order (left to right) of tight_first_linkage(Z)."""
    from scipy.cluster.hierarchy import leaves_list
    Zt = tight_first_linkage(Z)
    n = len(Zt) + 1
    order, stack = [], [2 * n - 2]
    while stack:
        c = stack.pop()
        if c < n:
            order.append(c)
        else:
            a, b = Zt[c - n, :2]
            stack += [int(b), int(a)]
    return order


def nci_dist():
    from scipy.spatial.distance import pdist, squareform
    X, lab = nci()
    return squareform(pdist(X)), lab


def cophenetic(Z):
    """Cophenetic dissimilarities C_ii' (height at which i and i' first join) from a linkage matrix."""
    n = len(Z) + 1
    members = {i: [i] for i in range(n)}
    C = np.zeros((n, n))
    for s, (a, b, h, _) in enumerate(Z):
        A, B = members.pop(int(a)), members.pop(int(b))
        C[np.ix_(A, B)] = h
        C[np.ix_(B, A)] = h
        members[n + s] = A + B
    return C


def cophenetic_correlation(D, Z):
    C = cophenetic(Z)
    iu = np.triu_indices(len(D), 1)
    return float(np.corrcoef(D[iu], C[iu])[0, 1])


TYPE_COLOURS = {"BREAST": "#d62728", "CNS": "#8c564b", "COLON": "#ff7f0e", "LEUKEMIA": "#2ca02c",
                "MELANOMA": "#1f5fbf", "NSCLC": "#7b4fbf", "OVARIAN": "#e377c2", "PROSTATE": "#17becf",
                "RENAL": "#555555", "UNKNOWN": "#000000"}


def _dendro(ax, Z, labels, colour="#4aa0d0", fontsize=5.5, leaf_labels=True):
    from scipy.cluster.hierarchy import dendrogram
    dendrogram(Z, ax=ax, labels=labels if leaf_labels else None, color_threshold=0, above_threshold_color=colour,
               leaf_font_size=fontsize, no_labels=not leaf_labels)
    for s in ("top", "right", "bottom"):
        ax.spines[s].set_visible(False)


def fig_14_12(out_dir=None):
    """Average-linkage dendrogram of the 64 microarray samples."""
    import matplotlib.pyplot as plt
    D, lab = nci_dist()
    Z = agglomerate(D, "average")
    fig, ax = plt.subplots(figsize=(9.0, 4.6))
    _dendro(ax, Z, [l.replace("-repro", "") for l in lab], colour="#3a9d3a")
    for t in ax.get_xticklabels():
        t.set_color(TYPE_COLOURS.get(t.get_text().rstrip("ABD") if t.get_text().startswith(("K562", "MCF7")) else t.get_text(), "#000000"))
    ax.set_ylabel("Dissimilarity (Euclidean distance)")
    fig.tight_layout()
    savefig(fig, CH, "fig14-12", out_dir)


def fig_14_13(out_dir=None):
    """Average, complete and single linkage dendrograms of the microarray samples."""
    import matplotlib.pyplot as plt
    from scipy.cluster import hierarchy
    from scipy.spatial.distance import squareform
    D, lab = nci_dist()
    fig, axes = plt.subplots(1, 3, figsize=(10.0, 3.8))
    cols = {"average": "#d9a441", "complete": "#4aa0d0", "single": "#3fb39b"}
    for ax, link in zip(axes, ["average", "complete", "single"]):
        Z = agglomerate(D, link)
        Zs = hierarchy.linkage(squareform(D, checks=False), link)
        assert np.allclose(np.sort(Z[:, 2]), np.sort(Zs[:, 2]))
        _dendro(ax, Z, None, colour=cols[link], leaf_labels=False)
        ax.set_title("%s linkage" % link.capitalize())
        print("  %s linkage: cophenetic correlation %.3f, top merge height %.1f" % (link, cophenetic_correlation(D, Z), Z[-1, 2]))
    fig.tight_layout()
    savefig(fig, CH, "fig14-13", out_dir)


def nci_gene_order():
    """Row (gene) order for Figure 14.14: average linkage on the 6830 genes (Euclidean distance between
    their 64-sample profiles), leaves ordered tighter-subtree-first. Cached."""
    path = os.path.join(CACHE_DIR, "ch14_nci_gene_order.npz")
    if os.path.exists(path):
        z = np.load(path)
        return z["order"], z["Z"]
    from scipy.cluster import hierarchy
    X, _ = nci()
    Z = hierarchy.linkage(X.T, "average", metric="euclidean")
    Z = tight_first_linkage(Z)
    order = np.array(tight_first_order(Z))
    np.savez_compressed(path, order=order, Z=Z)
    return order, Z


def fig_14_14(out_dir=None):
    """Two-way rearranged heat map of the microarray data (genes and samples ordered by average linkage)."""
    import matplotlib.pyplot as plt
    from matplotlib.colors import LinearSegmentedColormap
    X, lab = nci()
    D, _ = nci_dist()
    Zc = agglomerate(D, "average")
    corder = tight_first_order(Zc)
    rorder, Zr = nci_gene_order()
    M = X[corder][:, rorder].T                      # genes in rows
    cmap = LinearSegmentedColormap.from_list("gr", ["#00ff00", "#003300", "#000000", "#330000", "#ff0000"])
    fig = plt.figure(figsize=(6.4, 8.6))
    axt = fig.add_axes([0.30, 0.86, 0.66, 0.12])
    axl = fig.add_axes([0.02, 0.05, 0.27, 0.80])
    axh = fig.add_axes([0.30, 0.05, 0.66, 0.80])
    from scipy.cluster.hierarchy import dendrogram
    dendrogram(tight_first_linkage(Zc), ax=axt, color_threshold=0, above_threshold_color=GREY, no_labels=True,
               count_sort=False, distance_sort=False)
    axt.axis("off")
    dn = dendrogram(Zr, ax=axl, orientation="left", color_threshold=0, above_threshold_color=GREY, no_labels=True,
                    count_sort=False, distance_sort=False)
    assert list(dn["leaves"]) == list(rorder)
    axl.invert_yaxis()
    axl.axis("off")
    v = float(np.quantile(np.abs(M), 0.97))
    axh.imshow(np.clip(M, -v, v), aspect="auto", cmap=cmap, vmin=-v, vmax=v, interpolation="nearest")
    axh.set_xticks(range(64))
    axh.set_xticklabels([lab[i].replace("-repro", "") for i in corder], rotation=90, fontsize=4.5)
    axh.set_yticks([])
    axh.set_ylabel("6830 genes")
    savefig(fig, CH, "fig14-14", out_dir, formats=("png", "pdf"))


# =========================================================================== 14.4 self-organising maps
def som_init(X, q1=5, q2=5):
    """Prototypes on a q1 x q2 grid in the plane of the first two principal components, spanning
    +-1.5 standard deviations of the first two principal component scores (the 'buttons sewn on the
    principal component plane')."""
    xbar, U, d, V = pca(X)
    sd = d[:2] / math.sqrt(len(X))
    a = np.linspace(-1.5, 1.5, q1) * sd[0]
    b = np.linspace(-1.5, 1.5, q2) * sd[1]
    grid = np.array([(i, j) for j in range(1, q2 + 1) for i in range(1, q1 + 1)], float)
    M = np.array([xbar + a[int(i) - 1] * V[:, 0] + b[int(j) - 1] * V[:, 1] for i, j in grid])
    return M, grid


def som_online(X, q1=5, q2=5, passes=40, R=2.0, alpha0=1.0, seed=0, record_every=None, M0=None):
    """The online SOM of Section 14.4 with the rectangular neighbourhood (14.46): for observation x_i
    (taken in a random order each pass) find the closest prototype m_j and move every m_k with
    ||l_j - l_k|| <= r towards x_i by alpha (x_i - m_k); alpha decreases linearly from alpha0 to 0 and r
    from R to 1 over all passes x N updates. Returns (M, grid, error trace [(iteration, reconstruction
    error)])."""
    rng = np.random.default_rng(seed)
    M, grid = som_init(X, q1, q2)
    if M0 is not None:
        M = M0.copy()
    N = len(X)
    T = passes * N
    trace = []
    t = 0
    for p in range(passes):
        for i in rng.permutation(N):
            frac = t / T
            alpha = alpha0 * (1 - frac)
            r = R + (1 - R) * frac
            x = X[i]
            j = ((M - x) ** 2).sum(1).argmin()
            nb = np.sqrt(((grid - grid[j]) ** 2).sum(1)) <= r + 1e-12
            M[nb] += alpha * (x - M[nb])
            t += 1
            if record_every and t % record_every == 0:
                trace.append((t, som_error(X, M)))
    return M, grid, trace


def som_error(X, M):
    """Reconstruction error: total squared distance of each point to its closest prototype."""
    d2 = ((X[:, None, :] - M[None]) ** 2).sum(2)
    return float(d2.min(1).sum())


def som_batch(X, M, grid, r, iters=50, kernel="box"):
    """Batch SOM (14.48): m_j = sum_k w_k x_k / sum_k w_k over all points x_k, where w_k = h(||l_c(k) - l_j||)
    depends on the grid distance between j and the winning prototype c(k) of x_k; h is the box 1{d <= r}
    or the Gaussian exp(-d^2/(2 r^2)). With the box and r < 1, or the Gaussian and r -> 0, it is K-means."""
    G = np.sqrt(((grid[:, None, :] - grid[None]) ** 2).sum(2))
    Hm = (G <= r + 1e-12).astype(float) if kernel == "box" else np.exp(-G ** 2 / (2 * r * r))
    for _ in range(iters):
        win = ((X[:, None, :] - M[None]) ** 2).sum(2).argmin(1)
        Wt = Hm[:, win]                                   # K x N weights
        tot = Wt.sum(1)
        new = np.where(tot[:, None] > 0, (Wt @ X) / np.maximum(tot, 1e-300)[:, None], M)
        if np.allclose(new, M):
            break
        M = new
    return M


def _sphere_mesh(ax):
    u, v = np.meshgrid(np.linspace(0, 2 * np.pi, 41), np.linspace(0, np.pi / 2, 13))
    ax.plot_wireframe(np.sin(v) * np.cos(u), np.sin(v) * np.sin(u), np.cos(v), color="#c8c830", lw=0.4, alpha=0.7)


def fig_14_15(out_dir=None):
    """The half-sphere data: three clusters near the surface of the unit sphere."""
    import matplotlib.pyplot as plt
    X, g = half_sphere()
    fig = plt.figure(figsize=(5.4, 4.8))
    ax = fig.add_subplot(111, projection="3d")
    _sphere_mesh(ax)
    ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=[HS_COLOURS[k] for k in g], s=12, depthshade=False)
    ax.view_init(22, 35)
    ax.set_box_aspect((1, 1, 0.7))
    savefig(fig, CH, "fig14-15", out_dir)


def _som_panel(ax, X, g, M, grid, seed=0):
    rng = np.random.default_rng(seed)
    win = ((X[:, None, :] - M[None]) ** 2).sum(2).argmin(1)
    for j, (a, b) in enumerate(grid):
        ax.add_patch(plt_circle((a, b), 0.42))
    for i in range(len(X)):
        a, b = grid[win[i]]
        rad, th = 0.33 * math.sqrt(rng.uniform()), rng.uniform(0, 2 * math.pi)
        ax.plot(a + rad * math.cos(th), b + rad * math.sin(th), "o", ms=3, color=HS_COLOURS[g[i]])
    ax.set_xlim(0.4, grid[:, 0].max() + 0.6)
    ax.set_ylim(0.4, grid[:, 1].max() + 0.6)
    ax.set_aspect("equal")
    ax.set_xticks(range(1, int(grid[:, 0].max()) + 1))
    ax.set_yticks(range(1, int(grid[:, 1].max()) + 1))


def plt_circle(c, r):
    from matplotlib.patches import Circle
    return Circle(c, r, fill=False, ec="#444444", lw=0.8)


def som_fit_half_sphere():
    X, g = half_sphere()
    M0, grid = som_init(X)
    M, grid, trace = som_online(X, seed=1416, record_every=90)
    km = kmeans(X, 25, n_init=50, seed=25)
    return X, g, M0, M, grid, trace, km["W"]


def fig_14_16(out_dir=None):
    """SOM on the half-sphere data: initial and final 5 x 5 maps."""
    import matplotlib.pyplot as plt
    X, g, M0, M, grid, trace, Wk = som_fit_half_sphere()
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.8))
    _som_panel(axes[0], X, g, M0, grid)
    _som_panel(axes[1], X, g, M, grid)
    axes[0].set_title("Initial configuration")
    axes[1].set_title("After 40 passes (3600 updates)")
    fig.tight_layout()
    savefig(fig, CH, "fig14-16", out_dir)


def fig_14_17(out_dir=None):
    """Wire-mesh view of the fitted SOM in R^3."""
    import matplotlib.pyplot as plt
    X, g, M0, M, grid, trace, Wk = som_fit_half_sphere()
    fig = plt.figure(figsize=(5.4, 4.8))
    ax = fig.add_subplot(111, projection="3d")
    G = M.reshape(5, 5, 3)
    for i in range(5):
        ax.plot(G[i, :, 0], G[i, :, 1], G[i, :, 2], color="#3b3b8f", lw=1)
        ax.plot(G[:, i, 0], G[:, i, 1], G[:, i, 2], color="#3b3b8f", lw=1)
    ax.scatter(M[:, 0], M[:, 1], M[:, 2], color=PURPLE, s=14, depthshade=False)
    ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=[HS_COLOURS[k] for k in g], s=8, depthshade=False)
    ax.view_init(22, 35)
    ax.set_box_aspect((1, 1, 0.7))
    savefig(fig, CH, "fig14-17", out_dir)


def fig_14_18(out_dir=None):
    """SOM reconstruction error along the iterations; K-means with 25 centres for comparison."""
    import matplotlib.pyplot as plt
    X, g, M0, M, grid, trace, Wk = som_fit_half_sphere()
    t, e = np.array(trace).T
    fig, ax = plt.subplots(figsize=(4.8, 4.0))
    ax.plot(np.r_[0, t], np.r_[som_error(X, M0), e], "o-", color=RED, ms=3, lw=0.8)
    ax.axhline(Wk, color=GREEN)
    ax.set_xlabel("Iteration")
    ax.set_ylabel("Reconstruction error")
    ax.set_ylim(0, None)
    savefig(fig, CH, "fig14-18", out_dir)
    print("  SOM error: start %.2f, end %.2f; K-means (25 centres) %.2f" % (som_error(X, M0), e[-1], Wk))


# =========================================================================== 14.5.1 principal components
def fig_14_20(out_dir=None):
    """The first principal component line of 2-D data, with the orthogonal projections."""
    import matplotlib.pyplot as plt
    r = np.random.default_rng(1420)
    X = r.multivariate_normal([0, 0], [[1.0, 0.75], [0.75, 0.9]], 20)
    xbar, U, d, V = pca(X)
    lam = U[:, 0] * d[0]
    P = xbar + np.outer(lam, V[:, 0])
    fig, ax = plt.subplots(figsize=(4.6, 4.4))
    t = np.array([lam.min() - 0.6, lam.max() + 0.6])
    ax.plot(xbar[0] + t * V[0, 0], xbar[1] + t * V[1, 0], color="k", lw=1)
    for x, p in zip(X, P):
        ax.plot([x[0], p[0]], [x[1], p[1]], color="#17becf", lw=1)
    ax.scatter(X[:, 0], X[:, 1], s=14, color=RED, zorder=4)
    ax.scatter(P[:, 0], P[:, 1], s=8, color="#17becf", zorder=4)
    i = int(np.argsort(lam)[-4])
    ax.annotate(r"$x_i$", X[i], xytext=(8, -4), textcoords="offset points")
    ax.annotate(r"$u_{i1}d_1v_1$", P[i], xytext=(-62, 14), textcoords="offset points",
                arrowprops=dict(arrowstyle="-", color=GREY, lw=0.6))
    ax.annotate(r"$v_1$", xbar + t[1] * V[:, 0], xytext=(4, 4), textcoords="offset points")
    ax.set_aspect("equal")
    ax.set_xlabel("$X_1$")
    ax.set_ylabel("$X_2$")
    savefig(fig, CH, "fig14-20", out_dir)


def fig_14_21(out_dir=None):
    """The best rank-two linear approximation to the half-sphere data, and the projected points."""
    import matplotlib.pyplot as plt
    X, g = half_sphere()
    xbar, U, d, V = pca(X)
    Z = U[:, :2] * d[:2]
    fig = plt.figure(figsize=(9.0, 4.2))
    ax = fig.add_subplot(121, projection="3d")
    a = np.linspace(Z[:, 0].min(), Z[:, 0].max(), 12)
    b = np.linspace(Z[:, 1].min(), Z[:, 1].max(), 12)
    A_, B_ = np.meshgrid(a, b)
    S = xbar[:, None, None] + V[:, 0, None, None] * A_ + V[:, 1, None, None] * B_
    ax.plot_wireframe(S[0], S[1], S[2], color="#a0c040", lw=0.5)
    Pr = xbar + Z @ V[:, :2].T
    for x, p in zip(X, Pr):
        ax.plot([x[0], p[0]], [x[1], p[1]], [x[2], p[2]], color="#6060c0", lw=0.6)
    ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=[HS_COLOURS[k] for k in g], s=10, depthshade=False)
    nrm = V[:, 2] * np.sign(V[2, 2])                       # look at the plane from near its normal
    ax.view_init(math.degrees(math.asin(nrm[2])) - 25, math.degrees(math.atan2(nrm[1], nrm[0])) + 20)
    ax2 = fig.add_subplot(122)
    ax2.scatter(Z[:, 0], Z[:, 1], c=[HS_COLOURS[k] for k in g], s=12)
    ax2.set_xlabel("First principal component")
    ax2.set_ylabel("Second principal component")
    fig.tight_layout()
    savefig(fig, CH, "fig14-21", out_dir)


def _digit(ax, x, cmap="gray_r", vmin=-1, vmax=1):
    ax.imshow(np.asarray(x).reshape(16, 16), cmap=cmap, vmin=vmin, vmax=vmax, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])


def montage(imgs, nrow, ncol, pad=1, fill=-1.0):
    """Tile 16 x 16 images into one array."""
    H = np.full((nrow * (16 + pad) + pad, ncol * (16 + pad) + pad), fill)
    for k, x in enumerate(imgs[:nrow * ncol]):
        i, j = divmod(k, ncol)
        H[pad + i * (16 + pad): pad + i * (16 + pad) + 16, pad + j * (16 + pad): pad + j * (16 + pad) + 16] = np.asarray(x).reshape(16, 16)
    return H


def fig_14_22(out_dir=None):
    """A sample of 130 handwritten threes."""
    import matplotlib.pyplot as plt
    X = zip_threes()
    idx = np.random.default_rng(1422).choice(len(X), 130, replace=False)
    fig, ax = plt.subplots(figsize=(6.4, 8.4))
    ax.imshow(montage(X[idx], 13, 10, fill=-0.2), cmap="gray_r", vmin=-1, vmax=1, interpolation="nearest")
    ax.axis("off")
    savefig(fig, CH, "fig14-22", out_dir)


def threes_grid_points():
    """For Figure 14.23: the 5 x 5 grid of marginal quantiles (5, 25, 50, 75, 95%) of the first two
    principal component scores of the threes, and for each vertex the image whose projected point is
    closest (distance in the PC plane plus a small weight 0.1^2 on the orthogonal residual)."""
    X = zip_threes()
    xbar, U, d, V = pca(X)
    Z = U[:, :2] * d[:2]
    res = ((X - xbar) ** 2).sum(1) - (Z ** 2).sum(1)
    qs = [np.quantile(Z[:, k], [0.05, 0.25, 0.5, 0.75, 0.95]) for k in range(2)]
    pick = []
    for b in qs[1][::-1]:
        for a in qs[0]:
            dist = (Z[:, 0] - a) ** 2 + (Z[:, 1] - b) ** 2 + 0.01 * res
            pick.append(int(dist.argmin()))
    return X, Z, qs, pick, (xbar, U, d, V)


def fig_14_23(out_dir=None):
    """First two principal components of the threes; images nearest the vertices of a quantile grid."""
    import matplotlib.pyplot as plt
    X, Z, qs, pick, (xbar, U, d, V) = threes_grid_points()
    fig = plt.figure(figsize=(9.6, 4.6))
    ax = fig.add_axes([0.07, 0.11, 0.48, 0.85])
    ax.scatter(Z[:, 0], Z[:, 1], s=3, color="#3aa864")
    for a in qs[0]:
        ax.axvline(a, color=GREY, lw=0.6)
    for b in qs[1]:
        ax.axhline(b, color=GREY, lw=0.6)
    ax.scatter(Z[pick, 0], Z[pick, 1], s=60, facecolors="none", edgecolors=RED, lw=1.2)
    ax.set_xlabel("First principal component")
    ax.set_ylabel("Second principal component")
    ax2 = fig.add_axes([0.60, 0.11, 0.38, 0.85])
    ax2.imshow(montage(X[pick], 5, 5, fill=0.2), cmap="gray_r", vmin=-1, vmax=1, interpolation="nearest")
    ax2.axis("off")
    savefig(fig, CH, "fig14-23", out_dir)
    ev = d ** 2 / (d ** 2).sum()
    print("  threes: variance explained by 12 PCs %.3f; PCs for 90%%: %d" % (ev[:12].sum(), int(np.searchsorted(np.cumsum(ev), 0.9) + 1)))


def fig_14_23b(out_dir=None):
    """The rank-two model (14.55): the mean three and the first two principal directions as images."""
    import matplotlib.pyplot as plt
    X = zip_threes()
    xbar, U, d, V = pca(X)
    fig, axes = plt.subplots(1, 3, figsize=(4.8, 1.8))
    _digit(axes[0], xbar)
    m = np.abs(V[:, :2]).max()
    for k in range(2):
        axes[k + 1].imshow(V[:, k].reshape(16, 16), cmap="RdBu_r", vmin=-m, vmax=m, interpolation="nearest")
        axes[k + 1].set_xticks([])
        axes[k + 1].set_yticks([])
    for ax, t in zip(axes, [r"$\bar x$", r"$v_1$", r"$v_2$"]):
        ax.set_title(t)
    fig.tight_layout()
    savefig(fig, CH, "eq14-55", out_dir)


def fig_14_24(out_dir=None):
    """Singular values of the threes and of a column-scrambled copy."""
    import matplotlib.pyplot as plt
    X = zip_threes()
    r = np.random.default_rng(1424)
    Xr = np.column_stack([r.permutation(X[:, j]) for j in range(X.shape[1])])
    d = linalg.svdvals(X - X.mean(0))
    dr = linalg.svdvals(Xr - Xr.mean(0))
    fig, ax = plt.subplots(figsize=(5.2, 3.8))
    ax.plot(np.arange(1, 257), d, ".", color="#5ab4e6", ms=4, label="Real trace")
    ax.plot(np.arange(1, 257), dr, ".", color="#e09020", ms=4, label="Randomised trace")
    ax.set_xlabel("Dimension")
    ax.set_ylabel("Singular values")
    ax.legend(frameon=True)
    savefig(fig, CH, "fig14-24", out_dir)


# --------------------------------------------------------------------------- Procrustes (14.56)-(14.60)
def signatures():
    """The three time-warped signature S's of Figures 14.25-14.26 (book website, signatureData.csv):
    a list of three 96 x 2 arrays of corresponding landmarks."""
    import pandas as pd
    D = pd.read_csv(common.esl_file("signatureData.csv"), index_col=0).values
    return [D[:, 2 * k: 2 * k + 2].astype(float) for k in range(3)]


def procrustes(X1, X2, scaling=False):
    """min over orthogonal R, mu (and beta > 0 if scaling) of ||X2 - (beta X1 R + 1 mu^T)||_F (14.56),
    (14.58): with centred X1~, X2~ and X1~^T X2~ = U D V^T, R = U V^T, beta = trace(D)/||X1~||_F^2,
    mu = xbar2 - beta R^T xbar1 (14.57). Returns (R, mu, beta, fitted, distance)."""
    m1, m2 = X1.mean(0), X2.mean(0)
    A, B = X1 - m1, X2 - m2
    U, d, Vt = linalg.svd(A.T @ B)
    R = U @ Vt
    beta = d.sum() / (A ** 2).sum() if scaling else 1.0
    mu = m2 - beta * R.T @ m1
    fit = beta * X1 @ R + mu
    return R, mu, beta, fit, float(np.sqrt(((X2 - fit) ** 2).sum()))


def procrustes_average(Xs, scaling=False, iters=200, tol=1e-12):
    """Procrustes average (14.59) (with scaling (14.115) if requested) by alternation: start with M = the
    first centred shape; (1) rotate (and scale) each centred X_l to M; (2) M = average of the fitted
    shapes; when scaling, M is renormalised to the size of the first shape to rule out the trivial
    solution beta = 0. Returns (M, [R_l], [beta_l], criterion path)."""
    Xc = [X - X.mean(0) for X in Xs]
    M = Xc[0].copy()
    size = np.sqrt((M ** 2).sum())
    path = []
    for _ in range(iters):
        fits, Rs, bs = [], [], []
        for X in Xc:
            U, d, Vt = linalg.svd(X.T @ M)
            R = U @ Vt
            b = d.sum() / (X ** 2).sum() if scaling else 1.0
            Rs.append(R)
            bs.append(b)
            fits.append(b * X @ R)
        Mn = np.mean(fits, 0)
        if scaling:
            Mn *= size / np.sqrt((Mn ** 2).sum())
        crit = sum(((f - Mn) ** 2).sum() for f in fits)
        path.append(crit)
        if np.abs(Mn - M).max() < tol:
            M = Mn
            break
        M = Mn
    return M, Rs, bs, path


def affine_average(Xs, p=2):
    """The affine-invariant average (14.60) without iteration (Exercise 14.10): with H_l the projection
    onto the column space of the centred X_l, M = the p leading eigenvectors of the average of the H_l
    (so M^T M = I), and A_l = (X_l^T X_l)^{-1} X_l^T M."""
    Xc = [X - X.mean(0) for X in Xs]
    Hs = [X @ linalg.solve(X.T @ X, X.T) for X in Xc]
    w, V = linalg.eigh(np.mean(Hs, 0))
    M = V[:, ::-1][:, :p]
    As = [linalg.solve(X.T @ X, X.T @ M) for X in Xc]
    crit = sum(((X @ A - M) ** 2).sum() for X, A in zip(Xc, As))
    return M, As, crit, w[::-1][:p + 1]


def fig_14_25(out_dir=None):
    """Two signature S's before and after a Procrustes rotation and translation."""
    import matplotlib.pyplot as plt
    S = signatures()
    X1 = S[0]
    th = 0.6
    Rot = np.array([[math.cos(th), math.sin(th)], [-math.sin(th), math.cos(th)]])
    X2 = S[1] @ Rot + np.array([260.0, -60.0])             # rotated and moved "for visual effect"
    R, mu, beta, fit, dist = procrustes(X2, X1)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.6))
    for ax, B in zip(axes, [X2, fit]):
        ax.plot(X1[:, 0], X1[:, 1], "o-", color="#f0a030", ms=3, lw=0.8)
        ax.plot(B[:, 0], B[:, 1], "o-", color="#18a878", ms=3, lw=0.8)
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig14-25", out_dir)
    print("  Procrustes distance between S1 and S2: %.1f (rotation angle recovered %.3f rad)" % (
        dist, math.atan2(R[0, 1], R[0, 0])))


def fig_14_26(out_dir=None):
    """Procrustes average of the three S's, and the average mapped back to each S."""
    import matplotlib.pyplot as plt
    S = signatures()
    M, Rs, bs, path = procrustes_average(S)
    fig, axes = plt.subplots(1, 4, figsize=(10.4, 2.9))
    cols = ["#f0a030", "#18a878", "#5a7be0"]
    ax = axes[0]
    for X, R, c in zip(S, Rs, cols):
        Y = (X - X.mean(0)) @ R
        ax.plot(Y[:, 0], Y[:, 1], "-", color=c, lw=0.8)
    ax.plot(M[:, 0], M[:, 1], "--", color=RED, lw=1.4)
    ax.set_title("Average and rotated shapes", fontsize=9)
    for k, (X, R) in enumerate(zip(S, Rs)):
        ax = axes[k + 1]
        back = M @ R.T + X.mean(0)
        ax.plot(X[:, 0], X[:, 1], "-", color=cols[k], lw=1)
        ax.plot(back[:, 0], back[:, 1], "--", color=RED, lw=1.2)
        ax.set_title("Average mapped to S %d" % (k + 1), fontsize=9)
    for ax in axes:
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig14-26", out_dir)
    print("  Procrustes average: %d iterations, criterion %.1f -> %.1f" % (len(path), path[0], path[-1]))


# =========================================================================== exercises of part A
def em_spherical(X, means, sigma, iters=200, tol=1e-12):
    """EM for the mixture (14.114) with g_k = N(mu_k, sigma^2 I), sigma known (Exercise 14.2): E-step
    responsibilities r_ik proportional to pi_k exp(-||x_i - mu_k||^2/(2 sigma^2)); M-step pi_k = mean_i r_ik,
    mu_k = sum_i r_ik x_i / sum_i r_ik. Returns (means, pi, responsibilities, log-likelihood path)."""
    mu = np.array(means, float)
    K, p = mu.shape
    pi = np.full(K, 1.0 / K)
    path = []
    for _ in range(iters):
        d2 = ((X[:, None, :] - mu[None]) ** 2).sum(2)
        L = np.log(pi)[None] - d2 / (2 * sigma ** 2) - p * np.log(2 * np.pi * sigma ** 2) / 2
        ll = common.logsumexp(L, axis=1)
        R = np.exp(L - ll[:, None])
        path.append(float(ll.sum()))
        pi = np.maximum(R.mean(0), 1e-300)
        new = (R.T @ X) / np.maximum(R.sum(0), 1e-300)[:, None]
        if np.abs(new - mu).max() < tol:
            mu = new
            break
        mu = new
    return mu, pi, R, path


def exercise_14_2():
    """EM with a small known sigma reproduces K-means (Exercise 14.2) on the data of Figure 14.4."""
    X, _ = three_clusters()
    init = np.array([[-0.4, 3.9], [0.6, 3.5], [0.3, 1.4]])
    km = kmeans(X, 3, init=init)
    out = {}
    for s in (1.0, 0.3, 0.1, 0.03):
        mu, pi, R, path = em_spherical(X, init, s)
        out[s] = dict(max_mean_diff=float(np.abs(np.sort(mu, 0) - np.sort(km["centres"], 0)).max()),
                      agree=float(np.mean(R.argmax(1) == km["labels"])), max_soft=float(1 - R.max(1).min()),
                      monotone=bool(np.all(np.diff(path) > -1e-8)))
    return out


def market_tree(seed=144, depth=6, min_leaf=100):
    """Exercise 14.4 (and the problem of Exercise 14.3): the 6876 complete questionnaires (class 1) and a
    reference sample of the same size made by permuting each column independently (the product of the
    marginals (14.15), class 0), classified by a CART tree on the 14 coded inputs. Returns the root
    split's Gini gain, the best possible single-split gain on the pooled data, and the leaves with the
    highest class-1 fraction described as rules."""
    from sklearn.tree import DecisionTreeClassifier
    D = marketing()
    r = np.random.default_rng(seed)
    R = np.column_stack([r.permutation(D[:, j]) for j in range(D.shape[1])])
    P = np.vstack([D, R])
    y = np.r_[np.ones(len(D)), np.zeros(len(R))]
    t = DecisionTreeClassifier(max_depth=depth, min_samples_leaf=min_leaf, random_state=0).fit(P, y)
    tr = t.tree_
    # Gini gain of the root split and of a depth-2 tree, per observation
    imp0 = tr.impurity[0]
    l, rr = tr.children_left[0], tr.children_right[0]
    n = tr.weighted_n_node_samples
    gain_root = imp0 - (n[l] * tr.impurity[l] + n[rr] * tr.impurity[rr]) / n[0]
    leaves = np.where(tr.children_left == -1)[0]
    frac = tr.value[leaves][:, 0, 1] / tr.value[leaves][:, 0].sum(1)
    top = leaves[np.argsort(-frac)][:4]

    def path_to(node):
        parent = {}
        for i in range(tr.node_count):
            for c, side in ((tr.children_left[i], "<="), (tr.children_right[i], ">")):
                if c != -1:
                    parent[c] = (i, side)
        conds = []
        while node in parent:
            i, side = parent[node]
            conds.append("%s %s %.1f" % (MARKET_NAMES[tr.feature[i]], side, tr.threshold[i]))
            node = i
        return " and ".join(conds[::-1])
    out = []
    for leaf in top:
        nn = tr.value[leaf][0].sum()
        f1 = tr.value[leaf][0, 1] / nn
        out.append(dict(rule=path_to(leaf), class1=float(f1), support=float(f1 * n[leaf] / len(D))))
    return dict(gain_root=float(gain_root), leaves=out)


def exercise_14_6(Ks=((1, 2), (1, 5), (2, 5), (4, 5)), seed=146, radii=(2.0, 1.0, 0.5, 0.2, 0.05)):
    """Exercise 14.6: K-means and a batch SOM (Gaussian neighbourhood of grid width r) on the 64
    microarray samples (the columns of the gene x sample matrix), with K = 2, 5, 10, 20 prototypes on a
    q1 x q2 grid, started on the principal component plane. As r shrinks the SOM error falls towards
    the K-means value, and at the smallest r the SOM partition is a K-means fixed point. Returns {K:
    (best K-means W over 30 starts, [SOM error at each r], fraction of samples whose cluster is unchanged
    when K-means is started from the final SOM prototypes)}."""
    X, _ = nci()
    out = {}
    for q1, q2 in Ks:
        K = q1 * q2
        km = kmeans(X, K, n_init=30, seed=seed + K)
        M, grid = som_init(X, q1, q2)
        errs = []
        for r in radii:
            M = som_batch(X, M, grid, r, iters=100, kernel="gauss")
            errs.append(som_error(X, M))
        km_same = kmeans(X, K, init=M)
        win = ((X[:, None, :] - M[None]) ** 2).sum(2).argmin(1)
        out[K] = (km["W"], errs, float(np.mean(win == km_same["labels"])))
    return out


def exercise_14_5():
    """Exercise 14.5 with the printed noise level sd = 0.6 and with sd = 0.1: SOM and K-means (25
    prototypes) reconstruction errors, and the total sum of squares."""
    out = {}
    for sd in (0.6, 0.1):
        X, g = half_sphere(sd=sd)
        M, grid, tr = som_online(X, seed=1416)
        out[sd] = dict(som=som_error(X, M), kmeans=kmeans(X, 25, n_init=50, seed=25)["W"],
                       total=float(((X - X.mean(0)) ** 2).sum()))
    return out


def exercise_14_9_10():
    """Procrustes average with scaling (14.115) and the affine-invariant average (14.60) of the three S's."""
    S = signatures()
    M0, R0, b0, p0 = procrustes_average(S)
    M1, R1, b1, p1 = procrustes_average(S, scaling=True)
    Ma, As, crit, ev = affine_average(S)
    return dict(plain=p0[-1], scaled=p1[-1], betas=b1, affine_crit=crit, affine_eigs=ev)


def demo_reference():
    """Numbers quoted in the notes for part A."""
    out = {}
    rules, nfreq = market_rules()
    out["n_freq"], out["n_rules"] = nfreq, len(rules)
    return out


def fig_14_23_and_model(out_dir=None):
    """First two principal components of the threes, and the rank-two model (14.55) as images."""
    fig_14_23(out_dir)
    fig_14_23b(out_dir)


# =========================================================================== driver
FIGURES = {
    "14.2": fig_14_2, "14.3": fig_14_3, "14.4": fig_14_4, "14.5": fig_14_5, "14.6": fig_14_6,
    "14.7": fig_14_7, "14.8": fig_14_8, "14.9": fig_14_9, "14.10": fig_14_10, "14.11": fig_14_11,
    "14.12": fig_14_12, "14.13": fig_14_13, "14.14": fig_14_14, "14.15": fig_14_15, "14.16": fig_14_16,
    "14.17": fig_14_17, "14.18": fig_14_18, "14.20": fig_14_20, "14.21": fig_14_21, "14.22": fig_14_22,
    "14.23": fig_14_23_and_model, "14.24": fig_14_24, "14.25": fig_14_25, "14.26": fig_14_26,
}


if __name__ == "__main__":
    common.run(FIGURES, CH)
