Understanding K-Means Clustering: A Step-by-Step Implementation in R

K-means clustering is one of the most popular unsupervised machine learning algorithms, used to partition data into distinct groups based on similarity. This blog post walks through a practical implementation in R, demonstrating both manual iteration and convergence-based approaches.

The Problem Setup

We have a simple one-dimensional dataset:

x <- c(1, 2, 5, 6, 8, 10)

Our goal is to partition these six points into three clusters (K=3) using the k-means algorithm.

The K-Means Algorithm

K-means clustering follows an iterative two-step process:

1. Assignment Step: Assign each data point to the nearest centroid
2. Update Step: Recalculate centroids as the mean of all points assigned to each cluster

These steps repeat until the centroids no longer change (convergence).

Core Functions

Cluster Assignment Function

assign_clusters <- function(x, centroids) {
  # Compute distance from each point to each centroid
  dist_mat <- abs(outer(x, centroids, "-"))
  
  # For each point, find index of nearest centroid
  clusters <- max.col(-dist_mat)
  return(clusters)
}

This function uses R’s outer() function to efficiently compute a distance matrix where:

• Rows represent data points
• Columns represent centroids
• Each cell contains the absolute distance between point and centroid

The max.col(-dist_mat) trick finds the minimum distance (by negating) for each point, returning the centroid index.

Centroid Update Function

update_centroids <- function(x, clusters, K) {
  new_centroids <- numeric(K)
  for (k in 1:K) {
    new_centroids[k] <- mean(x[clusters == k])
  }
  return(new_centroids)
}

This function recalculates each centroid as the arithmetic mean of all points currently assigned to that cluster.

Two Implementation Approaches

Approach 1: Fixed Number of Iterations

The first implementation in the code runs exactly three iterations with initial centroids at positions 1, 5, and 6:

centroids <- c(1, 5, 6)   # mu1, mu2, mu3

This approach is useful when you want to:

• Observe the algorithm’s behavior step-by-step
• Debug clustering issues
• Understand how centroids evolve over iterations

Approach 2: Convergence-Based Iteration

The second implementation uses a repeat loop with a convergence check:

repeat {
  # Assignment and update steps...
  
  # Check convergence
  if (all(abs(new_centroids - centroids) < 1e-8)) {
    break
  } else {
    centroids <- new_centroids
  }
}

This approach:

• Continues iterating until centroids stabilize (change < 1e-8)
• Is more typical in production implementations
• Automatically determines the required number of iterations

Starting with different initial centroids (1, 2, 5), this approach demonstrates how initialization affects convergence speed and potentially final results.

Key Insights

Distance Metric

For one-dimensional data, the code uses absolute distance: abs(outer(x, centroids, "-")). In higher dimensions, you would typically use Euclidean distance.

Initialization Sensitivity

K-means is sensitive to initial centroid positions. The code shows two different initializations:

• First: {1, 5, 6}
• Second: {1, 2, 5}

Different starting points can lead to different convergence paths and potentially different final clusters.

Convergence Criteria

The convergence threshold (1e-8) is quite strict, ensuring centroids have essentially stopped moving. In practice, you might also add a maximum iteration limit to prevent infinite loops in edge cases.

Practical Applications

This implementation demonstrates k-means on simple one-dimensional data, but the algorithm extends naturally to higher dimensions. Common applications include:

• Customer segmentation in marketing analytics
• Image compression (color quantization)
• Document clustering for topic modeling
• Anomaly detection in time series data
• Feature engineering through cluster membership

Limitations to Consider

While powerful, k-means has several limitations:

1. Fixed K: You must specify the number of clusters beforehand
2. Initialization dependence: Different starting points can yield different results
3. Spherical clusters: Assumes clusters are roughly spherical and equally sized
4. Outlier sensitivity: Means are sensitive to extreme values

Final Thoughts

This R implementation provides a clear, readable demonstration of the k-means algorithm. By separating the assignment and update steps into distinct functions, the code emphasizes the algorithm’s iterative nature and makes it easy to track how clusters evolve over time.

The dual approach—showing both fixed iterations and convergence-based stopping—offers educational value for understanding algorithmic behavior while also demonstrating practical implementation patterns.

Whether you’re learning machine learning fundamentals or implementing clustering for data analysis, understanding k-means from first principles builds intuition for more advanced clustering techniques like k-means++, DBSCAN, or hierarchical clustering. ```