"""Hastie, Tibshirani and Friedman (2009), Chapter 15: Random Forests.

Reproduces the figures of Chapter 15 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning, 2nd edition (Springer, 2009), pp. 587-604, written from scratch with numpy and
matplotlib. The methods are small functions meant to be read next to the lecture notes
(../ch15-random-forests.html):

* Algorithm 15.1, from scratch: grow_tree() grows one random-forest tree on a bootstrap sample (at every
  node the variables are visited in a random order and the best split among the first m that vary in the
  node is taken; Gini index for classification, squared error for regression; a node is split only if
  it holds more than n_min cases and is not pure), and own_forest() grows B of them with the bootstrap
  samples and in-bag counts. Random numbers come from the demos' generator (JSRandom, the DK.rng of
  the browser demonstrations), so oob_error_demo() gives exactly the numbers of oob-error-demo.html,
  which runs the same code in JavaScript. tree_apply() and forest_votes() evaluate the trees;
  oob_votes() forms the out-of-bag predictions of Section 15.3.1; proximity() accumulates the
  proximity matrix of Section 15.3.3 and classical_mds() embeds it; rf_weights() gives the
  adaptive-nearest-neighbour weights of Section 15.4.3.
* For the larger data sets, grow_forest() runs the same algorithm with scikit-learn's compiled tree
  as the split search (DecisionTreeClassifier/Regressor with max_features = m, fitted to an explicit
  bootstrap sample drawn here, so that node sizes count repeated cases as in Algorithm 15.1). It
  records, tree by tree, the test error and the out-of-bag error, the Gini (impurity) importance of
  every variable (gini_importance_tree) and the out-of-bag permutation ('randomization') importance
  (Section 15.3.2). With m = p and the same bootstrap sample its trees fit the same values as grow_tree().
* Section 15.4: decorrelation_sim() estimates, at 600 test points, the variance of a single
  random-forest tree, its within-training-set part, the variance and squared bias of the forest
  (B -> infinity) and the tree-to-tree correlation rho(x) (15.5)-(15.10), by repeating the simulation
  (15.8) over many training sets, with the unbiased variance-component estimators described in the
  notes; ridge_on_sim() gives the ridge comparison quoted on p. 601.
* Data: the spam, California housing and nested-spheres data are those of Chapter 10
  (ch10_boosting.spam, .california, .nested_spheres), the mixture data that of Chapter 2
  (ch02_overview_supervised_learning.mixture, with its 10,000-point test set); sim_linear() is the
  model (15.8), mease_wyner() the model (15.11) of Exercise 15.3, sim_additive2() the additive model of
  Figure 15.8.

Figures reproduced: 15.1-15.11, plus two supplementary figures: 15.S1 (Exercise 15.6: out-of-bag and
test error of random forests on the spam data against m) and 15.S2 (the weights that a random forest
gives to the training points, Section 15.4.3, against the 3 nearest neighbours). Run
`python3 ch15_random_forests.py --list`, `python3 ch15_random_forests.py` (all figures, about half an hour
single-threaded the first time; forests and simulations are cached in cache/) or
`python3 ch15_random_forests.py --fig 15.4`. Files go to ../img/ch15/. The demos' data go to
../data/ch15-decorrelation.json (rf-decorrelation-demo.html) and ../data/ch15-spam-importance.json
(rf-importance-demo.html); oob-error-demo.html computes everything in the browser.

Figures not reproduced: none; every figure of the chapter is computed.

Settings chosen where the book gives none (the book used the R package randomForest, whose defaults
are followed: m = floor(sqrt(p)) and n_min = 1 for classification, m = floor(p/3) and n_min = 5 for
regression, majority vote for classification, ties going to class 0):
* Spam data (Figures 15.1, 15.4, 15.5, 15.S1): the book's training/test split. Random forest m = 7 with
  2500 trees; bagging (m = 57) with 1000 trees (each bagged tree costs six times as much). Gradient
  boosting: 5-leaf trees, shrinkage 0.05, half-subsamples (the gbm default), 2500 trees (the book's
  number, chosen there by cross-validation); scikit-learn's GradientBoostingClassifier, the method of
  Chapter 10. Permutation importance from the first 500 trees. Figure 15.S1: 500 trees for each m.
* Nested spheres (Figure 15.2): the simulation (10.2), N = 2000, 10,000 test points; 10 simulations
  (the book has 50); 200 trees per forest; gradient boosting with shrinkage 0.05 and 2000 trees of 2
  leaves (GBM-1) or 7 leaves (GBM-6), without subsampling (histogram-based boosting, for speed).
* California housing (Figure 15.3): the 80/20 split of Chapter 10; forests of 500 trees (the book's
  curves are flat after about 200); boosting with squared-error loss (gbm's default), shrinkage 0.05,
  1000 trees of 5 or 7 leaves (interaction depth 4 or 6), histogram-based.
* Mixture data (Figures 15.6, 15.11, 15.S2): own_forest with m = 1, n_min = 1, 500 trees, seed 15;
  proximities from out-of-bag pairs, normalised by the number of trees in which both points are out of
  bag; classical scaling of the dissimilarities 1 - proximity.
* Figure 15.7: the model (15.11) with J = 2 and q = 0.1, 15 simulations per setting (the book has 50),
  200 trees per forest; gradient boosting with 4-leaf trees, shrinkage 0.02 and 300 trees.
* Figure 15.8: Y = sin(pi X1) + X2 + eps with X uniform on [0, 1]^12 and eps ~ N(0, 1), N = 500,
  test sets of 2000, 30 simulations, m = 4, 200 trees.
* Figures 15.9-15.10: the model (15.8) with N = 100 and p = 50, 600 standard-normal test points,
  500 training sets, 10 trees per training set and m in {1, 4, 7, 10, 13, 19, 25, 31, 37, 43, 49, 50}.
"""
import json
import math
import os
import pickle

import numpy as np

import common
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, savefig
import ch02_overview_supervised_learning as ch02
import ch10_boosting as ch10

CH = 15
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")
JSRandom = ch10.JSRandom
SPAM_NAMES = ch10.SPAM_NAMES


