2 Unsupervised Learning

K-Means Clustering & its Variants

Objective Function & Lloyd's Algorithm

Partition $N$ points into $K$ clusters $S = \{S_1, S_2, \dots, S_K\}$ to minimize within-cluster sum of squares (Inertia):

$$\boxed{\min_{S, \mu} \sum_{i=1}^K \sum_{x \in S_i} \|x - \mu_i\|_2^2}$$

Two-step coordinate descent:

1. Assignment step: assign each instance to its closest centroid:
   $$c^{(i)} = \arg\min_j \|x^{(i)} - \mu_j\|_2^2$$
2. Update step: recompute centroids as mean of assigned points:
   $$\mu_j = \frac{\sum_{i=1}^N \mathbf{1}\{c^{(i)} = j\} x^{(i)}}{\sum_{i=1}^N \mathbf{1}\{c^{(i)} = j\}}$$

def calculate_distance(point1, point2):
    return sum((x-y)**2 for x,y in zip(point1,point2))

def k_means_clustering(points: list[tuple[float, ...]], k: int, initial_centroids: list[tuple[float, ...]], max_iterations: int) -> list[tuple[float, ...]]:
    final_centroids = list(initial_centroids)
    for i in range(max_iterations):
        # 1. Assignment step
        labels = [min(range(k), key= lambda x: calculate_distance(point, initial_centroids[x])) for point in points]

        # 2. Update step
        for i in range(k):
            group = [ point for point,label in zip(points, labels) if label == i]
            if group:
                final_centroids[i] = tuple(sum(item)/len(group) for item in zip(*group))
    return final_centroids

Limitations:

• Sensitive to centroid initialization (can get trapped in local minima).
• Assumes spherical, equally-sized clusters with similar density.
• Sensitive to outliers (mean is heavily affected).
• $K$ must be specified in advance.

How to Choose K

• Elbow Method: plot Inertia (SSE) vs $K$. Pick the "elbow" point where marginal loss reduction slows down significantly.
• Silhouette Score: evaluates cohesion vs separation for each sample:
  $$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \in [-1, 1]$$
  where $a(i)$ is mean intra-cluster distance, $b(i)$ is mean nearest-cluster distance. Higher is better.

Variants

1. K-Means++

Addresses initialization sensitivity:

1. Choose first centroid $\mu_1$ uniformly at random from dataset.
2. For each point $x$, compute $D(x)$, the shortest distance to existing centroids.
3. Choose next centroid from points with probability:
   $$\boxed{P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}}$$
4. Repeat steps 2-3 until $K$ centroids are chosen.

Theoretical guarantee: $O(\log K)$-competitive with optimal solution.

2. Mini-Batch K-Means

Optimized for large-scale datasets:

• Samples a mini-batch of size $B \ll N$ at each iteration.
• Centroids updated using online running average: $\mu_k \leftarrow (1-\eta)\mu_k + \eta x$.
• Drastically reduces computation and memory per step with minimal quality drop.

3. K-Medoids (PAM - Partitioning Around Medoids)

• Centroids must be actual data points (medoids) instead of means.
• Can minimize arbitrary dissimilarity (e.g. Manhattan L1 distance) instead of squared Euclidean:
  $$\min \sum_{i=1}^K \sum_{x \in S_i} d(x, m_i)$$
• Much more robust to outliers and noise than K-Means.

---

Principal Component Analysis (PCA)

Linear unsupervised dimensionality reduction: find orthogonal projection directions that maximize preserved variance (equivalently, minimize reconstruction error).

Mathematical Derivation (Maximum Variance)

Let dataset $X \in \mathbb{R}^{N \times d}$ be zero-centered: $\sum_{i=1}^N x^{(i)} = 0$.

Sample covariance matrix:

$$\Sigma = \frac1N X^T X \in \mathbb{R}^{d \times d}$$

Project data onto unit direction vector $u$ ($u^T u = 1$):

$$\text{Var}(Xu) = \frac1N (Xu)^T (Xu) = u^T \left(\frac1N X^T X\right) u = u^T \Sigma u$$

Maximize variance under constraint $u^T u = 1$:

$$L(u, \lambda) = u^T \Sigma u - \lambda(u^T u - 1)$$

Take derivative with respect to $u$:

$$\frac{\partial L}{\partial u} = 2\Sigma u - 2\lambda u = 0 \implies \boxed{\Sigma u = \lambda u}$$

• The optimal projection direction $u$ is an eigenvector of covariance matrix $\Sigma$.
• The variance along $u$ is the corresponding eigenvalue $\lambda$.

Algorithm Steps

1. Center the data: $\tilde{X} = X - \bar{X}$.
2. Compute covariance matrix: $\Sigma = \frac{1}{N} \tilde{X}^T \tilde{X}$.
3. Eigenvalue decomposition: solve $\Sigma v_i = \lambda_i v_i$.
4. Sort eigenvalues descending: $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d$, select top $k$ eigenvectors:
   $$W = [v_1, v_2, \dots, v_k] \in \mathbb{R}^{d \times k}$$
5. Project data:
   $$\boxed{Z = \tilde{X} W \in \mathbb{R}^{N \times k}}$$

Explained Variance Ratio

Proportion of total variance preserved by top $k$ principal components:

$$\text{Ratio}_k = \frac{\sum_{i=1}^k \lambda_i}{\sum_{i=1}^d \lambda_i}$$

Connection to SVD

For zero-centered $\tilde{X}$, compute Singular Value Decomposition: $\tilde{X} = U S V^T$.

$$\Sigma = \frac1N \tilde{X}^T \tilde{X} = \frac1N (V S U^T)(U S V^T) = \frac1N V S^2 V^T$$

• The right singular vectors $V$ are the principal direction eigenvectors of $\Sigma$.
• Singular values relate to eigenvalues by: $\lambda_i = \frac{s_i^2}{N}$.
• Direct SVD on $\tilde{X}$ avoids calculating $X^T X$, offering better numerical stability and speed.

import numpy as np

def pca(X: np.ndarray, k: int) -> tuple[np.ndarray, np.ndarray]:
    # 1. Zero-center
    X_centered = X - np.mean(X, axis=0)
    # 2. SVD: X = U S V^T
    U, S, Vt = np.linalg.svd(X_centered, full_matrices=False)
    # 3. Top-k components (V^T rows)
    components = Vt[:k]
    # 4. Project
    Z = np.dot(X_centered, components.T)
    return Z, components