"""Chapter 8 lab: decision trees, bagging, random forests, boosting and BART (Python version).

Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie, Tibshirani and
Taylor (2023), An Introduction to Statistical Learning with Applications in Python, Section 8.3, and
the R lab of James et al. (2021), Section 8.3.

The lab runs the analyses of ch08_lab.R on the Carseats and Boston data, with numpy, pandas, scipy and
scikit-learn. Four pieces are written out below so that every step can be read:

    RRandom     R's default random number generator (Mersenne-Twister) with set.seed(), runif() and
                sample(), so that the training sets and cross-validation folds are the R lab's own
    RTree       recursive binary splitting and cost-complexity pruning with the rules of R's tree package
                (tree(), prune.tree(), prune.misclass(), cv.tree()); scikit-learn's trees are used as well
    Forest      bagging and random forests grown like R's randomForest(), with the out-of-bag error and
                both importance measures (%IncMSE and IncNodePurity)
    BART        Bayesian additive regression trees, the birth-death sampler of Algorithm 8.3 with the
                default priors of R's BART::gbart()

Boosting uses scikit-learn's GradientBoostingRegressor with the settings of R's gbm() (gbm_like).
Run from the code/ folder:  python3 ch08_lab.py      (about two minutes)
Figures go to ../img/ch08/lab-py-*.svg and the key numbers to cache/ch08_lab_py.csv.
"""
import copy
import math
import os

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

import numpy as np
import pandas as pd
from scipy import stats

HERE = os.path.dirname(os.path.abspath(__file__))


# ======================================================================== R's random numbers
class RRandom:
    """R's default generator: Mersenne-Twister seeded by set.seed(), with R's sample().

    unif() is R's unif_rand(); sample(n, size, replace) is R's sample(n, size, replace) for R >= 3.6
    (rejection sampling of random bits). RRandom(1).sample(506, 253) is set.seed(1); sample(506, 253).
    """
    N, M = 624, 397

    def __init__(self, seed):
        s = seed & 0xffffffff
        for _ in range(50):                      # set.seed() scrambles the seed first
            s = (69069 * s + 1) & 0xffffffff
        mt = []
        for _ in range(625):
            s = (69069 * s + 1) & 0xffffffff
            mt.append(s)
        self.mt, self.mti = mt[1:], self.N

    def _genrand(self):
        mt = self.mt
        if self.mti >= self.N:
            for kk in range(self.N):
                y = (mt[kk] & 0x80000000) | (mt[(kk + 1) % self.N] & 0x7fffffff)
                mt[kk] = mt[(kk + self.M) % self.N] ^ (y >> 1) ^ (0x9908b0df if y & 1 else 0)
            self.mti = 0
        y = mt[self.mti]
        self.mti += 1
        y ^= y >> 11
        y ^= (y << 7) & 0x9d2c5680
        y ^= (y << 15) & 0xefc60000
        y ^= y >> 18
        return y * 2.3283064365386963e-10

    def unif(self):
        v = self._genrand()
        return min(max(v, 0.5 * 2.328306437080797e-10), 1.0 - 0.5 * 2.328306437080797e-10)

    def _index(self, dn):                        # R_unif_index(): a uniform integer in 0..dn-1
        bits = int(math.ceil(math.log2(dn)))
        while True:
            v = 0
            for _ in range(0, bits + 1, 16):
                v = 65536 * v + int(self.unif() * 65536)
            v &= (1 << bits) - 1
            if v < dn:
                return v

    def sample(self, n, size=None, replace=False):
        """R's sample(n, size, replace): 1-based integers."""
        size = n if size is None else size
        if replace:
            return np.array([self._index(n) + 1 for _ in range(size)])
        x, out, m = list(range(n)), [], n
        for _ in range(size):
            j = self._index(m)
            out.append(x[j] + 1)
            m -= 1
            x[j] = x[m]
        return np.array(out)


# ======================================================================== R's tree package
class RTree:
    """A regression or classification tree grown and pruned with the rules of R's tree package.

    Growing (tree()): recursive binary splitting. A node is split only if it has at least minsize = 10
    observations; the split must leave at least mincut = 5 in each child and must reduce the deviance by
    at least mindev = 1% of the deviance of the root. The deviance is the RSS for regression and
    -2 sum_k n_k log(n_k / n) for classification. A numeric input is split at the midpoint between two
    adjacent distinct values (printed with 6 significant digits, as R stores it); a factor is split by
    ordering its levels by the mean response (or the proportion of the second class) and cutting the
    ordered list, or by trying every subset of levels for three or more classes.
    Pruning (prune.tree(), prune.misclass()): the weakest-link sequence of Section 8.1.1.
    """

    def __init__(self, mincut=5, minsize=10, mindev=0.01):
        if mincut > minsize / 2:
            mincut = int(minsize // 2)
        self.mincut, self.minsize, self.mindev = max(1, mincut), max(2, minsize), mindev

    # ................................................................ deviance of a node
    @staticmethod
    def _class_dev(C):
        """-2 sum_k n_k log(n_k / n) for each row of a matrix of class counts."""
        n = C.sum(1, keepdims=True)
        with np.errstate(divide="ignore", invalid="ignore"):
            t = np.where(C > 0, C * np.log(C / n), 0.0)
        return -2 * t.sum(1)

    def _dev(self, y):
        if self.ylevels is None:
            return float(((y - y.mean()) ** 2).sum()) if len(y) else 0.0
        return self._class_dev(np.bincount(y, minlength=self.K)[None, :].astype(float))[0]

    # ................................................................ growing
    def fit(self, X, y):
        X = pd.DataFrame(X).reset_index(drop=True)
        self.names, self.kinds, self.xlevels, cols = list(X.columns), [], {}, []
        for c in self.names:
            v = X[c]
            if isinstance(v.dtype, pd.CategoricalDtype) or v.dtype == object:
                cat = pd.Categorical(v)
                self.xlevels[c] = list(cat.categories)
                cols.append(np.asarray(cat.codes, float))
                self.kinds.append("factor")
            else:
                cols.append(v.to_numpy(float))
                self.kinds.append("numeric")
        self.X = np.column_stack(cols)
        y = pd.Series(y).reset_index(drop=True)
        if isinstance(y.dtype, pd.CategoricalDtype) or y.dtype == object:
            cy = pd.Categorical(y)
            self.ylevels, self.K, self.y = list(cy.categories), len(cy.categories), np.asarray(cy.codes)
        else:
            self.ylevels, self.y = None, y.to_numpy(float)
        self.nodes, self.where = {}, np.zeros(len(self.y), int)
        self.rootdev = self._dev(self.y)
        self._grow(1, np.arange(len(self.y)))
        return self

    def _summary(self, idx):
        y = self.y[idx]
        if self.ylevels is None:
            return dict(n=len(idx), dev=self._dev(y), yval=float(y.mean()))
        c = np.bincount(y, minlength=self.K)
        # R reports the last of tied classes as the node's class
        return dict(n=len(idx), dev=self._dev(y), yval=int(self.K - 1 - np.argmax(c[::-1])), yprob=c / c.sum())

    def _split_dev_sorted(self, ys, pos):
        """Deviance of the two children for each split position (left = first pos observations)."""
        n = len(ys)
        if self.ylevels is None:                 # RSS of both sides from running sums (8.3)
            z = ys - ys.mean()
            s1, s2 = np.cumsum(z), np.cumsum(z * z)
            nl = pos.astype(float)
            sl, ql = s1[pos - 1], s2[pos - 1]
            sr, qr = s1[-1] - sl, s2[-1] - ql
            return (ql - sl ** 2 / nl) + (qr - sr ** 2 / (n - nl))
        Y = np.eye(self.K)[ys]
        Cl = np.cumsum(Y, 0)[pos - 1]
        return self._class_dev(Cl) + self._class_dev(Y.sum(0) - Cl)

    def _best_split(self, idx):
        y, n, mc, best = self.y[idx], len(idx), self.mincut, None

        def better(c):
            return best is None or c < best[0] - 1e-9 * max(1.0, abs(best[0]))
        for j, kind in enumerate(self.kinds):
            x = self.X[idx, j]
            if kind == "numeric":
                o = np.argsort(x, kind="stable")
                xs, ys = x[o], y[o]
                pos = np.arange(mc, n - mc + 1)
                pos = pos[xs[pos - 1] < xs[pos]]          # cut only between distinct values
                if not len(pos):
                    continue
                dev = self._split_dev_sorted(ys, pos)
                k = int(np.argmin(dev))
                if better(dev[k]):
                    lab = "%g" % (0.5 * (xs[pos[k] - 1] + xs[pos[k]]))
                    best = (dev[k], j, float(lab), lab)
            else:
                lev = np.unique(x).astype(int)
                if len(lev) < 2:
                    continue
                if self.ylevels is None or self.K == 2:   # order the levels, then cut the ordered list
                    score = [y[x == l].mean() if self.ylevels is None else (y[x == l] == 1).mean() for l in lev]
                    order = lev[np.argsort(score, kind="stable")]
                    cands = [set(order[:m].tolist()) for m in range(1, len(order))]
                else:                                     # every subset of levels
                    cands = [set(lev[[b for b in range(len(lev)) if mask >> b & 1]].tolist())
                             for mask in range(1, 2 ** (len(lev) - 1))]
                for left in cands:
                    inl = np.isin(x, list(left))
                    if inl.sum() < mc or n - inl.sum() < mc:
                        continue
                    dev = self._dev(y[inl]) + self._dev(y[~inl])
                    if better(dev):
                        best = (dev, j, left, None)
        return best

    def _grow(self, node, idx):
        s = self._summary(idx)
        s["leaf"] = True
        self.nodes[node] = s
        self.where[idx] = node
        if s["n"] < self.minsize:
            return
        b = self._best_split(idx)
        if b is None or s["dev"] - b[0] < self.mindev * self.rootdev:
            return
        dev, j, rule, lab = b
        x = self.X[idx, j]
        left = x < rule if self.kinds[j] == "numeric" else np.isin(x, list(rule))
        s.update(leaf=False, var=j, rule=rule, cut=lab)
        self._grow(2 * node, idx[left])
        self._grow(2 * node + 1, idx[~left])

    # ................................................................ reading the tree
    def leaves(self):
        return sorted(k for k, v in self.nodes.items() if v["leaf"])

    def split_label(self, node, side=0):
        """'Years < 4.5' (side 0) or 'Years > 4.5' (side 1), or 'ShelveLoc: Bad,Medium'."""
        s = self.nodes[node]
        nm = self.names[s["var"]]
        if self.kinds[s["var"]] == "numeric":
            return "%s %s %s" % (nm, "<>"[side], s["cut"])
        levs = self.xlevels[nm]
        x = self.X[self.where_in(node), s["var"]].astype(int)
        present = sorted(set(x.tolist()))
        chosen = [l for l in present if (l in s["rule"]) == (side == 0)]
        return "%s: %s" % (nm, ",".join(levs[l] for l in chosen))

    def where_in(self, node):
        """Training rows that pass through a node."""
        w = self.where.copy()
        out = np.zeros(len(w), bool)
        while True:
            out |= w == node
            w = w // 2
            if not (w >= node).any():
                return out

    def summary(self):
        """What summary() prints for a tree: variables used, leaves, residual mean deviance, error."""
        used = []

        def pre(k):                              # nodes in the order R prints them
            v = self.nodes[k]
            if not v["leaf"]:
                if self.names[v["var"]] not in used:
                    used.append(self.names[v["var"]])
                pre(2 * k)
                pre(2 * k + 1)
        pre(1)
        L = self.leaves()
        dev = sum(self.nodes[k]["dev"] for k in L)
        n = len(self.y)
        out = dict(used=used, size=len(L), dev=dev, rmd=dev / (n - len(L)))
        if self.ylevels is not None:
            out["errors"] = int(sum(v["n"] - round(v["yprob"][v["yval"]] * v["n"]) for k, v in self.nodes.items() if v["leaf"]))
            out["error_rate"] = out["errors"] / n
        return out

    @staticmethod
    def _depth(k):
        return int(math.floor(math.log2(k)))

    def text(self, digits=4):
        """The printed tree, one node per line, as print(tree) in R."""
        out = []

        def rec(node, label):
            s = self.nodes[node]
            yv = ("%.*g" % (digits, s["yval"])) if self.ylevels is None else self.ylevels[s["yval"]]
            extra = "" if self.ylevels is None else " (" + " ".join("%.4f" % p for p in s["yprob"]) + ")"
            out.append("%s%d) %s %d %.4g %s%s%s" % ("  " * self._depth(node), node, label, s["n"], s["dev"], yv,
                                                   extra, " *" if s["leaf"] else ""))
            if not s["leaf"]:
                rec(2 * node, self.split_label(node, 0))
                rec(2 * node + 1, self.split_label(node, 1))
        rec(1, "root")
        return "\n".join(out)

    # ................................................................ prediction
    def _encode(self, Xn):
        Xn = pd.DataFrame(Xn).reset_index(drop=True)
        cols = []
        for c, kind in zip(self.names, self.kinds):
            if kind == "factor":
                lev = self.xlevels[c]
                cols.append(np.array([lev.index(v) if v in lev else -1 for v in Xn[c].astype(object)], float))
            else:
                cols.append(Xn[c].to_numpy(float))
        return np.column_stack(cols)

    def paths(self, Xn):
        """For each new row, the nodes on its way from the root to a leaf."""
        out = []
        for row in self._encode(Xn):
            node, p = 1, [1]
            while not self.nodes[node]["leaf"]:
                s = self.nodes[node]
                v = row[s["var"]]
                go_left = v < s["rule"] if self.kinds[s["var"]] == "numeric" else int(v) in s["rule"]
                node = 2 * node + (0 if go_left else 1)
                p.append(node)
            out.append(p)
        return out

    def predict(self, Xn, type="vector", rng=None):
        """Mean (regression), class probabilities, or classes (type="class"). Like R's predict.tree(),
        type="class" breaks a tie between classes at random: pass an RRandom to draw as R does."""
        leaf = [p[-1] for p in self.paths(Xn)]
        if self.ylevels is None:
            return np.array([self.nodes[l]["yval"] for l in leaf])
        if type != "class":
            return np.array([self.nodes[l]["yprob"] for l in leaf])
        out = []
        for l in leaf:
            pr = self.nodes[l]["yprob"]
            top = np.flatnonzero(pr == pr.max())
            if len(top) > 1:
                top = [top[rng.sample(len(top), 1)[0] - 1]] if rng is not None else [np.random.choice(top)]
            out.append(self.ylevels[top[0]])
        return np.array(out, dtype=object)

    # ................................................................ cost-complexity pruning
    def _node_cost(self, method, newX=None, newy=None):
        """R(t) for every node t: deviance or number misclassified, on the training data or on new data."""
        if newX is None:
            if method == "deviance":
                return {k: v["dev"] for k, v in self.nodes.items()}
            return {k: v["n"] - round(v["yprob"][v["yval"]] * v["n"]) for k, v in self.nodes.items()}
        cost = {k: 0.0 for k in self.nodes}
        yv = np.asarray(newy, float) if self.ylevels is None else \
            [self.ylevels.index(v) for v in pd.Series(newy).astype(object)]
        for p, yi in zip(self.paths(newX), yv):
            for k in p:
                s = self.nodes[k]
                if method == "misclass":
                    cost[k] += float(s["yval"] != yi)
                elif self.ylevels is None:
                    cost[k] += (yi - s["yval"]) ** 2
                else:                            # zero probabilities are replaced by eps = 0.001
                    cost[k] += -2 * np.log(s["yprob"][yi] if s["yprob"][yi] > 0 else 0.001)
        return cost

    def prune_path(self, method="deviance", newX=None, newy=None):
        """The weakest-link sequence: at each step collapse the internal node t with the smallest
        g(t) = (R(t) - R(T_t)) / (|T_t| - 1). Returns a list of (alpha, node collapsed, leaves, cost),
        the cost being measured on new data when newX is given."""
        R = self._node_cost(method)
        Rn = R if newX is None else self._node_cost(method, newX, newy)
        leaf = {k: v["leaf"] for k, v in self.nodes.items()}

        def stats_(t):
            if leaf[t]:
                return R[t], Rn[t], 1
            a, b = stats_(2 * t), stats_(2 * t + 1)
            return a[0] + b[0], a[1] + b[1], a[2] + b[2]

        def alive(t):
            while t > 1:
                t //= 2
                if leaf[t]:
                    return False
            return True
        _, rn0, s0 = stats_(1)
        seq = [(-np.inf, None, s0, rn0)]
        while not leaf[1]:
            best, bt = None, None
            for t in sorted(q for q in self.nodes if not leaf[q] and alive(q)):
                rt, _, st = stats_(t)
                g = (R[t] - rt) / (st - 1)
                if best is None or g < best:
                    best, bt = g, t
            leaf[bt] = True
            _, rn0, s0 = stats_(1)
            seq.append((best, bt, s0, rn0))
        return seq

    def prune_sequence(self, method="deviance", k=None, newX=None, newy=None):
        """prune.tree(tree, k, newdata, method): the sizes, costs and k of the pruned sequence."""
        seq = self.prune_path(method, newX, newy)
        alpha = np.array([a for a, *_ in seq])
        size = np.array([s[2] for s in seq])
        dev = np.array([s[3] for s in seq])
        if k is None:
            ua = list(dict.fromkeys(alpha.tolist()))
            ind = np.array([(alpha <= a).sum() for a in ua]) - 1
            kk = alpha[ind].copy()
            kk[0] = -np.inf
            return dict(size=size[ind], dev=dev[ind], k=kk)
        k = np.maximum(np.asarray(k, float), -1e100)
        ind = np.array([(alpha <= a).sum() for a in k]) - 1
        return dict(size=size[ind], dev=dev[ind], k=k)

    def prune(self, best, method="deviance"):
        """prune.tree(tree, best = best): the smallest tree of the sequence with at least best leaves."""
        seq = self.prune_path(method)
        alpha = np.array([a for a, *_ in seq])
        size = np.array([s[2] for s in seq])
        ua = list(dict.fromkeys(alpha.tolist()))
        ind = np.array([(alpha <= a).sum() for a in ua]) - 1
        index = ind[(best <= size[ind]).sum() - 1]
        T = copy.deepcopy(self)
        for _, t, _, _ in seq[1:index + 1]:
            T._snip(t)
        return T

    def _snip(self, t):
        self.nodes[t]["leaf"] = True
        for k in list(self.nodes):
            a = k
            while a > t:
                a //= 2
            if a == t and k != t:
                del self.nodes[k]
        for i, w in enumerate(self.where):
            a = w
            while a > t:
                a //= 2
            if a == t:
                self.where[i] = t


def cv_tree(tree, X, y, rand, method="deviance"):
    """cv.tree(tree, rand, FUN): fold labels rand (R draws them with sample(10, n, replace = TRUE));
    on each fold a tree is grown with the default controls, pruned at the k of the full tree, and its
    deviance (or number of errors) on the held-out fold is added up."""
    init = tree.prune_sequence(method)
    X = pd.DataFrame(X).reset_index(drop=True)
    y = pd.Series(y).reset_index(drop=True)
    dev = np.zeros(len(init["k"]))
    for i in pd.unique(rand):
        tl = RTree().fit(X[rand != i], y[rand != i])
        dev += tl.prune_sequence(method, k=init["k"], newX=X[rand == i], newy=y[rand == i])["dev"]
    return dict(size=init["size"], dev=dev, k=init["k"])


def draw_tree(t, ax, digits=3, fontsize=7.5, leaf_fmt=None, color="#1f3fbf"):
    """Draw an RTree upside down, as plot(tree); text(tree, pretty = 0) in R: each split label is
    the condition for the left branch."""
    leaves = t.leaves()
    order = []

    def dfs(k):
        if t.nodes[k]["leaf"]:
            order.append(k)
        else:
            dfs(2 * k)
            dfs(2 * k + 1)
    dfs(1)
    xpos = {k: i for i, k in enumerate(order)}
    depth = max(t._depth(k) for k in leaves)

    def place(k):
        if t.nodes[k]["leaf"]:
            return xpos[k]
        xpos[k] = 0.5 * (place(2 * k) + place(2 * k + 1))
        return xpos[k]
    place(1)
    for k, s in t.nodes.items():
        x, yv = xpos[k], -t._depth(k)
        if s["leaf"]:
            lab = leaf_fmt(s) if leaf_fmt else (("%.*f" % (digits, s["yval"])) if t.ylevels is None else t.ylevels[s["yval"]])
            ax.text(x, yv - 0.12, lab, ha="center", va="top", fontsize=fontsize,
                    bbox=dict(fc="white", ec="none", pad=0.4))
        else:
            for c in (2 * k, 2 * k + 1):
                ax.plot([x, x, xpos[c]], [yv, yv - 0.55, yv - 0.55], color=color, lw=1)
                ax.plot([xpos[c], xpos[c]], [yv - 0.55, -t._depth(c)], color=color, lw=1)
            ax.text(x, yv + 0.06, t.split_label(k, 0), ha="center", va="bottom", fontsize=fontsize,
                    bbox=dict(fc="white", ec="none", pad=0.4), zorder=3)
    ax.plot([xpos[1], xpos[1]], [0, 0.0], color=color)
    ax.set_xlim(-0.7, len(order) - 0.3)
    ax.set_ylim(-depth - 0.6, 0.45)
    ax.axis("off")


# ======================================================================== bagging and random forests
class Forest:
    """Bagging (m = p) or a random forest (m < p), grown like R's randomForest().

    Each tree is grown on a bootstrap sample of the n rows (drawn with replacement), considering m
    randomly chosen inputs at every split, until the nodes are pure or have at most nodesize rows
    (5 for regression, 1 for classification), and is not pruned. The trees are scikit-learn trees.
    """

    def __init__(self, m, ntree=500, nodesize=None, classification=False, seed=0):
        self.m, self.ntree, self.classification, self.seed = m, ntree, classification, seed
        self.nodesize = nodesize if nodesize is not None else (1 if classification else 5)

    def fit(self, X, y):
        from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor
        X, y = np.asarray(X, float), np.asarray(y)
        rng = np.random.default_rng(self.seed)
        n = len(y)
        self.trees, self.inbag = [], np.zeros((self.ntree, n), int)
        Tree = DecisionTreeClassifier if self.classification else DecisionTreeRegressor
        for b in range(self.ntree):
            idx = rng.integers(0, n, n)
            self.inbag[b] = np.bincount(idx, minlength=n)
            tr = Tree(max_features=self.m, min_samples_split=self.nodesize + 1,
                      random_state=int(rng.integers(2 ** 31 - 1)))
            self.trees.append(tr.fit(X[idx], y[idx]))
        self.X, self.y = X, y
        if self.classification:
            self.classes = self.trees[0].classes_
        return self

    def tree_predictions(self, Xn):
        """B x n matrix: each tree's prediction (class index for classification)."""
        Xn = np.asarray(Xn, float)
        if self.classification:
            return np.array([np.searchsorted(self.classes, t.predict(Xn)) for t in self.trees])
        return np.array([t.predict(Xn) for t in self.trees])

    def _combine(self, P, mask=None):
        """Average (regression) or majority vote (classification) of the rows of P, optionally only
        over the trees where mask is True."""
        mask = np.ones(P.shape, bool) if mask is None else mask
        if not self.classification:
            cnt = mask.sum(0)
            return np.where(cnt > 0, (P * mask).sum(0) / np.maximum(cnt, 1), np.nan)
        votes = np.stack([((P == k) & mask).sum(0) for k in range(len(self.classes))], 1)
        return np.where(mask.sum(0) > 0, votes.argmax(1), -1)

    def predict(self, Xn):
        out = self._combine(self.tree_predictions(Xn))
        return self.classes[out] if self.classification else out

    def oob_prediction(self):
        return self._combine(self.tree_predictions(self.X), self.inbag == 0)

    def oob_error(self):
        p = self.oob_prediction()
        if self.classification:
            ok = p >= 0
            return np.mean(self.classes[p[ok]] != self.y[ok])
        return np.nanmean((p - self.y) ** 2)

    def importance(self, permute_seed=1):
        """R's importance(): %IncMSE (mean increase in out-of-bag MSE when the input is permuted among
        each tree's out-of-bag rows, divided by its standard error) and IncNodePurity (total decrease
        in RSS from splits on the input, averaged over the trees)."""
        rng = np.random.default_rng(permute_seed)
        p = self.X.shape[1]
        purity = np.zeros(p)
        diffs = np.zeros((self.ntree, p))
        for b, t in enumerate(self.trees):
            tr = t.tree_
            for nd in range(tr.node_count):
                if tr.children_left[nd] >= 0:
                    l, r = tr.children_left[nd], tr.children_right[nd]
                    w = tr.weighted_n_node_samples
                    purity[tr.feature[nd]] += w[nd] * tr.impurity[nd] - w[l] * tr.impurity[l] - w[r] * tr.impurity[r]
            oob = np.flatnonzero(self.inbag[b] == 0)
            if not len(oob) or self.classification:
                continue
            Xo, yo = self.X[oob], self.y[oob]
            base = np.mean((t.predict(Xo) - yo) ** 2)
            for j in range(p):
                Xp = Xo.copy()
                Xp[:, j] = rng.permutation(Xp[:, j])
                diffs[b, j] = np.mean((t.predict(Xp) - yo) ** 2) - base
        mean = diffs.mean(0)
        se = np.sqrt(np.maximum((diffs ** 2).mean(0) - mean ** 2, 1e-300) / self.ntree)
        return pd.DataFrame({"%IncMSE": mean / se, "IncNodePurity": purity / self.ntree})


# ======================================================================== boosting
def gbm_like(n_trees, depth=1, shrinkage=0.1, classification=False, seed=0):
    """scikit-learn's gradient boosting with the defaults of R's gbm(): interaction.depth = d splits per
    tree (max_leaf_nodes = d + 1, grown best-first), half of the training rows drawn afresh for every
    tree (bag.fraction = 0.5), at least 10 rows per leaf, squared error or Bernoulli deviance."""
    from sklearn.ensemble import GradientBoostingClassifier, GradientBoostingRegressor
    G = GradientBoostingClassifier if classification else GradientBoostingRegressor
    return G(n_estimators=n_trees, learning_rate=shrinkage, max_leaf_nodes=depth + 1, max_depth=None,
             subsample=0.5, min_samples_leaf=10, random_state=seed)


def partial_dependence(model, X, j, grid):
    """Partial dependence of the fit on input j: the average prediction over the data with input j
    set to each grid value (the other inputs are 'integrated out' over their observed values)."""
    X = np.asarray(X, float)
    out = []
    for g in grid:
        Xc = X.copy()
        Xc[:, j] = g
        out.append(model.predict(Xc).mean())
    return np.array(out)


# ======================================================================== BART
def bart_cutpoints(X, numcut=100):
    """BART's candidate cutpoints for each column: midpoints of the distinct values if there are fewer
    than numcut of them, otherwise numcut equally spaced points strictly inside the range."""
    cuts = []
    for j in range(X.shape[1]):
        xs = np.unique(X[:, j])
        if len(xs) < 2:
            cuts.append(np.array([]))
        elif len(xs) < numcut:
            cuts.append(0.5 * (xs[:-1] + xs[1:]))
        else:
            cuts.append(np.linspace(xs[0], xs[-1], numcut + 2)[1:-1])
    return cuts


class _BTree:
    """One tree of the sum: nodes in flat lists; each node keeps, for every input, the range [lo, hi)
    of cutpoint indices that are still available below it."""

    def __init__(self, ncut):
        self.var, self.cut, self.left, self.right, self.parent = [-1], [-1], [-1], [-1], [-1]
        self.depth, self.mu = [0], [0.0]
        self.lo, self.hi = [np.zeros(len(ncut), int)], [np.asarray(ncut, int).copy()]
        self.free = []

    def bots(self):
        return [i for i in range(len(self.var)) if self.left[i] == -1 and self.var[i] != -2]

    def nogs(self):           # internal nodes whose two children are both leaves
        return [i for i in range(len(self.var)) if self.left[i] != -1 and self.var[i] != -2
                and self.left[self.left[i]] == -1 and self.left[self.right[i]] == -1]

    def goodvars(self, i):
        return np.flatnonzero(self.hi[i] > self.lo[i])

    def new_node(self, parent, depth, lo, hi):
        vals = (-1, -1, -1, -1, parent, depth, 0.0, lo, hi)
        lists = (self.var, self.cut, self.left, self.right, self.parent, self.depth, self.mu, self.lo, self.hi)
        j = self.free.pop() if self.free else None
        for lst, v in zip(lists, vals):
            if j is None:
                lst.append(v)
            else:
                lst[j] = v
        return len(self.var) - 1 if j is None else j


class BART:
    """Bayesian additive regression trees (Chipman, George and McCulloch 2010): Algorithm 8.3 with the
    priors and defaults of R's BART::gbart().

    Model: y = f(x) + e, f = sum of K = 200 trees, e ~ N(0, sigma^2). Priors: a node at depth d splits
    with probability base (1 + d)^(-power) (base 0.95, power 2), on an input and a cutpoint chosen
    uniformly; each leaf value ~ N(0, tau^2) with tau = (max y - min y) / (2 k sqrt(K)), k = 2, after
    centring y at its mean; sigma^2 ~ nu lambda / chi^2_nu with nu = 3 and lambda set so that
    P(sigma < sigma_lm) = 0.9, sigma_lm the residual standard deviation of least squares.
    One iteration updates the K trees in turn: tree k is perturbed (a birth splits a leaf, a death
    merges two sibling leaves; Metropolis-Hastings with the leaf values integrated out, each child
    needing at least 5 observations), all its leaf values are then drawn from their normal posterior
    given the partial residual, and finally sigma^2 is drawn. binary=True gives probit BART
    (BART::pbart(): latent normal responses, sigma = 1, tau = 3 / (k sqrt(K)), K = 50 by default there).
    """

    def __init__(self, ntree=200, ndpost=1000, nskip=100, k=2.0, power=2.0, base=0.95, sigdf=3,
                 sigquant=0.9, numcut=100, minobs=5, binary=False, seed=0):
        self.ntree, self.ndpost, self.nskip, self.k, self.power, self.base = ntree, ndpost, nskip, k, power, base
        self.sigdf, self.sigquant, self.numcut, self.minobs = sigdf, sigquant, numcut, minobs
        self.binary, self.seed = binary, seed

    def _pgrow(self, depth, lo, hi):
        return self.base / (1.0 + depth) ** self.power if (hi > lo).any() else 0.0

    @staticmethod
    def _lml(n, s, sig2, tau2):
        """log marginal likelihood of the residuals in a leaf (n of them, sum s), the leaf value
        mu ~ N(0, tau^2) integrated out; terms that cancel in the acceptance ratio are dropped."""
        return 0.5 * np.log(sig2 / (sig2 + n * tau2)) + 0.5 * tau2 * s * s / (sig2 * (sig2 + n * tau2))

    def fit(self, X, y, Xtest=None, keep_draws=True, trace=None):
        rng = np.random.default_rng(self.seed)
        X, y = np.asarray(X, float), np.asarray(y, float)
        n, p = X.shape
        self.cuts = bart_cutpoints(X, self.numcut)
        ncut = np.array([len(c) for c in self.cuts])
        index = lambda Z: np.column_stack([np.searchsorted(self.cuts[j], Z[:, j], side="right") for j in range(p)])
        XI = index(X)                            # x < cuts[j][c]  <=>  XI[:, j] <= c
        if self.binary:
            self.offset = stats.norm.ppf(y.mean())
            tau, sig2, nu, lam = 3.0 / (self.k * np.sqrt(self.ntree)), 1.0, 1.0, 1.0
        else:
            self.offset = y.mean()
            tau = (y.max() - y.min()) / (2 * self.k * np.sqrt(self.ntree))
            if p < n:
                A = np.column_stack([np.ones(n), X])
                r = y - A @ np.linalg.lstsq(A, y, rcond=None)[0]
                sigest = np.sqrt(r @ r / (n - np.linalg.matrix_rank(A)))
            else:
                sigest = y.std(ddof=1)
            nu = self.sigdf
            lam = sigest ** 2 * stats.chi2.ppf(1 - self.sigquant, nu) / nu
            sig2 = sigest ** 2
        tau2, K = tau * tau, self.ntree
        trees = [_BTree(ncut) for _ in range(K)]
        leaf, tfit, fit = np.zeros((K, n), int), np.zeros((K, n)), np.zeros(n)
        nt = 0 if Xtest is None else len(Xtest)
        XIt = index(np.asarray(Xtest, float)) if nt else None
        leafT, tfitT, fitT = np.zeros((K, nt), int), np.zeros((K, nt)), np.zeros(nt)
        draws_tr, draws_te, sigmas, varcount = [], [], [], []
        ycen = y - self.offset
        for it in range(self.nskip + self.ndpost):
            if self.binary:                      # latent z_i ~ N(f(x_i), 1), truncated by the sign of y_i
                m = fit + self.offset
                u, c0 = rng.random(n), stats.norm.cdf(-m)
                z = np.where(y > 0, stats.norm.ppf(c0 + u * (1 - c0)), stats.norm.ppf(u * c0)) + m
                resp = z - self.offset
            else:
                resp = ycen
            for t in range(K):
                T = trees[t]
                r = resp - (fit - tfit[t])                       # partial residual, step 3(a)i
                self._move(T, leaf[t], r, XI, sig2, tau2, rng, leafT[t] if nt else None, XIt)
                L, nn = leaf[t], len(T.var)
                cnt, sm = np.bincount(L, minlength=nn), np.bincount(L, weights=r, minlength=nn)
                b = np.array(T.bots())
                a = 1.0 / tau2 + cnt[b] / sig2                     # leaf posterior precision
                mu = sm[b] / sig2 / a + rng.standard_normal(len(b)) / np.sqrt(a)
                muv = np.zeros(nn)
                muv[b] = mu
                for bi, mi in zip(b, mu):
                    T.mu[bi] = mi
                new = muv[L]
                fit += new - tfit[t]
                tfit[t] = new
                if nt:
                    newT = muv[leafT[t]]
                    fitT += newT - tfitT[t]
                    tfitT[t] = newT
            if not self.binary:
                e = ycen - fit
                sig2 = (nu * lam + e @ e) / rng.chisquare(nu + n)
            if it >= self.nskip:
                sigmas.append(np.sqrt(sig2))
                vc = np.zeros(p)
                for T in trees:
                    for i in range(len(T.var)):
                        if T.left[i] != -1 and T.var[i] >= 0:
                            vc[T.var[i]] += 1
                varcount.append(vc)
                if keep_draws:
                    draws_tr.append(fit + self.offset)
                    if nt:
                        draws_te.append(fitT + self.offset)
            if trace is not None:
                trace(it, fit + self.offset, fitT + self.offset if nt else None)
        self.sigma, self.varcount = np.array(sigmas), np.array(varcount)
        self.yhat_train = np.array(draws_tr) if keep_draws else None
        self.yhat_test = np.array(draws_te) if (keep_draws and nt) else None
        self.trees = trees
        return self

    def _move(self, T, L, r, XI, sig2, tau2, rng, LT, XIt):
        """One birth or death proposal for tree T, accepted with the Metropolis-Hastings probability."""
        bots = T.bots()
        good = [b for b in bots if len(T.goodvars(b))]
        pb = 0.0 if not good else (1.0 if len(bots) == 1 else 0.5)
        if rng.random() < pb:                                       # birth
            i = good[rng.integers(len(good))]
            gv = T.goodvars(i)
            v = gv[rng.integers(len(gv))]
            c = T.lo[i][v] + rng.integers(T.hi[i][v] - T.lo[i][v])
            inn = L == i
            gl = inn & (XI[:, v] <= c)
            gr = inn & ~gl
            nl, nr = int(gl.sum()), int(gr.sum())
            if nl < self.minobs or nr < self.minobs:
                return
            sl, sr = r[gl].sum(), r[gr].sum()
            d1 = T.depth[i] + 1
            lo_l, hi_l, lo_r, hi_r = T.lo[i].copy(), T.hi[i].copy(), T.lo[i].copy(), T.hi[i].copy()
            hi_l[v], lo_r[v] = c, c + 1
            PGn = self._pgrow(T.depth[i], T.lo[i], T.hi[i])
            PGl, PGr = self._pgrow(d1, lo_l, hi_l), self._pgrow(d1, lo_r, hi_r)
            par = T.parent[i]
            par_nog = par != -1 and T.left[T.left[par]] == -1 and T.left[T.right[par]] == -1
            nog_new = len(T.nogs()) + 1 - int(par_nog)
            good_new = len(good) - 1 + (PGl > 0) + (PGr > 0)
            PDy = 0.5 if good_new > 0 else 1.0                      # P(death) in the proposed tree
            la = (np.log(PGn) + np.log1p(-PGl) + np.log1p(-PGr) - np.log1p(-PGn)
                  + np.log(PDy) - np.log(nog_new) - np.log(pb) + np.log(len(good))
                  + self._lml(nl, sl, sig2, tau2) + self._lml(nr, sr, sig2, tau2)
                  - self._lml(nl + nr, sl + sr, sig2, tau2))
            if np.log(rng.random()) < la:
                li, ri = T.new_node(i, d1, lo_l, hi_l), T.new_node(i, d1, lo_r, hi_r)
                T.var[i], T.cut[i], T.left[i], T.right[i] = v, c, li, ri
                L[gl], L[gr] = li, ri
                if LT is not None:
                    tin = LT == i
                    tl = tin & (XIt[:, v] <= c)
                    LT[tl], LT[tin & ~tl] = li, ri
        else:                                                       # death
            nogs = T.nogs()
            i = nogs[rng.integers(len(nogs))]
            li, ri = T.left[i], T.right[i]
            gl, gr = L == li, L == ri
            nl, nr, sl, sr = int(gl.sum()), int(gr.sum()), r[gl].sum(), r[gr].sum()
            PGn = self._pgrow(T.depth[i], T.lo[i], T.hi[i])
            PGl = self._pgrow(T.depth[li], T.lo[li], T.hi[li])
            PGr = self._pgrow(T.depth[ri], T.lo[ri], T.hi[ri])
            good_new = len(good) - (li in good) - (ri in good) + 1
            PBy = 1.0 if len(bots) - 1 == 1 else 0.5                # P(birth) in the proposed tree
            la = (np.log1p(-PGn) - np.log(PGn) - np.log1p(-PGl) - np.log1p(-PGr)
                  + np.log(PBy) - np.log(good_new) - np.log(1.0 - pb) + np.log(len(nogs))
                  + self._lml(nl + nr, sl + sr, sig2, tau2)
                  - self._lml(nl, sl, sig2, tau2) - self._lml(nr, sr, sig2, tau2))
            if np.log(rng.random()) < la:
                L[gl | gr] = i
                if LT is not None:
                    LT[(LT == li) | (LT == ri)] = i
                T.var[li] = T.var[ri] = -2
                T.free += [li, ri]
                T.left[i] = T.right[i] = T.var[i] = T.cut[i] = -1


# ======================================================================== small helpers for the lab
def mse(a, b):
    return float(np.mean((np.asarray(a, float) - np.asarray(b, float)) ** 2))


def factors(df):
    """The book's CSV files store factors as strings: make them pandas categoricals (levels sorted, as R)."""
    df = df.copy()
    for c in df.columns:
        if df[c].dtype == object:
            df[c] = pd.Categorical(df[c])
    return df


def dummies(df, drop_first=True):
    """Model matrix without the intercept: numeric columns as they are, factors as 0/1 columns
    (drop_first=True drops the first level, as R's model.matrix; False keeps every level, as BART)."""
    parts = []
    for c in df.columns:
        if isinstance(df[c].dtype, pd.CategoricalDtype):
            d = pd.get_dummies(df[c], prefix=c, prefix_sep="", dtype=float)
            parts.append(d.iloc[:, 1:] if drop_first else d)
        else:
            parts.append(df[[c]].astype(float))
    return pd.concat(parts, axis=1)


def print_summary(t):
    s = t.summary()
    print("Variables actually used in tree construction:", s["used"])
    print("Number of terminal nodes:", s["size"])
    print("Residual mean deviance: %.4f = %.4f / %d" % (s["rmd"], s["dev"], len(t.y) - s["size"]))
    if "errors" in s:
        print("Misclassification error rate: %.4g = %d / %d" % (s["error_rate"], s["errors"], len(t.y)))
    return s


# ======================================================================== the Python edition's own analysis
def python_edition(keep):
    """The Python lab of James et al. (2023) on its own splits, with scikit-learn as there."""
    import sklearn.model_selection as skm
    from sklearn.ensemble import GradientBoostingRegressor as GBR
    from sklearn.ensemble import RandomForestRegressor as RF
    from sklearn.metrics import accuracy_score, log_loss
    from sklearn.tree import DecisionTreeClassifier as DTC
    from sklearn.tree import DecisionTreeRegressor as DTR
    import common
    Car = factors(common.isl_data("Carseats"))
    High = np.where(Car.Sales > 8, "Yes", "No")
    D = dummies(Car.drop(columns="Sales"))                 # the model matrix of the Python lab
    X = D.to_numpy()
    clf = DTC(criterion="entropy", max_depth=3, random_state=0).fit(X, High)
    acc, ll = accuracy_score(High, clf.predict(X)), log_loss(High, clf.predict_proba(X))
    print("depth-3 entropy tree on all 400: training accuracy %.4f, mean log loss %.4f, deviance %.2f"
          % (acc, ll, 2 * len(High) * ll))
    keep("pe_acc", acc); keep("pe_logloss", ll)
    validation = skm.ShuffleSplit(n_splits=1, test_size=200, random_state=0)
    v = skm.cross_validate(clf, D, High, cv=validation)["test_score"][0]
    Xtr, Xte, ytr, yte = skm.train_test_split(X, High, test_size=0.5, random_state=0)
    clf = DTC(criterion="entropy", random_state=0).fit(Xtr, ytr)
    full_acc, full_leaves = accuracy_score(yte, clf.predict(Xte)), clf.tree_.n_leaves
    path = clf.cost_complexity_pruning_path(Xtr, ytr)
    grid = skm.GridSearchCV(clf, {"ccp_alpha": path.ccp_alphas}, refit=True,
                            cv=skm.KFold(10, random_state=1, shuffle=True), scoring="accuracy").fit(Xtr, ytr)
    best = grid.best_estimator_
    print("validation accuracy %.3f; full tree %d leaves, test accuracy %.3f; CV-pruned %d leaves, CV accuracy %.3f, test accuracy %.3f"
          % (v, full_leaves, full_acc, best.tree_.n_leaves, grid.best_score_, accuracy_score(yte, best.predict(Xte))))
    keep("pe_val", v); keep("pe_full_acc", full_acc); keep("pe_full_leaves", full_leaves)
    keep("pe_cv_acc", grid.best_score_); keep("pe_prune_leaves", best.tree_.n_leaves)
    keep("pe_prune_acc", accuracy_score(yte, best.predict(Xte)))
    Bos = common.isl_data("Boston", index_col=0)
    Xb = Bos.drop(columns="medv").to_numpy(float)
    Xtr, Xte, ytr, yte = skm.train_test_split(Xb, Bos["medv"], test_size=0.3, random_state=0)
    reg = DTR(max_depth=3).fit(Xtr, ytr)
    path = reg.cost_complexity_pruning_path(Xtr, ytr)
    G = skm.GridSearchCV(reg, {"ccp_alpha": path.ccp_alphas}, refit=True,
                         cv=skm.KFold(5, shuffle=True, random_state=10), scoring="neg_mean_squared_error").fit(Xtr, ytr)
    out = {"tree": mse(yte, G.best_estimator_.predict(Xte))}
    out["bag100"] = mse(yte, RF(max_features=12, random_state=0).fit(Xtr, ytr).predict(Xte))
    out["bag500"] = mse(yte, RF(max_features=12, n_estimators=500, random_state=0).fit(Xtr, ytr).predict(Xte))
    out["rf6"] = mse(yte, RF(max_features=6, random_state=0).fit(Xtr, ytr).predict(Xte))
    for lr in (0.001, 0.2):
        g = GBR(n_estimators=5000, learning_rate=lr, max_depth=3, random_state=0).fit(Xtr, ytr)
        out["gbr%g" % lr] = mse(yte, g.predict(Xte))
    print("Boston, the Python edition's 70/30 split:", {k: round(v, 2) for k, v in out.items()})
    for k, v in out.items():
        keep("pe_" + k, v)


# ======================================================================== applied exercises (Section 8.4)
def exercises(keep, Bos, train, test):
    import matplotlib.pyplot as plt
    import statsmodels.api as sm
    from sklearn.neighbors import KNeighborsClassifier
    import common
    Xb, yb = Bos.drop(columns="medv").to_numpy(float), Bos["medv"].to_numpy()

    # Exercise 7: random forests on the Boston data for several m, test MSE against the number of trees
    ex7 = {}
    for m in (12, 6, 3):
        P = Forest(m, ntree=500, seed=7).fit(Xb[train], yb[train]).tree_predictions(Xb[test])
        ex7[m] = ((np.cumsum(P, 0) / np.arange(1, 501)[:, None] - yb[test]) ** 2).mean(1)
    fig, ax = plt.subplots(figsize=(6, 4))
    for m, col, lab in ((12, "orange", "m = p = 12"), (6, "blue", "m = p/2 = 6"), (3, "darkgreen", "m = 3")):
        ax.plot(np.arange(1, 501), ex7[m], color=col, label=lab)
    ax.set(xlabel="Number of trees", ylabel="Test MSE", ylim=(10, 30))
    ax.legend()
    common.savefig(fig, 8, "lab-py-ex7", formats=("svg",))
    print("Exercise 7: test MSE after 500 trees, m = 12, 6, 3:", [round(ex7[m][-1], 3) for m in (12, 6, 3)])
    keep("ex7_500", [ex7[m][-1] for m in (12, 6, 3)])

    # Exercise 8: regression trees and ensembles for Sales in Carseats
    Car = factors(common.isl_data("Carseats"))
    rng = RRandom(1)
    tr8 = rng.sample(len(Car), len(Car) // 2) - 1
    te8 = np.setdiff1d(np.arange(len(Car)), tr8)
    X8, y8 = Car.drop(columns="Sales"), Car["Sales"]
    t8 = RTree().fit(X8.iloc[tr8], y8.iloc[tr8])
    print_summary(t8)
    fig, ax = plt.subplots(figsize=(11, 6))
    draw_tree(t8, ax, digits=2, fontsize=6.5)
    common.savefig(fig, 8, "lab-py-ex8-tree", formats=("svg",))
    m8 = mse(t8.predict(X8.iloc[te8]), y8.iloc[te8])
    print("Exercise 8(b): tree with %d leaves, test MSE %.5f" % (len(t8.leaves()), m8))
    keep("ex8_size", len(t8.leaves())); keep("ex8_tree_mse", m8)
    cv8 = cv_tree(t8, X8.iloc[tr8], y8.iloc[tr8], rng.sample(10, len(tr8), replace=True))
    best8 = int(cv8["size"][np.argmin(cv8["dev"])])
    p8 = t8.prune(best8)
    print("Exercise 8(c): CV deviance", np.round(cv8["dev"], 3), "picks", best8, "leaves; pruned test MSE %.5f"
          % mse(p8.predict(X8.iloc[te8]), y8.iloc[te8]))
    keep("ex8_cv_dev", cv8["dev"]); keep("ex8_best", best8); keep("ex8_prune_mse", mse(p8.predict(X8.iloc[te8]), y8.iloc[te8]))
    D8 = dummies(X8)                                     # scikit-learn needs numbers: 0/1 columns for the factors
    Z8, Zn = D8.to_numpy(), list(D8.columns)
    bag8 = Forest(Z8.shape[1], ntree=500, seed=8).fit(Z8[tr8], y8.iloc[tr8])
    print("Exercise 8(d): bagging test MSE %.5f" % mse(bag8.predict(Z8[te8]), y8.iloc[te8]))
    print(bag8.importance().set_index(pd.Index(Zn)).round(2))
    keep("ex8_bag_mse", mse(bag8.predict(Z8[te8]), y8.iloc[te8]))
    rf8 = [mse(Forest(m, ntree=500, seed=8).fit(Z8[tr8], y8.iloc[tr8]).predict(Z8[te8]), y8.iloc[te8])
           for m in range(1, Z8.shape[1] + 1)]
    print("Exercise 8(e): random forest test MSE for m = 1..%d:" % Z8.shape[1], np.round(rf8, 3))
    keep("ex8_rf_mse", rf8)
    F8 = dummies(X8, drop_first=False).to_numpy()
    bart8 = BART(seed=8).fit(F8[tr8], y8.iloc[tr8], F8[te8])
    print("Exercise 8(f): BART test MSE %.5f" % mse(bart8.yhat_test.mean(0), y8.iloc[te8]))
    keep("ex8_bart_mse", mse(bart8.yhat_test.mean(0), y8.iloc[te8]))
    A8 = np.column_stack([np.ones(len(Z8)), Z8])            # for comparison: least squares
    lm8 = mse(A8[te8] @ np.linalg.lstsq(A8[tr8], y8.iloc[tr8], rcond=None)[0], y8.iloc[te8])
    print("Exercise 8: least squares test MSE %.5f" % lm8)
    keep("ex8_lm_mse", lm8)

    # Exercise 9: classification trees on the OJ data
    OJ = factors(common.isl_data("OJ"))
    rng = RRandom(1)
    tr9 = rng.sample(len(OJ), 800) - 1
    te9 = np.setdiff1d(np.arange(len(OJ)), tr9)
    X9, y9 = OJ.drop(columns="Purchase"), OJ["Purchase"]
    t9 = RTree().fit(X9.iloc[tr9], y9.iloc[tr9])
    s9 = print_summary(t9)
    print(t9.text())
    pred9 = t9.predict(X9.iloc[te9], "class", rng=rng)
    print(pd.crosstab(pd.Series(pred9, name="pred"), pd.Series(y9.iloc[te9].astype(str).to_numpy(), name="truth")))
    keep("ex9_size", s9["size"]); keep("ex9_train_err", s9["error_rate"])
    keep("ex9_test_err", np.mean(pred9 != y9.iloc[te9].astype(str).to_numpy()))
    cv9 = cv_tree(t9, X9.iloc[tr9], y9.iloc[tr9], rng.sample(10, 800, replace=True), method="misclass")
    print("Exercise 9(f): size", cv9["size"], "CV errors", cv9["dev"])
    keep("ex9_cv_size", cv9["size"]); keep("ex9_cv_dev", cv9["dev"])
    best9 = int(cv9["size"][np.argmin(cv9["dev"])])
    if best9 == cv9["size"].max():
        best9 = 5                                        # CV keeps the full tree: prune to five leaves instead
    p9 = t9.prune(best9, method="misclass")
    pred9p = p9.predict(X9.iloc[te9], "class", rng=rng)
    e_tr, e_te = p9.summary()["error_rate"], np.mean(pred9p != y9.iloc[te9].astype(str).to_numpy())
    print("Exercise 9: pruned to %d leaves; training error %.4f, test error %.6f" % (best9, e_tr, e_te))
    keep("ex9_best", best9); keep("ex9_prune_train_err", e_tr); keep("ex9_prune_test_err", e_te)

    # Exercise 10: boosting for log(Salary) in the Hitters data, first 200 players for training
    H = factors(common.isl_data("Hitters")).dropna().reset_index(drop=True)
    H["Salary"] = np.log(H["Salary"])
    XH = dummies(H.drop(columns="Salary"))
    Xtr, Xte = XH.iloc[:200].to_numpy(), XH.iloc[200:].to_numpy()
    ytr, yte = H["Salary"].iloc[:200].to_numpy(), H["Salary"].iloc[200:].to_numpy()
    lams = [0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2, 0.3, 0.5, 0.7, 1]
    ex10 = []
    for lam in lams:
        g = gbm_like(1000, depth=1, shrinkage=lam, seed=10).fit(Xtr, ytr)
        ex10.append((mse(g.predict(Xtr), ytr), mse(g.predict(Xte), yte)))
    ex10 = np.array(ex10)
    print(pd.DataFrame(ex10, index=lams, columns=["train", "test"]).round(5))
    keep("ex10_train", ex10[:, 0]); keep("ex10_test", ex10[:, 1])
    fig, ax = plt.subplots(1, 2, figsize=(8, 3.6))
    for a, k, lab in ((ax[0], 0, "training MSE"), (ax[1], 1, "test MSE")):
        a.plot(lams, ex10[:, k], "o-", ms=4)
        a.set(xscale="log", xlabel="shrinkage", ylabel=lab)
    common.savefig(fig, 8, "lab-py-ex10", formats=("svg",))
    A = np.column_stack([np.ones(200), Xtr])
    beta = np.linalg.lstsq(A, ytr, rcond=None)[0]
    lm_mse = mse(np.column_stack([np.ones(len(yte)), Xte]) @ beta, yte)
    mu, sd = Xtr.mean(0), Xtr.std(0, ddof=1)             # ridge with exact leave-one-out, as in the R lab
    Z, Zte, yc = (Xtr - mu) / sd, (Xte - mu) / sd, ytr - ytr.mean()
    grid = 10 ** np.linspace(-2, 4, 121)
    loo = []
    for l in grid:
        Hm = Z @ np.linalg.solve(Z.T @ Z + l * np.eye(Z.shape[1]), Z.T)
        loo.append(np.mean(((yc - Hm @ yc) / (1 - np.diag(Hm) - 1 / len(yc))) ** 2))
    lbest = grid[int(np.argmin(loo))]
    br = np.linalg.solve(Z.T @ Z + lbest * np.eye(Z.shape[1]), Z.T @ yc)
    ridge_mse = mse(ytr.mean() + Zte @ br, yte)
    print("Exercise 10(e): test MSE: boosting (shrinkage 0.01) %.6f, least squares %.6f, ridge (lambda %.4g) %.6f"
          % (ex10[lams.index(0.01), 1], lm_mse, lbest, ridge_mse))
    keep("ex10_lm_mse", lm_mse); keep("ex10_ridge_lambda", lbest); keep("ex10_ridge_mse", ridge_mse)
    g = gbm_like(1000, depth=1, shrinkage=0.01, seed=10).fit(Xtr, ytr)
    print(pd.Series(100 * g.feature_importances_, XH.columns).sort_values(ascending=False).head(5).round(3))
    bag10 = Forest(Xtr.shape[1], ntree=500, seed=10).fit(Xtr, ytr)
    print("Exercise 10(g): bagging test MSE %.6f" % mse(bag10.predict(Xte), yte))
    keep("ex10_bag_mse", mse(bag10.predict(Xte), yte))

    # Exercise 11: boosting on the Caravan data, first 1000 customers for training
    Cv = common.isl_data("Caravan")
    yC = (Cv["Purchase"] == "Yes").to_numpy(int)
    XC = Cv.drop(columns="Purchase").to_numpy(float)
    g11 = gbm_like(1000, depth=1, shrinkage=0.01, classification=True, seed=11).fit(XC[:1000], yC[:1000])
    print(pd.Series(100 * g11.feature_importances_, Cv.columns[:-1]).sort_values(ascending=False).head(6).round(3))
    p11 = g11.predict_proba(XC[1000:])[:, 1]
    print(pd.crosstab(pd.Series(p11 > 0.2, name="predicted"), pd.Series(yC[1000:], name="purchase")))
    keep("ex11_boost_prec", np.mean(yC[1000:][p11 > 0.2])); keep("ex11_boost_npred", int((p11 > 0.2).sum()))
    lg = sm.GLM(yC[:1000], sm.add_constant(XC[:1000]), family=sm.families.Binomial()).fit()
    q11 = lg.predict(sm.add_constant(XC[1000:]))
    print(pd.crosstab(pd.Series(q11 > 0.2, name="predicted"), pd.Series(yC[1000:], name="purchase")))
    keep("ex11_logit_prec", np.mean(yC[1000:][q11 > 0.2])); keep("ex11_logit_npred", int((q11 > 0.2).sum()))
    XCs = (XC - XC.mean(0)) / XC.std(0, ddof=1)
    k11 = KNeighborsClassifier(5).fit(XCs[:1000], yC[:1000]).predict(XCs[1000:])
    print(pd.crosstab(pd.Series(k11, name="predicted"), pd.Series(yC[1000:], name="purchase")))
    keep("ex11_knn_prec", np.mean(yC[1000:][k11 == 1]))

    # Exercise 12: the Auto data, mpg from the seven other numeric variables
    Au = common.isl_data("Auto", na_values="?").dropna().reset_index(drop=True)
    XA, yA = Au.iloc[:, 1:8].to_numpy(float), Au["mpg"].to_numpy(float)
    tr12 = RRandom(1).sample(len(yA), len(yA) // 2) - 1
    te12 = np.setdiff1d(np.arange(len(yA)), tr12)
    A1 = np.column_stack([np.ones(len(yA)), XA])
    b12 = np.linalg.lstsq(A1[tr12], yA[tr12], rcond=None)[0]
    ex12 = {"lm": mse(A1[te12] @ b12, yA[te12]),
            "bagging": mse(Forest(7, seed=12).fit(XA[tr12], yA[tr12]).predict(XA[te12]), yA[te12]),
            "forest": mse(Forest(2, seed=12).fit(XA[tr12], yA[tr12]).predict(XA[te12]), yA[te12]),
            "boosting": mse(gbm_like(2000, depth=2, shrinkage=0.01, seed=12).fit(XA[tr12], yA[tr12]).predict(XA[te12]), yA[te12]),
            "BART": mse(BART(seed=12).fit(XA[tr12], yA[tr12], XA[te12]).yhat_test.mean(0), yA[te12])}
    print("Exercise 12: test MSE", {k: round(v, 3) for k, v in ex12.items()})
    keep("ex12", list(ex12.values()))


# ======================================================================== the lab
def main():
    import matplotlib.pyplot as plt
    import common
    key = {}

    def keep(name, value):
        key[name] = np.atleast_1d(np.asarray(value, float)).ravel()

    # -- 8.3.1 Fitting classification trees
    Carseats = factors(common.isl_data("Carseats"))
    High = pd.Series(pd.Categorical(np.where(Carseats["Sales"] <= 8, "No", "Yes")), name="High")
    X = Carseats.drop(columns="Sales")                   # the formula High ~ . - Sales
    tree_carseats = RTree().fit(X, High)
    s = print_summary(tree_carseats)
    keep("car_size", s["size"]); keep("car_dev", s["dev"]); keep("car_err", s["error_rate"])
    fig, ax = plt.subplots(figsize=(13, 6.5))
    draw_tree(tree_carseats, ax, fontsize=6)
    common.savefig(fig, 8, "lab-py-carseats-tree", formats=("svg",))
    print("\n".join(tree_carseats.text().split("\n")[:4]))

    rng = RRandom(2)                                     # set.seed(2)
    train = rng.sample(len(Carseats), 200) - 1           # sample(1:nrow(Carseats), 200), 0-based
    test = np.setdiff1d(np.arange(len(Carseats)), train)
    tree_carseats = RTree().fit(X.iloc[train], High.iloc[train])
    tree_pred = tree_carseats.predict(X.iloc[test], type="class", rng=rng)   # ties broken as R does
    High_test = High.iloc[test].astype(str).to_numpy()
    print(pd.crosstab(pd.Series(tree_pred, name="tree.pred"), pd.Series(High_test, name="High.test")))
    keep("car_test_acc", np.mean(tree_pred == High_test))

    rng = RRandom(7)                                     # set.seed(7)
    rand = rng.sample(10, len(train), replace=True)      # the folds cv.tree() draws
    cv_carseats = cv_tree(tree_carseats, X.iloc[train], High.iloc[train], rand, method="misclass")
    print(cv_carseats)
    keep("car_cv_size", cv_carseats["size"]); keep("car_cv_dev", cv_carseats["dev"]); keep("car_cv_k", cv_carseats["k"][1:])
    fig, ax = plt.subplots(1, 2, figsize=(8, 3.6))
    ax[0].plot(cv_carseats["size"], cv_carseats["dev"], "o-", ms=4)
    ax[0].set(xlabel="size", ylabel="CV errors")
    ax[1].plot(cv_carseats["k"][1:], cv_carseats["dev"][1:], "o-", ms=4)
    ax[1].set(xlabel="k", ylabel="CV errors")
    common.savefig(fig, 8, "lab-py-carseats-cv", formats=("svg",))

    prune_carseats = tree_carseats.prune(9, method="misclass")
    fig, ax = plt.subplots(figsize=(8, 4.5))
    draw_tree(prune_carseats, ax, fontsize=8)
    common.savefig(fig, 8, "lab-py-carseats-pruned", formats=("svg",))
    tree_pred = prune_carseats.predict(X.iloc[test], type="class", rng=rng)
    print(pd.crosstab(pd.Series(tree_pred, name="tree.pred"), pd.Series(High_test, name="High.test")))
    keep("car_prune9_acc", np.mean(tree_pred == High_test))
    prune_carseats = tree_carseats.prune(14, method="misclass")
    tree_pred = prune_carseats.predict(X.iloc[test], type="class", rng=rng)
    print(pd.crosstab(pd.Series(tree_pred, name="tree.pred"), pd.Series(High_test, name="High.test")))
    keep("car_prune14_acc", np.mean(tree_pred == High_test))

    # -- 8.3.2 Fitting regression trees
    Boston = common.isl_data("Boston", index_col=0)
    rng = RRandom(1)                                     # set.seed(1)
    train = rng.sample(len(Boston), len(Boston) // 2) - 1
    test = np.setdiff1d(np.arange(len(Boston)), train)
    Xb, yb = Boston.drop(columns="medv"), Boston["medv"]
    tree_boston = RTree().fit(Xb.iloc[train], yb.iloc[train])
    s = print_summary(tree_boston)
    print(tree_boston.text())
    keep("bos_size", s["size"]); keep("bos_dev", s["dev"])
    fig, ax = plt.subplots(figsize=(7.5, 4.5))
    draw_tree(tree_boston, ax, digits=2, fontsize=8.5)
    common.savefig(fig, 8, "lab-py-boston-tree", formats=("svg",))
    cv_boston = cv_tree(tree_boston, Xb.iloc[train], yb.iloc[train], rng.sample(10, len(train), replace=True))
    print(cv_boston)
    keep("bos_cv_size", cv_boston["size"]); keep("bos_cv_dev", cv_boston["dev"])
    prune_boston = tree_boston.prune(5)
    print(prune_boston.text())
    yhat = tree_boston.predict(Xb.iloc[test])
    boston_test = yb.iloc[test].to_numpy()
    print("regression tree, test MSE: %.4f" % mse(yhat, boston_test))
    keep("bos_tree_mse", mse(yhat, boston_test)); keep("bos_prune5_mse", mse(prune_boston.predict(Xb.iloc[test]), boston_test))

    # -- 8.3.3 Bagging and random forests
    Xn, yn = Xb.to_numpy(float), yb.to_numpy(float)
    bag_boston = Forest(m=12, ntree=500, seed=1).fit(Xn[train], yn[train])
    yhat_bag = bag_boston.predict(Xn[test])
    print("bagging, 500 trees: OOB MSE %.4f, test MSE %.4f" % (bag_boston.oob_error(), mse(yhat_bag, boston_test)))
    keep("bag_mse", mse(yhat_bag, boston_test)); keep("bag_oob", bag_boston.oob_error())
    bag25 = Forest(m=12, ntree=25, seed=2).fit(Xn[train], yn[train])
    print("bagging, 25 trees, test MSE: %.4f" % mse(bag25.predict(Xn[test]), boston_test))
    keep("bag25_mse", mse(bag25.predict(Xn[test]), boston_test))
    rf_boston = Forest(m=6, ntree=500, seed=1).fit(Xn[train], yn[train])
    yhat_rf = rf_boston.predict(Xn[test])
    print("random forest, m = 6, test MSE: %.4f" % mse(yhat_rf, boston_test))
    keep("rf_mse", mse(yhat_rf, boston_test))
    imp = rf_boston.importance().set_index(Xb.columns)
    print(imp.round(3))
    keep("rf_incmse", imp["%IncMSE"]); keep("rf_purity", imp["IncNodePurity"])
    fig, ax = plt.subplots(1, 2, figsize=(8, 4))
    for a, col in zip(ax, imp.columns):
        o = imp[col].sort_values()
        a.plot(o.to_numpy(), np.arange(len(o)), "o", mfc="none")
        a.set_yticks(np.arange(len(o)), o.index)
        a.set(xlabel=col)
        a.grid(axis="y", ls=":", lw=0.6)
    common.savefig(fig, 8, "lab-py-varimp", formats=("svg",))

    # -- 8.3.4 Boosting
    boost_boston = gbm_like(5000, depth=4, shrinkage=0.1, seed=1).fit(Xn[train], yn[train])
    rel = pd.Series(100 * boost_boston.feature_importances_, Xb.columns).sort_values(ascending=False)
    print(rel.round(3))
    keep("gbm_relinf_rm", rel["rm"]); keep("gbm_relinf_lstat", rel["lstat"])
    fig, ax = plt.subplots(1, 2, figsize=(8, 3.6))
    for a, v in zip(ax, ("rm", "lstat")):
        j = list(Xb.columns).index(v)
        grid = np.linspace(Xn[train, j].min(), Xn[train, j].max(), 100)
        a.plot(grid, partial_dependence(boost_boston, Xn[train], j, grid))
        a.set(xlabel=v, ylabel="partial dependence of medv")
    common.savefig(fig, 8, "lab-py-pdp", formats=("svg",))
    yhat_boost = boost_boston.predict(Xn[test])
    print("boosting, shrinkage 0.1, test MSE: %.4f" % mse(yhat_boost, boston_test))
    keep("gbm_mse", mse(yhat_boost, boston_test))
    boost02 = gbm_like(5000, depth=4, shrinkage=0.2, seed=2).fit(Xn[train], yn[train])
    print("boosting, shrinkage 0.2, test MSE: %.4f" % mse(boost02.predict(Xn[test]), boston_test))
    keep("gbm02_mse", mse(boost02.predict(Xn[test]), boston_test))
    boost_slow = gbm_like(5000, depth=4, shrinkage=0.001, seed=1).fit(Xn[train], yn[train])
    print("boosting, shrinkage 0.001, test MSE: %.4f" % mse(boost_slow.predict(Xn[test]), boston_test))
    keep("gbm0001_mse", mse(boost_slow.predict(Xn[test]), boston_test))
    fig, ax = plt.subplots(figsize=(6, 4))
    for mdl, col, lab in ((boost_boston, "C0", "shrinkage 0.1"), (boost_slow, "C1", "shrinkage 0.001")):
        tr_err = [mse(p, yn[train]) for p in mdl.staged_predict(Xn[train])]
        te_err = [mse(p, boston_test) for p in mdl.staged_predict(Xn[test])]
        ax.plot(np.arange(1, 5001), tr_err, color=col, ls="--", lw=1, label=lab + ", training")
        ax.plot(np.arange(1, 5001), te_err, color=col, lw=1.4, label=lab + ", test")
    ax.set(xscale="log", xlabel="Number of trees", ylabel="MSE", ylim=(0, 90))
    ax.legend(fontsize=8)
    common.savefig(fig, 8, "lab-py-boost-curve", formats=("svg",))

    # -- 8.3.5 Bayesian additive regression trees
    bartfit = BART(seed=1).fit(Xn[train], yn[train], Xn[test])   # K = 200, 100 burn-in, 1000 draws
    yhat_bart = bartfit.yhat_test.mean(0)
    print("BART, test MSE: %.4f" % mse(yhat_bart, boston_test))
    keep("bart_mse", mse(yhat_bart, boston_test)); keep("bart_sigma", bartfit.sigma.mean())
    vc = pd.Series(bartfit.varcount.mean(0), Xb.columns)
    print(vc.sort_values(ascending=False).round(2))
    keep("bart_varcount", vc)

    python_edition(keep)
    exercises(keep, Boston, train, test)

    names, vals = [], []
    for k, v in key.items():
        names += [k] if len(v) == 1 else ["%s_%d" % (k, i + 1) for i in range(len(v))]
        vals += list(v)
    os.makedirs(os.path.join(HERE, "cache"), exist_ok=True)
    pd.DataFrame({"name": names, "value": vals}).to_csv(os.path.join(HERE, "cache", "ch08_lab_py.csv"),
                                                        index=False, float_format="%.10g")
    print("wrote %d numbers to cache/ch08_lab_py.csv" % len(vals))


if __name__ == "__main__":
    main()