def _cache(name, build):
    """Load cache/<name> or build it, store it and return it."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, name)
    if os.path.exists(path):
        with open(path, "rb") as f:
            return pickle.load(f)
    obj = build()
    with open(path + ".part", "wb") as f:
        pickle.dump(obj, f, protocol=4)
    os.replace(path + ".part", path)
    return obj


# =========================================================================== data
spam = ch10.spam
california = ch10.california


def nested_spheres(N, seed, p=10):
    """The simulation (10.2) with labels 0/1 (1 outside the sphere)."""
    X, y = ch10.nested_spheres(N, seed, p)
    return X, (y > 0).astype(int)


def sim_linear(N, rng, p=50, n_rel=None):
    """The model (15.8): X ~ N(0, I_p), Y = sum_{j <= r} X_j / sqrt(r) + eps, eps ~ N(0, 1), with
    r = p (the book's model) or r = n_rel relevant inputs. Returns X, Y, mu(X)."""
    r = p if n_rel is None else n_rel
    X = rng.standard_normal((N, p))
    mu = X[:, :r].sum(1) / math.sqrt(r)
    return X, mu + rng.standard_normal(N), mu


def mease_wyner(N, p, rng, J=2, q=0.1):
    """The model (15.11): X ~ U[0, 1]^p and Pr(Y = 1 | X) = q + (1 - 2q) I(X_1 + ... + X_J > J/2).
    Returns X, Y (0/1) and Pr(Y = 1 | X)."""
    X = rng.uniform(size=(N, p))
    prob = q + (1 - 2 * q) * (X[:, :J].sum(1) > J / 2)
    return X, (rng.uniform(size=N) < prob).astype(int), prob


def sim_additive2(N, rng, p=12):
    """Figure 15.8: Y = sin(pi X_1) + X_2 + eps, X ~ U[0, 1]^p, eps ~ N(0, 1). Returns X, Y, mu."""
    X = rng.uniform(size=(N, p))
    mu = np.sin(np.pi * X[:, 0]) + X[:, 1]
    return X, mu + rng.standard_normal(N), mu


def prob_relevant(p, r, m):
    """Probability that at least one of r relevant variables is among m drawn without replacement
    from p (the hypergeometric probability printed above the pairs in Figure 15.7)."""
    return 1.0 - math.comb(p - r, m) / math.comb(p, m)


def default_m(p, task="class"):
    """randomForest's defaults: floor(sqrt(p)) for classification, max(floor(p/3), 1) for regression."""
    return max(int(math.floor(math.sqrt(p))), 1) if task == "class" else max(p // 3, 1)


# =========================================================================== Algorithm 15.1 from scratch
def grow_tree(X, y, rows, m, nmin, rng, task="class"):
    """Grow one random-forest tree (Algorithm 15.1, step 1(b)) on the cases `rows` (a bootstrap
    sample: a list of row numbers, with repeats).

    X is a list of rows (lists of floats), y a list of floats (0/1 for classification). Nodes are
    processed first in, first out. A node is split only if it holds more than nmin cases and its
    responses are not all equal. At a node the p variables are put in a random order (Fisher-Yates
    shuffle with rng.u()); variables that are constant within the node are skipped, and the best split
    among the first m variables that vary is chosen: the one that most reduces the Gini index of the
    node (classification) or its residual sum of squares (regression). The split point is the midpoint
    between consecutive distinct values; a case goes left when x_j <= split point.

    Returns a dict of lists: feat (-1 for a leaf), thr, left, right, value (mean response of the cases
    in the node: the class-1 proportion for classification), n (number of cases), gain (the decrease
    in node impurity times the node size, for importance)."""
    p = len(X[0])
    T = {"feat": [], "thr": [], "left": [], "right": [], "value": [], "n": [], "gain": []}

    def new_node(idx):
        s = 0.0
        for i in idx:
            s += y[i]
        for key, v in (("feat", -1), ("thr", 0.0), ("left", -1), ("right", -1), ("value", s / len(idx)),
                       ("n", len(idx)), ("gain", 0.0)):
            T[key].append(v)
        return len(T["feat"]) - 1

    queue = [(new_node(rows), rows)]
    head = 0
    while head < len(queue):
        k, idx = queue[head]
        head += 1
        n = len(idx)
        if n <= nmin:
            continue
        y0 = y[idx[0]]
        if all(y[i] == y0 for i in idx):
            continue
        order = list(range(p))
        for i in range(p - 1, 0, -1):
            j = int(rng.u() * (i + 1))
            order[i], order[j] = order[j], order[i]
        tot = 0.0
        for i in idx:
            tot += y[i]
        best, bj, bt, tried = -math.inf, -1, 0.0, 0
        for j in order:
            if tried >= m:
                break
            o = sorted(idx, key=lambda i: X[i][j])
            if not X[o[n - 1]][j] > X[o[0]][j]:
                continue                       # constant in this node: skipped, not counted
            tried += 1
            sl = 0.0
            for kk in range(n - 1):
                sl += y[o[kk]]
                a, b = X[o[kk]][j], X[o[kk + 1]][j]
                if b > a:
                    nl = kk + 1
                    nr = n - nl
                    sr = tot - sl
                    if task == "class":
                        g = -sl * (nl - sl) / nl - sr * (nr - sr) / nr
                    else:
                        g = sl * sl / nl + sr * sr / nr
                    if g > best:
                        best, bj = g, j
                        bt = a / 2.0 + b / 2.0
                        if bt == b:
                            bt = a
        if bj < 0:
            continue
        L = [i for i in idx if X[i][bj] <= bt]
        R = [i for i in idx if X[i][bj] > bt]
        if task == "class":   # n * Gini = 2 n1 n0 / n; the decrease of n * Gini
            gain = 2.0 * (tot * (n - tot) / n + best)
        else:                 # decrease of the residual sum of squares
            gain = best - tot * tot / n
        T["feat"][k], T["thr"][k], T["gain"][k] = bj, bt, gain
        a, b = new_node(L), new_node(R)
        T["left"][k], T["right"][k] = a, b
        queue.append((a, L))
        queue.append((b, R))
    return {key: np.array(v) for key, v in T.items()}


def tree_apply(T, X):
    """Index of the leaf that each row of X falls into."""
    X = np.asarray(X, dtype=float)
    node = np.zeros(len(X), dtype=int)
    while True:
        f = T["feat"][node]
        inner = f >= 0
        if not inner.any():
            return node
        nd = node[inner]
        go_left = X[inner, f[inner]] <= T["thr"][nd]
        node[inner] = np.where(go_left, T["left"][nd], T["right"][nd])


def tree_predict(T, X):
    """The tree's fitted value at the rows of X (class-1 proportion for classification)."""
    return T["value"][tree_apply(T, X)]


def bootstrap_rows(rng, N):
    """N draws with replacement from 0..N-1 with the demos' generator (Math.floor(u * N))."""
    return [int(rng.u() * N) for _ in range(N)]


def own_forest(X, y, m, B, nmin=1, seed=1, task="class"):
    """Algorithm 15.1 with grow_tree(): returns the list of trees and the B x N matrix of in-bag counts.
    All random numbers (bootstrap draws, then the variable orders of the tree) come from JSRandom(seed),
    tree after tree."""
    X = np.asarray(X, dtype=float)
    Xl = X.tolist()
    yl = [float(v) for v in y]
    N = len(yl)
    rng = JSRandom(seed)
    trees, inbag = [], np.zeros((B, N), dtype=int)
    for b in range(B):
        rows = bootstrap_rows(rng, N)
        np.add.at(inbag[b], rows, 1)
        trees.append(grow_tree(Xl, yl, rows, m, nmin, rng, task))
    return trees, inbag


def forest_votes(trees, X, task="class"):
    """B x n matrix of the trees' outputs at the rows of X: class votes (0/1) or fitted values."""
    out = np.array([tree_predict(T, X) for T in trees])
    return (out > 0.5).astype(int) if task == "class" else out


def majority(votes1, ntrees):
    """Majority vote from the number of votes for class 1 among ntrees trees; ties go to class 0."""
    return (2 * np.asarray(votes1) > np.asarray(ntrees)).astype(int)


def oob_votes(trees, inbag, X, task="class"):
    """Out-of-bag outputs (Section 15.3.1): for each training case, the sum of the outputs of the
    trees whose bootstrap sample does not contain it, and the number of such trees."""
    V = forest_votes(trees, X, task)
    out = inbag == 0
    return (V * out).sum(0), out.sum(0)


def proximity(trees, inbag, X, oob_only=True):
    """Proximity matrix (Section 15.3.3): for every tree, every pair of cases (out-of-bag cases only,
    if oob_only) that fall in the same leaf gets one more; the counts are divided by the number of
    trees in which both cases were eligible. Returns P (N x N, unit diagonal)."""
    X = np.asarray(X, dtype=float)
    N = len(X)
    S = np.zeros((N, N))
    C = np.zeros((N, N))
    for T, cnt in zip(trees, inbag):
        leaf = tree_apply(T, X)
        e = (cnt == 0) if oob_only else np.ones(N, bool)
        idx = np.flatnonzero(e)
        same = leaf[idx][:, None] == leaf[idx][None, :]
        S[np.ix_(idx, idx)] += same
        C[np.ix_(idx, idx)] += 1
    P = np.divide(S, C, out=np.zeros_like(S), where=C > 0)
    np.fill_diagonal(P, 1.0)
    return P


def classical_mds(D, k=2):
    """Classical (Torgerson) scaling of the dissimilarity matrix D: the top-k eigenvectors of
    -1/2 J D^2 J scaled by the square roots of their eigenvalues (as R's cmdscale)."""
    N = len(D)
    J = np.eye(N) - 1.0 / N
    Bm = -0.5 * J @ (D ** 2) @ J
    w, V = np.linalg.eigh(Bm)
    o = np.argsort(w)[::-1][:k]
    return V[:, o] * np.sqrt(np.maximum(w[o], 0)), w[np.argsort(w)[::-1]]


def rf_weights(trees, inbag, Xtrain, x0):
    """Section 15.4.3: the forest's output at x0 is sum_i w_i(x0) y_i with
    w_i(x0) = (1/B) sum_b c_bi I(x_i in leaf_b(x0)) / (number of bootstrap cases in leaf_b(x0)),
    c_bi the in-bag count of case i in tree b. The weights are non-negative and sum to one."""
    Xtrain = np.asarray(Xtrain, dtype=float)
    x0 = np.atleast_2d(np.asarray(x0, dtype=float))
    w = np.zeros(len(Xtrain))
    for T, cnt in zip(trees, inbag):
        leaf_tr = tree_apply(T, Xtrain)
        l0 = tree_apply(T, x0)[0]
        inleaf = (leaf_tr == l0) * cnt
        w += inleaf / inleaf.sum()
    return w / len(trees)


# =========================================================================== the OOB demo (JavaScript twin)
def oob_demo_data(N, p, seed, J=2, q=0.1):
    """The data of oob-error-demo.html: case after case, p uniforms for X, then one uniform u and
    Y = 1 if u < Pr(Y = 1 | x) of (15.11)."""
    rng = JSRandom(seed)
    X = np.zeros((N, p))
    y = np.zeros(N, dtype=int)
    for i in range(N):
        for j in range(p):
            X[i, j] = rng.u()
        pr = q + (1 - 2 * q) * (1.0 if X[i, :J].sum() > J / 2 else 0.0)
        y[i] = 1 if rng.u() < pr else 0
    return X, y


def oob_error_demo(N=300, noise=5, m=None, B=300, seed=1, J=2, q=0.1, ntest=500):
    """Exactly what oob-error-demo.html computes: training data from seed, test data from seed + 1000,
    the forest from seed + 2000; returns the out-of-bag and test error after each tree (the OOB error
    over the cases that have at least one out-of-bag tree so far), the single-tree test error and
    the mean fraction of trees for which a case is out of bag."""
    p = J + noise
    m = default_m(p) if m is None else m
    X, y = oob_demo_data(N, p, seed, J, q)
    Xt, yt = oob_demo_data(ntest, p, seed + 1000, J, q)
    trees, inbag = own_forest(X, y, m, B, 1, seed + 2000, "class")
    Vtr = forest_votes(trees, X)
    Vte = forest_votes(trees, Xt)
    oob = inbag == 0
    c_oob = np.cumsum(Vtr * oob, 0)
    n_oob = np.cumsum(oob, 0)
    c_te = np.cumsum(Vte, 0)
    oob_err, test_err = [], []
    for b in range(B):
        have = n_oob[b] > 0
        pred = majority(c_oob[b], n_oob[b])
        oob_err.append(float(np.mean(pred[have] != y[have])) if have.any() else float("nan"))
        test_err.append(float(np.mean(majority(c_te[b], b + 1) != yt)))
    return {"oob": np.array(oob_err), "test": np.array(test_err), "tree1": float(np.mean(Vte[0] != yt)),
            "frac_oob": float(oob.mean()), "m": m, "p": p}


# =========================================================================== forests of compiled trees
def gini_importance_tree(est):
    """Decrease of (node size x impurity) at every split of a fitted scikit-learn tree, added up by
    split variable (Gini index for classification, mean squared error for regression, so that for
    regression this is the decrease in the residual sum of squares)."""
    t = est.tree_
    L, R = t.children_left, t.children_right
    inner = L >= 0
    w = t.weighted_n_node_samples
    imp = t.impurity
    dec = w[inner] * imp[inner] - w[L[inner]] * imp[L[inner]] - w[R[inner]] * imp[R[inner]]
    out = np.zeros(est.n_features_in_)
    np.add.at(out, t.feature[inner], dec)
    return out


def sk_tree(est, task="class"):
    """A fitted scikit-learn tree in the dict form of grow_tree() (value = class-1 proportion or mean),
    so that tree_apply() and tree_predict() evaluate it. scikit-learn compares inputs in single
    precision, so evaluate it on X32(X)."""
    t = est.tree_
    if task == "class":
        v = t.value[:, 0, :]
        v = v / v.sum(1, keepdims=True)
        k = list(est.classes_).index(1) if 1 in est.classes_ else None
        value = v[:, k] if k is not None else np.zeros(t.node_count)
    else:
        value = t.value[:, 0, 0]
    return {"feat": np.where(t.children_left >= 0, t.feature, -1), "thr": t.threshold, "left": t.children_left,
            "right": t.children_right, "value": value}


def X32(X):
    """X rounded to single precision (as scikit-learn's trees see it), returned in double precision."""
    return np.asarray(X, dtype=np.float32).astype(np.float64)


def grow_forest(X, y, m, B, task="class", nmin=None, seed=0, Xte=None, yte=None, n_perm=0, metric="err"):
    """Algorithm 15.1 with scikit-learn's compiled split search. Every tree is a DecisionTree*
    (max_features = m, min_samples_split = nmin + 1, otherwise grown out) fitted to a bootstrap sample
    of the rows drawn here with numpy default_rng(seed).

    Returns a dict with, after each tree b = 1..B: 'test' (test error, or test mean absolute error /
    mean squared error for regression, see metric) and 'oob' (out-of-bag error over the cases with at
    least one out-of-bag tree); the final test predictions; 'gini' (mean impurity decrease per tree,
    by variable); and for the first n_perm trees 'perm' (n_perm x p: decrease of the tree's OOB accuracy,
    or increase of its OOB squared error, when variable j is permuted among its OOB cases)."""
    from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor
    X = np.asarray(X, dtype=float)
    X3 = X32(X)
    Xte3 = None if Xte is None else X32(Xte)
    N, p = X.shape
    nmin = (1 if task == "class" else 5) if nmin is None else nmin
    rng = np.random.default_rng(seed)
    oob_s, oob_n = np.zeros(N), np.zeros(N)
    te_s = None if Xte is None else np.zeros(len(Xte))
    test_curve, oob_curve = [], []
    gini = np.zeros(p)
    perm = np.zeros((n_perm, p))
    ntr = np.zeros(N)
    for b in range(B):
        idx = rng.integers(0, N, N)
        cls = DecisionTreeClassifier if task == "class" else DecisionTreeRegressor
        est = cls(max_features=m, min_samples_split=nmin + 1, random_state=int(rng.integers(2 ** 31 - 1)))
        est.fit(X[idx], y[idx])
        gini += gini_importance_tree(est)
        cnt = np.bincount(idx, minlength=N)
        oob = np.flatnonzero(cnt == 0)

        T = sk_tree(est, task)

        def out(Z3):
            v = tree_predict(T, Z3)
            return (v > 0.5).astype(float) if task == "class" else v
        o = out(X3[oob])
        oob_s[oob] += o
        oob_n[oob] += 1
        have = oob_n > 0
        if task == "class":
            oob_curve.append(float(np.mean(majority(oob_s[have], oob_n[have]) != y[have])))
        else:
            oob_curve.append(float(np.mean((oob_s[have] / oob_n[have] - y[have]) ** 2)))
        if Xte is not None:
            te_s += out(Xte3)
            if task == "class":
                test_curve.append(float(np.mean(majority(te_s, b + 1) != yte)))
            elif metric == "aae":
                test_curve.append(float(np.mean(np.abs(te_s / (b + 1) - yte))))
            else:
                test_curve.append(float(np.mean((te_s / (b + 1) - yte) ** 2)))
        if b < n_perm and len(oob):
            Xo, yo = X3[oob], y[oob]
            if task == "class":
                base = np.mean(o == yo)
            else:
                base = np.mean((o - yo) ** 2)
            used = np.unique(est.tree_.feature[est.tree_.children_left >= 0])
            # an unused variable changes nothing (exactly zero); the used ones are permuted one at a time,
            # all evaluated in one call of the compiled tree
            no = len(oob)
            Xbig = np.repeat(Xo[None, :, :], len(used), axis=0)
            for k, j in enumerate(used):
                Xbig[k, :, j] = Xo[rng.permutation(no), j]
            Xbig = Xbig.reshape(-1, p).astype(np.float32)
            if task == "class":
                k1 = list(est.classes_).index(1) if 1 in est.classes_ else None
                ob = (est.predict_proba(Xbig)[:, k1] > 0.5).astype(float) if k1 is not None else np.zeros(len(Xbig))
                ob = ob.reshape(len(used), no)
                perm[b, used] = base - np.mean(ob == yo[None, :], axis=1)
            else:
                ob = est.predict(Xbig).reshape(len(used), no)
                perm[b, used] = np.mean((ob - yo[None, :]) ** 2, axis=1) - base
    res = {"oob": np.array(oob_curve), "gini": gini / B, "perm": perm, "m": m, "B": B}
    if Xte is not None:
        res["test"] = np.array(test_curve)
        res["pred_test"] = majority(te_s, B) if task == "class" else te_s / B
    if task == "class":
        res["pred_oob"] = majority(oob_s, oob_n)
    return res


# =========================================================================== cached model runs
def spam_rf(m, B, n_perm=500, seed=None, drop=None, extra=None):
    """A forest on the spam data (book's split): m candidate variables, B trees, permutation
    importance from the first n_perm trees. drop: a column to leave out; extra: 'dup' (a copy of '!'
    appended) or 'noise' (three uninformative columns appended: standard normal, fair coin, and the
    CAPAVE column shuffled). Cached."""
    seed = 1500 + m if seed is None else seed
    name = "ch15_spam_m%d_B%d%s%s.pkl" % (m, B, "" if drop is None else "_drop%d" % drop, "" if extra is None else "_" + extra)

    def build():
        Xtr, ytr, Xte, yte = spam_design(drop, extra)
        r = grow_forest(Xtr, ytr, m, B, "class", 1, seed, Xte, yte, n_perm=n_perm)
        r["perm_mean"] = r["perm"].mean(0) if n_perm else None
        r["perm_se"] = r["perm"].std(0, ddof=1) / math.sqrt(n_perm) if n_perm else None
        del r["perm"]
        return r
    return _cache(name, build)


def spam_design(drop=None, extra=None):
    """The spam matrices, optionally without column `drop` or with extra columns (see spam_rf)."""
    Xtr, ytr, Xte, yte = spam()
    names = list(SPAM_NAMES)
    if extra == "dup":
        k = SPAM_NAMES.index("!")
        Xtr, Xte = np.column_stack([Xtr, Xtr[:, k]]), np.column_stack([Xte, Xte[:, k]])
        names.append("! (copy)")
    elif extra == "noise":
        rng = np.random.default_rng(1515)
        k = SPAM_NAMES.index("CAPAVE")

        def add(X):
            n = len(X)
            return np.column_stack([X, rng.standard_normal(n), rng.integers(0, 2, n), X[rng.permutation(n), k]])
        Xtr, Xte = add(Xtr), add(Xte)
        names += ["noise: normal", "noise: coin", "noise: CAPAVE shuffled"]
    if drop is not None:
        Xtr, Xte = np.delete(Xtr, drop, 1), np.delete(Xte, drop, 1)
        names.pop(drop)
    return Xtr, ytr, Xte, yte


SPAM_MS = (1, 2, 3, 5, 7, 10, 15, 25, 40, 57)


def spam_suite():
    """Everything the spam figures, Exercise 15.6 and the importance demo use: the random forest with
    m = 7 (2500 trees), bagging (1000 trees), forests of 500 trees for the other m, the two variants,
    and the forests refitted without each of the twelve most important variables (200 trees)."""
    S = {"rf": spam_rf(7, 2500), "bag": spam_rf(57, 1000)}
    for m in SPAM_MS:
        if m not in (7, 57):
            S[m] = spam_rf(m, 500, n_perm=500 if m in (1, 3, 15) else 0)
    S[7], S[57] = S["rf"], S["bag"]
    S["dup"] = spam_rf(7, 500, extra="dup")
    S["noise"] = spam_rf(7, 500, extra="noise")
    top = np.argsort(-S["rf"]["perm_mean"])[:12]
    S["drop"] = {int(j): spam_rf(7, 200, n_perm=0, drop=int(j)) for j in top}
    S["gbm"] = spam_gbm()
    return S


def spam_gbm():
    """Gradient boosting on the spam data: 5-leaf trees, shrinkage 0.05, half-subsamples, 2500 trees
    (scikit-learn's GradientBoostingClassifier); test error after each tree. Cached."""
    def build():
        from sklearn.ensemble import GradientBoostingClassifier
        Xtr, ytr, Xte, yte = spam()
        g = GradientBoostingClassifier(max_leaf_nodes=5, max_depth=None, learning_rate=0.05, subsample=0.5,
                                       n_estimators=2500, random_state=15).fit(Xtr, ytr)
        err, last = [], None
        for pr in g.staged_predict(Xte):
            err.append(float(np.mean(pr != yte)))
            last = pr
        return {"test": np.array(err), "pred_test": last.astype(int)}
    return _cache("ch15_spam_gbm.pkl", build)


def mcnemar_pair(pa, pb, y):
    """McNemar's test (Exercise 10.6) for two classifiers' test predictions: the discordant counts
    (a right, b wrong) and (a wrong, b right) and ch10.mcnemar's statistics."""
    ra, rb = pa == y, pb == y
    n01, n10 = int(np.sum(ra & ~rb)), int(np.sum(~ra & rb))
    return (n01, n10) + tuple(ch10.mcnemar(n01, n10))


def spheres_sim(nsim=10, B=200):
    """Figure 15.2: test errors of RF-1, RF-3, bagging (m = 10), GBM-1 and GBM-6 on nsim draws of the
    simulation (10.2) (training seed 1000 + s, test seed 2000 + s). Cached."""
    def build():
        from sklearn.ensemble import HistGradientBoostingClassifier
        out = {k: [] for k in ("RF-1", "RF-3", "Bagging", "GBM-1", "GBM-6")}
        for s in range(nsim):
            X, y = nested_spheres(2000, 1000 + s)
            Xt, yt = nested_spheres(10000, 2000 + s)
            for lab, m in (("RF-1", 1), ("RF-3", 3), ("Bagging", 10)):
                out[lab].append(float(grow_forest(X, y, m, B, "class", 1, 30000 + 10 * s + m, Xt, yt)["test"][-1]))
            for lab, J in (("GBM-1", 2), ("GBM-6", 7)):
                g = HistGradientBoostingClassifier(learning_rate=0.05, max_iter=2000, max_leaf_nodes=J, min_samples_leaf=10,
                                                   early_stopping=False, random_state=s).fit(X, y)
                out[lab].append(float(np.mean(g.predict(Xt) != yt)))
            print("  spheres simulation %d:" % (s + 1), {k: round(v[-1], 4) for k, v in out.items()})
        return {k: np.array(v) for k, v in out.items()}
    return _cache("ch15_spheres_n%d_B%d.pkl" % (nsim, B), build)


def california_runs(B=500, M=1000):
    """Figure 15.3: test average absolute error against the number of trees for random forests with
    m = 2 and m = 6 (B trees, n_min = 5) and boosting with 5- and 7-leaf trees (shrinkage 0.05, M trees,
    squared-error loss, histogram-based). Cached."""
    def build():
        from sklearn.ensemble import HistGradientBoostingRegressor
        Xtr, ytr, Xte, yte = california()
        out = {}
        for m in (2, 6):
            r = grow_forest(Xtr, ytr, m, B, "reg", 5, 3100 + m, Xte, yte, metric="aae")
            out["RF m=%d" % m] = {"aae": r["test"], "abs": np.abs(r["pred_test"] - yte)}
        for d in (4, 6):
            g = HistGradientBoostingRegressor(learning_rate=0.05, max_iter=M, max_leaf_nodes=d + 1, min_samples_leaf=10,
                                              early_stopping=False, random_state=d).fit(Xtr, ytr)
            curve, last = [], None
            for pr in g.staged_predict(Xte):
                curve.append(float(np.mean(np.abs(pr - yte))))
                last = pr
            out["GBM depth=%d" % d] = {"aae": np.array(curve), "abs": np.abs(last - yte)}
        out["median"] = float(np.mean(np.abs(yte - np.median(ytr))))
        return out
    return _cache("ch15_california_B%d_M%d.pkl" % (B, M), build)


NOISE_SETTINGS = (5, 25, 50, 100, 150)


def noise_vars_sim(nsim=15, B=200, gbm=(4, 0.02, 300)):
    """Figure 15.7: the model (15.11) with J = 2, q = 0.1 and 2 + k inputs for k in NOISE_SETTINGS;
    training sets of 300 and test sets of 500; random forest with m = floor(sqrt(p)) and B trees,
    gradient boosting with gbm = (leaves, shrinkage, trees). Cached."""
    def build():
        from sklearn.ensemble import HistGradientBoostingClassifier
        out = {}
        for k in NOISE_SETTINGS:
            p = 2 + k
            rf, gb = [], []
            for s in range(nsim):
                rng = np.random.default_rng(70000 + 100 * k + s)
                X, y, _ = mease_wyner(300, p, rng)
                Xt, yt, _ = mease_wyner(500, p, rng)
                rf.append(float(grow_forest(X, y, default_m(p), B, "class", 1, 71000 + 100 * k + s, Xt, yt)["test"][-1]))
                g = HistGradientBoostingClassifier(learning_rate=gbm[1], max_iter=gbm[2], max_leaf_nodes=gbm[0], min_samples_leaf=5,
                                                   early_stopping=False, random_state=s).fit(X, y)
                gb.append(float(np.mean(g.predict(Xt) != yt)))
            out[k] = {"rf": np.array(rf), "gbm": np.array(gb), "prob": prob_relevant(p, 2, default_m(p))}
            print("  (2, %d): RF %.3f, GBM %.3f" % (k, np.mean(rf), np.mean(gb)))
        return out
    return _cache("ch15_noisevars_n%d_B%d_g%d_%g_%d.pkl" % ((nsim, B) + tuple(gbm)), build)


NODE_SIZES = (50, 30, 20, 10, 5)


def nodesize_sim(nsim=30, B=200, N=500):
    """Figure 15.8: test mean squared error (against new responses) of regression forests with
    minimum node sizes NODE_SIZES on the model sim_additive2 (m = 4). Cached."""
    def build():
        out = {n: [] for n in NODE_SIZES}
        for s in range(nsim):
            rng = np.random.default_rng(80000 + s)
            X, y, _ = sim_additive2(N, rng)
            Xt, yt, _ = sim_additive2(2000, rng)
            for n in NODE_SIZES:
                out[n].append(float(grow_forest(X, y, 4, B, "reg", n, 81000 + 100 * s + n, Xt, yt)["test"][-1]))
        return {n: np.array(v) for n, v in out.items()}
    return _cache("ch15_nodesize_n%d_B%d.pkl" % (nsim, B), build)


DECOR_MS = (1, 4, 7, 10, 13, 19, 25, 31, 37, 43, 49, 50)


def decorrelation_sim(n_rel=None, R=500, B=10, ms=DECOR_MS, N=100, p=50, ntest=600, seed=15):
    """Section 15.4: R training sets from the model (15.8) (n_rel relevant inputs, or all p), and for
    each m in ms, B random-forest regression trees per training set (n_min = 5) evaluated at ntest
    fixed test points; also one tree grown to the whole training set with all p variables.

    Per m and test point x it returns the estimates (notes, Filling the gap 15.5):
      W = E_Z Var(T | Z), mean over Z of the within-Z sample variance of the B trees (divisor B - 1);
      V = Var_Z f_rf(x) = s^2 - W / B, with s^2 the sample variance over Z of the B-tree average;
      total = V + W (the variance (15.7) of one tree), rho = V / total (15.6);
      bias2 = (mu(x) - mean over Z of the B-tree average)^2 - s^2 / R;  mse = bias2 + V;
      varb[b-1] = sample variance over Z of the average of the first b trees (b = 1..B), whose
      expectation is V + W / b, (15.1).
    Cached."""
    def build():
        from sklearn.tree import DecisionTreeRegressor
        Xt = np.random.default_rng(seed).standard_normal((ntest, p))
        r_ = p if n_rel is None else n_rel
        mu = Xt[:, :r_].sum(1) / math.sqrt(r_)
        S1 = {m: np.zeros(ntest) for m in ms}
        S2 = {m: np.zeros(ntest) for m in ms}
        Wsum = {m: np.zeros(ntest) for m in ms}
        Vb1 = {m: np.zeros((B, ntest)) for m in ms}
        Vb2 = {m: np.zeros((B, ntest)) for m in ms}
        T1, T2 = np.zeros(ntest), np.zeros(ntest)
        for r in range(R):
            rng = np.random.default_rng([seed, r])
            X, y, _ = sim_linear(N, rng, p, n_rel)
            t0 = DecisionTreeRegressor(min_samples_split=6, random_state=r).fit(X, y).predict(Xt)
            T1 += t0
            T2 += t0 ** 2
            for m in ms:
                P = np.empty((B, ntest))
                for b in range(B):
                    idx = rng.integers(0, N, N)
                    P[b] = DecisionTreeRegressor(max_features=m, min_samples_split=6,
                                                 random_state=int(rng.integers(2 ** 31 - 1))).fit(X[idx], y[idx]).predict(Xt)
                f = P.mean(0)
                S1[m] += f
                S2[m] += f ** 2
                Wsum[m] += P.var(0, ddof=1)
                cm = np.cumsum(P, 0) / np.arange(1, B + 1)[:, None]
                Vb1[m] += cm
                Vb2[m] += cm ** 2
            if (r + 1) % 100 == 0:
                print("  decorrelation simulation: %d of %d training sets" % (r + 1, R))
        out = {"ms": np.array(ms), "mu": mu, "R": R, "B": B, "N": N, "p": p, "n_rel": n_rel}
        for m in ms:
            mean = S1[m] / R
            s2 = (S2[m] - R * mean ** 2) / (R - 1)
            W = Wsum[m] / R
            V = s2 - W / B
            vb = (Vb2[m] - R * (Vb1[m] / R) ** 2) / (R - 1)
            bias2 = (mu - mean) ** 2 - s2 / R
            out[m] = {"W": W, "V": V, "total": V + W, "rho": V / (V + W), "bias2": bias2, "mse": bias2 + V,
                      "varb": vb, "mean": mean}
        tm = T1 / R
        tv = (T2 - R * tm ** 2) / (R - 1)
        out["tree"] = {"var": tv, "bias2": (mu - tm) ** 2 - tv / R}
        return out
    tag = "all" if n_rel is None else "r%d" % n_rel
    return _cache("ch15_decor_%s_R%d_B%d.pkl" % (tag, R, B), build)


def ridge_on_sim(R=500, N=100, p=50, ntest=600, seed=15, lams=None):
    """Ridge regression (with intercept) on the same training sets as decorrelation_sim: its mean
    squared error E_Z[(f_ridge(x) - mu(x))^2] averaged over the test points, for a grid of lambda, and
    the effective degrees of freedom df(lambda) = sum d_j^2 / (d_j^2 + lambda) averaged over Z."""
    lams = np.exp(np.linspace(np.log(1.0), np.log(1000.0), 121)) if lams is None else lams
    Xt = np.random.default_rng(seed).standard_normal((ntest, p))
    mu = Xt.sum(1) / math.sqrt(p)
    mse = np.zeros(len(lams))
    df = np.zeros(len(lams))
    for r in range(R):
        rng = np.random.default_rng([seed, r])
        X, y, _ = sim_linear(N, rng, p)
        xm, ym = X.mean(0), y.mean()
        U, d, Vt = np.linalg.svd(X - xm, full_matrices=False)
        uy = U.T @ (y - ym)
        for k, lam in enumerate(lams):
            beta = Vt.T @ (d / (d ** 2 + lam) * uy)
            f = ym + (Xt - xm) @ beta
            mse[k] += np.mean((f - mu) ** 2)
            df[k] += np.sum(d ** 2 / (d ** 2 + lam))
    return {"lam": lams, "mse": mse / R, "df": df / R}


def mixture_forest(B=500, seed=15):
    """Algorithm 15.1 (own implementation) on the mixture data of Chapter 2: m = 1, n_min = 1. Cached."""
    def build():
        d = ch02.mixture()
        trees, inbag = own_forest(d["X"], d["y"], 1, B, 1, seed, "class")
        return {"trees": trees, "inbag": inbag}
    return _cache("ch15_mixture_B%d_s%d.pkl" % (B, seed), build)


def mixture_results():
    """Errors of the forest and of 3-nearest neighbours on the mixture data, and the proximity MDS."""
    d = ch02.mixture()
    F = mixture_forest()
    trees, inbag = F["trees"], F["inbag"]
    Xt, yt = ch02.mixture_test(d["means"])
    vote_tr = forest_votes(trees, d["X"]).sum(0)
    vote_te = forest_votes(trees, Xt).sum(0)
    B = len(trees)
    s_oob, n_oob = oob_votes(trees, inbag, d["X"])
    P = proximity(trees, inbag, d["X"])
    Y, eig = classical_mds(1.0 - P)
    nn = knn3(d["X"], d["y"], Xt)
    return {"d": d, "trees": trees, "inbag": inbag, "Xt": Xt, "yt": yt,
            "rf_train": float(np.mean(majority(vote_tr, B) != d["y"])), "rf_test": float(np.mean(majority(vote_te, B) != yt)),
            "rf_oob": float(np.mean(majority(s_oob, n_oob) != d["y"])),
            "knn_train": float(np.mean(knn3(d["X"], d["y"], d["X"]) != d["y"])), "knn_test": float(np.mean(nn != yt)),
            "bayes": float(ch02.bayes_error(d["means"])), "P": P, "mds": Y, "eig": eig}


def knn3(X, y, Q, k=3):
    """k-nearest-neighbour majority vote (k odd; the training point itself counts when Q contains it)."""
    from scipy.spatial import cKDTree
    _, idx = cKDTree(X).query(Q, k=k)
    return (np.asarray(y)[idx].sum(1) * 2 > k).astype(int)


# =========================================================================== figures
def _ntrees(n):
    return np.arange(1, n + 1)


def fig_15_1(out_dir=None):
    """Spam data: test error against the number of trees for bagging, random forest and boosting."""
    import matplotlib.pyplot as plt
    S = spam_suite()
    Xtr, ytr, Xte, yte = spam()
    fig, ax = plt.subplots(figsize=(5.6, 4.0))
    for r, lab, c in ((S["bag"]["test"], "Bagging (m = 57)", CYAN), (S["rf"]["test"], "Random forest (m = 7)", ORANGE),
                      (S["gbm"]["test"], "Gradient boosting (5-leaf trees)", GREEN)):
        ax.step(_ntrees(len(r)), r, where="post", color=c, lw=1.3, label=lab)
    ax.set_xlim(0, 2500)
    ax.set_ylim(0.035, 0.075)
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Test error")
    ax.set_title("Spam data")
    ax.legend(loc="upper right", frameon=False)
    fig.tight_layout()
    e = {k: float(S[k]["test"][-1]) for k in ("bag", "rf", "gbm")}
    print("  final test errors: bagging %.4f (1000 trees), random forest %.4f (2500), boosting %.4f (2500)" % (e["bag"], e["rf"], e["gbm"]))
    for a, b in (("rf", "gbm"), ("bag", "rf"), ("bag", "gbm")):
        n01, n10, x2, p, x2c, pc, ex = mcnemar_pair(S[a]["pred_test"], S[b]["pred_test"], yte)
        print("  McNemar %s vs %s: %d / %d discordant, X2 = %.2f, p = %.3f (exact p = %.3f)" % (a, b, n01, n10, x2, p, ex))
    savefig(fig, CH, "fig15-1", out_dir)


def fig_15_2(out_dir=None):
    """Nested spheres: test error of random forests (m = 1, 3), bagging and boosting over simulations."""
    import matplotlib.pyplot as plt
    R = spheres_sim()
    labs = ["RF-1", "RF-3", "Bagging", "GBM-1", "GBM-6"]
    fig, ax = plt.subplots(figsize=(5.4, 3.9))
    bp = ax.boxplot([R[k] for k in labs], patch_artist=True, widths=0.55, medianprops=dict(color="black"))
    for patch in bp["boxes"]:
        patch.set_facecolor("#9fd3e6")
    ax.set_xticks(range(1, 6))
    ax.set_xticklabels(labs)
    ax.axhline(0.0, color=RED, ls="--", lw=1)
    ax.text(3, 0.004, "Bayes error", ha="center", va="bottom", fontsize=9)
    ax.set_ylim(-0.005, 0.2)
    ax.set_ylabel("Test misclassification error")
    ax.set_title("Nested spheres")
    fig.tight_layout()
    print("  means over %d simulations:" % len(R["RF-1"]), {k: round(float(np.mean(R[k])), 4) for k in labs})
    savefig(fig, CH, "fig15-2", out_dir)


def fig_15_3(out_dir=None):
    """California housing: test average absolute error against the number of trees."""
    import matplotlib.pyplot as plt
    from scipy.stats import wilcoxon
    C = california_runs()
    fig, ax = plt.subplots(figsize=(5.6, 4.0))
    for k, c, ls in (("RF m=2", CYAN, "-"), ("RF m=6", BLUE, "-"), ("GBM depth=4", ORANGE, "-"), ("GBM depth=6", RED, "-")):
        a = C[k]["aae"]
        ax.plot(_ntrees(len(a)), a, color=c, ls=ls, lw=1.6, label=k.replace("=", " = "))
    ax.set_xlim(0, 1000)
    ax.set_ylim(0.28, 0.46)
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Test average absolute error")
    ax.set_title("California housing data")
    ax.legend(frameon=False)
    fig.tight_layout()
    msg = ", ".join("%s %.4f" % (k, C[k]["aae"][-1]) for k in ("RF m=2", "RF m=6", "GBM depth=4", "GBM depth=6"))
    print("  final test AAE:", msg, "; RF m=2 at 200 trees %.4f" % C["RF m=2"]["aae"][199])
    w = wilcoxon(C["GBM depth=4"]["abs"], C["RF m=6"]["abs"])
    print("  Wilcoxon signed-rank test, |errors| of GBM depth 4 against RF m = 6: p = %.2g (mean difference %.4f)"
          % (w.pvalue, float(np.mean(C["GBM depth=4"]["abs"] - C["RF m=6"]["abs"]))))
    savefig(fig, CH, "fig15-3", out_dir)


def fig_15_4(out_dir=None):
    """Spam data: out-of-bag error against the test error as trees are added (m = 7)."""
    import matplotlib.pyplot as plt
    r = spam_suite()["rf"]
    fig, ax = plt.subplots(figsize=(5.6, 4.0))
    ax.step(_ntrees(len(r["oob"])), r["oob"], where="post", color=GREEN, lw=1.3, label="OOB error")
    ax.step(_ntrees(len(r["test"])), r["test"], where="post", color=ORANGE, lw=1.3, label="Test error")
    ax.set_xlim(0, 2500)
    ax.set_ylim(0.04, 0.08)
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Misclassification error")
    ax.legend(frameon=False)
    fig.tight_layout()
    print("  OOB / test error at 200, 500, 2500 trees: %s / %s" % (np.round(r["oob"][[199, 499, 2499]], 4), np.round(r["test"][[199, 499, 2499]], 4)))
    savefig(fig, CH, "fig15-4", out_dir)


def fig_15_5(out_dir=None):
    """Spam data: Gini and permutation (randomization) variable importance, in percent of the largest."""
    import matplotlib.pyplot as plt
    r = spam_suite()["rf"]
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 8.6))
    for ax, v, title in ((axes[0], r["gini"], "Gini"), (axes[1], r["perm_mean"], "Randomization")):
        rel = 100 * v / v.max()
        o = np.argsort(rel)
        ax.barh(np.arange(57), rel[o], color=RED, height=0.7)
        ax.set_yticks(np.arange(57))
        ax.set_yticklabels([SPAM_NAMES[k] for k in o], fontsize=7)
        ax.set_ylim(-0.7, 56.7)
        ax.set_xlim(0, 100)
        ax.set_xlabel("Variable importance")
        ax.set_title(title)
    fig.tight_layout()
    from scipy.stats import spearmanr
    print("  top 8 Gini:", [SPAM_NAMES[k] for k in np.argsort(-r["gini"])[:8]])
    print("  top 8 permutation:", [SPAM_NAMES[k] for k in np.argsort(-r["perm_mean"])[:8]])
    print("  Spearman rank correlation %.3f; median relative importance Gini %.1f%%, permutation %.1f%%"
          % (spearmanr(r["gini"], r["perm_mean"])[0], np.median(100 * r["gini"] / r["gini"].max()),
             np.median(100 * r["perm_mean"] / r["perm_mean"].max())))
    savefig(fig, CH, "fig15-5", out_dir)


