source: trunk/yat/classifier/NCC.h @ 3554

#ifndef _theplu_yat_classifier_ncc_
#define _theplu_yat_classifier_ncc_

// $Id$

/*
  Copyright (C) 2005 Peter Johansson, Markus Ringnér
  Copyright (C) 2006, 2007, 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
  Copyright (C) 2009, 2010 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "MatrixLookup.h"
#include "MatrixLookupWeighted.h"
#include "SupervisedClassifier.h"
#include "Target.h"

#include "yat/statistics/Averager.h"
#include "yat/statistics/AveragerWeighted.h"
#include "yat/utility/concept_check.h"
#include "yat/utility/Exception.h"
#include "yat/utility/Matrix.h"
#include "yat/utility/MatrixWeighted.h"
#include "yat/utility/Vector.h"
#include "yat/utility/stl_utility.h"
#include "yat/utility/yat_assert.h"

#include <boost/concept_check.hpp>

#include <iterator>
#include <map>
#include <cmath>

namespace theplu {
namespace yat {
namespace classifier {


  /**
     \brief Nearest Centroid Classifier

     A sample is predicted based on its distance to centroids for each
     class. The centroids are generated using training data. NCC
     supports using different measures, for example, Euclidean
     distance, to define distance between samples and centroids.

     The template argument Distance should be a class modelling
     the concept \ref concept_distance.
  */
  template <typename Distance>
  class NCC : public SupervisedClassifier
  {

  public:
    /**
       \brief Constructor

       Distance is initialized using its default constructor.
    */
    NCC(void);

    /**
       \brief Constructor using an initialized distance measure

       This constructor should be used if Distance has parameters and
       the user wants to specify the parameters by initializing
       Distance prior to constructing the NCC.
    */
    NCC(const Distance&);


    /**
       Destructor
    */
    virtual ~NCC(void);

    /**
       \brief Get the centroids for all classes.

       \return The centroids for each class as columns in a matrix.
    */
    const utility::Matrix& centroids(void) const;

    NCC<Distance>* make_classifier(void) const;

    /**
       \brief Make predictions for unweighted test data.

       Predictions are calculated and returned in \a results.  For
       each sample in \a data, \a results contains the distances to
       the centroids for each class. If a class has no training
       samples NaN's are returned for this class in \a
       results. Weighted distance calculations, in which NaN's have
       zero weights, are used if the centroids contain NaN's.

       \note NCC returns distances to centroids as the
       prediction. This means that the best class for a sample has the
       smallest value in \a results. This is in contrast to, for
       example, KNN for which the best class for a sample in \a
       results has the largest number (the largest number of nearest
       neighbors).
    */
    void predict(const MatrixLookup& data, utility::Matrix& results) const;

    /**
       \brief Make predictions for weighted test data.

       Predictions are calculated and returned in \a results.  For
       each sample in \a data, \a results contains the distances to
       the centroids for each class as in predict(const MatrixLookup&
       data, utility::Matrix& results). Weighted distance calculations
       are used, and zero weights are used for NaN's in centroids.  If
       for a test sample and centroid pair, all variables have either
       zero weight for the test sample or NaN for the centroid, the
       centroid and the sample have no variables with values in
       common. In this case the prediction for the sample is set to
       NaN for the class in \a results.

       \note NCC returns distances to centroids as the
       prediction. This means that the best class for a sample has the
       smallest value in \a results. This is in contrast to, for
       example, KNN for which the best class for a sample in \a
       results has the largest number (the largest number of nearest
       neighbors).
    */
    void predict(const MatrixLookupWeighted& data, utility::Matrix& results) const;

    /**
       \brief Train the NCC using unweighted training data with known
       targets.

       A centroid is calculated for each class. For each variable in
       \a data, a centroid for a class contains the average value of
       the variable across all training samples in the class.
    */
    void train(const MatrixLookup& data, const Target& targets);


    /**
       \brief Train the NCC using weighted training data with known
       targets.

       A centroid is calculated for each class as in
       train(const MatrixLookup&, const Target&).
       The weights of the data are used when calculating the centroids
       and the centroids should be interpreted as unweighted
       (i.e. centroid values have unity weights). If a variable has
       zero weights for all samples in a class, the centroid is set to
       NaN for that variable.
    */
    void train(const MatrixLookupWeighted& data, const Target& targets);


  private:

    void predict_unweighted(const MatrixLookup&, utility::Matrix&) const;
    void predict_weighted(const MatrixLookupWeighted&, utility::Matrix&) const;

    utility::Matrix centroids_;
    bool centroids_nan_;
    Distance distance_;
  };

  // templates

  template <typename Distance>
  NCC<Distance>::NCC()
    : SupervisedClassifier(), centroids_nan_(false)
  {
    BOOST_CONCEPT_ASSERT((utility::DistanceConcept<Distance>));
  }

  template <typename Distance>
  NCC<Distance>::NCC(const Distance& dist)
    : SupervisedClassifier(), centroids_nan_(false), distance_(dist)
  {
    BOOST_CONCEPT_ASSERT((utility::DistanceConcept<Distance>));
  }


  template <typename Distance>
  NCC<Distance>::~NCC()
  {
  }


  template <typename Distance>
  const utility::Matrix& NCC<Distance>::centroids(void) const
  {
    return centroids_;
  }


  template <typename Distance>
  NCC<Distance>*
  NCC<Distance>::make_classifier() const
  {
    // All private members should be copied here to generate an
    // identical but untrained classifier
    return new NCC<Distance>(distance_);
  }

  template <typename Distance>
  void NCC<Distance>::train(const MatrixLookup& data, const Target& target)
  {
    centroids_.resize(data.rows(), target.nof_classes());
    for(size_t i=0; i<data.rows(); i++) {
      std::vector<statistics::Averager> class_averager;
      class_averager.resize(target.nof_classes());
      for(size_t j=0; j<data.columns(); j++) {
        class_averager[target(j)].add(data(i,j));
      }
      for(size_t c=0;c<target.nof_classes();c++) {
        centroids_(i,c) = class_averager[c].mean();
      }
    }
  }


  template <typename Distance>
  void NCC<Distance>::train(const MatrixLookupWeighted& data, const Target& target)
  {
    centroids_.resize(data.rows(), target.nof_classes());
    for(size_t i=0; i<data.rows(); i++) {
      std::vector<statistics::AveragerWeighted> class_averager;
      class_averager.resize(target.nof_classes());
      for(size_t j=0; j<data.columns(); j++)
        class_averager[target(j)].add(data.data(i,j),data.weight(i,j));
      for(size_t c=0;c<target.nof_classes();c++) {
        if(class_averager[c].sum_w()==0) {
          centroids_nan_=true;
        }
        centroids_(i,c) = class_averager[c].mean();
      }
    }
  }


  template <typename Distance>
  void NCC<Distance>::predict(const MatrixLookup& test,
                              utility::Matrix& prediction) const
  {
    utility::yat_assert<utility::runtime_error>
      (centroids_.rows()==test.rows(),
       "NCC::predict test data with incorrect number of rows");

    prediction.resize(centroids_.columns(), test.columns());

    // If weighted training data has resulted in NaN in centroids: weighted calculations
    if(centroids_nan_) {
      predict_weighted(MatrixLookupWeighted(test),prediction);
    }
    // If unweighted training data: unweighted calculations
    else {
      predict_unweighted(test,prediction);
    }
  }

  template <typename Distance>
  void NCC<Distance>::predict(const MatrixLookupWeighted& test,
                              utility::Matrix& prediction) const
  {
    utility::yat_assert<utility::runtime_error>
      (centroids_.rows()==test.rows(),
       "NCC::predict test data with incorrect number of rows");

    prediction.resize(centroids_.columns(), test.columns());
    predict_weighted(test,prediction);
  }


  template <typename Distance>
  void NCC<Distance>::predict_unweighted(const MatrixLookup& test,
                                         utility::Matrix& prediction) const
  {
    for(size_t j=0; j<test.columns();j++)
      for(size_t k=0; k<centroids_.columns();k++)
        prediction(k,j) = distance_(test.begin_column(j), test.end_column(j),
                                    centroids_.begin_column(k));
  }

  template <typename Distance>
  void NCC<Distance>::predict_weighted(const MatrixLookupWeighted& test,
                                          utility::Matrix& prediction) const
  {
    utility::MatrixWeighted weighted_centroids(centroids_);
    for(size_t j=0; j<test.columns();j++)
      for(size_t k=0; k<centroids_.columns();k++)
        prediction(k,j) = distance_(test.begin_column(j), test.end_column(j),
                                    weighted_centroids.begin_column(k));
  }


}}} // of namespace classifier, yat, and theplu

#endif