"""Chapter 12 lab: Unsupervised Learning (Python version).

Course: Applied Statistical Learning in R and Python, which follows James, Witten, Hastie, Tibshirani
and Taylor (2023), An Introduction to Statistical Learning with Applications in Python, Section 12.5,
and the R edition of 2021.

  [1] the USArrests data;  [2] principal components with scikit-learn: loadings, scores, biplot, PVE;
  [3] matrix completion: the SVD and Algorithm 12.1 written out;  [4] K-means on simulated data;
  [5] hierarchical clustering: linkages, cutting the tree, scaling, correlation-based distance;
  [6] the NCI60 data: principal components;  [7] the NCI60 data: clustering the cell lines.
  [E2]-[E13] the exercises that need a computer.
Only numpy, pandas, scipy, scikit-learn and matplotlib are used (no ISLP package): the dendrograms
come from scipy.cluster.hierarchy directly. USArrests (an R data set, which the Python edition fetches
over the internet with statsmodels' get_rdataset) and NCI60 (from the R package ISLR2) are read from
copies exported once from R by ch12_unsupervised_learning.py. The seeds of [3]-[5] are those of the
Python edition. The R version is ch12_lab.R.

Run: python3 ch12_lab.py     (prints the results; writes the plots to ../img/ch12/lab-py-*)
The code is my own.
"""
import os

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

import warnings

import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import linkage, dendrogram, cut_tree
from scipy.stats import norm, ttest_ind
from sklearn.cluster import KMeans, AgglomerativeClustering
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

from common import isl_data, savefig, plt, RED, BLUE, ORANGE, GREY
from ch12_unsupervised_learning import usarrests, nci60

warnings.filterwarnings("ignore")
pd.set_option("display.width", 100)
pd.set_option("display.max_columns", 20)
np.set_printoptions(linewidth=100, suppress=True)


def step(k, title):
    print("\n== [%s] %s" % (k, title))


# -- [1] The USArrests data: 50 states, arrests per 100,000 residents and percent urban population
step(1, "The USArrests data")
USArrests = usarrests()
print(list(USArrests.index[:4]))
print(list(USArrests.columns))
print(USArrests.mean())
print(USArrests.var())

# -- [2] Principal components with scikit-learn: centre and scale the columns first
step(2, "Principal components")
scaler = StandardScaler(with_std=True, with_mean=True)
USArrests_scaled = scaler.fit_transform(USArrests)      # divides by the 1/n standard deviation
pcaUS = PCA()
pcaUS.fit(USArrests_scaled)
print(pcaUS.mean_.round(12))
print(pcaUS.components_)                  # the loading vectors phi_1, ..., phi_4 (rows)
scores = pcaUS.transform(USArrests_scaled)
print(scores.shape)
scores[:, 1] *= -1                        # flip PC2 (scores and loadings) to get Figure 12.1
pcaUS.components_[1] *= -1
fig, ax = plt.subplots(figsize=(6, 6))
ax.scatter(scores[:, 0], scores[:, 1], s=10, color=BLUE)
for k, nm in enumerate(USArrests.columns):
    ax.arrow(0, 0, 2 * pcaUS.components_[0, k], 2 * pcaUS.components_[1, k], color=ORANGE, head_width=0.05)
    ax.text(2.15 * pcaUS.components_[0, k], 2.15 * pcaUS.components_[1, k], nm, color=ORANGE)
ax.set_xlabel("PC1"); ax.set_ylabel("PC2")
savefig(fig, 12, "lab-py-biplot")
print(scores.std(0, ddof=1))
print(pcaUS.explained_variance_)          # the variances of the scores (divisor n - 1)
print(pcaUS.explained_variance_ratio_)    # the PVE (12.10)
fig, axes = plt.subplots(1, 2, figsize=(9, 3.8))
ticks = np.arange(pcaUS.n_components_) + 1
axes[0].plot(ticks, pcaUS.explained_variance_ratio_, marker="o")
axes[0].set_ylabel("Proportion of Variance Explained")
axes[1].plot(ticks, pcaUS.explained_variance_ratio_.cumsum(), marker="o")
axes[1].set_ylabel("Cumulative Proportion of Variance Explained")
for a in axes:
    a.set_xlabel("Principal Component"); a.set_ylim([0, 1]); a.set_xticks(ticks)
savefig(fig, 12, "lab-py-pve")

# -- [3] Matrix completion: the SVD, then Algorithm 12.1 by hand
step(3, "Matrix completion")
X = USArrests_scaled
U, D, V = np.linalg.svd(X, full_matrices=False)   # X = U diag(D) V; the rows of V are the loadings
print(U.shape, D.shape, V.shape)
print(V.round(3))
print(np.abs(np.abs(U * D[None, :]) - np.abs(pcaUS.transform(X))).max())   # U D = the scores, up to sign
n_omit = 20
np.random.seed(15)
r_idx = np.random.choice(np.arange(X.shape[0]), n_omit, replace=False)    # 20 states ...
c_idx = np.random.choice(np.arange(X.shape[1]), n_omit, replace=True)     # ... one variable in each
print(r_idx, c_idx)
Xna = X.copy()
Xna[r_idx, c_idx] = np.nan


def low_rank(X, M=1):
    """The best rank-M approximation of X."""
    U, D, V = np.linalg.svd(X, full_matrices=False)
    return (U[:, :M] * D[None, :M]) @ V[:M]


def complete(Xna, X, M=1, thresh=1e-7, start="py", verbose=True):
    """Algorithm 12.1 with the labs' stopping rule; returns the correlation of imputed and true values."""
    Xhat = Xna.copy()
    Xbar = np.nanmean(Xhat, axis=0)
    ismiss = np.isnan(Xna)
    Xhat[ismiss] = np.broadcast_to(Xbar, Xna.shape)[ismiss]              # step 1: column means
    mss0 = np.mean(Xna[~ismiss] ** 2)
    mssold = mss0 if start == "py" else np.mean((Xna - Xbar)[~ismiss] ** 2)
    rel_err, count = 1.0, 0
    while rel_err > thresh:
        count += 1
        Xapp = low_rank(Xhat, M=M)                                           # step 2(a)
        Xhat[ismiss] = Xapp[ismiss]                                          # step 2(b)
        mss = np.mean(((Xna - Xapp)[~ismiss]) ** 2)                         # step 2(c)
        rel_err = (mssold - mss) / mss0
        mssold = mss
        if verbose:
            print("Iteration: %d, MSS: %.6f, Rel.Err %.3e" % (count, mss, rel_err))
    return np.corrcoef(Xapp[ismiss], X[ismiss])[0, 1]


print(round(complete(Xna, X), 4))
# The R lab removes other entries (R's random numbers) from a matrix scaled with the n - 1 standard
# deviation. With R's entries and R's scaling, the iterations are exactly those of the R lab:
XR = (USArrests - USArrests.mean()) / USArrests.std(ddof=1)
XR = XR.to_numpy()
ina = np.array([37, 47, 42, 34, 38, 5, 25, 12, 20, 46, 1, 43, 50, 23, 2, 44, 10, 26, 21, 32]) - 1
inb = np.array([3, 1, 2, 4, 2, 2, 3, 3, 4, 3, 2, 1, 3, 1, 3, 3, 4, 2, 2, 3]) - 1
XRna = XR.copy()
XRna[ina, inb] = np.nan
print(round(complete(XRna, XR, start="R"), 6))

# -- [4] K-means clustering of simulated data with two groups
step(4, "K-means clustering")
np.random.seed(0)
X = np.random.standard_normal((50, 2))
X[:25, 0] += 3
X[:25, 1] -= 4
kmeans = KMeans(n_clusters=2, random_state=2, n_init=20).fit(X)
print(kmeans.labels_)
fig, axes = plt.subplots(1, 2, figsize=(8, 4))
axes[0].scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap="coolwarm")
axes[0].set_title("K-Means Clustering Results with K=2")
kmeans = KMeans(n_clusters=3, random_state=3, n_init=20).fit(X)
axes[1].scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap="viridis")
axes[1].set_title("K-Means Clustering Results with K=3")
savefig(fig, 12, "lab-py-kmeans")
print(np.bincount(kmeans.labels_))
kmeans1 = KMeans(n_clusters=3, random_state=3, n_init=1).fit(X)
kmeans20 = KMeans(n_clusters=3, random_state=3, n_init=20).fit(X)
print(round(kmeans1.inertia_, 4), round(kmeans20.inertia_, 4))
print(round(2 * kmeans20.inertia_, 4))      # the objective (12.17) is twice the inertia

# -- [5] Hierarchical clustering: three linkages, cutting the tree, scaling, correlation distance
step(5, "Hierarchical clustering")
linkage_comp = linkage(X, method="complete")      # Euclidean distances by default
linkage_avg = linkage(X, method="average")
linkage_sing = linkage(X, method="single")
cargs = {"color_threshold": -np.inf, "above_threshold_color": "black"}
fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for ax, L, t in zip(axes, (linkage_comp, linkage_avg, linkage_sing), ("Complete", "Average", "Single")):
    dendrogram(L, ax=ax, leaf_font_size=6, **cargs)
    ax.set_title(t + " Linkage")
savefig(fig, 12, "lab-py-hclust")
print(cut_tree(linkage_comp, n_clusters=4).T)
print(cut_tree(linkage_comp, height=5).T)
for L in (linkage_comp, linkage_avg, linkage_sing):
    print(cut_tree(L, n_clusters=2).ravel())
print(linkage_comp[-4:, 2].round(4))           # the last fusion heights
hc = AgglomerativeClustering(n_clusters=4, linkage="complete").fit(X)
print(pd.crosstab(hc.labels_, cut_tree(linkage_comp, n_clusters=4).ravel()))
X_scale = StandardScaler().fit_transform(X)
print(pd.crosstab(cut_tree(linkage(X_scale, "complete"), 2).ravel(), cut_tree(linkage_comp, 2).ravel()))
X3 = np.random.standard_normal((30, 3))        # 30 observations, 3 features, no true clusters
corD = 1 - np.corrcoef(X3)                     # correlation between observations (rows)
iu = np.triu_indices(30, 1)
linkage_cor = linkage(corD[iu], method="complete")   # linkage() takes the condensed distances
print(linkage_cor[-3:, 2].round(4))

# -- [6] The NCI60 data: principal components of 64 cell lines x 6830 genes
step(6, "NCI60: principal components")
nci_data, nci_labs = nci60()
nci_labs = pd.Series(nci_labs, name="label")
print(nci_data.shape)
print(list(nci_labs[:4]))
print(nci_labs.value_counts().to_dict())
nci_scaled = StandardScaler().fit_transform(nci_data)
nci_pca = PCA()
nci_scores = nci_pca.fit_transform(nci_scaled)
print(nci_scores[:3, :3].round(4))
fig, axes = plt.subplots(1, 2, figsize=(10, 4.2))
cancer_types = sorted(nci_labs.unique())
groups = np.array([cancer_types.index(l) for l in nci_labs])
for ax, j in zip(axes, (1, 2)):
    ax.scatter(nci_scores[:, 0], nci_scores[:, j], c=groups, cmap="tab20", s=30)
    ax.set_xlabel("PC1"); ax.set_ylabel("PC%d" % (j + 1))
savefig(fig, 12, "lab-py-nci-pcs")
print(nci_pca.explained_variance_ratio_[:6].round(5))
print((100 * nci_pca.explained_variance_ratio_.cumsum()[[4, 6, 9, 19, 62, 63]]).round(4))

