IMHO, there is two important things to be done for you current PR:

• write the unit tests right now;
• make some benchmarks such that we can compare with [WIP] k-means|| initialization for k-means #5530.

• for just testing take test_script.py from my repo and paste it in sckit-learn folder after generating binaries
• for plot it is enough to clone my repo and run sample_plot.py (for plot) requirements before running plot:numpy and matplotlib

You might want to avoid making code outside of scikit-learn since the core developers will have limited time to play with it. More importantly, plots and other results from those scripts can be posted directly inside the PR. It will greatly ease the follow-up of the PR.

Sure.Thanks a lot @glemaitre .

For easy follow up the algorithm:

This is a small benchmark test for an artificial data set. Basically the same one as the one in previous pr.

X, y = datasets.make_blobs(n_samples=10000,
                           n_features=20,
                           centers=15,
                           cluster_std=1)

OBSERVATIONS:

• Time taken to calculate centres increases with increase in sampling factor. So this happens because when we calculate D(x,c) in each step of the main for-loop (Step-3) candidate centres increases. we need to make the process of calculating distance of point from candidate_centres parallel. Which can be easily done as each point selects independently from a set of candidates.
• For step-5 we have to run (# n_clusters) for loops in parallel.

Code for plot is in this (gist)
The values for inertia and exact values for time taken are in this html document (an image of my ipynb): (doc).
I can post the plot image but inertia values can clearly show accuracy of initialisation so I refrained.

Hi, Could you re-post with clearer labelled plots. Which one is kmeans (master) and which one is the kmeans++? Also a bigger plot please...

And did you try kmeans (current implementation) with n_jobs... The speed gains seem really weird... Is this PR's implementation 100x better than current ?!

@raghavrv Thanks for taking a look at this. For clarity these are my benchmarks results in a tabular format-
I have compared the current k-means with k-means++ initialisation Vs k-means with my k-means||
initialisation.
sampling_factor - number of candidate centres chosen at one pass

These graphs say the moment I over sample (take extra candidate centres ) time taken shoots up.
Essentially I feel this can be controlled by parallelizing this implementation.

I will post proper graphs shortly. Thanks. : )

So the kmeans|| is quite slow and the benchmarks are as expected from the conclusions of #5530 or am I missing something?

If that is the case, I think it would be wise to not expend energy on it then.. (Please feel free to let me know if there is something I'm missing that would make addition of kmeans|| useful)

I would like to suggest that this is just a sequential implementation. I am sure making it parallel would reduce the time taken. This pr was put to actually show implementation of the algorithm and that it works although slow.

I started to work on it because I once wrote a search handler that had some very long code, I made it into functions, made it work async. This made search handler very fast. I am not sure how fast this can go but given a chance I would like to work on it.

I was just suggesting...

Please feel free to pursue further if you believe time and effort spent on it would yield a benefit to you (in terms of your PR getting merged) and to the community (in terms of the PR being significantly faster for significant use cases)...

I would like to suggest that this is just a sequential implementation. I am sure making it parallel would reduce the time taken

Also this PR is not cythonized while the one you are comparing to is... So cythonizing your implementation could also speed up maybe...

Thanks a lot @raghavrv .

I would like to add it as my GSOC proposal.Is it possible?

I guess it would not be worth it . Anyways learnt a lot. Thanks a lot for all the reviews. @glemaitre , @raghavrv , @jmschrei .