ML0059 K-means II

K-means partitions data into clusters where each point belongs to the cluster with the nearest mean. It is computationally efficient and easy to implement, but it requires specifying the number of clusters in advance, assumes spherical clusters, and is sensitive to initialization and outliers.

(1) Simple And Efficient: Fast to compute, easy to implement, and scalable to large datasets.
(2) Unsupervised And Interpretable: Needs no labels, and the centroids are intuitive summaries of each cluster.
(3) Strong Assumptions: Works best on compact, well-separated spherical clusters; the user must fix beforehand.
(4) Fragility: Poor initial centroids can lock in suboptimal results, outliers drag centroids, and plain Euclidean distance excludes non-numeric features.

Mathematical Formulation:

Where:

• is the number of clusters; the set of points in cluster .
• is the centroid of cluster ; a data point assigned to it.
• is the within-cluster sum of squared distances: the objective both steps of the algorithm drive down monotonically.

Figure 1: The assumption made visible: on spherical, well-separated blobs (left) K-means nails the structure; on two crescents (right) its linear, centroid-based split slices through both moons: the spherical-cluster assumption failing in action.