PLearn 0.1
KNNImputationVMatrix.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // KNNImputationVMatrix.cc
00004 //
00005 // Copyright (C) 2006 Olivier Delalleau
00006 //
00007 // Redistribution and use in source and binary forms, with or without
00008 // modification, are permitted provided that the following conditions are met:
00009 //
00010 //  1. Redistributions of source code must retain the above copyright
00011 //     notice, this list of conditions and the following disclaimer.
00012 //
00013 //  2. Redistributions in binary form must reproduce the above copyright
00014 //     notice, this list of conditions and the following disclaimer in the
00015 //     documentation and/or other materials provided with the distribution.
00016 //
00017 //  3. The name of the authors may not be used to endorse or promote
00018 //     products derived from this software without specific prior written
00019 //     permission.
00020 //
00021 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00022 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00023 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00024 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00025 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00026 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031 //
00032 // This file is part of the PLearn library. For more information on the PLearn
00033 // library, go to the PLearn Web site at www.plearn.org
00034 
00035 // Authors: Olivier Delalleau
00036 
00040 #include "KNNImputationVMatrix.h"
00041 #include <plearn/vmat/SubVMatrix.h>
00042 #include <plearn/vmat/VMat_basic_stats.h>
00043 #include <plearn_learners/nearest_neighbors/ExhaustiveNearestNeighbors.h>
00044 
00045 namespace PLearn {
00046 using namespace std;
00047 
00048 PLEARN_IMPLEMENT_OBJECT(
00049     KNNImputationVMatrix,
00050     "Impute missing values in its source by their average in a neighborhood.",
00051 
00052     "Each missing value is replaced by the mean of the observed values in\n"
00053     "the neighborhood of a sample, where the neighborhood is defined by a\n"
00054     "number of nearest neighbors 'knn' that have an observed value for this\n"
00055     "same variable.\n"
00056     "If no sample can be found with an observed value, the global mean of\n"
00057     "the variable is used.\n"
00058     "\n"
00059     "In its current implementation, the neighborhood relationships can be\n"
00060     "obtained in two different manners:\n"
00061     "- from the full dataset (i.e. with no missing values), if provided by\n"
00062     "  the 'full_source' option\n"
00063     "- from another VMat (the 'neighbors' option) that lists the neighbors\n"
00064     "  of each sample by increasing order of distance (in this case, the\n"
00065     "  'full_source' option can be used to specify another VMat whose\n"
00066     "  samples are the neighbors indexed in the 'neighbors' VMat, and that\n"
00067     "  will be used to compute the local mean instead of the source VMat).\n"
00068 );
00069 
00071 // KNNImputationVMatrix //
00073 KNNImputationVMatrix::KNNImputationVMatrix():
00074     knn(5),
00075     n_train_samples(-1),
00076     report_progress(true)
00077 {}
00078 
00080 // declareOptions //
00082 void KNNImputationVMatrix::declareOptions(OptionList& ol)
00083 {
00084     declareOption(ol, "knn", &KNNImputationVMatrix::knn,
00085                              OptionBase::buildoption,
00086         "Number of nearest neighbors considered.");
00087 
00088     declareOption(ol, "neighbors", &KNNImputationVMatrix::neighbors,
00089                                    OptionBase::buildoption,
00090         "Optional VMat that, if specified, contains in element (i,j) the\n"
00091         "j-th nearest neighbor of sample i, either in 'source' or (if\n"
00092         "provided) in 'full_source'.");
00093 
00094     declareOption(ol, "full_source", &KNNImputationVMatrix::full_source,
00095                                      OptionBase::buildoption,
00096         "If 'neighbors' is not provided, this is the same dataset as\n"
00097         "'source', but with no missing values.\n"
00098         "Otherwise, this is another dataset, possibly with missing values,\n"
00099         "that corresponds to the neighbors indexed in 'neighbors'.");
00100 
00101     declareOption(ol, "n_train_samples",
00102                   &KNNImputationVMatrix::n_train_samples,
00103                   OptionBase::buildoption,
00104         "If > 0, only samples in the first 'n_train_samples' will be\n"
00105         "considered candidate nearest neighbors.");
00106 
00107     declareOption(ol, "report_progress",
00108                   &KNNImputationVMatrix::report_progress,
00109                   OptionBase::buildoption,
00110         "Whether or not to display a progress bar.");
00111 
00112     // Now call the parent class' declareOptions
00113     inherited::declareOptions(ol);
00114 }
00115 
00117 // build //
00119 void KNNImputationVMatrix::build()
00120 {
00121     inherited::build();
00122     build_();
00123 }
00124 
00126 // build_ //
00128 void KNNImputationVMatrix::build_()
00129 {
00130     if (!source)
00131         return;
00132 
00133     PLASSERT( full_source );
00134     PLASSERT( neighbors || full_source->length() == source->length() );
00135     PLASSERT( full_source->width() == source->width()  );
00136 
00137     updateMtime(source);
00138     updateMtime(full_source);
00139     updateMtime(neighbors);
00140 
00141     VMat candidates;
00142     if (neighbors)
00143         candidates = full_source ? full_source : source;
00144     else
00145         candidates = full_source;
00146    
00147     if (n_train_samples > 0)
00148         candidates = new SubVMatrix(candidates, 0, 0, n_train_samples,
00149                                                       candidates->width());
00150 
00151     // Prepare nearest neighbor learner.
00152     PP<ExhaustiveNearestNeighbors> nn_learner =
00153         new ExhaustiveNearestNeighbors();
00154     nn_learner->num_neighbors = candidates->length();
00155     nn_learner->copy_target = false;
00156     nn_learner->copy_index = true;
00157     nn_learner->build();
00158 
00159     if (!neighbors) {
00160         nn_learner->setTrainingSet(candidates);
00161         nn_learner->train();
00162     }
00163 
00164     // Compute global mean.
00165     Vec global_mean;
00166     PLearn::computeMean(candidates, global_mean);
00167 
00168     // Perform actual missing values imputation.
00169     Vec input, target, output, input_nn;
00170     if (neighbors)
00171         output.resize(neighbors->width());
00172     real weight;
00173     imputed_input.resize(0, source->inputsize());
00174     Vec imputed_row(source->inputsize());
00175     sample_index_to_imputed_index.resize(source->length());
00176     sample_index_to_imputed_index.fill(-1);
00177     PP<ProgressBar> pb;
00178     if (report_progress)
00179         pb = new ProgressBar("Imputing missing values", source->length());
00180     for (int i = 0; i < source->length(); i++) {
00181         source->getExample(i, input, target, weight);
00182         if (input.hasMissing()) {
00183             if (neighbors)
00184                 neighbors->getRow(i, output);
00185             else
00186                 nn_learner->computeOutput(input, output);
00187             for (int k = 0; k < input.length(); k++)
00188                 if (is_missing(input[k])) {
00189                     int j = 0;
00190                     int count_neighbors = 0;
00191                     real mean = 0;
00192                     while (count_neighbors < knn && j < output.length()) {
00193                         int neighbor_index = int(round(output[j]));
00194                         if (neighbors && full_source)
00195                             full_source->getExample(neighbor_index, input_nn,
00196                                                     target, weight);
00197                         else
00198                             source->getExample(neighbor_index, input_nn,
00199                                                target, weight);
00200                         if (!is_missing(input_nn[k])) {
00201                             mean += input_nn[k];
00202                             count_neighbors++;
00203                         }
00204                         j++;
00205                     }
00206                     if (count_neighbors > 0) {
00207                         // Found some neighbors with an observed value for
00208                         // variable 'k'.
00209                         mean /= count_neighbors;
00210                     } else {
00211                         mean = global_mean[k];
00212                     }
00213                     imputed_row[k] = mean;
00214                 } else
00215                     imputed_row[k] = input[k];
00216             imputed_input.appendRow(imputed_row);
00217             sample_index_to_imputed_index[i] = imputed_input.length() - 1;
00218         }
00219         if (pb)
00220             pb->update(i + 1);
00221     }
00222 
00223     // Obtain meta information from source.
00224     setMetaInfoFromSource();
00225 }
00226 
00228 // getNewRow //
00230 void KNNImputationVMatrix::getNewRow(int i, const Vec& v) const
00231 {
00232     source->getRow(i, v);
00233     if (v.hasMissing()) {
00234         int idx = sample_index_to_imputed_index[i];
00235         PLASSERT( idx >= 0 );
00236         v.subVec(0, inputsize_) << imputed_input(idx);
00237     }
00238 }
00239 
00241 // makeDeepCopyFromShallowCopy //
00243 void KNNImputationVMatrix::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00244 {
00245     inherited::makeDeepCopyFromShallowCopy(copies);
00246 
00247     deepCopyField(full_source,                      copies);
00248     deepCopyField(neighbors,                        copies);
00249     deepCopyField(imputed_input,                    copies);
00250     deepCopyField(sample_index_to_imputed_index,    copies);
00251 }
00252 
00253 } // end of namespace PLearn
00254 
00255 
00256 /*
00257   Local Variables:
00258   mode:c++
00259   c-basic-offset:4
00260   c-file-style:"stroustrup"
00261   c-file-offsets:((innamespace . 0)(inline-open . 0))
00262   indent-tabs-mode:nil
00263   fill-column:79
00264   End:
00265 */
00266 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines