"""Chapter 12. Unsupervised Learning: the figures.

Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie and
Tibshirani (2021), An Introduction to Statistical Learning with Applications in R, 2nd edition,
and James, Witten, Hastie, Tibshirani and Taylor (2023), the Python edition, Chapter 12.

Reproduces all 19 figures of the chapter (Figure 12.2 has two panels, drawn as one figure):
  12.1   biplot of the first two principal components of the standardised USArrests data
  12.2   ninety simulated points in three dimensions, the best-fitting plane and the projection
  12.3   scree plot and cumulative proportion of variance explained (USArrests)
  12.4   biplots of USArrests with and without scaling the variables
  12.5   matrix completion (Algorithm 12.1, M = 1): imputed against true values of 20 entries
  12.6   100 repetitions: imputed against true first principal component scores and singular values
  12.7   K-means with K = 2, 3, 4 on 150 simulated points
  12.8   the steps of Algorithm 12.2 on the same data
  12.9   six runs of K-means from random starts, with the objective (12.17)
  12.10  45 simulated points from three classes
  12.11  complete-linkage dendrogram of those points, cut into two and three clusters
  12.12  a dendrogram of nine points next to the points themselves
  12.13  the first fusions of Algorithm 12.3 on the nine points
  12.14  average, complete and single linkage on the same data
  12.15  three profiles: Euclidean against correlation-based dissimilarity
  12.16  eight shoppers: socks and computers, raw, scaled and in dollars
  12.17  NCI60: the first three principal component scores, coloured by cancer type
  12.18  NCI60: proportion of variance explained and its cumulative sum
  12.19  NCI60: complete, average and single linkage dendrograms
plus two figures for the exercises (ex12-2: the dendrograms of Exercise 2; ex12-3: Exercise 3).
None is skipped. The simulated data of Figures 12.2, 12.7-12.15 are not published with the book;
they are simulated here from documented settings (seeds below), so the pictures have the book's
shapes but not its exact coordinates or objective values. Figure 12.16 is an invented example in
the book as well; the eight shoppers here are our own numbers. Table 12.1 is printed by 'T12.1'.

Data: USArrests ships with R (datasets package) and NCI60 with the R package ISLR2; neither is one
of the book's CSV files. The first call exports them once with Rscript to cache/ch12-USArrests.csv
and cache/ch01-NCI60.csv (the file the Chapter 1 code also uses); later calls read those files.

Conventions. Principal components are computed from the singular value decomposition of the
centred (and, if asked, standardised) data matrix, with R's divisor n - 1 for standard deviations
and variances, as prcomp() does. A loading vector is only defined up to sign (Section 12.2.4); we
flip each so that its loadings sum to a positive number, which gives the orientation of Table 12.1
and Figure 12.1 (prcomp() and scikit-learn return other signs). The K-means objective is (12.17),
which is twice the "total within-cluster sum of squares" that R's kmeans() and scikit-learn's
KMeans report (Result 12.6 in the notes).

It also writes the JSON files of the three demonstrations:
  ../data/ch12-usarrests.json   USArrests, the R lab's and the Python lab's missing entries
  ../data/ch12-clusters.json    data sets for K-means against hierarchical clustering

Run: python3 ch12_unsupervised_learning.py              (all figures and the JSON files, about 20 s)
     python3 ch12_unsupervised_learning.py --fig 12.5   (one figure)
The code is my own.
"""
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import json
import subprocess
import warnings

import numpy as np
import pandas as pd
from scipy.cluster import hierarchy as sch
from scipy.spatial.distance import pdist, squareform

from common import savefig, run, plt, panel_grid, HERE, BLUE, RED, GREEN, ORANGE, PURPLE, GREY, CYAN, MAGENTA

warnings.filterwarnings("ignore")
CH = 12
CACHE_DIR = os.path.join(HERE, "cache")
US_CSV = os.path.join(CACHE_DIR, "ch12-USArrests.csv")
NCI_CSV = os.path.join(CACHE_DIR, "ch01-NCI60.csv")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
RSCRIPT = os.environ.get("RSCRIPT", "/usr/local/bin/Rscript")

STATE_ABB = ["AL", "AK", "AZ", "AR", "CA", "CO", "CT", "DE", "FL", "GA", "HI", "ID", "IL", "IN", "IA", "KS",
             "KY", "LA", "ME", "MD", "MA", "MI", "MN", "MS", "MO", "MT", "NE", "NV", "NH", "NJ", "NM", "NY",
             "NC", "ND", "OH", "OK", "OR", "PA", "RI", "SC", "SD", "TN", "TX", "UT", "VT", "VA", "WA", "WV",
             "WI", "WY"]
# The missing entries of the R lab (Section 12.5.2): set.seed(15); ina <- sample(seq(50), 20);
# inb <- sample(1:4, 20, replace = TRUE). Printed by ch12_lab.R; 0-based here.
R_INA = np.array([37, 47, 42, 34, 38, 5, 25, 12, 20, 46, 1, 43, 50, 23, 2, 44, 10, 26, 21, 32]) - 1
R_INB = np.array([3, 1, 2, 4, 2, 2, 3, 3, 4, 3, 2, 1, 3, 1, 3, 3, 4, 2, 2, 3]) - 1
VAR_COLOURS = [ORANGE, CYAN, GREEN, "#444444"]   # Murder, Assault, UrbanPop, Rape (as in Figure 12.5)
K_COLOURS = ["#e69f00", "#009e73", "#cc79a7", "#56b4e9", "#d55e00", "#0072b2"]


# =========================================================================== data
def _rexport(code):
    os.makedirs(CACHE_DIR, exist_ok=True)
    subprocess.run([RSCRIPT, "-e", code], check=True, capture_output=True)


def usarrests():
    """USArrests (R's datasets package): 50 states x Murder, Assault, UrbanPop, Rape."""
    if not os.path.exists(US_CSV):
        _rexport('write.csv(USArrests, "%s")' % US_CSV)
    return pd.read_csv(US_CSV, index_col=0)


