"""Murphy (2022), Chapter 21: Clustering.

Companion code for Chapter 21 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 715-740, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch21-clustering.html). scikit-learn is used only
to load an example image and to confirm the implementations.

Methods
* Section 21.1.1, external evaluation of a clustering from the contingency table: purity (21.1), the
  pair counts TP, FP, FN, TN and the Rand index (21.3), the adjusted Rand index (21.6) with the
  hypergeometric expectation, mutual information (21.7) and normalised mutual information (21.8)
  (contingency, purity, pair_counts, rand_index, adjusted_rand, mutual_info, nmi).
* Section 21.2, hierarchical agglomerative clustering: Algorithm 21.1 with the Lance-Williams update
  for single, complete and average link (hac, which returns a linkage matrix in the usual format),
  cutting the tree (cut_tree), and single link as a minimum spanning tree (mst_prim).
* Section 21.3, K-means: Lloyd's two steps and the distortion (21.13)-(21.15) (kmeans), the K-means++
  seeding (21.18)-(21.19) (kmeanspp), restarts, mini-batch K-means (minibatch_kmeans), K-medoids by
  Voronoi iteration (Algorithm 21.2) and PAM (kmedoids, pam), vector quantisation of an image
  (vq_image), the silhouette coefficient (silhouette) and BIC for a Gaussian mixture.
* Section 21.4, mixtures: EM for a Gaussian mixture with full, tied, diagonal and spherical
  covariances (gmm_em), responsibilities (21.23), hard clustering (21.24); Gibbs sampling for a
  one-dimensional Gaussian mixture, label switching and the ordering constraint (21.25)-(21.26)
  (gibbs_gmm1d), and WAIC (waic).
* Section 21.5, spectral clustering: the Gaussian affinity, the Laplacians (21.30), (21.31), the
  normalised-cut value (21.28)-(21.29) (spectral_embed, spectral_cluster, ncut_value).
* Section 21.6, biclustering: the Bernoulli block model (21.33)-(21.35) fitted by alternating
  maximisation (bicluster_fit) and the nested partition (crosscat) pattern of Figure 21.21.

Data. The book's own data sets are not available offline, so close stand-ins are simulated with fixed
seeds and said so in the captions: the yeast time series of Figures 21.4 to 21.8 (300 genes, 7 time
points, eight prototype response shapes plus noise), the five-blob plane data of Figures 21.7 and
21.10 to 21.13, the 2-D data of Figure 21.14, the 1-D data of Figures 21.15 to 21.18, and the
animal-by-feature data of Figure 21.20. The grey-scale image of Figure 21.9 is a crop of the sample
photograph that ships with scikit-learn.

Figures. Reproduced here: 21.1 (redrawn with computed counts), 21.2, 21.3 (redrawn with computed
distances), 21.4, 21.5, 21.6, 21.7, 21.8, 21.9, 21.10, 21.11, 21.12, 21.13, 21.14, 21.15, 21.16,
21.17, 21.18, 21.19, 21.20 (on simulated data), 21.21. Skipped, with the reason:
  21.22  the crosscat MAP partition of the 22-animal data: the data (106 binary features) are the
         authors' and are not available; Figure 21.21b shows the model on a 6 x 6 example instead.
Supplementary figures for the gaps filled in the notes (names fig21-s1, ...):
  21.S1  single link is the minimum spanning tree: merge heights against the sorted MST edges;
  21.S2  K-means++ against random seeding: the distribution of the final distortion over seeds;
  21.S3  the Laplacian spectrum: the number of near-zero eigenvalues counts the connected pieces;
  21.S4  the likelihood of a Gaussian mixture is unbounded: collapsing a component on a data point.
Run `python3 ch21_clustering.py --list`, `python3 ch21_clustering.py` (all figures, a few minutes) or
`python3 ch21_clustering.py --fig 21.7`. Files go to ../img/ch21/; the data used by the browser
demonstrations go to ../data/ch21-*.json.
"""
import json
import math
import os
import sys
import time

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import special

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 21
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
PAL = ["#1f5fbf", "#d62728", "#2ca02c", "#ff7f0e", "#7b4fbf", "#17becf", "#c2185b", "#8c564b", "#7f7f7f", "#bcbd22",
       "#393b79", "#e377c2", "#637939", "#843c39", "#17a589", "#b8860b"]


def _r(a, nd=4):
    return np.round(np.asarray(a, float), nd).tolist()


# =========================================================================== data
YEAST_T = np.array([0.0, 9.5, 11.5, 13.5, 15.5, 18.5, 20.5])


def yeast_standin(n=300, seed=21):
    """Simulated stand-in for the yeast expression data (300 genes x 7 times): eight prototype shapes with
    unequal sizes, per-gene amplitude and noise; every gene is standardised to mean 0, sd 1."""
    rng = np.random.default_rng(seed)
    t = (YEAST_T - YEAST_T.min()) / (YEAST_T.max() - YEAST_T.min())
    protos = [
        3 * t - 1.5,                                  # steadily up
        -3 * t + 1.5,                                 # steadily down
        np.exp(-((t - 0.45) / 0.18) ** 2) * 3 - 0.8,  # mid bump
        -np.exp(-((t - 0.45) / 0.18) ** 2) * 3 + 0.8, # mid dip
        np.exp(-((t - 0.1) / 0.25) ** 2) * 3 - 0.6,   # early peak
        np.exp(-((t - 0.9) / 0.25) ** 2) * 3 - 0.6,   # late peak
        np.sin(2 * np.pi * t * 1.5),                  # oscillation
        np.where(t > 0.5, 1.2, -1.2) * np.ones_like(t),  # step up
    ]
    sizes = np.array([55, 50, 40, 30, 40, 35, 25, 25])
    sizes = (sizes * n / sizes.sum()).astype(int)
    sizes[0] += n - sizes.sum()
    rows, lab = [], []
    for k, (p, m) in enumerate(zip(protos, sizes)):
        amp = rng.uniform(0.7, 1.3, m)[:, None]
        shift = rng.normal(0, 0.15, (m, 1))
        x = amp * p[None, :] + shift + rng.normal(0, 0.45, (m, len(t)))
        rows.append(x)
        lab += [k] * m
    X = np.vstack(rows)
    X = (X - X.mean(1, keepdims=True)) / X.std(1, keepdims=True)
    perm = rng.permutation(len(X))
    return X[perm], np.array(lab)[perm]


def blobs5(n=2000, seed=7):
    """Five Gaussian blobs of unequal width in the plane (the K-means examples of Figures 21.7, 21.10-21.13)."""
    rng = np.random.default_rng(seed)
    centres = np.array([[0.5, 3.0], [-3.0, 3.0], [-6.5, 1.9], [-6.5, 3.0], [-6.5, 4.1]])
    stds = np.array([0.6, 0.5, 0.25, 0.25, 0.25])
    w = np.array([0.30, 0.30, 0.14, 0.14, 0.12])
    w = w / w.sum()
    z = rng.choice(5, n, p=w)
    X = centres[z] + stds[z, None] * rng.standard_normal((n, 2))
    return X, z


def gmm2d_data(n=900, seed=14):
    """2-D data from five Gaussian clusters, three of them strongly correlated (Figure 21.14)."""
    rng = np.random.default_rng(seed)
    mus = np.array([[-6.0, 2.2], [-3.2, -1.2], [0.6, 2.0], [3.6, -0.6], [-1.0, -2.0]])
    covs = [np.array([[1.4, 0.0], [0.0, 0.25]]), np.array([[1.2, 0.9], [0.9, 1.0]]),
            np.array([[0.9, -0.5], [-0.5, 0.6]]), np.array([[1.5, 1.1], [1.1, 1.0]]),
            np.array([[0.5, 0.0], [0.0, 0.5]])]
    w = np.array([0.22, 0.22, 0.2, 0.2, 0.16])
    z = rng.choice(5, n, p=w)
    X = np.zeros((n, 2))
    for k in range(5):
        m = z == k
        X[m] = rng.multivariate_normal(mus[k], covs[k], m.sum())
    return X, z


def data_1d(n=250, seed=15):
    """1-D data with two broad bumps near 47 and 57 and a right tail (Figure 21.15)."""
    rng = np.random.default_rng(seed)
    w = np.array([0.34, 0.46, 0.20])
    mu = np.array([47.0, 57.0, 62.5])
    sd = np.array([1.9, 2.4, 3.6])
    z = rng.choice(3, n, p=w)
    return np.sort(mu[z] + sd[z] * rng.standard_normal(n))


def rings(n=300, seed=19):
    """Two concentric noisy rings (radius 2 and 5), the case K-means cannot solve (Figure 21.19)."""
    rng = np.random.default_rng(seed)
    n1 = n // 3
    r = np.r_[np.full(n1, 2.0), np.full(n - n1, 5.0)] + 0.25 * rng.standard_normal(n)
    th = rng.uniform(0, 2 * np.pi, n)
    X = np.c_[r * np.cos(th), r * np.sin(th)]
    return X, np.r_[np.zeros(n1, int), np.ones(n - n1, int)]


