"""Hastie, Tibshirani and Friedman (2009), Chapter 1: Introduction.

Reproduces the data displays of Chapter 1 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning: Data Mining, Inference, and Prediction, 2nd edition (Springer, 2009), pp. 1-8,
from the book's own data sets, written from scratch with numpy, pandas and matplotlib. The functions are
meant to be read next to the lecture notes (../ch01-introduction.html):

* Example 1, email spam: load_spam reads the 4601 messages and 57 features; class_mean_table computes
  the class means of the 54 word and character frequencies and ranks them by the absolute difference
  of the means (Table 1.1) or by a two-sample t statistic; spam_rule evaluates the two illustrative
  rules of page 2; weighted_rule_search finds the thresholds of a rule of the first kind that minimise
  a cost-weighted training error.
* Example 2, prostate cancer: load_prostate reads the 97 men, 8 predictors, the response lpsa and the
  book's training/test split; ols_fit, knn_regress and prostate_fits give the training and test errors
  of the simple fits used in the notes (the mean, a least-squares line, k-nearest-neighbour averages
  and least squares on all eight predictors).
* Example 3, handwritten digits: load_zip reads the 16 x 16 ZIP code images.
* Example 4, DNA microarrays: load_nci reads the 6830 x 64 expression matrix and its labels;
  two_way_additive fits the additive model 'gene effect + sample effect' by least squares, and
  standardised_distance checks the identity between Euclidean distance and correlation.
* export_json writes the small data files read by the two browser demonstrations
  (../data/ch01-prostate.json and ../data/ch01-spam.json).

Figures reproduced: 1.1, 1.2, 1.3, and the content of Table 1.1 (printed, and written to
../data/ch01-spam.json; the notes show it as an HTML table). One supplementary figure, 1.S1
(training and test error of k-nearest-neighbour regression on the prostate data), illustrates the
notes' discussion of training versus test error. Run `python3 ch01_introduction.py --list`,
`python3 ch01_introduction.py` (all figures, about 20 seconds) or `python3 ch01_introduction.py --fig 1.1`.
Files go to ../img/ch01/.

Figures not reproduced: none. Chapter 1 has three figures and one table, all computed from data.

Settings chosen where the book gives none:
* Figure 1.2: the first six training images of each digit in zip.train (the book does not say which
  images it shows). The stored pixel values lie in [-1, 1] (the book's website rescaled the original
  0-255 grey levels); they are drawn with -1 as white and 1 as black.
* Figure 1.3: 100 genes drawn at random (numpy default_rng(2009)) from the 6830, and the 64 samples in
  a random order from the same generator; the genes are also shown in the order drawn, which is random.
  The colour scale runs from green (-2 or below) through black (0) to red (2 or above); about 3% of
  the entries shown exceed 2 in absolute value. The book's figure shows
  missing values in grey, but the data on the book's website have their missing values imputed (see
  nci.info.txt), so there is no grey here. The website file has no gene names, so rows are labelled by
  their index g1, ..., g6830.
* Figure 1.S1 and the prostate fits: the book's split (train == 'T': 67 men, 'F': 30 men); errors are
  mean squared errors; k-nearest neighbours in one input include every training point tied with the
  k-th smallest distance (see knn_regress), the convention used by the browser demonstration.
"""
import os

import numpy as np

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

import matplotlib.pyplot as plt
from matplotlib.colors import LinearSegmentedColormap

CH = 1
HERE = os.path.dirname(os.path.abspath(__file__))
JSON_DIR = os.path.normpath(os.path.join(HERE, "..", "data"))

PROSTATE_PREDICTORS = ["lcavol", "lweight", "age", "lbph", "svi", "lcp", "gleason", "pgg45"]

