Aller au contenu

Lab Session 3 - Unsupervised Learning⚓

Note

Before you begin, make sure you have downloaded the latest update of the course slides from here, and keep them close while doing the lab.

Note

You may use any AI assistant to help you here (and at any moment in the project). Comprehension is what is graded though, so use them as helpers, never automatically and blindly!

Objectives of the lab⚓

At the end of this session, you will be able to:

  • Cluster data with KMeans, and choose \(K\) with the elbow and the silhouette heuristics.
  • Recognize when the assumptions of K-means break, and pick an algorithm that fits the shape of your data.
  • Prepare your features so that distances actually mean something (scaling, removing useless features).
  • Decompose data with PCA: components, explained variance, reconstruction.
  • Visualize high dimensional data in 2D with PCA and TSNE — and know what a t-SNE plot does not tell you.
  • Evaluate a result without ground truth, and with labels when they happen to exist.
  • Run a first unsupervised exploration of your own project data.

The lab has three parts:

Part 1 ~1h Toy datasets you generate yourself: the whole unsupervised toolbox on data whose answer you already know.
Part 2 ~45 min MNIST: the same tools on a real, high dimensional dataset (the one of the course slides).
Part 3 ~45 min Your project data: cluster it, visualize it, and confront the result with what you know.

Note

Whenever possible, we have included links to the official documentation of the functions you need to use. Check them out, you'll save a lot of time!

Prerequisites⚓

You need the environment of lab 1 with scikit-learn installed in lab 2. Nothing new to install today (except, optionally, umap-learn at the very end).

From the previous labs, we assume you can: build a (N, d) numpy array from a dataset, make a scatter plot, and use the fit / predict API of sklearn.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

from sklearn.datasets import make_blobs, make_moons, make_swiss_roll, fetch_openml
from sklearn.preprocessing import StandardScaler
from sklearn.feature_selection import VarianceThreshold
from sklearn.cluster import KMeans, DBSCAN
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE
from sklearn.metrics import silhouette_score, adjusted_rand_score
from sklearn.metrics import homogeneity_completeness_v_measure

rng = np.random.default_rng(0)

What changes with respect to lab 2⚓

Three things, and they matter for everything below:

  • No y in fit. Every model today is fitted with model.fit(X) alone. Labels, when they exist, are used only for display and evaluation, never for fitting.
  • No train/test split (see the course): there is no right answer to generalize to, so you fit on all the data you have.
  • One exception, worth remembering: if an unsupervised step is a preprocessing for a supervised model (e.g. a PCA before a classifier), then it must be fitted on the training set only, otherwise information leaks from the test set.
  • fit_predict and fit_transform replace predict and score: clustering methods assign a cluster index to each sample (fit_predict), decomposition and manifold methods produce new coordinates (fit_transform).

Table of contents of the lab⚓

Part 1 — The toolbox on data you control (~1h)

  1. Generate your toy datasets
  2. A first clustering with K-means
  3. Choosing \(K\): elbow and silhouette
  4. Distances have units
  5. Where K-means breaks
  6. Two dimensions are not enough: a controlled high dimensional example

Part 2 — A real dataset: MNIST (~45 min)

  1. Load and subsample MNIST
  2. Which pixels carry information?
  3. Clustering MNIST, and evaluating it
  4. Decomposition: PCA on MNIST
  5. Visualization: PCA vs t-SNE

Part 3 — Your own project data (~45 min)

  1. Your own project data

Part 1 — The toolbox on data you control⚓

The point of Part 1 is that you decide what the structure of the data is, so you can tell whether an algorithm found it.

1.1 Generate your toy datasets⚓

Reuse make_blobs from lab 2, and add make_moons:

1
2
3
X_blobs, y_blobs = make_blobs(n_samples=500, n_features=2, centers=4,
                              cluster_std=1.0, random_state=0)
