Talip7/scikit-learn-issues-multilabel huggingface dataset:
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:
> planned change of default value for n_init parameter of KMeans to auto will silently worsen results of existing code

It's not silent, it follows a proper deprecation cycle.

> If this change is made as planned this should IMO be communicated very clearly.

Well it's in the changelog. Like any other change of default value it may have an impact on the results. Default values are not chosen to give the best quality in all situations (this is just impossible) nor the best efficiency, but a good tradeoff between those.

The snippet in the linked discussion shows a increase of around 3% on the inertia after the change of default. I think it's more than acceptable for a 10x speed-up. Looks like a good deal to me. The same snippet shows that increasing n_init to 100 would give better results by 1-2%, I don't think it would be a reasonnable argument to change the default to 100 :)

(If it were only me, the default would be 1 for all inits. Doing many inits means tuning the random_state. Doing random inits is just a naive way of trying to end up in a better local minima for a non convex problem. There are others, some better, solutions to achieve this. This is why I don't like doing that by default because most users are not aware of that.)

Labels: module:cluster
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:
Right now the docstring says: 

> Number of times the k-means algorithm is run with different centroid seeds. The final results is the best output of n_init consecutive runs in terms of inertia. Several runs are recommended for sparse high-dimensional problems (see [Clustering sparse data with k-means](https://scikit-learn.org/dev/auto_examples/text/plot_document_clustering.html#kmeans-sparse-high-dim)).

I would make that at least easier for users by saying something like "you might consider a larger `n_init` such as `n_init=10` for high dimensional data, or high dimensional sparse data".

I would also be okay with keeping `n_init` as `10`, and tell users they can get a 10x speedup but probably a less satisfactory result by setting it to 1.

Labels: module:cluster
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:
> the default parameter used in pydaal

I think you refer to daal4py which was more recently renamed to `scikit-learn-intelex`. The benchmark are here:

https://github.com/intel/scikit-learn-intelex#-acceleration

on some datasets, the Intel version is indeed 50x faster than scikit-learn but the benchmark code is using `n_init=1` explicitly:

- https://github.com/IntelPython/scikit-learn_bench/blob/3083ef8743ad220d1e20b8fa5f501256e176ad58/sklearn_bench/kmeans.py#L98

That being said, I am ok with keeping the switch but we should definitely currently in `main` improve the docstring as suggested by @adrinjalali in:

> I would make that at least easier for users by saying something like "you might consider a larger n_init such as n_init=10 for high dimensional data, or high dimensional sparse data".

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)?

Labels: module:cluster
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:
thx for your comments and apologies for the "silently". I was only looking at the dev code before my initial discussion post #25016. I became aware of the long discussion history and the planned deprecation measures only later. I will prepare answers to all your questions a.s.a.p.

Labels: module:cluster
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:
> and tell users they can get a 10x speedup but probably a less satisfactory result by setting it to 1.

To me it would be more interesting to do the opposite from a pedagogical point of view. That is defaulting to one and explain that the problem is non-convex so it'll end up in a local minima and one of the possible ways to find a better minima and thus improve the SSE could be to do random inits, at the cost of a substantial slow down. Imo it makes the discussion more interesting and focused around the optimization problem rather than just a matter of speed.

Labels: module:cluster
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:
As discussed irl with @ogrisel and @glemaitre, I think we can remove the blocker tag to not hold the release more. It's probably more a matter of documentation and we can still roll back, if discussions end up that way, between the release candidate and the finale release.

Labels: module:cluster
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:
@glemaitre wrote
> @gittar I am wondering if you encounter other situations where a single initialization with `"kmeans++"` would go sideways.

Definitely. In my experience this is much more often the case than not. The [3x3 cluster example from the docs](https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_stability_low_dim_dense.html) is special in the sense that the number of clusters (9) is very small and known (which is usually not the case). This gives k-means++ an unusually good chance to get it "right", i.e. put one center in each cluster. Once this is achieved, the solution is saturated and cannot get any better, so no more trials are needed.

Slightly modifying this example gives a diffent picture. If we chose 4x4 clusters and set the parameter `n_clusters` twice as high as the actual number of clusters in the data., k-means++ will get it right only with a very small probabilty. Here additional trials can be expected to improve the mean solution. (see https://github.com/gittar/skl-discussion/blob/main/n-init.ipynb)

IMO the probability of k-means++ to find a very good (low SSE) solution
* decreases with the number of clusters in the data
* decreases if the $k$ is larger than the number of clusters in the data, e.g., if $k$ is 2 times as large as the number of clusters, so that for same-sized clusters there should be 2 centroids per cluster.

For detailed simulation results (comparing greedy $k$-means++ with 1 and 10 trials and vanilla $k$-means++ with 10 trials on 45 different $k$-means problems) please see my draft paper (sent via email).

Labels: module:cluster
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:
@jeremiedbb wrote:
> (If it were only me, the default would be 1 for all inits. Doing many inits means tuning the random_state. Doing random inits is just a naive way of trying to end up in a better local minima for a non convex problem. There are others, some better, solutions to achieve this. This is why I don't like doing that by default because most users are not aware of that.)

This is also a valid point. Each randomized algorithm can be "improved" by running it several times and picking the best result. Whether this makes a lot of sense depends on the variation in the results. If the variation is high, so is the expected payoff in doing several trials and vice versa.

Any particular default number of trials (like 10 or 3) is quite arbitrary, however, and may not be noted by users of the algorithm giving them a wrong impression of the efficiency and quality of the algorithm.

Therefore, from a principled point of view, one could -- as @jeremiedbb suggests -- always set `n_init=1` and give the general hint that for all randomized algorithms performing several trials may improve the result at the cost of increased computation.

In this context I looked at other ocurrences of `n_init` and found `n_init=10` for `sklearn.cluster.SpectralClustering` and `sklearn.cluster.SpectralCoclustering` and `sklearn.cluster.SpectralBiclustering` for the use with `KMeans` and without deprecation note. Outside `sklearn.cluster` I saw `n_init=8` for `sklearn.manifold.smacof`and `n_init=4` for `sklearn.manifold.MDS`. The same arguments might apply here as for `KMeans`.

Labels: module:cluster
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:
> In this context I looked at other ocurrences of n_init and found n_init=10 for sklearn.cluster.SpectralClustering and sklearn.cluster.SpectralCoclustering and sklearn.cluster.SpectralBiclustering for the use with KMeans and without deprecation note

There's no deprecation note because the default will not change for these estimators. It makes me think that we should maybe do the change of default to match the default of KMeans.

Labels: module:cluster
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:
> Therefore, from a principled point of view, one could -- as @jeremiedbb suggests -- always set `n_init=1` and give the general hint that for all randomized algorithms performing several trials may improve the result at the cost of increased computation.
> 

I do like this idea in a pure sense.

> > and tell users they can get a 10x speedup but probably a less satisfactory result by setting it to 1.
> 
> To me it would be more interesting to do the opposite from a pedagogical point of view. That is defaulting to one and explain that the problem is non-convex so it'll end up in a local minima and one of the possible ways to find a better minima and thus improve the SSE could be to do random inits, at the cost of a substantial slow down. Imo it makes the discussion more interesting and focused around the optimization problem rather than just a matter of speed.

💯 

I think it makes much more sense to frame it as such, especially since this can be done equivalently via random seed perturbations.

Labels: module:cluster
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:
So it seems that we went forward with the deprecation cycle. Not sure to recall what was the issue. Closing.

Labels: module:cluster