Monte Carlo simulation uses randomization while accepting a controlled possibility of an incorrect or variable result in exchange for bounded resource usage. Unlike deterministic execution, repeated runs on identical input can produce different outcomes. section 4.12
A practical Monte Carlo workflow makes randomness explicit and limits its consequences:
- Choose a randomized starting state, such as initial centroids sampled from the input with added random noise. section 12.2
- Run the deterministic core procedure, repeatedly classifying points and updating centroids until assignments stabilize or a maximum iteration count is reached. section 12.2
- Repeat the algorithm with different random starts and compare the results when initialization can strongly affect quality. section 12.2
K-means with random restarts
K-means qualifies as a Monte Carlo randomized algorithm because its first step randomly initializes centroids. The later distance calculations and centroid updates are deterministic, but a poor initialization can slow convergence, remove an unused centroid, or produce a poor clustering before the iteration limit. Running k-means several times with different initializations and selecting the best clustering reduces this risk. section 12.2
Figure 12.3 An example of the k-means algorithm with k==3. Dataset points are initially lightly shaded. Step 1: k centroids (shaped as pentagons) are randomly created. Each centroid is assigned a different color: RGB. Step 2: For each point, measure the distance to all centroids, and assign the point to the closest one. At the end, each centroid C will define a cluster, a sphere centered at C and whose radius is the distance to the furthest point assigned to C. The clusters are highlighted in the same color as their centroids. Step 3: Update the centroids: for each cluster, compute its center of mass. Step 4: Repeat steps 2 and 3 j times. Some points will switch to a different cluster.
Visualizes random centroid creation, point assignment, centroid updates, and repeated k-means iterations. section 12.2
