A sequential kmeans algorithm implementation.

kmeans.c

#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <float.h>
#include <stdio.h>

#define N 300000
#define K 100
#define TOLERANCE 0.00001
#define SEED 11

typedef struct{
  double x;
  double y;
} Point;

double distance(Point p1, Point p2) {
  Point diff;
  diff.x = p1.x - p2.x;
  diff.y = p1.y - p2.y;
  return (double) sqrt(diff.x*diff.x + diff.y*diff.y);
}

void kmeans(Point* data, Point* means) {
  int p, k;
  int closerGroup;
  double dist, minDist;
  double prevError, error = DBL_MAX;
  int* groupForPoint = (int*) malloc(N*sizeof(int));
  Point pAdd;
  int n, iter;

  iter= 1;
  do {
    printf("Step %d\n", iter++);

    prevError = error;
    error = 0;

    for (p = 0; p < N; p++) {
      minDist = DBL_MAX;
      closerGroup = 0;

      for (k = 0; k < K; k++) {
        dist = distance(data[p], means[k]);
        if (dist < minDist) {
          minDist = dist;
          closerGroup = k;
        }
      }

      error += minDist;

      groupForPoint[p] = closerGroup;
    }

    for (k = 0; k < K; k++) {
      pAdd.x = 0; pAdd.y = 0;
      n = 0;
      for (p = 0; p < N; p++) {
        if (groupForPoint[p] == k) {
          pAdd.x += data[p].x;
          pAdd.y += data[p].y;
          n++; 
        }
      }

      if (n > 0) {
        means[k].x = pAdd.x / n;
        means[k].y = pAdd.y / n;
      }
    }

  } while (fabs(error - prevError) > TOLERANCE);

  free(groupForPoint);

}

int main(void) {

  printf("N: %d K: %d\n", N, K);

  int i;

  Point* data =  (Point*)malloc(N*sizeof(Point));
  Point* means =  (Point*)malloc(K*sizeof(Point));

  srand(SEED);

  /* Cargamos puntos */
  for (i = 0; i < N; i++) {
    data[i].x = (double)rand()/RAND_MAX;
    data[i].y = (double)rand()/RAND_MAX;
  }

  /* Inicializamos las medias */
  for (i = 0; i < K; i++) {
    means[i].x = (double)rand()/RAND_MAX;
    means[i].y = (double)rand()/RAND_MAX;
  }

  kmeans(data, means);

  for (i = 0; i < K; i++)
    printf("%f, %f\n", means[i].x, means[i].y);

  free(data);
  free(means);
  
}