K-Means Limitations & Bisecting K-Means

Source: Unit 4 §4

Plain K-means has two separate weaknesses: the shape of cluster it can express, and its dependence on where the initial centroids happen to land. Bisecting K-means is the standard answer to the second one.

K-means limitations

Limitation	Problem
Differing sizes	tends to split big clusters and merge small ones
Differing density	dense and sparse clusters together confuse it
Non-globular (non-convex) shapes	it assumes spherical clusters

K-means can only draw straight boundaries between centroids, so a crescent is a shape it is structurally unable to keep whole.

The initial-centroids problem

If there are K real clusters in the data, the chance of the random initialization picking one centroid from each is small, and it gets worse as K grows. Assuming the clusters are of equal size $n$:

$$P(\text{one centroid per cluster}) = \frac{K!}{K^K}$$

#NumbersHow bad it gets at K = 10

$10! / 10^{10} = \mathbf{0.00036}$. That is a 0.036% chance of a clean start. Sometimes the centroids readjust their way out of a bad start, and sometimes they do not.

Solutions to the initial-centroids problem:

• Multiple runs - helps, but the odds are not great.
• Sample plus hierarchical clustering to determine the initial centroids.
• Select more than K initial centroids, then keep the most widely separated ones.
• Post-processing.
• Generate more clusters than needed, then hierarchically merge them.
• Bisecting K-Means, which is less sensitive to initialization.

Bisecting K-Means

A variant that splits one cluster into two at each step (using K-means with K=2) until K clusters exist. It is a hybrid of divisive hierarchical clustering (top-down) and K-means.

→StepsBisecting K-Means

1. Set K, the desired number of clusters.
2. Put all the data in a single cluster.
3. Use K-means with K = 2 to split the cluster.
4. Measure each cluster's intra-cluster distance (sum of squared distance).
5. Select the cluster with the largest distance and split it into 2 with K-means.
6. Repeat steps 3 to 5 until the number of leaf clusters equals K.

Bisecting K-means never runs K-means with K > 2. It runs K-means with K = 2, over and over, always on the worst cluster it currently has.

≡FactsLocal vs global minimum

• A local minimum is good but not necessarily the best available.
• A global minimum is the best possible.
• Bisecting K-Means avoids getting stuck in a poor local minimum, which is exactly the failure mode plain K-means has.

Advantages over plain K-Means:

• More efficient when K is large.
• Produces clusters of similar sizes, where plain K-means produces widely different ones.

Cross-link: K-Means as EM

K-Means is a special case of Expectation-Maximization:

• E-step: assign each point to the closest cluster ($w_{ik} = 1$ if $x_i \in$ cluster $k$, else 0).
• M-step: recompute each centroid as the cluster mean.
• Convergence to a local minimum is guaranteed, which is why random restarts are standard practice.

(The full EM treatment is in Unit 3 §10.)