Class: KnnCv::Classifier

Inherits:

Object

• Object
• KnnCv::Classifier

Defined in:

ext/c_knn/knn.c

Defined Under Namespace

Classes: Classes, Instances, Numerics

Instance Method Summary

• #fitness_for(rb_features) ⇒ Object
• #initialize(rb_k, data, rb_class, rb_numeric, rb_random_par) ⇒ Object constructor

Constructor Details

#initialize(rb_k, data, rb_class, rb_numeric, rb_random_par) ⇒ Object

# File 'ext/c_knn/knn.c', line 187

VALUE method_c_knn_initialize(VALUE self, VALUE rb_k, VALUE data, VALUE rb_class, VALUE rb_numeric, VALUE rb_random_par) {
  long int ncol, nrow;

  double * instances = NULL;
  int * classes = NULL;
  int * which_numeric = NULL;

  // VALUE data = rb_funcall(rb_dataset, rb_intern("instances"), 0);
  // VALUE rb_class = rb_funcall(rb_dataset, rb_intern("classes"), 0);
  // VALUE rb_numeric = rb_funcall(rb_dataset, rb_intern("numeric_attrs"), 0);

  // Define global variables
  rb_iv_set(self, "@num_neighbors", rb_k);
  nrow = RARRAY_LEN(data);
  if (nrow > 0) {
    rb_iv_set(self, "@nrow", INT2NUM(nrow));
    ncol = RARRAY_LEN(rb_ary_entry(data, 0));
    rb_iv_set(self, "@ncol", INT2NUM(ncol));
    rb_iv_set(self, "@nclass", rb_funcall(rb_funcall(rb_class, rb_intern("uniq"), 0), rb_intern("length"), 0));
    FLOAT_MAX = NUM2DBL(rb_intern("Float::MAX"));
    rb_iv_set(self, "@rng", rb_random_par);

    instances = (double*) malloc(sizeof(double) * nrow * ncol);

    int i, j;
    for (i = 0; i < nrow; i++) {
      for (j = 0; j < ncol; j++) {
        if (TYPE(rb_ary_entry(rb_ary_entry(data, i), j)) == T_STRING) {
          rb_raise(rb_eArgError, "A string was found within the dataset. Aborting...");
        } else
        instances[i * ncol + j] = NUM2DBL(rb_ary_entry(rb_ary_entry(data, i), j));
      }
    }

    classes = (int*) malloc(sizeof(int) * nrow);

    for (i = 0; i < nrow; i++) {
      classes[i] = NUM2INT(rb_ary_entry(rb_class, i));
    }

    which_numeric = (int*) malloc(sizeof(int) * ncol);

    for (j = 0; j < ncol; j++) {
      which_numeric[j] = NUM2INT(rb_ary_entry(rb_numeric, j));
    }

    rb_iv_set(self, "@instances", Data_Wrap_Struct(C_instances, NULL, c_knn_free, instances));
    rb_iv_set(self, "@classes", Data_Wrap_Struct(C_classes, NULL, c_knn_free, classes));
    rb_iv_set(self, "@which_numeric", Data_Wrap_Struct(C_numerics, NULL, c_knn_free, which_numeric));
  } else {
    rb_raise(rb_eArgError, "Attempted to create a classifier for an empty dataset. Aborting...");
  }

  return self;
}

Instance Method Details

#fitness_for(rb_features) ⇒ Object

# File 'ext/c_knn/knn.c', line 44

