K-Means Assignment Step
K-Means Assignment Step
K-Means clustering alternates between two steps: assigning points to clusters and updating centroids. The assignment step assigns each data point to the nearest centroid based on squared Euclidean distance.
Given a list of data points and a list of current centroid positions, assign each point to the nearest centroid.
Formula
For each point p, find the centroid c that minimizes the squared Euclidean distance:
assignment(p)=argjmind=1∑D(pd−cj,d)2Examples
Input:
points = [[1, 1], [1, 2], [10, 10], [10, 11]], centroids = [[0, 0], [11, 11]]
Output:
[0, 0, 1, 1]
Points [1,1] and [1,2] are closer to centroid [0,0]. Points [10,10] and [10,11] are closer to centroid [11,11].
Input:
points = [[0, 0], [5, 5], [10, 0]], centroids = [[0, 0], [5, 5], [10, 0]]
Output:
[0, 1, 2]
Each point is exactly at one of the centroids, so each is assigned to that centroid.
Hint 1
For each point, loop over all centroids. Compute the squared distance as sum((p[d] - c[d])**2 for d in range(D)). Track the index of the centroid with the smallest distance.
Hint 2
Initialize best_dist = float('inf') and best_idx = 0 for each point. Use strict less-than (<) when comparing distances so that ties are broken by the first (smallest index) centroid.
Requirements
- For each point, compute the squared Euclidean distance to every centroid
- Assign the point to the centroid with the smallest distance
- If distances are tied, assign to the centroid with the smallest index
- Return a list of integer cluster indices
Constraints
- All points and centroids have the same dimensionality
- At least one point and one centroid
- Return a list of integers with the same length as points
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
K-Means Assignment Step
K-Means Assignment Step
K-Means clustering alternates between two steps: assigning points to clusters and updating centroids. The assignment step assigns each data point to the nearest centroid based on squared Euclidean distance.
Given a list of data points and a list of current centroid positions, assign each point to the nearest centroid.
Formula
For each point p, find the centroid c that minimizes the squared Euclidean distance:
assignment(p)=argjmind=1∑D(pd−cj,d)2Examples
Input:
points = [[1, 1], [1, 2], [10, 10], [10, 11]], centroids = [[0, 0], [11, 11]]
Output:
[0, 0, 1, 1]
Points [1,1] and [1,2] are closer to centroid [0,0]. Points [10,10] and [10,11] are closer to centroid [11,11].
Input:
points = [[0, 0], [5, 5], [10, 0]], centroids = [[0, 0], [5, 5], [10, 0]]
Output:
[0, 1, 2]
Each point is exactly at one of the centroids, so each is assigned to that centroid.
Hint 1
For each point, loop over all centroids. Compute the squared distance as sum((p[d] - c[d])**2 for d in range(D)). Track the index of the centroid with the smallest distance.
Hint 2
Initialize best_dist = float('inf') and best_idx = 0 for each point. Use strict less-than (<) when comparing distances so that ties are broken by the first (smallest index) centroid.
Requirements
- For each point, compute the squared Euclidean distance to every centroid
- Assign the point to the centroid with the smallest distance
- If distances are tied, assign to the centroid with the smallest index
- Return a list of integer cluster indices
Constraints
- All points and centroids have the same dimensionality
- At least one point and one centroid
- Return a list of integers with the same length as points
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array