# The 57 features of the spam data, in the order of the columns of spam.data (spam.info.txt): 48 word
# frequencies, 6 character frequencies, and 3 statistics of runs of capital letters.
SPAM_NAMES = ("make address all 3d our over remove internet order mail receive will people report addresses "
              "free business email you credit your font 000 money hp hpl george 650 lab labs telnet 857 data "
              "415 85 technology 1999 parts pm direct cs meeting original project re edu table conference "
              "; ( [ ! $ # CAPAVE CAPMAX CAPTOT").split()
N_FREQ = 54   # the word and character frequencies (percentages); the last three columns are run lengths


# =========================================================================== data
def load_prostate():
    """Prostate data (Stamey et al. 1989): X (97 x 8), y = lpsa, boolean training mask, predictor names."""
    P = common.esl_data("prostate.data")
    X = P[PROSTATE_PREDICTORS].to_numpy(float)
    y = P["lpsa"].to_numpy(float)
    train = (P["train"] == "T").to_numpy()
    return X, y, train, list(PROSTATE_PREDICTORS)


def load_spam():
    """Spam data: X (4601 x 57), y (1 = spam, 0 = email), boolean test mask (spam.traintest == 1)."""
    A = np.loadtxt(common.esl_file("spam.data"))
    tt = np.loadtxt(common.esl_file("spam.traintest")).astype(int)
    return A[:, :57], A[:, 57].astype(int), tt == 1


def load_zip(train=True):
    """ZIP code digits: images (N x 256, values in [-1, 1], row-major 16 x 16) and labels 0..9."""
    Z = np.loadtxt(common.esl_file("zip.train.gz" if train else "zip.test.gz"))
    return Z[:, 1:], Z[:, 0].astype(int)


def load_nci():
    """NCI60 microarray data: expression matrix (6830 genes x 64 samples) and the 64 sample labels."""
    import pandas as pd
    M = pd.read_csv(common.esl_file("nci.data.csv"), index_col=0).to_numpy(float)
    with open(common.esl_file("nci.label.txt")) as f:
        labels = [s.strip() for s in f if s.strip()]
    return M, labels


# =========================================================================== Example 1: spam
def class_mean_table(X, y, k=11, by="diff"):
    """Class means of the 54 frequency features, ranked by |mean(spam) - mean(email)| (by='diff', the
    ranking of Table 1.1) or by the absolute two-sample (Welch) t statistic (by='t').

    Returns a list of (name, mean_spam, mean_email, difference, t) for the top k features."""
    F = X[:, :N_FREQ]
    s, e = F[y == 1], F[y == 0]
    ms, me = s.mean(0), e.mean(0)
    d = ms - me
    se = np.sqrt(s.var(0, ddof=1) / len(s) + e.var(0, ddof=1) / len(e))
    t = d / se
    score = np.abs(d) if by == "diff" else np.abs(t)
    order = np.argsort(-score, kind="stable")[:k]
    return [(SPAM_NAMES[j], float(ms[j]), float(me[j]), float(d[j]), float(t[j])) for j in order]


def spam_rule(X, kind, a, b):
    """The two illustrative rules of Section 'Example 1' (page 2), as 0/1 predictions (1 = spam).

    kind='box':    spam if %george < a and %you > b          (the book: a = 0.6, b = 1.5)
    kind='linear': spam if a * %you - b * %george > 0        (the book: a = 0.2, b = 0.3)"""
    g, u = X[:, SPAM_NAMES.index("george")], X[:, SPAM_NAMES.index("you")]
    if kind == "box":
        return ((g < a) & (u > b)).astype(int)
    return ((a * u - b * g) > 0).astype(int)


def confusion(pred, y):
    """Counts: email kept, email flagged as spam, spam caught, spam let through; and the error rate."""
    ee = int(np.sum((pred == 0) & (y == 0)))
    es = int(np.sum((pred == 1) & (y == 0)))
    ss = int(np.sum((pred == 1) & (y == 1)))
    se = int(np.sum((pred == 0) & (y == 1)))
    return dict(email_ok=ee, email_lost=es, spam_caught=ss, spam_missed=se, error=(es + se) / len(y))


def weighted_rule_search(X, y, cost_email=10.0, cost_spam=1.0, a_grid=None, b_grid=None):
    """Thresholds (a, b) of the box rule 'george < a and you > b' minimising the average cost
    (cost_email per good email flagged, cost_spam per spam let through) on the rows given."""
    a_grid = np.round(np.arange(0.05, 3.0001, 0.05), 2) if a_grid is None else a_grid
    b_grid = np.round(np.arange(0.0, 8.0001, 0.1), 2) if b_grid is None else b_grid
    best = None
    for a in a_grid:
        for b in b_grid:
            c = confusion(spam_rule(X, "box", a, b), y)
            cost = (cost_email * c["email_lost"] + cost_spam * c["spam_missed"]) / len(y)
            if best is None or cost < best[0] - 1e-12:
                best = (cost, float(a), float(b), c)
    return best


# =========================================================================== Example 2: prostate
def ols_fit(X, y):
    """Least squares with an intercept: returns (beta0, beta) minimising sum (y - beta0 - X beta)^2."""
    X = np.atleast_2d(np.asarray(X, float))
    if X.shape[0] != len(y):
        X = X.T
    A = np.column_stack([np.ones(len(y)), X])
    coef, *_ = np.linalg.lstsq(A, y, rcond=None)
    return coef[0], coef[1:]


def ols_predict(fit, X):
    X = np.atleast_2d(np.asarray(X, float))
    if X.shape[1] != len(fit[1]):
        X = X.T
    return fit[0] + X @ fit[1]


def knn_regress(xtr, ytr, xq, k):
    """k-nearest-neighbour average (2.14) for a single input: the mean of the training responses whose
    inputs are among the k closest to each query point. Ties at the k-th smallest distance are all
    included, so the neighbourhood N_k(x) = {i : |x_i - x| <= d_(k)} may hold more than k points; this
    makes the rule independent of the order of the data (the prostate file is sorted by lpsa, so breaking
    ties by row order would bias the averages)."""
    xtr, ytr, xq = np.asarray(xtr, float), np.asarray(ytr, float), np.atleast_1d(np.asarray(xq, float))
    out = np.empty(len(xq))
    for i, x0 in enumerate(xq):
        d = np.abs(xtr - x0)
        dk = np.sort(d)[k - 1]
        out[i] = ytr[d <= dk].mean()
    return out


def mse(a, b):
    return float(np.mean((np.asarray(a) - np.asarray(b)) ** 2))


def prostate_fits(var="lcavol", ks=range(1, 41)):
    """Training and test mean squared errors of the simple fits of the notes and the demo."""
    X, y, tr, names = load_prostate()
    te = ~tr
    j = names.index(var)
    x = X[:, j]
    out = {}
    out["null"] = (mse(y[tr], y[tr].mean()), mse(y[te], y[tr].mean()))
    f1 = ols_fit(x[tr, None], y[tr])
    out["line"] = (mse(y[tr], ols_predict(f1, x[tr, None])), mse(y[te], ols_predict(f1, x[te, None])))
    out["line_coef"] = (float(f1[0]), float(f1[1][0]))
    fa = ols_fit(X[tr], y[tr])
    out["all8"] = (mse(y[tr], ols_predict(fa, X[tr])), mse(y[te], ols_predict(fa, X[te])))
    out["all8_coef"] = (float(fa[0]),) + tuple(float(v) for v in fa[1])
    knn = []
    for k in ks:
        knn.append((k, mse(y[tr], knn_regress(x[tr], y[tr], x[tr], k)), mse(y[te], knn_regress(x[tr], y[tr], x[te], k))))
    out["knn"] = knn
    # standard error of a test-set mean squared error: sd of the squared errors / sqrt(N_test)
    r2 = (y[te] - ols_predict(fa, X[te])) ** 2
    out["all8_test_se"] = float(r2.std(ddof=1) / np.sqrt(te.sum()))
    r0 = (y[te] - y[tr].mean()) ** 2
    out["null_test_se"] = float(r0.std(ddof=1) / np.sqrt(te.sum()))
    return out