# -- [7] Clustering the NCI60 cell lines
step(7, "NCI60: clustering")
trees = {m: linkage(nci_scaled, method=m) for m in ("complete", "average", "single")}
comp_cut = cut_tree(trees["complete"], n_clusters=4).ravel()
show = ["BREAST", "CNS", "COLON", "LEUKEMIA", "MELANOMA", "NSCLC", "OVARIAN", "RENAL"]
print(pd.crosstab(pd.Series(comp_cut, name="Complete"), nci_labs)[show])
print(trees["complete"][-4:, 2].round(2))      # the data are scaled with 1/n: heights x sqrt(64/63)
fig, ax = plt.subplots(figsize=(11, 5))
dendrogram(trees["complete"], ax=ax, labels=np.asarray(nci_labs), leaf_font_size=6,
           color_threshold=140, above_threshold_color="black")
ax.axhline(140, c="r", linewidth=2)
savefig(fig, 12, "lab-py-nci-cut")
nci_kmeans = KMeans(n_clusters=4, random_state=0, n_init=20).fit(nci_scaled)
print(pd.crosstab(pd.Series(comp_cut, name="HClust"), pd.Series(nci_kmeans.labels_, name="K-means")))
print(round(nci_kmeans.inertia_ * 63 / 64, 1))  # on R's scale, to compare with R's tot.withinss
hc_pca = linkage(nci_scores[:, :5], method="complete")
print(pd.crosstab(pd.Series(cut_tree(hc_pca, n_clusters=4).ravel(), name="Complete-PCA"), nci_labs)[show])

# ===================================================================== exercises


def hash_u(i, j, s=0):
    """A deterministic stand-in for random numbers, identical in R and Python (see ch12_lab.R)."""
    v = np.abs(np.sin(12.9898 * np.asarray(i, float) + 78.233 * np.asarray(j, float) + 37.719 * s)) * 43758.5453
    return np.clip(v - np.floor(v), 1e-12, 1 - 1e-12)


# -- [E2] Exercise 2: complete and single linkage from a dissimilarity matrix
step("E2", "Exercise 2")
D2 = np.array([[0, 0.3, 0.4, 0.7], [0.3, 0, 0.5, 0.8], [0.4, 0.5, 0, 0.45], [0.7, 0.8, 0.45, 0]])
iu = np.triu_indices(4, 1)
for m in ("complete", "single"):
    L2 = linkage(D2[iu], method=m)
    print(m, L2[:, :3].round(2).tolist(), cut_tree(L2, n_clusters=2).ravel() + 1)

# -- [E3] Exercise 3: K-means by hand, K = 2, from a fixed starting assignment
step("E3", "Exercise 3")
x3 = np.array([[1, 4], [1, 3], [0, 4], [5, 1], [6, 2], [4, 0]], float)
lab = np.array([1, 2, 1, 2, 1, 2])                # observations 1, 3, 5 start in cluster 1
while True:
    cent = np.array([x3[lab == k].mean(0) for k in (1, 2)])
    print(cent.round(5).tolist())
    new = np.where(((x3 - cent[0]) ** 2).sum(1) <= ((x3 - cent[1]) ** 2).sum(1), 1, 2)
    print(new)
    if np.array_equal(new, lab):
        break
    lab = new

# -- [E7] Exercise 7: correlation-based against squared Euclidean distance
step("E7", "Exercise 7")
A = USArrests.to_numpy(float)
xs = (A - A.mean(1, keepdims=True)) / A.std(1, ddof=1, keepdims=True)   # each STATE standardised
iu = np.triu_indices(50, 1)
d7 = ((xs[:, None, :] - xs[None, :, :]) ** 2).sum(2)[iu]
r7 = np.corrcoef(xs)[iu]
print(pd.Series(d7 / (1 - r7)).describe().round(4).to_dict())     # constant 2 (p - 1) = 6
xc = (A - A.mean(0)) / A.std(0, ddof=1)                            # columns scaled only
dc = ((xc[:, None, :] - xc[None, :, :]) ** 2).sum(2)[iu]
print(pd.Series(dc / (1 - np.corrcoef(xc)[iu])).describe().round(2).to_dict())

# -- [E8] Exercise 8: the PVE from the fitted PCA and directly from (12.10)
step("E8", "Exercise 8")
pca8 = PCA().fit(USArrests_scaled)
pve_b = ((USArrests_scaled @ pca8.components_.T) ** 2).sum(0) / (USArrests_scaled ** 2).sum()
print(np.vstack([pca8.explained_variance_ratio_, pve_b]).round(6))

# -- [E9] Exercise 9: hierarchical clustering of the states, unscaled and scaled
step("E9", "Exercise 9")
abb = ["AL", "AK", "AZ", "AR", "CA", "CO", "CT", "DE", "FL", "GA", "HI", "ID", "IL", "IN", "IA", "KS", "KY",
       "LA", "ME", "MD", "MA", "MI", "MN", "MS", "MO", "MT", "NE", "NV", "NH", "NJ", "NM", "NY", "NC", "ND",
       "OH", "OK", "OR", "PA", "RI", "SC", "SD", "TN", "TX", "UT", "VT", "VA", "WA", "WV", "WI", "WY"]
c9 = cut_tree(linkage(A, "complete"), n_clusters=3).ravel()
for k in range(3):
    print(k + 1, [a for a, c in zip(abb, c9) if c == k])
c9s = cut_tree(linkage(xc, "complete"), n_clusters=3).ravel()
print(pd.crosstab(pd.Series(c9 + 1, name="unscaled"), pd.Series(c9s + 1, name="scaled")))
print(USArrests.groupby(c9 + 1).mean().T.round(1))

# -- [E10] Exercise 10: three simulated classes, PCA and K-means
step("E10", "Exercise 10")
I10, J10 = np.meshgrid(np.arange(1, 61), np.arange(1, 51), indexing="ij")
x10 = norm.ppf(hash_u(I10, J10, 10))          # the same 60 x 50 values as the R lab
cls = np.repeat([1, 2, 3], 20)
x10[cls == 2, :25] += 1.2
x10[cls == 3, 25:] -= 1.2
pca10 = PCA().fit(x10)
z10 = pca10.transform(x10)
print(pca10.explained_variance_ratio_[:3].round(4))
fig, ax = plt.subplots(figsize=(4.5, 4.2))
ax.scatter(z10[:, 0], z10[:, 1], c=cls, cmap="brg", s=25)
ax.set_xlabel("PC1"); ax.set_ylabel("PC2")
savefig(fig, 12, "lab-py-ex10")
for data, K in ((x10, 3), (x10, 2), (x10, 4), (z10[:, :2], 3), (StandardScaler().fit_transform(x10), 3)):
    km = KMeans(n_clusters=K, n_init=20, random_state=10).fit(data)
    print(pd.crosstab(pd.Series(cls, name="cls"), km.labels_ + 1).to_string())

# -- [E11] Exercise 11: a matrix completion function, tested on the Boston data
step("E11", "Exercise 11")


def mat_complete(Xna, M=1, thresh=1e-7, maxit=500, verbose=False):
    ismiss = np.isnan(Xna)
    xbar = np.nanmean(Xna, 0)
    Xhat = np.where(ismiss, xbar, Xna)
    mss0 = np.mean(Xna[~ismiss] ** 2)
    mssold = np.mean((Xna - xbar)[~ismiss] ** 2)
    rel_err, it = 1.0, 0
    while rel_err > thresh and it < maxit:
        it += 1
        Xapp = low_rank(Xhat, M)
        Xhat[ismiss] = Xapp[ismiss]
        mss = np.mean(((Xna - Xapp)[~ismiss]) ** 2)
        rel_err = (mssold - mss) / mss0
        mssold = mss
        if verbose:
            print("Iter:", it, "MSS:", mss, "Rel. Err:", rel_err)
    return Xhat, it, mss


