Unsupervised Learning: K-Means, Hierarchical Clustering & PCA

Explanation

Clustering algorithms group data points such that intra-cluster distance is minimized while inter-cluster distance is maximized. K-Means minimizes inertia (Within-Cluster Sum of Squares - WCSS), but is sensitive to initial random centroid placement (remedied by K-Means++). Principal Component Analysis addresses the 'Curse of Dimensionality' by computing the singular value decomposition (SVD) or eigendecomposition of the data covariance matrix Sigma = (1/m) X^T X. The top k eigenvectors corresponding to the largest eigenvalues capture the maximum variance while compressing feature dimensions.

Key points

• K-Means Clustering: Iterative centroid-based algorithm alternating between assignment of points to nearest centroid and recalculation of centroid positions.
• Elbow Method & Silhouette Coefficient used to determine the optimal number of clusters K.
• Hierarchical Clustering: Agglomerative (bottom-up merging) and Divisive (top-down splitting); visualized using Dendrograms.
• Principal Component Analysis (PCA): Linear dimensionality reduction technique that projects data along orthogonal axes of maximum variance (eigenvectors of covariance matrix).

Example

Code examples

from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
import numpy as np

# PCA Dimensionality Reduction
X = np.random.randn(100, 10) # 100 samples, 10 features
pca = PCA(n_components=2)
X_reduced = pca.fit_transform(X)
print("Explained variance ratio:", pca.explained_variance_ratio_)

# K-Means Clustering on reduced space
kmeans = KMeans(n_clusters=3, init='k-means++', random_state=42)
labels = kmeans.fit_predict(X_reduced)

Exam questions

• [8 Marks] Explain the step-by-step algorithm for K-Means clustering. How is the Elbow Method used to identify optimal K?
• [8 Marks] Derive the mathematical concept behind Principal Component Analysis (PCA) and explain how eigenvectors capture maximum variance.