Preporato

Assign points to the nearest centroid

Easy8 min11 hidden tests

A grocery chain groups its shoppers into segments. Each shopper is a point such as (visits per month, average basket in tens of dollars), and each segment has a centroid, its center point. Write assign_clusters(points, centroids) that returns, for every shopper, the index of the closest centroid by Euclidean distance. If a shopper is exactly as close to two centroids, pick the lower index.

Drag a centroid

each point joins the closest centroid
Centroid 1Centroid 2Centroid 3

Centroid 1: 6 points · Centroid 2: 11 points · Centroid 3: 4 points

Centroid 1 selected. Centroid 1 has 6 points. Centroid 2 has 11 points. Centroid 3 has 4 points.

Examples

Two segments, three shoppers

assign_clusters([[1.0, 2.0], [8.0, 7.5], [4.0, 4.0]], [[2.0, 2.0], [7.0, 8.0]])

returns [0, 1, 0]

Exactly halfway, so the lower index wins

assign_clusters([[5.0, 5.0]], [[0.0, 0.0], [10.0, 10.0]])

returns [0]

Requirements

  • points is a 2-D list or array of shape (n, d) and centroids one of shape (k, d), with n, k and d all 1 or more.
  • Return a 1-D NumPy int array of length n. Entry i is the index (0 to k - 1) of the centroid nearest to point i.
  • Distance is Euclidean: the square root of the summed squared differences. Ties go to the lower centroid index.
The idea behind it

Clustering groups points that sit close together, with no labels to learn from. Most methods describe each group by a centroid, a point at its center. The basic step is assignment: give each point to its nearest centroid. Nearest needs a distance. Euclidean distance, the square root of the summed squared differences, is the usual one, and k-means is defined with it. Comparing squared distances gives the same winner and skips the square root. Ties need a fixed rule so the result never depends on luck. Here the lower index wins. Vectorized assignment matters in practice: a shop with a million shoppers and 20 segments needs 20 million distances, and NumPy broadcasting computes them in one expression. The same step serves new shoppers after training, to place them in a segment.

pythonCtrl+Enter runs
import numpy as np

def assign_clusters(points, centroids):
"""Index of the nearest centroid for each point.

points: 2-D list or array, shape (n, d)
centroids: 2-D list or array, shape (k, d)
Returns a 1-D int array of length n with values 0 to k - 1, using
Euclidean distance. Ties go to the lower centroid index.
"""
raise NotImplementedError

Stuck? Reveal one rung at a time

Worked solution

Give it a real try first. Then read the solution and why each line is there.