Change KMeans n_init default value to 1.

[amueller]

As mentioned in #9430, pydaal gets a speedup of 30x, mostly because they ignore n_init.
I feel like n_init=10 is a pretty odd choice. We don't really do random restarts anywhere else by default (afaik), and in the age of large datasets this is really pretty expensive.

Not sure if it's worth a deprecation cycle but this is pretty non-obvious behavior that potentially makes us look bad.

[jnothman]

Yes, let's change it. Or default to have an inverse relationship with dataset size.

…

On 12 September 2017 at 00:55, Andreas Mueller ***@***.***> wrote: As mentioned in #9430 <#9430>, pydaal gets a speedup of 30x, mostly because they ignore n_init. I feel like n_init=10 is a pretty odd choice. We don't really do random restarts anywhere else by default (afaik), and in the age of large datasets this is really pretty expensive. Not sure if it's worth a deprecation cycle but this is pretty non-obvious behavior that potentially makes us look bad. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#9729>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEz6zVQKD2vCDZr95LKaUQ7JLHwS6vUks5shUnagaJpZM4PTSrW> .

[amueller]

Standard deprecation cycle then?

[murielgrobler]

I created the warning for the future deprecation. Thanks for all the guidance at Scipy2018!

[amueller]

@murielgrobler Thanks!

[GaelVaroquaux]

I am -1for this. A single init by default for kmeans will not get good results.

We could revisit our init strategy to do only a partial converge. We could also change it to 5 by default. But I think that it is bad practice to race for speed at the detriment of quality of results.

[GaelVaroquaux]

@jeremiedbb is working on speeding up kmeans, and will gain some speed soon hopefully.

[amueller]

Why 5 though? That seems pretty arbitrary. And I think the gains with kmeans++ are very small. We don't to random restarts on any other non-convex optimization, right? It seems pretty inconsistent.

Also, it's not necessarily speed I'm optimizing for, it's user surprise.

[amueller]

oh, sorry 10, not 5. Why 10? ;)

[ni3-k]

Can I work on it?

[murielgrobler]

Yes, sure - thanks!

…

On Fri, Oct 5, 2018 at 2:26 PM Nitin Kshatriya ***@***.***> wrote: Can I work on it? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#9729 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AMspLSm1o09TYy8izexOtvd5otjEeEA2ks5uh7JNgaJpZM4PTSrW> .

[amueller]

I don't think there's a consensus on what to do, though.

[GaelVaroquaux]

I don't think there's a consensus on what to do, though.

I am willing to reconsider my opinion if what we are doing is significantly different from what other packages are doing.

[jeremiedbb]

I've always found the default n_init=10 really weird. What it does is run 10 KMeans with different random_states and pick the best. This is like a grid search (no cv) on the random_state.

I think the n_init parameter is often overlooked and I agree that most probably don't even know they are running KMeans 10 times and think it's pretty slow. It's also not consistent with our other clustering estimators as others already said. If I were to do it, I'd set the default to 1 but better document that kmeans is sensitive to randomness and what to do to about that.

In addition, the default init is "k-means++", which doesn't require as many runs as with "random" inits to get as good or even better clusterings.

[GaelVaroquaux]

This is like a grid search (no cv) on the random_state.

With non convex models this makes sense.

[jeremiedbb]

With non convex models this makes sense.

It does, but it's only one way to try to find a better local minimum. There are many other techniques. This one in particular is really not efficient since it does the whole optimization for each seed. More subtle strategies would for instance start the optimisation scheme and do some random restarts on "bad clusters".

Imo, This default is currently forcing the users to use the really naive search for a better minimum.

[thomasjpfan]

In the example: Empirical evaluation of the impact of k-means initialization, it does show that n_init > 1 leads to an improvement for init="random". For k-means++, n_init does not make a difference. If we go by the example, then we can have a n_init="auto", where: n_init=1 for kmeans++ and n_init=10 for random.

[GaelVaroquaux]

n_init="auto", where: n_init=1 for kmeans++ and n_init=10 for random.

Sounds like a good idea.