def _six_points(Y, y):
    """Six cases to label in Figure 15.6: the two most extreme cases of each class's arm of the MDS
    plot and the two cases nearest its centre."""
    c = np.median(Y, 0)
    r = np.sqrt(((Y - c) ** 2).sum(1))
    pick = []
    for k in (0, 1):
        idx = np.flatnonzero(y == k)
        far = idx[np.argsort(-r[idx])]
        pick.append(far[0])
        # the far end of the class arm in the other direction
        far2 = [i for i in far[1:] if np.dot(Y[i] - c, Y[far[0]] - c) < 0]
        pick.append(far2[0] if far2 else far[1])
    near = np.argsort(r)
    gap = 0.08 * np.ptp(Y, 0).max()
    for k in (0, 1):     # the case of each class nearest the centre (labels kept apart)
        pick.append([i for i in near if y[i] == k and min(np.sqrt(((Y[i] - Y[j]) ** 2).sum()) for j in pick) > gap][0])
    return pick


def fig_15_6(out_dir=None):
    """Mixture data: proximity plot (classical scaling of 1 - proximity) and the forest's boundary."""
    import matplotlib.pyplot as plt
    R = mixture_results()
    d, Y = R["d"], R["mds"]
    six = _six_points(Y, d["y"])
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 4.2))
    ax = axes[0]
    for k, c in ((0, ch02.MIX_BLUE), (1, ch02.MIX_ORANGE)):
        ax.scatter(Y[d["y"] == k, 0], Y[d["y"] == k, 1], s=12, color=c, lw=0)
    for t, i in enumerate(six):
        ax.annotate(str(t + 1), Y[i], fontsize=8, ha="center", va="center", bbox=dict(boxstyle="square,pad=0.15", fc="white", ec="black", lw=0.6))
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_xlabel("Dimension 1")
    ax.set_ylabel("Dimension 2")
    ax.set_title("Proximity plot")
    trees = R["trees"]

    def score(P):
        return forest_votes(trees, P).mean(0)
    ch02._mixture_panel(axes[1], d, score, "Random forest classifier")
    for t, i in enumerate(six):
        axes[1].annotate(str(t + 1), d["X"][i], fontsize=8, ha="center", va="center", bbox=dict(boxstyle="square,pad=0.15", fc="white", ec="black", lw=0.6))
    axes[1].set_xlabel("$X_1$")
    axes[1].set_ylabel("$X_2$")
    fig.tight_layout()
    print("  OOB error %.3f; leading eigenvalues of the scaling %s" % (R["rf_oob"], np.round(R["eig"][:4], 2)))
    savefig(fig, CH, "fig15-6", out_dir)


