Unsupervised Learning & Embeddings

Learning without labels

In supervised learning (M55, M56) every training example came with the right answer. In unsupervised learning there is no answer column; the algorithm looks for structure in X alone. That sounds vague, so it helps to name the three questions we will answer:

Because there are no labels, there is no single "accuracy" to optimize. Evaluating unsupervised results needs internal measures (how tight and separated are the clusters?), downstream usefulness (do the segments help the marketing team?), and human judgment. Keep that humility in mind: an algorithm will always return clusters, even on pure noise.

Remember: unsupervised learning finds groups, directions, and outliers in unlabeled data; judge it by usefulness, not by a single score.

k-means from scratch

k-means splits the data into k clusters, each represented by its centroid (the mean of its points). It alternates two steps until nothing changes:

1. Assign: put every point in the cluster of its nearest centroid.
2. Update: move every centroid to the mean of the points assigned to it.

Each step can only lower (or keep) the inertia, the sum of squared distances from points to their centroid, so the algorithm always converges. But it converges to a local minimum that depends on the starting centroids. Two remedies are standard: k-means++ initialization (pick each new starting centroid far from the ones already chosen) and running several restarts (n_init) and keeping the run with the lowest inertia. Step through it here, and try a bad random start versus k-means++:

Remember: assign to nearest centroid, move centroids to means, repeat. It minimizes inertia, finds a local optimum, and likes round clusters on scaled features.

k-means in scikit-learn, and choosing k

KMeans(n_clusters=k, n_init=10, random_state=0) uses k-means++ and 10 restarts by default. After fit, look at labels_, cluster_centers_, and inertia_; new points get clusters from predict. But what k? Two common heuristics:

• Elbow method: plot inertia against k. Inertia always falls as k grows (with k = n it is zero), but it falls steeply until the true structure is captured, then flattens. The bend is the "elbow". Often ambiguous.
• Silhouette score: for each point, a = mean distance to its own cluster, b = mean distance to the nearest other cluster, and s = (b − a) / max(a, b). Near 1 means well inside its cluster, near 0 means on a border, negative means probably misassigned. Average over points; higher is better.

Remember: inertia always decreases with k; look for the elbow, prefer the silhouette peak, and sanity-check that the clusters mean something to a human.

DBSCAN for odd shapes, and hierarchical clustering

DBSCAN (density-based spatial clustering of applications with noise) defines clusters as dense regions. A point with at least min_samples neighbors within radius eps is a core point; clusters grow by chaining core points that are within eps of each other; points reachable from no core point are noise (label -1). Consequences: you do not choose k, clusters can have any shape, and outliers are labeled rather than forced into a cluster. The price is choosing eps (a k-distance plot helps) and trouble when clusters have very different densities.

Hierarchical (agglomerative) clustering starts with every point as its own cluster and repeatedly merges the two closest clusters. The full merge history is a tree called a dendrogram; cutting it at a height gives a clustering, so you can choose the number of clusters after seeing the tree. The linkage decides what "closest clusters" means: ward (merge that least increases variance, similar to k-means), single (closest pair of points; can follow chains), complete, average. It costs O(n²) memory, so it suits thousands of points, not millions.

Remember: DBSCAN finds arbitrary shapes and marks noise, but needs eps; hierarchical clustering gives a whole tree you can cut at any level.

Dimensionality reduction: PCA, t-SNE, UMAP

Principal component analysis (PCA), which you met in M49, finds the orthogonal directions along which the (centered) data varies most. Projecting onto the first few principal components compresses the data while keeping as much variance as possible. explained_variance_ratio_ tells you what fraction each component keeps. PCA is linear, fast, deterministic, and invertible (approximately), which makes it good for preprocessing, compression, and denoising.

