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

// $Id: NNI.cc 687 2006-10-16 23:51:10Z jari $

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

  This file is part of the yat library, http://lev.thep.lu.se/trac/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 u_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<u_int,double> >
  NNI::calculate_distances(const u_int row) const
  {
    std::vector<std::pair<u_int,double> > distance;
    for (size_t i=0; i<data_.rows(); i++)
      if (i!=row) {
        double contribs=0;
        std::pair<u_int,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;
  }



  // Contributing nearest neighbours are added up to the user set
  // number, and neighbours are disqualified if their element (column)
  // weight is zero
  std::vector<u_int> 
  NNI::nearest_neighbours(const u_int column,
                          const std::vector<std::pair<u_int,double> >& d) const
  {
    std::vector<u_int> index;
    double contribs=0;
    for (u_int 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