Mastering K-Means: How Distance-Based Clustering Works and How to Implement It

1. K-means Algorithm

K-means is a simple yet classic distance‑based clustering algorithm that uses distance as a similarity metric, assuming that the closer two objects are, the more similar they are. The algorithm forms clusters from nearby objects, aiming for compact and independent clusters.

Through iterative optimization, K-means seeks a partition of k clusters that minimizes the total error when each cluster’s mean represents its samples.

K clusters have the following properties: each cluster is as compact as possible, while clusters are as far apart from each other as possible.

The foundation of K-means is the minimization of the sum of squared errors (SSE). If the data are expressed mathematically and the clusters are denoted as C₁,…,C_k, the objective is to minimize:

∑_{j=1}^{k} ∑_{x_i ∈ C_j} ‖x_i – μ_j‖², where μ_j is the centroid (mean vector) of cluster j.

Directly finding the global minimum is NP‑hard, so a heuristic iterative method is used.

2. Steps

Step 1: Randomly select k initial cluster centroids.

Step 2: Repeat the following until convergence:

For each sample i, assign it to the nearest centroid’s cluster.

Step 3: For each cluster, recompute its centroid as the mean of its assigned samples.

Convergence is reached when the distance between newly computed centroids and the previous centroids falls below a predefined threshold, indicating stable centroid positions.

Reference

ThomsonRen GitHub https://github.com/ThomsonRen/mathmodels