M2-054M2: Classical Machine LearningClustering AlgorithmsMedium
⚡Flashcard Drill➔Mastery:

Compare K-Means, Gaussian Mixture Models (GMM), and DBSCAN Across Assumptions, Geometry, and Complexity

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-055 →
📐 Mathematical Definition
GMM: p(x)=∑kπkN(x∣μk,Σk)\text{GMM}:\ p(x)=\sum_k\pi_k\mathcal N(x\mid\mu_k,\Sigma_k)
⚡ One-Sentence Core Answer
K-Means enforces hard spherical partitions; GMM provides probabilistic soft clustering with ellipsoidal covariance; DBSCAN discovers arbitrarily shaped density clusters without pre-specifying KK and naturally isolates noise.

📌 Key Takeaways

  • •
    K-Means: Hard assignment; spherical clusters; requires pre-specifying KK; sensitive to outliers; O(NKd)O(N K d) time.
  • •
    GMM: Soft assignment (posterior probability γik∈[0,1]\gamma_{ik} \in [0, 1]); arbitrary ellipsoidal covariance matrices Σk\Sigma_k; requires pre-specifying KK; fits via EM algorithm.
  • •
    DBSCAN: Density-based (core points, border points, noise); arbitrarily shaped clusters; does NOT require specifying KK; robust to noise; requires (ϵ,MinPts)(\epsilon, \text{MinPts}).

📐 Mathematical Derivations

Structural comparison of boundary definitions: (1) K-Means boundary: Voronoi diagram of hyperplanes equidistant between centroids ∥x−μi∥=∥x−μj∥\|x - \mu_i\| = \|x - \mu_j\|. (2) GMM boundary: Quadratic decision boundaries determined by log-odds: log⁡P(z=1∣x)P(z=2∣x)=0  ⟺  (x−μ1)TΣ1−1(x−μ1)−(x−μ2)TΣ2−1(x−μ2)+const=0\log\frac{P(z=1\mid x)}{P(z=2\mid x)} = 0 \iff (x-\mu_1)^T \Sigma_1^{-1}(x-\mu_1) - (x-\mu_2)^T \Sigma_2^{-1}(x-\mu_2) + \text{const} = 0. (3) DBSCAN density connectivity: A point pp is a Core Point if ∣Nϵ(p)∣≥MinPts|N_\epsilon(p)| \ge \text{MinPts}. Point qq is directly density-reachable from pp if q∈Nϵ(p)q \in N_\epsilon(p) and pp is a core point. A cluster is a maximal set of density-connected points; any point not density-reachable from any core point is labeled Noise (−1-1).

🏭 Production Trade-offs

When to choose which: (1) K-Means: Massive datasets where fast computation and hard segmentation are required (e.g. Image color quantization, vector quantization). (2) GMM: Overlapping clusters where uncertainty quantification matters (e.g. Financial regime modeling, speaker identification). (3) DBSCAN: Spatial geo-data, GPS trajectory analysis, and anomaly detection where clusters have arbitrary non-linear shapes (crescents, rings) and noise must be filtered.
⚠️ Common Interview Pitfalls
  • ✕
    Using DBSCAN on datasets with wildly varying cluster densities (a single global ϵ\epsilon cannot capture both dense and sparse clusters; HDBSCAN must be used).
  • ✕
    Using K-Means on concentric ring or crescent-shaped data (K-Means will cut rings in half linearly).
🎯 Interviewer Follow-up Inquiries
  • ?
    How does HDBSCAN extend DBSCAN to multi-scale hierarchical densities without tuning epsilon?
  • ?
    Why does full-covariance GMM require estimating K⋅d(d+1)2K \cdot \frac{d(d+1)}{2} parameters, and how do tied or diagonal covariance constraints mitigate overfitting?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-053: Detail Methodologies for Selecting the Optimal Number of Clusters K in Unsupervised Learning📋 Back to BankNext →M2-055: Derive the Expectation-Maximization (EM) Algorithm and Prove Its Monotonic Likelihood Ascent via Jensen's Inequality