KNN.h

#ifndef _theplu_yat_classifier_knn_ 
#define _theplu_yat_classifier_knn_ 

// $Id: KNN.h 2384 2010-12-22 14:03:36Z 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 {

  template <typename Distance, typename NeighborWeighting=KNN_Uniform>
  class KNN : public SupervisedClassifier
  {
    
  public:
    KNN(void);


    KNN(const Distance&);


    virtual ~KNN();
    
    
    unsigned int k() const;

    void k(unsigned int k_in);


    KNN<Distance,NeighborWeighting>* make_classifier(void) const;
    
    void predict(const MatrixLookup& data , utility::Matrix& results) const;

    void predict(const MatrixLookupWeighted& data, 
                 utility::Matrix& results) const;


    void train(const MatrixLookup& data, const Target& targets);
    
    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;

  };
  
  
  template <class T>
  class NeighborWeightingConcept 
    : public boost::DefaultConstructible<T>, public boost::Assignable<T>
  {
  public:
    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