K-means is widely used in clustering due to its simplicity and efficiency. The algorithm begins by initializing k centroids, where k is the number of clusters defined by the user. These centroids are placed randomly within the data space. Each data point is then assigned to the cluster represented by the nearest centroid, with the distance typically measured using the Euclidean distance formula.
After all points have been assigned, the centroids of the clusters are updated to the mean position of all points within each cluster. This process of assignment and update is repeated iteratively until the centroids stabilize, meaning they no longer change significantly, or a maximum number of iterations is reached.
flowchart TD
A[Start] --> B[Initialize k centroids randomly]
B --> C[Assign data points to nearest centroid]
C --> D[Recalculate centroids as the mean of assigned points]
D --> E{Centroids stabilise?}
E -- No --> C
E -- Yes --> F[Clusters are formed]
F --> G[End]
For example, in a sports setting, consider performance data for players on a football team, including metrics such as goals scored, assists, tackles, and distance covered during a game.
K-means can group these players into clusters that represent different playing styles, such as strikers, midfielders, and defenders, based on their performance characteristics.
The algorithm begins by randomly initialising k centroids in the data space. Each data point xi is assigned to the cluster Cj whose centroid μj is closest to it, typically based on the Euclidean distance.
The assignment step minimises the following distance:
$$ d(x_i, \mu_j) = \sqrt{\sum_{m=1}^n (x_{im} - \mu_{jm})^2} $$
After the assignment, the centroids are updated by taking the mean of all data points in the cluster:
$$ u_j = \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i $$
This process of assignment and update is repeated iteratively until the centroids stabilise or a maximum number of iterations is reached.
