K-Means Clustering & PCA for GATE DA: Worked Iterations and Variance Explained
The unsupervised half of the ML syllabus, done by hand — every assign/update step of a k-means run traced to convergence, and a complete PCA with eigenvalues, components and variance-explained ratios.
By Piyush Wairale · GATE DA Educator & Course Instructor, IIT Madras BS Programme · Updated August 2026
Key Takeaways
• K-means minimises within-cluster sum of squares (WCSS) by alternating two steps: assign each point to its nearest centroid, then update each centroid to its cluster’s mean. It always converges — but only to a local optimum.
• The elbow method picks k where the WCSS-vs-k curve stops dropping steeply; k-means++ fixes bad initialisations.
• PCA finds orthogonal directions of maximum variance: eigenvectors of the covariance matrix, sorted by eigenvalue. Variance explained by PCᵢ = λᵢ/Σλ.
• PCA is SVD applied to centered data — same directions, and GATE asks the variance-explained NAT almost every year.
On this page
The k-means objective · Worked iteration (to convergence) · Properties & elbow method · Hierarchical clustering · PCA (worked) · PCA ↔ SVD & scree plots · Comparison table · Solved problems · Mistakes · Exam patterns · FAQs
The K-Means Objective: What Is Actually Being Minimised
Given n points and a chosen k, k-means seeks cluster assignments and centroids μ₁…μₖ minimising the within-cluster sum of squares:
Both alternating steps can only lower (or keep) this objective — assignment picks the nearest centroid by definition, and the mean is the point minimising summed squared distance to a set. Since there are finitely many partitions, the algorithm must converge. Clustering and dimensionality reduction are both named in the official GATE DA syllabus; the ML pillar guide places them in the full roadmap.
▶ Watch: my complete Machine Learning playlist for GATE DA
Clustering and PCA numericals solved on camera — all playlists →
A Full K-Means Run, Worked to Convergence
Data (1D for clean arithmetic): 2, 3, 4, 10, 11, 12, with k = 2 and initial centroids μ₁ = 3, μ₂ = 4.
Iteration 1
Assign: 2 → C₁ (|2−3| = 1 < |2−4| = 2); 3 → C₁ (0 < 1); 4 → C₂ (0); 10, 11, 12 → C₂ (all nearer 4 than 3). Clusters: C₁ = {2, 3}, C₂ = {4, 10, 11, 12}.
Update: μ₁ = (2+3)/2 = 2.5; μ₂ = (4+10+11+12)/4 = 9.25.
Iteration 2
Assign: 2, 3 stay in C₁. Point 4: |4−2.5| = 1.5 < |4−9.25| = 5.25 → 4 switches to C₁. 10, 11, 12 stay in C₂. Clusters: C₁ = {2, 3, 4}, C₂ = {10, 11, 12}.
Update: μ₁ = (2+3+4)/3 = 3; μ₂ = (10+11+12)/3 = 11.
Iteration 3 — convergence check
Assign: every point keeps its cluster (all of 2, 3, 4 are nearer 3; all of 10, 11, 12 nearer 11). No assignment changed → converged. Final WCSS = (1+0+1) + (1+0+1) = 4. GATE questions stop at exactly this level: run one or two iterations, report a centroid or the final WCSS.
Properties, Initialisation and the Elbow Method
Facts GATE tests directly: k-means always converges in finitely many steps, but to a local optimum — different initial centroids can give different final clusterings (run it multiple times and keep the lowest WCSS). It assumes roughly spherical, similar-sized clusters, uses Euclidean distance, and is sensitive to outliers (a single far point drags its centroid). k-means++ initialises centroids far apart probabilistically, dramatically improving typical results.
Choosing k — the elbow method: WCSS always decreases as k grows (more centroids can only help), so you can’t just minimise it. Plot WCSS against k and pick the “elbow” where the steep drop flattens:
Hierarchical Clustering in Brief
Agglomerative hierarchical clustering needs no k upfront: start with every point as its own cluster and repeatedly merge the two closest clusters, producing a dendrogram you can cut at any height. “Closest” depends on the linkage: single linkage = minimum pairwise distance between clusters (prone to chaining), complete linkage = maximum pairwise distance (compact clusters), average linkage = mean of all pairs. GATE numericals give a small distance matrix and ask which pair merges first, or the single/complete-linkage distance between two named clusters — pure table lookup plus min/max.
PCA: Directions of Maximum Variance, Worked
The recipe: (1) center the data (subtract each feature’s mean); (2) form the covariance matrix S; (3) find its eigenvalues and eigenvectors; (4) sort by eigenvalue — the top eigenvector is PC1, the direction along which the data varies most; (5) project onto the top components to reduce dimension.
Worked 2D example
Suppose the centered data has covariance matrix S = [ [5, 2], [2, 2] ].
Eigenvalues: det(S − λI) = (5−λ)(2−λ) − 4 = λ² − 7λ + 6 = 0 ⇒ λ₁ = 6, λ₂ = 1.
PC1 direction: solve (S − 6I)v = 0: (−1)v₁ + 2v₂ = 0 ⇒ v₁ = 2v₂ ⇒ v = (2, 1)/√5. PC2 is the orthogonal (−1, 2)/√5.
Variance explained: PC1 accounts for λ₁/(λ₁+λ₂) = 6/7 ≈ 85.7%; keeping only PC1 halves the dimension while retaining ~86% of the variance. Note the sanity check GATE loves: trace(S) = 5 + 2 = 7 = λ₁ + λ₂ — total variance is preserved by the rotation.
PCA ↔ SVD, and Choosing the Number of Components
Run SVD on the centered data matrix X and the right singular vectors V are exactly the principal components, with λᵢ = σᵢ²/(n−1). That’s why numerical libraries implement PCA via SVD — no covariance matrix ever formed. To choose how many components to keep: plot eigenvalues in decreasing order (a scree plot, same elbow logic as WCSS-vs-k) or keep the smallest m with cumulative variance Σ₁…ₘλᵢ/Σλ above a threshold like 90–95%. Two practical rules that appear as MCQs: standardise features first (else the largest-scale feature hijacks PC1), and components are orthogonal by construction. Eigen-machinery rusty? The Linear Algebra pillar rebuilds it from scratch.
K-Means vs Hierarchical vs PCA at a Glance
| Aspect | K-means | Hierarchical | PCA |
|---|---|---|---|
| Task | Partition into k clusters | Nested cluster tree | Dimensionality reduction |
| Needs k upfront? | Yes (elbow helps) | No — cut dendrogram later | Choose m by variance kept |
| Core computation | Assign/update to local optimum | Merge closest by linkage | Eigendecomposition of covariance |
| Deterministic? | No — depends on init | Yes, given linkage | Yes (up to sign) |
Three GATE-Style Problems, Solved
Problem 1 (MCQ). Centroids are μ₁ = (2, 3) and μ₂ = (6, 1). Where does point (4, 4) go?
Solution. Squared distances (no square roots needed for comparison): to μ₁: (4−2)² + (4−3)² = 5; to μ₂: (4−6)² + (4−1)² = 13. 5 < 13 → cluster 1. Always compare squared distances — same answer, half the work.
Problem 2 (NAT). A 4-feature dataset has covariance eigenvalues 8, 4, 2, 2. How much variance do the first two PCs explain, and what’s the minimum number of components for ≥ 85%?
Solution. Total = 16. First two: (8+4)/16 = 75%. Cumulative: 1 PC → 50%, 2 PCs → 75%, 3 PCs → 14/16 = 87.5% ≥ 85% → 3 components.
Problem 3 (NAT). Clusters A = {1, 4} and B = {7, 9} on a line. Single-linkage and complete-linkage distances?
Solution. Pairwise distances: |1−7| = 6, |1−9| = 8, |4−7| = 3, |4−9| = 5. Single linkage = min = 3; complete linkage = max = 8.
Common Mistakes to Avoid
Claiming k-means finds the global optimum. It converges, but to a local optimum that depends on initialisation — the classic true/false trap.
Updating centroids before finishing assignments. One full assign pass, then one full update pass. Interleaving gives wrong intermediate centroids in traced questions.
Forgetting to center (and usually standardise) before PCA. Uncentered PCA points PC1 at the data’s mean, not its spread.
Reporting variance explained from eigenvalues in the wrong order. Sort descending first; λ₁ is the largest.
Mixing linkage definitions. Single = closest pair, complete = farthest pair. Half of all dendrogram errors are this swap.
How GATE DA Asks Clustering and PCA
The recurring shapes: (1) NAT — one or two k-means iterations on ≤ 8 points, report a centroid coordinate or WCSS; (2) NAT — variance-explained percentages from given eigenvalues (nearly every year); (3) NAT/MCQ — linkage distances from a small distance matrix; (4) MCQ — properties: convergence, initialisation sensitivity, orthogonality of PCs, PCA-SVD relationship. All arithmetic is small integers — the marks are for procedure discipline.
Master the full ML syllabus for GATE DA 2027
My complete Machine Learning course covers clustering, PCA, regression, SVM, trees, naive Bayes and neural networks with recorded lectures, notes and GATE-level practice — aligned exactly to the DA syllabus.
Explore the Machine Learning Course →FAQs: K-Means & PCA for GATE DA
Does k-means always converge?
Yes — each step can only decrease (or preserve) WCSS and there are finitely many partitions, so it terminates. But the endpoint is a local optimum, not necessarily the best clustering.
Is PCA supervised or unsupervised?
Unsupervised — it never looks at labels, only at the feature covariance. That’s also why maximum-variance directions aren’t guaranteed to be the most discriminative ones for a later classifier.
How is PCA related to SVD exactly?
PCA’s components are the right singular vectors of the centered data matrix, and each eigenvalue is σᵢ²/(n−1). The SVD deep dive works this machinery on numbers.
Can I use k-means for non-spherical clusters?
Poorly — WCSS with Euclidean distance favours round, similar-sized clusters. Elongated or nested shapes suit hierarchical (single linkage) or density-based methods better; GATE tests this as a “which method fails here?” MCQ.
What should I study next?
Neural networks — the last big block of the ML section. The ML pillar guide has the recommended order.
Keep building: revise the complete ML roadmap, work the eigen-machinery in the Linear Algebra pillar and the SVD & LU deep dive, and track your coverage against the GATE DA 2027 syllabus. New ML problem-solving sessions drop regularly on my YouTube channel — subscribe so you don’t miss them.
Recent Post
Complete GATE RA 2027 guide to forward kinematics of manipulators: rotation matrices, homogeneous transformations, the DH convention, planar 2R and articulated RRR arms, the Jacobian, and five worked GATE-style problems with diagrams.
GATE 2027 registration is postponed: the portal now opens 27 August and closes 27 September 2026 (late fee till 5 October). New dates, reasons and what DA aspirants should do.
GATE DA 2027 registration opens Aug 27 at gate2027.iitm.ac.in. Step-by-step application guide: dates, fees, DigiLocker facial recognition, documents and mistakes to avoid.
A* search and alpha-beta pruning for GATE DA 2027: full open/closed-list trace, admissible heuristics, minimax with pruning counted leaf by leaf, solved problems.
Taylor series and maxima-minima for GATE DA 2027: standard expansions, e^0.1 and cos(0.2) approximated, derivative tests and the Hessian rule worked with solved problems.
Normal forms for GATE DA 2027: functional dependencies, attribute closure worked, 1NF to BCNF with full decompositions, checklist table and solved GATE problems.
Learn Daily, Wherever You Are
Free lectures, exam updates, PYQ discussions, and job alerts — delivered through our YouTube channel and Telegram communities.
