Partitioning Methods vs Hierarchical Methods in Cluster Analysis

Definition. Partitioning methods decompose the data set directly into a fixed number of non-overlapping clusters, while hierarchical methods build a nested hierarchy of clusters, usually displayed as a dendrogram, and reach a partition by cutting that tree.

1. Partitioning methods

• Idea: one flat partition of $n$ objects into $k$ clusters, $k$ specified in advance.
• Representative algorithms: k-means (centroid), k-medoids/PAM (representative object), CLARA and CLARANS for large data, k-modes for categorical data.
• Typical criterion: minimise the within-cluster sum of squares $J = \sum_{c=1}^{k}\sum_{x_i \in C_c} \lVert x_i - \mu_c \rVert^2$ by iterative relocation: assign, recompute, repeat until no change.
• Properties: fast ($O(nkt)$ for k-means), simple, but produces only one flat solution, is sensitive to initialisation and to outliers, and tends to find spherical clusters of similar size.

2. Hierarchical methods

• Idea: produce a sequence of nested partitions rather than one; no $k$ needed up front.
• Agglomerative (bottom-up): start with $n$ singletons, repeatedly merge the two closest clusters until one remains.
• Divisive (top-down): start with all data in one cluster and recursively split it.
• Linkage criteria: single (minimum distance between clusters, chaining effect), complete (maximum distance), average (UPGMA), Ward (minimum increase in within-cluster variance).
• Properties: yields a dendrogram, reveals structure at every granularity, is deterministic, but costs $O(n^2 \log n)$ or $O(n^3)$ time and $O(n^2)$ memory, and merges once made are irreversible.

Dendrogram (agglomerative)

|                  +---- P6
|             +----+---- P5
|        +----+----+---- P4
|   +----+----+---- P3
+---+----+----+---- P2
    +----+----+---- P1
    |         |         |\    height -> distance at which clusters merge

3. Comparison

Criterion	Partitioning (k-means)	Hierarchical (agglomerative)
Output	One flat partition	Nested hierarchy / dendrogram
Number of clusters $k$	Must be fixed in advance	Chosen afterwards by cutting the tree
Approach	Iterative relocation of assignments	Greedy merging or splitting
Reversibility	Reassignments allowed, non-monotonic	Merges are permanent and monotonic
Repeatability	Depends on random seeds	Deterministic for a fixed linkage
Scalability	$O(nkt)$, good for large $n$	$O(n^2 \log n)$, poor for very large $n$
Cluster shape	Spherical, similar sizes	Any shape, depends on linkage
Outliers	Absorbed into clusters	Can be isolated early as singleton branches
Interpretability	Centroids only	Full dendrogram of relationships

4. When to use which

Use partitioning when the data is large, $k$ is known (e.g. $k$ customer segments) and a single flat answer is enough. Use hierarchical methods when the nesting itself is the insight — taxonomy building, gene-family trees, or when $k$ is unknown and the analyst will decide by cutting the dendrogram. Bisecting k-means and BIRCH combine the two ideas: BIRCH builds a compact summary tree first and then partitions it.