Two dimensions of PCA mix the digit classes together, because the boundaries between digits are curved. t-SNE (t-distributed stochastic neighbor embedding) and UMAP (uniform manifold approximation and projection) are nonlinear methods built for visualization: they try to keep each point's nearest neighbors nearby in 2-D. They make beautiful, well-separated maps, with caveats: distances between clusters and cluster sizes in the picture are not meaningful, results change with hyperparameters (t-SNE's perplexity) and random seeds, and t-SNE cannot embed new points afterwards. Use them to look, not as features for a model. t-SNE is in scikit-learn (sklearn.manifold.TSNE); UMAP is the separate umap-learn package, which you would add with pixi add umap-learn.

Remember: PCA for compression and preprocessing (linear, fast, reusable); t-SNE/UMAP for 2-D pictures of neighborhoods (do not read distances between clusters).

Embeddings and cosine similarity

An embedding is a vector that represents an item so that similar items get nearby vectors. You already made some: a PCA projection embeds images; a row of the user × film rating matrix embeds a user by their tastes. Modern systems learn embeddings for words, sentences, images, products, and users with neural networks (M58). Whatever produced them, using them looks the same: compare vectors.

The standard comparison is cosine similarity, the cosine of the angle between two vectors:

cos(a, b) = (a · b) / (‖a‖ ‖b‖)

It is 1 for vectors pointing the same way, 0 for perpendicular (unrelated), −1 for opposite. Crucially it ignores length. A long review and a short review about the same topic have very different word counts, but point in the same direction. If vectors are normalized to length 1, cosine similarity is just the dot product, and ranking by cosine is the same as ranking by Euclidean distance.

Real embeddings have hundreds of dimensions learned from data, not four chosen by hand, and nobody can name what each dimension means. A simpler, very practical text representation is TF-IDF (term frequency × inverse document frequency): a document becomes a sparse vector with one entry per word, weighted up when the word is frequent in this document and down when it appears in many documents ("the" gets almost zero weight). sklearn.feature_extraction.text.TfidfVectorizer computes it and L2-normalizes the rows, so the dot product of two rows is their cosine similarity.

Remember: an embedding is a vector where similar things are close; compare with cosine similarity; TF-IDF is a strong, simple text embedding.

Nearest-neighbor search

Given a query vector, find the k stored vectors closest to it. That single operation powers "similar products", k-NN classification, de-duplication, and retrieval for chatbots. There are three tiers of answers.

1. Brute force

Compute the distance from the query to every stored vector and take the k smallest. With NumPy this is a matrix product and an argpartition: O(n · d) per query, exact, and fine up to a few hundred thousand vectors. Always start here.

2. Space-partitioning trees (exact)

A KD-tree recursively splits space on one coordinate at a time, like a binary search tree for points. A query descends to its region and only checks nearby boxes, skipping most points: roughly O(log n) per query in low dimensions. scipy.spatial.KDTree (see M50) and sklearn.neighbors.NearestNeighbors(algorithm="kd_tree") (or "ball_tree") provide them.

The curse of dimensionality

Trees stop helping in high dimensions (roughly beyond 20). Worse, in high dimensions all distances become similar: with random points in 1,000 dimensions the nearest neighbor is barely closer than the farthest one, so "nearest" carries less meaning and pruning cannot skip anything. Run the experiment:

Real embeddings escape the worst of this because they are not uniform noise: the data lies near a much lower-dimensional structure. But exact search over millions of 768-dimensional vectors is still too slow, which is why the third tier exists.

3. Approximate nearest neighbors (ANN)

ANN methods return almost the true neighbors (measured by recall@k: the fraction of the true top-k found) in a tiny fraction of the time.

• Locality-sensitive hashing (LSH): hash vectors so similar ones collide. For cosine similarity, draw random hyperplanes; each vector's hash is the pattern of which side of each plane it falls on. Vectors at a small angle usually get the same bits. Build several independent hash tables so true neighbors only need to collide in one of them, then check just the union of the query's buckets.
• Graph indexes such as HNSW (hierarchical navigable small world): connect each vector to some near neighbors in a layered graph; a search greedily walks the graph toward the query, starting in a sparse top layer for long jumps and refining in denser lower layers. Very fast with high recall; the most common choice today.
• Quantization and inverted files (IVF, product quantization): cluster the vectors (k-means again), search only the nearest clusters, and compress vectors to save memory.

