source: trunk/c++_tools/utility/NNI.cc @ 675

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

References #83. Changing project name to yat. Compilation will fail in this revision.

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