PLearn 0.1
|
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 :