def nci60():
    """NCI60 (R package ISLR2): (X, labels), X the 64 x 6830 expression matrix."""
    if not os.path.exists(NCI_CSV):
        _rexport('library(ISLR2); d <- data.frame(label = NCI60$labs, NCI60$data, check.names = FALSE); '
                 'write.csv(d, "%s", row.names = FALSE)' % NCI_CSV)
    D = pd.read_csv(NCI_CSV)
    return D.iloc[:, 1:].to_numpy(float), D["label"].to_numpy(str)


def standardise(X, ddof=1):
    """Centre each column and divide by its standard deviation (R's scale() uses ddof = 1)."""
    X = np.asarray(X, float)
    return (X - X.mean(0)) / X.std(0, ddof=ddof)


# =========================================================================== principal components
def pca(X, scale=True, orient=True):
    """Principal components of the n x p matrix X by the SVD of the centred (standardised) matrix.

    Returns a dict with loadings V (p x r, columns phi_m), scores Z = X_c V (n x r), the singular
    values d, sdev = d / sqrt(n - 1) (prcomp's sdev), the variances sdev^2 and the PVE (12.10).
    With orient=True each loading vector is flipped so that its entries sum to a positive number."""
    X = np.asarray(X, float)
    n = X.shape[0]
    Xc = standardise(X) if scale else X - X.mean(0)
    U, d, Vt = np.linalg.svd(Xc, full_matrices=False)
    r = min(n - 1, X.shape[1])
    U, d, V = U[:, :r], d[:r], Vt[:r].T
    if orient:
        s = np.where(V.sum(0) < 0, -1.0, 1.0)
        U, V = U * s, V * s
    Z = U * d
    var = d ** 2 / (n - 1)
    return {"V": V, "Z": Z, "d": d, "sdev": np.sqrt(var), "var": var, "pve": var / var.sum(), "Xc": Xc}


def pve_direct(Xc, V):
    """(12.10): sum_i (sum_j phi_jm x_ij)^2 / sum_ij x_ij^2 for each loading vector phi_m."""
    return ((Xc @ V) ** 2).sum(0) / (Xc ** 2).sum()


def low_rank(X, M=1):
    """The best rank-M approximation sum_{m <= M} d_m u_m v_m^T of X (Eckart-Young), by the SVD."""
    U, d, Vt = np.linalg.svd(X, full_matrices=False)
    return (U[:, :M] * d[:M]) @ Vt[:M]


def hard_impute(Xna, M=1, thresh=1e-7, start="R", maxit=10000):
    """Algorithm 12.1 (iterative SVD, 'hard impute') with the stopping rule of the labs.

    Xna has np.nan in the missing entries. Step 1 fills them with the column means of the observed
    entries; step 2 alternates (a) Xapp = best rank-M approximation of Xhat, (b) Xhat[miss] = Xapp[miss],
    (c) mss = mean squared error of Xapp on the observed entries, the objective (12.14) divided by |O|,
    until the relative decrease (mss_old - mss) / mss0 falls below thresh, mss0 being the mean square
    of the observed entries. start='R' starts mss_old at the objective of the column-mean fit (the R
    lab); start='py' at mss0 (the Python lab). Returns Xhat, Xapp and the list of (mss, rel_err)."""
    Xna = np.asarray(Xna, float)
    miss = np.isnan(Xna)
    xbar = np.nanmean(Xna, 0)
    Xhat = np.where(miss, xbar, Xna)
    mss0 = np.mean(Xna[~miss] ** 2)
    mssold = np.mean(((Xna - xbar)[~miss]) ** 2) if start == "R" else np.mean(Xhat[~miss] ** 2)
    rel_err, hist, Xapp = 1.0, [], None
    while rel_err > thresh and len(hist) < maxit:
        Xapp = low_rank(Xhat, M)
        Xhat[miss] = Xapp[miss]
        mss = np.mean(((Xna - Xapp)[~miss]) ** 2)
        rel_err = (mssold - mss) / mss0
        mssold = mss
        hist.append((mss, rel_err))
    return Xhat, Xapp, hist


def us_missing_R():
    """The R lab's matrix: scale(USArrests) with the 20 entries of R_INA, R_INB set to NaN."""
    X = standardise(usarrests().to_numpy(float))
    Xna = X.copy()
    Xna[R_INA, R_INB] = np.nan
    return X, Xna


# =========================================================================== K-means
def centroids(X, lab, K):
    return np.array([X[lab == k].mean(0) if np.any(lab == k) else np.full(X.shape[1], np.nan) for k in range(K)])


def kmeans_objective(X, lab):
    """(12.17): sum_k (1/|C_k|) sum_{i,i' in C_k} ||x_i - x_i'||^2, computed by (12.18) as 2 x WSS."""
    K = int(lab.max()) + 1
    return 2.0 * sum(((X[lab == k] - X[lab == k].mean(0)) ** 2).sum() for k in range(K) if np.any(lab == k))


def kmeans_alg(X, K, lab0, max_iter=200, trace=False):
    """Algorithm 12.2 from the initial labels lab0: (a) centroids, (b) reassign, until no change.
    Returns labels, centroids, objective (12.17) and, with trace=True, the list of
    (labels, centroids) after every step."""
    lab = np.asarray(lab0).copy()
    steps = [(lab.copy(), None)]
    for _ in range(max_iter):
        C = centroids(X, lab, K)
        steps.append((lab.copy(), C))
        d = ((X[:, None, :] - C[None]) ** 2).sum(2)
        d[:, np.isnan(C).any(1)] = np.inf
        new = d.argmin(1)
        steps.append((new.copy(), C))
        if np.array_equal(new, lab):
            break
        lab = new
    C = centroids(X, lab, K)
    out = (lab, C, kmeans_objective(X, lab))
    return out + (steps,) if trace else out


def kmeans_best(X, K, nstart=50, seed=0):
    """The best of nstart runs of Algorithm 12.2 from random label assignments."""
    rng = np.random.default_rng(seed)
    best = None
    for _ in range(nstart):
        lab, C, obj = kmeans_alg(X, K, rng.integers(0, K, len(X)))
        if best is None or obj < best[2] - 1e-12:
            best = (lab, C, obj)
    return best


def relabel_by_size(lab):
    """Relabel clusters 0, 1, ... in order of first appearance (for stable colours)."""
    order, out = {}, np.empty_like(lab)
    for i, v in enumerate(lab):
        order.setdefault(v, len(order))
        out[i] = order[v]
    return out


# =========================================================================== hierarchical clustering
def hclust(X=None, method="complete", D=None):
    """scipy linkage matrix for Euclidean distances between the rows of X (or a square dissimilarity D)."""
    if D is not None:
        return sch.linkage(squareform(D, checks=False), method=method)
    return sch.linkage(X, method=method, metric="euclidean")


def cut(L, k):
    """Cluster labels 0..k-1 from cutting the tree into k clusters (numbered by first appearance)."""
    return relabel_by_size(sch.cut_tree(L, n_clusters=k).ravel())


def merge_heights(L):
    return L[:, 2]


def dendro(ax, L, labels=None, colour="black", leaf_colours=None, lw=0.9, fs=7, rot=90):
    """Draw a dendrogram in one colour; optionally colour the leaf labels."""
    r = sch.dendrogram(L, ax=ax, labels=labels, color_threshold=-np.inf, above_threshold_color=colour,
                       leaf_rotation=rot, leaf_font_size=fs, no_labels=labels is None)
    for c in ax.collections:
        c.set_linewidth(lw)
    if leaf_colours is not None and labels is not None:
        for t in ax.get_xmajorticklabels():
            t.set_color(leaf_colours.get(t.get_text(), "black"))
    ax.spines[["top", "right", "bottom"]].set_visible(False)
    return r


# =========================================================================== simulated data
def sim_plane(seed=122):
    """Figure 12.2: 90 points (three groups of 30) close to a plane through the origin in 3-D."""
    rng = np.random.default_rng(seed)
    u1 = np.array([0.80, 0.45, -0.40]); u1 /= np.linalg.norm(u1)
    u2 = np.array([-0.25, 0.80, 0.55]); u2 -= (u2 @ u1) * u1; u2 /= np.linalg.norm(u2)
    nrm = np.cross(u1, u2)
    centres = [(-0.70, -0.20), (0.45, 0.75), (0.55, -0.55)]
    spread = [(0.13, 0.13), (0.30, 0.13), (0.28, 0.20)]
    X, g = [], []
    for k, ((a, b), (sa, sb)) in enumerate(zip(centres, spread)):
        A = a + sa * rng.standard_normal(30)
        B = b + sb * rng.standard_normal(30)
        E = 0.2 * rng.standard_normal(30)
        X.append(A[:, None] * u1 + B[:, None] * u2 + E[:, None] * nrm)
        g += [k] * 30
    return np.vstack(X), np.array(g)


def sim_kmeans(seed=127):
    """Figures 12.7-12.9: 150 points, a tight group of 50 on top and two overlapping groups below."""
    rng = np.random.default_rng(seed)
    X = np.vstack([rng.normal([0.0, 4.2], [0.75, 0.55], (50, 2)),
                   rng.normal([-0.9, 0.0], [0.75, 0.80], (50, 2)),
                   rng.normal([1.1, 0.3], [0.75, 0.80], (50, 2))])
    return X


def sim_three_classes(seed=1210):
    """Figure 12.10: 45 points, 15 from each of three classes."""
    rng = np.random.default_rng(seed)
    means = np.array([[-4.8, 0.2], [0.7, 3.4], [-0.9, -1.2]])
    X = np.vstack([rng.normal(m, [0.85, 0.75], (15, 2)) for m in means])
    return X, np.repeat([0, 1, 2], 15)


# nine points for Figures 12.12 and 12.13 (our own coordinates): 5 and 7 are the closest pair,
# then 1 and 6; point 9 is about equally far from 2, 8, 5 and 7, so it joins their cluster in one step
NINE = np.array([[-0.55, -1.00], [0.05, -0.80], [-1.50, -0.30], [-1.35, -1.55], [1.05, -0.25],
                 [-0.95, -1.15], [1.20, 0.02], [0.55, -0.25], [0.15, 0.90]])


def sim_linkage(seed=1214):
    """Figure 12.14: 60 points in two dimensions with weak group structure."""
    rng = np.random.default_rng(seed)
    means = rng.uniform(-3, 3, (6, 2))
    return np.vstack([rng.normal(m, 0.9, (10, 2)) for m in means])


def profiles():
    """Figure 12.15: three observations on 20 variables. 1 and 2 have the same shape (high correlation)
    at different levels (far apart); 1 and 3 are at the same level (close) with unrelated shapes."""
    j = np.arange(20)
    shape = np.array([1.0, 1.25, 0.9, -0.6, -0.6, -1.15, 1.0, 1.1, 1.05, 0.95, -0.55, -0.95, -1.15, 0.2, 1.05,
                      0.95, 0.95, -0.7, -0.6, -0.65])
    wob = 0.15 * np.sin(1.7 * j + 0.4)
    o1 = 2.0 + 2.2 * shape + wob
    o2 = 10.0 + 4.0 * shape - wob
    w = np.sin(0.9 * j + 1.0) + 0.6 * np.cos(2.3 * j)
    w, c1 = w - w.mean(), o1 - o1.mean()
    w -= (w @ c1) / (c1 @ c1) * c1          # remove the part of w that follows observation 1's shape
    o3 = 2.1 + 0.9 * w / w.std()             # so observations 1 and 3 are uncorrelated
    return np.vstack([o1, o2, o3])


SHOPPERS = {"socks": np.array([8, 11, 7, 6, 5, 6, 7, 9]), "computers": np.array([0, 0, 0, 0, 1, 1, 1, 1]),
            "price_socks": 3.0, "price_computers": 1500.0}
SHOPPER_COLOURS = ["#111111", "#e69f00", "#56b4e9", "#009e73", "#f0e442", "#0072b2", "#d55e00", "#cc79a7"]


# =========================================================================== figures: PCA
def _biplot(ax, Z, V, names, labels=None, factor=None, star=False, lim=None, fs=7.5):
    """Scores (state names or stars) with the loading arrows drawn on secondary (top/right) axes."""
    if lim is None:
        lim = 1.1 * np.abs(Z[:, :2]).max()
    if factor is None:
        factor = lim / 1.1 / np.abs(V[:, :2]).max() * 0.9
    if star or labels is None:
        ax.scatter(Z[:, 0], Z[:, 1], s=10, marker="*" if star else "o", color=BLUE, lw=0)
    else:
        for (x, y), s in zip(Z[:, :2], labels):
            ax.text(x, y, s, color=BLUE, fontsize=fs, ha="center", va="center")
    for j, nm in enumerate(names):
        x, y = factor * V[j, 0], factor * V[j, 1]
        ax.annotate("", xy=(x, y), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=ORANGE, lw=1.1))
        ax.text(1.12 * x, 1.12 * y, nm, color=ORANGE, fontsize=fs + 1, ha="center", va="center")
    ax.set_xlim(-lim, lim); ax.set_ylim(-lim, lim)
    ax.set_xlabel("First principal component"); ax.set_ylabel("Second principal component")
    sx = ax.secondary_xaxis("top", functions=(lambda v: v / factor, lambda v: v * factor))
    sy = ax.secondary_yaxis("right", functions=(lambda v: v / factor, lambda v: v * factor))
    for s in (sx, sy):
        s.tick_params(colors=ORANGE, labelsize=8)
    ax.axhline(0, color=GREY, lw=0.4, ls=":"); ax.axvline(0, color=GREY, lw=0.4, ls=":")


def fig12_1(out=None):
    """Biplot of the standardised USArrests data (scores and loadings)."""
    U = usarrests()
    P = pca(U.to_numpy(float))
    fig, ax = plt.subplots(figsize=(6.6, 6.4))
    _biplot(ax, P["Z"], P["V"], list(U.columns), list(U.index), factor=3.5, lim=3.5, fs=6.6)
    savefig(fig, CH, "fig12-1", out)


def table12_1(out=None):
    """Table 12.1: the first two loading vectors of the standardised USArrests data."""
    U = usarrests()
    P = pca(U.to_numpy(float))
    print(pd.DataFrame(P["V"][:, :2], index=U.columns, columns=["PC1", "PC2"]).round(7))
    print("PVE:", np.round(P["pve"], 4), " sdev:", np.round(P["sdev"], 4))


def fig12_2(out=None):
    """Simulated 3-D data: the plane of the first two principal components, and the projection."""
    X, g = sim_plane()
    P = pca(X, scale=False)
    mu = X.mean(0)
    V = P["V"]
    cols = np.array([ORANGE, GREEN, CYAN])[g]
    fig = plt.figure(figsize=(10.2, 4.8))
    ax = fig.add_subplot(1, 2, 1, projection="3d")
    a = np.linspace(-1.2, 1.2, 9)
    A, B = np.meshgrid(a, np.linspace(-1.0, 1.0, 8))
    S = mu + A[..., None] * V[:, 0] + B[..., None] * V[:, 1]
    ax.plot_wireframe(S[..., 0], S[..., 1], S[..., 2], color="#8c8c8c", lw=0.45)
    ax.plot_surface(S[..., 0], S[..., 1], S[..., 2], color="#d9d9d9", alpha=0.25, lw=0, shade=False)
    proj = mu + P["Z"][:, :2] @ V[:, :2].T
    for x, p_, c in zip(X, proj, cols):
        ax.plot([x[0], p_[0]], [x[1], p_[1]], [x[2], p_[2]], color="#555555", lw=0.6)
    ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=cols, s=14, depthshade=False)
    ax.view_init(elev=28, azim=-35)
    ax.set_xticklabels([]); ax.set_yticklabels([]); ax.set_zticklabels([])
    ax.set_title("Data and the plane of the first two components")
    ax2 = fig.add_subplot(1, 2, 2)
    ax2.scatter(P["Z"][:, 0], P["Z"][:, 1], c=cols, s=18)
    ax2.set_xlabel("First principal component"); ax2.set_ylabel("Second principal component")
    ax2.set_title("Scores: coordinates in that plane")
    ax2.set_aspect("equal", adjustable="datalim")
    fig.tight_layout()
    savefig(fig, CH, "fig12-2", out)


def fig12_3(out=None):
    """Scree plot and cumulative PVE for USArrests."""
    P = pca(usarrests().to_numpy(float))
    fig, axes = panel_grid(1, 2, size=(3.6, 3.1))
    m = np.arange(1, 5)
    for ax, y, lab in [(axes[0, 0], P["pve"], "Prop. variance explained"),
                       (axes[0, 1], np.cumsum(P["pve"]), "Cumulative prop. variance explained")]:
        ax.plot(m, y, "o-", color=BLUE, mfc="white")
        ax.set_ylim(0, 1.03); ax.set_xticks(m)
        ax.set_xlabel("Principal component"); ax.set_ylabel(lab)
        for x, v in zip(m, y):
            ax.text(x + 0.08, v + 0.035, "%.3f" % v, fontsize=8, color=GREY)
    fig.tight_layout()
    savefig(fig, CH, "fig12-3", out)


def fig12_4(out=None):
    """Biplots with the variables scaled to unit standard deviation (left) and unscaled (right)."""
    U = usarrests()
    Ps, Pu = pca(U.to_numpy(float)), pca(U.to_numpy(float), scale=False)
    fig, axes = panel_grid(1, 2, size=(4.3, 4.3))
    _biplot(axes[0, 0], Ps["Z"], Ps["V"], list(U.columns), star=True, factor=3.5, lim=3.5)
    _biplot(axes[0, 1], Pu["Z"], Pu["V"], list(U.columns), star=True, factor=150.0, lim=175)
    axes[0, 0].set_title("Scaled", pad=22); axes[0, 1].set_title("Unscaled", pad=22)
    fig.tight_layout()
    savefig(fig, CH, "fig12-4", out)


