Partitioning Methods

Partitioning Methods

1. Principle

Given $n$ objects, a partitioning method constructs $k$ partitions, each partition representing a cluster, where $1 \le k \le n$, and each object belongs to exactly one cluster (hard partition). Quality is judged by an objective function — normally the sum of squared errors / total within-cluster variation.

Global optimality is NP-hard (the number of ways to partition $n$ objects into $k$ clusters is $\frac{1}{k!}\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}i^{n}$), so methods use greedy, iterative relocation (hill-climbing) heuristics.

2. k-Means (Lloyd's algorithm)

Objective:

k-means(D, k):
  1. Choose k objects at random as initial centroids m_1..m_k  (random or k-means++)
  2. repeat
        (a) assign each object p to the cluster C_i whose centroid is nearest
              (minimises E for fixed centroids)
        (b) recompute each centroid as the mean of its assigned objects
     until no object changes cluster  (E stops decreasing)
  3. return clusters

Proof of convergence: step (a) never increases $E$ (each point goes to its nearest centre); step (b) never increases $E$ (the mean is the minimiser of squared distance for a fixed assignment). So $E$ decreases monotonically and the algorithm terminates in a finite number of steps — though at a local minimum.

Numerical example (2-D points A(1,1), B(2,1), C(4,3), D(5,4); $k=2$, initial centroids C1 = A(1,1), C2 = D(5,4)):

Iteration	Assignments	New centroids	E
0	—	$m_1=(1,1)$, $m_2=(5,4)$	—
1	A,B → C1; C,D → C2	$m_1=(1.5,1)$, $m_2=(4.5,3.5)$	$0.5+0.5+0.5+0.5 = 2.0$
2	(check: A,B nearest $m_1$; C,D nearest $m_2$) → unchanged	—	2.0 (converged)

Another typical textbook case: points (2,10), (2,5), (8,4), (5,8), (7,5), (6,4), (1,2), (4,9), $k=3$ → the SSE decreases with each iteration until stable at $E = 21.33$ for the final partition; a different random start can give a different local optimum with a higher $E$.

Choosing initial centroids: random choice is sensitive to outliers and to the random seed. Strategies: (i) multiple runs and keep the lowest $E$; (ii) sample a small subset and use hierarchical clustering to seed; (iii) k-means++ — pick the first centre at random, then each next centre with probability proportional to $D(x)^2$ (squared distance to the nearest chosen centre). The $O(\log k)$-approximation guarantee makes it the modern default.

Determining $k$: run for a range of $k$, plot the elbow curve of $E$ vs $k$ (or use silhouette, gap statistic, BIC) and choose the knee.

 E |
   |\
   | \
   |  \___
   |      \__ knee (elbow) at k = 3
   +------------------------------- k
     1   2   3   4   5   6

3. Limitations of k-Means

• Needs $k$ in advance; sensitive to initial centroids and converges to a local optimum.
• Sensitive to outliers and noise (the mean is pulled; SSE is dominated by distant points).
• Only detects globally spherical, similar-size, similar-density clusters; fails on non-convex shapes.
• Requires numeric attributes ($\|\cdot\|$ and mean) — categorical data needs k-modes/k-prototypes.
• Not suitable for very large $n$ without sampling/variants (each iteration is $O(nkd)$).

4. k-Medoids / PAM (Partitioning Around Medoids)

A medoid is the most centrally located actual object of a cluster — the one that minimises the sum of distances to all other objects in the cluster. Using a real object makes the method robust to outliers.

PAM (Kaufman & Rousseeuw, 1987) uses two phases:

1. BUILD: greedily select the $k$ initial medoids, each time adding the object that most reduces the total cost.
2. SWAP: repeatedly try replacing each medoid with each non-medoid; accept the swap if the total cost (sum of distances from each object to its nearest medoid) decreases; stop when no swap improves.

PAM pseudocode
 BUILD:   pick k medoids (greedy, minimum TCAC)
 repeat
    for each medoid m and each non-medoid o:
        compute the change in cost if m is replaced by o
    accept the best swap if the cost decreases
 until no change

Cost/dissimilarity measure:

Complexity: $O(k(n-k)^2)$ per iteration → too slow for large $n$; use on small datasets only.

5. CLARA (Clustering LARge Applications)

Handles large data by sampling: draw several samples of 40+2k objects, run PAM on each, and keep the clustering with the lowest total cost evaluated on the whole dataset.

Complexity: $O(k(40+k)^2 + k(n-k))$ per sample — much faster than PAM; quality depends on the sample being representative (a rare cluster may be missed).

6. CLARANS (Clustering Large Applications based on RANdomized Search)

Improves on CLARA by searching the whole dataset with randomised search instead of sampling:

• Each node = a set of $k$ medoids; neighbours = nodes obtained by swapping one medoid with a non-medoid.
• numlocal attempts, each performing maxneighbor random neighbour trials; move to a neighbour only if the cost improves. If no improving neighbour is found after maxneighbor trials, the current node is a local optimum — restart from a new random node and keep the best.
• Complexity: $O(n k \times \text{number of trials})$ — better than PAM/CLARA and it does not trade accuracy for sampling.
• Parameter tuning: larger numlocal → better quality, larger maxneighbor → better quality but slower; experiments suggest maxneighbor ≈ 1.25% of $k(n-k)$ gives good results.

7. Comparison

Criterion	k-means	k-medoids (PAM)	CLARA	CLARANS
Representative	Mean (computed)	Actual object (medoid)	Medoid	Medoid
Objective	Minimise SSE	Minimise sum of dissimilarities	Same, on full data	Same
Outlier robustness	Low	High	High	High
Attribute types	Numeric only (k-prototypes for mixed)	Any type with a valid distance	Any with distance	Any with distance
Complexity	$O(nkd)$ per iter	$O(k(n-k)^2)$ per iter	$O(k(40+k)^2 + kn)$	$O(nk \cdot trials)$
Scalability	High	Low	High	High
Cluster shape	Spherical, equal size	Spherical	Spherical	Spherical
Determinism	Random init, local optimum	Greedy, local optimum	Sample dependent	Randomised search

8. Strengths and Weaknesses of Partitioning Methods

Strengths: simple, intuitive, fast on moderate data, easy to implement and parallelise, work well when clusters are compact and $k$ is known.
Weaknesses: need $k$; convex/ball-shaped bias; sensitive to noise (k-means) and initialisation; local optima; poor for varying density, arbitrary shapes, or categorical/high-dimensional data.

9. Exam Points

• Explain k-means with the algorithm, objective function, and a small numerical (2 iterations) — 10 marks (very frequent).
• Prove that k-means converges / E decreases monotonically — 5 marks.
• Explain PAM (BUILD and SWAP) and state why medoids are better than means — 7 marks.
• Compare k-means, k-medoids, CLARA and CLARANS — 5-7 marks.
• Limitations of partitioning methods and how to choose $k$ (elbow/k-means++) — 5 marks.