Module: Cluster

Defined in:

lib/rbcluster/node.rb,
lib/rbcluster/tree.rb,
lib/rbcluster/version.rb,
ext/rbcluster/rbcluster.c

Defined Under Namespace

Classes: Node, Tree

Constant Summary

VERSION =

"0.0.2"

C_VERSION =

rb_str_new2(CLUSTERVERSION)

Class Method Summary

• .clusterdistance(*args) ⇒ Object
• .cuttree(nodes, clusters) ⇒ Object
• .distancematrix(*args) ⇒ Object
• .kcluster(*args) ⇒ Object

  main function.

• .kmedoids(*args) ⇒ Object
• .mean(ary) ⇒ Object
• .median(ary) ⇒ Object
• .pca(data) ⇒ Object
• .somcluster(*args) ⇒ Object
• .treecluster(*args) ⇒ Object

Class Method Details

.clusterdistance(*args) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 460

VALUE rbcluster_clusterdistance(int argc, VALUE* argv, VALUE self) {
  VALUE data, index1, index2, opts;
  int nrows, ncols;

  rb_scan_args(argc, argv, "31", &data, &index1, &index2, &opts);
  double** rows = rbcluster_ary_to_rows(data, &nrows, &ncols);

  int nidx1, nidx2;
  int* idx1 = rbcluster_parse_index(index1, &nidx1);
  int* idx2 = rbcluster_parse_index(index2, &nidx2);

  int** mask = rbcluster_create_mask(nrows, ncols);
  double* weight = rbcluster_create_weight(ncols);
  char method = 'a';
  char dist = 'e';
  int transpose = 0;

  if(opts != Qnil) {
    rbcluster_parse_mask(opts, mask, nrows, ncols);
    rbcluster_parse_weight(opts, &weight, ncols);
    rbcluster_parse_char(opts, "dist", &dist);
    rbcluster_parse_char(opts, "method", &method);
    rbcluster_parse_bool(opts, "transpose", &transpose);
  }

  double result = clusterdistance(
    nrows,
    ncols,
    rows,
    mask,
    weight,
    nidx1,
    nidx2,
    idx1,
    idx2,
    dist,
    method,
    transpose
  );

  free(weight);
  free(idx1);
  free(idx2);
  rbcluster_free_rows(rows, nrows);
  rbcluster_free_mask(mask, nrows);

  return DBL2NUM(result);
}

.cuttree(nodes, clusters) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 780

VALUE rbcluster_cuttree(VALUE self, VALUE nodes, VALUE clusters) {
  int nelements, nclusters;

  nclusters = NUM2INT(clusters);

  Node* cnodes = rbcluster_ary_to_nodes(nodes, &nelements);
  int n = nelements + 1;

  if(nclusters < 1) {
    rb_raise(rb_eArgError, "nclusters must be >= 1");
  }

  if(nclusters > n) {
    rb_raise(rb_eArgError, "more clusters requested than items available");
  }

  int clusterid[n];
  cuttree(n, cnodes, nclusters, clusterid);
  free(cnodes);

  if(clusterid[0] == -1) {
    rb_raise(rb_eNoMemError, "could not allocate memory for cuttree()");
  }

  return rbcluster_ints2rb(clusterid, (long)n);
}

.distancematrix(*args) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 388

VALUE rbcluster_distancematrix(int argc, VALUE* argv, VALUE self) {
  VALUE data, opts;
  int nrows, ncols, i, j;

  rb_scan_args(argc, argv, "11", &data, &opts);
  double** rows = rbcluster_ary_to_rows(data, &nrows, &ncols);

  char dist      = 'e';
  int transpose  = 0;
  int** mask     = rbcluster_create_mask(nrows, ncols);
  double* weight = rbcluster_create_weight(ncols);

  if(opts != Qnil) {
    Check_Type(opts, T_HASH);
    VALUE val;

    rbcluster_parse_mask(opts, mask, nrows, ncols);
    rbcluster_parse_weight(opts, &weight, ncols);
    rbcluster_parse_char(opts, "dist", &dist);
    rbcluster_parse_bool(opts, "transpose", &transpose);
  }

  VALUE result = Qnil;
  double** distances = distancematrix(
    nrows,
    ncols,
    rows,
    mask,
    weight,
    dist,
    transpose
  );

  if(distances) {
    result = rb_ary_new();
    for(i = 0; i < nrows; ++i) {
      VALUE row = rb_ary_new();

      for(j = 0; j < i; ++j){
        rb_ary_push(row, DBL2NUM(distances[i][j]));
      }

      // first row is NULL
      if(i != 0) {
        free(distances[i]);
      }

      rb_ary_push(result, row);
    }
  }

  free(weight);
  rbcluster_free_rows(rows, nrows);
  rbcluster_free_mask(mask, nrows);

  return result;
}