def fig12_5(out=None):
    """Imputed against true values for the 20 entries removed in the R lab (Algorithm 12.1, M = 1)."""
    X, Xna = us_missing_R()
    Xhat, Xapp, hist = hard_impute(Xna, 1)
    t, e = X[R_INA, R_INB], Xhat[R_INA, R_INB]
    names = list(usarrests().columns)
    fig, ax = plt.subplots(figsize=(5.0, 5.0))
    ax.plot([-2, 2], [-2, 2], ls="--", color=GREY, lw=0.8)
    for j in range(4):
        k = R_INB == j
        ax.scatter(t[k], e[k], color=VAR_COLOURS[j], s=22, label=names[j], zorder=3)
    for i, j, x, y in zip(R_INA, R_INB, t, e):
        ax.text(x, y + 0.06, STATE_ABB[i], fontsize=7, ha="center", va="bottom")
    ax.set_xlim(-1.95, 1.95); ax.set_ylim(-1.95, 1.95)
    ax.set_xlabel("Original value"); ax.set_ylabel("Imputed value")
    ax.legend(loc="lower right", fontsize=8, frameon=True)
    ax.text(-1.85, 1.7, "correlation %.4f\n%d iterations" % (np.corrcoef(t, e)[0, 1], len(hist)), fontsize=8)
    savefig(fig, CH, "fig12-5", out)


def imputation_trials(n_trials=100, n_omit=20, M=1, seed=1206):
    """Figure 12.6 and the text's 0.63 +- 0.11 against 0.79 +- 0.08: 100 random patterns of 20
    missing entries (20 states, one variable each) in the standardised USArrests data."""
    X = standardise(usarrests().to_numpy(float))
    n, p = X.shape
    full = low_rank(X, M)
    U0, d0, V0t = np.linalg.svd(X, full_matrices=False)
    z0 = U0[:, 0] * d0[0]
    rng = np.random.default_rng(seed)
    cor_imp, cor_full, z1, dd = [], [], [], []
    for _ in range(n_trials):
        ina = rng.choice(n, n_omit, replace=False)
        inb = rng.integers(0, p, n_omit)
        Xna = X.copy()
        Xna[ina, inb] = np.nan
        Xhat, _, _ = hard_impute(Xna, M)
        cor_imp.append(np.corrcoef(X[ina, inb], Xhat[ina, inb])[0, 1])
        cor_full.append(np.corrcoef(X[ina, inb], full[ina, inb])[0, 1])
        U, d, Vt = np.linalg.svd(Xhat, full_matrices=False)
        z = U[:, 0] * d[0]
        z1.append(z if z @ z0 >= 0 else -z)
        dd.append(d)
    return {"cor_imp": np.array(cor_imp), "cor_full": np.array(cor_full), "z1": np.array(z1), "d": np.array(dd),
            "z0": z0, "d0": d0}


def fig12_6(out=None):
    """100 repetitions: first PC scores and singular values of the completed matrix against the truth."""
    T = imputation_trials()
    fig, axes = panel_grid(1, 2, size=(3.9, 3.7))
    ax = axes[0, 0]
    m, s = T["z1"].mean(0), T["z1"].std(0, ddof=1)
    ax.plot([-3.2, 3.2], [-3.2, 3.2], ls="--", color=GREY, lw=0.8)
    ax.errorbar(T["z0"], m, yerr=s, fmt="o", ms=3, color=ORANGE, ecolor=ORANGE, elinewidth=0.8, capsize=2)
    ax.set_xlabel("True first principal component"); ax.set_ylabel("Imputed first principal component")
    ax = axes[0, 1]
    m, s = T["d"].mean(0), T["d"].std(0, ddof=1)
    ax.plot([1.5, 12.5], [1.5, 12.5], ls="--", color=GREY, lw=0.8)
    ax.errorbar(T["d0"], m, yerr=s, fmt="o", ms=4, color=CYAN, ecolor=CYAN, capsize=2)
    ax.set_xlabel(r"True singular values $d_m$"); ax.set_ylabel(r"Imputed singular values $d_m$")
    fig.tight_layout()
    savefig(fig, CH, "fig12-6", out)


# =========================================================================== figures: K-means
def _kscatter(ax, X, lab=None, C=None, title=None, cols=K_COLOURS, s=11):
    if lab is None:
        ax.scatter(X[:, 0], X[:, 1], s=s, color="black", lw=0)
    else:
        ax.scatter(X[:, 0], X[:, 1], s=s, c=[cols[k] for k in lab], lw=0)
    if C is not None:
        for k, c in enumerate(C):
            if not np.isnan(c).any():
                ax.scatter([c[0]], [c[1]], s=110, color=cols[k], edgecolor="black", lw=1.4, zorder=4)
    ax.set_xticks([]); ax.set_yticks([])
    if title:
        ax.set_title(title, fontweight="bold")


def fig12_7(out=None):
    """K-means with K = 2, 3, 4 on 150 simulated points."""
    X = sim_kmeans()
    fig, axes = panel_grid(1, 3, size=(2.9, 3.0))
    for ax, K in zip(axes[0], (2, 3, 4)):
        lab, C, obj = kmeans_best(X, K, nstart=50, seed=K)
        _kscatter(ax, X, relabel_by_size(lab), title="K=%d" % K)
    fig.tight_layout()
    savefig(fig, CH, "fig12-7", out)


FIG12_8_SEED = 8


def fig12_8(out=None):
    """The steps of Algorithm 12.2 (K = 3) from a random assignment."""
    X = sim_kmeans()
    rng = np.random.default_rng(FIG12_8_SEED)
    lab0 = rng.integers(0, 3, len(X))
    lab, C, obj, steps = kmeans_alg(X, 3, lab0, trace=True)
    fig, axes = panel_grid(2, 3, size=(2.9, 3.0))
    _kscatter(axes[0, 0], X, title="Data")
    _kscatter(axes[0, 1], X, steps[0][0], title="Step 1")
    _kscatter(axes[0, 2], X, steps[1][0], steps[1][1], title="Iteration 1, Step 2a")
    _kscatter(axes[1, 0], X, steps[2][0], steps[2][1], title="Iteration 1, Step 2b")
    _kscatter(axes[1, 1], X, steps[3][0], steps[3][1], title="Iteration 2, Step 2a")
    n_it = (len(steps) - 1) // 2
    _kscatter(axes[1, 2], X, lab, C, title="Final results (%d iterations)" % n_it)
    fig.tight_layout()
    savefig(fig, CH, "fig12-8", out)


