Overview of Clustering Approaches (with Examples)

Clustering groups objects so that objects within a cluster are similar and objects in different clusters are dissimilar. The main approaches are:

1. Partitioning Methods

Partition $n$ objects into a pre-specified number $k$ of clusters by iteratively refining the cluster representatives until a criterion (typically the squared error) is minimised.

• Examples: k-Means (mean-based centroid), k-Medoids / PAM (uses actual data points as medoids — robust to outliers).

2. Hierarchical Methods

Create a nested hierarchy (dendrogram) either:

• agglomeratively (bottom-up) — each object is its own cluster initially; repeatedly merge the two closest clusters (AGNES);
• divisively (top-down) — start with one cluster and split (DIANA).
  No $k$ is required in advance — choose it by cutting the dendrogram.
• Examples: AGNES, DIANA, BIRCH (scalable, uses CF-trees), CURE (multiple representative points, handles arbitrary shapes).

3. Density-Based Methods

Clusters are dense regions of points separated by low-density areas. They can find clusters of arbitrary shape and naturally identify noise.

• Examples: DBSCAN (dense regions via ε-neighbourhood and MinPts: core/border/noise points), OPTICS (handles varying densities), DENCLUE.

4. Grid-Based Methods

Overlay the data space with a grid of cells and do the clustering on the cells, not on individual objects — the cost depends on the number of cells, not on the number of data objects, so clustering is very fast.

• Examples: STING (statistical summaries per cell), CLIQUE (grid + subspace), WaveCluster.

5. Model-Based Methods

Assume the data follow a probabilistic (mixture) model — one probability distribution per cluster — and find the model that best fits the data (highest likelihood). Membership becomes a probability rather than a hard assignment.

• Examples: EM (Expectation–Maximization) for Gaussian mixtures, Self-Organising Maps (Kohonen nets), COBWEB (conceptual clustering).

6. Methods for High-Dimensional Data

In high dimensions distances concentrate and standard clustering degrades (curse of dimensionality). Approaches:

• subspace clustering — find clusters in lower-dimensional subspaces;
• co-clustering / bi-clustering — group rows and columns simultaneously (common in gene-expression analysis);
• dimension-reduction pre-processing, e.g. PCA, before clustering.
• Examples: CLIQUE, PROCLUS (projected clustering), co-clustering / block clustering.

7. Constraint-Based Methods

Perform clustering subject to user or application constraints, e.g. must-link / cannot-link pairs, or spatial obstacles.

• Examples: COD (Clustering with Obstacles), COP-KMEANS (must-link / cannot-link constraints).

Summary Table

Approach	Core idea	Example
Partitioning	split into k clusters, iterate	k-means, PAM
Hierarchical	nested dendrogram; merge/split	AGNES, BIRCH, CURE
Density-based	dense regions separated by sparse areas	DBSCAN, OPTICS
Grid-based	operate on grid cells	STING, CLIQUE
Model-based	fit a probability model	EM / GMM, SOM
High-dimensional	subspace / co-clustering	CLIQUE, PROCLUS
Constraint-based	obey background constraints	COP-KMEANS, COD