def fig_15_7(out_dir=None):
    """Random forest against boosting as noise variables are added to the model (15.11)."""
    import matplotlib.pyplot as plt
    R = noise_vars_sim()
    fig, ax = plt.subplots(figsize=(6.4, 4.2))
    pos_rf = np.arange(len(NOISE_SETTINGS)) * 3 + 1
    for data, pos, c in (([R[k]["rf"] for k in NOISE_SETTINGS], pos_rf, RED), ([R[k]["gbm"] for k in NOISE_SETTINGS], pos_rf + 1, BLUE)):
        bp = ax.boxplot(data, positions=pos, widths=0.8, patch_artist=True, medianprops=dict(color="black"))
        for patch in bp["boxes"]:
            patch.set_facecolor(c)
    ax.set_xticks(pos_rf + 0.5)
    ax.set_xticklabels(["(2, %d)" % k for k in NOISE_SETTINGS])
    ax.set_xlim(0, pos_rf[-1] + 2)
    ax.axhline(0.1, color="black", ls="--", lw=0.9)
    ax.text(pos_rf[2] + 0.5, 0.102, "Bayes error", ha="center", va="bottom", fontsize=9)
    ax.set_ylim(0.08, 0.32)
    ax.set_xlabel("Number of (relevant, noise) variables")
    ax.set_ylabel("Test misclassification error")
    top = ax.secondary_xaxis("top")
    top.set_xticks(pos_rf + 0.5)
    top.set_xticklabels(["%.2f" % R[k]["prob"] for k in NOISE_SETTINGS])
    from matplotlib.patches import Patch
    ax.legend(handles=[Patch(color=RED, label="Random forest"), Patch(color=BLUE, label="Gradient boosting")], loc="upper left", frameon=False)
    fig.tight_layout()
    for k in NOISE_SETTINGS:
        print("  (2, %d): Pr(relevant variable among candidates) %.3f, mean test error RF %.3f, GBM %.3f"
              % (k, R[k]["prob"], R[k]["rf"].mean(), R[k]["gbm"].mean()))
    savefig(fig, CH, "fig15-7", out_dir)


