Skip to content
elevatedevco

Cheat sheet · Machine Learning

k-NN & k-Means cheat sheet

The key ideas on one page — plus common pitfalls and interview tips. Skim it before an interview, or print it for revision.

Cheat sheet

k-NN is a supervised, instance-based (lazy) algorithm for classification/regression; k-Means is an unsupervised partitioning clustering algorithm. They share the letter 'k' and a reliance on distance metrics but solve fundamentally different problems and are frequently confused in interviews.

Core Distinction (the #1 trap)

  • k-NN = SUPERVISED, lazy/instance-based learner: predicts a label/value from the k closest LABELED training points. Here 'k' = number of neighbors.
  • k-Means = UNSUPERVISED clustering: partitions UNLABELED data into k groups by iteratively assigning points to the nearest centroid. Here 'k' = number of clusters.
  • k-NN has no real 'training' phase (it just stores the data); k-Means has an iterative fitting phase that learns centroids.
  • k-NN inference is expensive (neighbor search at query time); k-Means inference is cheap once centroids exist (assign to nearest centroid).
  • Both are distance-based, so both are sensitive to feature scaling and to the curse of dimensionality.

k-NN Mechanics

  • Algorithm: compute distance from the query to all training points, take the k nearest, then majority vote (classification) or (weighted) mean (regression).
  • Distance choice matters: Euclidean (L2) is the default; Manhattan (L1) for high-dim/grid data; cosine for text/embeddings; Minkowski generalizes both via parameter p.
  • Distance weighting (weights='distance') gives closer neighbors more influence (weight = 1/d), reducing ties and tail effects vs. uniform voting. sklearn handles exact matches (d=0) so the 1/d weight does not divide by zero.
  • Choosing k: small k => low bias, high variance (noisy, overfits); large k => high bias, smoother boundary. Tune via cross-validation; use odd k for binary classification to avoid vote ties.
  • Scaling is mandatory: standardize/normalize features so large-range features don't dominate the metric.
  • Speedups: KD-Tree / Ball-Tree for low-to-moderate dimensions; brute force or approximate NN (HNSW, FAISS, ScaNN, Annoy) for high-dim embeddings.

k-NN Complexity & Trade-offs

  • Training: negligible compute ('lazy'), but O(n*d) memory to store the full dataset; building a KD/Ball-Tree index costs ~O(n*d*log n).
  • Inference (brute force): O(n*d) per query; tree structures help only in low dimensions and degrade toward brute force as d grows.
  • Pros: simple, non-parametric, no training step, naturally multi-class, adapts to complex (non-linear) decision boundaries.
  • Cons: slow and memory-heavy at scale, suffers from the curse of dimensionality, sensitive to irrelevant features and class imbalance.
  • Mitigations: dimensionality reduction (PCA), feature selection, ANN indexes for large corpora, and per-class/distance weighting for imbalance.

k-Means Mechanics (Lloyd's Algorithm)

  • Objective: minimize the within-cluster sum of squares (inertia) = sum over points of ||x - mu_c||^2 to the assigned centroid c.
  • Iterate two steps until convergence: (1) Assignment - assign each point to its nearest centroid; (2) Update - recompute each centroid as the mean of its members.
  • Initialization matters: random init can give poor local optima; k-means++ spreads initial centroids and is the sklearn default. Run multiple inits (n_init) and keep the lowest inertia.
  • Converges to a LOCAL optimum, not the global one; the result depends on init and k. Convergence is guaranteed since inertia is non-increasing each step.
  • Assumes roughly spherical, similarly sized, equal-density clusters because it uses Euclidean distance to a mean - it fails on elongated or varied-density shapes.
  • Empty clusters can occur; sklearn reseeds them automatically. Variants: MiniBatchKMeans (big data), k-medoids/PAM (robust to outliers, uses actual points), k-modes (categorical), GMM (soft/elliptical clusters).

Choosing k & Evaluating Clusters

  • Elbow method: plot inertia vs. k and pick the 'elbow' where marginal gain drops - heuristic and often ambiguous.
  • Silhouette score: ranges [-1, 1]; measures cohesion vs. separation; higher = better-defined clusters. Often more reliable than the elbow.
  • Other metrics: Davies-Bouldin (lower is better), Calinski-Harabasz (higher is better); use Adjusted Rand Index / NMI when ground-truth labels exist.
  • Inertia always decreases as k increases (k=n gives 0), so never pick k by minimizing inertia alone.
  • Scale features first; consider whitening/PCA. For non-globular structure prefer DBSCAN, HDBSCAN, or spectral/agglomerative clustering.

Complexity & When to Use Each

  • k-Means time: O(n*k*d*i) per run (i = iterations); near-linear in n, making it scalable vs. hierarchical clustering (O(n^2) or worse).
  • Use k-NN when: small/medium labeled dataset, low dimensionality (or good embeddings + ANN), and you want a simple non-parametric baseline; it also powers retrieval/recommenders via vector search.
  • Use k-Means when: you need fast, scalable unsupervised segmentation (customer segmentation, vector quantization, image color compression, feature bucketing).
  • Both need feature scaling and degrade in high dimensions; both require choosing k thoughtfully.
  • Modern context (2026): k-NN underpins vector databases / semantic search via approximate NN (FAISS, HNSW, ScaNN); k-Means drives embedding quantization and centroid init for product quantization in RAG pipelines.
Read the full lesson