PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // GenericNearestNeighbors.cc 00004 // 00005 // Copyright (C) 2004 Nicolas Chapados 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 /* ******************************************************* 00036 * $Id: GenericNearestNeighbors.cc 8184 2007-10-15 20:09:46Z nouiz $ 00037 ******************************************************* */ 00038 00039 // Authors: Nicolas Chapados 00040 00043 // From PLearn 00044 #include "GenericNearestNeighbors.h" 00045 #include <plearn/ker/DistanceKernel.h> 00046 00047 #include <assert.h> 00048 00049 // From C++ stdlib 00050 #include <algorithm> 00051 00052 namespace PLearn { 00053 using namespace std; 00054 00055 PLEARN_IMPLEMENT_ABSTRACT_OBJECT( 00056 GenericNearestNeighbors, 00057 "Base class for algorithms that find nearest-neighbors", 00058 "This class provides an abstract base class for nearest-neighbors-type\n" 00059 "algorithms. The basic abstraction is that from a test point, one can\n" 00060 "ask to find the \"K\" nearest points from the training set. (Specified\n" 00061 "through the \"num_neighbors\" option). Although per se, this class (and\n" 00062 "its descendants) only FIND the nearest neighbors, the design is such\n" 00063 "that it can be embedded in concrete algorithms that perform\n" 00064 "classification or regression. The separation between \"neighborhood\n" 00065 "finding\" and \"how to use the neighbors\" allows multiple instantiations\n" 00066 "of, say, K-Nearest-Neighbors classification, using several (exact and\n" 00067 "approximate) neighbors-finding algorithms.\n" 00068 "\n" 00069 "There are a number of options that control how the output vectors are\n" 00070 "generated. (See below). For a given neighbor found, the output vector\n" 00071 "is always the concatenation of one or more of (in that order):\n" 00072 "\n" 00073 "- The input vector from the training set (option \"copy_input\")\n" 00074 "- The target vector from the training set (option \"copy_target\")\n" 00075 "- The weight from the training set (option \"copy_weight\"); note that\n" 00076 " if the training set DOES NOT contain a weight, but copy_weight is\n" 00077 " set to 'true', then a weight of 1.0 is always inserted. This\n" 00078 " simplifies client code who may then assume that a weight is always\n" 00079 " present if requested\n" 00080 "- The index (row number) of the example from the training set (option\n" 00081 " \"copy_index\")\n" 00082 "\n" 00083 "If more than one neighbor is requested, the complete output vector of\n" 00084 "this learner is simply the concatenation of the above template for\n" 00085 "creating one output vector.\n" 00086 "\n" 00087 "The learner's costs are dependent on the derived classes. It is\n" 00088 "suggested that, at least, the similarity measure (Kernel value) between\n" 00089 "the test and train points be output.\n" 00090 "\n" 00091 "Instead of Euclidean distance, the user can specify another distance\n" 00092 "by providing a distance_kernel (something that returns a small non-negative number\n" 00093 "when its arguments are 'similar'.\n" 00094 ); 00095 00096 GenericNearestNeighbors::GenericNearestNeighbors() 00097 : num_neighbors(1), 00098 copy_input(false), 00099 copy_target(true), 00100 copy_weight(false), 00101 copy_index(false) 00102 { } 00103 00104 void GenericNearestNeighbors::declareOptions(OptionList& ol) 00105 { 00106 /* train_set is normally not saved in the PLearner base class. 00107 But the current implementation of GenericNearestNeighbors, 00108 unfortunately seems to require to keep it around. 00109 Important note: if this requirement is some day removed (as it should), 00110 beware that subclasses such as ExhaustiveNearestNeighbor rely on the 00111 train_set being available. Thus the delareOption for train_set should 00112 then be moved to such sub-classes that need to access it. 00113 */ 00114 declareOption( 00115 ol, "train_set", &GenericNearestNeighbors::train_set, 00116 OptionBase::learntoption, 00117 "train_set is normally not saved in the PLearner base class, \n" 00118 "But the current implementation of GenericNearestNeighbors, requires\n" 00119 "to keep it around. (see comment in .cc file if you plan to remove\n" 00120 "this unnecessary requirement)"); 00121 00122 declareOption( 00123 ol, "num_neighbors", &GenericNearestNeighbors::num_neighbors, 00124 OptionBase::buildoption, 00125 "Number of nearest-neighbors to compute. This is usually called \"K\".\n" 00126 "The output vector is simply the concatenation of all found neighbors.\n" 00127 "(Default = 1)"); 00128 00129 declareOption( 00130 ol, "copy_input", &GenericNearestNeighbors::copy_input, 00131 OptionBase::buildoption, 00132 "If true, the output contains a copy of the found input vector(s).\n" 00133 "(Default = false)"); 00134 00135 declareOption( 00136 ol, "copy_target", &GenericNearestNeighbors::copy_target, 00137 OptionBase::buildoption, 00138 "If true, the output contains a copy of the found target vector(s).\n" 00139 "(Default = true)"); 00140 00141 declareOption( 00142 ol, "copy_weight", &GenericNearestNeighbors::copy_weight, 00143 OptionBase::buildoption, 00144 "If true, the output contains a copy of the found weight. If no\n" 00145 "weight is present in the training set, a weight of 1.0 is put.\n" 00146 "(Default = true)"); 00147 00148 declareOption( 00149 ol, "copy_index", &GenericNearestNeighbors::copy_index, 00150 OptionBase::buildoption, 00151 "If true, the output contains the index of the found neighbor\n" 00152 "(as the row number, zero-based, in the training set.)\n" 00153 "(Default = false)"); 00154 00155 declareOption( 00156 ol, "distance_kernel", &GenericNearestNeighbors::distance_kernel, 00157 OptionBase::buildoption, 00158 "An optional alternative to the Euclidean distance (DistanceKernel with\n" 00159 "n=2 and pow_distance=1). It should be a 'distance-like' kernel rather\n" 00160 "than a 'dot-product-like' kernel, i.e. small when the arguments are\n" 00161 "similar, and it should always be non-negative, and 0 only if arguments\n" 00162 "are equal.\n"); 00163 00164 // Now call the parent class' declareOptions 00165 inherited::declareOptions(ol); 00166 } 00167 00168 void GenericNearestNeighbors::build_() 00169 { 00171 if (num_neighbors <= 0) 00172 PLERROR("GenericNearestNeighbors::build_: the option \"num_neighbors\" " 00173 "must be strictly positive"); 00174 if (! (copy_input || copy_target || copy_weight || copy_index)) 00175 PLERROR("GenericNearestNeighbors::build_: at least one of the options " 00176 "\"copy_input\", \"copy_target\", \"copy_weight\", \"copy_index\" " 00177 "must be specified (i.e. true)"); 00178 if (!distance_kernel) 00179 // Default is ordinary Euclidean squared distance (i.e. sum of square differences). 00180 distance_kernel = new DistanceKernel(2,true); 00181 } 00182 00183 // ### Nothing to add here, simply calls build_ 00184 void GenericNearestNeighbors::build() 00185 { 00186 inherited::build(); 00187 build_(); 00188 } 00189 00190 00191 void GenericNearestNeighbors::makeDeepCopyFromShallowCopy(CopiesMap& copies) 00192 { 00193 deepCopyField(currow, copies); 00194 deepCopyField(distance_kernel, copies); 00195 00196 inherited::makeDeepCopyFromShallowCopy(copies); 00197 } 00198 00199 00200 int GenericNearestNeighbors::outputsize() const 00201 { 00202 if (!train_set) 00203 // We do not have a training set yet. 00204 return -1; 00205 int base_outputsize = 0; 00206 if (copy_input) 00207 base_outputsize += train_set->inputsize(); 00208 if (copy_target) 00209 base_outputsize += train_set->targetsize(); 00210 if (copy_weight) 00211 base_outputsize += 1; 00212 if (copy_index) 00213 base_outputsize += 1; 00214 00215 PLASSERT( num_neighbors > 0 ); 00216 PLASSERT( base_outputsize > 0 ); 00217 00218 return num_neighbors * base_outputsize; 00219 } 00220 00221 void GenericNearestNeighbors::constructOutputVector(const TVec<int>& indices, 00222 Vec& output, 00223 const Mat& train_mat_override) const 00224 { 00225 // PLASSERT( output.size() == outputsize() ); 00226 output.resize(outputsize()); 00227 00228 int i, n=min(num_neighbors, indices.size()); 00229 int inputsize = train_set->inputsize(); 00230 int targetsize = train_set->targetsize(); 00231 int weightsize = train_set->weightsize(); 00232 real* output_data = output.data(); 00233 00234 currow.resize(train_set.width()); 00235 for (i=0 ; i<n ; ++i) { 00236 real* currow_data = 0; 00237 if (train_mat_override.isNotNull()) 00238 currow_data = train_mat_override[indices[i]]; 00239 else { 00240 train_set->getRow(indices[i], currow); 00241 currow_data = currow.data(); 00242 } 00243 PLASSERT( currow_data ); 00244 00245 if(copy_input) { 00246 copy(currow_data, currow_data+inputsize, output_data); 00247 output_data += inputsize; 00248 } 00249 currow_data += inputsize; 00250 00251 if(copy_target) { 00252 copy(currow_data, currow_data+targetsize, output_data); 00253 output_data += targetsize; 00254 } 00255 currow_data += targetsize; 00256 00257 if(copy_weight) { 00258 if(weightsize) { 00259 copy(currow_data, currow_data+weightsize, output_data); 00260 output_data += weightsize; 00261 } 00262 else 00263 *output_data++ = 1.0; 00264 } 00265 00266 if (copy_index) 00267 *output_data++ = real(indices[i]); 00268 } 00269 00270 if (n < num_neighbors) 00271 fill(output_data, output.end(), MISSING_VALUE); 00272 } 00273 00274 } // end of namespace PLearn 00275 00276 00277 /* 00278 Local Variables: 00279 mode:c++ 00280 c-basic-offset:4 00281 c-file-style:"stroustrup" 00282 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00283 indent-tabs-mode:nil 00284 fill-column:79 00285 End: 00286 */ 00287 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :