K-means strengths and weaknesses

K-means algorithm

K-means partitions n objects into k clusters where each object belongs to the cluster with the nearest mean (centroid).

1. Choose k and select k initial centroids (random objects).
2. Repeat
   a. Assign each object to the nearest centroid
      (Euclidean distance) -> k clusters.
   b. Recompute each centroid as the mean of its cluster.
3. Until no object changes cluster (centroids stable).

It minimises SSE = Σᵢ Σ_{x∈Cᵢ} d(x, cᵢ)². Example: points 1, 2, 9, 10 and k = 2 with initial centroids 1 and 2 give {1, 2} and {9, 10} with centroids 1.5 and 9.5.

Strengths

• Simple and easy to implement and understand.
• Efficient and scalable: complexity O(n·k·t), where t (iterations) and k are much less than n.
• Usually converges quickly; good for large data sets.
• Produces tight, compact clusters when clusters are globular, and gives clear cluster centres.
• Easy to adapt (k-medoids, k-modes, bisecting k-means).

Weaknesses

• The number of clusters k must be specified in advance.
• Result depends on the initial centroids and often ends in a local optimum; it must be rerun several times.
• Sensitive to noise and outliers since the mean is affected by extreme values.
• Applicable only when the mean is defined (numeric data); categorical data needs k-modes.
• Cannot find non-convex or arbitrarily shaped clusters, nor clusters of very different sizes or densities.
• Distances lose meaning in high dimensions; empty clusters may occur.