def moons(n=200, noise=0.08, seed=3):
    rng = np.random.default_rng(seed)
    m = n // 2
    t = rng.uniform(0, np.pi, m)
    a = np.c_[np.cos(t), np.sin(t)]
    b = np.c_[1 - np.cos(t), 0.5 - np.sin(t)]
    X = np.vstack([a, b]) + noise * rng.standard_normal((2 * m, 2))
    return X, np.r_[np.zeros(m, int), np.ones(m, int)]


def sample_image():
    """200 x 320 grey-scale crop of the sample photograph shipped with scikit-learn, values in 0..255."""
    from sklearn.datasets import load_sample_image
    im = load_sample_image("china.jpg").astype(float)
    g = 0.299 * im[..., 0] + 0.587 * im[..., 1] + 0.114 * im[..., 2]
    return np.round(g[110:310, 100:420])


# =========================================================================== evaluation of a clustering
def contingency(u, v):
    """N_ij = number of objects in cluster i of u and class j of v (labels need not be 0..R-1)."""
    ui, uinv = np.unique(u, return_inverse=True)
    vj, vinv = np.unique(v, return_inverse=True)
    T = np.zeros((len(ui), len(vj)), dtype=np.int64)
    np.add.at(T, (uinv, vinv), 1)
    return T


def purity(T):
    """(21.1): sum_i (N_i / N) max_j p_ij = (1/N) sum_i max_j N_ij."""
    return T.max(1).sum() / T.sum()


def _c2(a):
    a = np.asarray(a, dtype=np.int64)
    return a * (a - 1) // 2


def pair_counts(T):
    """TP, FP, FN, TN of the pairs (rows of T = estimated clusters U, columns = reference V)."""
    N = T.sum()
    tp = _c2(T).sum()
    same_u = _c2(T.sum(1)).sum()
    same_v = _c2(T.sum(0)).sum()
    fp = same_u - tp
    fn = same_v - tp
    tn = _c2(N) - tp - fp - fn
    return int(tp), int(fp), int(fn), int(tn)


def rand_index(T):
    tp, fp, fn, tn = pair_counts(T)
    return (tp + tn) / (tp + fp + fn + tn)


def adjusted_rand(T):
    """(21.6) with the hypergeometric model: index = sum_ij C(N_ij,2); expected = (sum_i C(a_i,2))(sum_j C(b_j,2))/C(N,2);
    max = (sum_i C(a_i,2) + sum_j C(b_j,2)) / 2 (Hubert and Arabie 1985)."""
    N = T.sum()
    idx = _c2(T).sum()
    sa = _c2(T.sum(1)).sum()
    sb = _c2(T.sum(0)).sum()
    exp = sa * sb / _c2(N)
    mx = 0.5 * (sa + sb)
    return float((idx - exp) / (mx - exp))


def entropy_counts(c):
    p = np.asarray(c, float) / np.sum(c)
    p = p[p > 0]
    return float(-(p * np.log(p)).sum())


def mutual_info(T):
    """(21.7), natural logarithm."""
    P = T / T.sum()
    pu, pv = P.sum(1, keepdims=True), P.sum(0, keepdims=True)
    m = P > 0
    return float((P[m] * np.log(P[m] / (pu @ pv)[m])).sum())


def nmi(T):
    """(21.8): I(U,V) / ((H(U)+H(V))/2)."""
    hu, hv = entropy_counts(T.sum(1)), entropy_counts(T.sum(0))
    return mutual_info(T) / (0.5 * (hu + hv))


# =========================================================================== hierarchical clustering
def hac(D, method="average"):
    """Algorithm 21.1 for a symmetric dissimilarity matrix D (N x N). Returns the linkage matrix Z of
    shape (N-1, 4): rows (cluster a, cluster b, merge height, size), new clusters numbered N, N+1, ...
    method: 'single' (21.10), 'complete' (21.11), 'average' (21.12). Lance-Williams updates; O(N^3)."""
    N = len(D)
    d = np.array(D, dtype=float)
    np.fill_diagonal(d, np.inf)
    ids = list(range(N))
    size = np.ones(N)
    active = np.ones(N, bool)
    Z = np.zeros((N - 1, 4))
    for step in range(N - 1):
        dd = np.where(active[:, None] & active[None, :], d, np.inf)
        k = int(np.argmin(dd))
        i, j = divmod(k, N)
        if i > j:
            i, j = j, i
        h = dd[i, j]
        Z[step] = (min(ids[i], ids[j]), max(ids[i], ids[j]), h, size[i] + size[j])
        # update row i to hold the union, retire j
        if method == "single":
            new = np.minimum(d[i], d[j])
        elif method == "complete":
            new = np.maximum(d[i], d[j])
        elif method == "average":
            new = (size[i] * d[i] + size[j] * d[j]) / (size[i] + size[j])
        else:
            raise ValueError(method)
        d[i, :] = new
        d[:, i] = new
        d[i, i] = np.inf
        active[j] = False
        size[i] += size[j]
        ids[i] = N + step
    return Z


def cut_tree(Z, k):
    """Labels 0..k-1 of the k clusters obtained by undoing the last k-1 merges of the linkage matrix Z."""
    N = len(Z) + 1
    parent = list(range(2 * N - 1))

    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a
    for s in range(N - k):
        a, b = int(Z[s, 0]), int(Z[s, 1])
        parent[find(a)] = N + s
        parent[find(b)] = N + s
    roots = [find(i) for i in range(N)]
    _, lab = np.unique(roots, return_inverse=True)
    return lab


def pdist_matrix(X, metric="euclidean"):
    X = np.asarray(X, float)
    if metric == "cityblock":
        return np.abs(X[:, None, :] - X[None, :, :]).sum(2)
    return np.sqrt(np.maximum(((X[:, None, :] - X[None, :, :]) ** 2).sum(2), 0))


def mst_prim(D):
    """Edges (i, j, w) of a minimum spanning tree by Prim's algorithm, sorted by weight."""
    N = len(D)
    inT = np.zeros(N, bool)
    inT[0] = True
    best = D[0].astype(float).copy()
    frm = np.zeros(N, int)
    edges = []
    for _ in range(N - 1):
        cand = np.where(inT, np.inf, best)
        j = int(np.argmin(cand))
        edges.append((int(frm[j]), j, float(best[j])))
        inT[j] = True
        upd = D[j] < best
        best = np.where(upd & ~inT, D[j], best)
        frm = np.where(upd & ~inT, j, frm)
    return sorted(edges, key=lambda e: e[2])


# =========================================================================== K-means
def sqdist(X, C):
    return np.maximum((X ** 2).sum(1)[:, None] - 2 * X @ C.T + (C ** 2).sum(1)[None, :], 0.0)


def kmeanspp(X, K, rng):
    """K-means++ seeding (21.18)-(21.19): first centre uniform, then D^2 sampling."""
    N = len(X)
    idx = [int(rng.integers(N))]
    d2 = ((X - X[idx[0]]) ** 2).sum(1)
    for _ in range(1, K):
        p = d2 / d2.sum()
        j = int(rng.choice(N, p=p))
        idx.append(j)
        d2 = np.minimum(d2, ((X - X[j]) ** 2).sum(1))
    return X[idx].copy()


def kmeans(X, K, init="kmeans++", rng=None, max_iter=300, return_trace=False):
    """Lloyd's algorithm: alternate (21.13) and (21.14) until the assignments stop changing.
    init: 'kmeans++', 'random' (K distinct data points) or an array of K starting centres.
    Returns centres, labels, distortion J of (21.15) (a sum, not a mean); optionally the J after every step."""
    rng = rng or np.random.default_rng(0)
    X = np.asarray(X, float)
    if isinstance(init, str):
        C = kmeanspp(X, K, rng) if init == "kmeans++" else X[rng.choice(len(X), K, replace=False)].copy()
    else:
        C = np.array(init, float).copy()
    lab = None
    trace = []
    for it in range(max_iter):
        d = sqdist(X, C)
        new = d.argmin(1)
        trace.append(float(d[np.arange(len(X)), new].sum()))
        if lab is not None and np.array_equal(new, lab):
            break
        lab = new
        for k in range(K):
            m = lab == k
            if m.any():
                C[k] = X[m].mean(0)
            else:                                   # empty cluster: restart it at the worst-fit point
                C[k] = X[d[np.arange(len(X)), lab].argmax()]
    J = float(((X - C[lab]) ** 2).sum())
    return (C, lab, J, trace) if return_trace else (C, lab, J)


def kmeans_best(X, K, n_init=10, seed=0, init="kmeans++"):
    rng = np.random.default_rng(seed)
    best = None
    for _ in range(n_init):
        r = kmeans(X, K, init, rng)
        if best is None or r[2] < best[2]:
            best = r
    return best


def minibatch_kmeans(X, K, batch=256, iters=100, rng=None):
    """Sculley (2010): per-centre learning rate 1/(number of points the centre has absorbed)."""
    rng = rng or np.random.default_rng(0)
    C = kmeanspp(X, K, rng)
    cnt = np.zeros(K)
    for _ in range(iters):
        B = X[rng.choice(len(X), batch, replace=False)]
        a = sqdist(B, C).argmin(1)
        for x, k in zip(B, a):
            cnt[k] += 1
            C[k] += (x - C[k]) / cnt[k]
    lab = sqdist(X, C).argmin(1)
    return C, lab, float(((X - C[lab]) ** 2).sum())


def kmedoids(Dm, K, rng=None, max_iter=100, init=None):
    """Algorithm 21.2 (Voronoi iteration) on a distance matrix; returns medoid indices, labels, cost."""
    rng = rng or np.random.default_rng(0)
    N = len(Dm)
    m = np.array(init) if init is not None else rng.choice(N, K, replace=False)
    lab = None
    for _ in range(max_iter):
        new = Dm[:, m].argmin(1)
        if lab is not None and np.array_equal(new, lab):
            break
        lab = new
        for k in range(K):
            idx = np.where(lab == k)[0]
            if len(idx):
                m[k] = idx[Dm[np.ix_(idx, idx)].sum(1).argmin()]
    lab = Dm[:, m].argmin(1)
    return m, lab, float(Dm[np.arange(N), m[lab]].sum())


def pam(Dm, K, init):
    """Partitioning around medoids: accept any single swap medoid <-> non-medoid that lowers the cost."""
    N = len(Dm)
    m = list(init)
    cost = Dm[:, m].min(1).sum()
    improved = True
    while improved:
        improved = False
        for a in range(K):
            for o in range(N):
                if o in m:
                    continue
                t = m.copy()
                t[a] = o
                c = Dm[:, t].min(1).sum()
                if c < cost - 1e-12:
                    m, cost, improved = t, c, True
    return np.array(m), float(cost)


def distortion(X, C):
    return float(sqdist(X, C).min(1).sum())


def silhouette(X, lab, per_point=False, book=False):
    """Silhouette coefficients sc(i) = (b - a) / max(a, b); a = mean distance to the other members of the
    own cluster, b = smallest mean distance to another cluster (standard definition). With book=True the
    'next closest cluster' is the one with the nearest centroid, as in the text of Section 21.3.7.3."""
    X = np.asarray(X, float)
    K = lab.max() + 1
    D = np.sqrt(sqdist(X, X))
    n = np.array([(lab == k).sum() for k in range(K)])
    S = np.stack([D[:, lab == k].sum(1) for k in range(K)], 1)            # sum of distances to each cluster
    own = lab
    a = S[np.arange(len(X)), own] / np.maximum(n[own] - 1, 1)
    M = S / np.maximum(n[None, :], 1)
    M[np.arange(len(X)), own] = np.inf
    if book:
        C = np.stack([X[lab == k].mean(0) for k in range(K)])
        dc = sqdist(X, C)
        dc[np.arange(len(X)), own] = np.inf
        nxt = dc.argmin(1)
        b = M[np.arange(len(X)), nxt]
    else:
        b = M.min(1)
    sc = (b - a) / np.maximum(a, b)
    sc[n[own] == 1] = 0.0
    return sc if per_point else float(sc.mean())


def vq_image(img, K, seed=0):
    """Vector quantisation of grey levels: K-means on the pixel values (1-D), K centres, rate log2 K bits per pixel."""
    x = img.reshape(-1, 1)
    C, lab, J = kmeans_best(x, K, 5, seed)
    return C[lab].reshape(img.shape), C.ravel(), J / x.shape[0]


# =========================================================================== Gaussian mixtures (EM)
def _logpdf_full(X, mu, S):
    return common.gauss_logpdf(X, mu, S)


def gmm_loglik_components(X, w, mu, Sig):
    """(N, K) matrix of log pi_k + log N(x_n | mu_k, Sigma_k)."""
    return np.stack([np.log(w[k]) + _logpdf_full(X, mu[k], Sig[k]) for k in range(len(w))], 1)


