Start learning free

LESSON 80 OF 165 · MACHINE LEARNING: ML INTERVIEW QUESTIONS

k-means from Scratch in Python

Practice

An interviewer asks: "Implement k-means with numpy only." The idea in one sentence: start from k centers, give every point to its nearest center, move each center to the mean of its points, and repeat until nothing changes.

The starting code gives you 9 points, 3 starting centers and distances(points, centers), which gives back a table with one row per point and one column per center. Four numpy tools do the rest. .argmin(axis=1) gives back, for each row, the position of its smallest number. points[labels == j] keeps only the rows whose label is j. .mean(axis=0) gives back the mean of each column. (a != b).any() gives back True when at least one number differs.

d = np.array([[4.0, 1.0], [0.5, 3.0], [2.0, 6.0]])
print(d.argmin(axis=1))            # [1 0 0]

pts = np.array([[0, 0], [4, 2], [2, 2]])
lab = np.array([1, 0, 1])
print(pts[lab == 1].mean(axis=0))  # [1. 1.]

Each round of the loop makes two moves: label every point with its nearest center, then put each center at the mean of its group. When a round moves no center, the loop stops. On this lesson's points the script must print:

Labels: [0 0 0 2 2 2 1 1 1]
Centers:
[[1.67 2.  ]
 [2.   8.33]
 [8.67 8.  ]]
Rounds until nothing changed: 3
Same groups as scikit-learn's KMeans on 60 random points: True

Your task: fill in mean_of_groups so each row of result is the mean of one group. Then write the while loop of kmeans: the labels from the nearest center, the new centers from the group means, a stop rule with .any(), and the move to the new centers. The last two lines of the expected output are printed by a check that runs after your script, so do not print them. The check counts rounds by counting calls to distances, so call it once per round. It also calls kmeans on its own points, so do not change what kmeans takes and returns.


Assignment
Follow the Coding Tutorial to write the group means and the k-means loop, one line at a time.


Hint
changed starts as True, so the first round always runs. In the finished loop the order is: labels, new centers, the stop rule, then centers = new_centers. The script runs only once all seven lines are in.


STEP 1 OF 7
    Ctrl + Enter to check

    Mlq Kmeans in Python

    Keep going with Python1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free