K-Means Clustering

Traditionally, in machine learning, we start with the popular partitional clustering algorithm called $k$-means clustering. This algorithm divides the data into $k$ clusters based on a similarity score. The objective is to minimize the total variance of the $k$ clusters. The number of clusters, $k$, must be specified.

Note: The choice of similarity metric is a hyperparameter.

Objective

K-means clustering aims to partition a dataset into $k$ clusters such that the total variance of the clusters is minimized. This means we want the data points within each cluster to be as close to each other as possible.

Given a set of $n$ data points $D=\{\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n\}$ in $\mathbf{R}^d$ (a $d$-dimensional Euclidean space), the goal is to partition $D$ into $k \ge 2$We require at least two partitions because clustering a dataset into 1 cluster would simply be the original dataset itself, which is trivial. non-empty partitions, ...