K-Means Clustering

MediumML Coding

Problem statement

Implement k_means_clustering(points, k, initial_centroids, max_iterations) and return the final centroids. Starting from the supplied centroids, alternate assigning each point to its nearest centroid and moving each centroid to the mean of its assigned points.

Function Inputs:
  • points: A list of points, where each point is a tuple of coordinates (e.g., (x, y) for 2D points or (x, y, z) for 3D points). All points must have the same dimensionality.
  • k: An integer representing the number of clusters to form
  • initial_centroids: A list of initial centroid points, each a tuple of coordinates with the same dimensionality as the input points
  • max_iterations: An integer representing the maximum number of iterations to perform
Function Output:

Return a list of k coordinate tuples in the same cluster order as initial_centroids. Round each coordinate to 4 decimal places only when returning; keep full precision during the iterations.

Rules:

  • Each iteration assigns every point to the nearest centroid by Euclidean distance (on a tie, the centroid with the lower index), then moves each centroid to the mean of its assigned points.
  • If a cluster receives no points, keep its previous centroid.
  • Stop after max_iterations iterations, or earlier if the centroids stop changing. Return a list of k tuples with every coordinate rounded to 4 decimals.

Example

Input:

points = [(1, 2), (1, 4), (1, 0), (10, 2), (10, 4), (10, 0)], k = 2, initial_centroids = [(1, 1), (10, 1)], max_iterations = 10

Output:

[(1.0, 2.0), (10.0, 2.0)]

Reasoning: The three points with $x = 1$ are closest to $(1, 1)$ and the three with $x = 10$ are closest to $(10, 1)$. Their means are $(1, 2)$ and $(10, 2)$; a second pass assigns the points the same way, so the centroids stop changing.

Show hint

The algorithm alternates two steps; what is fixed and what is optimized in each one?

Relevant roles: ML Engineer, Data Scientist, Applied Scientist and Research Scientist.

Related free problems