I modified the kmeans init to match the apparent serial dependency in center choices as described in http://en.wikipedia.org/wiki/K-means%2B%2B
The change was simple, and it now passes the test_KMeans2_sphere5_bad_inits.py test, even with higher trial counts. (this used to fail intermittently)
Assuming that means "it's better"...but still want to do more testing.

Yes, the serialization means there's a higher init cost for large k? But the init was doing 5 interations of sampling k * 3 centers and collapsing them down to k, and not counting those in the reported iterations.

Also: if you can't guarantee good results in a single kmeans, the user is forced to do 5-10 trys, looking to make sure he got "best"...which is why my test was failing. We didn't get a high percentage of "best" result with a single try.

Here, I changed Sampler, to ask for 1 new center each time, rather than k * 3. I left it the code where it does a kmeans to "collapse". The # of iterations for the init is no longer = 5, but set to k..i.e. one new center is added each time. The new center is apparently randomly chosen with the algorithm of weighted probability using D(x)**2 from the current nearest center. ..but I didn't examine that. Assumed that's what the init must have been trying to do (the comment says so)

I ran a handle of KMeans tests and they all passed. I will run my 26GB dataset after I push

With closer examination, the kmeans "collapsing" during the init is probably unnecessary. But I'm thinking it's more important at this point to get "best" answer, rather than worry about

Papers do say that iterations on kmeans are non-linear with respect to rows (upper bound). So I don't think it's bad doing 1 doAll per cluster center init. And our default init is KMeans++, so we can assume that's the typical use (So I'm not worried about slowing down the random init case (which we don't support any more? just Furthest)

Someone should probably review/improve. There's only two lines that changed. I left the old lines in as comments with // kbn. prefix.
I ran build.sh which passed the Junit tests.