X_moons, y_moons = make_moons(n_samples=500, noise=0.06, random_state=0)
1
2
3
###  - Plot both datasets with scatter, side by side.
###  - Plot them twice: once without colors (what the algorithm sees),
###    once colored with y (what you know, and the algorithm does not).

Important

Keep the "without colors" version in mind for the whole lab. Your algorithms only ever see the black-and-white version. y_blobs and y_moons exist here only so that you can check the answers.

1.2 A first clustering with K-means⚓

Use KMeans. The number of clusters is a parameter you must decide in advance:

1
2
kmeans = KMeans(n_clusters=4, n_init=10, random_state=0)
labels = kmeans.fit_predict(X_blobs)
1
2
3
4
###  - Cluster X_blobs, and scatter plot it colored by the cluster labels.
###  - Add the centroids (kmeans.cluster_centers_) on top of the plot,
###    as big markers (e.g. marker="X", s=200).
###  - Print kmeans.inertia_ : this is the error E of the course.

Now compare your clusters to the true groups y_blobs. Do not use accuracy: cluster indices are arbitrary, cluster 0 has no reason to be class 0 (the course insists on this: a clustering is a partition, not a labelling). The metric that ignores this permutation is the Adjusted Rand Index:

1
print(adjusted_rand_score(y_blobs, labels))   # 1.0 = same partition, ~0.0 = random
1
2
###  - Print the ARI. Then look at the scatter plot again and find, visually,
###    the points responsible for the missing part of the score.

Tip

K-means depends on its initialization (the course says: NP-hard problem, we only find a local minimum). n_init is the number of restarts sklearn does before keeping the best one. Try n_init=1 with a few different random_state and see how much the result moves. Keeping n_init=10 is a good default habit.

1.3 Choosing \(K\): elbow and silhouette⚓

In practice, nobody tells you the number of clusters. Compute both heuristics of the course over a range of \(K\):

  • the inertia (kmeans.inertia_), which always decreases with \(K\) → look for a bend,
  • the silhouette score (silhouette_score), bounded in \([-1, 1]\) → look for a maximum.
1
2
3
###  - For k in range(2, 11): fit a KMeans, store inertia_ and silhouette_score(X, labels).
###  - Plot the two curves, side by side, as a function of k.
###  - Conclude: which k does each heuristic suggest?

Note

The silhouette needs at least 2 clusters (it compares each point to another cluster), which is why the range starts at 2. On a large dataset it costs \(O(N^2)\) distances, so use its sample_size argument.

1
###  - Do the same on X_moons. Do the two heuristics agree with what you see?

Important

You should already meet an uncomfortable case here. Both heuristics are definitions of what a good clustering is, and on the moons neither of them describes the structure you can see with your eyes. Being able to say "the metric says 2, but the metric is wrong here, and here is why" is exactly the skill this session is about.

1.4 Distances have units⚓

Every method of this session compares distances or variances. Neither is invariant to the scale of your features. Let's break a clustering that worked, by changing nothing but a unit:

1
2
X_stretched = X_blobs.copy()
X_stretched[:, 1] *= 100      # same data, second feature now expressed in "centi-something"
1
2
3
###  - Cluster X_stretched with the same KMeans(n_clusters=4) and compute the ARI again.
###  - Then apply StandardScaler to X_stretched, cluster the result, and recompute the ARI.
###  - Plot the three clusterings to see what happened geometrically.

You should observe a clear drop of the ARI, and a recovery after scaling. Ask yourself what this means for a real dataset with an age in years, a salary in euros and a distance in kilometers in the same matrix.

Tip

Chaining a scaler and a model is what Pipeline is made for: make_pipeline(StandardScaler(), KMeans(n_clusters=4)). Use it, it is one line and it prevents the classical mistake of scaling with the wrong statistics.

1.5 Where K-means breaks⚓

K-means only manipulates means and euclidean distances, so it implicitly looks for round, similarly sized clusters. The moons are neither.

