Cluster Analysis (Advanced)

This chapter covers density-based, model-based, grid-based, spectral, and high-dimensional clustering, plus how to validate clusters.

1. Density-Based: DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds arbitrarily shaped clusters separated by low-density regions; also labels noise/outliers.

Definitions

$ϵ$ -neighborhood: $N_{ϵ} (p) = {q ∣ d i s t (p, q) \leq ϵ}$ .
Core point: $| N_{ϵ} (p) | \geq M i n P t s$ (density-reachable interior).
Border point: not core, but within $ϵ$ of a core point.
Noise point (outlier): neither core nor border.
Directly density-reachable: $q \in N_{ϵ} (p)$ and $p$ is core.
Density-reachable: chain of direct reachable via core points.
Density-connected: both reachable from a common core point.

Algorithm

label all points as unvisited;
for each p:
   if visited: continue;
   mark visited; N = Nε(p);
   if |N| < MinPts: mark p as NOISE (may later become border);
   else:
      start new cluster C; add p to C; seed set S = N;
      for each q in S:
         mark q visited; Nq = Nε(q);
         if |Nq| ≥ MinPts: add Nq to S;       // expand
         if q not yet in any cluster: add q to C;

Clusters grow by chaining core points; border points attach to one cluster.

Pros	Cons
arbitrary shape clusters	needs $ϵ$ , $M i n P t s$ tuning
finds noise automatically	struggles with varying densities
only 2 params, no k needed	distance-based ⇒ curse of dimensionality

2. OPTICS (Ordering Points To Identify Clustering Structure)

Generalizes DBSCAN for data with varying densities.
Produces an ordering of points with two values: core-distance and reachability-distance, visualized as a reachability plot (valleys = clusters).
core-distance(p) = distance to the $M i n P t s$ -th neighbor.
reachability-distance(p,q) = $max (c o r e - d i s t (p), d i s t (p, q))$ .
Lets users extract clusters at multiple $ϵ$ thresholds after one pass; no single global $ϵ$ .
Extensions: OPTICS-XI, HiSC (hierarchical subspace clustering).

3. Grid-Based: STING, CLIQUE

STING: partition space into rectangular grid cells; compute statistical info per cell; query answers computed bottom-up by cell densities (fast, $O (n)$ build, query $O (cells)$ ).
CLIQUE: automatic subspace clustering — finds dense grids in subspaces (handles high-dimensional data; combines density + grid).

4. Model-Based: Expectation-Maximization (EM)

Mixture of Gaussians

Assume data generated by a mixture of $k$ Gaussian components: $p (x) = \sum_{l = 1}^{k} π_{l} N (x ∣ μ_{l}, Σ_{l})$ with mixing weights $π_{l} \geq 0$ , $\sum π_{l} = 1$ .

EM Algorithm (two steps, iterated)

initialize π_l, μ_l, Σ_l;
repeat:
  E-step: compute responsibilities (soft assignment)
     γ(z_{il}) = P(component l | x_i) =
        π_l N(x_i|μ_l,Σ_l) / Σ_{j} π_j N(x_i|μ_j,Σ_j)
  M-step: re-estimate parameters by weighted MLE:
     μ_l = (Σ_i γ_{il} x_i) / (Σ_i γ_{il})
     Σ_l = (Σ_i γ_{il}(x_i-μ_l)(x_i-μ_l)^T) / (Σ_i γ_{il})
     π_l = (Σ_i γ_{il}) / n
until log-likelihood converges;

Properties

Soft assignment (probabilities) vs k-means hard assignment — k-means is a limiting case of EM for spherical equal covariances.
Converges to local optimum (log-likelihood non-decreasing).
✅ gives probabilities & component models; ❌ assumes Gaussian shape, needs $k$ , slow.

EM (soft)	k-means (hard)
probabilistic, soft membership	hard assignment
arbitrary covariance (ellipses)	spherical (equal var)
likelihood-based	SSE-based