Boston = isl_data("Boston", index_col=0)
XB = Boston.to_numpy(float)
XB = (XB - XB.mean(0)) / XB.std(0, ddof=1)
N = XB.size
fracs = np.arange(1, 7) * 0.05
err = np.zeros((10, 6, 8))
for r in range(1, 11):
    order = np.argsort(hash_u(np.arange(1, N + 1), 0, 100 + r), kind="stable")   # R's column-major order
    for a, f in enumerate(fracs):
        miss = order[:int(round(f * N))]
        rows, cols = miss % XB.shape[0], miss // XB.shape[0]
        Xna = XB.copy()
        Xna[rows, cols] = np.nan
        for M in range(1, 9):
            Xhat, _, _ = mat_complete(Xna, M)
            err[r - 1, a, M - 1] = np.mean((Xhat[rows, cols] - XB[rows, cols]) ** 2)
E11 = pd.DataFrame(err.mean(0), index=["%d%%" % round(100 * f) for f in fracs],
                   columns=["M=%d" % M for M in range(1, 9)])
print(E11.round(3))
fig, ax = plt.subplots(figsize=(5.5, 3.8))
for M in range(1, 9):
    ax.plot(100 * fracs, E11.iloc[:, M - 1], marker="o", label="M = %d" % M)
ax.axhline(1, color=GREY, ls=":", lw=1)
ax.set_yscale("log"); ax.set_xlabel("% of entries missing"); ax.set_ylabel("mean squared error, missing entries")
ax.legend(fontsize=7, ncol=2)
savefig(fig, 12, "lab-py-ex11")

# -- [E12] Exercise 12: Algorithm 12.1 with PCA() in place of the SVD
step("E12", "Exercise 12")


def fit_pca(X, M=1):
    """PCA() centres the columns, so its rank-M reconstruction is mean + rank-M (an affine fit)."""
    p = PCA(n_components=M).fit(X)
    return p.inverse_transform(p.transform(X))


def impute_with(fitfun, Xna, M=1):
    ismiss = np.isnan(Xna)
    xbar = np.nanmean(Xna, 0)
    Xhat = np.where(ismiss, xbar, Xna)
    mss0 = np.mean(Xna[~ismiss] ** 2)
    mssold = np.mean((Xna - xbar)[~ismiss] ** 2)
    rel_err = 1.0
    while rel_err > 1e-7:
        Xapp = fitfun(Xhat, M)
        Xhat[ismiss] = Xapp[ismiss]
        mss = np.mean(((Xna - Xapp)[~ismiss]) ** 2)
        rel_err = (mssold - mss) / mss0
        mssold = mss
    return Xhat


print({"svd": round(np.corrcoef(impute_with(low_rank, XRna)[ina, inb], XR[ina, inb])[0, 1], 6),
       "PCA (centred)": round(np.corrcoef(impute_with(fit_pca, XRna)[ina, inb], XR[ina, inb])[0, 1], 6)})

# -- [E13] Exercise 13: gene expression of 40 tissue samples (20 healthy, 20 diseased)
step("E13", "Exercise 13")
g13 = isl_data("Ch12Ex13", header=None).to_numpy(float)
print(g13.shape)                               # 1000 genes (rows) x 40 samples (columns)
dcor = 1 - np.corrcoef(g13.T)                  # correlation between samples
iu = np.triu_indices(40, 1)
for m in ("complete", "average", "single"):
    print(m, ":", cut_tree(linkage(dcor[iu], method=m), n_clusters=2).ravel() + 1)
t13, p13 = ttest_ind(g13[:, :20], g13[:, 20:], axis=1, equal_var=False)
print((p13 < 0.05 / 1000).sum())               # genes significant after a Bonferroni correction
print(np.argsort(-np.abs(t13))[:10] + 1)       # the ten genes with the largest |t|
print(np.flatnonzero(p13 < 0.05 / 1000)[[0, -1]] + 1)