1
###  - Cluster X_moons with KMeans(n_clusters=2), plot the result, compute the ARI.

You should get an ARI around \(0.25\): the algorithm cuts the two moons in half instead of separating them, and no hyperparameter will fix this. The assumption is wrong, so the model must change. Try a density-based method, DBSCAN:

1
2
dbscan = DBSCAN(eps=0.2, min_samples=5)
labels_db = dbscan.fit_predict(X_moons)

Note that DBSCAN does not take a number of clusters: it grows clusters from dense neighborhoods, so the number of clusters is a result. Its two real hyperparameters are eps (the neighborhood radius) and min_samples. Points that belong to no dense region are labelled -1: they are noise, an option K-means does not have.

1
2
3
###  - For eps in [0.05, 0.1, 0.15, 0.2, 0.3, 0.5]:
###      print the number of clusters found, the number of noise points (label == -1), and the ARI.
###  - Plot the two extreme cases. What happens when eps is too small? Too large?

Now the interesting part. Compute the silhouette score of both results (excluding the noise points for DBSCAN):

1
2
###  - silhouette of the KMeans labels on X_moons
###  - silhouette of the DBSCAN labels on X_moons (keep only labels != -1)

Important

The silhouette prefers K-means, the solution you can see is wrong. This is not a bug: as stated in the course, the silhouette (like the inertia) rewards compact and convex clusters, so it encodes a definition of "good cluster" that the moons do not satisfy. A metric always answers one particular question. Whenever you report an internal metric in your project, be able to say which assumption it makes.

Call the teacher and discuss this comparison!

If you have time⚓

Build the other classical failure cases of K-means yourself, and find a model that handles them:

  • Elongated clusters: X @ [[0.6, -0.6], [-0.4, 0.8]] on blobs (anisotropic), then try GaussianMixture, which fits a covariance per cluster.
  • Clusters of very different sizes/densities: make_blobs(..., cluster_std=[1.0, 2.5, 0.5]).
  • Other candidates worth 3 lines of code each: AgglomerativeClustering (try linkage="single" on the moons) and SpectralClustering (try affinity="nearest_neighbors").

Tip

AgglomerativeClustering and SpectralClustering may be very useful for your project; don't hesitate to test them here!

The sklearn clustering comparison page shows all of this on one figure. Look at it after trying, not before.

1.6 Two dimensions are not enough: a controlled high dimensional example⚓

Everything above was 2D so you could plot it. Your project data will not be. Before using dimensionality reduction on a real dataset, let's check it on data whose structure we chose.

Case A — linear structure. Generate blobs in dimension 50, and project them in 2D with PCA:

1
2
3
4
5
X_hd, y_hd = make_blobs(n_samples=1000, n_features=50, centers=5,
                        cluster_std=2.0, random_state=0)

pca = PCA(n_components=2, random_state=0)
X_2d = pca.fit_transform(X_hd)
1
2
3
###  - Scatter plot X_2d, colored with y_hd. Are the 5 groups visible?
###  - Print pca.explained_variance_ratio_.sum(): how much of the data do these 2 components carry?
###  - Cluster with KMeans in the 50D space and in the 2D space: do you get the same ARI?

Case B — curved structure. The "swiss roll" of the course slides:

1
2
X_roll, t_roll = make_swiss_roll(n_samples=1500, noise=0.05, random_state=0)
# t_roll is the position ALONG the roll: the single parameter that generated the data
1
2
3
###  - Project X_roll in 2D with PCA, then with TSNE. Color both plots with t_roll.
###  - Which one "unrolls" the surface, i.e. gives a plot where the color varies smoothly
###    along one direction, without folding back on itself?

Note

PCA only knows straight lines, so it can only photograph the roll from the best angle: layers that are far apart along the surface end up superimposed. t-SNE preserves neighborhoods instead, and recovers the 1D parameter almost exactly. This is the whole idea of manifold learning: the intrinsic dimension (here 1, up to the width of the roll) can be far below \(d\).


