DBSCAN and Gaussian mixture models
Study notes comparing DBSCAN (a density-based clustering algorithm) and Gaussian Mixture Models (GMMs) with the EM algorithm, covering definitions, derivations, formulas, examples, common mistakes and exam guidance.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
DBSCAN and Gaussian mixture models (GMMs) are two widely used clustering methods engineers apply when they need to group unlabeled data: DBSCAN is useful when clusters have arbitrary shape and there is noise, while GMMs are useful when clusters are approximately Gaussian and we want soft probabilistic assignments (e.g., speaker clustering, image segmentation, sensor data grouping).
Key ideas
Start from simple terms.
- Cluster: a group of data points that are similar under some measure (usually distance). Unit: none (unitless) or same as data units.
DBSCAN family
- DBSCAN stands for Density-Based Spatial Clustering of Applications with Noise. It groups points by region of high point density and marks isolated points as noise.
- ε‑neighbourhood (epsilon-neighbourhood) of a point x: the set of points within distance ε of x. Notation: Nε(x) = {y : dist(x,y) ≤ ε}.
- minPts: an integer threshold; the minimum number of points required to form a dense region (count includes the point itself).
- Core point: a point x is a core point if |Nε(x)| ≥ minPts.
- Border point: a point y is a border point if |Nε(y)| < minPts but y is in the ε‑neighbourhood of some core point.
- Noise point (outlier): neither core nor border.
- Directly density-reachable: y is directly density-reachable from x if y ∈ Nε(x) and x is a core point.
- Density-reachable: y is density-reachable from x if there exists a chain x = p0, p1, ..., pn = y where each pi+1 is directly density-reachable from pi.
- Density-connected: x and y are density-connected if there exists z such that x and y are both density-reachable from z.
- A DBSCAN cluster is a maximal set of density-connected points.
Algorithm sketch (step-by-step exam style):
- For each unvisited point p, mark visited and find Nε(p).
- If p is a core point (|Nε(p)| ≥ minPts) start a new cluster and expand by adding all points density-reachable from p (use BFS/stack); mark points visited as you add them.
- If p is not a core point, mark it as noise temporarily (it might later become border if added to a cluster).
- Continue until all points visited.
Notes on parameters and complexity:
- Choosing ε: use a k-distance plot (k = minPts, i.e., distance to the minPts-th nearest neighbour, excluding the point itself). For each point compute distance to its k-th nearest neighbour, plot sorted distances; look for a knee (sharp bend) — that value is a candidate ε. Draw the plot: x-axis index of sorted points, y-axis k-distance; label knee. Rule-of-thumb for minPts: set minPts ≥ d+1 (e.g., 4 in 2D) or use 2·d as a heuristic, where d is the data dimension.
- Complexity: naive O(n^2); with spatial index (KD-tree or ball-tree) average O(n log n) for low-medium dimensions, but worst-case O(n^2).
Gaussian mixture models (GMM) family
- Gaussian mixture model (GMM): probability model that represents a distribution as a weighted sum of K Gaussian components: p(x) = sum_{k=1..K} π_k N(x | μ_k, Σ_k).
- Mixture weight π_k: non-negative, sum to 1; π_k is prior probability of component k.
- Component Gaussian N(x | μ, Σ): multivariate normal distribution with mean μ and covariance Σ.
- Expectation-Maximization (EM): iterative algorithm to find maximum-likelihood estimates of parameters for models with latent (hidden) variables. For GMM the latent variable z_n ∈ {1..K} indicates which Gaussian generated x_n.
EM derivation for GMM (standard exam derivation):
- Write complete-data log-likelihood for observed x_n and hidden z_n (as one-hot): L_complete = sum_n sum_k I[z_n=k] (log π_k + log N(x_n | μ_k, Σ_k)).
- E-step: compute responsibilities (posterior probabilities) γ_{nk} = P(z_n=k | x_n, θ_old) = π_k N(x_n|μ_k,Σ_k) / sum_j π_j N(x_n|μ_j,Σ_j).
- M-step: maximize expected complete-data log-likelihood w.r.t parameters using γ_{nk} as weights: Nk = sum_n γ_{nk}. μ_k_new = (1/Nk) sum_n γ_{nk} x_n. Σ_k_new = (1/Nk) sum_n γ_{nk} (x_n − μ_k_new)(x_n − μ_k_new)^T. π_k_new = Nk / N.
- Repeat until log-likelihood converges or parameter change small. EM increases the observed-data log-likelihood monotonically but can converge to local optima; use multiple random restarts and a good initialization (e.g., K-means). Choose K using BIC/AIC or cross-validation when it is not known a priori.
- Assumptions: component Gaussians are valid (Σ_k positive definite), data are IID, K is known. Note: the GMM log-likelihood is unbounded above—EM can collapse a component onto a single point with Σ_k → 0—so add covariance regularization or Bayesian priors to avoid degeneracy in practice.
Relationship and choice:
- Use DBSCAN when clusters have arbitrary shape, noise is expected, and you want a non-parametric method. Limitation: DBSCAN struggles when cluster densities differ significantly; consider HDBSCAN or OPTICS in that case.
- Use GMM when clusters are ellipsoidal (Gaussian-like), you need soft assignments or probabilistic modeling, or you want component-wise covariance estimates.
Formulas
N(x | μ, Σ) = (2π)^{-d/2} |Σ|^{-1/2} exp(−1/2 (x−μ)^T Σ^{-1} (x−μ)) — multivariate Gaussian pdf; x in R^d (units same as data), μ mean (same units), Σ covariance (units^2).
p(x) = sum_{k=1..K} π_k N(x | μ_k, Σ_k) — GMM density; π_k unitless, sum π_k = 1.
γ_{nk} = π_k N(x_n|μ_k,Σ_k) / sum_{j=1..K} π_j N(x_n|μ_j,Σ_j) — responsibility of component k for point n; unitless, 0≤γ≤1.
Nk = sum_{n=1..N} γ_{nk} — effective membership count for component k; unitless.
μ_k = (1 / Nk) sum_{n=1..N} γ_{nk} x_n — new mean; same units as x.
Σ_k = (1 / Nk) sum_{n=1..N} γ_{nk} (x_n − μ_k)(x_n − μ_k)^T — covariance matrix; units are (data units)^2.
π_k = Nk / N — new mixing weight; unitless.
log L = sum_{n=1..N} log ( sum_{k=1..K} π_k N(x_n | μ_k, Σ_k) ) — observed-data log-likelihood; unitless.
Nε(x) = { y : dist(x,y) ≤ ε } — ε-neighbourhood; ε has same units as data (e.g., meters).
|Nε(x)| ≥ minPts — core point condition; minPts unitless.
Worked examples
- DBSCAN — manual clustering (2D points, units: meters) Data: P1(0.0, 0.0), P2(0.5, 0.0), P3(0.0, 0.6), P4(5.0,5.0), P5(5.2,5.0), P6(4.9,5.1), P7(10.0,0.0), P8(10.5,0.2). Parameters: ε = 1.0 m, minPts = 3. Step 1: Compute ε-neighbourhood sizes (distance calculations shown briefly):
- Distances among P1,P2,P3 are ≤ 0.81 m so each of P1,P2,P3 has Nε size = 3 → all are core points.
- Distances among P4,P5,P6 are ≤ 0.32 m (max ≈ 0.316 m) so each has Nε size ≥ 3 → all core points.
- P7 and P8 are distance ≈ 0.54 m from each other, so each has Nε size = 2 (< minPts) → neither core nor border from own neighbourhood; they are not within ε of any core point, so they are noise. Step 2: Start DBSCAN: pick unvisited P1 → core → expand cluster C1 = {P1,P2,P3}. Step 3: Next unvisited P4 → core → expand cluster C2 = {P4,P5,P6}. Step 4: P7,P8 visited and marked noise. Result: Two clusters (C1 with P1–P3, C2 with P4–P6) and noise {P7,P8}. Final answers: Cluster 1: P1, P2, P3; Cluster 2: P4, P5, P6; Noise: P7, P8.
- GMM with EM — 1D numerical EM step (unitless data) Data: x = {1.0, 1.2, 0.8, 4.5, 4.8, 5.1}, N=6. Use K=2. Initial parameters: μ1=1.0, μ2=5.0, σ1^2=σ2^2=0.25 (σ=0.5), π1=π2=0.5. Gaussian pdf for σ=0.5: N(x|μ,σ^2)=0.79788456 * exp(−2*(x−μ)^2). E-step: compute responsibilities γ_{n1}, γ_{n2}.
- For x=1.0: N1=0.7979, N2≈0 (exp(−32) negligible) → γ_{1,1}≈1, γ_{1,2}≈0.
- For x=1.2: (x−μ1)=0.2 → N1=0.7979exp(−20.04)=0.7979exp(−0.08)=0.79790.9231≈0.7366. For μ2=5.0 the exponent is −2*(−3.8)^2≈−28.88 → N2≈0 → γ≈1 for component 1.
- For x=0.8: symmetric to 1.2 → γ≈1 for component 1.
- For x=4.5,4.8,5.1: similarly γ≈1 for component 2. Thus Nk ≈ 3 for each component. M-step: update parameters.
- μ1 = (1/3)*(1.0 + 1.2 + 0.8) = 1.0 (unitless). μ1 = 1.0.
- μ2 = (1/3)*(4.5 + 4.8 + 5.1) = 4.8. μ2 = 4.8.
- σ1^2 = (1/3)*( (0)^2 + (0.2)^2 + (−0.2)^2 ) = 0.08/3 = 0.0266667. σ1 ≈ 0.1633.
- σ2^2 = (1/3)*( (−0.3)^2 + 0^2 + 0.3^2 ) = 0.18/3 = 0.06. σ2 ≈ 0.2449.
- π1 = π2 = 3/6 = 0.5. Interpretation: EM after one iteration separates the two obvious groups and estimates tighter variances for the compact groups.
Common mistakes
- In EM, forgetting to normalize responsibilities (sum across k should equal 1 for each n).
- Using sample variance formula with N−1 in the M-step: EM uses Nk in denominator (maximum likelihood), not Nk−1 (that would be unbiased estimator for observed data).
- For GMM derivation, forgetting the log-sum-exp stability when computing log-likelihood in code or exam notes.
- Assuming DBSCAN will work well in high dimensions without noting the curse of dimensionality (density notion breaks down).
For your exam
Kinds of questions:
- Definitions: define core/border/noise point; give DBSCAN algorithm steps.
- Short notes: compare DBSCAN vs GMM, mention assumptions and use-cases.
- Derivations: derive EM updates for μ_k, Σ_k and π_k starting from complete-data log-likelihood; show responsibilities.
- Numericals: run DBSCAN on small 2D set by hand; run one EM iteration on a toy 1D dataset (show responsibilities and updated parameters).
- Diagrams: draw k-distance plot (sorted k-distance on y, point index on x) and label knee; draw clusters and noise points for DBSCAN example. What a full-marks answer includes:
- Clear definitions with notation and units.
- For EM derivation: show complete-data log-likelihood, E-step formula for γ_{nk}, then M-step weighted sums and final update equations.
- For DBSCAN: precise algorithm steps, a correct explanation of density-reachability and an example showing cluster expansion.
Quick check
- Define a core point in DBSCAN and state the core condition.
- Write the formula for the responsibility γ_{nk} in a GMM.
- In EM for GMM, give the update formula for μ_k. Answers: 1) A core point has |Nε(x)| ≥ minPts (count includes the point itself). 2) γ_{nk} = π_k N(x_n|μ_k,Σ_k) / sum_j π_j N(x_n|μ_j,Σ_j). 3) μ_k = (1/Nk) sum_n γ_{nk} x_n.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?