Cluster Analysis and the Major Clustering Methods

1. What is cluster analysis?

Cluster analysis (clustering) is the task of grouping a set of physical or abstract objects into classes (clusters) of similar objects, so that objects within a cluster are highly similar to one another and as dissimilar as possible to objects in other clusters. It is an unsupervised learning task - no class labels are supplied, and the grouping emerges from the data itself. Similarity is usually measured by distance functions such as Euclidean, Manhattan or cosine distance.

Requirements of a good clustering algorithm: scalability to large data sets, ability to deal with different attribute types, minimal dependence on domain knowledge, discovery of clusters of arbitrary shape, robustness to noise and outliers, and interpretable results.

2. Categorisation of major clustering methods

Method	Representative algorithms	Key idea
Partitioning	k-means, k-medoids (PAM), CLARANS	Build k partitions that minimise a cost function; clusters are spherical and described by prototypes (centroids)
Hierarchical	AGNES, DIANA, BIRCH, CURE, CHAMELEON	Create a nested hierarchy (tree / dendrogram) of clusters, either bottom-up (agglomerative) or top-down (divisive)
Density-based	DBSCAN, OPTICS, DenCLUE	A cluster is a continuous region of high point density separated by regions of low density; finds arbitrary shapes and marks noise
Grid-based	STING, CLIQUE, WaveCluster	Quantise the object space into a finite number of cells on a grid and operate on the grid - very fast, resolution-dependent
Model-based	EM (Gaussian mixtures), COBWEB, SOM	Assume a statistical or neural model for each cluster and fit the data to it (e.g. maximise likelihood)

Brief explanation:

1. Partitioning methods - start with a random or sampled set of k representatives and iteratively reassign points to the nearest representative until convergence (e.g. Lloyd's k-means). Fast and simple, but need k in advance and favour convex clusters.
2. Hierarchical methods - produce a dendrogram that the analyst can cut at any level; no need to prespecify k, but merges/splits are irreversible and a naive implementation costs $O(n^3)$ time and $O(n^2)$ memory.
3. Density-based methods - grow clusters from dense seeds, so the number of clusters and the cluster shape are discovered automatically and noise is handled naturally.
4. Grid-based methods - move the computation from individual objects to cells, giving constant-time complexity with respect to the number of data objects.
5. Model-based methods - treat clusters as probability distributions or neural units, giving a principled statistical framework (but assuming a particular model form).