Back to Curriculum
Basic•Machine Learning
K-Means Clustering
Unsupervised grouping of data points.
Interactive Playground
Initializing Interactive Playground...
Research-Level Deep Dive & Equations
Clustering is the primary unsupervised learning task, aimed at partitioning an unlabeled dataset into distinct homogeneous groups. Formally, given a dataset where , the objective is to partition the samples into disjoint subsets (where and for ).
The quality of a partition is measured by the **Within-Cluster Sum of Squares (WCSS)**, also known as the K-means objective function:
where is the representative prototype (centroid) of cluster .
**NP-Hardness & Combinatorial Complexity**:
To find the global minimizer of , one could theoretically evaluate all possible partitions of elements into non-empty sets. The number of such partitions is given by the **Stirling numbers of the second kind**:
For extremely modest datasets (e.g., ), , which exceeds the computational capabilities of any physical computer. Thus, global minimization of the WCSS objective is NP-hard in Euclidean space, even for in arbitrary dimensions, or for in arbitrary cluster counts. We must therefore rely on iterative, heuristic optimization algorithms.
Key Equations
Test Your Knowledge
Check whether you have mastered this concept with a quick quiz.
Was this lesson helpful?
Your feedback helps us continuously improve the curriculum and interactive visualizations.