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:
- Choose $k$ initial centroids. The most basic method is to choose $k$ samples from the dataset $X$, although other variations exist.
- Assign each data point to its nearest centroid.
- 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.
- 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.