.kcluster(*args) ⇒ Object

main function

# File 'ext/rbcluster/rbcluster.c', line 230

VALUE rbcluster_kcluster(int argc, VALUE* argv, VALUE self) {
  VALUE arr, opts;
  int nrows, ncols, i, j;

  rb_scan_args(argc, argv, "11", &arr, &opts);

  double** data = rbcluster_ary_to_rows(arr, &nrows, &ncols);
  int** mask    = rbcluster_create_mask(nrows, ncols);

  // defaults
  int nclusters = 2;
  int transpose = 0;
  int npass     = 1;
  char method   = 'a';
  char dist     = 'e';
  double* weight = rbcluster_create_weight(nrows);

  int* clusterid = malloc(nrows*sizeof(int));
  int ifound    = 0;
  double error;

  // options
  if(opts != Qnil) {
    Check_Type(opts, T_HASH);
    VALUE val;

    rbcluster_parse_int(opts, "clusters", &nclusters);
    rbcluster_parse_mask(opts, mask, nrows, ncols);
    rbcluster_parse_weight(opts, &weight, ncols);
    rbcluster_parse_bool(opts, "transpose", &transpose);
    rbcluster_parse_int(opts, "passes", &npass);
    rbcluster_parse_char(opts, "method", &method);
    rbcluster_parse_char(opts, "dist", &dist);
  }

  kcluster(
    nclusters,
    nrows,
    ncols,
    data,
    mask,
    weight,
    transpose,
    npass,
    method,
    dist,
    clusterid,
    &error,
    &ifound
  );

  VALUE result = rbcluster_ints2rb(clusterid, nrows);

  rbcluster_free_rows(data, nrows);
  rbcluster_free_mask(mask, nrows);

  free(weight);
  free(clusterid);

  return rb_ary_new3(3, result, DBL2NUM(error), INT2NUM(ifound));
}

.kmedoids(*args) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 292

VALUE rbcluster_kmedoids(int argc, VALUE* argv, VALUE self) {
  VALUE data, opts;

  rb_scan_args(argc, argv, "11", &data, &opts);
  Check_Type(data, T_ARRAY);

  int nitems = (int)RARRAY_LEN(data);
  int nclusters = 2;
  int npass = 1;

  // populate 'distances' from the input Array
  double** distances = malloc(nitems*sizeof(double*));
  int i, j;
  VALUE row, num;

  for(i = 0; i < nitems; ++i) {
    row = rb_ary_entry(data, i);
    // TODO: better error message
    Check_Type(row, T_ARRAY);
    if(RARRAY_LEN(row) != i) {
      rb_raise(rb_eArgError,
        "expected row %d to have exactly %d elements, got %ld", i, i, RARRAY_LEN(row));
    }

    if(i == 0) {
      distances[i] = NULL;
    } else {
      distances[i] = malloc(i*sizeof(double));
    }

    for(j = 0; j < i; ++j) {
      distances[i][j] = NUM2DBL(rb_ary_entry(row, j));
    }
  }

  if(opts != Qnil) {
    rbcluster_parse_int(opts, "clusters", &nclusters);
    rbcluster_parse_int(opts, "passes", &npass);
    // TODO: initialid
  }

  int* clusterid = malloc(nitems*sizeof(int));
  double error;
  int ifound;

  // void kmedoids (int nclusters, int nelements, double** distance,
  //   int npass, int clusterid[], double* error, int* ifound);
  kmedoids(
    nclusters,
    nitems,
    distances,
    npass,
    clusterid,
    &error,
    &ifound
  );

  VALUE result = rbcluster_ints2rb(clusterid, nitems);
  free(clusterid);
  for(i = 1; i < nitems; ++i) free(distances[i]);

  return rb_ary_new3(3, result, DBL2NUM(error), INT2NUM(ifound));
}

