PLearn 0.1
|
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 :