fn_sparse_random_ecoc.hpp

Go to the documentation of this file.

// Copyright (C) 2011 the authors listed below
// http://ecocpak.sourceforge.net
//
// Authors:
// - Dimitrios Bouzas (bouzas at ieee dot org)
// - Nikolaos Arvanitopoulos (niarvani at ieee dot org)
// - Anastasios Tefas (tefas at aiia dot csd dot auth dot gr)
//
// This file is part of the ECOC PAK C++ library. It is
// provided without any warranty of fitness for any purpose.
//
// You can redistribute this file and/or modify it under
// the terms of the GNU Lesser General Public License (LGPL)
// as published by the Free Software Foundation, either
// version 3 of the License or (at your option) any later
// version.
// (see http://www.opensource.org/licenses for more info)





imat
create_sparse_matrix_from_rand
  (
  const double* random_matrix,
  const u32 n_rows,
  const u32 n_cols
  )
  {
  // number of matrix elements to be processed
  const u32 n_elem = n_rows * n_cols;

  // allocate coding matrix
  imat coding_matrix = zeros<imat>(n_rows, n_cols);

  // pointer to coding_matrix
  int* coding_matrix_ptr = coding_matrix.memptr();

  // iterate through elements of input matrix column wise
  for(u32 i = 0; i < n_elem; i++)
    {
    // 0.5 probability for zero
    if(random_matrix[i] >= 0.5)
      {
      // 0.25 probability for 1 and -1
      (random_matrix[i] >= 0.75)?
        coding_matrix_ptr[i] = 1
        :
        coding_matrix_ptr[i] = -1;
      }

    }

  return coding_matrix;
  }



bool
identical_columns_sparse
  (
  const imat& coding_matrix
  )
  {
  u32 counter = 0;

  for(u32 i = 0; i < coding_matrix.n_cols - 1; i++)
    {
    u32 n_zeros_i = accu(coding_matrix.col(i) == 0);

    for(u32 j = i + 1; j < coding_matrix.n_cols; j++)
      {
      u32 n_zeros_j = accu(coding_matrix.col(j) == 0);

      u32 matches = accu(coding_matrix.col(i) == coding_matrix.col(j));

      if(
        (matches == coding_matrix.n_rows) ||
        (matches == 0 && n_zeros_i == 0 && n_zeros_j == 0)
        )
        {
        return true;
        }
      else
        {
        counter = 0;
        for(u32 k = 0; k < coding_matrix.n_rows; k++)
          {
          if(
            (coding_matrix(k, i) != coding_matrix(k, j)) &&
            (coding_matrix(k, i) != 0) && (coding_matrix(k, j) != 0)
            )
            {
            counter++;
            }

          if(coding_matrix(k, i) == 0 && coding_matrix(k, j) == 0)
            {
            counter++;
            }

          }

        if(counter == coding_matrix.n_rows)
          {
          return true;
          }

        }

      }

    }

  return false;
  }



imat
create_sparse_random_matrix
  (
  const u32 n_classes,
  const u32 n_classifiers,
  const u32 n_matrices
  )
  {
  // declare coding matrix to be filled
  imat coding_matrix;

  // distance between pairs of rows of the coding matrix
  double dist = 0.0;

  int n_iterations = n_matrices;
  while(n_iterations > 0)
    {
    // temporary random matrix auxiliary for the creation of the coding
    // matrix
    mat tmp_rand_matrix = randu<mat>(n_classes, n_classifiers);

    // create current sparse random coding matrix
    imat current_coding_matrix = create_sparse_matrix_from_rand
                                   (
                                   tmp_rand_matrix.memptr(),
                                   n_classes,
                                   n_classifiers
                                   );

    // denotes if current coding matrix is valid
    bool is_valid = true;

    // distance between pairs of rows of the current examined matrix
    double current_dist = 0.0;

    // iterate through number of columns
    for(u32 i = 0; i < n_classifiers; i++)
      {
      const u32 n_plus_ones  = accu(current_coding_matrix.col(i) ==  1);
      const u32 n_minus_ones = accu(current_coding_matrix.col(i) == -1);
      const u32 n_zeros      = accu(current_coding_matrix.col(i) ==  0);

      // check if the current coding matrix is valid (i.e., does not
      // contain columns with only +1 or only -1 only zeros e.t.c)
      if(    n_plus_ones  == n_classes // column contains all plus ones
          || n_minus_ones == n_classes // column contains all minus ones
          || n_zeros      == n_classes // column contains all zeros
          || n_plus_ones  == 0         // column doesn't contain not
                                       // even one plus one
          || n_minus_ones == 0         // column doesn't contain not
                                       // even one minus one
          // column is identical with some other column of the coding
          // matrix
          || identical_columns_sparse(current_coding_matrix) == true
          )
        {
        // if something of the above is true set the is_valid centintel
        // to false (i.e., signal that current coding matrix is not
        // valid)
        is_valid = false;

        // break from the for loop
        break;
        }

      }

    // if the current coding matrix is valid
    if(is_valid == true)
      {
      //reduce number of matrices examined of iterations by one
      n_iterations--;

      // for each pair of rows of the current coding matrix
      for(u32 j = 0; j < n_classes - 1; j++)
        {
        for(u32 k = j + 1; k < n_classes; k++)
          {
          // compute current distance between rows j and k
          current_dist =
          norm
          (
          conv_to<rowvec>::from(current_coding_matrix.row(j))
          - conv_to<rowvec>::from(current_coding_matrix.row(k)),
          2
          );

          // if current distance is greater than the distance of any
          // pair of rows of the previously encountered coding matrices
          if(current_dist > dist)
            {
            dist = current_dist;
            coding_matrix = current_coding_matrix;
            }

          }

        }

      }

    }

  return coding_matrix;
  }



