PLearn 0.1
GenericNearestNeighbors.cc
Go to the documentation of this file.
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 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines