Unsupervised Learning

What Is Unsupervised Learning?

Unsupervised learning finds hidden structure in data with no labels. The model learns patterns, groupings, or compressed representations from the input $X$ alone.

Main Tasks

Task	Goal	Examples
Clustering	Group similar points	Customer segmentation, document clustering
Dimensionality Reduction	Compress features	Visualization, noise removal, preprocessing
Density Estimation	Model the data distribution	Anomaly detection, generative models
Association Rules	Find co-occurrence patterns	Market basket analysis

K-Means Clustering

K-Means partitions $n$ data points into $k$ clusters by alternating between two steps:

1. Assignment: assign each point to the nearest centroid $c_i = \arg\min_j \|x_i - \mu_j\|^2$

2. Update: recompute centroids as cluster means $\mu_j = \frac{1}{|C_j|} \sum_{i \in C_j} x_i$

Minimizes the Within-Cluster Sum of Squares (WCSS): $J = \sum_{j=1}^{k} \sum_{i \in C_j} \|x_i - \mu_j\|^2$

Choosing K — The Elbow Method

Plot WCSS vs. $k$; look for the "elbow" where adding more clusters gives diminishing returns.

Limitations

• Must specify $k$ in advance
• Assumes spherical, equally-sized clusters
• Sensitive to outliers (use K-Medoids instead)
• Converges to local minima — run multiple times with different initializations (K-Means++)

DBSCAN

Density-Based Spatial Clustering of Applications with Noise — finds clusters of arbitrary shape and automatically identifies outliers.

Two hyperparameters:

• ε (eps): neighborhood radius
• min_samples: minimum points to form a dense region

Point types:

• Core point: has ≥ min_samples neighbors within ε
• Border point: within ε of a core point but not core itself
• Noise point: neither core nor border → labeled as outlier (-1)

When to Use DBSCAN

• Unknown or variable number of clusters
• Clusters of arbitrary shape (crescents, rings)
• Need explicit noise/outlier detection
• Clusters of varying density → use HDBSCAN instead

Hierarchical Clustering

Builds a dendrogram (tree) of clusters without specifying $k$ in advance.

Agglomerative (bottom-up):

1. Start: each point is its own cluster
2. Merge the two closest clusters
3. Repeat until all points are in one cluster
4. Cut the dendrogram at desired height → choose $k$

Linkage Criteria (how to measure cluster distance)

Linkage	Distance Measure	Cluster Shape
Single	Min pairwise distance	Long chains (chaining effect)
Complete	Max pairwise distance	Compact, roughly equal sizes
Average	Mean pairwise distance	Balanced, general purpose
Ward	Minimizes variance increase	Best for compact spherical clusters

import numpy as np
from sklearn.datasets import make_blobs, make_moons
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

# Generate datasets
X_blobs, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.6, random_state=42)
X_moons, _ = make_moons(n_samples=300, noise=0.05, random_state=42)
X = StandardScaler().fit_transform(X_blobs)

# K-Means
kmeans = KMeans(n_clusters=4, init="k-means++", n_init=10, random_state=42)
labels_km = kmeans.fit_predict(X)
print(f"K-Means      silhouette: {silhouette_score(X, labels_km):.3f}")

# Elbow method
wcss = [KMeans(n_clusters=k, n_init=10, random_state=42).fit(X).inertia_
        for k in range(2, 10)]
print(f"WCSS by k:   {[f'{w:.0f}' for w in wcss]}")

# DBSCAN — great for arbitrary shapes
X_moons_scaled = StandardScaler().fit_transform(X_moons)
dbscan = DBSCAN(eps=0.3, min_samples=5)
labels_db = dbscan.fit_predict(X_moons_scaled)
n_clusters = len(set(labels_db)) - (1 if -1 in labels_db else 0)
n_noise = (labels_db == -1).sum()
print(f"DBSCAN       clusters: {n_clusters}, noise points: {n_noise}")

# Hierarchical
hc = AgglomerativeClustering(n_clusters=4, linkage="ward")
labels_hc = hc.fit_predict(X)
print(f"Hierarchical silhouette: {silhouette_score(X, labels_hc):.3f}")

# Silhouette score: ranges -1 to 1; higher is better
# Rule: > 0.5 good structure, 0.25-0.5 weak, < 0.25 no structure

Principal Component Analysis (PCA)

PCA finds the directions of maximum variance in the data and projects onto a lower-dimensional subspace.

Steps:

1. Center the data: $X \leftarrow X - \bar{X}$
2. Compute covariance matrix: $C = \frac{1}{n-1} X^T X$
3. Eigen-decompose: $C = V \Lambda V^T$
4. Project: $Z = X V_k$ (top $k$ eigenvectors)

Explained Variance Ratio: the fraction of total variance captured by each component. Choose $k$ to capture 90–95% of variance.

$\text{Explained Variance}_j = \frac{\lambda_j}{\sum_i \lambda_i}$

Use Cases

• Visualization (project to 2D/3D)
• Noise removal (drop low-variance components)
• Speed up training (reduce features before feeding to ML model)
• Multicollinearity removal

t-SNE and UMAP

t-SNE (t-distributed Stochastic Neighbor Embedding) is optimized for 2D/3D visualization:

• Preserves local structure (nearby points stay nearby)
• Does NOT preserve global distances
• Non-deterministic, slow on large datasets
• Key hyperparameter: perplexity (5–50; try 30)

UMAP (Uniform Manifold Approximation and Projection):

• Faster than t-SNE (especially on large datasets)
• Preserves both local and more global structure
• Deterministic (with fixed seed)
• Better for downstream tasks (embeddings can be reused)

Comparison

Method	Speed	Local Structure	Global Structure	Use Case
PCA	Very fast	Poor	Good	Preprocessing, linear data
t-SNE	Slow	Excellent	Poor	Visualization only
UMAP	Fast	Excellent	Good	Visualization + downstream ML

import numpy as np
from sklearn.datasets import load_digits
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE
from sklearn.preprocessing import StandardScaler

# Load high-dimensional dataset (64 features, 10 classes)
X, y = load_digits(return_X_y=True)
X_scaled = StandardScaler().fit_transform(X)
print(f"Original shape: {X.shape}")  # (1797, 64)

# ── PCA ─────────────────────────────────────────────────────
pca = PCA(n_components=0.95)   # keep 95% of variance
X_pca = pca.fit_transform(X_scaled)
print(f"PCA shape: {X_pca.shape}")   # (1797, ~29)
print(f"Explained variance per component: {pca.explained_variance_ratio_[:5].round(3)}")

# 2D PCA for visualization
pca2d = PCA(n_components=2)
X_pca2d = pca2d.fit_transform(X_scaled)

# ── t-SNE ────────────────────────────────────────────────────
# Best practice: PCA first (reduce to ~50 dims), then t-SNE
X_pca50 = PCA(n_components=50).fit_transform(X_scaled)
tsne = TSNE(n_components=2, perplexity=30, n_iter=1000, random_state=42)
X_tsne = tsne.fit_transform(X_pca50)
print(f"t-SNE shape: {X_tsne.shape}")   # (1797, 2)

# ── UMAP ─────────────────────────────────────────────────────
# pip install umap-learn
from umap import UMAP
umap = UMAP(n_components=2, n_neighbors=15, min_dist=0.1, random_state=42)
X_umap = umap.fit_transform(X_scaled)

# Both X_tsne and X_umap are 2D — use matplotlib to visualize clusters

Summary

• K-Means: fast, simple, spherical clusters, requires $k$ upfront
• DBSCAN: arbitrary shapes, automatic outlier detection, requires ε and min_samples
• Hierarchical: no $k$ needed, produces dendrogram, computationally expensive
• PCA: linear dimensionality reduction, fast, interpretable components
• t-SNE/UMAP: non-linear visualization, t-SNE for local structure, UMAP for both

Next: Reinforcement Learning — agents that learn by trial and error from environmental feedback.