Part 2 — A real dataset: MNIST⚓

Same tools, on the dataset used throughout the course slides. You may reproduce some of the figures contained in the slides, so keep them open and close to you!

2.1 Load and subsample MNIST⚓

MNIST is 70000 handwritten digits of \(28 \times 28\) pixels, so \(d = 784\) once vectorized (see the course: the algorithms know nothing about the 2D layout of the pixels). We work on a random subset, both for speed and because t-SNE is \(O(N^2)\)-ish.

1
2
3
4
5
6
7
8
9
mnist = fetch_openml("mnist_784", version=1, as_frame=False)
X_all, y_all = mnist.data, mnist.target.astype(int)
print(X_all.shape, X_all.min(), X_all.max())

# Random subset of 5000 samples
idx = rng.choice(len(X_all), size=5000, replace=False)
X, y = X_all[idx] / 255.0, y_all[idx]      # pixels scaled to [0, 1]

np.savez_compressed("mnist_subset.npz", X=X, y=y)   # so you download it only once

Tip

The download takes a minute or two the first time (it is cached in ~/scikit_learn_data). Once you have saved the .npz, reload it with d = np.load("mnist_subset.npz"); X, y = d["X"], d["y"]. If the network is unreliable in the room, from sklearn.datasets import load_digits gives a much smaller \(8\times8\) version of the same problem, and everything below works with side = 8.

Here is the only plotting helper we provide; it displays any set of MNIST-sized vectors as a grid of images. You will reuse it for examples, masks, centroids, components and reconstructions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def plot_image_grid(vectors, side=28, titles=None, n_cols=10, cmap="gray"):
    """Display a set of vectorized images as a grid.
    - vectors: array of shape (n, side*side)
    - titles: optional list of n titles
    """
    n = len(vectors)
    n_rows = int(np.ceil(n / n_cols))
    fig, axes = plt.subplots(n_rows, n_cols, figsize=(1.2*n_cols, 1.35*n_rows), squeeze=False)
    for i, ax in enumerate(axes.ravel()):
        ax.set_xticks([]); ax.set_yticks([])
        if i < n:
            ax.imshow(vectors[i].reshape(side, side), cmap=cmap)
            if titles is not None:
                ax.set_title(str(titles[i]), fontsize=9)
        else:
            ax.axis("off")
    plt.tight_layout()
    plt.show()
1
2
###  - Plot one example of each digit, with its label as title.
###    Hint: np.where(y == c)[0][0] gives the index of the first sample of class c.

2.2 Which pixels carry information?⚓

On MNIST, feature selection has an obvious meaning: some pixels are (almost) always black.

1
variances = X.var(axis=0)
1
2
###  - Display the variance map: plot_image_grid(variances[None, :]).
###  - How many pixels have a variance of exactly 0?

Now use VarianceThreshold to remove the least informative pixels. Rather than guessing a threshold, pick it as a percentile of the variances, so you directly control the proportion of removed features:

1
2
3
4
5
thr = np.percentile(variances, 50)        # remove the 50% least varying pixels
selector = VarianceThreshold(threshold=thr)
X_selected = selector.fit_transform(X)
mask = selector.get_support()             # boolean, True = kept
print(X.shape, "->", X_selected.shape)
1
2
3
4
5
6
###  - Display the mask as an image: plot_image_grid(mask.astype(float)[None, :]),
###    and a few digits multiplied by the mask (X[i] * mask).
###  - Increase the percentile (75, 90, 95...). Up to which proportion of removed pixels
###    can you still recognize the digits?
###  - Cluster with KMeans(n_clusters=10) on X and on X_selected, and compare the ARI.
###    Did removing half of the pixels cost you anything?

Important

Two lessons here. Selection destroys information, so it has to be justified. So, how would you justify selection here? Discuss this with a teacher!