.mean(ary) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 372

VALUE rbcluster_mean(VALUE self, VALUE ary) {
  Check_Type(ary, T_ARRAY);

  long len = RARRAY_LEN(ary);
  double arr[len];
  int i;
  VALUE num;

  for(i = 0; i < len; ++i) {
    num = rb_ary_entry(ary, i);
    arr[i] = NUM2DBL(num);
  }

  return DBL2NUM(mean((int)len, arr));
}

.median(ary) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 356

VALUE rbcluster_median(VALUE self, VALUE ary) {
  Check_Type(ary, T_ARRAY);

  long len = RARRAY_LEN(ary);
  double arr[len];
  int i;
  VALUE num;

  for(i = 0; i < len; ++i) {
    num = rb_ary_entry(ary, i);
    arr[i] = NUM2DBL(num);
  }

  return DBL2NUM(median((int)len, arr));
}

.pca(data) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 721

VALUE rbcluster_pca(VALUE self, VALUE data) {
  int nrows, ncols, i, j;

  double** u = rbcluster_ary_to_rows(data, &nrows, &ncols);
  int ndata = min(nrows, ncols);

  double** v = malloc(ndata*sizeof(double*));
  for(i = 0; i < ndata; ++i) {
    v[i] = malloc(ndata*sizeof(double));
  }
  double* w = malloc(ndata*sizeof(double));
  double* means = malloc(ncols*sizeof(double));

  // calculate the mean of each column
  for(j = 0; j < ncols; ++j) {
    means[j] = 0.0;
    for(i = 0; i < nrows; ++i) {
      means[j] += u[i][j];
    }

    means[j] /= nrows;
  }

  // subtract the mean of each column
  for(i = 0; i < nrows; ++i) {
    for(j = 0; j < ncols; ++j) {
      u[i][j] = u[i][j] - means[j];
    }
  }

  int ok = pca(nrows, ncols, u, v, w);
  if(ok == -1) {
    rb_raise(rb_eNoMemError, "could not allocate memory");
  } else if(ok > 0) {
    rb_raise(rb_eStandardError, "svd failed to converge");
  }

  VALUE mean = rbcluster_doubles2rb(means, ncols);
  VALUE eigenvalues = rbcluster_doubles2rb(w, ndata);
  VALUE coordinates = Qnil;
  VALUE pc = Qnil;

  if(nrows >= ncols) {
    coordinates = rbcluster_rows2rb(u, nrows, ncols);
    pc          = rbcluster_rows2rb(v, ndata, ndata);
  } else {
    pc          = rbcluster_rows2rb(u, nrows, ncols);
    coordinates = rbcluster_rows2rb(v, ndata, ndata);
  }

  rbcluster_free_rows(u, nrows);
  rbcluster_free_rows(v, ndata);

  free(w);
  free(means);

  return rb_ary_new3(4, mean, coordinates, pc, eigenvalues);
}

.somcluster(*args) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 618

