Suppose an e-commerce site wants to group customers by purchasing habits and demographics without assigning categories in advance. K-means turns each customer into a point and partitions the points into a chosen number, k, of clusters. It is a centroid-based, hard-clustering method: each point belongs to one cluster, represented by a center. section 12.0 section 12.2.5
Given n points with d numeric coordinates, a cluster count k, and an iteration limit, the basic algorithm is:
- Choose k initial centroids at random. They need not be points in the dataset. section 12.2
- Assign each point to its closest centroid by computing the distances. The assignments form clusters. section 12.2
- Move each centroid to the center of mass of its assigned points, then reassign points. Stop when assignments no longer change or the iteration limit is reached. section 12.2
Listing 12.1 k-means clustering
function kmeans(points, numCentroids, maxIter) #1
centroids ← randomCentroidInit(points, numCentroids) #2
clusterIndices[p] ← 0 (∀ p ϵ points) #3
for iter in {1, .., maxIter} do #4
newClusterIndices ← classifyPoints(points, centroids) #5
if clusterIndices == newClusterIndices then #6
break
clusterIndices ← newClusterIndices #7
centroids ← updateCentroids(points, clusterIndices) #8
return (centroids, clusterIndices) #9
The pseudocode shows the implementation’s loop: retain cluster indices, compare them with new assignments, and update centroids only when assignments change. section 12.2
Initialization matters. Unlucky centroids can delay convergence; a centroid with no assigned points may be removed, reducing the cluster count. Run the algorithm several times with different random starts and compare the resulting clusterings. The later assignment and recentering steps are deterministic for a given initialization. section 12.2
K-means is a good candidate when k can be estimated beforehand and clusters are roughly spherical in low-to-medium-dimensional data. It struggles when clusters cannot be approximated by hyperspheres, including non-linearly separable shapes. High dimensions also make nearest-centroid distances less informative and can slow convergence. Density-based alternatives such as DBSCAN address different cluster shapes. section 12.2.2 section 12.2.5 section 12.6
A constrained tree split
An SS+-tree split can use a k-means variant with k = 2 and at most M points per cluster. Grouping nearby points can reduce the oversized, overlapping bounding envelopes caused by a variance-based split. With j iterations, this costs O(jdM), rather than O(dM) for the original heuristic: the iteration limit trades running time for split quality. section 10.5.3
For general clustering, at most m iterations take O(mknd) time: each assignment checks k distances across d coordinates for each of n points. The stated extra-memory bound is O(n + k) for assignments and centroids. Classification can also be distributed because each point needs only the centroid list; reducers can group assigned points for recentering. Distributed initialization is harder and can use centroids supplied by canopy clustering. section 12.2.3 section 13.3
