Questions tagged [k-means]

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. Repeat 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} \bigg(\big \lVert x_i - \mu_j \big \rVert^2 \bigg)$$

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