Advertisement
cd62131

k-means clustering

Jun 4th, 2019
592
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.12 KB | None | 0 0
  1. #include <float.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <tgmath.h>
  5. #include <time.h>
  6. #define CLUSTER 3
  7. #define ELEMS 1000
  8. typedef struct {
  9.   complex double z;
  10.   int cluster;
  11. } elem;
  12. typedef struct {
  13.   complex double V[2][CLUSTER];
  14.   int flip;
  15. } center;
  16. #define center_at(c, i) (c)->V[(c)->flip][(i)]
  17. static void center_init(center *c) {
  18.   c->flip = 0;
  19.   for (int i = 0; i < CLUSTER; ++i) { c->V[0][i] = c->V[1][i] = 0.; }
  20. }
  21. static void center_update(center *c, elem *elems, int n) {
  22.   c->flip = 1 - c->flip;
  23.   complex double s[CLUSTER] = {0};
  24.   int es[CLUSTER] = {0};
  25.   for (int i = 0; i < n; ++i) {
  26.     s[elems[i].cluster] += elems[i].z, ++es[elems[i].cluster];
  27.   }
  28.   for (int i = 0; i < CLUSTER; ++i) { center_at(c, i) = s[i] / es[i]; }
  29. }
  30. static int center_reassign(center *c, elem *elems, int n) {
  31.   int change = 0;
  32.   for (int i = 0; i < n; ++i) {
  33.     double d[CLUSTER];
  34.     for (int j = 0; j < CLUSTER; ++j) {
  35.       d[j] = fabs(elems[i].z - center_at(c, j));
  36.     }
  37.     double min = DBL_MAX;
  38.     int next_cluster;
  39.     for (int j = 0; j < CLUSTER; ++j) {
  40.       if (d[j] < min) { min = d[j], next_cluster = j; }
  41.     }
  42.     if (next_cluster != elems[i].cluster) {
  43.       elems[i].cluster = next_cluster, ++change;
  44.     }
  45.   }
  46.   return change;
  47. }
  48. static int build_elems(FILE *in, elem *elems, int n) {
  49.   double x, y;
  50.   int used = 0;
  51.   srand(time(NULL));
  52.   while (fscanf(in, "%lf,%lf", &x, &y) == 2) {
  53.     if (n <= used) { exit(1); }
  54.     elems[used].z = CMPLX(x, y), elems[used].cluster = rand() % 3, ++used;
  55.   }
  56.   return used;
  57. }
  58. static void output_elems(FILE *out, elem *elems, int n) {
  59.   for (int i = 0; i < n; ++i) {
  60.     fprintf(out, "%f,%f,%d\n", creal(elems[i].z), cimag(elems[i].z),
  61.             elems[i].cluster);
  62.   }
  63. }
  64. int main(void) {
  65.   FILE *in = fopen("nocluster.csv", "r");
  66.   elem elems[ELEMS];
  67.   int n = build_elems(in, elems, ELEMS);
  68.   fclose(in);
  69.   center c;
  70.   for (center_init(&c), center_update(&c, elems, n);
  71.        center_reassign(&c, elems, n) > 0; center_update(&c, elems, n)) {
  72.     ;
  73.   }
  74.   FILE *out = fopen("out.csv", "w");
  75.   output_elems(out, elems, n), fclose(out);
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement