fn_forest_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
permvec
  (
  const ivec& A
  )
  {
  // output binary matrix where its columns will be the permutation
  // vectors of A
  imat out;

  // number of possible permutations
  u32 n = pow(2, A.n_elem);

  // index counters
  u32 k = 0;
  u32 l = 0;

  // clone input vector
  ivec tmp1 = A;

  // iterate through the available number of permutations
  for(u32 i = 0; i < n; i++)
    {
    if(k == A.n_elem)
      {
      k = 0;

      if(l == A.n_elem)
        {
        return out;
        }
      else
        {
        tmp1(l) = -tmp1(l);
        l++;
        k++;
        }

      }

    ivec tmp = tmp1;

    tmp(k) = -tmp(k);

    bool exists = false;

    if
      (
      tmp.n_elem == accu(tmp)       ||
      tmp.n_elem == accu(-tmp)      ||
      tmp.n_elem == accu(tmp == A)  ||
      tmp.n_elem == accu(-tmp == A)
      )
      {
      exists = true;
      }
    else
      {
      for(u32 j = 0; j < out.n_cols; j++)
        {
        if
          (
          out.n_rows == accu(tmp == out.col(j))  ||
          out.n_rows == accu(-tmp == out.col(j))
          )
          {
          exists = true;
          break;
          }

        }

      }

    if(exists == false)
      {
      out = join_rows(out, tmp);
      }

    k++;
    }

  return out;
  }



void
append_tree
  (
  const vector<ClassData>& classes_vector,
  const ivec& root,
  const int criterion_option,
  const int classifiers_type,
  imat& M,
  vector<Classifier*>& classifiers_vector
  )
  {
  // number of active classes
  uvec actinds = find(root != 0);
  u32 n_classes = actinds.n_elem;

  // trivial recursion step
  if(n_classes < 2)
    {
    // exit
    return;
    }

  // case classes are two
  if(n_classes == 2)
    {
    // create column to be appended in the coding matrix
    ivec c = zeros<ivec>(M.n_rows);

    c[classes_vector[actinds[0]].ClassLabel() - 1] =  1;
    c[classes_vector[actinds[1]].ClassLabel() - 1] = -1;

    // update coding matrix
    M = join_rows(M, c);

    // create binary classifier
    Classifier* tmpcl = create_classifier
                          (
                          classes_vector[actinds[0]].Data(),
                          classes_vector[actinds[1]].Data(),
                          classifiers_type
                          );

    // update classifier's info
    tmpcl->pos.push_back(const_cast<ClassData*>(&(classes_vector[actinds[0]])));
    tmpcl->neg.push_back(const_cast<ClassData*>(&(classes_vector[actinds[1]])));

    tmpcl->n_pos = classes_vector[actinds[0]].Samples();
    tmpcl->n_neg = classes_vector[actinds[1]].Samples();

    // create and push back classifier
    classifiers_vector.push_back(tmpcl);

    // exit
    return;
    }
  else
    {
    // first partition of classes
    vector<ClassData> part1;

    // second partition of classes
    vector<ClassData> part2;

    // datamatrix of possitive classes
    mat A;

    // datamatrix of negative classes
    mat B;

    // create partitions for root of tree
    for(u32 i = 0; i < root.n_elem; i++)
      {
      if(root[i] == 1)
        {
        part1.push_back(classes_vector[i]);
        A = join_cols(A, classes_vector[i].Data());
        }
      else
        {
        if(root[i] == -1)
          {
          part2.push_back(classes_vector[i]);
          B = join_cols(B, classes_vector[i].Data());
          }

        }

      }

    // append column to coding matrix
    M = join_rows(M, root);

    // create and push classifier for root of tree
    Classifier* tmpcl = create_classifier(A, B, classifiers_type);

    // update classifier's data for positive classes
    for(u32 i = 0; i < part1.size(); i++)
      {
      tmpcl->pos.push_back
        (
        const_cast<ClassData*>(&(classes_vector[part1[i].ClassLabel() - 1]))
        );

      tmpcl->n_pos += part1[i].Samples();
      }

    // updata classifier's data for negative classes
    for(u32 i = 0; i < part2.size(); i++)
      {
      tmpcl->neg.push_back
        (
        const_cast<ClassData*>(&(classes_vector[part2[i].ClassLabel() - 1]))
        );

      tmpcl->n_neg += part2[i].Samples();
      }

    // push back classifier
    classifiers_vector.push_back(tmpcl);

    // create root for first partition
    ivec root1 = zeros<ivec>(M.n_rows);

    // create root for second partion
    ivec root2 = zeros<ivec>(M.n_rows);

    // positive classes are more than 2
    if(part1.size() > 2)
      {
      // find new bipartions for current positive classes
      uvec indsbest1 = sffs(part1, criterion_option);
      uvec indscomp1 = complement(indsbest1, part1.size());

      for(u32 i = 0; i < indsbest1.n_elem; i++)
        {
        root1[part1[indsbest1[i]].ClassLabel() - 1] = 1;
        }

      for(u32 i = 0; i < indscomp1.n_elem; i++)
        {
        root1[part1[indscomp1[i]].ClassLabel() - 1] = -1;
        }

      }
    else
      {
      if(part1.size() == 2)
        {
        root1[part1[0].ClassLabel() - 1] =  1;
        root1[part1[1].ClassLabel() - 1] = -1;
        }
      else
        {
        root1[part1[0].ClassLabel() - 1] =  1;
        }

      }

    // if negative classes are more than 2
    if(part2.size() > 2)
      {
      // find new bipartions for current negative classes
      uvec indsbest2 = sffs(part2, criterion_option);
      uvec indscomp2 = complement(indsbest2, part2.size());

      for(u32 i = 0; i < indsbest2.n_elem; i++)
        {
        root2[part2[indsbest2[i]].ClassLabel() - 1] = 1;
        }

      for(u32 i = 0; i < indscomp2.n_elem; i++)
        {
        root2[part2[indscomp2[i]].ClassLabel() - 1] = -1;
        }

      }
    else
      {
      if(part2.size() == 2)
        {
        root2[part2[0].ClassLabel() - 1] =  1;
        root2[part2[1].ClassLabel() - 1] = -1;
        }
      else
        {
        root2[part2[0].ClassLabel() - 1] =  1;
        }

      }

    // recursion step for positive classes
    append_tree
      (
      classes_vector,
      root1,
      criterion_option,
      classifiers_type,
      M,
      classifiers_vector
      );

    // recursion step for negative classes
    append_tree
      (
      classes_vector,
      root2,
      criterion_option,
      classifiers_type,
      M,
      classifiers_vector
      );

    }

  return;
  }



u32
forest_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 int criterion_option,
  const u32 n_forests,
  const bool verbose,
  ofstream& verbose_output,
  double& elapsed_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;

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

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

  // create classes vector
  vector<ClassData> classes_vector = create_class_vector
                                       (
                                       training_samples,
                                       tmp_training_labels
                                       );

  // coding matrix
  imat coding_matrix;

  // classifiers vector
  vector<Classifier*> classifiers_vector;

  // classification error
  double error = 0.0;

  // predictions for each sample
  uvec predictions;

  // confussion matrix
  umat confussion;

  // number of misclassified samples
  u32 n_missed = 0;

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

    // create initial tree
    decoc_ecocone
      (
      classes_vector,
      classifiers_type,
      criterion_option,
      coding_matrix,
      classifiers_vector
      );

    // create all valide roots matrix
    imat vroots = permvec(coding_matrix.col(0));

    u32 n_iter = n_forests;

    if(n_forests > vroots.n_cols)
      {
      n_iter = vroots.n_cols;
      }

    // create random permutation of indices
    vec rv = randu<vec>(vroots.n_cols);
    uvec rinds = sort_index(rv);

    // iterate through number of forests
    for(u32 i = 0; i < n_iter; i++)
      {
      append_tree
        (
        classes_vector,
        vroots.col(rinds[i]),
        criterion_option,
        classifiers_type,
        coding_matrix,
        classifiers_vector
        );

      }

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

    // decode coding matrix and compute generalization error
    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
  elapsed_time = timer.toc();

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

  // return number of misclassified samples
  return n_missed;
  }