Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

k-means in high dimensional spaces

English · فارسی

k-means in high dimensional spaces

Computer Science Dept, Ferdowsi University of Mashhad

Source
<Figure size 640x480 with 1 Axes>
<Figure size 640x480 with 1 Axes>

Exercises

  1. Take KK centroids on a grid in [0,1]d[0,1]^d and compute the expected squared distance from a uniform point to its nearest centroid, for d=1,…,20d=1,\dots,20 with K=10K=10. Explain the growth.

  2. Argue that a partition into KK convex cells can separate at most KK regions, while covering the cube at a fixed resolution needs roughly KdK^d cells. What does that say about a fixed KK as dd grows?

  3. Run k-means with the same KK and increasing dd on synthetic data with a fixed number of true clusters. Plot the inertia and the ARI against dd and interpret the two curves.