def gmm_nparams(K, D, cov):
    base = (K - 1) + K * D
    return base + {"full": K * D * (D + 1) // 2, "tied": D * (D + 1) // 2, "diag": K * D, "spherical": K}[cov]


def gmm_em(X, K, cov="full", n_iter=500, tol=1e-9, seed=0, init_lab=None, reg=1e-6):
    """EM for a Gaussian mixture (Section 21.4.1) with covariance structure cov in
    {'full', 'tied', 'diag', 'spherical'}; started from K-means. Returns dict(w, mu, Sig, ll, resp, ...)."""
    X = np.asarray(X, float)
    N, D = X.shape
    if init_lab is None:
        init_lab = kmeans_best(X, K, 5, seed)[1]
    R = np.eye(K)[init_lab]
    prev = -np.inf
    lls = []
    for it in range(n_iter):
        # M step
        Nk = R.sum(0) + 1e-12
        w = Nk / N
        mu = (R.T @ X) / Nk[:, None]
        S = []
        for k in range(K):
            d = X - mu[k]
            S.append((R[:, k, None] * d).T @ d / Nk[k])
        if cov == "full":
            Sig = [s + reg * np.eye(D) for s in S]
        elif cov == "tied":
            T = sum(Nk[k] * S[k] for k in range(K)) / N + reg * np.eye(D)
            Sig = [T] * K
        elif cov == "diag":
            Sig = [np.diag(np.diag(s)) + reg * np.eye(D) for s in S]
        else:
            Sig = [(np.trace(s) / D + reg) * np.eye(D) for s in S]
        # E step
        L = gmm_loglik_components(X, w, mu, Sig)
        lse = special.logsumexp(L, axis=1)
        R = np.exp(L - lse[:, None])
        ll = float(lse.sum())
        lls.append(ll)
        if ll - prev < tol * abs(ll):
            break
        prev = ll
    return dict(w=w, mu=mu, Sig=np.array(Sig), ll=ll, resp=R, lls=lls, cov=cov, K=K,
                bic=-2 * ll + gmm_nparams(K, D, cov) * math.log(N))


def gmm_best(X, K, cov="full", n_init=5, seed=0):
    best = None
    for s in range(n_init):
        r = gmm_em(X, K, cov, seed=seed + s)
        if best is None or r["ll"] > best["ll"]:
            best = r
    return best


# =========================================================================== 1-D Gibbs sampler, WAIC
def gibbs_gmm1d(y, K, n_iter=1500, burn=500, seed=0, init_mu=None, a0=2.0, b0=None, m0=None, s0=30.0):
    """Gibbs sampler for a K-component 1-D Gaussian mixture with conjugate priors:
    pi ~ Dir(1), mu_k ~ N(m0, s0^2), sigma_k^2 ~ InvGamma(a0, b0). Returns draws of (pi, mu, sigma2)
    after burn-in (labels are NOT relabelled: this is the unconstrained posterior)."""
    rng = np.random.default_rng(seed)
    n = len(y)
    m0 = float(np.mean(y)) if m0 is None else m0
    b0 = 0.5 * float(np.var(y)) / 4 if b0 is None else b0
    mu = np.array(init_mu, float) if init_mu is not None else np.sort(rng.choice(y, K, replace=False)).astype(float)
    s2 = np.full(K, np.var(y) / K ** 1.0)
    pi = np.full(K, 1.0 / K)
    out = []
    for it in range(n_iter):
        lp = np.log(pi)[None, :] - 0.5 * np.log(2 * np.pi * s2)[None, :] - 0.5 * (y[:, None] - mu[None, :]) ** 2 / s2[None, :]
        lp -= lp.max(1, keepdims=True)
        p = np.exp(lp)
        p /= p.sum(1, keepdims=True)
        u = rng.random(n)[:, None]
        z = (p.cumsum(1) < u).sum(1)
        z = np.minimum(z, K - 1)
        cnt = np.bincount(z, minlength=K)
        pi = rng.dirichlet(1.0 + cnt)
        for k in range(K):
            yk = y[z == k]
            prec = 1.0 / s0 ** 2 + cnt[k] / s2[k]
            mean = (m0 / s0 ** 2 + yk.sum() / s2[k]) / prec
            mu[k] = mean + rng.standard_normal() / math.sqrt(prec)
            ss = ((yk - mu[k]) ** 2).sum()
            s2[k] = 1.0 / rng.gamma(a0 + 0.5 * cnt[k], 1.0 / (b0 + 0.5 * ss))
        if it >= burn:
            out.append((pi.copy(), mu.copy(), s2.copy()))
    pi_d = np.array([o[0] for o in out])
    mu_d = np.array([o[1] for o in out])
    s2_d = np.array([o[2] for o in out])
    return pi_d, mu_d, s2_d


def mix_logpdf_draws(y, pi, mu, s2):
    """(S, N): log of the mixture density of every point under every draw."""
    lp = np.log(pi)[:, None, :] - 0.5 * np.log(2 * np.pi * s2)[:, None, :] - 0.5 * (y[None, :, None] - mu[:, None, :]) ** 2 / s2[:, None, :]
    return special.logsumexp(lp, axis=2)


def waic(y, pi, mu, s2):
    """WAIC on the log-score scale: elpd = sum_i [log mean_s p(y_i | theta_s) - var_s log p(y_i | theta_s)],
    its standard error, lppd (in-sample) and the penalty p_waic."""
    L = mix_logpdf_draws(y, pi, mu, s2)
    lppd_i = special.logsumexp(L, axis=0) - np.log(L.shape[0])
    p_i = L.var(0, ddof=1)
    e_i = lppd_i - p_i
    return dict(elpd=float(e_i.sum()), se=float(np.sqrt(len(y) * e_i.var(ddof=1))), lppd=float(lppd_i.sum()), p=float(p_i.sum()))


def sort_draws(pi, mu, s2):
    o = np.argsort(mu, axis=1)
    r = np.arange(len(mu))[:, None]
    return pi[r, o], mu[r, o], s2[r, o]


# =========================================================================== spectral clustering
def gaussian_affinity(X, sigma):
    return np.exp(-sqdist(X, X) / (2 * sigma ** 2))


def laplacians(W):
    d = W.sum(1)
    L = np.diag(d) - W
    Dm12 = 1.0 / np.sqrt(d)
    Lsym = np.eye(len(W)) - Dm12[:, None] * W * Dm12[None, :]
    Lrw = np.eye(len(W)) - W / d[:, None]
    return L, Lsym, Lrw, d


def spectral_embed(W, K, kind="sym"):
    """The N x K matrix of the K smallest eigenvectors: of L (kind 'unnorm'), of Lsym with unit-norm rows
    (kind 'sym', the algorithm after (21.30)) or of Lrw (kind 'rw'). Also returns all eigenvalues."""
    L, Lsym, Lrw, d = laplacians(W)
    if kind == "unnorm":
        ev, U = np.linalg.eigh(L)
        return U[:, :K], ev
    if kind == "sym":
        ev, U = np.linalg.eigh(Lsym)
        U = U[:, :K]
        return U / np.linalg.norm(U, axis=1, keepdims=True), ev
    ev, V = np.linalg.eigh(Lsym)                 # eigenvectors of Lrw are D^{-1/2} v for the symmetric problem
    return (V[:, :K] / np.sqrt(d)[:, None]), ev


def spectral_cluster(X, K, sigma, kind="sym", seed=0):
    W = gaussian_affinity(X, sigma)
    np.fill_diagonal(W, 0.0)
    U, ev = spectral_embed(W, K, kind)
    lab = kmeans_best(U, K, 10, seed)[1]
    return lab, U, ev


def ncut_value(W, lab, half=True):
    """(21.29): (1/2) sum_k W(S_k, complement) / vol(S_k); with half=False the factor 1/2 is dropped."""
    d = W.sum(1)
    tot = 0.0
    for k in np.unique(lab):
        m = lab == k
        tot += W[np.ix_(m, ~m)].sum() / d[m].sum()
    return 0.5 * tot if half else tot


# =========================================================================== biclustering
def block_data(Nr=50, Nc=60, nu=4, nv=3, seed=5, flip=0.0):
    rng = np.random.default_rng(seed)
    theta = np.array([[0.85, 0.08, 0.08], [0.08, 0.85, 0.08], [0.08, 0.08, 0.85], [0.85, 0.85, 0.08]])[:nu, :nv]
    u = rng.integers(nu, size=Nr)
    v = rng.integers(nv, size=Nc)
    X = (rng.random((Nr, Nc)) < theta[u][:, v]).astype(int)
    return X, u, v, theta


def bicluster_fit(X, nu, nv, n_iter=60, seed=0, n_init=10):
    """Alternating maximisation of the Bernoulli block-model likelihood (21.33)-(21.35): given the column
    clusters, move every row to the row cluster with the largest log-likelihood; then the same for columns."""
    rng = np.random.default_rng(seed)
    Nr, Nc = X.shape
    best = None
    for _ in range(n_init):
        u = rng.integers(nu, size=Nr)
        v = rng.integers(nv, size=Nc)
        prev = -np.inf
        for it in range(n_iter):
            Cv = np.eye(nv)[v]
            Cu = np.eye(nu)[u]
            ones = Cu.T @ X @ Cv
            cnt = np.outer(Cu.sum(0), Cv.sum(0))
            th = np.clip((ones + 0.5) / (cnt + 1.0), 1e-3, 1 - 1e-3)
            # rows
            r1 = X @ Cv                                    # (Nr, nv): ones of row i in column cluster b
            r0 = (1 - X) @ Cv
            u = (r1 @ np.log(th).T + r0 @ np.log(1 - th).T).argmax(1)
            Cu = np.eye(nu)[u]
            ones = Cu.T @ X @ Cv
            th = np.clip((ones + 0.5) / (np.outer(Cu.sum(0), Cv.sum(0)) + 1.0), 1e-3, 1 - 1e-3)
            c1 = X.T @ Cu
            c0 = (1 - X).T @ Cu
            v = (c1 @ np.log(th) + c0 @ np.log(1 - th)).argmax(1)
            Cv = np.eye(nv)[v]
            ones = Cu.T @ X @ Cv
            th = np.clip((ones + 0.5) / (np.outer(Cu.sum(0), Cv.sum(0)) + 1.0), 1e-3, 1 - 1e-3)
            ll = float((ones * np.log(th)).sum() + ((np.outer(Cu.sum(0), Cv.sum(0)) - ones) * np.log(1 - th)).sum())
            if ll <= prev + 1e-9:
                break
            prev = ll
        if best is None or ll > best[0]:
            best = (ll, u.copy(), v.copy(), th.copy())
    return best


def crosscat_example():
    """The 6 x 6 example of Section 21.6.2: v = [1,1,2,3,3,3] and one row partition per column cluster; returns the
    matrix of cocluster labels 'k.l' (row cluster k, column cluster l) as in Figure 21.21b."""
    v = [1, 1, 2, 3, 3, 3]
    U = {1: [1, 1, 1, 2, 2, 2], 2: [1, 1, 2, 2, 2, 2], 3: [1, 1, 1, 1, 1, 2]}
    lab = [["%d.%d" % (U[v[j]][i], v[j]) for j in range(6)] for i in range(6)]
    return v, U, lab


# =========================================================================== figures
def _save(fig, name, out):
    return savefig(fig, CH, name, out)


def _cluster_scatter(ax, X, lab, s=4, alpha=0.8):
    for k in np.unique(lab):
        ax.scatter(X[lab == k, 0], X[lab == k, 1], s=s, c=PAL[int(k) % len(PAL)], alpha=alpha, lw=0)


def _voronoi_regions(ax, C, xlim, ylim, n=220):
    gx, gy = np.meshgrid(np.linspace(*xlim, n), np.linspace(*ylim, n))
    G = np.c_[gx.ravel(), gy.ravel()]
    z = sqdist(G, C).argmin(1).reshape(gx.shape)
    cm = matplotlib_cmap(len(C))
    ax.contourf(gx, gy, z, levels=np.arange(-0.5, len(C) + 0.5, 1), colors=cm, alpha=0.18)
    ax.contour(gx, gy, z, levels=np.arange(0.5, len(C) - 0.5, 1), colors="k", linewidths=0.6)


def matplotlib_cmap(K):
    return [PAL[k % len(PAL)] for k in range(K)]


def fig_21_1(out=None):
    """Figure 21.1: three clusters of labelled objects; the purity, Rand index and ARI computed from the table."""
    T = np.array([[5, 1, 0], [1, 4, 1], [2, 0, 3]])          # rows: clusters 1..3, columns: classes A, B, C
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.0), gridspec_kw={"width_ratios": [1.3, 1]})
    ax = axes[0]
    ax.set_xlim(0, 10)
    ax.set_ylim(0, 3.6)
    ax.axis("off")
    marks = ["o", "s", "^"]
    cols = [RED, BLUE, GREEN]
    rng = np.random.default_rng(1)
    for i in range(3):
        cx = 1.7 + 3.3 * i
        ax.add_patch(plt.Circle((cx, 1.7), 1.45, fill=False, ec="k", lw=1.0))
        pts = []
        for j in range(3):
            pts += [j] * T[i, j]
        ang = np.linspace(0, 2 * np.pi, len(pts), endpoint=False) + 0.4
        for a, j in zip(ang, pts):
            r = 0.75 if len(pts) > 1 else 0
            ax.scatter(cx + r * np.cos(a), 1.7 + r * np.sin(a), marker=marks[j], c=cols[j], s=55, zorder=3)
        ax.text(cx, 3.35, "cluster %d" % (i + 1), ha="center", fontsize=9)
    tp, fp, fn, tn = pair_counts(T)
    ax2 = axes[1]
    ax2.axis("off")
    txt = ("classes: circle A, square B, triangle C\n\npurity = %.2f\nTP = %d, FP = %d, FN = %d, TN = %d\nRand index = %.2f\nadjusted Rand = %.3f\nNMI = %.3f"
           % (purity(T), tp, fp, fn, tn, rand_index(T), adjusted_rand(T), nmi(T)))
    ax2.text(0.0, 0.95, txt, va="top", fontsize=9.5, transform=ax2.transAxes)
    print("  purity %.4f, TP/FP/FN/TN = %d/%d/%d/%d, Rand %.4f, ARI %.4f, NMI %.4f" % (purity(T), tp, fp, fn, tn, rand_index(T), adjusted_rand(T), nmi(T)))
    fig.tight_layout()
    return _save(fig, "fig21-1", out)