2.3 Clustering MNIST, and evaluating it⚓

Compute KMEANS on MNIST:

1
kmeans = KMeans(n_clusters=10, n_init=10, random_state=0).fit(X)
1
2
3
4
###  - Display the 10 centroids with plot_image_grid. Do they look like digits?
###    Which digits are missing? Which ones appear twice?
###  - Quantization (course slide): take one sample per class, and display each sample
###    next to its closest centroid, i.e. kmeans.cluster_centers_[kmeans.predict(X_samp)].

Then evaluate, using the different metrics seen in the course:

1
2
3
4
###  1. Internal: silhouette_score(X, kmeans.labels_, sample_size=2000, random_state=0)
###     and the elbow curve for k in [2, 5, 10, 15, 20, 30, 40].
###  2. With labels: adjusted_rand_score, and homogeneity_completeness_v_measure.
###  3. Compare K = 10 and K = 20 with these three numbers.

Important

Take the time to interpret the \(K=10\) vs \(K=20\) comparison, it is the heart of the course's evaluation section. With 20 clusters, homogeneity goes up (each cluster is purer) while completeness goes down (a digit is now split across several clusters), and the ARI does not necessarily improve. There is no contradiction: these numbers answer different questions. Compare visually the centroids to confirm this!

1
2
###  - Build the contingency table between clusters and true digits:
###    pd.crosstab(kmeans.labels_, y). Which digits are systematically confused?

Discuss your findings with a teacher!

2.4 Decomposition: PCA on MNIST⚓

1
pca = PCA(n_components=32, random_state=0).fit(X)
1
2
3
4
5
###  - Display the first 16 components (pca.components_) with plot_image_grid.
###    They are vectors of dimension 784, so they can be displayed as images ("ghost digits").
###  - Plot the cumulative sum of pca.explained_variance_ratio_ as a function of the number
###    of components (fit a PCA without n_components to get all of them).
###  - How many components are needed to keep 90% of the variance? 95%?

Reconstruct, as on the slides. inverse_transform goes back to the pixel space, i.e. it computes \(UV\) of the course:

1
X_reconstructed = pca.inverse_transform(pca.transform(X))
1
2
3
4
5
###  - For K in [1, 2, 5, 10, 32, 100]: fit a PCA, reconstruct the same 10 samples,
###    and display original / reconstruction pairs.
###  - From how many components are the digits recognizable?
###  - Plot the mean reconstruction error, np.mean(np.sum((X - X_reconstructed)**2, axis=1)),
###    as a function of K. What is its value for K = 784, and why is that useless?

Note

Storing 32 coefficients instead of 784 pixels is a compression by a factor ~24, obtained without any label, and most (if not all) the digits stay readable. This is also why PCA is such a common preprocessing: going from \(d=784\) to \(d=32\) directly mitigates the curse of dimensionality of the previous session.

2.5 Visualization: PCA vs t-SNE⚓

Try to reproduce the last figure of the course, comparing PCA with t-SNE on MNIST. Fit the parameters to study their effects.

1
2
3
4
5
X_pca2 = PCA(n_components=2, random_state=0).fit_transform(X)

# Standard recipe: PCA first (denoise + speed up), then t-SNE
X_pca50 = PCA(n_components=50, random_state=0).fit_transform(X)
X_tsne = TSNE(n_components=2, random_state=0, init="pca", perplexity=30).fit_transform(X_pca50)
1
2
###  - Plot both 2D projections side by side, colored with y, with a colorbar or a legend.
###  - Which classes does PCA superimpose? Which ones does t-SNE separate?

Important

The colors are the labels, used only for display: both algorithms ran without them. Doing exactly this is the cheapest sanity check of an unsupervised pipeline, and you will redo it on your own data in Part 3.

The caveats of the course are testable, so test them:

