GClasses
|
An efficient algorithm for finding neighbors. More...
#include <GNeighborFinder.h>
Public Member Functions | |
GKdTree (GMatrix *pData, size_t neighborCount, GDistanceMetric *pMetric, bool ownMetric) | |
virtual | ~GKdTree () |
virtual size_t | addCopy (const double *pVector) |
Add a new point-vector to the internal set. | |
virtual double * | releaseVector (size_t nIndex) |
Release a point-vector from the internal set. | |
virtual void | reoptimize () |
Rebuilds the tree to improve subsequent performance. This should be called after a significant number of point-vectors are added to or released from the internal set. | |
virtual void | neighbors (size_t *pOutNeighbors, size_t index) |
See the comment for GNeighborFinder::neighbors. | |
virtual void | neighbors (size_t *pOutNeighbors, double *pOutDistances, size_t index) |
See the comment for GNeighborFinder::neighbors. | |
virtual void | neighbors (size_t *pOutNeighbors, double *pOutDistances, const double *pInputVector) |
See the comment for GNeighborFinderGeneralizing::neighbors. | |
void | setMaxLeafSize (size_t n) |
Specify the max number of point-vectors to store in each leaf node. | |
GKdNode * | root () |
Returns the root node of the kd-tree. | |
GKdNode * | buildTree (size_t count, size_t *pIndexes) |
Build the tree. | |
bool | isGreaterOrEqual (const double *pPat, size_t attr, double pivot) |
Returns true iff the specified point-vector is on the >= side of the specified pivot. | |
Static Public Member Functions | |
static void | test () |
Performs unit tests for this class. Throws an exception if there is a failure. | |
static double | medianDistanceToNeighbor (GMatrix &data, size_t n) |
Computes the median distance to the n^th closest neighbor of each row in data. | |
Protected Member Functions | |
void | findNeighbors (size_t *pOutNeighbors, double *pOutDistances, const double *pInputVector, size_t nExclude) |
This is the helper method that finds the neighbors. | |
void | computePivotAndGoodness (size_t count, size_t *pIndexes, size_t attr, double *pOutPivot, double *pOutGoodness) |
Computes a good pivot for the specified attribute, and the goodness of splitting on that attribute. For continuous attributes, the pivot is the (not scaled) mean and the goodness is the scaled variance. For nominal attributes, the pivot is the most common value and the goodness is scaled entropy. | |
size_t | splitIndexes (size_t count, size_t *pIndexes, size_t attr, double pivot) |
Moves all the indexes that refer to rows that have a value less than pivot in the specified attribute to the beginning of the list, and the rest to the end. Returns the number of rows with a value less than the pivot. For nominal values, not-equal values are moved to the beginning, and equal values are moved to the end. | |
Protected Attributes | |
size_t | m_maxLeafSize |
size_t | m_size |
GKdNode * | m_pRoot |
An efficient algorithm for finding neighbors.
GClasses::GKdTree::GKdTree | ( | GMatrix * | pData, |
size_t | neighborCount, | ||
GDistanceMetric * | pMetric, | ||
bool | ownMetric | ||
) |
virtual GClasses::GKdTree::~GKdTree | ( | ) | [virtual] |
virtual size_t GClasses::GKdTree::addCopy | ( | const double * | pVector | ) | [virtual] |
Add a new point-vector to the internal set.
Implements GClasses::GNeighborFinderGeneralizing.
GKdNode* GClasses::GKdTree::buildTree | ( | size_t | count, |
size_t * | pIndexes | ||
) |
Build the tree.
void GClasses::GKdTree::computePivotAndGoodness | ( | size_t | count, |
size_t * | pIndexes, | ||
size_t | attr, | ||
double * | pOutPivot, | ||
double * | pOutGoodness | ||
) | [protected] |
Computes a good pivot for the specified attribute, and the goodness of splitting on that attribute. For continuous attributes, the pivot is the (not scaled) mean and the goodness is the scaled variance. For nominal attributes, the pivot is the most common value and the goodness is scaled entropy.
void GClasses::GKdTree::findNeighbors | ( | size_t * | pOutNeighbors, |
double * | pOutDistances, | ||
const double * | pInputVector, | ||
size_t | nExclude | ||
) | [protected] |
This is the helper method that finds the neighbors.
bool GClasses::GKdTree::isGreaterOrEqual | ( | const double * | pPat, |
size_t | attr, | ||
double | pivot | ||
) |
Returns true iff the specified point-vector is on the >= side of the specified pivot.
static double GClasses::GKdTree::medianDistanceToNeighbor | ( | GMatrix & | data, |
size_t | n | ||
) | [static] |
Computes the median distance to the n^th closest neighbor of each row in data.
virtual void GClasses::GKdTree::neighbors | ( | size_t * | pOutNeighbors, |
size_t | index | ||
) | [virtual] |
See the comment for GNeighborFinder::neighbors.
Implements GClasses::GNeighborFinder.
virtual void GClasses::GKdTree::neighbors | ( | size_t * | pOutNeighbors, |
double * | pOutDistances, | ||
size_t | index | ||
) | [virtual] |
See the comment for GNeighborFinder::neighbors.
Implements GClasses::GNeighborFinder.
virtual void GClasses::GKdTree::neighbors | ( | size_t * | pOutNeighbors, |
double * | pOutDistances, | ||
const double * | pInputVector | ||
) | [virtual] |
See the comment for GNeighborFinderGeneralizing::neighbors.
Implements GClasses::GNeighborFinderGeneralizing.
virtual double* GClasses::GKdTree::releaseVector | ( | size_t | nIndex | ) | [virtual] |
Release a point-vector from the internal set.
Implements GClasses::GNeighborFinderGeneralizing.
virtual void GClasses::GKdTree::reoptimize | ( | ) | [virtual] |
Rebuilds the tree to improve subsequent performance. This should be called after a significant number of point-vectors are added to or released from the internal set.
Implements GClasses::GNeighborFinderGeneralizing.
GKdNode* GClasses::GKdTree::root | ( | ) | [inline] |
Returns the root node of the kd-tree.
void GClasses::GKdTree::setMaxLeafSize | ( | size_t | n | ) | [inline] |
Specify the max number of point-vectors to store in each leaf node.
size_t GClasses::GKdTree::splitIndexes | ( | size_t | count, |
size_t * | pIndexes, | ||
size_t | attr, | ||
double | pivot | ||
) | [protected] |
Moves all the indexes that refer to rows that have a value less than pivot in the specified attribute to the beginning of the list, and the rest to the end. Returns the number of rows with a value less than the pivot. For nominal values, not-equal values are moved to the beginning, and equal values are moved to the end.
static void GClasses::GKdTree::test | ( | ) | [static] |
Performs unit tests for this class. Throws an exception if there is a failure.
size_t GClasses::GKdTree::m_maxLeafSize [protected] |
GKdNode* GClasses::GKdTree::m_pRoot [protected] |
size_t GClasses::GKdTree::m_size [protected] |