FIVE_PTS = np.array([[1.0, 3.0], [2.3, 4.6], [1.0, 2.0], [3.0, 1.0], [3.0, 0.0]])   # points 1..5 of Figure 21.2a


def fig_21_2(out=None):
    """Figure 21.2: five points, city-block distance, single link merges and the dendrogram."""
    from scipy.cluster.hierarchy import dendrogram
    D = pdist_matrix(FIVE_PTS, "cityblock")
    Z = hac(D, "single")
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 3.0))
    ax = axes[0]
    for i, p in enumerate(FIVE_PTS):
        ax.scatter(*p, c=PAL[0], s=36, zorder=3)
        ax.annotate(str(i + 1), p, textcoords="offset points", xytext=(6, 4), fontsize=10)
    ax.set_xlim(0.5, 4.0)
    ax.set_ylim(-0.5, 5.2)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    common.panel_label(ax, "a", "upper right")
    ax = axes[1]
    dendrogram(Z, ax=ax, labels=[str(i + 1) for i in range(5)], color_threshold=0, above_threshold_color="k")
    ax.set_ylabel("single-link distance")
    common.panel_label(ax, "b", "upper right")
    print("  merges:", [(int(a) + 1 if a < 5 else int(a), int(b) + 1 if b < 5 else int(b), float(h)) for a, b, h, _ in Z])
    fig.tight_layout()
    return _save(fig, "fig21-2", out)


def fig_21_3(out=None):
    """Figure 21.3: single, complete and average link distance between two groups of points."""
    rng = np.random.default_rng(4)
    G = rng.normal(0, 0.55, (6, 2)) + [0, 0]
    H = rng.normal(0, 0.55, (5, 2)) + [3.4, 0.7]
    d = np.sqrt(sqdist(G, H))
    fig, axes = plt.subplots(1, 3, figsize=(7.6, 2.6), sharex=True, sharey=True)
    for ax, kind, lab in zip(axes, ("single", "complete", "average"), "abc"):
        ax.scatter(*G.T, c=BLUE, s=26, zorder=3)
        ax.scatter(*H.T, c=RED, s=26, zorder=3)
        if kind in ("single", "complete"):
            idx = np.unravel_index(d.argmin() if kind == "single" else d.argmax(), d.shape)
            ax.plot([G[idx[0], 0], H[idx[1], 0]], [G[idx[0], 1], H[idx[1], 1]], "k-", lw=1.4)
            val = d.min() if kind == "single" else d.max()
        else:
            for a in range(len(G)):
                for b in range(len(H)):
                    ax.plot([G[a, 0], H[b, 0]], [G[a, 1], H[b, 1]], c=GREY, lw=0.5, alpha=0.6)
            val = d.mean()
        ax.set_title("%s link: %.2f" % (kind, val))
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
        common.panel_label(ax, lab, "upper left")
    fig.tight_layout()
    return _save(fig, "fig21-3", out)


def _yeast_hac():
    X, lab = yeast_standin()
    D = pdist_matrix(X)
    return X, lab, D, {m: hac(D, m) for m in ("single", "complete", "average")}


def fig_21_4(out=None):
    """Figure 21.4: single, complete and average linkage dendrograms of the (simulated) yeast data."""
    from scipy.cluster.hierarchy import dendrogram
    X, lab, D, Zs = _yeast_hac()
    fig, axes = plt.subplots(3, 1, figsize=(7.2, 6.6))
    for ax, m, l in zip(axes, ("single", "complete", "average"), "abc"):
        dendrogram(Zs[m], ax=ax, no_labels=True, color_threshold=0, above_threshold_color="k")
        ax.set_title("%s link" % m)
        common.panel_label(ax, l, "upper right")
        ax.set_ylabel("height")
    fig.tight_layout()
    return _save(fig, "fig21-4", out)


def fig_21_5(out=None):
    """Figure 21.5: the (simulated) yeast data as a heat map and as time series."""
    X, lab = yeast_standin()
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.6))
    ax = axes[0]
    im = ax.imshow(X, aspect="auto", cmap="RdBu_r", vmin=-2.5, vmax=2.5, interpolation="nearest")
    ax.set_xticks(range(7))
    ax.set_xticklabels(["%g" % t for t in YEAST_T], fontsize=8)
    ax.set_xlabel("time")
    ax.set_ylabel("genes")
    fig.colorbar(im, ax=ax, fraction=0.05, pad=0.03)
    common.panel_label(ax, "a", "upper left")
    ax = axes[1]
    ax.plot(YEAST_T, X.T, c=BLUE, lw=0.4, alpha=0.35)
    ax.set_xlabel("time")
    ax.set_ylabel("standardised expression")
    common.panel_label(ax, "b", "upper right")
    fig.tight_layout()
    return _save(fig, "fig21-5", out)


