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.

Practical Issues: Starting Values and Choosing K

English · فارسی

Practical Issues: Starting Values and Choosing KK

Computer Science Dept, Ferdowsi University of Mashhad

Where this page sits

Section 14.3.11 of Hastie et al. (2009) (pp. 518-520) collects the two questions that K-means and K-medoids cannot answer for themselves:

  1. where to start, i.e. the initial set of centres {m1,…,mK}\{m_1,\dots,m_K\} or indices {i1,…,iK}\{i_1,\dots,i_K\};

  2. how many clusters, when KK is not given by the problem.

The first is a local-minimum question, familiar from the families page. The second is deeper, because the obvious tool - cross-validation - does not work here, and the book is unusually explicit about why. What replaces it is a heuristic (the kink) and its automation (the Gap statistic).

The clustering validation page covers the rest of the toolbox: purity and the other external measures, and the silhouette, which answers the same question from inside a single clustering.

What you should be able to do at the end

  • describe forward stepwise initialisation and say what it buys over random starts;

  • explain why cross-validation cannot select KK for clustering;

  • derive the Gap statistic from the kink idea and state the rule (14.39);

  • read a Gap plot, including the error bars.

1. Starting values

The book lists a range of practice, from “simple random selection” to a deliberate forward stepwise strategy: choose the first centre, then the second to minimise the criterion given the first, then the third given the first two, and so on. Each step is a search over the observations, so the whole thing costs KK passes over the data, and it tends to spread the centres out - a new centre is only chosen if it improves the fit, and a point inside an existing cluster improves very little.

The experiment below compares the two strategies on data where it matters: three groups that are close enough that some starts converge into the wrong configuration.

random starts (50 runs): best    320.8  median    323.7  worst    380.6
runs above the median  : 25 of 50
forward stepwise       :    325.3

The forward stepwise start lands within a few units of the best value the fifty random starts found, and far from the worst, in a single attempt. On well-separated data every strategy gives the same answer and none of this matters; the distance between best and worst above is the cost of not choosing.

2. Choosing KK: the kink, and why cross-validation fails

The data-based approach is to compute the within-cluster dissimilarity WKW_K for K=1,2,…,Kmax⁡K = 1, 2, \dots, K_{\max} and look at the curve. It always decreases. The reason is not that more clusters fit better in a statistical sense, and the book is precise: even on an independent test set the criterion decreases, because “a large number of cluster centers will tend to fill the feature space densely and thus will be close to all data points”. There is no test-set penalty to pay, so the usual machine-learning remedy of holding data out does not select KK at all. The cell below shows it happening.

 K     W_K on the held-out data
 1                      321.9
 2                      177.6
 3                      124.8
 4                       85.9
 5                       69.9
 6                       61.3
 7                       57.0
 8                       44.9

Monotone decreasing from top to bottom, so the minimum is always K=Kmax⁡K = K_{\max}. Clustering is not prediction: there is nothing to predict, and no held-out error to pay for overfitting.

What the book uses instead is the shape of the curve. If the data really contain Kˉ\bar K groups, then for K<KˉK < \bar K the algorithm must merge groups that are far apart, and each extra cluster reduces WW a lot; for K>KˉK > \bar K the extra cluster splits a group that is already tight, and the reduction is small. So the successive differences WK−WK+1W_K - W_{K+1} drop sharply at Kˉ\bar K, which is the “kink” - and it is a heuristic. The tumour example is the honest counterexample: the curve there has no kink at all, and the book chooses K=3K = 3 for illustration.

3. The Gap statistic

The Gap statistic replaces the visual kink with a reference curve. For each KK compare the observed log⁡WK\log W_K with the value expected if the data had no clusters at all, obtained by sampling uniform data over the box that contains the data:

G(K)=1B∑b=1Blog⁡WK(b)−log⁡WK,G(K) = \frac{1}{B}\sum_{b=1}^{B} \log W_K^{(b)} - \log W_K ,

where WK(b)W_K^{(b)} is computed on the bb-th uniform sample. If the data are one blob, the two curves are close and G(K)G(K) stays near zero. If there are Kˉ\bar K groups, the observed curve falls faster than the reference up to Kˉ\bar K and then runs parallel to it, so the gap peaks and then flattens.

