K-means assignment and update

ImplementMedium25 min13 checks

clustering k-means unsupervised-learning vectorization

Lesson: Unsupervised Learning Cheat sheet Track: Classical ML

K-means groups points into k clusters. It repeats two steps. The assignment step sends each point to its nearest centroid. The update step moves each centroid to the mean of its points. The run stops when no point changes its cluster.

Task

Write three functions.

assign(X, centroids) returns the index of the nearest centroid for each point, by squared Euclidean distance.
update(X, assignments, centroids) returns the new centroids. Centroid $inline$ is the mean of the points with assignment $inline$ .
kmeans(X, init_centroids, max_iterations=100) runs the two steps from the given centroids and returns (centroids, assignments, iterations).

Use these rules.

Tie rule: when two or more centroids are at the same distance from a point, the point goes to the lowest index.
Empty cluster rule: when no point has assignment $inline$ , centroid $inline$ keeps its old value.

kmeans does these steps.

Compute the assignments for the initial centroids.
Repeat for $inline$ max_iterations:

- Update the centroids with the current assignments.

- Compute the new assignments for the new centroids.

- When the new assignments are equal to the old ones, stop and return the new centroids, the assignments and $inline$ .

When no stop occurs, return the centroids and assignments of the last pass and max_iterations.

Input and output

Name	Type	Shape	Meaning
`X`	float array	`(n, d)`	one point in each row
`centroids`	float array	`(k, d)`	one centroid in each row
`assignments`	int array	`(n,)`	the cluster of each point, from `0` to `k - 1`
`init_centroids`	float array	`(k, d)`	the start centroids for `kmeans`
`max_iterations`	int	scalar	the largest number of update steps

assign returns an int array of shape (n,).
update returns a new float array of shape (k, d).
kmeans returns a float array of shape (k, d), an int array of shape (n,) and an int.

Constraints

1 <= n <= 2000, 1 <= k <= 20 and 1 <= d <= 20.
Do not change the input arrays.
Use numpy only. Do not use random numbers. The start centroids are given.

Examples

pythonX = np.array([[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [5.0, 5.0], [6.0, 5.0], [5.0, 6.0]])
C = np.array([[0.0, 0.0], [1.0, 1.0]])
assign(X, C)

text[0 0 0 1 1 1]

The points [1, 0] and [0, 1] are at the same distance from both centroids. The tie rule sends them to cluster 0.

pythonupdate(X, np.array([0, 0, 0, 1, 1, 1]), C)

text[[0.33333333 0.33333333]
 [5.33333333 5.33333333]]

pythonX = np.array([[0.0], [1.0], [2.0], [10.0], [11.0], [12.0], [20.0]])
kmeans(X, np.array([[0.0], [1.0], [2.0]]))

text(array([[ 0.  ],
       [ 1.5 ],
       [13.25]]), array([0, 1, 1, 2, 2, 2, 2]), 2)

Hints

4 hints

Solution and notes

Locked

Pass every check with Submit to open the reference solution and the notes.

Run it on your computer

Clone the repository, install numpy and run the same checks in a terminal:

python3 scripts/practice/run.py kmeans-step my_answer.py
python3 scripts/practice/run.py kmeans-step my_answer.py --examples

Start my_answer.py from starter.py.

Your code is saved in this browser as you type. On a phone you can read and edit the code, but the checks are easier to use on a desktop.

Keyboard shortcuts

Ctrl Enter: Run the examples
Ctrl Shift Enter: Submit
Tab / Shift Tab: Indent or outdent the lines
Esc then Tab: Move the focus out of the editor
Alt H: Show the next hint

On a Mac, use Cmd in place of Ctrl.

Select Run to check the examples, or Submit to run every check.

Problem