title: is k-means ++ suitable for large data?
body: <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>