Return to Question

I have implemented the K-Mean clustering Algorithm in Numpy:

from __future__ import division
import numpy as np

def kmean_step(centroids, datapoints):
    ds = centroids[:,np.newaxis]-datapoints
    e_dists =  np.sqrt(np.sum(np.square(ds),axis=-1))
    cluster_allocs = np.argmin(e_dists, axis=0)
    clusters = [datapoints[cluster_allocs==ci] for ci in range(len(centroids))]
    new_centroids = np.asarray([(1/len(cl))*np.sum(cl, axis=0) for cl in clusters if len(cl)>0])
    return new_centroids, clusters

def kmean(centroids, datapoints, n_gen, do_print=True):
    clusters=None
    for ii in range(1,n_gen):
        new_centroids, clusters = kmean_step(centroids, datapoints)
        if np.array_equal(centroids,new_centroids):
            print "After %i generations stabalised" % ii
            break
        else:
            centroids = new_centroids
            if do_print:
                print_clusters(clusters,centroids)
    return clusters

I have left out the print_clusters method. It as expected, displays the current clusters using coloured plots in matplotlib.

###Issues

• kmean_step seems really ugly for an algorithm that can be described by:
  • Recluster the dataset around the centroids;
  • Recenter the centroids with their clusters.
• I am a bit unsure about the termination conditions in the kmean function. I have read that they are:
  • Centroids don't move,
  • or Cluster membership does not change,
  • or number of iterations exceeds preset max.
• I have the first and last of those, but the second seems like it will happen automatically by the first. If the cluster membership doesn't change, then the center doesn't move. Do I really need to include it? (it is surprisingly hard to implement) Or is it only included in the algorithm description for clarity?
• Is this an optimal way to implement it? To fully take advantage of vectorized operations? I am a bit iff about having 2 list comprehensions, particularly since one immediately cases to a ndarrray.

I have implemented the K-Mean clustering Algorithm in Numpy:

from __future__ import division
import numpy as np

def kmean_step(centroids, datapoints):
    ds = centroids[:,np.newaxis]-datapoints
    e_dists =  np.sqrt(np.sum(np.square(ds),axis=-1))
    cluster_allocs = np.argmin(e_dists, axis=0)
    clusters = [datapoints[cluster_allocs==ci] for ci in range(len(centroids))]
    new_centroids = np.asarray([(1/len(cl))*np.sum(cl, axis=0) for cl in clusters if len(cl)>0])
    return new_centroids, clusters

def kmean(centroids, datapoints, n_gen, do_print=True):
    clusters=None
    for ii in range(1,n_gen):
        new_centroids, clusters = kmean_step(centroids, datapoints)
        if np.array_equal(centroids,new_centroids):
            print "After %i generations stabalised" % ii
            break
        else:
            centroids = new_centroids
            if do_print:
                print_clusters(clusters,centroids)
    return clusters

I have left out the print_clusters method. It as expected, displays the current clusters using coloured plots in matplotlib.

Issues

• kmean_step seems really ugly for an algorithm that can be described by:
  • Recluster the dataset around the centroids;
  • Recenter the centroids with their clusters.
• I am a bit unsure about the termination conditions in the kmean function. I have read that they are:
  • Centroids don't move,
  • or Cluster membership does not change,
  • or number of iterations exceeds preset max.
• I have the first and last of those, but the second seems like it will happen automatically by the first. If the cluster membership doesn't change, then the center doesn't move. Do I really need to include it? (it is surprisingly hard to implement) Or is it only included in the algorithm description for clarity?
• Is this an optimal way to implement it? To fully take advantage of vectorized operations? I am a bit iff about having 2 list comprehensions, particularly since one immediately cases to a ndarrray.

I have implemented the K-Mean clustering Algorithm in Numpy:

from __future__ import division
import numpy as np

def kmean_step(centroids, datapoints):
 
    ds = centroids[:,np.newaxis]-datapoints
    e_dists =  np.sqrt(np.sum(np.square(ds),axis=-1))
    cluster_allocs = np.argmin(e_dists, axis=0)
    clusters = [datapoints[cluster_allocs==ci] for ci in range(len(centroids))]
    
    new_centroids = np.asarray([(1/len(cl))*np.sum(cl, axis=0) for cl in clusters if len(cl)>0])
    return new_centroids, clusters

def kmean(centroids, datapoints, n_gen, do_print=True):
    clusters=None
    for ii in range(1,n_gen):
        new_centroids, clusters = kmean_step(centroids, datapoints)
        if np.array_equal(centroids,new_centroids):
            print "After %i generations stabalised" % ii
            break
        else:
            centroids = new_centroids
            if do_print:
                print_clusters(clusters,centroids)
    return clusters

I have left out the print_clusters method. It as expected, displays the current clusters using coloured plots in matplotlib.

###Issues

• 'kmean_step' seems really ugly for an algorithm that can be described by:
  • Recluster the dataset around the centroids;
  • Recenter the centroids with their clusters.
• I am a bit unsure about the termination conditions in the kmean function. I have read that they are:
  • Centroids don't move,
  • or Cluster membership does not change,
  • or number of iterations exceeds preset max.
• I have the first and last of those, but the second seems like it will happen automatically by the first. If the cluster membership doesn't change, then the center doesn't move. Do I really need to include it? (it is surprisingly hard to implement) Or is it only included in the algorithm description for clarity?
• Is this an optimal way to implement it? To fully take advantage of vectorized operations? I am a bit iff about having 2 list comprehensions, particularly since one immediately cases to a ndarrray.

I have implemented the K-Mean clustering Algorithm in Numpy:

from __future__ import division
import numpy as np

def kmean_step(centroids, datapoints):
    ds = centroids[:,np.newaxis]-datapoints
    e_dists =  np.sqrt(np.sum(np.square(ds),axis=-1))
    cluster_allocs = np.argmin(e_dists, axis=0)
    clusters = [datapoints[cluster_allocs==ci] for ci in range(len(centroids))]
    new_centroids = np.asarray([(1/len(cl))*np.sum(cl, axis=0) for cl in clusters if len(cl)>0])
    return new_centroids, clusters

def kmean(centroids, datapoints, n_gen, do_print=True):
    clusters=None
    for ii in range(1,n_gen):
        new_centroids, clusters = kmean_step(centroids, datapoints)
        if np.array_equal(centroids,new_centroids):
            print "After %i generations stabalised" % ii
            break
        else:
            centroids = new_centroids
            if do_print:
                print_clusters(clusters,centroids)
    return clusters

I have left out the print_clusters method. It as expected, displays the current clusters using coloured plots in matplotlib.

###Issues

• kmean_step seems really ugly for an algorithm that can be described by:
  • Recluster the dataset around the centroids;
  • Recenter the centroids with their clusters.
• I am a bit unsure about the termination conditions in the kmean function. I have read that they are:
  • Centroids don't move,
  • or Cluster membership does not change,
  • or number of iterations exceeds preset max.
• I have the first and last of those, but the second seems like it will happen automatically by the first. If the cluster membership doesn't change, then the center doesn't move. Do I really need to include it? (it is surprisingly hard to implement) Or is it only included in the algorithm description for clarity?
• Is this an optimal way to implement it? To fully take advantage of vectorized operations? I am a bit iff about having 2 list comprehensions, particularly since one immediately cases to a ndarrray.