Categorization of Major Clustering Methods

Clustering groups data objects so that objects in the same cluster are similar to each other and different from objects in other clusters. It is unsupervised learning. The major methods are grouped into five categories.

1. Partitioning methods

Divide n objects into k partitions (clusters), each object belonging to one cluster; the user gives k.

• K-means: each cluster is represented by its mean (centroid); objects are repeatedly assigned to the nearest centroid.
• K-medoids (PAM, CLARA, CLARANS): each cluster is represented by an actual object (medoid); less sensitive to outliers.
• Good for spherical clusters of similar size and for large data; needs k.

2. Hierarchical methods

Build a tree of clusters (dendrogram).

• Agglomerative (bottom-up): start with each object as a cluster and merge the closest.
• Divisive (top-down): start with one cluster and split.
• Linkage: single, complete, average. Variants: BIRCH, CURE, Chameleon.
• No k needed in advance, but a merge or split cannot be undone and it is costly for big data.

3. Density-based methods

A cluster is a dense region of objects separated by regions of low density.

• DBSCAN (parameters eps and MinPts), OPTICS, DENCLUE.
• Finds arbitrary-shaped clusters and handles noise; k not needed; struggles with varying densities.

4. Grid-based methods

Quantize the space into a finite number of grid cells and cluster the cells.

• STING, CLIQUE, WaveCluster.
• Very fast: the time depends on the number of cells, not on the number of objects.

5. Model-based methods

Assume a mathematical model for each cluster and fit the data to it.

• EM (Expectation-Maximization) with Gaussian mixtures, COBWEB (conceptual clustering), SOM (self-organizing maps).
• Gives soft (probabilistic) membership; depends on the assumed model.

Summary table

Category	Basic idea	Examples	Strength	Weakness
Partitioning	Split into k groups, iteratively optimize	K-means, K-medoids	Simple, scalable	Needs k, spherical shapes, outliers
Hierarchical	Tree of merges/splits	AGNES, DIANA, BIRCH	Dendrogram, no k	Not scalable, no undo
Density-based	Dense regions	DBSCAN, OPTICS	Arbitrary shapes, noise	Parameter sensitivity
Grid-based	Grid cells	STING, CLIQUE	Fast	Less accurate boundaries
Model-based	Statistical model fit	EM, COBWEB, SOM	Soft clusters	Model assumptions

Some methods combine ideas from several categories (for example high-dimensional and constraint-based clustering).

Conclusion

The right method depends on data size, cluster shape, presence of noise and whether k is known.