Lab 9: Dimensional Reduction - PCA & t-SNE

Course: INS-605: Data Analysis II
Lecturer: Sothea HAS, PhD



The notebook of the lab can be downloaded from Lab9: Dimensional Reduction.


# These are the libraries that you will need for this lab
import time, warnings
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE

warnings.filterwarnings('ignore')
plt.rcParams['figure.figsize'] = (10, 3.5)
SEED = 605

1. PCA on the USArrests Data (~30 min)

Goal: summarize 4 correlated variables with a few principal components, understand what PCA computes (eigen-decomposition), measure what is lost when we reduce the dimension, and interpret the components with a correlation circle.

Data: USArrests: for each of the 50 US states in 1973, the number of arrests per 100,000 residents for Murder, Assault and Rape, and the percentage of the population living in urban areas (UrbanPop).

1.1. Data Exploration

The data may be downloaded from Kaggle using the following link: Kaggle USArrests dataset.

# TODO: Load the dataset

A. Look at the scale of the variables: the summary statistics are printed below. Compute the variance of each variable.

display(arrests.describe().round(2))
variances = None   # TODO: the variance of each of the 4 variables (a pandas Series indexed by the variable names)
print(variances.round(2))

B. Compute the correlation matrix of the variables and display it as a heatmap.

corr = None   # TODO: the 4 x 4 correlation matrix of the variables (a table)

fig, ax = plt.subplots(figsize=(5, 4))
sns.heatmap(corr, annot=True, cmap='RdBu_r', vmin=-1, vmax=1, ax=ax)
ax.set_title('Correlation matrix'); plt.show()

C. In a markdown cell, briefly answer:

  1. Which variables are strongly correlated? According to the lecture, is a dimensional reduction promising here?

  2. The variances are very different. If we ran PCA on the raw data, which variable would dominate the 1st principal direction, and why? What should we do before PCA?

C. Your answer here:

  1. …

  2. …

1.2. PCA on Raw vs Standardized Data

The lecture distinguishes two versions of PCA: unnormalized PCA (eigen-decomposition of the covariance matrix, centered data) and normalized PCA (eigen-decomposition of the correlation matrix, i.e. standardized data). Note that PCA of scikit-learn centers the data but does not scale it.

A. Fit a PCA with all 4 components on the raw data and on the standardized data, and compare the proportion of variance explained by each PC.

cols = list(arrests.columns)

scaler = None      # TODO: a standard scaler learned on the 4 variables
Z = None           # TODO: the standardized data (a NumPy array): each variable now has mean 0 and standard deviation 1
pca_raw = None     # TODO: a PCA keeping all 4 components, fitted on the RAW data
pca_std = None     # TODO: a PCA keeping all 4 components, fitted on the standardized data Z

pcs = [f'PC{i}' for i in range(1, 5)]
evr = pd.DataFrame({'raw data': pca_raw.explained_variance_ratio_,
                    'standardized data': pca_std.explained_variance_ratio_}, index=pcs)
evr.round(4)

B. Build the loading tables (the principal directions \(\vec{u}_k\)): one row per original variable and one column per PC, for both PCAs. Be careful: scikit-learn stores the directions as the rows of its components_ attribute.

load_raw = None   # TODO: table of the principal directions of pca_raw: variable names as index, PC names (PC1,...,PC4) as columns
load_std = None   # TODO: the same table for pca_std

pd.concat({'Raw data': load_raw, 'Standardized data': load_std}, axis=1).round(3)    # side by side

C. In a markdown cell, briefly answer:

  1. On the raw data, how much variance does PC1 capture and which variable does it essentially contain? Explain it with your answer of 1.1.C.

  2. What changes on the standardized data (variance explained, loadings of PC1)? Why do we use the standardized version here?

C. Your answer here:

  1. …

  2. …

1.3. PCA by Hand: Eigen-decomposition of the Correlation Matrix

According to the lecture, normalized PCA is the eigen-decomposition \(C=U\Lambda U^T\) of the correlation matrix \(C\): the columns of \(U\) are the principal directions, \(\lambda_1\geq\dots\geq\lambda_4\) are the variances along them, and the rotated data (the principal components) is \(\tilde D=ZU\).

A. Recompute everything without the PCA class and check that you get the same results as scikit-learn.

C = None                 # TODO: the 4 x 4 correlation matrix of the variables (as a NumPy array)
eigval, eigvec = None, None   # TODO: the eigenvalues and eigenvectors of C (C is symmetric), sorted from the LARGEST to the smallest eigenvalue (careful: the function you use may return them in increasing order). The eigenvectors are the columns of eigvec
scores_manual = None     # TODO: the rotated data: the standardized data Z multiplied by the matrix of eigenvectors

