PLearn 0.1
MeanMedianModeImputationVMatrix.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PLearn (A C++ Machine Learning Library)
00004 // Copyright (C) 1998 Pascal Vincent
00005 // Copyright (C) 1999-2001 Pascal Vincent, Yoshua Bengio, Rejean Ducharme and University of Montreal
00006 // Copyright (C) 2002 Pascal Vincent, Julien Keable, Xavier Saint-Mleux
00007 // Copyright (C) 2003 Olivier Delalleau
00008 //
00009 // Redistribution and use in source and binary forms, with or without
00010 // modification, are permitted provided that the following conditions are met:
00011 // 
00012 //  1. Redistributions of source code must retain the above copyright
00013 //     notice, this list of conditions and the following disclaimer.
00014 // 
00015 //  2. Redistributions in binary form must reproduce the above copyright
00016 //     notice, this list of conditions and the following disclaimer in the
00017 //     documentation and/or other materials provided with the distribution.
00018 // 
00019 //  3. The name of the authors may not be used to endorse or promote
00020 //     products derived from this software without specific prior written
00021 //     permission.
00022 // 
00023 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00024 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00025 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00026 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00027 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00028 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00029 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00030 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00031 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00032 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00033 // 
00034 // This file is part of the PLearn library. For more information on the PLearn
00035 // library, go to the PLearn Web site at www.plearn.org
00036 
00037 
00038 /* *******************************************************************    
00039    * $Id: MeanMedianModeImputationVMatrix.cc 3658 2005-07-06 20:30:15  Godbout $
00040    ******************************************************************* */
00041 
00042 
00043 #include "MeanMedianModeImputationVMatrix.h"
00044 #include "MemoryVMatrix.h"
00045 
00046 namespace PLearn {
00047 using namespace std;
00048 
00051 PLEARN_IMPLEMENT_OBJECT(
00052   MeanMedianModeImputationVMatrix,
00053   "VMat class to impute the observed variable mean to replace missing values in the source matrix.",
00054   "This class will replace missing values in the underlying dataset with the mean, median or mode observed on the train set.\n"
00055   "The imputed value is based on the imputation instruction option.\n"
00056   );
00057 
00058 MeanMedianModeImputationVMatrix::MeanMedianModeImputationVMatrix()
00059   : number_of_train_samples_to_use(0.0),
00060     missing_field_error(true)
00061 {
00062 }
00063 
00064 MeanMedianModeImputationVMatrix::~MeanMedianModeImputationVMatrix()
00065 {
00066 }
00067 
00068 void MeanMedianModeImputationVMatrix::declareOptions(OptionList &ol)
00069 {
00070   declareOption(ol, "train_set", &MeanMedianModeImputationVMatrix::train_set, OptionBase::buildoption, 
00071                 "A referenced train set.\n"
00072                 "The mean, median or mode is computed with the observed values in this data set.\n"
00073                 "It is used in combination with the option number_of_train_samples_to_use\n");
00074 
00075   declareOption(ol, "number_of_train_samples_to_use", &MeanMedianModeImputationVMatrix::number_of_train_samples_to_use, OptionBase::buildoption, 
00076                 "The number of samples from the train set that will be examined to compute the required statistic for each variable.\n" 
00077                 "If equal to zero, all the samples from the train set are used to calculated the statistics.\n"
00078                 "If it is a fraction between 0 and 1, this proportion of the samples are used.\n"
00079                 "If greater or equal to 1, the integer portion is interpreted as the number of samples to use.");
00080       
00081   declareOption(ol, "imputation_spec", &MeanMedianModeImputationVMatrix::imputation_spec, OptionBase::buildoption, 
00082                 "Pairs of instruction of the form field_name : mean | median | mode | none | err.\n"
00083                 " -mean  : put the mean of the field if one value is missing\n"
00084                 " -median: put the median of the field if one value is missing\n"
00085                 " -mode  : put the mode(most frequent value) of the field if one value is missing\n"
00086                 " -none  : let the missing value in this field\n"
00087                 " -err   : make it an error to have a missing value in this field"
00088                 );
00089 
00090   declareOption(ol, "missing_field_error", &MeanMedianModeImputationVMatrix::missing_field_error,
00091                 OptionBase::buildoption, 
00092                 "If True, will generate an error if some field in the"
00093                 " imputation_spec are present but not in the source. Otherwise"
00094                 " will generate a warning. This also applies for regex spec.");
00095 
00096   declareOption(ol, "default_instruction", &MeanMedianModeImputationVMatrix::default_instruction,
00097                 OptionBase::buildoption, 
00098                 "The default instruction to use. If empty(default), will generate"
00099                 " an error is some source variable don't have an one in imputation_spec.");
00100 
00101   declareOption(ol, "variable_mean", &MeanMedianModeImputationVMatrix::variable_mean, OptionBase::learntoption, 
00102                 "The vector of variable means observed from the train set.");
00103 
00104   declareOption(ol, "variable_median", &MeanMedianModeImputationVMatrix::variable_median, OptionBase::learntoption, 
00105                 "The vector of variable medians observed from the train set.");
00106 
00107   declareOption(ol, "variable_mode", &MeanMedianModeImputationVMatrix::variable_mode, OptionBase::learntoption, 
00108                 "The vector of variable modes observed from the train set.");
00109 
00110   declareOption(ol, "variable_imputation_instruction", &MeanMedianModeImputationVMatrix::variable_imputation_instruction, OptionBase::learntoption, 
00111                 "The vector of coded instruction for each variables.");
00112 
00113   inherited::declareOptions(ol);
00114 
00115   declareOption(ol, "length", &MeanMedianModeImputationVMatrix::length_,
00116                 OptionBase::nosave,
00117                 "The number of example. Computed each time from source.");
00118   
00119   redeclareOption(ol, "inputsize", &MeanMedianModeImputationVMatrix::inputsize_,
00120                   OptionBase::nosave,
00121                   "Taken from source in  MeanMedianModeImputationVMatrix.");
00122   
00123   redeclareOption(ol, "targetsize",
00124                   &MeanMedianModeImputationVMatrix::targetsize_,
00125                   OptionBase::nosave,
00126                   "Taken from source in MeanMedianModeImputationVMatrix.");
00127   
00128   redeclareOption(ol, "weightsize",
00129                   &MeanMedianModeImputationVMatrix::weightsize_,
00130                   OptionBase::nosave,
00131                   "Taken from source in MeanMedianModeImputationVMatrix.");
00132   
00133   redeclareOption(ol, "extrasize", &MeanMedianModeImputationVMatrix::extrasize_,
00134                   OptionBase::nosave,
00135                   "Taken from source in MeanMedianModeImputationVMatrix.");
00136   
00137   redeclareOption(ol, "width", &MeanMedianModeImputationVMatrix::width_,
00138                   OptionBase::nosave,
00139                   "Taken from source in MeanMedianModeImputationVMatrix.");
00140 }
00141 
00142 void MeanMedianModeImputationVMatrix::build()
00143 {
00144   inherited::build();
00145   build_();
00146 }
00147 
00148 void MeanMedianModeImputationVMatrix::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00149 {
00150   deepCopyField(train_set, copies);
00151   deepCopyField(number_of_train_samples_to_use, copies);
00152   deepCopyField(imputation_spec, copies);
00153   deepCopyField(variable_mean, copies);
00154   deepCopyField(variable_median, copies);
00155   deepCopyField(variable_mode, copies);
00156   deepCopyField(variable_imputation_instruction, copies);
00157   inherited::makeDeepCopyFromShallowCopy(copies);
00158 }
00159 
00160 real MeanMedianModeImputationVMatrix::get(int i, int j) const
00161 { 
00162   real variable_value = source->get(i, j);
00163   if (!is_missing(variable_value)) return variable_value;
00164   else if (variable_imputation_instruction[j] == 1) return variable_mean[j];
00165   else if (variable_imputation_instruction[j] == 2) return variable_median[j];
00166   else if (variable_imputation_instruction[j] == 3) return variable_mode[j];
00167   else if (variable_imputation_instruction[j] == 4) return variable_value;
00168   else if (variable_imputation_instruction[j] == 5)
00169     return MISSING_VALUE;//PLERROR("");//PLERROR("In MeanMedianModeImputationVMatrix::get(%d,%d) - the value is"
00170       //           " missing and have a instruction err!",i,j);
00171   else
00172     PLERROR("In MeanMedianModeImputationVMatrix::get(%d,%d) - "
00173             "unknow variable_imputation_instruction value of %d",i,j,
00174             variable_imputation_instruction[j] );
00175   //Should not be executed, to remove a warning
00176   return MISSING_VALUE;
00177 }
00178 
00179 void MeanMedianModeImputationVMatrix::getSubRow(int i, int j, Vec v) const
00180 {  
00181   source->getSubRow(i, j, v);
00182   for (int source_col = 0; source_col < v->length(); source_col++) 
00183     if (is_missing(v[source_col])){
00184       if (variable_imputation_instruction[source_col + j] == 1)
00185         v[source_col] = variable_mean[source_col + j];
00186       else if (variable_imputation_instruction[source_col + j] == 2)
00187         v[source_col] = variable_median[source_col + j];
00188       else if (variable_imputation_instruction[source_col + j] == 3)
00189         v[source_col] = variable_mode[source_col + j];
00190       else if (variable_imputation_instruction[source_col + j] == 4)
00191         ;//do nothing
00192       else if (variable_imputation_instruction[source_col + j] == 5)
00193         return PLERROR("In MeanMedianModeImputationVMatrix::getSubRow(%d,%d) - the value is"
00194                        " missing and have a instruction err!",i,j);
00195       else
00196         PLERROR("In MeanMedianModeImputationVMatrix::getSubRow(%d,%d, Vec) - "
00197                 "unknow variable_imputation_instruction value of %d",i,j,
00198                 variable_imputation_instruction[source_col + j] );
00199     }
00200 
00201 }
00202 
00203 void MeanMedianModeImputationVMatrix::getRow(int i, Vec v) const
00204 {  
00205   source-> getRow(i, v);
00206   for (int source_col = 0; source_col < v->length(); source_col++)
00207     if (is_missing(v[source_col])){
00208       if (variable_imputation_instruction[source_col] == 1)
00209         v[source_col] = variable_mean[source_col];
00210       else if (variable_imputation_instruction[source_col] == 2)
00211         v[source_col] = variable_median[source_col];
00212       else if (variable_imputation_instruction[source_col] == 3)
00213         v[source_col] = variable_mode[source_col]; 
00214       else if (variable_imputation_instruction[source_col] == 4)
00215         ;//do nothing
00216       else if (variable_imputation_instruction[source_col] == 5)
00217         return PLERROR("In MeanMedianModeImputationVMatrix::getRow(%d) -"
00218                        " the value is missing for column %s"
00219                        " and have a instruction err!",i, fieldName(source_col).c_str());
00220       else
00221         PLERROR("In MeanMedianModeImputationVMatrix::getRow(%d, Vec) - "
00222                 "unknow variable_imputation_instruction value of %d",i,
00223                 variable_imputation_instruction[source_col] );
00224     }
00225 }
00226 
00227 void MeanMedianModeImputationVMatrix::getColumn(int i, Vec v) const
00228 {  
00229   source-> getColumn(i, v);
00230   for (int source_row = 0; source_row < v->length(); source_row++)
00231     if (is_missing(v[source_row])){
00232       if (variable_imputation_instruction[i] == 1) v[source_row] = variable_mean[i];
00233       else if (variable_imputation_instruction[i] == 2) v[source_row] = variable_median[i];
00234       else if (variable_imputation_instruction[i] == 3) v[source_row] = variable_mode[i];
00235       else if (variable_imputation_instruction[i] == 4)
00236         ;//do nothing
00237       else if (variable_imputation_instruction[i] == 5)
00238         return PLERROR("In MeanMedianModeImputationVMatrix::getColumn(%d) - the value is"
00239                        " missing and have a instruction err!",i);
00240       else
00241         PLERROR("In MeanMedianModeImputationVMatrix::getRow(%d, Vec) - "
00242                 "unknow variable_imputation_instruction value of %d",i,
00243                 variable_imputation_instruction[i] );
00244     }
00245 }
00246 
00247 
00248 
00249 void MeanMedianModeImputationVMatrix::build_()
00250 {
00251     if (!source) PLERROR("In MeanMedianModeImputationVMatrix:: source vmat must be supplied");
00252     if (!train_set)
00253       train_set = source;
00254 
00255     updateMtime(train_set);
00256     updateMtime(source);
00257 
00258     int train_length = train_set->length();
00259     int train_width = train_set->width();
00260 
00261     if (number_of_train_samples_to_use > 0.0){
00262         if (number_of_train_samples_to_use < 1.0) train_length = (int) (number_of_train_samples_to_use * (real) train_length);
00263         else train_length = (int) number_of_train_samples_to_use;
00264     }
00265     if (train_length > train_set->length()) train_length = train_set->length();
00266     if(train_length < 1) 
00267       PLERROR("In MeanMedianModeImputationVMatrix::length of the number of"
00268               " train samples to use must be at least 1, got: %i", train_length);
00269 
00270     if(train_set->inputsize() < 1) 
00271       PLERROR("In MeanMedianModeImputationVMatrix::inputsize of the train vmat"
00272               " must be supplied, got : %i", train_set->inputsize());
00273     source->compatibleSizeError(train_set);
00274     setMetaInfoFrom(source);
00275 
00276     train_field_names.resize(train_width);
00277     train_field_names = train_set->fieldNames();
00278 
00279     declareFieldNames(train_field_names);
00280     variable_mean.resize(train_width);
00281     variable_median.resize(train_width);
00282     variable_mode.resize(train_width);
00283     variable_imputation_instruction.resize(train_width);
00284 
00285     if(default_instruction.empty()) variable_imputation_instruction.clear();
00286     else if (default_instruction == "mean") variable_imputation_instruction.fill(1);
00287     else if (default_instruction == "median") variable_imputation_instruction.fill(2);
00288     else if (default_instruction == "mode") variable_imputation_instruction.fill(3);
00289     else if (default_instruction == "none") variable_imputation_instruction.fill(4);
00290     else if (default_instruction == "err") variable_imputation_instruction.fill(5);
00291     else
00292       PLERROR("In MeanMedianModeImputationVMatrix: unsupported default_imputation instruction: %s ",
00293               default_instruction.c_str());
00294 
00295 
00296     TVec<string> nofields;
00297     
00298     //We sho
00299     TVec<pair<string,string> > save_imputation_spec = imputation_spec;
00300     imputation_spec = save_imputation_spec.copy();
00301     TVec<string> not_expanded;
00302     for (int spec_col = 0; spec_col < imputation_spec.size(); spec_col++)
00303     {
00304         int train_col;
00305         string fname = imputation_spec[spec_col].first;
00306         for (train_col = 0; train_col < train_width; train_col++)
00307         {
00308           if (fname == train_field_names[train_col]) break;
00309         }
00310         char last_char = fname[fname.size()-1];
00311         if (train_col >= train_width && last_char!='*'){
00312           nofields.append(fname.c_str());
00313           continue;
00314         }
00315         else if(train_col >= train_width && last_char=='*')
00316         {
00317           bool expended = false;
00318           fname.resize(fname.size()-1);//remove the last caracter (*)
00319           for(train_col = 0; train_col < train_width; train_col++)
00320           {
00321             if(string_begins_with(train_field_names[train_col],fname))
00322             {
00323               pair<string,string> n=make_pair(train_field_names[train_col],
00324                                               imputation_spec[spec_col].second);
00325 //                    perr<<"expanding "<<train_field_names[train_col] << " to " << n <<endl;
00326               
00327               imputation_spec.append(n);
00328               expended = true;
00329             }
00330           }
00331           if(!expended){
00332             not_expanded.append(imputation_spec[spec_col].first);
00333           }
00334           continue;
00335         }
00336         if (imputation_spec[spec_col].second == "mean") variable_imputation_instruction[train_col] = 1;
00337         else if (imputation_spec[spec_col].second == "median") variable_imputation_instruction[train_col] = 2;
00338         else if (imputation_spec[spec_col].second == "mode") variable_imputation_instruction[train_col] = 3;
00339         else if (imputation_spec[spec_col].second == "none") variable_imputation_instruction[train_col] = 4;
00340         else if (imputation_spec[spec_col].second == "err") variable_imputation_instruction[train_col] = 5;
00341         else
00342           PLERROR("In MeanMedianModeImputationVMatrix: unsupported imputation instruction: %s : %s",
00343                      (imputation_spec[spec_col].first).c_str(), (imputation_spec[spec_col].second).c_str());
00344     }
00345     if(not_expanded.length()>0){
00346       PLWARN_ERR(!missing_field_error,
00347                  "In MeanMedianModeImputationVMatrix::build_() - "
00348                  "For %d spec, we didn't found partial match '%s'",
00349                  not_expanded.length(), tostring(not_expanded).c_str());
00350     }
00351         
00352 
00353     imputation_spec = save_imputation_spec;
00354 
00355     if(nofields.length()>0)
00356       PLWARN_ERR(!missing_field_error,
00357                  "In MeanMedianModeImputationVMatrix::build_() Their is %d"
00358                  " fields in the imputation_spec that are not in train set:"
00359                  " '%s'",nofields.length(),
00360                  tostring(nofields).c_str());
00361 
00362     TVec<string> no_instruction;
00363     for(int i = 0;i<variable_imputation_instruction.size();i++)
00364       if(variable_imputation_instruction[i]==0)
00365         no_instruction.append(train_field_names[i]);
00366     if(no_instruction.size()>0)
00367       PLERROR("In MeanMedianModeImputationVMatrix::build_() In the source"
00368               " VMatrix their is %d field(s) that do not have instruction: '%s'.",
00369               no_instruction.size(),tostring(no_instruction).c_str());
00370 
00371 }
00372 void MeanMedianModeImputationVMatrix::setMetaDataDir(const PPath& the_metadatadir)
00373 {
00374   inherited::setMetaDataDir(the_metadatadir);
00375   if(!train_set->hasMetaDataDir() && !hasMetaDataDir())
00376     PLERROR("In MeanMedianModeImputationVMatrix::setMetaDataDir() - the "
00377             " train_set should have a metadata dir or we should have one!");
00378   else if(!train_set->hasMetaDataDir())
00379     train_set->setMetaDataDir(getMetaDataDir()/"train_set");
00380   
00381   PPath train_metadata = train_set->getMetaDataDir();
00382   PPath mean_median_mode_file_name = train_metadata + "mean_median_mode_file.pmat";
00383 
00384   bool uptodate = train_set->isUpToDate(mean_median_mode_file_name,false)
00385     && source->isUpToDate(mean_median_mode_file_name,false);
00386 
00387   train_set->lockMetaDataDir();
00388   try{
00389     if (!uptodate)
00390       {
00391         computeMeanMedianModeVectors();
00392         createMeanMedianModeFile(mean_median_mode_file_name);
00393       }
00394     else loadMeanMedianModeFile(mean_median_mode_file_name);
00395   }catch(const PLearnError& e){
00396     train_set->unlockMetaDataDir();
00397 
00398     //we erase the file if we are creating it
00399     // as it can be partilly saved.
00400     if(!uptodate && isfile(mean_median_mode_file_name))
00401       rm(mean_median_mode_file_name);
00402     throw e;
00403   }
00404   train_set->unlockMetaDataDir();
00405 }
00406 
00407 void MeanMedianModeImputationVMatrix::createMeanMedianModeFile(PPath file_name)
00408 {
00409     mean_median_mode_file = new FileVMatrix(file_name, 3, train_field_names);
00410     mean_median_mode_file->setMetaInfoFrom(this);
00411     mean_median_mode_file->putRow(0, variable_mean);
00412     mean_median_mode_file->putRow(1, variable_median);
00413     mean_median_mode_file->putRow(2, variable_mode);
00414 }
00415 
00416 void MeanMedianModeImputationVMatrix::loadMeanMedianModeFile(PPath file_name)
00417 {
00418     train_set->isUpToDate(file_name,true,true);
00419 
00420     mean_median_mode_file = new FileVMatrix(file_name);
00421     compatibleSizeError(mean_median_mode_file, "Bad file "+file_name);
00422     if(mean_median_mode_file->fieldNames()!=fieldNames())
00423       PLERROR("In MeanMedianModeImputationVMatrix::loadMeanMedianModeFile(%s) -"
00424               " The file don't have the same field name as the source. "
00425               "Delete it to have it recreated it automatically.",
00426               file_name.c_str());
00427     mean_median_mode_file->getRow(0, variable_mean);
00428     mean_median_mode_file->getRow(1, variable_median);
00429     mean_median_mode_file->getRow(2, variable_mode);
00430 }
00431 
00432 VMat MeanMedianModeImputationVMatrix::getMeanMedianModeFile()
00433 {
00434     return mean_median_mode_file;
00435 }
00436 
00437 void MeanMedianModeImputationVMatrix::computeMeanMedianModeVectors()
00438 {
00439     TVec<int> variable_present_count(width_);
00440     TVec<int> variable_mode_count(width_);
00441     variable_mean.clear();
00442     variable_median.clear();
00443     variable_mode.clear();
00444     variable_present_count.clear();
00445     variable_mode_count.clear();
00446     Vec variable_vec(train_set->length());
00447     cout << fixed << showpoint;
00448     ProgressBar* pb = 0;
00449     pb = new ProgressBar("Computing the mean, median and mode vectors", width_);
00450     VMat train_set_mem = new MemoryVMatrix(train_set);
00451     for (int train_col = 0; train_col < width_; train_col++)
00452     {
00453         real current_value = 0.0;
00454         int current_value_count = 0;
00455         train_set_mem->getColumn(train_col, variable_vec);
00456         sortColumn(variable_vec, 0, train_set_mem->length());
00457         for (int train_row = 0; train_row < train_set_mem->length(); train_row++)
00458         {
00459             if (is_missing(variable_vec[train_row]))
00460               continue;
00461             variable_mean[train_col] += variable_vec[train_row];
00462             variable_present_count[train_col] += 1;
00463             if (variable_vec[train_row] != current_value)
00464             {
00465                 if (current_value_count > variable_mode_count[train_col])
00466                 {
00467                     variable_mode[train_col] = current_value;
00468                     variable_mode_count[train_col] = current_value_count;
00469                 }
00470                 current_value_count = 0;
00471                 current_value = variable_vec[train_row];
00472             }
00473             current_value_count += 1;
00474         }
00475         if (variable_present_count[train_col] > 0)
00476         {
00477             variable_mean[train_col] = variable_mean[train_col] / variable_present_count[train_col];
00478             variable_median[train_col] = variable_vec[(variable_present_count[train_col] / 2)];
00479         }
00480         if (current_value_count > variable_mode_count[train_col])
00481         {
00482             variable_mode[train_col] = current_value;
00483             variable_mode_count[train_col] = current_value_count;
00484         }
00485         pb->update( train_col );
00486         /*
00487         cout << "col: "         << setw(3)  <<                     train_col
00488              << " present: "    << setw(5)  <<                     variable_present_count[train_col]
00489              << " missing: "    << setw(5)  <<                     variable_missing_count[train_col]
00490              << " mean: "       << setw(11) << setprecision(2) <<  variable_mean[train_col]
00491              << " median: "     << setw(11) << setprecision(2) <<  variable_median[train_col]
00492              << " mode count: " << setw(5)  <<                     variable_mode_count[train_col]
00493              << " mode: "       << setw(11) << setprecision(2) <<  variable_mode[train_col]
00494              << " name: "       <<                                 train_field_names[train_col]
00495              << endl;
00496         */
00497     }
00498     delete pb;
00499 }
00500 
00501 void MeanMedianModeImputationVMatrix::sortColumn(Vec input_vec, int start, int end)
00502 {
00503   int start_index = start;
00504   int end_index = end - 1;
00505   int forward_index;
00506   int backward_index;
00507   int stack_index = -1;
00508   real pivot_value;
00509   TVec<int> stack(50);
00510   for (;;)
00511   {
00512     if ((end_index - start_index) < 7)
00513     {
00514       if (end_index > start_index)
00515       {
00516         sortSmallSubArray(input_vec, start_index, end_index);
00517       }
00518       if (stack_index < 0)
00519       {
00520         break;
00521       }
00522       end_index = stack[stack_index--];
00523       start_index = stack[stack_index--];
00524     }
00525     else
00526     {
00527       swapValues(input_vec, start_index + 1, (start_index + end_index) / 2);
00528       if (compare(input_vec[start_index], input_vec[end_index]) > 0.0) swapValues(input_vec, start_index, end_index);
00529       if (compare(input_vec[start_index + 1], input_vec[end_index]) > 0.0) swapValues(input_vec, start_index + 1, end_index);
00530       if (compare(input_vec[start_index], input_vec[start_index + 1]) > 0.0) swapValues(input_vec, start_index, start_index + 1);
00531       forward_index = start_index + 1;
00532       backward_index = end_index;
00533       pivot_value = input_vec[start_index + 1];
00534       for (;;)
00535       {
00536         do forward_index++; while (compare(input_vec[forward_index], pivot_value) < 0.0);
00537         do backward_index--; while (compare(input_vec[backward_index], pivot_value) > 0.0);
00538         if (backward_index < forward_index)
00539         {
00540           break;
00541         }
00542         swapValues(input_vec, forward_index, backward_index);
00543       }
00544       swapValues(input_vec, start_index + 1, backward_index);
00545       stack_index += 2;
00546       if (stack_index > 50)
00547         PLERROR("RegressionTreeRegistersVMatrix: the stack for sorting the rows is too small");
00548       if ((end_index - forward_index + 1) >= (backward_index - start_index))
00549       {
00550         stack[stack_index] = end_index;
00551         stack[stack_index - 1] = forward_index;
00552         end_index = backward_index - 1;
00553       }
00554       else
00555       {
00556         stack[stack_index] = backward_index - 1;
00557         stack[stack_index - 1] = start_index;
00558         start_index = forward_index;
00559       }
00560     }
00561   }
00562 }
00563   
00564 void MeanMedianModeImputationVMatrix::sortSmallSubArray(Vec input_vec, int start_index, int end_index)
00565 {
00566   int index_i;
00567   int index_j;
00568   for (index_i = start_index + 1; index_i <= end_index; index_i++)
00569   {
00570     real saved_value = input_vec[index_i];
00571     for (index_j = index_i - 1; index_j >= start_index; index_j--)
00572     {
00573       if (compare(input_vec[index_j], saved_value) <= 0.0)
00574       {
00575         break;
00576       }
00577       input_vec[index_j + 1] = input_vec[index_j];
00578     }
00579     input_vec[index_j + 1] = saved_value;
00580   }  
00581 }
00582 
00583 void MeanMedianModeImputationVMatrix::swapValues(Vec input_vec, int index_i, int index_j)
00584 {
00585   real saved_value = input_vec[index_i];
00586   input_vec[index_i] = input_vec[index_j];
00587   input_vec[index_j] = saved_value;
00588 }
00589 
00590 real MeanMedianModeImputationVMatrix::compare(real field1, real field2)
00591 {
00592   if (is_missing(field1) && is_missing(field2)) return 0.0;
00593   if (is_missing(field1)) return +1.0;
00594   if (is_missing(field2)) return -1.0;
00595   return field1 - field2;
00596 }
00597 
00598 } // end of namespcae PLearn
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines