Home → Machine Learning → Unit IV

Clustering & PCA

Grouping similar data and reducing dimensionality

K-Means

  • Partition data into K clusters by minimizing within-cluster variance
  • Initialize centroids → Assign points → Update centroids (iterate)
  • Use Elbow/Silhouette methods to choose K

Algorithm:

  1. Initialize centroids (random or k-means++).
  2. Assignment: assign each xᵢ to nearest centroid.
  3. Update: recompute centroid as mean of assigned points.
  4. Repeat 2–3 until centroids stabilize or max iters.

Complexity per iteration: O(n k d)

Hierarchical Clustering

Agglomerative (bottom-up) or Divisive (top-down); linkage criteria: single, complete, average, Ward's method.

Distance between clusters A,B:
 single:  min d(a,b)
 complete: max d(a,b)
 average: mean d(a,b)
 Ward: minimize increase in SSE

DBSCAN

Density-based clustering with parameters ε (radius) and minPts.

  • Classifies points as core (≥minPts in ε-neighborhood), border, or noise.
  • Can find arbitrary-shaped clusters; robust to outliers.
  • Sensitive to scale; use distance normalization or k-distance plots to choose ε.

Principal Component Analysis

Transforms data into orthogonal components capturing maximum variance.

  1. Standardize features (zero mean, unit variance).
  2. Compute covariance matrix Σ = (1/n) XᵀX.
  3. Eigen-decompose Σ; sort eigenvalues λ₁ ≥ λ₂ ≥ ...
  4. Select top-k eigenvectors to form projection matrix W.
  5. Project: Z = X W.

Explained Variance

Choose k such that Σ_{i=1..k} λᵢ / Σ λᵢ ≥ desired threshold (e.g., 95%).

SVD & Eigen Decomposition

SVD factorizes X = U Σ Vᵀ. For mean-centered data, PCA components are columns of V; singular values relate to sqrt of eigenvalues.

Quick Revision

  • PCA steps: standardize → covariance → eigenvectors → project.
  • K-Means: iterate assign/update; complexity O(n k d) per iteration.
  • DBSCAN: ε and minPts; identifies noise points.