FIG12_9_SEEDS = (51, 1, 2, 3, 4, 254)   # chosen to show two local optima, as in the book


def six_runs():
    """Figure 12.9: Algorithm 12.2 (K = 3) from six random assignments; returns [(labels, objective)]."""
    X = sim_kmeans()
    res = []
    for s in FIG12_9_SEEDS:
        rng = np.random.default_rng(1290 + s)
        lab, C, obj = kmeans_alg(X, 3, rng.integers(0, 3, len(X)))
        res.append((lab, obj))
    return X, res


def fig12_9(out=None):
    """Six runs of K-means (K = 3) from random starts, labelled by the objective (12.17)."""
    X, res = six_runs()
    best = min(o for _, o in res)
    fig, axes = panel_grid(2, 3, size=(2.9, 3.0))
    for ax, (lab, obj) in zip(axes.ravel(), res):
        _kscatter(ax, X, relabel_by_size(lab))
        ax.set_title("%.1f" % obj, fontweight="bold", color=RED if obj < best + 1e-6 else "#7f8fb0")
    fig.tight_layout()
    savefig(fig, CH, "fig12-9", out)


# =========================================================================== figures: hierarchical clustering
def fig12_10(out=None):
    """45 simulated points from three classes."""
    X, g = sim_three_classes()
    fig, ax = plt.subplots(figsize=(4.6, 4.2))
    ax.scatter(X[:, 0], X[:, 1], c=[K_COLOURS[[1, 0, 2][k]] for k in g], s=22)
    ax.set_xlabel("$X_1$"); ax.set_ylabel("$X_2$")
    savefig(fig, CH, "fig12-10", out)


FIG12_11_CUTS = (9.0, 5.0)


def fig12_11(out=None):
    """Complete-linkage dendrogram of the 45 points; cut at two heights."""
    X, g = sim_three_classes()
    L = hclust(X, "complete")
    fig, axes = panel_grid(1, 3, size=(3.4, 3.0))
    for ax, h in zip(axes[0], (None,) + FIG12_11_CUTS):
        if h is None:
            sch.dendrogram(L, ax=ax, no_labels=True, color_threshold=-np.inf, above_threshold_color="black")
        else:
            k = len(set(sch.fcluster(L, h, "distance")))
            pal = ["#cc79a7", "#009e73", "#e6c200"][:k]
            sch.set_link_color_palette(pal)
            sch.dendrogram(L, ax=ax, no_labels=True, color_threshold=h, above_threshold_color="black")
            sch.set_link_color_palette(None)
            ax.axhline(h, ls="--", color="black", lw=0.8)
            ax.set_title("cut at %g: %d clusters" % (h, k))
        for c in ax.collections:
            c.set_linewidth(0.8)
        ax.spines[["top", "right", "bottom"]].set_visible(False)
    fig.tight_layout()
    savefig(fig, CH, "fig12-11", out)


def fig12_12(out=None):
    """A dendrogram of nine points (complete linkage) and the points themselves."""
    L = hclust(NINE, "complete")
    fig, axes = panel_grid(1, 2, size=(3.8, 3.3))
    ax = axes[0, 0]
    sch.dendrogram(L, ax=ax, labels=[str(i) for i in range(1, 10)], color_threshold=-np.inf,
                   above_threshold_color="black", leaf_font_size=10)
    ax.spines[["top", "right", "bottom"]].set_visible(False)
    ax = axes[0, 1]
    for i, (x, y) in enumerate(NINE):
        ax.text(x, y, str(i + 1), ha="center", va="center", fontsize=10)
    ax.set_xlim(-1.8, 1.5); ax.set_ylim(-1.8, 1.15)
    ax.set_xlabel("$X_1$"); ax.set_ylabel("$X_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig12-12", out)


def fig12_13(out=None):
    """The first three fusions of complete-linkage clustering on the nine points."""
    L = hclust(NINE, "complete")
    clusters = {i: [i] for i in range(9)}
    boxes = []
    states = [list(boxes)]
    for t in range(3):
        a, b = int(L[t, 0]), int(L[t, 1])
        members = clusters.pop(a) + clusters.pop(b)
        clusters[9 + t] = members
        boxes = [bx for bx in boxes if not set(bx[0]) <= set(members)] + [(members, t)]
        states.append(list(boxes))
    fig, axes = panel_grid(2, 2, size=(3.5, 3.2))
    bcol = [RED, BLUE, GREEN]
    for ax, st in zip(axes.ravel(), states):
        for i, (x, y) in enumerate(NINE):
            ax.text(x, y, str(i + 1), ha="center", va="center", fontsize=10)
        for members, t in st:
            P = NINE[members]
            lo, hi = P.min(0) - 0.14, P.max(0) + 0.14
            ax.add_patch(plt.Rectangle(lo, *(hi - lo), fill=False, ec=bcol[t], lw=1.3))
        ax.set_xlim(-1.8, 1.5); ax.set_ylim(-1.8, 1.15)
        ax.set_xlabel("$X_1$"); ax.set_ylabel("$X_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig12-13", out)


def fig12_14(out=None):
    """Average, complete and single linkage on the same 60 points."""
    X = sim_linkage()
    fig, axes = panel_grid(1, 3, size=(3.3, 3.4))
    for ax, meth, col in zip(axes[0], ("average", "complete", "single"), ("#e6a800", "#56b4e9", "#3cb38a")):
        sch.dendrogram(hclust(X, meth), ax=ax, no_labels=True, color_threshold=-np.inf, above_threshold_color=col)
        for c in ax.collections:
            c.set_linewidth(0.8)
        ax.set_title(meth.capitalize() + " linkage")
        ax.set_yticks([])
        for sp in ax.spines.values():
            sp.set_visible(True)
    fig.tight_layout()
    savefig(fig, CH, "fig12-14", out)


def fig12_15(out=None):
    """Three profiles on 20 variables: Euclidean distance against correlation."""
    O = profiles()
    cols = ["#e69f00", "#009e73", "#cc79a7"]
    fig, ax = plt.subplots(figsize=(6.2, 3.9))
    for k in range(3):
        ax.plot(np.arange(1, 21), O[k], color=cols[k], label="Observation %d" % (k + 1))
        ax.text(20.4, O[k, -1], str(k + 1), color=cols[k], va="center")
    ax.set_xlabel("Variable index")
    ax.legend(fontsize=8, loc="lower center", bbox_to_anchor=(0.5, 1.0), ncol=3, frameon=False)
    savefig(fig, CH, "fig12-15", out)


def fig12_16(out=None):
    """Eight shoppers: socks and computers bought, raw counts, scaled by the standard deviation, dollars."""
    S = SHOPPERS
    raw = np.vstack([S["socks"], S["computers"]]).astype(float)
    sc = raw / raw.std(1, ddof=1)[:, None]
    dol = raw * np.array([[S["price_socks"]], [S["price_computers"]]])
    fig, axes = panel_grid(1, 3, size=(3.0, 2.9))
    for ax, M, yl in zip(axes[0], (raw, sc, dol), ("Number bought", "Number / standard deviation", "Dollars spent")):
        w = 0.1
        for i in range(8):
            for j in range(2):
                ax.bar(j + (i - 3.5) * w, M[j, i], width=w, color=SHOPPER_COLOURS[i], edgecolor="black", lw=0.3)
        ax.set_xticks([0, 1]); ax.set_xticklabels(["Socks", "Computers"]); ax.set_ylabel(yl)
    fig.tight_layout()
    savefig(fig, CH, "fig12-16", out)


# =========================================================================== figures: NCI60


def nci_pca():
    """PCA of the standardised NCI60 data (R's scale(), divisor n - 1), with prcomp()'s signs for the
    first three components (prcomp's signs are those of R's LAPACK SVD; we fix them by checking that
    the first three scores of the first cell line have the signs printed by ch12_lab.R)."""
    X, labs = nci60()
    P = pca(X, orient=False)
    ref = np.array([-19.682, 3.528, -9.735])     # prcomp(nci.data, scale = TRUE)$x[1, 1:3]
    s = np.sign(P["Z"][0, :3]) * np.sign(ref)
    P["Z"][:, :3] *= s
    P["V"][:, :3] *= s
    return P, labs


def nci_colours(labs):
    types = sorted(set(labs))
    cmap = plt.get_cmap("tab20")
    return {t: cmap(i) for i, t in enumerate(types)}


