Unsupervised learning

What unsupervised learning does

Definition. In unsupervised learning the data has no labels: only feature vectors $x_1, \dots, x_n$. The aim is to find structure, such as groups of similar points (clustering) or a few directions that capture most of the variation (dimensionality reduction).

Exam point. There is no "correct answer" to compare against, so results are judged by measures such as the within-cluster sum of squares or the share of variance explained.

k-means clustering

Definition. k-means splits the data into $k$ clusters by minimising the within-cluster sum of squared distances

$J = \sum_{j=1}^{k} \sum_{x \in C_j} \lVert x - \mu_j \rVert^2 ,$

where $\mu_j$ is the mean (centroid) of cluster $C_j$.

Lloyd's algorithm.

1. Choose $k$ initial centroids.
2. Assign every point to its nearest centroid.
3. Update every centroid to the mean of the points assigned to it.
4. Repeat steps 2–3 until the assignments stop changing.

Each step can only lower $J$, so the algorithm always stops, but it may stop at a local minimum that depends on the starting centroids. Running it from several random starts (or using k-means++ seeding) helps. Clusters are convex (roughly spherical); k-means is sensitive to outliers, because a mean is pulled by extreme values.

Choosing $k$. $J$ always decreases as $k$ grows (with $k = n$ it is 0), so we look for an "elbow" where the decrease slows down, or use the silhouette score.

Solved examples

Example 1: one iteration. Points on a line: 1, 2, 3, 10, 11, 12. Start with centroids $\mu_1 = 1$, $\mu_2 = 3$.

1. Assign: 1 and 2 are nearer 1; 3 is at distance 0 from $\mu_2$; 10, 11, 12 are nearer 3. Clusters {1, 2} and {3, 10, 11, 12}.
2. Update: $\mu_1 = 1.5$, $\mu_2 = 36/4 = 9$.
3. Assign again: 3 is at distance 1.5 from 1.5 and 6 from 9, so it moves to cluster 1. Clusters {1, 2, 3} and {10, 11, 12}.
4. Update: $\mu_1 = 2$, $\mu_2 = 11$. Assigning again changes nothing, so the algorithm has converged with $J = (1+0+1) + (1+0+1) = 4$.

Example 2: why the start matters. With points 0, 2, 4 and $k = 2$, starting centroids 0 and 4 give clusters {0, 2} and {4} (or {0} and {2, 4}); both are stable. So k-means can end in different solutions from different starts.

k-medoids

Definition. k-medoids is like k-means but each cluster centre must be one of the data points (the medoid: the point with the smallest total distance to the others in its cluster). It works with any distance measure, and because it does not average coordinates it is more robust to outliers than k-means.

Example 3. Cluster {1, 2, 3, 50}. The mean is 14, dragged by the outlier 50. Total distances from each point: from 1: $1+2+49 = 52$; from 2: $1+1+48 = 50$; from 3: $2+1+47 = 50$; from 50: $49+48+47 = 144$. The medoid is 2 (or 3), a representative point not pulled by the outlier.

Hierarchical clustering

Definition. Hierarchical clustering builds a tree of clusters (a dendrogram) instead of one fixed split.

• Bottom-up (agglomerative): start with every point as its own cluster and repeatedly merge the two closest clusters until one cluster remains.
• Top-down (divisive): start with one cluster and repeatedly split a cluster.

Cutting the dendrogram at a chosen height gives the clusters; $k$ does not have to be fixed in advance.

Linkage: the distance between two clusters $A$ and $B$.

• Single linkage: $\min_{a \in A, b \in B} d(a,b)$, the closest pair. Tends to form long chains.
• Complete linkage: $\max_{a, b} d(a,b)$, the farthest pair. Gives compact clusters.
• Average linkage: the average of all pairwise distances.
• Centroid / Ward: distance between means, or the increase in within-cluster variance.

Solved example

Example 4. Points on a line: A = 0, B = 1, C = 4, D = 6.

1. Closest pair: A–B (distance 1). Merge {A, B}.
2. Single linkage distances now: {A,B}–C $= \min(4,3) = 3$; {A,B}–D $= 5$; C–D $= 2$. Merge {C, D}.
3. Finally merge {A,B} with {C,D} at single-linkage distance $\min(4,6,3,5) = 3$.