# =========================================================================== Example 4: microarray
def two_way_additive(M):
    """Least-squares fit of x_ij = mu + alpha_i + beta_j (sum alpha = sum beta = 0) to a complete
    matrix: returns mu, alpha (row effects), beta (column effects), and the shares of the total sum of
    squares about the grand mean explained by rows, by columns, and left in the residual (interaction)."""
    mu = M.mean()
    a = M.mean(1) - mu
    b = M.mean(0) - mu
    R = M - mu - a[:, None] - b[None, :]
    tot = ((M - mu) ** 2).sum()
    n, p = M.shape
    return mu, a, b, dict(rows=p * (a ** 2).sum() / tot, cols=n * (b ** 2).sum() / tot, resid=(R ** 2).sum() / tot)


def standardised_distance(u, v):
    """Squared Euclidean distance between two profiles after centring and scaling each to unit
    (population) variance, and 2 p (1 - r) with r their correlation: the two numbers are equal."""
    p = len(u)
    zu = (u - u.mean()) / u.std()
    zv = (v - v.mean()) / v.std()
    r = np.corrcoef(u, v)[0, 1]
    return float(((zu - zv) ** 2).sum()), float(2 * p * (1 - r))


# =========================================================================== figures
def fig_1_1(out_dir=None):
    """Scatterplot matrix of the prostate cancer data (lpsa first, then the eight predictors)."""
    X, y, tr, names = load_prostate()
    V = np.column_stack([y, X])
    labels = ["lpsa"] + names
    p = V.shape[1]
    col = "#a24bd6"
    fig, axes = plt.subplots(p, p, figsize=(9.0, 9.0))
    lims = []
    for j in range(p):
        lo, hi = V[:, j].min(), V[:, j].max()
        pad = 0.08 * (hi - lo)
        lims.append((lo - pad, hi + pad))
    for i in range(p):
        for j in range(p):
            ax = axes[i, j]
            ax.set_xlim(lims[j])
            ax.set_ylim(lims[i])
            ax.tick_params(length=2, labelsize=6.5, pad=1)
            ax.set_xticks([])
            ax.set_yticks([])
            if i == j:
                ax.text(0.5, 0.5, labels[i], transform=ax.transAxes, ha="center", va="center", fontsize=10)
            else:
                ax.scatter(V[:, j], V[:, i], s=6, facecolors="none", edgecolors=col, linewidths=0.6)
            # R-style alternating tick labels on the outer edges
            if i == 0 and j % 2 == 1:
                ax.xaxis.set_ticks_position("top")
                ax.set_xticks(_nice_ticks(lims[j]))
            if i == p - 1 and j % 2 == 0:
                ax.set_xticks(_nice_ticks(lims[j]))
            if j == 0 and i % 2 == 1:
                ax.set_yticks(_nice_ticks(lims[i]))
            if j == p - 1 and i % 2 == 0:
                ax.yaxis.set_ticks_position("right")
                ax.set_yticks(_nice_ticks(lims[i]))
    fig.subplots_adjust(wspace=0.06, hspace=0.06, left=0.05, right=0.95, bottom=0.05, top=0.95)
    savefig(fig, CH, "fig1-1", out_dir)
    C = np.corrcoef(V.T)
    print("  correlation of lpsa with " + ", ".join("%s %.3f" % (labels[j], C[0, j]) for j in range(1, p)))


def _nice_ticks(lim):
    from matplotlib.ticker import MaxNLocator
    t = MaxNLocator(nbins=3, steps=[1, 2, 2.5, 5, 10]).tick_values(*lim)
    return [v for v in t if lim[0] <= v <= lim[1]]


def fig_1_2(out_dir=None):
    """Examples of handwritten digits: the first six training images of each class 0-9."""
    Z, lab = load_zip(train=True)
    rows, gap = 6, 2
    W = 10 * 16 + 11 * gap
    H = rows * 16 + (rows + 1) * gap
    img = np.full((H, W, 3), 1.0)
    green = np.array([0.55, 0.85, 0.45])
    img[:, :, :] = green
    for d in range(10):
        idx = np.flatnonzero(lab == d)[:rows]
        for r, i in enumerate(idx):
            g = 1.0 - (Z[i].reshape(16, 16) + 1.0) / 2.0          # -1 -> white, 1 -> black
            y0, x0 = gap + r * (16 + gap), gap + d * (16 + gap)
            img[y0:y0 + 16, x0:x0 + 16, :] = g[:, :, None]
    fig, ax = plt.subplots(figsize=(6.0, 6.0 * H / W))
    ax.imshow(img, interpolation="nearest")
    ax.set_axis_off()
    savefig(fig, CH, "fig1-2", out_dir)
    print("  training images per digit:", np.bincount(lab).tolist())


GREEN_RED = LinearSegmentedColormap.from_list("green_black_red", [(0.0, (0.0, 1.0, 0.0)), (0.5, (0.0, 0.0, 0.0)),
                                                                   (1.0, (1.0, 0.0, 0.0))])


def heatmap_selection(seed=2009, n_rows=100):
    """The random genes and the random sample order of Figure 1.3."""
    M, labels = load_nci()
    rng = np.random.default_rng(seed)
    rows = rng.choice(M.shape[0], n_rows, replace=False)   # in random order, as in the book
    cols = rng.permutation(M.shape[1])
    return M, labels, rows, cols


def fig_1_3(out_dir=None):
    """Heat map of 100 random genes x 64 samples of the NCI microarray data (green < 0 < red)."""
    M, labels, rows, cols = heatmap_selection()
    S = M[np.ix_(rows, cols)]
    fig, ax = plt.subplots(figsize=(6.2, 8.2))
    ax.imshow(S, cmap=GREEN_RED, vmin=-2, vmax=2, aspect="auto", interpolation="nearest")
    ax.set_yticks(range(len(rows)))
    ax.set_yticklabels(["g%d" % (r + 1) for r in rows], fontsize=4.2)
    ax.yaxis.tick_right()
    ax.set_xticks(range(len(cols)))
    ax.set_xticklabels([labels[c] for c in cols], rotation=90, fontsize=4.6)
    ax.tick_params(length=0, pad=1.5)
    for s in ax.spines.values():
        s.set_visible(False)
    savefig(fig, CH, "fig1-3", out_dir)
    print("  shown entries: %.1f%% beyond +-2 (drawn at full colour)" % (100 * np.mean(np.abs(S) > 2)))


def fig_1_S1(out_dir=None):
    """Supplementary: training and test error of k-NN regression of lpsa on lcavol, against k."""
    r = prostate_fits("lcavol")
    ks = np.array([k for k, _, _ in r["knn"]])
    trn = np.array([a for _, a, _ in r["knn"]])
    tst = np.array([b for _, _, b in r["knn"]])
    fig, ax = plt.subplots(figsize=(5.2, 4.2))
    ax.plot(ks, trn, "o-", color=BLUE, ms=3, lw=1.2, label="k-NN on lcavol: training error")
    ax.plot(ks, tst, "o-", color=RED, ms=3, lw=1.2, label="k-NN on lcavol: test error")
    ax.axhline(r["line"][1], color=PURPLE, ls="--", lw=1.1, label="least-squares line on lcavol: test error")
    ax.axhline(r["all8"][1], color="black", ls=":", lw=1.2, label="least squares on all 8 inputs: test error")
    ax.axhline(r["null"][1], color=GREY, ls="-.", lw=1.0, label="training mean (no inputs): test error")
    ax.set_xlabel("number of neighbours k")
    ax.set_ylabel("mean squared error")
    ax.set_xlim(0, ks.max() + 1)
    ax.set_ylim(0, 1.2)
    ax.legend(fontsize=7.4, frameon=False, loc="upper center", bbox_to_anchor=(0.5, -0.17), ncol=2)
    fig.tight_layout()
    savefig(fig, CH, "fig1-S1", out_dir)
    kb = int(ks[np.argmin(tst)])
    print("  k-NN: training error at k=1 %.4f, test error at k=1 %.4f; best test error %.4f at k=%d"
          % (trn[0], tst[0], tst.min(), kb))
    print("  line on lcavol: train %.4f test %.4f; all eight: train %.4f test %.4f (se %.3f); mean only: test %.4f (se %.3f)"
          % (r["line"] + r["all8"] + (r["all8_test_se"], r["null"][1], r["null_test_se"])))


def table_1_1():
    """Table 1.1: the 11 words and characters with the largest difference in class means."""
    X, y, _ = load_spam()
    rows = class_mean_table(X, y, 11, "diff")
    print("  Table 1.1 (mean percentage of words/characters; spam / email):")
    for name, ms, me, d, t in rows:
        print("    %-8s %5.2f %5.2f   diff %+.3f   t %+.1f" % (name, ms, me, d, t))
    return rows


# =========================================================================== data for the demos
def export_json():
    """Write ../data/ch01-prostate.json and ../data/ch01-spam.json for the browser demonstrations."""
    import json
    os.makedirs(JSON_DIR, exist_ok=True)
    X, y, tr, names = load_prostate()
    pro = dict(names=names, response="lpsa", X=[[float(v) for v in row] for row in X],
               y=[float(v) for v in y], train=[int(t) for t in tr])
    with open(os.path.join(JSON_DIR, "ch01-prostate.json"), "w") as f:
        json.dump(pro, f, separators=(",", ":"))
    Xs, ys, test = load_spam()
    F = Xs[:, :N_FREQ]
    s, e = F[ys == 1], F[ys == 0]
    summary = dict(names=SPAM_NAMES[:N_FREQ], mean_spam=[round(float(v), 5) for v in s.mean(0)],
                   mean_email=[round(float(v), 5) for v in e.mean(0)],
                   var_spam=[round(float(v), 6) for v in s.var(0, ddof=1)],
                   var_email=[round(float(v), 6) for v in e.var(0, ddof=1)],
                   nonzero_spam=[round(float(v), 5) for v in (s > 0).mean(0)],
                   nonzero_email=[round(float(v), 5) for v in (e > 0).mean(0)],
                   n_spam=int(len(s)), n_email=int(len(e)))
    words = [r[0] for r in class_mean_table(Xs, ys, 11, "diff")]
    cols = {w: [float("%.4g" % v) for v in Xs[:, SPAM_NAMES.index(w)]] for w in words}
    spam = dict(summary=summary, words=words, cols=cols, y=[int(v) for v in ys], test=[int(v) for v in test])
    with open(os.path.join(JSON_DIR, "ch01-spam.json"), "w") as f:
        json.dump(spam, f, separators=(",", ":"))
    for n in ("ch01-prostate.json", "ch01-spam.json"):
        print("wrote", os.path.relpath(os.path.join(JSON_DIR, n), os.getcwd()),
              "(%d kB)" % (os.path.getsize(os.path.join(JSON_DIR, n)) // 1024))


def fig_table_and_data(out_dir=None):
    """Table 1.1 (printed) and the JSON files of the demonstrations."""
    table_1_1()
    X, y, test = load_spam()
    for kind, a, b in (("box", 0.6, 1.5), ("linear", 0.2, 0.3)):
        c = confusion(spam_rule(X, kind, a, b), y)
        print("  rule %-6s (%.1f, %.1f): error %.4f, email flagged %d of %d, spam missed %d of %d"
              % (kind, a, b, c["error"], c["email_lost"], c["email_lost"] + c["email_ok"], c["spam_missed"],
                 c["spam_missed"] + c["spam_caught"]))
    export_json()


FIGURES = {"1.1": fig_1_1, "1.2": fig_1_2, "1.3": fig_1_3, "1.S1": fig_1_S1, "T1.1": fig_table_and_data}

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