kmeans2 '++' method is orders of magnitude slower than sklearn.cluster.KMeans()

[Gabriel-p]

The implementation of kmeans that uses the '++' method is orders of magnitude slower than the same algorithm in sklearn.cluster.KMeans(). This happens when n_clusters>10 in the code below.

With a 'random' initialization scipy's method is faster, so the problem is with '++'.

Reproducing code example:

import numpy as np
from sklearn.cluster import KMeans
from scipy.cluster.vq import kmeans2
import time as t

N = 1000
data = np.random.uniform(0., 1., (N, 4))

n_clusters = 50

s = t.time()
centroid, labels1 = kmeans2(
    data, n_clusters, minit='++', iter=10, thresh=1.e-4)
print("scipy:", t.time() - s)

s = t.time()
# KMeans
model = KMeans(n_clusters=n_clusters, init='k-means++', n_init=10, tol=1.e-4,
    max_iter=1000, verbose=0)
model.fit(data)
labels2 = model.labels_
print("sklearn", t.time() - s)

Scipy/Numpy/Python version information:

1.4.1 1.18.1 sys.version_info(major=3, minor=7, micro=6, releaselevel='final', serial=0)

[jjerphan]

Hello,
I am interested to contribute to scipy, is this a good first issue to pick?

[rgommers]

Fixed by gh-11982. Thanks @jjerphan, and thanks for reporting @Gabriel-p