Libraries such as FAISS and hnswlib implement these indexes. Vector databases wrap an ANN index with storage, metadata filtering ("only products in stock"), updates, and replication; options range from dedicated services to extensions for existing databases (for example pgvector for PostgreSQL). For a few hundred thousand vectors, brute-force NumPy is often fast enough; reach for ANN when measurements tell you to.

Remember: brute force first; KD-trees for low dimensions; ANN (LSH, HNSW, IVF) for millions of high-dimensional vectors, trading a little recall for a lot of speed.

Anomaly detection with Isolation Forest

An anomaly (outlier) is a record that does not look like the rest. The isolation forest uses a clever observation: if you split the data with random cuts (random feature, random threshold), an unusual point gets isolated in its own region after very few cuts, while a typical point deep inside a cluster needs many. Average the number of cuts over many random trees and you get an anomaly score. It needs no labels, scales well, and copes with many features. contamination sets the expected fraction of anomalies, which decides the threshold for predict (which returns -1 for anomalies, 1 for normal).

Remember: isolation forest scores how quickly random cuts isolate a point; tune contamination to your expected anomaly rate.

Practice

NumPy and scikit-learn are available.

import numpy as np

def assign(X, centroids):
    d2 = ((X[:, None, :] - centroids[None, :, :]) ** 2).sum(axis=2)
    return d2.argmin(axis=1)

import numpy as np

def update(X, labels, old_centroids):
    new = np.array(old_centroids, dtype=float, copy=True)
    for j in range(len(new)):
        members = X[labels == j]
        if len(members):
            new[j] = members.mean(axis=0)
    return new

def inertia(X, labels, centroids):
    return float(((X - centroids[labels]) ** 2).sum())

import numpy as np

def cosine_matrix(A):
    A = np.asarray(A, dtype=float)
    norms = np.linalg.norm(A, axis=1, keepdims=True)
    U = np.divide(A, norms, out=np.zeros_like(A), where=norms > 0)
    return U @ U.T

import numpy as np

def knn(query, data, k):
    dist = np.linalg.norm(np.asarray(data) - np.asarray(query), axis=1)
    return np.argsort(dist, kind="stable")[:k].tolist()

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

def best_k(X, ks):
    def score(k):
        labels = KMeans(n_clusters=k, n_init=10, random_state=0).fit_predict(X)
        return silhouette_score(X, labels)
    return int(max(ks, key=score))

Mini-project

Quiz

Recap

• Unsupervised learning finds clusters, low-dimensional structure, and anomalies without labels.
• k-means alternates assign and update, minimizes inertia, needs scaled features and a chosen k; use k-means++ and restarts.
• Choose k with the elbow and silhouette, then check that clusters make sense.
• DBSCAN finds arbitrary shapes and labels noise; hierarchical clustering yields a dendrogram you can cut.
• PCA compresses linearly and is reusable; t-SNE and UMAP make 2-D neighborhood maps for looking only.
• Embeddings are vectors where similar things are close; compare them with cosine similarity; TF-IDF is a strong text baseline.
• Nearest neighbors: brute force first, KD-trees in low dimensions, ANN (LSH, HNSW, IVF) and vector databases at scale.
• Isolation forests score anomalies by how easily random cuts isolate a point.

Going further

• scikit-learn: clustering (with a comparison of algorithms on toy datasets)
• scikit-learn: decomposition (PCA and friends)
• scikit-learn: manifold learning (t-SNE)
• scikit-learn: nearest neighbors
• scipy.spatial.KDTree
• How to use t-SNE effectively (Distill)
• Next: M58 · Neural Networks from Scratch.