def fig_15_8(out_dir=None):
    """Regression forests: test mean squared error against the minimum node size."""
    import matplotlib.pyplot as plt
    R = nodesize_sim()
    fig, ax = plt.subplots(figsize=(5.2, 3.9))
    bp = ax.boxplot([R[n] for n in NODE_SIZES], patch_artist=True, widths=0.6, medianprops=dict(color="black"))
    for patch in bp["boxes"]:
        patch.set_facecolor("#5fb4e8")
    ax.set_xticks(range(1, len(NODE_SIZES) + 1))
    ax.set_xticklabels([str(n) for n in NODE_SIZES])
    ax.set_xlabel("Minimum node size")
    ax.set_ylabel("Mean squared test error")
    ax.text(0.02, 1.02, "Shallow", transform=ax.transAxes, fontsize=9)
    ax.text(0.98, 1.02, "Deep", transform=ax.transAxes, ha="right", fontsize=9)
    fig.tight_layout()
    print("  mean test MSE by node size:", {n: round(float(R[n].mean()), 4) for n in NODE_SIZES},
          " deep minus shallow, paired: %.4f (sd %.4f)" % (np.mean(R[5] - R[50]), np.std(R[5] - R[50], ddof=1)))
    savefig(fig, CH, "fig15-8", out_dir)


def fig_15_9(out_dir=None):
    """Correlation between pairs of random-forest trees at 600 test points, against m."""
    import matplotlib.pyplot as plt
    D = decorrelation_sim()
    ms = [int(m) for m in D["ms"] if m != 50]
    fig, ax = plt.subplots(figsize=(5.6, 3.9))
    bp = ax.boxplot([D[m]["rho"] for m in ms], positions=ms, widths=2.0, patch_artist=True, sym="",
                    whis=(5, 95), medianprops=dict(color="black"))
    for patch in bp["boxes"]:
        patch.set_facecolor("#e8c06e")
    ax.set_xticks(ms)
    ax.set_xticklabels([str(m) for m in ms])
    ax.set_xlim(-1, 52)
    ax.set_xlabel("Number of randomly selected splitting variables m")
    ax.set_ylabel("Correlation between trees")
    fig.tight_layout()
    print("  median rho(x) by m:", {m: round(float(np.median(D[m]["rho"])), 4) for m in D["ms"]})
    savefig(fig, CH, "fig15-9", out_dir)


def decor_summary(D):
    """Averages over the test points of the quantities of decorrelation_sim, per m."""
    ms = [int(m) for m in D["ms"]]
    out = {k: np.array([float(np.mean(D[m][k])) for m in ms]) for k in ("W", "V", "total", "bias2", "mse")}
    out["ms"] = np.array(ms)
    out["rho_med"] = np.array([float(np.median(D[m]["rho"])) for m in ms])
    out["tree_var"] = float(np.mean(D["tree"]["var"]))
    out["tree_bias2"] = float(np.mean(D["tree"]["bias2"]))
    return out


def fig_15_10(out_dir=None):
    """Simulation (15.8): variance of a single forest tree, and bias, variance and MSE of the forest."""
    import matplotlib.pyplot as plt
    D = decorrelation_sim()
    s = decor_summary(D)
    ms = s["ms"]
    keep = ms != 50
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 4.0))
    ax = axes[0]
    ax.plot(ms[keep], s["W"][keep], "o", color=GREEN, ms=4, label="Within Z")
    ax.plot(ms[keep], s["total"][keep], "o", color=ORANGE, ms=4, label="Total")
    ax.axhline(s["tree_var"], color=CYAN, lw=1)
    ax.set_xlabel("m")
    ax.set_ylabel("Variance")
    ax.set_title("Single tree")
    ax.legend(loc="lower right", frameon=True)
    ax = axes[1]
    ax.plot(ms[keep], s["mse"][keep], "o-", color=BLUE, ms=4, lw=0.6, label="Mean squared error")
    ax.plot(ms[keep], s["bias2"][keep], "o-", color=MAGENTA, ms=4, lw=0.6, label="Squared bias")
    ax.axhline(s["tree_bias2"], color=CYAN, lw=1)
    ax.set_xlabel("m")
    ax.set_ylabel("Mean squared error and squared bias")
    ax.set_title("Random forest ensemble")
    ax2 = ax.twinx()
    ax2.plot(ms[keep], s["V"][keep], "o-", color=ORANGE, ms=4, lw=0.6, label="Variance")
    ax2.set_ylabel("Variance")
    lo = min(s["bias2"][keep].min(), s["tree_bias2"]) - 0.02
    hi = s["mse"][keep].max() + 0.02
    ax.set_ylim(lo, hi + 0.05)
    ax2.set_ylim(0.0, hi + 0.05 - lo)
    h1, l1 = ax.get_legend_handles_labels()
    h2, l2 = ax2.get_legend_handles_labels()
    ax.legend(h1 + h2, l1 + l2, loc="upper center", ncol=2, fontsize=8, frameon=True)
    fig.tight_layout()
    i = int(np.argmin(s["mse"][keep]))
    print("  single tree (no bootstrap, all variables): variance %.3f, squared bias %.3f" % (s["tree_var"], s["tree_bias2"]))
    for k in range(len(ms)):
        print("   m = %2d: total %.3f within %.3f | forest variance %.3f squared bias %.3f MSE %.3f | median rho %.4f"
              % (ms[k], s["total"][k], s["W"][k], s["V"][k], s["bias2"][k], s["mse"][k], s["rho_med"][k]))
    print("  smallest MSE at m = %d" % ms[keep][i])
    Rg = ridge_on_sim()
    j = int(np.argmin(Rg["mse"]))
    print("  ridge regression: smallest MSE %.3f at lambda %.1f, df %.1f" % (Rg["mse"][j], Rg["lam"][j], Rg["df"][j]))
    savefig(fig, CH, "fig15-10", out_dir)