VALUE method_c_knn_leaveoneout(VALUE self, VALUE rb_features) {
  double * instances = NULL;
  int * classes = NULL;
  int * which_numeric = NULL;

  Data_Get_Struct(rb_iv_get(self, "@instances"), double, instances);
  Data_Get_Struct(rb_iv_get(self, "@classes"), int, classes);
  Data_Get_Struct(rb_iv_get(self, "@which_numeric"), int, which_numeric);

  int nrow = NUM2INT(rb_iv_get(self, "@nrow"));
  int ncol = NUM2INT(rb_iv_get(self, "@ncol"));
  int num_neighbors = NUM2INT(rb_iv_get(self, "@num_neighbors"));
  int class_count = NUM2INT(rb_iv_get(self, "@nclass"));

  rb_features = rb_funcall(rb_features, rb_intern("to_a"), 0);
  int correct_guesses;
  double fitness;


  /* The following is code based on the "class" package from R */
  /***************************************************************
   VR_knn input parameters:
     Sint *kin, Sint *lin, Sint *pntr, Sint *pnte, Sint *p,
     double *train, Sint *class, double *test, Sint *res, double *pr,
     Sint *votes, Sint *nc, Sint *cv, Sint *use_all
  ***************************************************************/
  int   i, index, j, k, k1, kinit = num_neighbors, kn, l = 0, mm, npat, ntie, extras;
  int   pos[MAX_TIES];
  double dist, tmp, nndist[MAX_TIES];

  // Prediction results
  int * res = (int*) malloc(sizeof(int) * nrow);
  int * votes = (int*) malloc(sizeof(int) * class_count);

  /*
  Use a 'fence' in the (k+1)st position to avoid special cases.
  Simple insertion sort will suffice since k will be small.
  */

  for (npat = 0; npat < nrow; npat++) {
    kn = kinit;

    for (k = 0; k < kn; k++)
      nndist[k] = 0.99 * FLOAT_MAX;

    for (j = 0; j < nrow; j++) {
      if (j == npat) // Skip own instance for leave-one-out cross_validation
        continue;

      dist = 0.0;

      for (k = 0; k < ncol; k++) {
        // Skip unselected features
        if (NUM2INT(rb_ary_entry(rb_features, k))) {
          // Distinguish numeric attributes from nominal
          tmp = instances[npat * ncol + k] - instances[j * ncol + k];

          if (which_numeric[k]) {
            dist += tmp * tmp;
          } else if (tmp < EPS && tmp > -EPS) { // Nominal feature
            // Add 1 if values are different
            dist += 1;
          }
        }
      }

      /* Use 'fuzz' since distance computed could depend on order of coordinates */
      if (dist <= nndist[kinit - 1] * (1 + EPS))
        for (k = 0; k <= kn; k++)
          if (dist < nndist[k]) {
            for (k1 = kn; k1 > k; k1--) {
              nndist[k1] = nndist[k1 - 1];
              pos[k1] = pos[k1 - 1];
            }
            nndist[k] = dist;
            pos[k] = j;

            /* Keep an extra distance if the largest current one ties with current kth */
            if (nndist[kn] <= nndist[kinit - 1])
              if (++kn == MAX_TIES - 1)
                return rb_float_new(-2.0); // Too many ties. Fail
            break;
          }

      nndist[kn] = 0.99 * FLOAT_MAX;
    }

    for (j = 0; j < class_count; j++)
      votes[j] = 0;

    // use_all is true always so unneeded code has been removed
    for (j = 0; j < kinit; j++){
      votes[classes[pos[j]]]++;
    }
    extras = 0;

    for (j = kinit; j < kn; j++) {
      if (nndist[j] > nndist[kinit - 1] * (1 + EPS))
        break;

      extras++;
      votes[classes[pos[j]]]++;
    }

    /* Use reservoir sampling to choose amongst the tied votes */
    ntie = 1;

    mm = votes[0];
    index = 0;

    for (i = 1; i < class_count; i++)
      if (votes[i] > mm) {
        ntie = 1;
        index = i;
        mm = votes[i];
      } else if (votes[i] == mm && votes[i] >= l) {
        // This line is causing segfaults:
        //if (++ntie * NUM2DBL(rb_funcall(rb_random, rb_intern("rand"), 0)) < 1.0)
        if (++ntie * NUM2DBL(rb_funcall(rb_iv_get(self, "@rng"), rb_intern("rand"), 0)) < 1.0)
          index = i;
      }

    res[npat] = index;
    //pr[npat] = (double) mm / (kinit + extras);
  }
  /* end of "class" code */

  free(votes);

  correct_guesses = 0;

  for (npat = 0; npat < nrow; npat++) {
    // Count correct guesses
    correct_guesses += res[npat] == classes[npat];
  }

  free(res);

  fitness = (double)(correct_guesses) / (double)(nrow);

  return rb_float_new(fitness);
}