k-means on 60 points: assign, move, repeat
Real k-means libraries pick random or smarter starting centroids. Fixed starting points keep this example identical in all three languages.
IVF (inverted file) groups the vectors into clusters with k-means, then answers a question by searching only the few clusters whose centres are closest to it. The number of clusters (nlist) and the number searched (nprobe) set the speed against recall.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 6 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Write assign(points, centroids) for 2-D points that returns each point's nearest centroid index using squared distance, with ties going to the lower index. Print the labels for the points (0, 0), (1, 1), (5, 5), (6, 5), (2.5, 2.5) and centroids (0, 0), (5, 5). The last point is exactly in the middle.
Write scan_cost(list_sizes, probe_order, nprobe) returning the distances an IVF search computes: one per centroid plus every vector in the first nprobe lists of probe_order. For list sizes [10, 20, 30, 40] and probe order [2, 0, 3, 1], print the cost for nprobe 1 to 4 next to the exact-search cost. What do you notice at nprobe 4?
Explain it without notes
Describe how an IVF index is built and how it answers a question.
What do nlist and nprobe control, and what happens to speed and recall as you raise each?
Why can IVF miss a true nearest neighbour? Give the example from this topic.
Compute the number of distances a search needs for nlist = 100, 100,000 vectors in equal lists and nprobe = 5. Compare with exact search.
Expected output
step 1: cluster sizes [4, 35, 6, 15], total squared distance to centroids 6.326
step 2: cluster sizes [14, 20, 7, 19], total squared distance to centroids 3.849
step 3: cluster sizes [18, 11, 9, 22], total squared distance to centroids 2.973
step 4: cluster sizes [17, 9, 11, 23], total squared distance to centroids 2.649
step 5: cluster sizes [18, 8, 11, 23], total squared distance to centroids 2.574
centroid 0: (0.197, 0.352)
centroid 1: (0.582, 0.095)
centroid 2: (0.270, 0.803)
centroid 3: (0.769, 0.616)