VALUE rbcluster_somcluster(int argc, VALUE* argv, VALUE self) {
  VALUE data, opts;

  rb_scan_args(argc, argv, "11", &data, &opts);

  int nrows, ncols;
  double** rows = rbcluster_ary_to_rows(data, &nrows, &ncols);
  int** mask = rbcluster_create_mask(nrows, ncols);
  double* weight = rbcluster_create_weight(ncols);

  int transpose  = 0;
  char dist      = 'e';
  int nxgrid     = 2;
  int nygrid     = 1;
  double inittau = 0.02;
  int niter      = 1;

  if(opts != Qnil) {
    rbcluster_parse_mask(opts, mask, nrows, ncols);
    rbcluster_parse_weight(opts, &weight, ncols);
    rbcluster_parse_bool(opts, "transpose", &transpose);
    rbcluster_parse_int(opts, "nxgrid", &nxgrid);
    rbcluster_parse_int(opts, "nygrid", &nygrid);
    rbcluster_parse_double(opts, "inittau", &inittau);
    rbcluster_parse_int(opts, "niter", &niter);
    rbcluster_parse_char(opts, "dist", &dist);
  }

  int i, j, k;
  double*** celldata = rbcluster_create_celldata(nygrid, nxgrid, ncols);

  int clusterid[nrows][2];

  somcluster(
    nrows,
    ncols,
    rows,
    mask,
    weight,
    transpose,
    nxgrid,
    nygrid,
    inittau,
    niter,
    dist,
    celldata,
    clusterid
  );

  VALUE rb_celldata = rb_ary_new2(nxgrid);
  VALUE rb_clusterid = rb_ary_new2(nrows);

  VALUE iarr, jarr;

  for(i = 0; i < nxgrid; ++i) {
    iarr = rb_ary_new2(nygrid);
    for(j = 0; j < nygrid; ++j) {
      jarr = rb_ary_new2(ncols);
      for(k = 0; k < ncols; ++k) {
        rb_ary_push(jarr, DBL2NUM(celldata[i][j][k]));
      }
      rb_ary_push(iarr, jarr);
    }
    rb_ary_push(rb_celldata, iarr);
  }

  VALUE inner_arr;
  for(i = 0; i < nrows; ++i) {
    inner_arr = rb_ary_new2(2);
    rb_ary_push(inner_arr, INT2FIX(clusterid[i][0]));
    rb_ary_push(inner_arr, INT2FIX(clusterid[i][1]));

    rb_ary_push(rb_clusterid, inner_arr);
  }

  free(weight);
  rbcluster_free_rows(rows, nrows);
  rbcluster_free_mask(mask, nrows);
  rbcluster_free_celldata(celldata, nxgrid, nygrid);

  return rb_ary_new3(2, rb_clusterid, rb_celldata);
}

.treecluster(*args) ⇒ Object

# File 'ext/rbcluster/rbcluster.c', line 563

VALUE rbcluster_treecluster(int argc, VALUE* argv, VALUE self) {
  VALUE data, opts;
  rb_scan_args(argc, argv, "11", &data, &opts);

  int nrows, ncols;
  double** rows = rbcluster_ary_to_rows(data, &nrows, &ncols);

  int** mask     = rbcluster_create_mask(nrows, ncols);
  double* weight = rbcluster_create_weight(ncols);
  int transpose  = 0;
  char dist      = 'e';
  char method    = 'a';

   // TODO: allow passing a distance matrix instead of data.
  double** distmatrix = NULL;

  // options
  if(opts != Qnil) {
    rbcluster_parse_mask(opts, mask, nrows, ncols);
    rbcluster_parse_weight(opts, &weight, ncols);
    rbcluster_parse_char(opts, "dist", &dist);
    rbcluster_parse_char(opts, "method", &method);
    rbcluster_parse_bool(opts, "transpose", &transpose);

    if(TYPE(opts) == T_HASH && rb_hash_aref(opts, ID2SYM(rb_intern("distancematrix"))) != Qnil) {
      rb_raise(rb_eNotImpError, "passing a distance matrix to treecluster() is not yet implemented");
    }
  }

  Node* tree = treecluster(
    nrows,
    ncols,
    rows,
    mask,
    weight,
    transpose,
    dist,
    method,
    distmatrix
  );

  VALUE result = rb_ary_new2(nrows - 1);
  for(int i = 0; i < nrows - 1; ++i) {
    rb_ary_push(result, rbcluster_create_node(&tree[i]));
  }

  free(tree);
  free(weight);
  rbcluster_free_rows(rows, nrows);
  rbcluster_free_mask(mask, nrows);

  VALUE args[] = { result };
  return rb_class_new_instance(1, args, rbcluster_cTree);
}