Basic Clustering Methods

The fundamental clustering approaches, with their ideas and typical algorithms:

1. Partitioning Methods

Divide the $n$ objects into $k$ clusters (given in advance) by iteratively refining cluster representatives (centroids/medoids) until a criterion such as the squared error is minimised.

$$E = \sum_{i=1}^{k}\sum_{x \in C_i} \|x - \mu_i\|^2$$

• Examples: k-Means (mean centroid), k-Medoids/PAM (actual data object as representative, robust to outliers).

2. Hierarchical Methods

Create a nested hierarchy of clusters (dendrogram):

• agglomerative (bottom-up): start with every object as its own cluster, repeatedly merge the closest two;
• divisive (top-down): start with one cluster, repeatedly split.
  No $k$ is needed upfront — the user "cuts" the dendrogram later.
• Examples: AGNES, DIANA, BIRCH (scalable via CF-trees), CURE (multiple representatives, arbitrary shapes).

3. Density-Based Methods

Clusters are dense regions of points separated by low-density (sparse) regions. Can discover clusters of arbitrary shape and explicitly mark noise.

• Examples: DBSCAN (ε-neighbourhood + MinPts), OPTICS, DENCLUE.

4. Grid-Based Methods

Partition the data space into a grid of cells and cluster on the cells rather than on individual points — cost depends on number of cells, not on data size, so these methods are very fast.

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

5. Model-Based Methods

Assume each cluster follows a probability distribution (e.g., Gaussian) and find the model that best fits the data (maximising likelihood). Membership becomes probabilistic rather than hard.

• Examples: EM (Expectation–Maximization / Gaussian mixture), Self-Organising Maps (SOM), COBWEB (conceptual clustering).

---

Comparison table

Method	Key idea	k needed?	Shapes	Complexity (typical)
Partitioning	refine k centroids/medoids	Yes	spherical	O(n·k·iterations)
Hierarchical	merge/split into a dendrogram	No	any (linkage-dependent)	O(n²)–O(n³)
Density-based	dense regions separated by sparse	No	arbitrary	O(n log n) w/ index
Grid-based	cluster on grid cells	No	arbitrary	depends on grid size
Model-based	fit probability distributions	No (AIC/BIC)	distribution-shaped	iterative EM

These five form the basic taxonomy of clustering methods in data mining.