Extension of the basic K-Means algorithm
Basic idea: Initially split the data into two
cluster, then further split one of the clusters,
and so on, until there are K clusters
Side-product: results in hierarchical clusters

Initialization: Set of clusters contains one
cluster with all points
Repeat until list of clusters contains K clusters
Remove cluster from list
For number of trials do:
Bisect cluster with basic K-Means
Select bisection with lowest total SSE
Add both clusters to list of cluster

Which cluster should be selected for bisection?
Cluster with largest SSE
Largest cluster (in terms of number of points)
The `trials' in the bisecting K-Means algorithm
try di erent seed initializations (see basic
K-Means)