PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // VMat_computeNearestNeighbors.cc 00004 // 00005 // Copyright (C) 2004 Pascal Vincent 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: VMat_computeNearestNeighbors.cc 7042 2007-05-09 23:44:20Z saintmlx $ 00037 ******************************************************* */ 00038 00039 // Authors: Pascal Vincent 00040 00044 #include <plearn/base/Object.h> 00045 #include "VMat_computeNearestNeighbors.h" 00046 #include <plearn/vmat/VMat.h> 00047 #include <plearn/math/BottomNI.h> 00048 #include <plearn/math/TMat_maths.h> 00049 00050 namespace PLearn { 00051 using namespace std; 00052 00053 // This is an efficient version of the most basic nearest neighbor search, using a Mat and euclidean distance 00054 void computeNearestNeighbors(VMat dataset, Vec x, TVec<int>& neighbors, int ignore_row) 00055 { 00056 int K = neighbors.length(); // how many neighbors do we want? 00057 BottomNI<real> neighbs(K); 00058 Vec row(dataset->width()); 00059 for(int i=0; i<dataset->length(); i++) 00060 if(i!=ignore_row) 00061 { 00062 dataset->getRow(i,row); 00063 neighbs.update(powdistance(row,x), i); 00064 } 00065 neighbs.sort(); 00066 TVec< pair<real,int> > indices = neighbs.getBottomN(); 00067 int nonzero=0; 00068 for(int k=0; k<K; k++) 00069 { 00070 if(indices[k].first>0) 00071 nonzero++; 00072 neighbors[k] = indices[k].second; 00073 } 00074 if(nonzero==0) 00075 PLERROR("All neighbors had 0 distance. Use more neighbors. (There were %i other patterns with same values)",neighbs.nZeros()); 00076 } 00077 00078 00079 00080 } // end of namespace PLearn 00081 00082 00083 /* 00084 Local Variables: 00085 mode:c++ 00086 c-basic-offset:4 00087 c-file-style:"stroustrup" 00088 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00089 indent-tabs-mode:nil 00090 fill-column:79 00091 End: 00092 */ 00093 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :