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