def fig12_17(out=None):
    """NCI60 cell lines on the first three principal component scores, coloured by cancer type."""
    P, labs = nci_pca()
    cmap = nci_colours(labs)
    fig, axes = panel_grid(1, 2, size=(4.2, 3.9))
    for ax, (a, b) in zip(axes[0], ((0, 1), (0, 2))):
        ax.scatter(P["Z"][:, a], P["Z"][:, b], c=[cmap[l] for l in labs], s=22, edgecolor="black", lw=0.3)
        ax.set_xlabel("$Z_%d$" % (a + 1)); ax.set_ylabel("$Z_%d$" % (b + 1))
    handles = [plt.Line2D([], [], marker="o", ls="", color=cmap[t], mec="black", mew=0.3, label=t) for t in cmap]
    fig.legend(handles=handles, loc="center left", bbox_to_anchor=(1.0, 0.5), fontsize=7.5, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig12-17", out)


def fig12_18(out=None):
    """NCI60: PVE of each component and the cumulative PVE (percent)."""
    P, _ = nci_pca()
    m = np.arange(1, len(P["pve"]) + 1)
    fig, axes = panel_grid(1, 2, size=(3.7, 3.0))
    axes[0, 0].plot(m, 100 * P["pve"], "o-", color=BLUE, ms=3, mfc="white")
    axes[0, 0].set_ylabel("PVE")
    axes[0, 1].plot(m, 100 * np.cumsum(P["pve"]), "o-", color="#cd3333", ms=3, mfc="white")
    axes[0, 1].set_ylabel("Cumulative PVE")
    for ax in axes[0]:
        ax.set_xlabel("Principal component")
    fig.tight_layout()
    savefig(fig, CH, "fig12-18", out)


def nci_trees():
    X, labs = nci60()
    Xs = standardise(X)
    return {m: hclust(Xs, m) for m in ("complete", "average", "single")}, labs


def fig12_19(out=None):
    """NCI60 dendrograms with complete, average and single linkage (Euclidean distance)."""
    T, labs = nci_trees()
    cmap = nci_colours(labs)
    fig, axes = plt.subplots(3, 1, figsize=(9.5, 12.0))
    for ax, m in zip(axes, ("complete", "average", "single")):
        sch.dendrogram(T[m], ax=ax, labels=list(labs), color_threshold=-np.inf, above_threshold_color="black",
                       leaf_rotation=90, leaf_font_size=6.5)
        for c in ax.collections:
            c.set_linewidth(0.7)
        for t in ax.get_xmajorticklabels():
            t.set_color(cmap[t.get_text()])
        ax.set_title(m.capitalize() + " linkage")
        ax.spines[["top", "right", "bottom"]].set_visible(False)
    fig.tight_layout()
    savefig(fig, CH, "fig12-19", out)


# =========================================================================== exercise figures
EX2_D = np.array([[0, 0.3, 0.4, 0.7], [0.3, 0, 0.5, 0.8], [0.4, 0.5, 0, 0.45], [0.7, 0.8, 0.45, 0]])
EX3_X = np.array([[1, 4], [1, 3], [0, 4], [5, 1], [6, 2], [4, 0]], float)
EX3_START = np.array([0, 1, 0, 1, 0, 1])     # a fixed 'random' start: observations 1, 3, 5 in cluster 1


def fig_ex12_2(out=None):
    """Exercise 2: complete and single linkage on the 4 x 4 dissimilarity matrix, and a reordering."""
    fig, axes = panel_grid(1, 3, size=(2.9, 2.8))
    Lc, Ls = hclust(D=EX2_D, method="complete"), hclust(D=EX2_D, method="single")
    for ax, L, t, lab in [(axes[0, 0], Lc, "(a) complete", None), (axes[0, 1], Ls, "(b) single", None),
                          (axes[0, 2], Lc, "(e) complete, reordered", "swap")]:
        r = sch.dendrogram(L, ax=ax, labels=["1", "2", "3", "4"], color_threshold=-np.inf,
                           above_threshold_color="black", leaf_font_size=10)
        if lab == "swap":
            ax.cla()
            # swap the two branches at the top and within {1, 2}: leaves 4, 3, 2, 1
            Lr = L.copy()
            sch.dendrogram(Lr, ax=ax, labels=["1", "2", "3", "4"], color_threshold=-np.inf,
                           above_threshold_color="black", leaf_font_size=10)
            ax.invert_xaxis()   # leaves now read 4, 3, 2, 1: both fusions swapped, same tree
        for h in L[:, 2]:
            ax.axhline(h, color=GREY, lw=0.4, ls=":")
        ax.set_yticks(sorted(set(np.round(L[:, 2], 2))))
        ax.set_title(t)
        ax.spines[["top", "right", "bottom"]].set_visible(False)
    fig.tight_layout()
    savefig(fig, CH, "ex12-2", out)


def fig_ex12_3(out=None):
    """Exercise 3: K-means by hand with K = 2 on six points, from a fixed start."""
    lab, C, obj, steps = kmeans_alg(EX3_X, 2, EX3_START, trace=True)
    fig, axes = panel_grid(1, 3, size=(2.8, 2.8))
    shown = [(steps[1][0], steps[1][1], "(b), (c) start and centroids"), (steps[2][0], steps[1][1], "(d) reassigned"),
             (lab, C, "(e), (f) final")]
    for ax, (l, c, t) in zip(axes[0], shown):
        ax.scatter(EX3_X[:, 0], EX3_X[:, 1], c=[K_COLOURS[k] for k in l], s=40, edgecolor="black", lw=0.4)
        for i, (x, y) in enumerate(EX3_X):
            ax.text(x + 0.18, y + 0.18, str(i + 1), fontsize=8)
        for k in range(2):
            ax.scatter([c[k, 0]], [c[k, 1]], marker="X", s=90, color=K_COLOURS[k], edgecolor="black")
        ax.set_xlim(-0.8, 7); ax.set_ylim(-0.8, 5); ax.set_title(t, fontsize=9)
        ax.set_xlabel("$X_1$"); ax.set_ylabel("$X_2$")
    fig.tight_layout()
    savefig(fig, CH, "ex12-3", out)


# =========================================================================== demo data
def r4(a, d=4):
    return np.round(np.asarray(a, float), d).tolist()


def people_data(seed=1212):
    """'Men and women from three countries' (Section 12.4.2): three features, sex on the first,
    country on the other two (an equilateral triangle of side 1). With half-distance 0.46 between
    the sexes, the best two clusters split by sex and the best three by country (Result 12.9)."""
    rng = np.random.default_rng(seed)
    tri = np.array([[0.0, 0.5774], [-0.5, -0.2887], [0.5, -0.2887]])
    X, sex, country = [], [], []
    for s, a in enumerate((-0.46, 0.46)):
        for c in range(3):
            X.append(np.column_stack([a + 0.07 * rng.standard_normal(15),
                                      tri[c, 0] + 0.07 * rng.standard_normal(15),
                                      tri[c, 1] + 0.07 * rng.standard_normal(15)]))
            sex += [s] * 15
            country += [c] * 15
    return np.vstack(X), np.array(sex), np.array(country)


def export_data(out=None):
    """Write the JSON files used by the three demonstrations."""
    os.makedirs(DATA_OUT, exist_ok=True)
    U = usarrests()
    np.random.seed(15)                    # the Python lab's missing entries (legacy numpy generator)
    py_r = np.random.choice(np.arange(50), 20, replace=False)
    py_c = np.random.choice(np.arange(4), 20, replace=True)
    us = {"states": list(U.index), "abb": STATE_ABB, "vars": list(U.columns), "X": U.to_numpy(float).tolist(),
          "r_rows": R_INA.tolist(), "r_cols": R_INB.tolist(), "py_rows": py_r.tolist(), "py_cols": py_c.tolist()}
    with open(os.path.join(DATA_OUT, "ch12-usarrests.json"), "w") as f:
        json.dump(us, f, separators=(",", ":"))
    Xp, sex, country = people_data()
    P, labs = nci_pca()
    Z5 = P["Z"][:, :5]
    Xu = standardise(U.to_numpy(float))
    cl = {"people": {"X": r4(Xp, 4), "sex": sex.tolist(), "country": country.tolist()},
          "usarrests": {"X": r4(Xu, 6), "names": STATE_ABB, "vars": list(U.columns)},
          "nci": {"X": r4(Z5, 4), "labels": labs.tolist()},
          "blobs": {"X": r4(sim_kmeans(), 4)}}
    with open(os.path.join(DATA_OUT, "ch12-clusters.json"), "w") as f:
        json.dump(cl, f, separators=(",", ":"))
    for nm in ("ch12-usarrests.json", "ch12-clusters.json"):
        print("wrote ../data/%s (%.0f kB)" % (nm, os.path.getsize(os.path.join(DATA_OUT, nm)) / 1024))


FIGURES = {
    "12.1": fig12_1, "T12.1": table12_1, "12.2": fig12_2, "12.3": fig12_3, "12.4": fig12_4, "12.5": fig12_5,
    "12.6": fig12_6, "12.7": fig12_7, "12.8": fig12_8, "12.9": fig12_9, "12.10": fig12_10,
    "12.11": fig12_11, "12.12": fig12_12, "12.13": fig12_13, "12.14": fig12_14, "12.15": fig12_15,
    "12.16": fig12_16, "12.17": fig12_17, "12.18": fig12_18, "12.19": fig12_19,
    "ex2": fig_ex12_2, "ex3": fig_ex12_3, "data": export_data,
}

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