1
2
3
4
###  - Re-run t-SNE with perplexity in [5, 30, 100]. Do the groups you see survive?
###  - Try to call .transform() on a fitted TSNE. Read the error message.
###  - Look at the distance between two groups of your t-SNE plot: what can you conclude
###    from it? (Careful, this is a trick question.)

If you have time⚓

  • Does the decomposition help the clustering? Run KMeans(n_clusters=10) on X_pca50 instead of X, and compare ARI and computation time. This is a downstream evaluation, the most honest kind according to the course.
  • UMAP: pip install umap-learn, then import umap; umap.UMAP().fit_transform(X_pca50). Same usage as t-SNE, usually faster, and preserves a bit more of the global structure.
  • Clustering the t-SNE output: try it, then argue whether it is legitimate. (Hint: re-read the t-SNE caveats.)

Part 3 — Your own project data⚓

Apply the very same pipeline to your project dataset. This is exploratory work: the quality of your exploration and of your justifications will matter more than the beauty of any final plot.

  1. Build your feature matrix. You need a numeric array X of shape (N, d), with no missing values (dropna, or fill them). If your data is not numeric yet (text, images, audio, categorical columns), extract the simplest reasonable features for now, as in lab 2; shallow features are fine today, better representations will come with foundation models in Session 5.

  2. Prepare your features, and say why. Are your columns in comparable units? If not, scale them (§1.4 showed what happens otherwise). Are some columns constant, or duplicated, or almost so?

  3. Look at your data in 2D. Project with PCA, then with t-SNE, and color each plot with everything you have: your target if you have one, but also a category, a date, a source, the length of the sample. This is the highest-value 30 minutes of this lab for most projects: it is how you discover that your data is duplicated, unbalanced, dominated by one feature, or already separated. This step will still be useful for Deep Learning and Foundation models analysis!

  4. How redundant are your features? Plot the cumulative explained variance. If 3 components out of 40 carry 95% of the variance, your 40 columns are measuring far fewer than 40 things.

  5. Cluster it. KMeans with a \(K\) chosen with both heuristics (elbow and silhouette), plus a check of stability: re-run with several random_state and see whether the clusters move. Then try one non-K-means algorithm, chosen for a reason you can state (density-based if your 2D plot shows non-convex shapes, GMM if you see elongated groups, agglomerative if a hierarchy makes sense for your data).

  6. Evaluate, and interpret.

    • Always available: an internal metric (silhouette), plus your own eyes on the 2D plot.
    • If you have labels: adjusted_rand_score and homogeneity_completeness_v_measure for evaluation only, never for fitting.
    • Then the real question: what did your clusters actually capture? Inspect a few samples of each cluster. If your clusters correspond to the recording device, the year, or the source file rather than to your target, that is a finding about your dataset (and a very common one).

Important

Conclude with one question: is this unsupervised step useful for my project, and for what? Acceptable answers include "the 2D projection showed that my two classes overlap completely with these features, so I need better ones", or "there is no cluster structure at this scale". A negative result that you correctly diagnose is worth more than a lucky one!

Note

Keep this notebook and these figures. A 2D projection of your data, colored by your target, may turn into a useful slide in your final presentation (or, conversely, may show the complexity of your task).


What you should take home from this session⚓

  • The unsupervised API: fit(X) alone, then fit_predict / fit_transform, and labels only for evaluation.
  • Choosing \(K\) is a decision you justify: elbow and silhouette are heuristics that can disagree, and both can be wrong.
  • No algorithm is best: K-means assumes round clusters, DBSCAN assumes dense regions, PCA assumes linear structure, t-SNE preserves only neighborhoods. Matching the assumption to the shape of your data is the actual work.
  • Distances have units: scaling is not cosmetic, it may change the result.
  • The reflex of projecting your data in 2D and coloring it with any metadata you have. Nonetheless, never trust blindly a vizualization; hyperparameters may introduce artifacts!
  • A first unsupervised exploration of your own data.