PLearn 0.1
|
#include <BallTreeNearestNeighbors.h>
Public Member Functions | |
BallTreeNearestNeighbors () | |
Default constructor. | |
BallTreeNearestNeighbors (const VMat &tr_set, const BinBallTree &b_tree) | |
Constructor from a TrainSet and a BinBallTree. | |
virtual void | BallKNN (priority_queue< pair< real, int > > &q, BinBallTree node, const Vec &t, real &d_sofar, real d_minp, const int k) const |
virtual void | FindBallKNN (priority_queue< pair< real, int > > &q, const Vec &point, int k) const |
virtual void | build () |
Simply calls inherited::build() then build_(). | |
virtual void | makeDeepCopyFromShallowCopy (CopiesMap &copies) |
Transforms a shallow copy into a deep copy. | |
virtual string | classname () const |
virtual OptionList & | getOptionList () const |
virtual OptionMap & | getOptionMap () const |
virtual RemoteMethodMap & | getRemoteMethodMap () const |
virtual BallTreeNearestNeighbors * | deepCopy (CopiesMap &copies) const |
virtual void | forget () |
(Re-)initializes the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!). | |
virtual void | train () |
The role of the train method is to bring the learner up to stage==nstages, updating the train_stats collector with training costs measured on-line in the process. | |
void | createAnchors (int nb_anchors) |
BinBallTree | leafFromAnchor (int anchor_index) |
BinBallTree | treeFromLeaves (const TVec< BinBallTree > &leaves) |
BinBallTree | getBallTree () |
virtual void | computeOutputAndCosts (const Vec &input, const Vec &target, Vec &output, Vec &costs) const |
Computes the output and costs from the input (more effectively) | |
virtual void | computeOutput (const Vec &input, Vec &output) const |
Computes the output from the input. | |
virtual void | computeCostsFromOutputs (const Vec &input, const Vec &output, const Vec &target, Vec &costs) const |
Computes the costs from already computed output. | |
virtual TVec< string > | getTestCostNames () const |
Returns the names of the costs computed by computeCostsFromOutpus (and thus the test method). | |
virtual TVec< string > | getTrainCostNames () const |
Returns the names of the objective costs that the train method. | |
Static Public Member Functions | |
static bool | intersect (const Vec ¢er1, const real &radius1, const Vec ¢er2, const real &radius2) |
static bool | contain (const Vec ¢er1, const real &radius1, const Vec ¢er2, const real &radius2) |
static void | smallestContainer (const Vec ¢er1, const real &radius1, const Vec ¢er2, const real &radius2, Vec &t_center, real &t_radius) |
static string | _classname_ () |
static OptionList & | _getOptionList_ () |
static RemoteMethodMap & | _getRemoteMethodMap_ () |
static Object * | _new_instance_for_typemap_ () |
static bool | _isa_ (const Object *o) |
static void | _static_initialize_ () |
static const PPath & | declaringFile () |
Public Attributes | |
TVec< int > | point_indices |
int | rmin |
string | train_method |
TVec< Mat > | anchor_set |
TVec< int > | pivot_indices |
Static Public Attributes | |
static StaticInitializer | _static_initializer_ |
Static Protected Member Functions | |
static void | declareOptions (OptionList &ol) |
Declares this class' options. | |
Protected Attributes | |
BinBallTree | ball_tree |
int | nb_train_points |
int | nb_points |
Private Types | |
typedef GenericNearestNeighbors | inherited |
Private Member Functions | |
void | build_ () |
This does the actual building. | |
void | anchorTrain () |
Definition at line 62 of file BallTreeNearestNeighbors.h.
typedef GenericNearestNeighbors PLearn::BallTreeNearestNeighbors::inherited [private] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 67 of file BallTreeNearestNeighbors.h.
PLearn::BallTreeNearestNeighbors::BallTreeNearestNeighbors | ( | ) |
Default constructor.
Definition at line 49 of file BallTreeNearestNeighbors.cc.
References PLearn::PLearner::expdir, PLearn::PLearner::nstages, PLearn::GenericNearestNeighbors::num_neighbors, PLearn::PLearner::report_progress, and PLearn::PLearner::stage.
Referenced by anchorTrain().
: rmin( 1 ), train_method( "anchor" ) { num_neighbors = 1; expdir = ""; stage = 0; nstages = -1; report_progress = 0; }
PLearn::BallTreeNearestNeighbors::BallTreeNearestNeighbors | ( | const VMat & | tr_set, |
const BinBallTree & | b_tree | ||
) |
Constructor from a TrainSet and a BinBallTree.
Definition at line 60 of file BallTreeNearestNeighbors.cc.
References ball_tree, PLearn::PLearner::expdir, PLearn::PLearner::nstages, PLearn::GenericNearestNeighbors::num_neighbors, PLearn::PLearner::report_progress, PLearn::PLearner::setTrainingSet(), and PLearn::PLearner::stage.
: rmin( 1 ), train_method( "anchor" ) { num_neighbors = 1; expdir = ""; stage = 1; nstages = 1; report_progress = 0; setTrainingSet( tr_set ); ball_tree = b_tree; }
string PLearn::BallTreeNearestNeighbors::_classname_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
OptionList & PLearn::BallTreeNearestNeighbors::_getOptionList_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
RemoteMethodMap & PLearn::BallTreeNearestNeighbors::_getRemoteMethodMap_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
Object * PLearn::BallTreeNearestNeighbors::_new_instance_for_typemap_ | ( | ) | [static] |
Reimplemented from PLearn::Object.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
StaticInitializer BallTreeNearestNeighbors::_static_initializer_ & PLearn::BallTreeNearestNeighbors::_static_initialize_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
void PLearn::BallTreeNearestNeighbors::anchorTrain | ( | ) | [private] |
Definition at line 186 of file BallTreeNearestNeighbors.cc.
References anchor_set, ball_tree, BallTreeNearestNeighbors(), PLearn::TMat< T >::column(), createAnchors(), PLearn::GenericNearestNeighbors::distance_kernel, forget(), PLearn::VMat::getSubRow(), i, PLearn::PLearner::inputsize(), leafFromAnchor(), PLearn::TVec< T >::length(), PLearn::min(), nb_points, nb_train_points, PLearn::PLearner::nstages, pivot_indices, PLearn::TMat< T >::resize(), PLearn::TVec< T >::resize(), rmin, PLearn::TVec< T >::size(), PLearn::sortRows(), PLearn::sqrt(), PLearn::PLearner::stage, train_method, PLearn::PLearner::train_set, and treeFromLeaves().
Referenced by train().
{ /* nstages and stage conventions, for "anchor" train method: * * nstages == -1 * We will construct ball_tree recursively, * until, for all leaf, nb_points <= rmin, * no matter how many iterations it will take. * * nstages == 0 * We want the PLearner il its fresh, blank state. * * nstages == 1 * We want ball_tree to be a unique leaf node, * containing all the point indices, with no children. * * nstages > 1 * We want to build ball_tree recursively, * but limiting the levels of recursion. * This means we will decrement this number at each recursive call, * the recursion will stop when nstages == 1 or nb_points <= rmin. * * stage == 0 * The learner is it its fresh, blank state. * * stage == 1 * The learner has one anchor, that's all. * * Other values of stage might be used one day or anoter... */ if( stage == 0 && nstages !=0 ) { // That means we weren't provided with any anchor nor node parameter, // or that they were just bullsh!t // So, we build a single anchor pivot_indices.resize( 1 ); pivot_indices[ 0 ] = 0; Vec pivot = train_set.getSubRow( 0, inputsize() ); distance_kernel->setDataForKernelMatrix( train_set ); distance_kernel->build(); Vec distances_from_pivot( nb_train_points ); distance_kernel->evaluate_all_i_x( pivot, distances_from_pivot ); anchor_set.resize( 1 ); Mat* p_anchor = &anchor_set[ 0 ]; p_anchor->resize( nb_points, 2 ); p_anchor->column( 0 ) << Vec( 0, nb_points-1, 1 ); p_anchor->column( 1 ) << distances_from_pivot; sortRows( *p_anchor, TVec<int>( 1, 1 ), false ); // then, we build the corresponding tree ball_tree = leafFromAnchor( 0 ); ++stage; } if( nstages == 0 ) { // we want a fresh, blank learner forget(); } else if( nstages == 1 ) { // We have an anchor, and we want a leaf node ball_tree = leafFromAnchor( 0 ); } else { // nstages to be used on children learners int new_nstages = nstages<0 ? -1 : nstages-1; // First create sqrt( R )-1 anchors, from the initial anchor_set int nb_anchors = (int) sqrt( (float) nb_points ) + 1 ; nb_anchors = min( nb_anchors, nb_points ); createAnchors( nb_anchors-1 ); // because we already have one // Convert them into leaf nodes TVec< BinBallTree > leaf_set = TVec<BinBallTree>( nb_anchors ); for ( int i=0 ; i<nb_anchors ; i++ ) { leaf_set[ i ] = leafFromAnchor( i ); } // Then, group them to form the ball_tree // keep an index of the leaves ball_tree = treeFromLeaves( leaf_set ); // Now, recurse... for( int i=0 ; i<leaf_set.size() ; i++ ) { int rec_nb_points = anchor_set[ i ].length(); // if the leaf is too small, don't do anything if( rec_nb_points > rmin ) { // child learner PP<BallTreeNearestNeighbors> p_rec_learner = new BallTreeNearestNeighbors(); // initializes child's nstages (see explanation above) stringstream out; out << new_nstages; p_rec_learner->setOption( "nstages" , out.str() ); // keep the same training set: it give us all the point coordinates ! // but we don't want to call forget() after that p_rec_learner->setTrainingSet( train_set, false ); // however, we only work on the points contained by current leaf p_rec_learner->anchor_set.resize( 1 ); p_rec_learner->anchor_set[ 0 ].resize( rec_nb_points, 2 ); p_rec_learner->anchor_set[ 0 ] << anchor_set[ i ]; p_rec_learner->pivot_indices.resize( 1 ); p_rec_learner->pivot_indices[ 0 ] = pivot_indices[ i ]; p_rec_learner->point_indices.resize( rec_nb_points ); p_rec_learner->point_indices << p_rec_learner->anchor_set[ 0 ].column( 0 ); p_rec_learner->stage = 1; // faudra peut-etre faire ça plus subtilement p_rec_learner->rmin = rmin; p_rec_learner->train_method = train_method; p_rec_learner->build(); p_rec_learner->train(); // once the child learner is trained, we can get the sub-tree, // and link it correctly BinBallTree subtree = p_rec_learner->getBallTree(); leaf_set[ i ]->pivot = subtree->pivot; leaf_set[ i ]->radius = subtree->radius; leaf_set[ i ]->point_set.resize( subtree->point_set.size() ); leaf_set[ i ]->point_set << subtree->point_set; leaf_set[ i ]->setFirstChild( subtree->getFirstChild() ); leaf_set[ i ]->setSecondChild( subtree->getSecondChild() ); } } } }
void PLearn::BallTreeNearestNeighbors::BallKNN | ( | priority_queue< pair< real, int > > & | q, |
BinBallTree | node, | ||
const Vec & | t, | ||
real & | d_sofar, | ||
real | d_minp, | ||
const int | k | ||
) | const [virtual] |
Definition at line 711 of file BallTreeNearestNeighbors.cc.
References PLearn::dist(), PLearn::VMat::getSubRow(), i, PLearn::PLearner::inputsize(), j, PLearn::max(), PLearn::pl_swap(), PLERROR, PLearn::powdistance(), PLearn::sqrt(), PLearn::PLearner::train_set, and x.
Referenced by FindBallKNN().
{ real d_minp = max( sqrt(d2_pivot) - node->radius, real(0.0) ); #ifdef DEBUG_CHECK_NAN if (isnan(d_minp)) PLERROR("BallTreeNearestNeighbors::BallKNN: d_minp is NaN"); #endif if (d_minp*d_minp > d2_sofar) { // no chance of finding anything closer around this node return; } else if (node->point_set.size()!=0) // node is leaf { int n_points = node->point_set.size(); for( int i=0 ; i<n_points ; i++ ) { int j = node->point_set[i]; real dist; // last point is pivot, and we already now the distance if( i==n_points-1 ) { dist = d2_pivot; } else { Vec x = train_set.getSubRow(j, inputsize()); dist = powdistance(x, t, 2); } if( dist < d2_sofar ) { q.push( make_pair(dist, j) ); int n_found = int(q.size()); if( n_found > k ) q.pop(); if( n_found >= k ) d2_sofar = q.top().first; } } } else if (!node->isEmpty()) // node is not leaf { BinBallTree node1 = node->getFirstChild(); BinBallTree node2 = node->getSecondChild(); real d2_pivot1 = powdistance(t, node1->pivot, 2); real d2_pivot2 = powdistance(t, node2->pivot, 2); if( d2_pivot1 > d2_pivot2 ) // node1 is closer to t { pl_swap(node1, node2); pl_swap(d2_pivot1, d2_pivot2); } BallKNN(q, node1, t, d2_sofar, d2_pivot1, k); BallKNN(q, node2, t, d2_sofar, d2_pivot2, k); } }
void PLearn::BallTreeNearestNeighbors::build | ( | ) | [virtual] |
Simply calls inherited::build() then build_().
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 139 of file BallTreeNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::build(), and build_().
Referenced by forget().
{ inherited::build(); build_(); }
void PLearn::BallTreeNearestNeighbors::build_ | ( | ) | [private] |
This does the actual building.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 123 of file BallTreeNearestNeighbors.cc.
References PLearn::VMat::length(), nb_points, nb_train_points, point_indices, PLearn::TVec< T >::size(), and PLearn::PLearner::train_set.
Referenced by build().
{ if (train_set) { // initialize nb_train_points nb_train_points = train_set.length(); // if point_indices isn't specified, we take all the points in train_set if( !point_indices ) point_indices = TVec<int>( 0, nb_train_points-1, 1 ); // initialize nb_points nb_points = point_indices.size(); } }
string PLearn::BallTreeNearestNeighbors::classname | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
void PLearn::BallTreeNearestNeighbors::computeCostsFromOutputs | ( | const Vec & | input, |
const Vec & | output, | ||
const Vec & | target, | ||
Vec & | costs | ||
) | const [virtual] |
Computes the costs from already computed output.
Implements PLearn::PLearner.
Definition at line 589 of file BallTreeNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::copy_index, PLearn::GenericNearestNeighbors::copy_input, PLearn::GenericNearestNeighbors::copy_target, PLearn::GenericNearestNeighbors::copy_weight, i, PLearn::PLearner::inputsize(), PLearn::GenericNearestNeighbors::num_neighbors, PLearn::GenericNearestNeighbors::outputsize(), PLERROR, PLearn::powdistance(), PLearn::TVec< T >::resize(), PLearn::TVec< T >::subVec(), PLearn::PLearner::targetsize(), PLearn::PLearner::train_set, and PLearn::PLearner::weightsize().
{ // Compute the costs from *already* computed output. costs.resize( num_neighbors ); int inputsize = train_set->inputsize(); int targetsize = train_set->targetsize(); int weightsize = train_set->weightsize(); Mat out( num_neighbors, inputsize ); if( copy_input ) { for( int i=0 ; i<num_neighbors ; i++ ) out( i ) << output.subVec( i*outputsize(), inputsize ); } else if( copy_index ) { int offset = 0; if( copy_target ) offset += targetsize; if( copy_weight ) offset += weightsize; for( int i=0 ; i<num_neighbors ; i++ ) out( i ) << train_set( (int) output[ i*outputsize() + offset ] ); } else { PLERROR( "computeCostsFromOutput:\n" "neither indices nor coordinates of output computed\n" ); } for( int i=0 ; i<num_neighbors ; i++ ) costs[ i ] = powdistance( input, out( i ) ); }
void PLearn::BallTreeNearestNeighbors::computeOutput | ( | const Vec & | input, |
Vec & | output | ||
) | const [virtual] |
Computes the output from the input.
Reimplemented from PLearn::PLearner.
Definition at line 560 of file BallTreeNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::constructOutputVector(), FindBallKNN(), i, PLearn::GenericNearestNeighbors::num_neighbors, PLearn::GenericNearestNeighbors::outputsize(), and PLearn::TVec< T >::resize().
{ // Compute the output from the input. // int nout = outputsize(); // output.resize(nout); int nout = outputsize(); output.resize( nout ); // we launch a k-nearest-neighbors query on the root node (ball_tree) priority_queue< pair<real,int> > q; FindBallKNN( q, input, num_neighbors ); // dequeue the found nearest neighbors, beginning by the farthest away int n_found = int(q.size()); TVec<int> neighbors( n_found ); for( int i=n_found-1 ; i>=0 ; i-- ) { const pair<real,int>& cur_top = q.top(); neighbors[i] = cur_top.second; q.pop(); } constructOutputVector( neighbors, output ); }
void PLearn::BallTreeNearestNeighbors::computeOutputAndCosts | ( | const Vec & | input, |
const Vec & | target, | ||
Vec & | output, | ||
Vec & | costs | ||
) | const [virtual] |
Computes the output and costs from the input (more effectively)
Reimplemented from PLearn::PLearner.
Definition at line 531 of file BallTreeNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::constructOutputVector(), FindBallKNN(), PLearn::TVec< T >::first(), i, MISSING_VALUE, PLearn::GenericNearestNeighbors::num_neighbors, PLearn::GenericNearestNeighbors::outputsize(), and PLearn::TVec< T >::resize().
{ int nout = outputsize(); output.resize( nout ); costs.resize( num_neighbors ); // we launch a k-nearest-neighbors query on the root node (ball_tree) priority_queue< pair<real,int> > q; FindBallKNN( q, input, num_neighbors ); // dequeue the found nearest neighbors, beginning by the farthest away int n_found = int(q.size()); TVec<int> neighbors( n_found ); for( int i=n_found-1 ; i>=0 ; i-- ) { const pair<real,int>& cur_top = q.top(); costs[i] = cur_top.first; neighbors[i] = cur_top.second; q.pop(); } // fill costs with missing values for( int i= n_found ; i<num_neighbors ; i++ ) costs[i] = MISSING_VALUE; constructOutputVector( neighbors, output ); }
bool PLearn::BallTreeNearestNeighbors::contain | ( | const Vec & | center1, |
const real & | radius1, | ||
const Vec & | center2, | ||
const real & | radius2 | ||
) | [static] |
Definition at line 652 of file BallTreeNearestNeighbors.cc.
References PLearn::powdistance(), and PLearn::sqrt().
Referenced by smallestContainer().
{ real radius1 = sqrt( powrad1 ); real radius2 = sqrt( powrad2 ); real rad_dif = radius1 - radius2; if( rad_dif >= 0 ) { real pow_dist = powdistance( center1, center2, 2 ); bool result = ( pow_dist <= ( rad_dif * rad_dif ) ); return result; } else { return false; } }
void PLearn::BallTreeNearestNeighbors::createAnchors | ( | int | nb_anchors | ) |
Definition at line 333 of file BallTreeNearestNeighbors.cc.
References anchor_set, PLearn::TVec< T >::append(), PLearn::TMat< T >::appendRow(), PLearn::VMat::getSubRow(), i, PLearn::PLearner::inputsize(), j, PLearn::TMat< T >::length(), nb_points, pivot_indices, PLERROR, PLearn::powdistance(), PLearn::removeRow(), PLearn::TVec< T >::resize(), PLearn::TVec< T >::size(), PLearn::sortRows(), and PLearn::PLearner::train_set.
Referenced by anchorTrain().
{ // This method creates nb_anchors new anchors, and adds them to anchor_set // Make room int anchor_set_size = anchor_set.size(); anchor_set.resize( anchor_set_size, nb_anchors ); for( int i=0 ; i<nb_anchors ; i++ ) { Mat new_anchor = Mat( 1, 2 ); int new_pivot_index; // Search for the largest ball. // pivot of the new anchor will be the point of this ball // that is the furthest from the pivot. int largest_index = 0; real largest_radius = 0; for( int j=0 ; j<anchor_set_size ; j++ ) { // points are sorted in decreasing order of distance, // so anchor_set[ j ]( 0, 1 ) is the furthest point from // pivot_indices[ j ] real current_radius = anchor_set[ j ]( 0, 1 ); if( current_radius > largest_radius ) { largest_radius = current_radius; largest_index = j; } } Mat* p_largest_anchor = &anchor_set[ largest_index ]; new_pivot_index = (int) (*p_largest_anchor)( 0, 0 ); // assign the point to its new anchor new_anchor( 0, 0 ) = new_pivot_index; new_anchor( 0, 1 ) = 0; Vec new_pivot = train_set.getSubRow( new_pivot_index, inputsize() ); int largest_anchor_length = p_largest_anchor->length(); // Verify that largest_anchor owns at least 2 points if( largest_anchor_length <= 1 ) { PLERROR("In BallTreeNearestNeighbors::createAnchors, more anchors asked than points"); } // delete this point from its original anchor *p_largest_anchor = p_largest_anchor-> subMatRows( 1, largest_anchor_length-1 ); // now, try to steal points from all the existing anchors for( int j=0 ; j<anchor_set_size ; j++ ) { Mat* p_anchor = &anchor_set[ j ]; int nb_points = p_anchor->length(); int pivot_index = pivot_indices[ j ]; Vec pivot = train_set.getSubRow( pivot_index, inputsize() ); real pivot_pow_dist = powdistance( new_pivot, pivot, 2 ); // loop on the anchor's points for( int k=0 ; k<nb_points ; k++ ) { int point_index = (int) (*p_anchor)( k, 0 ); real point_pow_dist = (*p_anchor)( k, 1 ); // if this inequality is verified, // then we're sure that all the points closer to the pivot // belong to the pivot, and we don't need to check if( 4*point_pow_dist < pivot_pow_dist ) { break; } Vec point = train_set.getSubRow( point_index, inputsize() ); real new_pow_dist = powdistance( new_pivot, point, 2 ); // if the point is closer to the new pivot, then steal it if( new_pow_dist < point_pow_dist ) { Vec new_row( 2 ); new_row[ 0 ] = point_index; new_row[ 1 ] = new_pow_dist; new_anchor.appendRow( new_row ); *p_anchor = removeRow( *p_anchor, k ); // bleaah, this is ugly ! --k; --nb_points; } } } // sort the points by decreasing distance sortRows( new_anchor, TVec<int>( 1, 1 ), false ); // append the new anchor to the anchor_set (and same for pivot) anchor_set.append( new_anchor ); pivot_indices.append( new_pivot_index ); ++anchor_set_size; } }
void PLearn::BallTreeNearestNeighbors::declareOptions | ( | OptionList & | ol | ) | [static, protected] |
Declares this class' options.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 81 of file BallTreeNearestNeighbors.cc.
References anchor_set, ball_tree, PLearn::OptionBase::buildoption, PLearn::declareOption(), PLearn::GenericNearestNeighbors::declareOptions(), PLearn::OptionBase::learntoption, nb_points, nb_train_points, pivot_indices, point_indices, rmin, train_method, and PLearn::PLearner::train_set.
{ // build options declareOption( ol, "point_indices", &BallTreeNearestNeighbors::point_indices, OptionBase::buildoption, "Indices of the points we will consider" ); declareOption( ol, "rmin", &BallTreeNearestNeighbors::rmin, OptionBase::buildoption, "Max number of points in a leaf node of the tree" ); declareOption( ol, "train_method", &BallTreeNearestNeighbors::train_method, OptionBase::buildoption, "Method used to build the tree. Just one is supported:\n" " \"anchor\" (middle-out building based on Anchor\'s hierarchy\n" ); declareOption( ol, "anchor_set", &BallTreeNearestNeighbors::anchor_set, OptionBase::learntoption, "Set of anchors, hierarchizing the set of points" ); declareOption( ol, "pivot_indices", &BallTreeNearestNeighbors::pivot_indices, OptionBase::learntoption, "Indices of the anchors' centers" ); // saved options declareOption( ol, "train_set", &BallTreeNearestNeighbors::train_set, OptionBase::buildoption, "Indexed set of points we will be working with" ); declareOption( ol, "nb_train_points", &BallTreeNearestNeighbors::nb_train_points, OptionBase::learntoption, "Number of points in train_set" ); declareOption( ol, "nb_points", &BallTreeNearestNeighbors::nb_points, OptionBase::learntoption, "Number of points in point_indices" ); declareOption( ol, "ball_tree", &BallTreeNearestNeighbors::ball_tree, OptionBase::learntoption, "Built ball-tree" ); // Now call the parent class' declareOptions inherited::declareOptions( ol ); }
static const PPath& PLearn::BallTreeNearestNeighbors::declaringFile | ( | ) | [inline, static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 159 of file BallTreeNearestNeighbors.h.
BallTreeNearestNeighbors * PLearn::BallTreeNearestNeighbors::deepCopy | ( | CopiesMap & | copies | ) | const [virtual] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
void PLearn::BallTreeNearestNeighbors::FindBallKNN | ( | priority_queue< pair< real, int > > & | q, |
const Vec & | point, | ||
int | k | ||
) | const [virtual] |
Definition at line 774 of file BallTreeNearestNeighbors.cc.
References ball_tree, BallKNN(), PLearn::pl_isnumber(), and PLearn::powdistance().
Referenced by computeOutput(), and computeOutputAndCosts().
{ real d2_sofar; pl_isnumber("+inf", &d2_sofar); real d2_pivot = powdistance(point, ball_tree->pivot, 2); // real d_minp = 0; BallKNN(q, ball_tree, point, d2_sofar, d2_pivot, k); }
void PLearn::BallTreeNearestNeighbors::forget | ( | ) | [virtual] |
(Re-)initializes the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!).
(Re-)initialize the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!)
Reimplemented from PLearn::PLearner.
Definition at line 157 of file BallTreeNearestNeighbors.cc.
References anchor_set, ball_tree, build(), pivot_indices, PLearn::TVec< T >::resize(), and PLearn::PLearner::stage.
Referenced by anchorTrain().
{ anchor_set.resize( 0 ); pivot_indices.resize( 0 ); ball_tree = new BinaryBallTree; stage = 0; build(); }
BinBallTree PLearn::BallTreeNearestNeighbors::getBallTree | ( | ) |
Definition at line 525 of file BallTreeNearestNeighbors.cc.
References ball_tree.
{ return ball_tree; }
OptionList & PLearn::BallTreeNearestNeighbors::getOptionList | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
OptionMap & PLearn::BallTreeNearestNeighbors::getOptionMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
RemoteMethodMap & PLearn::BallTreeNearestNeighbors::getRemoteMethodMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 79 of file BallTreeNearestNeighbors.cc.
TVec< string > PLearn::BallTreeNearestNeighbors::getTestCostNames | ( | ) | const [virtual] |
Returns the names of the costs computed by computeCostsFromOutpus (and thus the test method).
Implements PLearn::PLearner.
Definition at line 629 of file BallTreeNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::num_neighbors.
{ return TVec<string>( num_neighbors, "squared_distance" ); }
TVec< string > PLearn::BallTreeNearestNeighbors::getTrainCostNames | ( | ) | const [virtual] |
Returns the names of the objective costs that the train method.
Implements PLearn::PLearner.
Definition at line 634 of file BallTreeNearestNeighbors.cc.
{
return TVec<string>();
}
bool PLearn::BallTreeNearestNeighbors::intersect | ( | const Vec & | center1, |
const real & | radius1, | ||
const Vec & | center2, | ||
const real & | radius2 | ||
) | [static] |
Definition at line 639 of file BallTreeNearestNeighbors.cc.
References PLearn::powdistance(), and PLearn::sqrt().
{ real radius1 = sqrt( powrad1 ); real radius2 = sqrt( powrad2 ); real pow_dist = powdistance( center1, center2, 2 ); real rad_sum = radius1 + radius2; bool result = ( pow_dist <= ( rad_sum * rad_sum ) ); return result; }
BinBallTree PLearn::BallTreeNearestNeighbors::leafFromAnchor | ( | int | anchor_index | ) |
Definition at line 436 of file BallTreeNearestNeighbors.cc.
References anchor_set, PLearn::VMat::getSubRow(), PLearn::PLearner::inputsize(), PLearn::TVec< T >::length(), pivot_indices, and PLearn::PLearner::train_set.
Referenced by anchorTrain().
{ BinBallTree leaf = new BinaryBallTree(); int pivot_index = pivot_indices[ anchor_index ]; leaf->pivot = train_set.getSubRow( pivot_index, inputsize() ); leaf->radius = anchor_set[ anchor_index ]( 0, 1 ); int nb_leaf_points = anchor_set[ anchor_index ].length(); leaf->point_set.resize( nb_leaf_points ); leaf->point_set << anchor_set[ anchor_index ].column( 0 ); return leaf; }
void PLearn::BallTreeNearestNeighbors::makeDeepCopyFromShallowCopy | ( | CopiesMap & | copies | ) | [virtual] |
Transforms a shallow copy into a deep copy.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 146 of file BallTreeNearestNeighbors.cc.
References anchor_set, ball_tree, PLearn::deepCopyField(), PLearn::GenericNearestNeighbors::makeDeepCopyFromShallowCopy(), pivot_indices, and point_indices.
{ inherited::makeDeepCopyFromShallowCopy(copies); deepCopyField( ball_tree, copies ); deepCopyField( point_indices, copies ); deepCopyField( anchor_set, copies ); deepCopyField( pivot_indices, copies ); }
void PLearn::BallTreeNearestNeighbors::smallestContainer | ( | const Vec & | center1, |
const real & | radius1, | ||
const Vec & | center2, | ||
const real & | radius2, | ||
Vec & | t_center, | ||
real & | t_radius | ||
) | [static] |
Definition at line 672 of file BallTreeNearestNeighbors.cc.
References contain(), PLearn::dist(), PLearn::TVec< T >::hasMissing(), PLearn::max(), PLERROR, and PLearn::sqrt().
Referenced by treeFromLeaves().
{ if( center1 == center2 ) { t_center = center1; t_powrad = max( powrad1, powrad2 ); } else if( contain( center1, powrad1, center2, powrad2 ) ) { t_center = center1; t_powrad = powrad1; } else if( contain( center2, powrad2, center1, powrad1 ) ) { t_center = center2; t_powrad = powrad2; } else { real radius1 = sqrt( powrad1 ); real radius2 = sqrt( powrad2 ); real center_dist = dist( center1, center2, 2 ) ; real coef = ( radius1 - radius2 ) / center_dist ; t_center = real(0.5) * ( ( 1 + coef ) * center1 + ( 1 - coef ) * center2 ) ; real t_radius = real(0.5) * ( center_dist + radius1 + radius2 ) ; t_powrad = t_radius * t_radius; } #ifdef DEBUG_CHECK_NAN if (t_center.hasMissing()) PLERROR("In BallTreeNearestNeighbors::smallestContainer: t_center is NaN."); #endif }
void PLearn::BallTreeNearestNeighbors::train | ( | ) | [virtual] |
The role of the train method is to bring the learner up to stage==nstages, updating the train_stats collector with training costs measured on-line in the process.
Implements PLearn::PLearner.
Definition at line 172 of file BallTreeNearestNeighbors.cc.
References anchorTrain(), PLERROR, and train_method.
{ // The role of the train method is to bring the learner up to stage==nstages, // updating train_stats with training costs measured on-line in the process. if( train_method == "anchor" ) { anchorTrain(); } else PLERROR( "train_method \"%s\" not implemented", train_method.c_str() ); }
BinBallTree PLearn::BallTreeNearestNeighbors::treeFromLeaves | ( | const TVec< BinBallTree > & | leaves | ) |
Definition at line 453 of file BallTreeNearestNeighbors.cc.
References PLearn::TVec< T >::hasMissing(), i, j, PLERROR, PLearn::TVec< T >::remove(), PLearn::TVec< T >::size(), and smallestContainer().
Referenced by anchorTrain().
{ int nb_nodes = leaves.size(); TVec<BinBallTree> nodes = TVec<BinBallTree>( nb_nodes ); nodes << leaves; // if there is no leaf if( nb_nodes < 1 ) { PLERROR( "In BallTreeNearestNeighbors::treeFromLeaves(): no leaf existing" ); } while( nb_nodes > 1 ) { int min_i = 0; int min_j = 0; Vec min_center; real min_radius = -1; // we get the most "compatible" pair of nodes : // the ball containing them both is the smallest for( int i=0 ; i<nb_nodes ; i++ ) { Vec center_i = nodes[ i ]->pivot; real radius_i = nodes[ i ]->radius; // to scan all pairs only once, and avoid i==j for( int j=0 ; j<i ; j++ ) { Vec center_j = nodes[ j ]->pivot; real radius_j = nodes[ j ]->radius; Vec t_center; real t_radius; smallestContainer( center_i, radius_i, center_j, radius_j, t_center, t_radius ); if( t_radius < min_radius || min_radius < 0 ) { min_i = i; min_j = j ; min_radius = t_radius; min_center = t_center; } } } #ifdef DEBUG_CHECK_NAN if (min_center.hasMissing()) PLERROR("In BallTreeNearestNeighbors::treeFromLeaves: min_center is NaN"); #endif // Group these two nodes into a parent_node. // TODO: something more sensible for the radius and center... BinBallTree parent_node = new BinaryBallTree(); parent_node->pivot = min_center; parent_node->radius = min_radius; parent_node->setFirstChild( nodes[ min_i ] ); parent_node->setSecondChild( nodes[ min_j ] ); nodes[ min_j ] = parent_node; nodes.remove( min_i ); --nb_nodes; } // then, we have only one anchor BinBallTree root = nodes[ 0 ]; return root; }
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 159 of file BallTreeNearestNeighbors.h.
Definition at line 88 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), createAnchors(), declareOptions(), forget(), leafFromAnchor(), and makeDeepCopyFromShallowCopy().
Definition at line 75 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), BallTreeNearestNeighbors(), declareOptions(), FindBallKNN(), forget(), getBallTree(), and makeDeepCopyFromShallowCopy().
int PLearn::BallTreeNearestNeighbors::nb_points [protected] |
Definition at line 77 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), build_(), createAnchors(), and declareOptions().
int PLearn::BallTreeNearestNeighbors::nb_train_points [protected] |
Definition at line 76 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), build_(), and declareOptions().
Definition at line 89 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), createAnchors(), declareOptions(), forget(), leafFromAnchor(), and makeDeepCopyFromShallowCopy().
Definition at line 85 of file BallTreeNearestNeighbors.h.
Referenced by build_(), declareOptions(), and makeDeepCopyFromShallowCopy().
Definition at line 86 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), and declareOptions().
Definition at line 87 of file BallTreeNearestNeighbors.h.
Referenced by anchorTrain(), declareOptions(), and train().