Overview of Core Clustering Approaches with Examples

Clustering groups unlabeled data into sets (clusters) such that items in the same cluster are more similar to each other than to items in other clusters. Common high-level families include partitioning methods , hierarchical methods , density-based methods , grid-based methods , model-based methods , high-dimensional methods , and constraint-based methods.

Key terms you’ll see repeatedly:

• k
• dendrogram
• [epsilon ($\epsilon$)]{def="Radius parameter defining a neighborhood in density-based clustering"}
• latent variable
• subspace clustering

1) Partitioning methods

Partitioning methods try to find a single partition of the dataset into $k$ clusters, usually by iterative refinement.

Typical examples

k-means

• Assumes clusters are represented by centroids and assigns each point to its nearest centroid.
• Optimizes the within-cluster sum of squares (squared Euclidean distances).

k-medoids (PAM)

• Like k-means but uses actual data points as representatives (medoids) rather than centroids.
• Minimizes the sum of distances to the nearest medoid.

Concrete example

Suppose you have 2D customer embeddings and want $k=3$ segments.

• With k-means, you initialize 3 centroids and repeatedly (1) reassign points to the closest centroid, then (2) recompute centroids as the mean of assigned points.
• With k-medoids, you would instead pick 3 actual points (medoids) and reassign points to the closest medoid, updating medoids to reduce total distance.

When they work well: approximately spherical clusters with comparable variance and Euclidean-like geometry.
Common failure modes: sensitivity to initialization/outliers; forcing $k$ even when the data has a different number of natural groups.

Footnotes

1. k-means clustering - Wikipedia - Describes k-means objective as minimizing within-cluster sum of squares. ↩ ↩²

2. k-medoids - Wikipedia - Defines medoids as representative data points and describes PAM/k-medoids. ↩ ↩²

3. Lecture 10: k-means clustering (Lloyd’s algorithm) - Provides Lloyd’s algorithm structure and k-means cost. ↩

2) Hierarchical methods

Hierarchical methods construct a nested set of partitions, visualized as a dendrogram.

Two directions

• Agglomerative (bottom-up): start with each point as its own cluster, then merge the closest clusters until one cluster remains (or until you have $k$ clusters).
• Divisive (top-down): start with all points in one cluster, then split clusters recursively.

Linkage criteria (how distance between clusters is defined)

Common linkage choices:

• Single linkage: uses nearest pair distance → can produce “chaining.”
• Complete linkage: uses farthest pair distance → tends to produce more compact clusters.
• Average linkage: uses average pairwise distance.
• Ward linkage: merges clusters to minimize increase in within-cluster variance (typically Euclidean only).

Concrete example

You can cluster 1,000 samples into 4 groups by:

1. Run agglomerative clustering to build the dendrogram.
2. Choose a cut height (or directly request $n\_clusters=4$).
3. Compare linkages (e.g., single vs complete vs Ward) to see how dendrogram structure changes.

Footnotes

1. Agglomerative Clustering - GeeksforGeeks - Explains agglomerative hierarchical clustering procedure and dendrogram notion. ↩

2. Choosing a Linkage Method for Hierarchical Clustering (MetricGate) - Compares single/complete/average/Ward and interprets linkage behavior. ↩ ↩²

3) Density-based methods

Density-based methods identify clusters as connected regions of high density and label isolated points as noise/outliers.

Typical examples

DBSCAN

• Uses parameters $\epsilon$ (neighborhood radius) and MinPts (minimum points to form a dense region).
• Does not require pre-specifying the number of clusters.
• Forms clusters by growing connected dense regions; points in low-density areas become outliers.

OPTICS

• Extends DBSCAN’s idea by producing an ordering of points and a reachability plot, helping reveal clusters across varying densities.

Concrete example

Consider GPS points from multiple trips that have dense “route cores” and sparse gaps.

• With DBSCAN, pick $\epsilon$ and MinPts so that dense segments become clusters, while gaps become separation/noise.
• If clusters have different densities (e.g., some routes are dense, others are sparse), OPTICS can help because its reachability plot reveals structure across density levels.

Key limitations (brief)

DBSCAN’s performance can depend on global $\epsilon$ and MinPts when density varies strongly across the dataset.

Footnotes

1. DBSCAN - Wikipedia - Defines DBSCAN, parameters ($\epsilon$, MinPts), and outlier handling. ↩ ↩² ↩³

2. Ordering Points With OPTICS (CRAN dbscan package vignette) - Explains OPTICS ordering, reachability plot, and parameter roles. ↩ ↩²

4) Grid-based methods

Grid-based methods discretize the space into a grid and cluster dense cells. This can improve scalability and handle certain subspace patterns.

Typical examples

CLIQUE

• Finds dense clusters in subspaces by searching across different dimensionalities and locating dense units using a grid approach (often via an Apriori-like strategy). STING / WaveCluster (conceptual family)
• Other grid-based approaches compute statistics per cell and use hierarchical merging/splitting of dense regions (e.g., STING uses multi-level grids and summary statistics).

Concrete example

For gene-expression data with many features, clusters may only appear in some subsets of genes.

• CLIQUE searches for dense regions in many subspaces (not just the full dimension), then returns subspace clusters.

Footnotes

1. A Survey on STING and CLIQUE Grid Based Clustering Methods - Survey describing CLIQUE grid/subspace density clustering approach. ↩ ↩²

2. A Survey on STING and CLIQUE Grid Based Clustering Methods - Includes discussion of STING/WaveCluster style grid approaches. ↩

5) Model-based methods

Model-based methods treat clustering as inference in a probabilistic model. Assignments can be “soft” (probabilistic membership).

Typical examples

Gaussian Mixture Models (GMM)

• Assume data are generated by a mixture of Gaussian distributions.
• Parameters are typically estimated by the Expectation-Maximization (EM) algorithm.

Concrete example

Suppose you model 2D sensor readings as mixtures of two overlapping Gaussian blobs.

• Fit a GMM with $k=2$ components using EM.
• Each point gets posterior probabilities of belonging to each component (soft clustering), and you can label clusters by the highest posterior. 2

Footnotes

1. Expectation-Maximization for the Gaussian Mixture Model (Bonald notes) - Describes EM for fitting GMM parameters and relation to clustering. ↩ ↩²

2. Applied Machine Learning Lecture video transcript (EM in GMM) - Video explanation of EM steps for GMM clustering (used as a learning resource). ↩

6) Methods for high-dimensional data

High-dimensional data methods address the curse of dimensionality, where distance measures become less meaningful and points can become sparse.

Typical examples / strategies

Subspace clustering

• Assumes meaningful clusters exist only in subsets (subspaces) of features.
• CLIQUE is a canonical example: it searches for dense clusters in subspaces of varying dimensionality.
• More broadly, subspace clustering integrates feature selection with clustering to avoid treating all dimensions as equally relevant.

Concrete example

For text data represented by bag-of-words or embeddings:

• Instead of clustering in the full feature space, subspace methods attempt to find feature subsets where clusters are dense/structured—improving interpretability and robustness against irrelevant/noisy features. 2

Footnotes

1. Subspace Clustering for High Dimensional Data: A Review (KDD Explorations PDF) - Discusses curse of dimensionality and why distances lose meaning. ↩ ↩²

2. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications (CLIQUE paper PDF) - Presents CLIQUE and subspace-density clustering. ↩

3. Subspace Clustering for High Dimensional Data: A Review (KDD Explorations PDF) - Motivates subspace clustering integrating feature relevance with clustering. ↩ ↩²

7) Constraint-based methods

Constraint-based methods incorporate prior knowledge about which pairs should (or should not) be in the same cluster.

Typical examples

COP-KMeans (Constrained k-means)

• Uses must-link and cannot-link constraints as hard feasibility conditions in the assignment step.
• If an instance cannot be assigned without violating constraints, the algorithm may fail (no feasible solution).

Concrete example

You have semi-labeled supervision from a domain expert:

• must-link: “These two documents are definitely in the same topic cluster.”
• cannot-link: “These two documents must not be in the same cluster.” Using COP-KMeans, assignments are constrained so cluster membership respects those pairwise rules during optimization. 2

Footnotes

1. Constrained clustering with must-link and cannot-link constraints (COP-KMeans referenced) - Explains COP-KMeans as hard constraints in assignment. ↩ ↩²

2. Constrained K-means Clustering with Background Knowledge (notes) - Provides COP-KMeans-style must-link/cannot-link constraint enforcement algorithm outline. ↩

Summary table (what each family optimizes / discovers)

Footnotes

1. k-means clustering - Wikipedia - Describes k-means objective as minimizing within-cluster sum of squares. ↩

2. k-medoids - Wikipedia - Defines medoids as representative data points and describes PAM/k-medoids. ↩

3. Agglomerative Clustering - GeeksforGeeks - Explains agglomerative hierarchical clustering procedure and dendrogram notion. ↩

4. Choosing a Linkage Method for Hierarchical Clustering (MetricGate) - Compares single/complete/average/Ward and interprets linkage behavior. ↩

5. DBSCAN - Wikipedia - Defines DBSCAN, parameters ($\epsilon$, MinPts), and outlier handling. ↩

6. Ordering Points With OPTICS (CRAN dbscan package vignette) - Explains OPTICS ordering, reachability plot, and parameter roles. ↩

7. A Survey on STING and CLIQUE Grid Based Clustering Methods - Survey describing CLIQUE grid/subspace density clustering approach. ↩

8. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications (CLIQUE paper PDF) - Presents CLIQUE and subspace-density clustering. ↩

9. Expectation-Maximization for the Gaussian Mixture Model (Bonald notes) - Describes EM for fitting GMM parameters and relation to clustering. ↩

10. Applied Machine Learning Lecture video transcript (EM in GMM) - Video explanation of EM steps for GMM clustering (used as a learning resource). ↩

11. Subspace Clustering for High Dimensional Data: A Review (KDD Explorations PDF) - Discusses curse of dimensionality and why distances lose meaning. ↩

12. Subspace Clustering for High Dimensional Data: A Review (KDD Explorations PDF) - Motivates subspace clustering integrating feature relevance with clustering. ↩

13. Constrained clustering with must-link and cannot-link constraints (COP-KMeans referenced) - Explains COP-KMeans as hard constraints in assignment. ↩

14. Constrained K-means Clustering with Background Knowledge (notes) - Provides COP-KMeans-style must-link/cannot-link constraint enforcement algorithm outline. ↩