source: trunk/yat/utility/NNI.cc @ 1275

// $Id: NNI.cc 1275 2008-04-11 06:10:12Z jari $

/*
  Copyright (C) 2004 Jari Häkkinen
  Copyright (C) 2005 Peter Johansson
  Copyright (C) 2006 Jari Häkkinen
  Copyright (C) 2007 Jari Häkkinen, Peter Johansson
  Copyright (C) 2008 Peter Johansson

  This file is part of the yat library, http://trac.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 2 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 this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  02111-1307, USA.
*/

#include "NNI.h"
#include "stl_utility.h"

#include <algorithm>
#include <cmath>
#include <fstream>

namespace theplu {
namespace yat {
namespace utility {

  // For a discussion and motivation for various algorithm
  // implementations here see the paper cited in the class definition
  // documentation.
  NNI::NNI(const utility::Matrix& matrix,const utility::Matrix& weight,
           const unsigned int neighbours)
    : data_(matrix), imputed_data_(matrix), neighbours_(neighbours),
      weight_(weight)
  {
  }


  // d_{ij}^2=\frac {\sum_{k=1,C} w_{ik} w_{jk} (x_{ik}-x_{jk})^2 }
  //                {\sum_{k=l,C} w_{ik} w_{jk} }
  // where C is the number of columns
  std::vector<std::pair<size_t,double> >
  NNI::calculate_distances(const size_t row) const
  {
    std::vector<std::pair<size_t,double> > distance;
    for (size_t i=0; i<data_.rows(); i++)
      if (i!=row) {
        double contribs=0;
        std::pair<size_t,double> this_distance(i,0.0);
        for (size_t j=0; j<data_.columns(); j++)
          // 0 contribution for missing values
          if (weight_(i,j) && weight_(row,j)) {
            double weight_factor=weight_(i,j)*weight_(row,j);
            this_distance.second+=( weight_factor *
                                    (data_(i,j)-data_(row,j)) *
                                    (data_(i,j)-data_(row,j)) );
            contribs+=weight_factor;
          }
        if (contribs) { // ignore lines without any contributions
          this_distance.second=sqrt(this_distance.second/contribs);
          distance.push_back(this_distance);
        }
      }
    return distance;
  }


  const utility::Matrix& NNI::imputed_data(void) const
  {
    return imputed_data_;
  }


  const std::vector<size_t>& NNI::not_imputed(void) const
  {
    return not_imputed_;
  }


  // Contributing nearest neighbours are added up to the user set
  // number, and neighbours are disqualified if their element (column)
  // weight is zero
  std::vector<size_t> 
  NNI::nearest_neighbours(const size_t column,
                          const std::vector<std::pair<size_t,double> >& d) const
  {
    std::vector<size_t> index;
    double contribs=0;
    for (size_t i=0; ((i<d.size()) &&
                     (contribs+=weight_(d[i].first,column))<=neighbours_); i++)
      if (weight_(d[i].first,column))
        index.push_back(i);
    return index;
  }

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