Classical Machine Learning: KNN, PCA, And K-Means

What's being tested

These questions test practical mastery of K-Nearest Neighbors, Principal Component Analysis, and K-Means: algorithmic behavior, preprocessing effects, numerical/implementation robustness, and hyperparameter selection. Interviewers want a Data Scientist who can choose the right tradeoffs (accuracy vs. scalability), diagnose failure modes (high-dimensional data, empty clusters), and implement/validate clustering and instance-based models reliably.

Patterns & templates

• Brute-force KNN: compute pairwise distances O(n·d) per query, then sort/select k; acceptable for n up to ~100k with optimized BLAS, else use indices.

• Indexed KNN: use `KDTree`/`BallTree` for low-dimensional data (average query ≈ O(log n)); deteriorates under the curse of dimensionality.

• Distance choices: pick Euclidean for continuous features, cosine for sparse/high-d vectors, and consider distance-weighting (1/d) for soft voting.

• PCA workflow: center data, compute SVD or eigendecomposition (`sklearn.decomposition.PCA`); complexity ≈ O(min(n·d^2, d·n^2)); use randomized SVD for large matrices.

• K-Means basics: Lloyd’s algorithm with `k-means++` init (`sklearn.cluster.KMeans`), complexity O(n·k·i·d); stop on max-iter or small inertia change.

• Empty-cluster handling: re-seed from farthest point, split largest cluster, or reduce k; document chosen strategy.

• Model selection: tune k via cross-validation for KNN, elbow/silhouette/BIC for K-Means, and explained variance ratio for PCA components.

• Scaling & preprocessing: always scale features for Euclidean-based methods; impute or drop NaNs; consider PCA before KNN in very high-d sparse data.

Common pitfalls

Pitfall: Treating `KDTree` as a cure-all—trees often perform worse than brute force in >20 dimensional data.

Pitfall: Forgetting to center data before PCA, which shifts principal components and invalidates explained variance.

Pitfall: Ignoring empty clusters in K-Means implementations; silent failures produce biased centroids and wrong cluster counts.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.