print('eigenvalues:', eigval.round(4), '| sum =', eigval.sum().round(4))
print('variance ratios match sklearn  :', np.allclose(eigval / eigval.sum(), pca_std.explained_variance_ratio_))
print('directions match (up to sign)  :', np.allclose(np.abs(eigvec), np.abs(pca_std.components_.T)))
print('components match (up to sign)  :', np.allclose(np.abs(scores_manual), np.abs(pca_std.transform(Z))))

B. In a markdown cell, briefly answer:

  1. Why do the eigenvalues of the correlation matrix sum to 4? What does the ratio \(\lambda_k/\sum_j\lambda_j\) represent?

  2. Why do we compare the directions and the components only up to sign?

B. Your answer here:

  1. …

  2. …

1.4. Dimensional Reduction & Reconstruction

A. Compute the cumulative proportion of variance explained by the first \(k\) PCs (\(k=1,\dots,4\)), using the eigenvalues of 1.3, and plot it (a scree plot).

cum_var = None    # TODO: an array of 4 numbers: the proportion of variance explained by the first k PCs, for k = 1, 2, 3, 4 (cumulative sum of the eigenvalues divided by their total)

fig, axes = plt.subplots(1, 2, figsize=(11, 3.5))
axes[0].bar(range(1, 5), eigval / eigval.sum(), color='#345a8b'); axes[0].set_title('Variance explained by each PC')
axes[1].plot(range(1, 5), cum_var * 100, 'o-', color='#345a8b'); axes[1].axhline(85, color='red', ls='--', label='85%')
axes[1].set_title('Cumulative variance explained (%)'); axes[1].set_xticks(range(1, 5)); axes[1].legend()
for ax in axes: ax.set_xlabel('number of PCs')
plt.tight_layout(); plt.show()
print((cum_var * 100).round(2))

B. Reconstruct the standardized data from the first \(k\) PCs, \(Z^{\text{rec}}_k=\tilde D_k\,U_k^T\) (lecture), and measure the relative squared reconstruction error \(\|Z-Z^{\text{rec}}_k\|_F^2/\|Z\|_F^2\). Compare it with \(1-\) (variance explained).

rows = []
for k in range(1, 5):
    Z_rec = None   # TODO: reconstruction of Z from the first k PCs: the first k columns of scores_manual multiplied by the transpose of the first k columns of eigvec
    err = None     # TODO: the relative squared Frobenius error: (sum of the squared entries of Z - Z_rec) divided by (sum of the squared entries of Z)
    rows.append({'k': k, 'relative squared error': err, '1 - variance explained': 1 - cum_var[k - 1]})
pd.DataFrame(rows).set_index('k').round(4)

C. In a markdown cell, briefly answer:

  1. How many PCs would you keep to retain at least 85% of the variance? What do we gain?

  2. What relation do you observe between the reconstruction error and the variance explained? Why? What is the error for \(k=4\)?

C. Your answer here:

  1. …

  2. …

1.5. Correlation Circle & Biplot

A. To interpret the PCs, compute the correlation between each original (standardized) variable and PC1, PC2. The scores of the first two PCs are already prepared below.

scores_df = pd.DataFrame(pca_std.transform(Z)[:, :2], index=arrests.index, columns=['PC1', 'PC2'])
Z_df = pd.DataFrame(Z, index=arrests.index, columns=cols)

corr_pc = None   # TODO: a 4 x 2 table: the correlation between each standardized variable (rows) and each of PC1, PC2 (columns). Z_df and scores_df are two tables with the same rows (the states)
corr_pc.round(3)

B. Run the cell below: the correlation circle (left) and the biplot of the states (right, the 10 states farthest from the origin are named). The sign of a PC is arbitrary, so the cell flips it, if needed, to make PC1 positively correlated with Murder and PC2 with UrbanPop.

signs = np.where(np.diag(corr_pc.loc[['Murder', 'UrbanPop']].to_numpy()) < 0, -1, 1)
corr_pc, scores_df = corr_pc * signs, scores_df * signs
evr_std = pca_std.explained_variance_ratio_

fig, axes = plt.subplots(1, 2, figsize=(13, 5.5))
ax = axes[0]
ax.add_patch(plt.Circle((0, 0), 1, fill=False, ls='--', color='k'))
for var, (a, b) in corr_pc.iterrows():
    ax.arrow(0, 0, a, b, head_width=0.03, color='#345a8b', length_includes_head=True)
    ax.text(a * 1.1, b * 1.1, var, ha='center')
ax.axhline(0, color='gray', ls='--', lw=.8); ax.axvline(0, color='gray', ls='--', lw=.8)
ax.set_xlim(-1.25, 1.25); ax.set_ylim(-1.25, 1.25); ax.set_aspect('equal')
ax.set_xlabel(f'PC1 ({evr_std[0]:.1%})'); ax.set_ylabel(f'PC2 ({evr_std[1]:.1%})'); ax.set_title('Correlation circle')

ax = axes[1]
ax.scatter(scores_df['PC1'], scores_df['PC2'], color='#345a8b', s=18)
for st in (scores_df ** 2).sum(axis=1).nlargest(10).index:
    ax.annotate(st, (scores_df.loc[st, 'PC1'], scores_df.loc[st, 'PC2']), fontsize=8)
ax.axhline(0, color='gray', ls='--', lw=.8); ax.axvline(0, color='gray', ls='--', lw=.8)
ax.set_xlabel(f'PC1 ({evr_std[0]:.1%})'); ax.set_ylabel(f'PC2 ({evr_std[1]:.1%})'); ax.set_title('Biplot of the states')
plt.tight_layout(); plt.show()

C. In a markdown cell, briefly answer:

  1. Interpret PC1 and PC2: which variables are well represented by the plane (long arrows)? Which ones are aligned / nearly perpendicular, and what does it say about their correlation (compare with 1.1.B)?

  2. Use the biplot: name a state with a high PC1 and a state with a low PC1, a state with a high PC2 and a state with a low PC2.

  3. The lecture warns that the interpretation of PCs may be misleading. Why?

C. Your answer here:

  1. …

  2. …

  3. …


2. t-SNE on Fashion-MNIST (~28 min)

Goal: visualize high-dimensional data (\(d=784\)) in 2D, compare the linear PCA with the non-linear \(t\)-SNE, and explore the effect of the main hyperparameter of \(t\)-SNE: the perplexity.

Data: Fashion-MNIST: 28x28 grayscale images of 10 types of clothing (60,000 for training). Each image is a vector of \(d=784\) pixels. To keep \(t\)-SNE fast, we use a random sample of \(N=2000\) images.

2.1. Data

Run the cell below to load the data (it needs keras as in the lecture; if it is not installed, it downloads the data from OpenML instead, so an internet connection is required).

try:
    from keras.datasets import fashion_mnist           # same source as the MNIST example of the lecture
    (x_train, y_train), _ = fashion_mnist.load_data()
except Exception:
    from sklearn.datasets import fetch_openml
    fm = fetch_openml('Fashion-MNIST', version=1, as_frame=False)
    x_train, y_train = fm.data[:60000].reshape(-1, 28, 28), fm.target[:60000].astype(int)
print(x_train.shape, y_train.shape)

A. Take a random sample of \(N=2000\) images and transform each image into a row vector of 784 pixels, with pixel values rescaled to \([0,1]\).

class_names = ['T-shirt/top', 'Trouser', 'Pullover', 'Dress', 'Coat', 'Sandal', 'Shirt', 'Sneaker', 'Bag', 'Ankle boot']
N = 2000
rng = np.random.default_rng(SEED)
idx = rng.choice(len(x_train), size=N, replace=False)
img_s, y_s = x_train[idx], y_train[idx]

X_s = None    # TODO: the N sampled images as a matrix with N rows and 784 columns (each 28 x 28 image flattened into one row), with the pixel values rescaled from [0, 255] to [0, 1]
print(X_s.shape, X_s.min(), X_s.max(), '| images per class:', np.bincount(y_s))

Run the cell below to look at some images and to define a plotting helper used in the next sections.

fig, axes = plt.subplots(2, 6, figsize=(10, 3.4))
for ax, i in zip(axes.ravel(), range(12)):
    ax.imshow(img_s[i], cmap='gray'); ax.axis('off'); ax.set_title(class_names[y_s[i]], fontsize=9)
plt.tight_layout(); plt.show()

def scatter2d(Z2, y, ax, title):
    # 2D scatter plot with one color per class
    sns.scatterplot(x=Z2[:, 0], y=Z2[:, 1], hue=[class_names[c] for c in y], hue_order=class_names,
                    palette='tab10', s=14, ax=ax, legend=False)
    ax.set_title(title); ax.set_xticks([]); ax.set_yticks([])

2.2. Baseline: PCA in 2D

A. Fit a PCA with 2 components on X_s and project the data. Then fit a PCA with all components and find the smallest number of PCs explaining at least 90% of the variance.

