Reconsider the change for `n_init` in `KMeans` and `MiniBatchKMeans`

I open this PR to reconsider the changes introduced in #23038.

We decided to use a single initialization when using `init="kmeans++`. In the original issue (#9729), it seems that we based our choice on two aspects:

1. the default parameter used in `pydaal`
2. the benchmark of the following examples: https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_stability_low_dim_dense.html

While 1. is not an absolute ground truth, we might have overlooked some aspects in 2. Indeed, the example from https://github.com/scikit-learn/scikit-learn/discussions/25016 illustrates a decrease in statistical performance. In this latest benchmark, the data do not have an underlying structure and limiting the number of initialization is detrimental in this case.

We should reconsider because it could be quite surprising behaviour.

Possible resolutions are:

- keep the behaviour implemented in `main`
- revert to `n_init=10` for both `init="random"` and `init="kmeans++"`
- change `n_init` from 1 to 5 when `init="kmeans++"`

@gittar I am wondering if you encounter other situations where a single initialization with `"kmeans++"` would go sideways.

COMMENT:
@ogrisel wrote:
> Also a question for @gittar: we don't really care about 2%-3% of SSE on purely random data since this would probably not lead to a meaningful improvement in expectation (on held-out evaluation data). Could you re-try similar experiments on a semi-structured dataset (e.g. wide blob-ish clusters + uniform noise background) with a random train-test split and evaluate the impact of `n_init` on the SSE measured on the test data for the clusters returned by k-means++ for different `n_init` values (e.g. 1 vs 10 or 5 vs 10)?

Is the structured example in https://github.com/gittar/skl-discussion/blob/main/n-init.ipynb any helpful? Regarding statements like "2%-3% of SSE are not of interest (on random data)" or as @jeremiedb stated "an increase of 3% is a good deal if one gets a 10x speedup" I would say: This is typically what you get from multiple runs of k-means++. The total cost is obviously proportional to the number of runs. The maximum gain in SSE is limited by the expected distance of a single k-means++ run from the (usually unknown) optimal solution. Since k-means++ is quite good, this distance is often below 10% IMO.

IMO it is the user who has to decide whether the gain is worth the cost. And instead of repeating k-means++ it might be more economical to use other methods which get to better solutions at lower costs. (ad for "breathing k-means" deleted :-) )

Regarding the original question (Should the default of `n_init` be changed to 1?) I see the following reasons not to do it:

* by having the default at 10 for many years you have set a de-facto standard equally to using the greedy variant of k-means++. Scitkit learn's `KMeans` class is IMO the most used k-means implementation by far and calling it with default parameters is likely built into many GUI-driven applications and integrated in automated processing pipelines. Changing the default - even with advance deprecation warnings on stderr - might go unnoticed in many productive systems and suddenly worsen the `KMeans` results.
* regarding speed comparison with other systems like `scikit-learn-intelex`: if they claim a 50x speedup but do not consider that `scikit-learn` does 10 initializations per call, that is - probably just due to sloppiness - a false claim by an order of magnitude. The speedup is only 5x, of course. Such statistics should also compare the quality of results, this would make it easier to double-check the respective claims. But the problem here is IMO not the default value of 10, but rather the inexact reporting of results.

Regarding the question for experiments with held-out test data: I never considered doing this since in my understanding the $k$-means problem is defined wrt. a single and completely known given data set and the stated goal is to minimize the SSE for that data set using a specific number $k$ of centroids. I would expect performance on data subsets always to be  highly correlated as long as they are sampled iid from the same distribution.

Please see my draft paper (sent via email) for relevant empirical results.

Labels: module:cluster