def fig_15_11(out_dir=None):
    """Mixture data: random forest against 3-nearest neighbours."""
    import matplotlib.pyplot as plt
    R = mixture_results()
    d, trees = R["d"], R["trees"]
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.9))

    def rf_score(P):
        return forest_votes(trees, P).mean(0)

    def knn_score(P):
        from scipy.spatial import cKDTree
        _, idx = cKDTree(d["X"]).query(P, k=3)
        return d["y"][idx].mean(1)
    for ax, sc, title, tr, te in ((axes[0], rf_score, "Random forest classifier", R["rf_train"], R["rf_test"]),
                                  (axes[1], knn_score, "3-nearest neighbors", R["knn_train"], R["knn_test"])):
        ch02._mixture_panel(ax, d, sc, title)
        ax.text(0.02, 0.02, "Training error: %.3f\nTest error:       %.3f\nBayes error:    %.3f" % (tr, te, R["bayes"]),
                transform=ax.transAxes, fontsize=8, va="bottom", bbox=dict(fc="white", ec="none", alpha=0.85))
    fig.tight_layout()
    print("  random forest: training %.3f, test %.3f, OOB %.3f; 3-NN: training %.3f, test %.3f; Bayes %.4f"
          % (R["rf_train"], R["rf_test"], R["rf_oob"], R["knn_train"], R["knn_test"], R["bayes"]))
    savefig(fig, CH, "fig15-11", out_dir)


def fig_15_s1(out_dir=None):
    """Exercise 15.6: spam data, OOB and test error of 500-tree forests against m."""
    import matplotlib.pyplot as plt
    S = spam_suite()
    oob = [S[m]["oob"][499] for m in SPAM_MS]
    te = [S[m]["test"][499] for m in SPAM_MS]
    fig, ax = plt.subplots(figsize=(5.4, 3.8))
    ax.plot(SPAM_MS, oob, "o-", color=GREEN, label="OOB error")
    ax.plot(SPAM_MS, te, "s-", color=ORANGE, label="Test error")
    ax.set_xscale("log")
    ax.set_xticks(SPAM_MS)
    ax.set_xticklabels([str(m) for m in SPAM_MS])
    ax.set_xlabel("m (log scale)")
    ax.set_ylabel("Misclassification error, 500 trees")
    ax.set_title("Spam data: sensitivity to m")
    ax.legend(frameon=False)
    fig.tight_layout()
    print("  m:", SPAM_MS)
    print("  OOB: ", np.round(oob, 4))
    print("  test:", np.round(te, 4))
    savefig(fig, CH, "fig15-s1", out_dir)


def fig_15_s2(out_dir=None):
    """Section 15.4.3: the forest's weights on the training points at two targets, against 3-NN."""
    import matplotlib.pyplot as plt
    R = mixture_results()
    d, trees, inbag = R["d"], R["trees"], R["inbag"]
    targets = np.array([[-0.8, 1.6], [1.0, 0.6]])
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.9))
    for ax, x0 in zip(axes, targets):
        w = rf_weights(trees, inbag, d["X"], x0)
        col = np.where(d["y"] == 1, ch02.MIX_ORANGE, ch02.MIX_BLUE)
        ax.scatter(d["X"][:, 0], d["X"][:, 1], s=6, color=col, alpha=0.35, lw=0)
        big = w > 0
        ax.scatter(d["X"][big, 0], d["X"][big, 1], s=2400 * w[big], facecolors="none", edgecolors=col[big], lw=1.2)
        nn = np.argsort(((d["X"] - x0) ** 2).sum(1))[:3]
        ax.scatter(d["X"][nn, 0], d["X"][nn, 1], marker="x", s=40, color="black", lw=1.2)
        ax.plot(*x0, marker="*", ms=13, color="black")
        ax.set_xlim(-2.75, 4.35)
        ax.set_ylim(-2.1, 3.0)
        ax.set_xticks([])
        ax.set_yticks([])
        neff = 1.0 / np.sum(w ** 2)
        ax.set_title("Target (%.1f, %.1f): %d points with weight > 0, effective number %.1f" % (x0[0], x0[1], big.sum(), neff), fontsize=9)
        print("  target %s: forest output sum w_i y_i = %.3f, vote fraction %.3f, %d points with positive weight, 1/sum w^2 = %.1f"
              % (x0, float(w @ d["y"]), float(forest_votes(trees, x0[None, :]).mean()), big.sum(), neff))
    fig.tight_layout()
    savefig(fig, CH, "fig15-s2", out_dir)


# =========================================================================== data for the demonstrations
def _r(a, d=4):
    return [round(float(v), d) for v in np.asarray(a).ravel()]


def export_decorrelation_json():
    """data/ch15-decorrelation.json for rf-decorrelation-demo.html: per scenario and m, the averages
    over the test points, the quartiles of rho(x), and the variance of the average of b trees."""
    out = {"note": "Simulation (15.8) of Hastie, Tibshirani and Friedman (2009), Section 15.4: N = 100, p = 50, "
                   "600 test points; regression trees with minimum node size 5; per training set 10 trees for each m.",
           "scenarios": []}
    for key, lab, D in (("all", "All 50 inputs relevant, model (15.8)", decorrelation_sim()),
                        ("r5", "Only 5 of the 50 inputs relevant", decorrelation_sim(n_rel=5, R=200))):
        s = decor_summary(D)
        sc = {"key": key, "label": lab, "R": int(D["R"]), "B": int(D["B"]), "ms": [int(m) for m in s["ms"]],
              "W": _r(s["W"]), "V": _r(s["V"]), "total": _r(s["total"]), "bias2": _r(s["bias2"]), "mse": _r(s["mse"]),
              "tree_var": round(s["tree_var"], 4), "tree_bias2": round(s["tree_bias2"], 4),
              "rho_q": [_r(np.percentile(D[m]["rho"], [5, 25, 50, 75, 95])) for m in s["ms"]],
              "rho_mean": _r([np.mean(D[m]["rho"]) for m in s["ms"]]),
              "varb": [_r(D[m]["varb"].mean(1)) for m in s["ms"]]}
        if key == "all":
            Rg = ridge_on_sim()
            j = int(np.argmin(Rg["mse"]))
            sc["ridge"] = {"mse": round(float(Rg["mse"][j]), 4), "df": round(float(Rg["df"][j]), 2)}
        out["scenarios"].append(sc)
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch15-decorrelation.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return out


def export_importance_json():
    """data/ch15-spam-importance.json for rf-importance-demo.html."""
    S = spam_suite()
    cfg = []
    for key, lab, r, names in [(str(m), "m = %d" % m, S[m], SPAM_NAMES) for m in (1, 3, 7, 15, 57)] + \
            [("dup", "m = 7, with a copy of '!' added", S["dup"], list(SPAM_NAMES) + ["! (copy)"]),
             ("noise", "m = 7, with three noise variables added", S["noise"],
              list(SPAM_NAMES) + ["noise: normal", "noise: coin", "noise: CAPAVE shuffled"])]:
        B = 500
        cfg.append({"key": key, "label": lab, "names": names, "gini": _r(r["gini"], 3), "perm": _r(100 * r["perm_mean"], 4),
                    "perm_se": _r(100 * r["perm_se"], 4), "test": round(float(r["test"][B - 1]), 4),
                    "oob": round(float(r["oob"][B - 1]), 4)})
    base = S["rf"]
    drop = []
    for j, r in S["drop"].items():
        drop.append({"var": SPAM_NAMES[j], "j": j, "test": round(float(r["test"][-1]), 4), "oob": round(float(r["oob"][-1]), 4)})
    out = {"note": "Spam data (book's training/test split), random forests of 500 trees; Gini importance = mean decrease of "
                   "node size x Gini index per tree; permutation importance = mean decrease of the tree's out-of-bag accuracy "
                   "(percentage points) when the variable is permuted among the out-of-bag cases.",
           "configs": cfg, "drop": drop, "full200": {"test": round(float(base["test"][199]), 4), "oob": round(float(base["oob"][199]), 4)}}
    path = os.path.join(DATA_OUT, "ch15-spam-importance.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return out


FIGURES = {"15.1": fig_15_1, "15.2": fig_15_2, "15.3": fig_15_3, "15.4": fig_15_4, "15.5": fig_15_5,
           "15.6": fig_15_6, "15.7": fig_15_7, "15.8": fig_15_8, "15.9": fig_15_9, "15.10": fig_15_10,
           "15.11": fig_15_11, "15.S1": fig_15_s1, "15.S2": fig_15_s2}

if __name__ == "__main__":
    common.run(FIGURES, CH)
    import sys
    if "--list" not in sys.argv:
        export_decorrelation_json()
        export_importance_json()