The error bar accounts for the simulation, with sKs_K the standard deviation of log⁡WK\log W_K over the BB samples:

sK′=sK1+1/B,K^=arg⁡min⁡{K:G(K)≥G(K+1)−sK+1′}.(14.39)s'_K = s_K \sqrt{1 + 1/B}, \qquad \hat K = \arg\min \left\{ K : G(K) \ge G(K+1) - s'_{K+1} \right\}. \qquad \text{(14.39)}

The rule is not “take the maximum”: it takes the smallest KK whose gap is within one error bar of the next one, which is the formal version of “stop when the curve flattens”. And it works when the data have a single cluster - then K^=1\hat K = 1 - which is the case where the kink method has nothing to point at.

K = 1:  gap = -0.506   error bar = 0.083
K = 2:  gap = -0.385   error bar = 0.083
K = 3:  gap =  3.028   error bar = 0.078
K = 4:  gap =  2.865   error bar = 0.053
K = 5:  gap =  2.795   error bar = 0.069
K = 6:  gap =  2.782   error bar = 0.079
K = 7:  gap =  2.802   error bar = 0.073
K = 8:  gap =  2.833   error bar = 0.058

Gap estimate of K: 3

The printed estimate is the smallest KK whose gap is within one error bar of the following gap, and here it is the number of groups the data were built from. Note the shape. For K=1K = 1 and K=2K = 2 the gap is negative: the observed data are three tight groups spread over a large box, while the reference is one diffuse blob, so one or two centres describe the reference better than they describe the data. At K=3K = 3 the observed curve collapses and the gap jumps by more than three units - the kink, measured against a reference instead of guessed by eye. After that the two curves run parallel and the gap is flat.

<Figure size 1100x400 with 2 Axes>

4. What to report

Neither criterion is a test. Both are heuristics that answer “how many groups would a reasonable person see in this picture”, and the honest way to use them is:

  • report the whole WKW_K curve, not only the chosen KK;

  • say which rule chose KK - the problem (a company with KK sales people), the kink, the Gap statistic, or a validation measure;

  • check stability: recluster bootstrap samples and see whether the same groups come back;

  • remember that the number of starts and the number of clusters are both part of the answer, as the first section shows.

Summary

  • Initialisation is a choice: random starts need repetition, forward stepwise chooses centres one at a time to minimise the criterion and usually lands near the best solution found by many random starts.

  • WKW_K decreases monotonically even on held-out data, because centres fill the feature space; cross-validation therefore cannot select KK.

  • The kink in WKW_K, or in log⁡WK\log W_K, is the heuristic answer, and it can be absent - as in the tumour example.

  • The Gap statistic compares log⁡WK\log W_K with a uniform reference, and (14.39) picks the smallest KK within one error bar of the next; it also returns one cluster when that is the right answer.

  • Whatever rule you use, report the curve and the rule.

Exercises

  1. Run 200 random starts on the data of Section 1 and plot the histogram of final values. How many distinct local minima are there?

  2. Implement the kink rule as code: the first KK where WK−WK+1W_K - W_{K+1} falls below a fraction of the previous difference. How sensitive is the answer to that fraction?

  3. Apply the Gap statistic to the data of the tumour example (or to 64 points drawn from three overlapping Gaussians) and see whether it finds a kink that the curve does not show.

  4. Repeat the Gap computation with B=5B = 5 and B=100B = 100. What happens to the error bars, and to K^\hat K?

  5. Show by simulation that the Gap statistic returns K^=1\hat K = 1 for data from a single Gaussian, and that the kink rule does not.

  6. Forward stepwise chooses centres to minimise WW; K-means++ samples them with probability proportional to the squared distance to the nearest chosen centre. Compare the two on 100 starts.

Sources

  • Forward stepwise initialisation, the argument against cross-validation, the kink, the Gap statistic, (14.39) and Figure 14.11: §14.3.11 of Hastie et al. (2009), pp. 518-520; the Gap statistic is Tibshirani, Walther and Hastie (2001), cited there.

  • The absent kink on real data: Tumor-Microarray-Example and ESL Figure 14.8.

  • Other ways to judge a clustering - purity, Rand, Jaccard, silhouette: Clustering-Validation-Metrics.

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7