<p>Initial seeding has a large impact on k-means execution time. In <a href="http://datasciencelab.wordpress.com/2014/01/15/improved-seeding-for-clustering-with-k-means/" rel="nofollow noreferrer">this post</a> you can find some strategies to speed it up.</p>

<p>Perhaps, you could consider to use the <a href="https://arxiv.org/abs/1701.04600" rel="nofollow noreferrer">Siddhesh Khandelwal's K-means variant</a>, which was publised in Proceedings of European Conference on Information Retrieval (ECIR 2017).
Siddhesh provided the python implementation <a href="https://github.com/siddheshk/Faster-Kmeans" rel="nofollow noreferrer">in GitHub</a>, and it is accompanied by some other previous heuristic algorithms.  </p>
is k-means ++ suitable for large data?
<p>I used this k-means++ python code for initializing k centers but it is very long for large data, for example 400000 points of 2 dimension:</p>

<pre><code>class KPlusPlus(KMeans):
def _dist_from_centers(self):
    cent = self.mu
    X = self.X
    D2 = np.array([min([np.linalg.norm(x-c)**2 for c in cent]) for x in X])
    self.D2 = D2

def _choose_next_center(self):
    self.probs = self.D2/self.D2.sum()
    self.cumprobs = self.probs.cumsum()
    r = random.random()
    ind = np.where(self.cumprobs &gt;= r)[0][0]
    return(self.X[ind])

def init_centers(self):
    self.mu = random.sample(self.X, 1)
    while len(self.mu) &lt; self.K:
        self._dist_from_centers()
        self.mu.append(self._choose_next_center())

def plot_init_centers(self):
    X = self.X
    fig = plt.figure(figsize=(5,5))
    plt.xlim(-1,1)
    plt.ylim(-1,1)
    plt.plot(zip(*X)[0], zip(*X)[1], '.', alpha=0.5)
    plt.plot(zip(*self.mu)[0], zip(*self.mu)[1], 'ro')
    plt.savefig('kpp_init_N%s_K%s.png' % (str(self.N),str(self.K)), \
                bbox_inches='tight', dpi=200)
</code></pre>

<p>Is there a way to speed up k-means++?</p>