Finding the K in K-Means Clustering

Abstraction: Gap statistic method to determine optimal cluster count in k-means

Key points:

• Elbow method graphs variance explained vs K but the "elbow" is often ambiguous in practice
• Gap statistic (Tibshirani, Walther, Hastie — Stanford 2001) compares log(W_k) against a null uniform reference distribution
• Reference datasets sampled uniformly from the bounding box of original data using B=10 Monte Carlo replicates
• Optimal K is the smallest k satisfying: gap(k) >= gap(k+1) - s_{k+1}, where s accounts for simulation error
• Python implementation with gap_statistic() and Wk() functions spans k=1 to 9
• Method correctly identifies K for Gaussian clusters, single centroid, and uniform non-clustered distributions

Connections: Stanford · Clustering · K Means · Unsupervised Learning

Source: https://datasciencelab.wordpress.com/2013/12/27/finding-the-k-in-k-means-clustering/