PLearn 0.1
Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | Static Protected Member Functions | Protected Attributes | Private Types | Private Member Functions
PLearn::BallTreeNearestNeighbors Class Reference

#include <BallTreeNearestNeighbors.h>

Inheritance diagram for PLearn::BallTreeNearestNeighbors:
Inheritance graph
[legend]
Collaboration diagram for PLearn::BallTreeNearestNeighbors:
Collaboration graph
[legend]

List of all members.

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 OptionListgetOptionList () const
virtual OptionMapgetOptionMap () const
virtual RemoteMethodMapgetRemoteMethodMap () const
virtual BallTreeNearestNeighborsdeepCopy (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 &center1, const real &radius1, const Vec &center2, const real &radius2)
static bool contain (const Vec &center1, const real &radius1, const Vec &center2, const real &radius2)
static void smallestContainer (const Vec &center1, const real &radius1, const Vec &center2, 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 PPathdeclaringFile ()

Public Attributes

TVec< intpoint_indices
int rmin
string train_method
TVec< Matanchor_set
TVec< intpivot_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 ()

Detailed Description

Definition at line 62 of file BallTreeNearestNeighbors.h.


Member Typedef Documentation

Reimplemented from PLearn::GenericNearestNeighbors.

Definition at line 67 of file BallTreeNearestNeighbors.h.


Constructor & Destructor Documentation

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;
}

Here is the caller graph for this function:

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;
}

Here is the call graph for this function:


Member Function Documentation

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.

bool PLearn::BallTreeNearestNeighbors::_isa_ ( const Object o) [static]

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() );

            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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); 
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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().

Here is the call graph for this function:

Here is the caller graph for this function:

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();
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 ) );
}

Here is the call graph for this function:

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 );

}

Here is the call graph for this function:

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 );
}

Here is the call graph for this function:

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;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 );
}

Here is the call graph for this function:

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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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();
}

Here is the call graph for this function:

Here is the caller graph for this function:

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;
}

Here is the call graph for this function:

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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

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
}

Here is the call graph for this function:

Here is the caller graph for this function:

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() );
}

Here is the call graph for this function:

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;
}

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

Reimplemented from PLearn::GenericNearestNeighbors.

Definition at line 159 of file BallTreeNearestNeighbors.h.

Definition at line 77 of file BallTreeNearestNeighbors.h.

Referenced by anchorTrain(), build_(), createAnchors(), and declareOptions().

Definition at line 76 of file BallTreeNearestNeighbors.h.

Referenced by anchorTrain(), build_(), and declareOptions().

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().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines