k-means is a method to partition data into clusters by finding a specified number of means, k, s.t. when data are assigned to clusters w/ the nearest mean, the w/i cluster sum of squares is minimized

K-means clustering attempts to achieve the following objective:

Given an integer $k$ and a set of $n$ data points in $\mathbb{R}^{d}$, the goal is to choose $k$ centers so as to minimize the total squared distance between each point and its closest center, also known as the within-group sum of squares.

To solve this problem exactly is in fact NP-hard, so instead an approximation algorithm is used:

  1. Choose $k$ initial centroids. The most basic method is to choose $k$ samples from the dataset $X$, although other variations exist.
  2. Assign each data point to its nearest centroid.
  3. Create new centroids by taking the mean value of all of the data points assigned to each previous centroid. Find the difference. This is the within-group sum of squares.
  4. Repeats steps 2. and 3. until the difference is less than a threshold.

Mathematically, k-means attempts to choose centroids that minimize the following objective function:

$$ \sum_{i=0}^{n}\min_{\mu_j \in C}(||x_i - \mu_j||^2)$$

where $x_j$ are data points and $\mu_i$ is the $i^{th}$ centroid.

history | excerpt history