pca_fm = None     # TODO: a PCA with 2 components fitted on X_s
Z_pca = None      # TODO: the 2-dimensional projection of X_s (a matrix with N rows and 2 columns)
print(f'Variance explained by 2 PCs: {pca_fm.explained_variance_ratio_.sum():.1%}')

pca_full = None   # TODO: a PCA keeping all the components, fitted on X_s
k90 = None        # TODO: the smallest number of PCs whose cumulative proportion of explained variance is at least 90%
print('Number of PCs needed for 90% of the variance:', k90)

fig, ax = plt.subplots(figsize=(6, 5))
scatter2d(Z_pca, y_s, ax, 'PCA (2 components)')
ax.legend(handles=[plt.Line2D([], [], marker='o', ls='', color=c, label=n) for c, n in zip(sns.color_palette('tab10'), class_names)],
          bbox_to_anchor=(1.02, 1), loc='upper left', fontsize=8)
plt.tight_layout(); plt.show()

B. In a markdown cell, briefly answer:

  1. How much variance do 2 PCs keep, and how many PCs are needed for 90%? Is the data “essentially 2-dimensional” for a linear method?

  2. Looking at the PCA plot, which classes are well separated and which ones overlap?

B. Your answer here:

  1. …

  2. …

2.3. t-SNE in 2D

\(t\)-SNE converts the distances between the images into neighbor probabilities \(P\) (Gaussian, in the 784-D space) and looks for 2D points whose \(t\)-distribution probabilities \(Q\) are as close as possible to \(P\) in terms of the KL divergence (minimized by gradient descent with momentum).

A. Fit a TSNE with 2 components, perplexity 30 and random_state=SEED on X_s (this takes about 10-60 s) and report the final KL divergence.

t0 = time.time()
tsne = None       # TODO: a t-SNE model with 2 components, perplexity 30 and random_state=SEED
Z_tsne = None     # TODO: the 2-dimensional embedding of X_s learned by this model
print(f'{time.time() - t0:.0f}s | final KL divergence: {tsne.kl_divergence_:.3f}')

fig, axes = plt.subplots(1, 2, figsize=(13, 5))
scatter2d(Z_pca, y_s, axes[0], 'PCA (2 components)')
scatter2d(Z_tsne, y_s, axes[1], 't-SNE (perplexity 30)')
axes[1].legend(handles=[plt.Line2D([], [], marker='o', ls='', color=c, label=n) for c, n in zip(sns.color_palette('tab10'), class_names)],
               bbox_to_anchor=(1.02, 1), loc='upper left', fontsize=8)
plt.tight_layout(); plt.show()

B. In a markdown cell, briefly answer:

  1. Compare t-SNE with PCA: which classes are now well separated? Which ones still overlap and why?

  2. PCA is a linear rotation, t-SNE is non-linear and keeps neighborhoods. In which situation would you prefer each one?

B. Your answer here:

  1. …

  2. …

2.4. Effect of the Perplexity

The perplexity is the main hyperparameter of \(t\)-SNE: it is (roughly) the number of effective neighbors of each point, typically between 5 and 50 (see the How to use t-SNE effectively article of the lecture).

A. Fit a t-SNE for each perplexity in [5, 30, 100] (same random_state=SEED), keep the embeddings and the final KL divergences (about 1-3 min in total), and plot the three embeddings.

perplexities = [5, 30, 100]
embeds, kls = {}, {}
for perp in perplexities:
    model = None            # TODO: a t-SNE model with 2 components, perplexity `perp` and random_state=SEED
    embeds[perp] = None     # TODO: the 2-dimensional embedding of X_s learned by this model
    kls[perp] = None        # TODO: the final KL divergence reached by this model
    print(f'perplexity {perp:>3}: KL = {kls[perp]:.3f}')

fig, axes = plt.subplots(1, 3, figsize=(16, 5))
for ax, perp in zip(axes, perplexities):
    scatter2d(embeds[perp], y_s, ax, f'perplexity = {perp}')
plt.tight_layout(); plt.show()

B. In a markdown cell, briefly answer:

  1. Describe how the embedding changes when the perplexity goes from 5 to 100 (cluster shapes, fragmentation, global arrangement).

  2. Which quantity of the lecture does the perplexity control? (think about \(p_{j|i}\) and \(\sigma_i\))

  3. The KL divergence is smaller for one of the perplexities. Can we use it to choose the best perplexity? Can we read the distances between clusters and the cluster sizes in a t-SNE plot?

B. Your answer here:

  1. …

  2. …

  3. …


3. Going Further (Homework)

The sections below are for you to complete after class.

3.1. Reconstruction of Images with PCA

A. The lecture showed that PCA can reconstruct the data from \(k<d\) PCs. For \(k\in\{2,10,50,200\}\), fit a PCA with \(k\) components on X_s, reconstruct all the images from their \(k\) PCs, and compute the mean squared reconstruction error (mean of the squared differences between X_s and its reconstruction). The cell then displays 4 reconstructed images for each \(k\).

ks = [2, 10, 50, 200]
recs, mses = {}, {}
for k in ks:
    pca_k = None          # TODO: a PCA with k components fitted on X_s
    recs[k] = None        # TODO: the reconstruction of X_s from its k PCs (project the images on the k PCs, then go back to the 784-dimensional space)
    mses[k] = None        # TODO: the mean of the squared differences between X_s and recs[k]
print({k: round(v, 5) for k, v in mses.items()})

fig, axes = plt.subplots(len(ks) + 1, 4, figsize=(7, 9))
for j in range(4):
    axes[0, j].imshow(X_s[j].reshape(28, 28), cmap='gray'); axes[0, j].set_title('original', fontsize=8)
    for i, k in enumerate(ks, start=1):
        axes[i, j].imshow(recs[k][j].reshape(28, 28), cmap='gray'); axes[i, j].set_title(f'k = {k}', fontsize=8)
for ax in axes.ravel(): ax.axis('off')
plt.tight_layout(); plt.show()

B. In a markdown cell: how does the error behave when \(k\) increases? From which \(k\) can you recognize the garments? Compare with the number of PCs needed for 90% of the variance in 2.2.

B. Your answer here:

…

3.2. Speeding up t-SNE with PCA

A. A common practice is to apply PCA first (here 50 PCs) and then t-SNE on the PCs. Fit a PCA with 50 components on X_s, run a t-SNE (perplexity 30, random_state=SEED) on these 50 PCs, measure the time and plot the result next to the t-SNE of 2.3.

pca50 = None        # TODO: a PCA with 50 components fitted on X_s
X_50 = None         # TODO: the data X_s projected on these 50 PCs

t0 = time.time()
Z_tsne50 = None     # TODO: the 2-dimensional t-SNE embedding (perplexity 30, random_state=SEED) of X_50
print(f'{time.time() - t0:.0f}s | variance kept by the 50 PCs: {pca50.explained_variance_ratio_.sum():.1%}')

fig, axes = plt.subplots(1, 2, figsize=(12, 5))
scatter2d(Z_tsne, y_s, axes[0], 't-SNE on the 784 pixels')
scatter2d(Z_tsne50, y_s, axes[1], 't-SNE on the 50 first PCs')
plt.tight_layout(); plt.show()

B. In a markdown cell: is the picture similar? Why does the PCA preprocessing speed up t-SNE and why can it even help (think about the noise and about the distances in high dimension)?

B. Your answer here:

…

3.3. More Experiments

A. Do the following (add cells below):

  1. Stability: run the t-SNE of 2.3 with 3 different random_state. What stays the same and what changes between the runs?
  2. PCA + kNN (Lab 8): split X_s into train/test (80/20, stratified). For \(k\in\{2,5,10,20,50,100\}\) PCs, fit PCA on the training set only, train a kNN classifier on the PCs and plot the test accuracy against \(k\). How many PCs are enough? Compare with the accuracy of the kNN on the 784 pixels.
  3. USArrests with t-SNE: apply a t-SNE (perplexity 10) on the standardized USArrests data and compare the 2D picture with the biplot of 1.5.
# your code here

A. Your answer here:

…


Wrap-up

In this lab you:

  • Explored the USArrests data and saw why PCA must be applied on standardized data when the variables have different scales (Sections 1.1-1.2).
  • Computed PCA by hand (eigen-decomposition of the correlation matrix), measured the variance explained, and reconstructed the data from the first \(k\) PCs (Sections 1.3-1.4).
  • Interpreted the PCs with a correlation circle and a biplot (Section 1.5).
  • Embedded Fashion-MNIST in 2D with PCA and t-SNE, and explored the effect of the perplexity (Section 2).
  • (At home) Reconstructed images with PCA, combined PCA and t-SNE, and ran more experiments (Section 3).

The core idea: PCA is a linear, deterministic, interpretable rotation that keeps the largest variance (good for summarizing, compressing and reconstructing); t-SNE is a non-linear, stochastic, visualization-only embedding that keeps neighborhoods (clusters are meaningful, distances between clusters and cluster sizes are not).