K-Means Clustering
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 forminitial_centroids: A list of initial centroid points, each a tuple of coordinates with the same dimensionality as the input pointsmax_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_iterationsiterations, or earlier if the centroids stop changing. Return a list ofktuples 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
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium