Katkat
Back

Implement K-means clustering from scratch

AdobeMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your understanding of the K-means clustering algorithm, specifically the iterative process of centroid initialization, assignment, and update steps.

Problem Statement

Implement the K-means clustering algorithm from scratch. Given a set of 2D points and an integer k, group the points into k clusters.

Your task is to implement the kmeans(points, k, max_iters) function. You should initialize the centroids by randomly selecting k points from the input data. Use Euclidean distance to assign points to the nearest centroid and update centroids by calculating the mean of all points assigned to that cluster.

Function Signature

import numpy as np

def kmeans(points, k, max_iters=100):
    # points: numpy array of shape (N, D)
    # k: number of clusters
    # returns: centroids (k, D) and labels (N,)
    pass

Example

points = np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]])
k = 2
# Expected behavior: Two clusters should emerge, one around (1, 2) and one around (10, 2).

Constraints

  • 1 <= k <= N
  • points will contain between 1 and 10,000 samples.
  • Handle the case where a cluster might become empty during an iteration (e.g., re-initialize that centroid to a random point from the dataset).

Edge Cases

  • What happens if the centroids do not move significantly between iterations?
  • How do you handle clusters that contain no points after an assignment step?

Hints

Hint 1

Use numpy broadcasting to efficiently calculate the distance matrix between all points and all centroids.

Hint 2

The assignment step involves finding the index of the minimum distance for each point, which can be done using `np.argmin` along the correct axis.

Hint 3

To handle empty clusters, you can check if any centroid has zero points assigned to it and re-initialize it to a random data point.

Follow-up questions

  • How does the choice of initial centroids affect the final clustering result, and what is the 'K-means++' initialization technique?
  • How would you determine the optimal value of 'k' if it is not provided?
  • What is the computational complexity of one iteration of K-means, and how does it scale with dimensions and the number of points?