PLearn 0.1
BallTreeNearestNeighbors.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // BallTreeNearestNeighbors.h
00004 //
00005 // Copyright (C) 2004 Pascal Lamblin & Marius Muja
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: BallTreeNearestNeighbors.h 8184 2007-10-15 20:09:46Z nouiz $ 
00037  ******************************************************* */
00038 
00039 // Authors: Pascal Lamblin & Marius Muja
00040 
00044 #ifndef BallTreeNearestNeighbors_INC
00045 #define BallTreeNearestNeighbors_INC
00046 
00047 
00048 #include "BinaryBallTree.h"
00049 #include <plearn_learners/generic/PLearner.h>
00050 #include <plearn_learners/nearest_neighbors/GenericNearestNeighbors.h>
00051 #include <plearn/vmat/SelectRowsVMatrix.h>
00052 #include <plearn/ker/DistanceKernel.h>
00053 
00054 #include <queue>
00055 
00056 namespace PLearn {
00057 using namespace std;
00058 
00059 class BallTreeNearestNeighbors;
00060 typedef PP< BallTreeNearestNeighbors > BallTreeNN;
00061 
00062 class BallTreeNearestNeighbors: public GenericNearestNeighbors
00063 {
00064 
00065 private:
00066 
00067     typedef GenericNearestNeighbors inherited;
00068 
00069 protected:
00070 
00071     // *********************
00072     // * protected options *
00073     // *********************
00074 
00075     BinBallTree ball_tree;
00076     int nb_train_points;
00077     int nb_points;
00078 
00079 public:
00080 
00081     // ************************
00082     // * public build options *
00083     // ************************
00084 
00085     TVec<int> point_indices;
00086     int rmin;
00087     string train_method;
00088     TVec<Mat> anchor_set;
00089     TVec<int> pivot_indices;
00090 
00091     // ****************
00092     // * Constructors *
00093     // ****************
00094 
00096     BallTreeNearestNeighbors();
00097 
00099     BallTreeNearestNeighbors( const VMat& tr_set, const BinBallTree& b_tree );
00100 
00101     // ********************
00102     // * PLearner methods *
00103     // ********************
00104 
00105 private: 
00106 
00108     // (Please implement in .cc)
00109     void build_();
00110     void anchorTrain();
00111 
00112 protected: 
00113   
00115     // (Please implement in .cc)
00116     static void declareOptions(OptionList& ol);
00117 
00118 public:
00119 
00120     // ************************
00121     // **** Static methods ****
00122     // ************************
00123     // Maybe should I put this somewhere else...
00124 
00125     // Returns true if the balls defined by (center1, radius1) and
00126     // (center2, radius2) have a common part
00127 
00128     static bool intersect( const Vec& center1, const real& radius1,
00129                            const Vec& center2, const real& radius2 );
00130 
00131     // Returns true if the first ball contains the second one
00132     static bool contain( const Vec& center1, const real& radius1,
00133                          const Vec& center2, const real& radius2 );
00134 
00135     // Returns the smallest ball containing two balls
00136     static void smallestContainer( const Vec& center1, const real& radius1,
00137                                    const Vec& center2, const real& radius2,
00138                                    Vec& t_center, real& t_radius);
00139 
00140     virtual void BallKNN( priority_queue< pair<real,int> >& q,
00141                           BinBallTree node, const Vec& t,
00142                           real& d_sofar, real d_minp, const int k ) const;
00143 
00144     virtual void FindBallKNN( priority_queue< pair<real,int> >& q,
00145                               const Vec& point, int k ) const;
00146 
00147 
00148     // ************************
00149     // **** Object methods ****
00150     // ************************
00151 
00153     virtual void build();
00154 
00156     virtual void makeDeepCopyFromShallowCopy(CopiesMap& copies);
00157 
00158     // Declares other standard object methods.
00159     PLEARN_DECLARE_OBJECT(BallTreeNearestNeighbors);
00160 
00161 
00162     // **************************
00163     // **** PLearner methods ****
00164     // **************************
00165 
00169     virtual void forget();
00170 
00171 
00175     virtual void train();
00176 
00177     void createAnchors( int nb_anchors );
00178 
00179 
00180     BinBallTree leafFromAnchor( int anchor_index );
00181 
00182     BinBallTree treeFromLeaves( const TVec<BinBallTree>& leaves );
00183 
00184     BinBallTree getBallTree();
00185 
00186 
00188     virtual void computeOutputAndCosts( const Vec& input, const Vec& target,
00189                                         Vec& output, Vec& costs ) const;
00191     virtual void computeOutput(const Vec& input, Vec& output) const;
00192 
00194     virtual void computeCostsFromOutputs(const Vec& input, const Vec& output, 
00195                                          const Vec& target, Vec& costs) const;
00196 
00197 
00200     virtual TVec<string> getTestCostNames() const;
00201 
00203     //computes and ! for which it updates the VecStatsCollector
00204     //train_stats.  (PLEASE IMPLEMENT IN .cc)
00205     virtual TVec<string> getTrainCostNames() const;
00206 
00207 };
00208 
00209 // Declares a few other classes and functions related to this class.
00210 DECLARE_OBJECT_PTR(BallTreeNearestNeighbors);
00211 
00212 } // end of namespace PLearn
00213 
00214 #endif
00215 
00216 
00217 /*
00218   Local Variables:
00219   mode:c++
00220   c-basic-offset:4
00221   c-file-style:"stroustrup"
00222   c-file-offsets:((innamespace . 0)(inline-open . 0))
00223   indent-tabs-mode:nil
00224   fill-column:79
00225   End:
00226 */
00227 // 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