source: trunk/c++_tools/utility/NNI.h @ 649

#ifndef _theplu_utility_nni_
#define _theplu_utility_nni_ 

// $Id: NNI.h 649 2006-09-15 14:03:31Z jari $

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

  This file is part of the thep c++ tools library,
                                http://lev.thep.lu.se/trac/c++_tools

  The c++ tools 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 c++ tools 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 <iostream>
#include <utility>
#include <vector>

#include <c++_tools/utility/matrix.h>

namespace theplu {
namespace utility {

  ///
  /// NNI is an abstract base class defining the interface for nearest
  /// neighbour imputation (NNI) algorithms.
  ///
  /// NNI algorithms implemented here is discussed in documents
  /// created in the WeNNI project. This document will be released for
  /// public access, and the necessary information for retrieving that
  /// document will be provided here.
  ///
  /// Short introduction to NNI is that one may want to improve
  /// (correct) uncertain data. Here, the data to be imputed is stored in a
  /// matrix where rows similar to each other are used to adjust
  /// uncertain data. The data matrix is accompanied by a weight
  /// (uncertainty) matrix defining what data is to be considered as
  /// 'certain' and what data is uncertain. The weight matrix can be
  /// binary with 1's indicating that the data does not need
  /// corrections, whereas a 0 means that the data should be replaced
  /// by an imputed value. Naturally, the weight matrix can also be
  /// continuous where values between 0 and 1 defines how certain a
  /// data element is.
  ///
  /// The imputation depends on how similarity of rows of data is
  /// defined and on the number of closest neighbours (here; rows) to
  /// use in the imputation can be set.
  ///
  /// Implementation issues
  ///
  /// The current implementation treats rows where all data are tagged
  /// are completely uncertain, i.e. all weights are zero, by
  /// ignoring these lines in nearest neighbourhood
  /// calculations. Importantly, this type of data are not changed
  /// (imputed) either since there is no close neighbourhood defined
  /// for this data.
  ///
  /// Rows that is completely identical in an imputation algorithm
  /// sense will give problems since the distance between will usually
  /// become zero. This is solved by setting zero distance to a small
  /// number. Identical rows in this context are basically a
  /// comparison between elements with non-zero uncertainty weights
  /// only, and all these elements are equal. Zero weight elements are
  /// not used in the comparison since these are considered as
  /// non/sense values.
  ///
  class NNI
  {
  public:

    ///
    /// Base constructor for the nearest neighbour imputation
    /// algorithms.
    ///
    NNI(const utility::matrix& matrix,const utility::matrix& weight,
        const u_int neighbours);

    virtual ~NNI(void) {};

    ///
    /// Function doing the imputation.
    ///
    /// @return number of rows not imputed
    ///
    virtual u_int estimate(void)=0;

    ///
    /// @return A const reference to the modified data.
    ///
    const utility::matrix& imputed_data(void) const { return imputed_data_; }

    ///
    /// @return indices of rows in data matrix not imputed
    ///
    inline std::vector<size_t> not_imputed(void) const { return not_imputed_; }

  protected:
    /**
       \f$ 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} } \f$ where C is the number of columns
    */
    std::vector<std::pair<u_int,double> > calculate_distances(const u_int) const;
    /// 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> nearest_neighbours(const u_int,
                             const std::vector<std::pair<u_int,double> >&) const;
    ///
    /// original data matrix
    ///
    const utility::matrix& data_;

    ///
    /// data after imputation
    ///
    utility::matrix imputed_data_;

    ///
    /// number of neighbor to use
    ///
    u_int neighbours_;

    ///
    /// which rows are not imputed due to lack of data
    ///
    std::vector<size_t> not_imputed_;

    ///
    /// weight matrix
    ///
    const utility::matrix& weight_;
  };

}} // of namespace utility and namespace theplu

#endif