Other model-based

COBWEB / CLASSIT: conceptual clustering of categorical data (incrementally builds a taxonomy).
SOM (Self-Organizing Map): neural net that produces a topology-preserving 2-D map.

5. Spectral Clustering

Uses the similarity graph of points: build affinity matrix $W$ (e.g., $W_{i j} = \exp (- ∥ x_{i} - x_{j} ∥^{2} / 2 σ^{2})$ ), degree matrix $D$ ( $D_{i i} = \sum_{j} W_{i j}$ ), Laplacian $L = D - W$ (or normalized $L_{s y m} = D^{- 1 / 2} L D^{- 1 / 2}$ ).
Compute the first $k$ eigenvectors of $L$ , form matrix $U$ ( $n \times k$ ), normalize rows, then run k-means on rows.
Excellent for non-convex / concentric clusters that k-means fails on.

build similarity graph W; D = diag(row sums); L = D - W;
eigendecompose L → k smallest eigenvectors (or normalized);
stack as rows → normalize each row; run k-means on these embeddings;

6. High-Dimensional & Subspace Clustering

In high-D, distances concentrate (curse of dimensionality) ⇒ clusters exist only in subspaces.
Subspace clustering: CLIQUE, PROCLUS (find relevant subspaces per cluster), FIRES.
Projected clustering: each cluster defined on a subset of dimensions.

7. Cluster Validation

External Indices (vs known labels)

Rand Index / Adjusted Rand Index (ARI): fraction of agreeing point pairs, corrected for chance (1 = perfect, 0 = random).
Mutual Information / NMI, Fowlkes-Mallows.

Internal Indices (no labels)

Sum of Squares: $S S B$ (between), $S S W$ (within); higher $S S B / S S W$ ⇒ better separation.
Silhouette coefficient (for point $i$ in cluster $C_{i}$ ): $a (i) = avg distance to others in same cluster$ $b (i) = min_{C \neq C_{i}} avg distance to points in C$ $s (i) = \frac{b (i) - a (i)}{max (a (i), b (i))} \in [- 1, 1]$ $s \approx 1$ well-clustered, $s \approx 0$ on boundary, $s < 0$ likely wrong cluster. Overall silhouette = mean $s (i)$ ; higher = better.
Davies-Bouldin, Calinski-Harabasz, Xie-Beni indices.

Relative Criteria

Compare clusterings from the same algorithm under different $k$ (e.g., silhouette vs $k$ , elbow of SSE).

Stability

Perturb data / subsample; measure consistency of clustering.

DBSCAN — Worked Example

Points in 1-D for clarity: ${1, 2, 3, 8, 9, 30}$ , $ϵ = 2$ , $M i n P t s = 3$ .

$1, 2, 3$ : each has ≥3 points within $ϵ = 2$ (e.g., around 2: {1,2,3}) ⇒ core points forming cluster $C_{1} = {1, 2, 3}$ .
$8, 9$ : within 2 of each other but not enough neighbors (only 2) ⇒ with $M i n P t s = 3$ they are border/noise unless connected to a core. Here they are isolated ⇒ noise.
$30$ : far from all ⇒ noise (outlier). DBSCAN thus finds one dense cluster and flags 8,9,30 as noise/outliers — something k-means (forced to make $k$ groups) cannot do. Lower $M i n P t s$ would let {8,9} form a second cluster.

EM — Worked Sketch (1-D, k=2)

Two Gaussians: red $N (2, 1)$ , blue $N (8, 1)$ . Initialize $μ_{r} = 3, μ_{b} = 7, π = 0.5$ each.

E-step: for each point compute $γ_{r e d}, γ_{b l u e}$ (responsibilities) from current params. A point at 2 gets $γ_{r e d} \approx 0.88, γ_{b l u e} \approx 0.12$ .
M-step: new $μ_{r}$ = responsibility-weighted mean of all points (shifts toward 2), $μ_{b}$ toward 8; update variances & $π$ .
Iterate; log-likelihood rises each step; converges to recovered components. Unlike k-means, points get soft memberships (e.g., a midpoint point belongs 50/50).

Spectral — Intuition

Two concentric rings are not linearly separable in original space, so k-means fails. The graph Laplacian's eigenvectors separate the rings into two clean bands; k-means on the embeddings recovers both rings. Spectral clustering excels when clusters are defined by connectivity, not centroid proximity.

Validation — Worked Silhouette

Point $i$ in cluster A with $a (i) = 2$ (avg intra dist); nearest other cluster has $b (i) = 6$ . $s (i) = (6 - 2) / max (2, 6) = 4 / 6 = 0.67$ ⇒ well clustered. If instead $a (i) = 5, b (i) = 6$ , $s (i) = 0.17$ ⇒ borderline. Mean silhouette over all points ≈ overall quality; compare across $k$ to pick the best.

Index Comparison

Index	Range	Higher = better?	Needs labels?
ARI / NMI	[0,1] (ARI can be <0)	yes	yes
Silhouette	[−1,1]	yes	no
Davies-Bouldin	[0,∞)	no (lower)	no
Calinski-Harabasz	[0,∞)	yes	no

Self-Organizing Map (SOM)

A neural-net grid (usually 2-D) where each neuron holds a weight vector; training moves neurons toward nearby input points (competitive learning + neighborhood updating). Result: a topology-preserving map where similar inputs land in adjacent neurons — a soft, visualizable cluster structure.

COBWEB (Conceptual / Categorical)

Incremental hierarchical clustering for categorical data; splits/merges nodes to maximize category utility (a heuristic combining intra-cluster similarity and inter-cluster dissimilarity). Produces a concept tree rather than numeric clusters.

Choosing a Clustering Method (Guide)

Data	Recommended
spherical, similar size, known $k$	k-means / k-medoids
arbitrary shape, noise, unknown $k$	DBSCAN / OPTICS
non-convex / concentric	spectral
probabilistic, need soft membership	EM
very large / streaming	BIRCH / CLARA / STING
high-D, clusters in subspaces	CLIQUE / PROCLUS / subspace

Summary

Advanced clustering handles shapes, densities, models, and high dimensions that basic methods miss. DBSCAN finds arbitrary shapes and noise via density (core/border/noise, $ϵ$ , $M i n P t s$ ); OPTICS extends it to varying densities via a reachability plot. Grid/CLIQUE methods quantize space for speed and subspace discovery. EM fits Gaussian mixtures with soft assignments (eigendecomposition-free, likelihood-based). Spectral clustering embeds points via the graph Laplacian then k-means — great for non-convex clusters. Validate with external (ARI, NMI) and internal indices (silhouette, Davies-Bouldin, Calinski-Harabasz), and choose $k$ by relative criteria.

Cluster Analysis (Advanced) ​

1. Density-Based: DBSCAN ​

Definitions ​

Algorithm ​

2. OPTICS (Ordering Points To Identify Clustering Structure) ​

3. Grid-Based: STING, CLIQUE ​

4. Model-Based: Expectation-Maximization (EM) ​

Mixture of Gaussians ​

EM Algorithm (two steps, iterated) ​

Properties ​

Other model-based ​

5. Spectral Clustering ​

6. High-Dimensional & Subspace Clustering ​

7. Cluster Validation ​

External Indices (vs known labels) ​

Internal Indices (no labels) ​

Relative Criteria ​

Stability ​

DBSCAN — Worked Example ​

EM — Worked Sketch (1-D, k=2) ​

Spectral — Intuition ​

Validation — Worked Silhouette ​

Index Comparison ​

Self-Organizing Map (SOM) ​

COBWEB (Conceptual / Categorical) ​

Choosing a Clustering Method (Guide) ​

Summary ​