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

Last change on this file since 1486 was 1486, checked in by Jari Häkkinen, 13 years ago

Addresses #436.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 3.1 KB
Line 
1// $Id: NNI.cc 1486 2008-09-09 21:17:19Z jari $
2
3/*
4  Copyright (C) 2004 Jari Häkkinen
5  Copyright (C) 2005 Peter Johansson
6  Copyright (C) 2006 Jari Häkkinen
7  Copyright (C) 2007 Jari Häkkinen, Peter Johansson
8  Copyright (C) 2008 Peter Johansson
9
10  This file is part of the yat library, http://dev.thep.lu.se/yat
11
12  The yat library is free software; you can redistribute it and/or
13  modify it under the terms of the GNU General Public License as
14  published by the Free Software Foundation; either version 3 of the
15  License, or (at your option) any later version.
16
17  The yat library is distributed in the hope that it will be useful,
18  but WITHOUT ANY WARRANTY; without even the implied warranty of
19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20  General Public License for more details.
21
22  You should have received a copy of the GNU General Public License
23  along with this program; if not, write to the Free Software
24  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
25  02111-1307, USA.
26*/
27
28#include "NNI.h"
29#include "stl_utility.h"
30
31#include <algorithm>
32#include <cmath>
33#include <fstream>
34
35namespace theplu {
36namespace yat {
37namespace utility {
38
39  // For a discussion and motivation for various algorithm
40  // implementations here see the paper cited in the class definition
41  // documentation.
42  NNI::NNI(const utility::Matrix& matrix,const utility::Matrix& weight,
43           const unsigned int neighbours)
44    : data_(matrix), imputed_data_(matrix), neighbours_(neighbours),
45      weight_(weight)
46  {
47  }
48
49
50  // d_{ij}^2=\frac {\sum_{k=1,C} w_{ik} w_{jk} (x_{ik}-x_{jk})^2 }
51  //                {\sum_{k=l,C} w_{ik} w_{jk} }
52  // where C is the number of columns
53  std::vector<std::pair<size_t,double> >
54  NNI::calculate_distances(const size_t row) const
55  {
56    std::vector<std::pair<size_t,double> > distance;
57    for (size_t i=0; i<data_.rows(); i++)
58      if (i!=row) {
59        double contribs=0;
60        std::pair<size_t,double> this_distance(i,0.0);
61        for (size_t j=0; j<data_.columns(); j++)
62          // 0 contribution for missing values
63          if (weight_(i,j) && weight_(row,j)) {
64            double weight_factor=weight_(i,j)*weight_(row,j);
65            this_distance.second+=( weight_factor *
66                                    (data_(i,j)-data_(row,j)) *
67                                    (data_(i,j)-data_(row,j)) );
68            contribs+=weight_factor;
69          }
70        if (contribs) { // ignore lines without any contributions
71          this_distance.second=sqrt(this_distance.second/contribs);
72          distance.push_back(this_distance);
73        }
74      }
75    return distance;
76  }
77
78
79  const utility::Matrix& NNI::imputed_data(void) const
80  {
81    return imputed_data_;
82  }
83
84
85  const std::vector<size_t>& NNI::not_imputed(void) const
86  {
87    return not_imputed_;
88  }
89
90
91  // Contributing nearest neighbours are added up to the user set
92  // number, and neighbours are disqualified if their element (column)
93  // weight is zero
94  std::vector<size_t> 
95  NNI::nearest_neighbours(const size_t column,
96                          const std::vector<std::pair<size_t,double> >& d) const
97  {
98    std::vector<size_t> index;
99    double contribs=0;
100    for (size_t i=0; ((i<d.size()) &&
101                     (contribs+=weight_(d[i].first,column))<=neighbours_); i++)
102      if (weight_(d[i].first,column))
103        index.push_back(i);
104    return index;
105  }
106
107}}} // of namespace utility, yat, and theplu
Note: See TracBrowser for help on using the repository browser.