With complete linkage the last merge would happen at $\max(4,6,3,5) = 6$ instead. The merge order can be the same while the merge heights differ.

Dimensionality reduction

Why. Many features are correlated or redundant. Reducing dimension speeds up learning, removes noise, and lets us plot data in 2 or 3 dimensions.

Principal component analysis (PCA)

Definition. PCA finds new orthogonal axes (principal components) ordered by how much variance of the data they capture.

1. Centre the data: subtract the mean of every feature.
2. Compute the covariance matrix $S = \frac{1}{n} X^\top X$ (or $\frac{1}{n-1}$), a $d \times d$ symmetric matrix.
3. Find its eigenvectors $v_1, v_2, \dots$ with eigenvalues $\lambda_1 \ge \lambda_2 \ge \dots \ge 0$.
4. The first principal component is $v_1$; the variance of the data along $v_j$ is $\lambda_j$.
5. Keep the top $m$ components and project: $z = V_m^\top x$.

The share of variance explained by the first $m$ components is $\frac{\lambda_1 + \dots + \lambda_m}{\lambda_1 + \dots + \lambda_d}$, and $\lambda_1 + \dots + \lambda_d = \operatorname{trace}(S)$ = the total variance.

Exam points.

• Components are orthogonal (eigenvectors of a symmetric matrix) and the projected coordinates are uncorrelated.
• PCA is sensitive to scale: standardise features measured in different units first.
• PCA can also be computed from the SVD of the centred data matrix $X = U\Sigma V^\top$: the columns of $V$ are the components and the variances are $\sigma_j^2 / n$.
• PCA is linear and unsupervised; it ignores labels.

Solved examples

Example 5: variance explained. A covariance matrix has eigenvalues 6, 3 and 1. The first component explains $6/10 = 60\%$ of the variance; the first two explain $9/10 = 90\%$.

Example 6: from a 2×2 covariance matrix. $S = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$. Eigenvalues: $\lambda^2 - 4\lambda + 3 = 0$, so $\lambda = 3, 1$. For $\lambda = 3$: $(S - 3I)v = 0$ gives $v \propto (1, 1)$. The first principal component is $\frac{1}{\sqrt2}(1,1)$, capturing $3/4 = 75\%$ of the variance.

Distance and similarity: the input to every clustering method

Clustering groups points that are "close", so the result depends completely on how closeness is measured.

Measure	Formula for $x, y \in \mathbb{R}^d$	Notes
Euclidean ($L_2$)	$\sqrt{\sum_i (x_i - y_i)^2}$	default for k-means
Manhattan ($L_1$)	$\sum_i \lvert x_i - y_i \rvert$	city-block distance
Chebyshev ($L_\infty$)	$\max_i \lvert x_i - y_i \rvert$	largest single difference
Minkowski ($L_p$)	$\left(\sum_i \lvert x_i - y_i\rvert^p\right)^{1/p}$	$p = 1, 2, \infty$ give the three above
Cosine similarity	$\dfrac{x \cdot y}{\lVert x\rVert\,\lVert y\rVert}$	angle only, ignores length; used for text

Example A: the same pair, three distances. $x = (1, 2)$, $y = (4, 6)$. Differences are 3 and 4.

• Euclidean: $\sqrt{9 + 16} = 5$.
• Manhattan: $3 + 4 = 7$.
• Chebyshev: $\max(3, 4) = 4$.

Always $L_\infty \le L_2 \le L_1$.

Example B: cosine. $a = (1, 0)$, $b = (1, 1)$: $\cos\theta = \frac{1}{1 \cdot \sqrt 2} \approx 0.707$, so the angle is $45^\circ$. Scaling $b$ to $(5, 5)$ does not change the cosine, but it changes the Euclidean distance a lot.

Scaling matters. If one feature is income in rupees (values near $10^5$) and another is age in years (values near 30), Euclidean distance is decided almost entirely by income. Standardise each feature first: $z = (x - \text{mean}) / \text{standard deviation}$. Min–max scaling to $[0, 1]$ is the other common choice.

k-means in depth

Why the objective never increases

Write $J(C, \mu) = \sum_j \sum_{x \in C_j} \lVert x - \mu_j\rVert^2$. Lloyd's algorithm alternates two steps, and each one minimises $J$ over one set of variables while the other is held fixed.