source: trunk/yat/classifier/KNN.h @ 3553

#ifndef _theplu_yat_classifier_knn_
#define _theplu_yat_classifier_knn_

// $Id: KNN.h 3553 2017-01-03 07:56:01Z peter $

/*
  Copyright (C) 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 "DataLookup1D.h"
#include "DataLookupWeighted1D.h"
#include "KNN_Uniform.h"
#include "MatrixLookup.h"
#include "MatrixLookupWeighted.h"
#include "SupervisedClassifier.h"
#include "Target.h"
#include "yat/utility/concept_check.h"
#include "yat/utility/Exception.h"
#include "yat/utility/Matrix.h"
#include "yat/utility/Vector.h"
#include "yat/utility/VectorConstView.h"
#include "yat/utility/VectorView.h"
#include "yat/utility/yat_assert.h"

#include <boost/concept_check.hpp>

#include <cmath>
#include <limits>
#include <map>
#include <stdexcept>
#include <vector>

namespace theplu {
namespace yat {
namespace classifier {

  /**
     \brief Nearest Neighbor Classifier

     A sample is predicted based on the classes of its k nearest
     neighbors among the training data samples. KNN supports using
     different measures, for example, Euclidean distance, to define
     distance between samples. KNN also supports using different ways to
     weight the votes of the k nearest neighbors. For example, using a
     uniform vote a test sample gets a vote for each class which is the
     number of nearest neighbors belonging to the class.

     The template argument Distance should be a class modelling the
     concept \ref concept_distance. The template argument
     NeighborWeighting should be a class modelling the concept \ref
     concept_neighbor_weighting.
  */
  template <typename Distance, typename NeighborWeighting=KNN_Uniform>
  class KNN : public SupervisedClassifier
  {

  public:
    /**
       \brief Default constructor.

       The number of nearest neighbors (k) is set to 3. Distance and
       NeighborWeighting are initialized using their default
       constructuors.
    */
    KNN(void);


    /**
       \brief Constructor using an intialized distance measure.

       The number of nearest neighbors (k) is set to
       3. NeighborWeighting is initialized using its default
       constructor. This constructor should be used if Distance has
       parameters and the user wants to specify the parameters by
       initializing Distance prior to constructing the KNN.
    */
    KNN(const Distance&);


    /**
       Destructor
    */
    virtual ~KNN();


    /**
       \brief Get the number of nearest neighbors.
       \return The number of neighbors.
    */
    unsigned int k() const;

    /**
       \brief Set the number of nearest neighbors.

       Sets the number of neighbors to \a k_in.
    */
    void k(unsigned int k_in);


    KNN<Distance,NeighborWeighting>* 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 weighted number
       of nearest neighbors which belong to each class. Numbers of
       nearest neighbors are weighted according to
       NeighborWeighting. If a class has no training samples NaN's are
       returned for this class in \a results.
    */
    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 weighted
        number of nearest neighbors which belong to each class as in
        predict(const MatrixLookup& data, utility::Matrix& results).
        If a test and training sample pair has no variables with
        non-zero weights in common, there are no variables which can
        be used to calculate the distance between the two samples. In
        this case the distance between the two is set to infinity.
    */
    void predict(const MatrixLookupWeighted& data,
                 utility::Matrix& results) const;


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

       For KNN there is no actual training; the entire training data
       set is stored with targets. KNN only stores references to \a data
       and \a targets as copying these would make the %classifier
       slow. If the number of training samples set is smaller than k,
       k is set to the number of training samples.

       \note If \a data or \a targets go out of scope ore are
       deleted, the KNN becomes invalid and further use is undefined
       unless it is trained again.
    */
    void train(const MatrixLookup& data, const Target& targets);

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

       See train(const MatrixLookup& data, const Target& targets) for
       additional information.
    */
    void train(const MatrixLookupWeighted& data, const Target& targets);

  private:

    const MatrixLookup* data_ml_;
    const MatrixLookupWeighted* data_mlw_;
    const Target* target_;

    // The number of neighbors
    unsigned int k_;

    Distance distance_;
    NeighborWeighting weighting_;

    void calculate_unweighted(const MatrixLookup&,
                              const MatrixLookup&,
                              utility::Matrix*) const;
    void calculate_weighted(const MatrixLookupWeighted&,
                            const MatrixLookupWeighted&,
                            utility::Matrix*) const;

    void predict_common(const utility::Matrix& distances,
                        utility::Matrix& prediction) const;

  };


  /**
     \brief Concept check for a \ref concept_neighbor_weighting

     This class is intended to be used in a <a
     href="\boost_url/concept_check/using_concept_check.htm">
     BOOST_CONCEPT_ASSERT </a>

     \code
     template<class Distance>
     void some_function(double x)
     {
     BOOST_CONCEPT_ASSERT((DistanceConcept<Distance>));
     ...
     }
     \endcode

     \since New in yat 0.7
  */
  template <class T>
  class NeighborWeightingConcept
    : public boost::DefaultConstructible<T>, public boost::Assignable<T>
  {
  public:
    /**
       \brief function doing the concept test
     */
    BOOST_CONCEPT_USAGE(NeighborWeightingConcept)
    {
      T neighbor_weighting;
      utility::Vector vec;
      const utility::VectorBase& distance(vec);
      utility::VectorMutable& prediction(vec);
      std::vector<size_t> k_sorted;
      Target target;
      neighbor_weighting(distance, k_sorted, target, prediction);
    }
  private:
  };

  // template implementation

  template <typename Distance, typename NeighborWeighting>
  KNN<Distance, NeighborWeighting>::KNN()
    : SupervisedClassifier(),data_ml_(0),data_mlw_(0),target_(0),k_(3)
  {
    BOOST_CONCEPT_ASSERT((utility::DistanceConcept<Distance>));
    BOOST_CONCEPT_ASSERT((NeighborWeightingConcept<NeighborWeighting>));
  }

  template <typename Distance, typename NeighborWeighting>
  KNN<Distance, NeighborWeighting>::KNN(const Distance& dist)
    : SupervisedClassifier(), data_ml_(0), data_mlw_(0), target_(0), k_(3),
      distance_(dist)
  {
    BOOST_CONCEPT_ASSERT((utility::DistanceConcept<Distance>));
    BOOST_CONCEPT_ASSERT((NeighborWeightingConcept<NeighborWeighting>));
  }


  template <typename Distance, typename NeighborWeighting>
  KNN<Distance, NeighborWeighting>::~KNN()
  {
  }


  template <typename Distance, typename NeighborWeighting>
  void  KNN<Distance, NeighborWeighting>::calculate_unweighted
  (const MatrixLookup& training, const MatrixLookup& test,
   utility::Matrix* distances) const
  {
    for(size_t i=0; i<training.columns(); i++) {
      for(size_t j=0; j<test.columns(); j++) {
        (*distances)(i,j) = distance_(training.begin_column(i),
                                      training.end_column(i),
                                      test.begin_column(j));
        YAT_ASSERT(!std::isnan((*distances)(i,j)));
      }
    }
  }


  template <typename Distance, typename NeighborWeighting>
  void
  KNN<Distance, NeighborWeighting>::calculate_weighted
  (const MatrixLookupWeighted& training, const MatrixLookupWeighted& test,
   utility::Matrix* distances) const
  {
    for(size_t i=0; i<training.columns(); i++) {
      for(size_t j=0; j<test.columns(); j++) {
        (*distances)(i,j) = distance_(training.begin_column(i),
                                      training.end_column(i),
                                      test.begin_column(j));
        // If the distance is NaN (no common variables with non-zero weights),
        // the distance is set to infinity to be sorted as a neighbor at the end
        if(std::isnan((*distances)(i,j)))
          (*distances)(i,j)=std::numeric_limits<double>::infinity();
      }
    }
  }


  template <typename Distance, typename NeighborWeighting>
  unsigned int KNN<Distance, NeighborWeighting>::k() const
  {
    return k_;
  }

  template <typename Distance, typename NeighborWeighting>
  void KNN<Distance, NeighborWeighting>::k(unsigned int k)
  {
    k_=k;
  }


  template <typename Distance, typename NeighborWeighting>
  KNN<Distance, NeighborWeighting>*
  KNN<Distance, NeighborWeighting>::make_classifier() const
  {
    // All private members should be copied here to generate an
    // identical but untrained classifier
    KNN* knn=new KNN<Distance, NeighborWeighting>(distance_);
    knn->weighting_=this->weighting_;
    knn->k(this->k());
    return knn;
  }


  template <typename Distance, typename NeighborWeighting>
  void KNN<Distance, NeighborWeighting>::train(const MatrixLookup& data,
                                               const Target& target)
  {
    utility::yat_assert<utility::runtime_error>
      (data.columns()==target.size(),
       "KNN::train called with different sizes of target and data");
    // k has to be at most the number of training samples.
    if(data.columns()<k_)
      k_=data.columns();
    data_ml_=&data;
    data_mlw_=0;
    target_=&target;
  }

  template <typename Distance, typename NeighborWeighting>
  void KNN<Distance, NeighborWeighting>::train(const MatrixLookupWeighted& data,
                                               const Target& target)
  {
    utility::yat_assert<utility::runtime_error>
      (data.columns()==target.size(),
       "KNN::train called with different sizes of target and data");
    // k has to be at most the number of training samples.
    if(data.columns()<k_)
      k_=data.columns();
    data_ml_=0;
    data_mlw_=&data;
    target_=&target;
  }


  template <typename Distance, typename NeighborWeighting>
  void
  KNN<Distance, NeighborWeighting>::predict(const MatrixLookup& test,
                                            utility::Matrix& prediction) const
  {
    // matrix with training samples as rows and test samples as columns
    utility::Matrix* distances = 0;
    // unweighted training data
    if(data_ml_ && !data_mlw_) {
      utility::yat_assert<utility::runtime_error>
        (data_ml_->rows()==test.rows(),
         "KNN::predict different number of rows in training and test data");
      distances=new utility::Matrix(data_ml_->columns(),test.columns());
      calculate_unweighted(*data_ml_,test,distances);
    }
    else if (data_mlw_ && !data_ml_) {
      // weighted training data
      utility::yat_assert<utility::runtime_error>
        (data_mlw_->rows()==test.rows(),
         "KNN::predict different number of rows in training and test data");
      distances=new utility::Matrix(data_mlw_->columns(),test.columns());
      calculate_weighted(*data_mlw_,MatrixLookupWeighted(test),
                         distances);
    }
    else {
      throw utility::runtime_error("KNN::predict no training data");
    }

    prediction.resize(target_->nof_classes(),test.columns(),0.0);
    predict_common(*distances,prediction);
    if(distances)
      delete distances;
  }

  template <typename Distance, typename NeighborWeighting>
  void
  KNN<Distance, NeighborWeighting>::predict(const MatrixLookupWeighted& test,
                                            utility::Matrix& prediction) const
  {
    // matrix with training samples as rows and test samples as columns
    utility::Matrix* distances=0;
    // unweighted training data
    if(data_ml_ && !data_mlw_) {
      utility::yat_assert<utility::runtime_error>
        (data_ml_->rows()==test.rows(),
         "KNN::predict different number of rows in training and test data");
      distances=new utility::Matrix(data_ml_->columns(),test.columns());
      calculate_weighted(MatrixLookupWeighted(*data_ml_),test,distances);
    }
    // weighted training data
    else if (data_mlw_ && !data_ml_) {
      utility::yat_assert<utility::runtime_error>
        (data_mlw_->rows()==test.rows(),
         "KNN::predict different number of rows in training and test data");
      distances=new utility::Matrix(data_mlw_->columns(),test.columns());
      calculate_weighted(*data_mlw_,test,distances);
    }
    else {
      throw utility::runtime_error("KNN::predict no training data");
    }

    prediction.resize(target_->nof_classes(),test.columns(),0.0);
    predict_common(*distances,prediction);

    if(distances)
      delete distances;
  }

  template <typename Distance, typename NeighborWeighting>
  void KNN<Distance, NeighborWeighting>::predict_common
  (const utility::Matrix& distances, utility::Matrix& prediction) const
  {
    for(size_t sample=0;sample<distances.columns();sample++) {
      std::vector<size_t> k_index;
      utility::VectorConstView dist=distances.column_const_view(sample);
      utility::sort_smallest_index(k_index,k_,dist);
      utility::VectorView pred=prediction.column_view(sample);
      weighting_(dist,k_index,*target_,pred);
    }

    // classes for which there are no training samples should be set
    // to nan in the predictions
    for(size_t c=0;c<target_->nof_classes(); c++)
      if(!target_->size(c))
        for(size_t j=0;j<prediction.columns();j++)
          prediction(c,j)=std::numeric_limits<double>::quiet_NaN();
  }
}}} // of namespace classifier, yat, and theplu

#endif