u32
sparse_random_ecoc
  (
  const mat& training_samples,
  const icolvec& training_labels,
  const mat& testing_samples,
  const icolvec& testing_labels,
  const int decoding_strategy,
  const int classifiers_type,
  const u32 n_matrices,
  const u32 n_desired_classifiers,
  const bool verbose,
  ofstream& verbose_output,
  double& execution_time
  )
  {
  // timer object to count execution times
  wall_clock timer;

  // start timer
  timer.tic();

  // number of training samples
  const u32 n_training_samples = training_samples.n_rows;

  // number of samples attributes
  const u32 n_attributes = training_samples.n_cols;

  // number of testing samples
  const u32 n_testing_samples = testing_samples.n_rows;

  // variable to hold the number of classes
  u32 n_classes = 0;

  // vector to hold number of samples per class
  ucolvec n_samples_per_class;

  // adjust the training samples class labels to start from one
  // and count number of classes
  const ucolvec tmp_training_labels = process_labels
                                        (
                                        training_labels,
                                        n_classes
                                        );

  // adjust the testing samples class labels to start from one
  const ucolvec tmp_testing_labels = process_labels(testing_labels);

  // decompose the training samples matrix into ClassData object
  vector<ClassData> classes_vector =
    create_class_vector
      (
      training_samples,
      conv_to<icolvec>::from(tmp_training_labels)
      );

  // declare empty classifiers vector
  // vector<Classifier*> classifiers_vector;

  // compute coding matrix for sparse random ecoc design
  imat coding_matrix = create_sparse_random_matrix
                         (
                         n_classes,
                         n_desired_classifiers,
                         n_matrices
                         );

  // classifiers vector
  vector<Classifier*> classifiers_vector;

  // ================================================================ //
  // ||                        Training Step                       || //
  // ================================================================ //

    // start training
    for(u32 i = 0; i < coding_matrix.n_cols; i++)
      {
      // data matrix of positive classes for current column of coding
      // matrix
      mat first_bipartition;

      // data matrix of positive classes for current column of coding
      // matrix
      mat second_bipartition;

      // temporary vector to store pointers of positive classes
      vector<ClassData*> pos_classes;

      // temporary vector to store pointers of negative classes
      vector<ClassData*> neg_classes;

      // temporary number of possitive samples
      u32 n_pos = 0;

      // temporary number of negative samples
      u32 n_neg = 0;

      // iterate through number of classes
      for(u32 j = 0; j < n_classes; j++)
        {
        // if current class is considered positive
        if(coding_matrix(j, i) == 1)
          {
          // append samples of current class to the positive classes
          // data matrix
          first_bipartition = join_cols
                                (
                                first_bipartition,
                                classes_vector[j].Data()
                                );

          // add pointer of current class to temporary vector of
          // positive classes
          pos_classes.push_back(&(classes_vector[j]));

          // update number of positive samples
          n_pos += classes_vector[j].Samples();
          }
        else
          {
          // if current class is considered negative
          if(coding_matrix(j, i) == -1)
            {
            // append samples of current class to the negative classe
            // data matrix
            second_bipartition = join_cols
                                   (
                                   second_bipartition,
                                   classes_vector[j].Data()
                                   );

            // add pointer of current class to temporary vector of
            // negative classes
            neg_classes.push_back(&(classes_vector[j]));

            // update number of positive samples
            n_neg += classes_vector[j].Samples();
            }

          // otherwise current class is not considered

          }

        }

      // according to user specified classifier
      switch(classifiers_type)
        {
         // Nearest Class Centroid Classifier
        case NCC:
          {
          Classifier_ncc* tmp = new Classifier_ncc
                                      (
                                      first_bipartition,
                                      second_bipartition
                                      );

          // update classifier classes
          tmp->pos = pos_classes;
          tmp->neg = neg_classes;
          tmp->n_pos = n_pos;
          tmp->n_neg = n_neg;

          // store classifier
          classifiers_vector.push_back(tmp);

          break;
          }

        // Fisher Linear Discriminant followed by NCC
        case FLDA:
          {
          Classifier_flda* tmp = new Classifier_flda
                                       (
                                       first_bipartition,
                                       second_bipartition
                                       );

          // update classifier classes
          tmp->pos = pos_classes;
          tmp->neg = neg_classes;
          tmp->n_pos = n_pos;
          tmp->n_neg = n_neg;

          // store classifier
          classifiers_vector.push_back(tmp);

          break;
          }

        // Support Vector Machine Classifier
        case SVM:
          {
          Classifier_svm* tmp = new Classifier_svm
                                      (
                                      first_bipartition,
                                      second_bipartition
                                      );

          // update classifier classes
          tmp->pos = pos_classes;
          tmp->neg = neg_classes;
          tmp->n_pos = n_pos;
          tmp->n_neg = n_neg;

          // store classifier
          classifiers_vector.push_back(tmp);

          break;
          }

        // AdaBoost Classifier
        case ADABOOST:
          {
          Classifier_adaBoost* tmp = new Classifier_adaBoost
                                           (
                                           first_bipartition,
                                           second_bipartition
                                           );

          // update classifier classes
          tmp->pos = pos_classes;
          tmp->neg = neg_classes;
          tmp->n_pos = n_pos;
          tmp->n_neg = n_neg;

          // store classifier
          classifiers_vector.push_back(tmp);

          break;
          }

        // Sum of Error Squares Classifier
        case LEAST_SQUARES:
          {
          Classifier_ls* tmp = new Classifier_ls
                                     (
                                     first_bipartition,
                                     second_bipartition
                                     );

          // update classifier classes
          tmp->pos = pos_classes;
          tmp->neg = neg_classes;
          tmp->n_pos = n_pos;
          tmp->n_neg = n_neg;

          // store classifier
          classifiers_vector.push_back(tmp);

          break;
          }

        // Custom Classifier
        case CUSTOM_CLASSIFIER:
          {
          Classifier_custom* tmp = new Classifier_custom
                                         (
                                         first_bipartition,
                                         second_bipartition
                                         );

          // update classifier classes
          tmp->pos = pos_classes;
          tmp->neg = neg_classes;
          tmp->n_pos = n_pos;
          tmp->n_neg = n_neg;

          // store classifier
          classifiers_vector.push_back(tmp);

          break;
          }

        default:
          {
          arma_debug_print
            (
            "sparse_random_ecoc(): Unknown classifier's option"
            );

          }

        }

      }

  // ================================================================ //
  // ||                        Testing Step                        || //
  // ================================================================ //

    // classification error
    double error = 0.0;

    // predictions for each sample
    uvec predictions;

    // confussion matrix
    umat confussion;

    // number of misclassified samples
    u32 n_missed = 0;

    // used to hold the number of missclassified testing samples
    decode
      (
      testing_samples,
      tmp_testing_labels,
      coding_matrix,
      classifiers_vector,
      classes_vector,
      decoding_strategy,
      predictions,
      n_missed,
      error,
      confussion
      );

  // if verbose output is activated
  if(verbose == true)
    {
    predictions = join_rows(predictions, tmp_testing_labels);
    verbose_output << "* Predictions vs Labels: " << endl << predictions << endl << endl;
    verbose_output << "* Coding Matrix: " << endl << coding_matrix << endl << endl;
    verbose_output << "* Confusion Matrix: " << endl << confussion << endl;
    }

  // clean up classifiers vector
  for(u32 i = 0; i < classifiers_vector.size(); i++)
    {
    delete classifiers_vector[i];
    }

  // stop timer
  execution_time = timer.toc();

  // reset class counter
  ClassData::globalIndex = 0;

  // return number of misclassified samples
  return n_missed;
  }