def _profile_grid(X, lab, K, ncol=4, title=None, centres=None, ylim=(-2.7, 2.7)):
    nrow = int(math.ceil(K / ncol))
    fig, axes = plt.subplots(nrow, ncol, figsize=(7.0, 1.55 * nrow), sharex=True, sharey=True, squeeze=False)
    for k in range(nrow * ncol):
        ax = axes[k // ncol, k % ncol]
        if k >= K:
            ax.axis("off")
            continue
        m = lab == k
        if centres is None:
            ax.plot(YEAST_T, X[m].T, c=BLUE, lw=0.6, alpha=0.7)
        else:
            ax.plot(YEAST_T, centres[k], c=RED, lw=1.8)
        ax.set_ylim(*ylim)
        ax.set_title("%d (n=%d)" % (k, m.sum()), fontsize=8, pad=2)
        ax.tick_params(labelsize=7)
    fig.tight_layout(h_pad=0.4, w_pad=0.3)
    return fig


def fig_21_6(out=None):
    """Figure 21.6: average-link tree of the yeast data: rows reordered by the tree, and the 16-cluster cut."""
    from scipy.cluster.hierarchy import leaves_list
    X, lab, D, Zs = _yeast_hac()
    Z = Zs["average"]
    order = leaves_list(Z)
    cl = cut_tree(Z, 16)
    fig, ax = plt.subplots(figsize=(3.6, 3.8))
    ax.imshow(X[order], aspect="auto", cmap="RdBu_r", vmin=-2.5, vmax=2.5, interpolation="nearest")
    ax.set_xticks(range(7))
    ax.set_xticklabels(["%g" % t for t in YEAST_T], fontsize=7)
    ax.set_ylabel("genes (tree order)")
    ax.set_xlabel("time")
    _save(fig, "fig21-6a", out)
    f2 = _profile_grid(X, cl, 16)
    print("  cluster sizes:", np.bincount(cl).tolist())
    return _save(f2, "fig21-6b", out)


def fig_21_7(out=None):
    """Figure 21.7: K-means with K = 5 from two random initialisations, Voronoi cells and distortions."""
    X, z = blobs5()
    runs = []
    for seed in range(40):
        C, lab, J = kmeans(X, 5, "random", np.random.default_rng(seed))
        runs.append((J, seed))
    runs.sort()
    best = runs[0]
    bad = [r for r in runs if r[0] > best[0] * 1.15]
    bad = bad[0] if bad else runs[-1]
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.4), sharey=True)
    xl, yl = (-8.5, 3.0), (0.2, 5.8)
    for ax, (J, seed), l in zip(axes, (best, bad), "ab"):
        C, lab, J2 = kmeans(X, 5, "random", np.random.default_rng(seed))
        _voronoi_regions(ax, C, xl, yl)
        ax.scatter(X[:, 0], X[:, 1], s=2.5, c="k", alpha=0.55, lw=0)
        ax.scatter(C[:, 0], C[:, 1], marker="x", s=70, c=RED, lw=2.2, zorder=4)
        ax.set_xlim(*xl)
        ax.set_ylim(*yl)
        ax.set_title("distortion = %.1f (seed %d)" % (J2, seed), fontsize=9)
        common.panel_label(ax, l, "upper left")
    print("  best %.2f (seed %d), poor %.2f (seed %d); distribution over 40 seeds: min %.1f median %.1f max %.1f"
          % (best[0], best[1], bad[0], bad[1], runs[0][0], runs[len(runs) // 2][0], runs[-1][0]))
    fig.tight_layout()
    return _save(fig, "fig21-7", out)


def fig_21_8(out=None):
    """Figure 21.8: K-means with K = 16 on the yeast data: clusters and centroids."""
    X, lab = yeast_standin()
    C, cl, J = kmeans(X, 16, "random", np.random.default_rng(2))
    print("  K=16 distortion %.1f, empty clusters: %d" % (J, int((np.bincount(cl, minlength=16) == 0).sum())))
    _save(_profile_grid(X, cl, 16), "fig21-8a", out)
    f2 = _profile_grid(X, cl, 16, centres=C)
    return _save(f2, "fig21-8b", out)


def fig_21_9(out=None):
    """Figure 21.9: vector quantisation of a 200 x 320 grey-scale image with codebooks of size 2 and 4."""
    img = sample_image()
    fig, axes = plt.subplots(1, 3, figsize=(7.6, 2.5))
    for ax, K, l in zip(axes[:2], (2, 4), "ab"):
        q, cb, J = vq_image(img, K)
        ax.imshow(q, cmap="gray", vmin=0, vmax=255)
        ax.set_title("VQ with K = %d clusters" % K, fontsize=9)
        print("  K=%d codebook %s, mean squared error %.1f, rate %d bits/pixel" % (K, np.round(np.sort(cb), 1).tolist(), J, int(math.log2(K))))
    axes[2].imshow(img, cmap="gray", vmin=0, vmax=255)
    axes[2].set_title("original", fontsize=9)
    for ax, l in zip(axes, "abc"):
        ax.axis("off")
    fig.tight_layout()
    return _save(fig, "fig21-9", out)


def fig_21_10(out=None):
    """Figure 21.10: batch and mini-batch K-means: distortion and training time against K."""
    rng = np.random.default_rng(10)
    X, _ = blobs5(10000, seed=10)
    Ks = list(range(2, 51, 4))
    Jb, Jm, tb, tm = [], [], [], []
    for K in Ks:
        t0 = time.time()
        C, lab, J = kmeans(X, K, "kmeans++", np.random.default_rng(K), max_iter=60)
        tb.append(time.time() - t0)
        Jb.append(J)
        t0 = time.time()
        C, lab, J = minibatch_kmeans(X, K, 256, 60, np.random.default_rng(K))
        tm.append(time.time() - t0)
        Jm.append(J)
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 2.8))
    axes[0].plot(Ks, Jb, "-o", c=BLUE, ms=3, label="K-means")
    axes[0].plot(Ks, Jm, "-s", c=RED, ms=3, label="mini-batch K-means")
    axes[0].set_xlabel("K")
    axes[0].set_ylabel("distortion")
    axes[0].legend()
    axes[1].plot(Ks, tb, "-o", c=BLUE, ms=3)
    axes[1].plot(Ks, tm, "-s", c=RED, ms=3)
    axes[1].set_xlabel("K")
    axes[1].set_ylabel("training time (s)")
    print("  K=50: distortion %.0f vs %.0f (mini-batch), time %.2f s vs %.2f s" % (Jb[-1], Jm[-1], tb[-1], tm[-1]))
    fig.tight_layout()
    return _save(fig, "fig21-10", out)


def k_selection_curves(X, Ks=range(2, 9), seed=0):
    rng = np.random.default_rng(seed)
    idx = rng.permutation(len(X))
    tr, va = X[idx[: len(X) // 2]], X[idx[len(X) // 2:]]
    dist_val, bic, sil = [], [], []
    for K in Ks:
        C, lab, J = kmeans_best(tr, K, 10, seed)
        dist_val.append(distortion(va, C))
        g = gmm_best(X, K, "full", 10, seed)
        bic.append(g["bic"])
        Cf, labf, Jf = kmeans_best(X, K, 10, seed)
        sil.append(silhouette(X, labf))
    return list(Ks), dist_val, bic, sil


def fig_21_11(out=None):
    """Figure 21.11: validation distortion, BIC of a Gaussian mixture and silhouette score against K."""
    X, _ = blobs5()
    Ks, dv, bic, sil = k_selection_curves(X)
    fig, axes = plt.subplots(1, 3, figsize=(7.6, 2.6))
    axes[0].plot(Ks, dv, "-o", c=BLUE, ms=3)
    axes[0].set_ylabel("distortion (validation set)")
    axes[1].plot(Ks, bic, "-o", c=RED, ms=3)
    axes[1].set_ylabel("BIC")
    axes[2].plot(Ks, sil, "-o", c=GREEN, ms=3)
    axes[2].set_ylabel("silhouette score")
    for ax, l in zip(axes, "abc"):
        ax.set_xlabel("K")
        common.panel_label(ax, l, "upper right")
    print("  validation distortion:", np.round(dv, 1).tolist(), "\n  BIC:", np.round(bic, 1).tolist(), "argmin K =", Ks[int(np.argmin(bic))],
          "\n  silhouette:", np.round(sil, 3).tolist(), "argmax K =", Ks[int(np.argmax(sil))])
    fig.tight_layout()
    return _save(fig, "fig21-11", out)


def fig_21_12(out=None):
    """Figure 21.12: Voronoi diagrams of K-means for K = 3, 4, 5, 6."""
    X, _ = blobs5()
    fig, axes = plt.subplots(2, 2, figsize=(6.6, 5.2), sharex=True, sharey=True)
    xl, yl = (-8.5, 3.0), (0.2, 5.8)
    for ax, K, l in zip(axes.ravel(), (3, 4, 5, 6), "abcd"):
        C, lab, J = kmeans_best(X, K, 10)
        _voronoi_regions(ax, C, xl, yl)
        ax.scatter(X[:, 0], X[:, 1], s=2, c="k", alpha=0.5, lw=0)
        ax.scatter(C[:, 0], C[:, 1], marker="x", s=60, c=RED, lw=2, zorder=4)
        ax.set_xlim(*xl)
        ax.set_ylim(*yl)
        ax.set_title("K = %d" % K, fontsize=9)
        common.panel_label(ax, l, "upper left")
    fig.tight_layout()
    return _save(fig, "fig21-12", out)


def fig_21_13(out=None):
    """Figure 21.13: silhouette diagrams for K = 3, 4, 5, 6."""
    X, _ = blobs5()
    fig, axes = plt.subplots(2, 2, figsize=(7.0, 5.4))
    for ax, K, l in zip(axes.ravel(), (3, 4, 5, 6), "abcd"):
        C, lab, J = kmeans_best(X, K, 10)
        sc = silhouette(X, lab, per_point=True)
        y0 = 0
        for k in range(K):
            v = np.sort(sc[lab == k])
            ax.fill_betweenx(np.arange(y0, y0 + len(v)), 0, v, color=PAL[k], alpha=0.85, lw=0)
            ax.text(-0.17, y0 + len(v) / 2, str(k), fontsize=8, va="center")
            y0 += len(v) + 40
        ax.axvline(sc.mean(), c="k", ls=":", lw=1.2)
        ax.set_xlim(-0.2, 1.0)
        ax.set_title("K = %d, score = %.2f" % (K, sc.mean()), fontsize=9)
        ax.set_yticks([])
        ax.set_xlabel("silhouette coefficient")
        common.panel_label(ax, l, "lower right")
    fig.tight_layout()
    return _save(fig, "fig21-13", out)


def _gmm_density_grid(g, xl, yl, n=200):
    gx, gy = np.meshgrid(np.linspace(*xl, n), np.linspace(*yl, n))
    G = np.c_[gx.ravel(), gy.ravel()]
    lp = special.logsumexp(gmm_loglik_components(G, g["w"], g["mu"], g["Sig"]), axis=1)
    return gx, gy, np.exp(lp).reshape(gx.shape)


def fig_21_14(out=None):
    """Figure 21.14: a K = 5 Gaussian mixture with full, tied, diagonal and spherical covariances."""
    X, z = gmm2d_data()
    xl, yl = (-9.5, 7.0), (-4.6, 4.8)
    fig, axes = plt.subplots(4, 2, figsize=(6.8, 11.4))
    info = {}
    for r, cov in enumerate(("full", "tied", "diag", "spherical")):
        g = gmm_best(X, 5, cov, 8, seed=1)
        info[cov] = (g["ll"], g["bic"])
        gx, gy, dens = _gmm_density_grid(g, xl, yl)
        ax = axes[r, 0]
        ax.contourf(gx, gy, dens, levels=12, cmap="Blues")
        ax.scatter(X[:, 0], X[:, 1], s=2, c="k", alpha=0.4, lw=0)
        ax.set_xlim(*xl)
        ax.set_ylim(*yl)
        ax.set_title("%s: marginal density" % cov, fontsize=9)
        common.panel_label(ax, "abcdefgh"[2 * r], "upper left")
        ax = axes[r, 1]
        hard = g["resp"].argmax(1)
        _cluster_scatter(ax, X, hard, s=4)
        for k in range(5):
            ex, ey = common.ellipse_xy(g["mu"][k], g["Sig"][k], 2.0)
            ax.plot(ex, ey, c="k", lw=1.0)
        ax.set_xlim(*xl)
        ax.set_ylim(*yl)
        ax.set_title("%s: hard assignment" % cov, fontsize=9)
        common.panel_label(ax, "abcdefgh"[2 * r + 1], "upper left")
    print("  log-likelihood and BIC:", {k: (round(v[0], 1), round(v[1], 1)) for k, v in info.items()})
    fig.tight_layout()
    return _save(fig, "fig21-14", out)


def fig_21_15(out=None):
    """Figure 21.15: the 1-D data with a kernel density estimate."""
    y = data_1d()
    fig, ax = plt.subplots(figsize=(4.8, 2.6))
    ax.hist(y, bins=30, density=True, color="#bbbbbb", ec="white")
    h = 1.06 * y.std() * len(y) ** (-0.2) * 0.6
    g = np.linspace(40, 75, 400)
    ax.plot(g, np.exp(-0.5 * ((g[:, None] - y[None]) / h) ** 2).sum(1) / (len(y) * h * math.sqrt(2 * math.pi)), c="k", lw=1.5, label="KDE")
    ax.plot(y, np.full_like(y, -0.003), "|", c="k", ms=6)
    ax.set_xlabel("x")
    ax.set_yticks([])
    ax.legend()
    fig.tight_layout()
    return _save(fig, "fig21-15", out)


def _run_chains(y, K, n_chain=4, n_iter=1500, burn=500):
    P, M, S = [], [], []
    for c in range(n_chain):
        rng = np.random.default_rng(100 + c)
        init = None
        if K == 2:
            init = [47.0, 57.0] if c % 2 == 0 else [57.0, 47.0]
        p, m, s = gibbs_gmm1d(y, K, n_iter, burn, seed=100 + c, init_mu=init)
        P.append(p), M.append(m), S.append(s)
    return np.vstack(P), np.vstack(M), np.vstack(S)


def fig_21_16(out=None):
    """Figure 21.16: label switching: posterior marginals of the two means, unconstrained and ordered."""
    y = data_1d()
    P, M, S = _run_chains(y, 2)
    Ps, Ms, Ss = sort_draws(P, M, S)
    fig, axes = plt.subplots(2, 2, figsize=(7.2, 4.6))
    for j in range(2):
        axes[0, j].hist(M[:, j], bins=60, density=True, color=PAL[j], alpha=0.85)
        axes[0, j].set_xlabel("means[%d]" % j)
        axes[1, j].hist(Ms[:, j], bins=60, density=True, color=PAL[j], alpha=0.85)
        axes[1, j].set_xlabel("means[%d]" % j)
    axes[0, 0].set_title("(a) unconstrained model: symmetric posterior", fontsize=9, loc="left")
    axes[1, 0].set_title("(b) ordered model, $\\mu_0 < \\mu_1$", fontsize=9, loc="left")
    print("  unconstrained: share of draws with mu0 > mu1 = %.2f; ordered means %.2f, %.2f" % ((M[:, 0] > M[:, 1]).mean(), Ms[:, 0].mean(), Ms[:, 1].mean()))
    fig.tight_layout()
    return _save(fig, "fig21-16", out)


def _fit_K_cached(y, Ks=(3, 4, 5, 6)):
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch21_gibbs_K.npz")
    if os.path.exists(path):
        z = np.load(path)
        return {K: (z["P%d" % K], z["M%d" % K], z["S%d" % K]) for K in Ks}
    res = {}
    arrs = {}
    for K in Ks:
        P, M, S = _run_chains(y, K, 4, 1500, 500)
        Ps, Ms, Ss = sort_draws(P, M, S)
        res[K] = (Ps, Ms, Ss)
        arrs.update({"P%d" % K: Ps, "M%d" % K: Ms, "S%d" % K: Ss})
    np.savez(path, **arrs)
    return res


def fig_21_17(out=None):
    """Figure 21.17: Gaussian mixtures with K = 3..6 components fitted by Gibbs sampling (ordered means)."""
    y = data_1d()
    fits = _fit_K_cached(y)
    g = np.linspace(40, 75, 400)
    h = 1.06 * y.std() * len(y) ** (-0.2) * 0.6
    kde = np.exp(-0.5 * ((g[:, None] - y[None]) / h) ** 2).sum(1) / (len(y) * h * math.sqrt(2 * math.pi))
    fig, axes = plt.subplots(1, 4, figsize=(7.8, 2.3), sharey=True)
    rng = np.random.default_rng(0)
    for ax, K in zip(axes, (3, 4, 5, 6)):
        P, M, S = fits[K]
        dens = lambda p, m, s2: (p[None] * np.exp(-0.5 * (g[:, None] - m[None]) ** 2 / s2[None]) / np.sqrt(2 * np.pi * s2[None])).sum(1)
        for i in rng.choice(len(P), 25, replace=False):
            ax.plot(g, dens(P[i], M[i], S[i]), c=BLUE, lw=0.5, alpha=0.2)
        ax.plot(g, np.mean([dens(P[i], M[i], S[i]) for i in range(0, len(P), 10)], axis=0), c=BLUE, lw=1.6)
        pm, mm, sm = P.mean(0), M.mean(0), S.mean(0)
        for k in range(K):
            ax.plot(g, pm[k] * np.exp(-0.5 * (g - mm[k]) ** 2 / sm[k]) / np.sqrt(2 * np.pi * sm[k]), c=BLUE, ls=":", lw=1.0)
        ax.plot(g, kde, c="k", lw=1.2)
        ax.set_title("K = %d" % K, fontsize=9)
        ax.set_xlabel("x")
    axes[0].set_yticks([])
    fig.tight_layout()
    return _save(fig, "fig21-17", out)


def fig_21_18(out=None):
    """Figure 21.18: WAIC (log-score scale) of the K = 3..6 mixtures."""
    y = data_1d()
    fits = _fit_K_cached(y)
    Ks = (3, 4, 5, 6)
    W = {K: waic(y, *fits[K]) for K in Ks}
    fig, ax = plt.subplots(figsize=(4.6, 2.8))
    best = max(W[K]["elpd"] for K in Ks)
    for i, K in enumerate(Ks):
        ax.errorbar(W[K]["elpd"], i, xerr=W[K]["se"], fmt="o", mfc="white", c="k", capsize=3)
        ax.plot(W[K]["lppd"], i, "o", c="k", ms=4)
    ax.axvline(best, c="k", ls="--", lw=0.8)
    ax.set_yticks(range(4))
    ax.set_yticklabels([str(K) for K in Ks])
    ax.set_ylabel("K")
    ax.set_xlabel("log score (WAIC); filled: in-sample lppd")
    print("  WAIC:", {K: (round(W[K]["elpd"], 1), round(W[K]["se"], 1), round(W[K]["p"], 1), round(W[K]["lppd"], 1)) for K in Ks})
    fig.tight_layout()
    return _save(fig, "fig21-18", out)


def fig_21_19(out=None):
    """Figure 21.19: K-means and spectral clustering of two concentric rings."""
    X, z = rings()
    Ck, lk, Jk = kmeans_best(X, 2, 10)
    ls, U, ev = spectral_cluster(X, 2, 0.5)
    Tk, Ts = contingency(lk, z), contingency(ls, z)
    fig, axes = plt.subplots(1, 2, figsize=(6.8, 3.3), sharey=True)
    for ax, lab, t, l in zip(axes, (lk, ls), ("k-means clustering", "spectral clustering"), "ab"):
        _cluster_scatter(ax, X, lab, s=9, alpha=0.9)
        ax.set_aspect("equal")
        ax.set_title(t, fontsize=9)
        ax.set_xlabel("x")
        common.panel_label(ax, l, "upper left")
    axes[0].set_ylabel("y")
    print("  ARI: k-means %.3f, spectral %.3f" % (adjusted_rand(Tk), adjusted_rand(Ts)))
    fig.tight_layout()
    return _save(fig, "fig21-19", out)


def fig_21_20(out=None):
    """Figure 21.20: basic biclustering of a binary matrix (simulated animals-by-features stand-in)."""
    X, u, v, th = block_data(50, 60, 4, 3, seed=5)
    rng = np.random.default_rng(0)
    pr, pc = rng.permutation(50), rng.permutation(60)
    Xs = X[np.ix_(pr, pc)]
    ll, uh, vh, thh = bicluster_fit(Xs, 4, 3, seed=1, n_init=20)
    ro, co = np.lexsort((np.arange(50), uh)), np.lexsort((np.arange(60), vh))
    fig, axes = plt.subplots(1, 3, figsize=(7.6, 3.1))
    axes[0].imshow(1 - Xs, cmap="gray", aspect="auto", interpolation="nearest")
    axes[0].set_title("data, rows and columns shuffled", fontsize=9)
    axes[1].imshow(1 - X[np.ix_(np.argsort(u, kind="stable"), np.argsort(v, kind="stable"))], cmap="gray", aspect="auto", interpolation="nearest")
    axes[1].set_title("sorted by the true clusters", fontsize=9)
    axes[2].imshow(1 - Xs[np.ix_(ro, co)], cmap="gray", aspect="auto", interpolation="nearest")
    axes[2].set_title("sorted by the fitted clusters", fontsize=9)
    bu = np.cumsum(np.bincount(uh, minlength=4))[:-1] - 0.5
    bv = np.cumsum(np.bincount(vh, minlength=3))[:-1] - 0.5
    for b in bu:
        axes[2].axhline(b, c=RED, lw=0.8)
    for b in bv:
        axes[2].axvline(b, c=RED, lw=0.8)
    for ax, l in zip(axes, "abc"):
        ax.set_xticks([])
        ax.set_yticks([])
    ari_r = adjusted_rand(contingency(uh, u[pr]))
    ari_c = adjusted_rand(contingency(vh, v[pc]))
    print("  fitted ll %.1f; ARI rows %.3f, columns %.3f" % (ll, ari_r, ari_c))
    fig.tight_layout()
    return _save(fig, "fig21-20", out)


def fig_21_21(out=None):
    """Figure 21.21: coclustering and the nested partition (multi-clustering) model on a 6 x 6 example."""
    v = np.array([1, 1, 2, 3, 3, 3])
    u_basic = np.array([1, 1, 1, 2, 2, 2])
    labs_a = [["%d.%d" % (u_basic[i], v[j]) for j in range(6)] for i in range(6)]
    _, _, labs_b = crosscat_example()
    fig, axes = plt.subplots(1, 2, figsize=(6.4, 3.1))
    tint = {1: "#cfe0ff", 2: "#ffd9cf", 3: "#d9f2d0"}
    for ax, lab, l, ttl in zip(axes, (labs_a, labs_b), "ab", ("one partition of the rows", "rows partitioned per column group")):
        for i in range(6):
            for j in range(6):
                k = int(lab[i][j].split(".")[0])
                ax.add_patch(plt.Rectangle((j, 5 - i), 1, 1, fc=tint[k] if lab is labs_b else tint[k], ec="#888888", lw=0.5))
                ax.text(j + 0.5, 5 - i + 0.5, lab[i][j], ha="center", va="center", fontsize=8)
        for b in (2, 3):
            ax.axvline(b, c="k", lw=1.8)
        ax.set_xlim(0, 6)
        ax.set_ylim(0, 6)
        ax.set_aspect("equal")
        ax.axis("off")
        ax.set_title("(%s) %s" % (l, ttl), fontsize=9)
    fig.tight_layout()
    return _save(fig, "fig21-21", out)


# ----------------------------------------------------------------------- supplementary figures
def fig_21_s1(out=None):
    """Supplementary: single-link merge heights equal the sorted minimum-spanning-tree edge weights."""
    X, lab = yeast_standin()
    D = pdist_matrix(X)
    Z = hac(D, "single")
    mst = [e[2] for e in mst_prim(D)]
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    ax.plot(mst, c=BLUE, lw=3, label="sorted MST edge weights")
    ax.plot(Z[:, 2], c=RED, lw=1.2, ls="--", label="single-link merge heights")
    ax.set_xlabel("merge number")
    ax.set_ylabel("height")
    ax.legend()
    print("  max |merge height - MST weight| = %.2e" % np.abs(Z[:, 2] - np.array(mst)).max())
    fig.tight_layout()
    return _save(fig, "fig21-s1", out)


def fig_21_s2(out=None):
    """Supplementary: final distortion over 300 seeds for random seeding and for K-means++."""
    X, z = blobs5(1000, seed=7)
    res = {}
    for init in ("random", "kmeans++"):
        res[init] = np.array([kmeans(X, 5, init, np.random.default_rng(s))[2] for s in range(300)])
    fig, ax = plt.subplots(figsize=(5.2, 3.0))
    lo, hi = min(r.min() for r in res.values()), max(r.max() for r in res.values())
    bins = np.linspace(lo, hi, 40)
    ax.hist(res["random"], bins=bins, color=RED, alpha=0.6, label="random points")
    ax.hist(res["kmeans++"], bins=bins, color=BLUE, alpha=0.6, label="K-means++")
    ax.set_xlabel("final distortion")
    ax.set_ylabel("number of seeds (of 300)")
    ax.legend()
    print("  mean distortion: random %.1f, kmeans++ %.1f; share within 2%% of the best: %.2f vs %.2f"
          % (res["random"].mean(), res["kmeans++"].mean(), (res["random"] < 1.02 * lo).mean(), (res["kmeans++"] < 1.02 * lo).mean()))
    fig.tight_layout()
    return _save(fig, "fig21-s2", out)


def fig_21_s3(out=None):
    """Supplementary: the Laplacian spectrum: the number of zero eigenvalues is the number of connected pieces."""
    rng = np.random.default_rng(2)
    X = np.vstack([rng.normal(c, 0.35, (40, 2)) for c in ([0, 0], [4, 0], [2, 3.5])])
    fig, axes = plt.subplots(1, 3, figsize=(7.6, 2.6))
    for ax, sig, l in zip(axes, (0.5, 1.0, 2.2), "abc"):
        W = gaussian_affinity(X, sig)
        np.fill_diagonal(W, 0)
        ev = spectral_embed(W, 3, "sym")[1]
        ax.plot(range(1, 11), ev[:10], "o-", c=BLUE, ms=3)
        ax.set_title("$\\sigma$ = %.1f" % sig, fontsize=9)
        ax.set_xlabel("index")
        common.panel_label(ax, l, "lower right")
    axes[0].set_ylabel("eigenvalue of $L_{sym}$")
    fig.tight_layout()
    return _save(fig, "fig21-s3", out)


def fig_21_s4(out=None):
    """Supplementary: the Gaussian-mixture likelihood is unbounded: one component collapses on a data point."""
    X, z = gmm2d_data(200)
    best = gmm_best(X, 3, "full", 3, 0)
    sig = np.logspace(-0.5, -4, 30)
    lls = []
    for s in sig:
        w, mu, Sig = best["w"].copy(), best["mu"].copy(), best["Sig"].copy()
        mu[0] = X[0]
        Sig[0] = (s ** 2) * np.eye(2)
        lls.append(float(special.logsumexp(gmm_loglik_components(X, w, mu, Sig), axis=1).sum()))
    fig, ax = plt.subplots(figsize=(4.6, 2.9))
    ax.semilogx(sig, lls, c=RED)
    ax.axhline(best["ll"], c="k", ls="--", lw=0.8, label="EM solution")
    ax.set_xlabel("$\\sigma$ of the collapsing component")
    ax.set_ylabel("log-likelihood")
    ax.invert_xaxis()
    ax.legend()
    fig.tight_layout()
    return _save(fig, "fig21-s4", out)


FIGURES = {"21.1": fig_21_1, "21.2": fig_21_2, "21.3": fig_21_3, "21.4": fig_21_4, "21.5": fig_21_5, "21.6": fig_21_6,
           "21.7": fig_21_7, "21.8": fig_21_8, "21.9": fig_21_9, "21.10": fig_21_10, "21.11": fig_21_11,
           "21.12": fig_21_12, "21.13": fig_21_13, "21.14": fig_21_14, "21.15": fig_21_15, "21.16": fig_21_16,
           "21.17": fig_21_17, "21.18": fig_21_18, "21.19": fig_21_19, "21.20": fig_21_20, "21.21": fig_21_21,
           "21.S1": fig_21_s1, "21.S2": fig_21_s2, "21.S3": fig_21_s3, "21.S4": fig_21_s4}


# =========================================================================== data for the browser demonstrations
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)

    def dump(name, d):
        with open(os.path.join(DATA_OUT, name), "w") as f:
            json.dump(d, f, separators=(",", ":"))
    # ---- K-means and choice of K (the 2000-point five-blob data)
    X, z = blobs5()
    X = np.round(X, 3)
    ref = {"kmeans": {}, "bic": {}, "sil": {}}
    for K in range(1, 11):
        C, lab, J = kmeans_best(X, K, 30, 0)
        ref["kmeans"][str(K)] = round(J, 4)
        ref["bic"][str(K)] = round(gmm_best(X, K, "full", 10, 0)["bic"], 3)
        if K >= 2:
            ref["sil"][str(K)] = round(silhouette(X, lab), 6)
    # Lloyd from fixed starting centres (the same trace must come out of the browser)
    starts = {"bad": X[[0, 1, 2, 3, 4]].tolist()}
    idx_bad = None
    best_bad = None
    for s in range(200):
        rng = np.random.default_rng(s)
        C0 = X[rng.choice(len(X), 5, replace=False)]
        C, lab, J = kmeans(X, 5, C0.copy())
        if best_bad is None or J > best_bad[0]:
            best_bad = (J, s, C0.copy())
    C0 = best_bad[2]
    C, lab, J, tr = kmeans(X, 5, C0.copy(), return_trace=True)
    ref["fixed_start"] = dict(centres=_r(C0, 4), trace=_r(tr, 4), final=round(J, 4))
    C0b = kmeanspp(X, 5, np.random.default_rng(3))
    C, lab, J, tr = kmeans(X, 5, C0b.copy(), return_trace=True)
    ref["pp_start"] = dict(centres=_r(C0b, 4), trace=_r(tr, 4), final=round(J, 4))
    dump("ch21-blobs.json", dict(X=X.tolist(), z=z.tolist(), ref=ref))
    # ---- hierarchical clustering demo data
    out = {}
    rng = np.random.default_rng(31)
    B = np.vstack([rng.normal(c, 0.55, (20, 2)) for c in ([0, 0], [3.2, 0.3], [1.5, 2.8])])
    M, mz = moons(80, 0.07, 3)
    Y, yl = yeast_standin()
    Rg = rings(90, 19)[0]
    sets = {"blobs": B, "moons": M, "rings": Rg, "yeast": Y}
    for name, A in sets.items():
        A = np.round(A, 3)
        D = pdist_matrix(A)
        entry = dict(X=A.tolist(), ref={})
        for m in ("single", "complete", "average"):
            Z = hac(D, m)
            entry["ref"][m] = dict(heights=_r(Z[:, 2], 6), cut3=cut_tree(Z, 3).tolist() if name != "yeast" else None,
                                   sizes3=np.bincount(cut_tree(Z, 3)).tolist())
        out[name] = entry
    out["yeast"]["labels"] = yl.tolist()
    dump("ch21-hac.json", out)
    print("wrote ch21-*.json")


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
