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