PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // ExhaustiveNearestNeighbors.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: ExhaustiveNearestNeighbors.cc 8184 2007-10-15 20:09:46Z nouiz $ 00037 ******************************************************* */ 00038 00039 // Authors: Nicolas Chapados 00040 00044 #include "ExhaustiveNearestNeighbors.h" 00045 #include <assert.h> 00046 #include <plearn/base/stringutils.h> 00047 #include <plearn/ker/DistanceKernel.h> 00048 00049 namespace PLearn { 00050 using namespace std; 00051 00052 PLEARN_IMPLEMENT_OBJECT( 00053 ExhaustiveNearestNeighbors, 00054 "Classical nearest-neighbors implementation using exhaustive search", 00055 "This class provides the basic implementation of the classical O(N^2)\n" 00056 "nearest-neighbors algorithm. For each test point, it performs an\n" 00057 "exhaustive search in the training set to find the K (specified by the\n" 00058 "inherited 'num_neighbors' option) closest examples according to a\n" 00059 "user-specified Kernel.\n" 00060 "\n" 00061 "It is important to specify whether the Kernel denotes a SIMILARITY or a\n" 00062 "(pseudo-)DISTANCE measure. A similarity measure is HIGHER for points\n" 00063 "that are closer. The GaussianKernel is a similarity measure. On the\n" 00064 "other hand, a distance measure is LOWER for points that are closer. A\n" 00065 "DistanceKernel is a distance measure. The option\n" 00066 "'kernel_is_pseudo_distance' controls this:\n" 00067 "\n" 00068 " - if false: the distance_kernel is a similarity measure\n" 00069 " - if true (the default): the distance_kernel is a distance measure\n" 00070 "\n" 00071 "The output costs are simply the kernel values for each found training\n" 00072 "point. The costs are named 'ker0', 'ker1', ..., 'kerK-1'.\n" 00073 "\n" 00074 // "The training set is SAVED with this learner, under the option name\n" 00075 // "'train_set'. Otherwise, one would NOT be able to reload the learner\n" 00076 // "and carry out test operations!\n" 00077 ); 00078 00079 Ker ExhaustiveNearestNeighbors::default_kernel = new DistanceKernel(); 00080 00081 ExhaustiveNearestNeighbors::ExhaustiveNearestNeighbors( 00082 Ker distance_kernel_, bool kernel_is_pseudo_distance_) 00083 : inherited(), 00084 kernel_is_pseudo_distance(kernel_is_pseudo_distance_) 00085 { 00086 distance_kernel = distance_kernel_; 00087 } 00088 00089 void ExhaustiveNearestNeighbors::declareOptions(OptionList& ol) 00090 { 00091 /* // No longer needed: train_set is saved as part of the options of 00092 // parent class GenericNearestNeighbors. See comment there. 00093 declareOption( 00094 ol, "training_mat", &ExhaustiveNearestNeighbors::training_mat, 00095 OptionBase::learntoption, 00096 "Saved training set"); 00097 */ 00098 00099 declareOption( 00100 ol, "kernel_is_pseudo_distance", 00101 &ExhaustiveNearestNeighbors::kernel_is_pseudo_distance, 00102 OptionBase::buildoption, 00103 "Whether the kernel defined by the 'distance_kernel' option should be\n" 00104 "interpreted as a (pseudo-)distance measure (true) or a similarity\n" 00105 "measure (false). Default = true. Note that this interpretation is\n" 00106 "strictly specific to the class ExhaustiveNearestNeighbors.\n"); 00107 00108 declareOption( 00109 ol, "kernel", &GenericNearestNeighbors::distance_kernel, 00110 OptionBase::buildoption | OptionBase::nosave, 00111 "Alternate name for 'distance_kernel'. (Deprecated; use only so that\n" 00112 "existing scripts can run.)"); 00113 00114 // Now call the parent class' declareOptions 00115 inherited::declareOptions(ol); 00116 } 00117 00118 void ExhaustiveNearestNeighbors::build_() 00119 { 00120 if (! distance_kernel) 00121 PLERROR("ExhaustiveNearestNeighbors::build_: the 'distance_kernel' option " 00122 "must be specified"); 00123 } 00124 00125 // ### Nothing to add here, simply calls build_ 00126 void ExhaustiveNearestNeighbors::build() 00127 { 00128 inherited::build(); 00129 build_(); 00130 } 00131 00132 00133 void ExhaustiveNearestNeighbors::makeDeepCopyFromShallowCopy(CopiesMap& copies) 00134 { 00135 inherited::makeDeepCopyFromShallowCopy(copies); 00136 00137 deepCopyField(dummy_vec, copies); 00138 deepCopyField(tmp_indices, copies); 00139 deepCopyField(tmp_distances, copies); 00140 deepCopyField(cached_inputs, copies); 00141 } 00142 00143 void ExhaustiveNearestNeighbors::setTrainingSet(VMat training_set, 00144 bool call_forget) 00145 { 00146 inherited::setTrainingSet(training_set, call_forget); 00147 cached_inputs.resize(0,0); 00148 } 00149 00150 00151 void ExhaustiveNearestNeighbors::forget() 00152 { 00153 cached_inputs.resize(0,0); 00154 } 00155 00156 void ExhaustiveNearestNeighbors::train() 00157 { 00158 // Train is nearly instantaneous. :-) 00159 // Note: this conversion is performed on train() rather than 00160 // setTrainingSet since the training VMat may depend upon some 00161 // PLearners which may not have been trained when setTrainingSet is 00162 // called. It's safer to delay the conversion until necessary. 00163 cached_inputs.resize(0,0); 00164 preloadInputCache(); 00165 } 00166 00167 // New implementation (more efficient) 00168 void ExhaustiveNearestNeighbors::findNearestNeighbors(const Vec& input, int K, TVec<int>& indices, Vec& distances) const 00169 { 00170 PLASSERT(pq.empty()); 00171 if(cached_inputs.size()==0) 00172 preloadInputCache(); 00173 00174 int l = train_set->length(); 00175 for(int i=0; i<l; ++i) 00176 { 00177 real d = distance_kernel(input, cached_inputs(i)); 00178 if(!kernel_is_pseudo_distance) // make it distance-like (smaller means closer) 00179 d = -d; 00180 if(int(pq.size())<K) 00181 pq.push(pair<double,int>(d,i)); 00182 else if(d<pq.top().first) 00183 { 00184 pq.pop(); 00185 pq.push(pair<double,int>(d,i)); 00186 } 00187 } 00188 00189 int pqsize = (int)pq.size(); 00190 indices.resize(pqsize); 00191 distances.resize(pqsize); 00192 00193 for(int j=pqsize-1; j>=0; j--) 00194 { 00195 const pair<real,int>& cur_top = pq.top(); 00196 real d = cur_top.first; 00197 if(!kernel_is_pseudo_distance) // restore actual kernel value (larger means closer) 00198 d = -d; 00199 distances[j] = d; 00200 indices[j] = cur_top.second; 00201 pq.pop(); 00202 } 00203 } 00204 00205 00206 void ExhaustiveNearestNeighbors::computeOutputAndCosts( 00207 const Vec& input, const Vec& target, Vec& output, Vec& costs) const 00208 { 00209 findNearestNeighbors(input, num_neighbors, tmp_indices, tmp_distances); 00210 int effective_num_neighbors = tmp_indices.size(); 00211 costs.resize(num_neighbors); 00212 for(int j=0; j<effective_num_neighbors; j++) 00213 costs[j] = tmp_distances[j]; 00214 // Make remaining costs into missing values if the found number of 00215 // neighbors is smaller than the requested number of neighbors 00216 for(int j=effective_num_neighbors; j<num_neighbors; j++) 00217 costs[j] = MISSING_VALUE; 00218 00219 constructOutputVector(tmp_indices, output); 00220 } 00221 00222 00223 void ExhaustiveNearestNeighbors::computeOutput(const Vec& input, Vec& output) const 00224 { 00225 findNearestNeighbors(input, num_neighbors, tmp_indices, tmp_distances); 00226 constructOutputVector(tmp_indices, output); 00227 } 00228 00229 00230 void ExhaustiveNearestNeighbors::computeCostsFromOutputs( 00231 const Vec& input, const Vec& output, const Vec& target, Vec& costs) const 00232 { 00233 // Not really efficient (the output has probably already been computed). 00234 dummy_vec.resize(outputsize()); 00235 computeOutputAndCosts(input, target, dummy_vec, costs); 00236 } 00237 00238 00239 TVec<string> ExhaustiveNearestNeighbors::getTestCostNames() const 00240 { 00241 TVec<string> costs(num_neighbors); 00242 for (int i=0, n=num_neighbors ; i<n ; ++i) 00243 costs[i] = "ker" + tostring(i); 00244 return costs; 00245 } 00246 00247 00248 int ExhaustiveNearestNeighbors::nTestCosts() const 00249 { 00250 return num_neighbors; 00251 } 00252 00253 00254 TVec<string> ExhaustiveNearestNeighbors::getTrainCostNames() const 00255 { 00256 // No training statistics 00257 return TVec<string>(); 00258 } 00259 00260 void ExhaustiveNearestNeighbors::preloadInputCache() const 00261 { 00262 int l = train_set->length(); 00263 int ninputs = train_set->inputsize(); 00264 cached_inputs.resize(l,ninputs); 00265 for(int i=0; i<l; i++) 00266 train_set->getSubRow(i,0,cached_inputs(i)); 00267 } 00268 00269 } // end of namespace PLearn 00270 00271 00272 /* 00273 Local Variables: 00274 mode:c++ 00275 c-basic-offset:4 00276 c-file-style:"stroustrup" 00277 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00278 indent-tabs-mode:nil 00279 fill-column:79 00280 End: 00281 */ 00282 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :