title: K-Means Clustering From Scratch in Python
body: <p>I've been trying to implement a simple k-means clustering algorithm from scratch in python/numpy. Initially I used a random array of size [1000,2] as a "dataset," so I could plot it easily, and my code seems to be working (dividing the points into k sections, placing centroids at the center of each section). Now I'd like to test it on a dataset with actual groups, so I concatenated two smaller arrays. It works as intended when k=2. However, larger values of k don't work; the number of points in each cluster seems to be 0 for some reason, and it returns a mean of empty slice warning, invalid value encountered in true_division on line 42 (dividing by 0 in np.mean() gives NaN). I tried seeing where the centroids are that it doesn't assign any points to some clusters, and plotting them only shows 1 centroid (instead of k centroids) at (0.5,0.5). Why do the other centroids not show, and why do some centroids not have their clusters?</p>
  
  <p>I've tried initializing the centroids at random points in the dataset (instead of initializing them entirely at random) and it still often (it has worked a couple times) results in the same error. </p>
  
  <pre><code>import numpy as np
  import pandas as pd
  import matplotlib.pyplot as plt
  
  w1 = np.random.uniform(0.8,1.0,(50,2))
  w2 = np.random.uniform(0.0,0.2,(50,2))
  X = np.concatenate((w1,w2),axis=0)
  
  def dist(a,b):
      a = np.reshape(a,(1,np.shape(a)[0],np.shape(a)[1]))
      b = np.reshape(b,(np.shape(b)[0],1,np.shape(b)[1]))
  
      dist = np.sqrt(np.sum(np.square(a-b), axis=2))
  
      a = np.reshape(a,(np.shape(a)[1],np.shape(a)[2]))
      b = np.reshape(b,(np.shape(b)[0],np.shape(b)[2]))
      return dist
  
  def k_means(k, X):
      centroids = np.random.rand(k,np.shape(X)[1])
  
      error = 1
      while error != 0:
          prevcen = centroids
  
          cluster = np.argmin(dist(X,centroids), axis=0)
  
          clusters = {}
          points = {}
  
          for i in range(k):
              point = np.empty((0,np.shape(X)[1]))
              for j in range(np.shape(X)[0]):
                  if cluster[j] == i:
                      concatenation = np.reshape(X[j,:],(1,np.shape(X)[1]))
                      point = np.concatenate((point, concatenation), axis=0)
              points = {i: point}
              clusters.update(points)
  
          for i in range(k):
              points = clusters[i]
              centroids[i,:] = np.mean(points, axis=0)
  
          error = np.linalg.norm((prevcen - centroids))
  
      return clusters, centroids
  
      k = 4
      clusters, centroids = k_means(k,X)
  
      colors = ["red", "green", "blue", "beige", "yellow", "magenta","purple", "pink", "cyan", "gray"]
  
      plt.scatter(centroids[:,0], centroids[:,1], s=20, c="black")
  
      for i in range(k):
          cluster = clusters[i]
          plt.scatter(cluster[:,0], cluster[:,1], s=5, c=colors[i])
  
      plt.show()
  </code></pre>