MLPACK
1.0.4
|
A binary space partitioning tree, such as a KD-tree or a ball tree. More...
Classes | |
class | DualTreeTraverser |
class | SingleTreeTraverser |
Public Types | |
typedef MatType | Mat |
So other classes can use TreeType::Mat. | |
Public Member Functions | |
BinarySpaceTree (MatType &data, const size_t leafSize=20) | |
Construct this as the root node of a binary space tree using the given dataset. | |
BinarySpaceTree (MatType &data, std::vector< size_t > &oldFromNew, const size_t leafSize=20) | |
Construct this as the root node of a binary space tree using the given dataset. | |
BinarySpaceTree (MatType &data, std::vector< size_t > &oldFromNew, std::vector< size_t > &newFromOld, const size_t leafSize=20) | |
Construct this as the root node of a binary space tree using the given dataset. | |
BinarySpaceTree (MatType &data, const size_t begin, const size_t count, const size_t leafSize=20) | |
Construct this node on a subset of the given matrix, starting at column begin and using count points. | |
BinarySpaceTree (MatType &data, const size_t begin, const size_t count, std::vector< size_t > &oldFromNew, const size_t leafSize=20) | |
Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points. | |
BinarySpaceTree (MatType &data, const size_t begin, const size_t count, std::vector< size_t > &oldFromNew, std::vector< size_t > &newFromOld, const size_t leafSize=20) | |
Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points. | |
BinarySpaceTree () | |
Create an empty tree node. | |
~BinarySpaceTree () | |
Deletes this node, deallocating the memory for the children and calling their destructors in turn. | |
size_t | Begin () const |
Gets the index of the beginning point of this subset. | |
const BoundType & | Bound () const |
Return the bound object for this node. | |
BoundType & | Bound () |
Return the bound object for this node. | |
BinarySpaceTree & | Child (const size_t child) const |
Return the specified child (0 will be left, 1 will be right). | |
size_t | Count () const |
Gets the number of points in this subset. | |
size_t | End () const |
Gets the index one beyond the last index in the subset. | |
size_t | ExtendTree (const size_t level) |
Fills the tree to the specified level. | |
const BinarySpaceTree * | FindByBeginCount (size_t begin, size_t count) const |
Find a node in this tree by its begin and count (const). | |
BinarySpaceTree * | FindByBeginCount (size_t begin, size_t count) |
Find a node in this tree by its begin and count. | |
double | FurthestDescendantDistance () const |
Return the furthest possible descendant distance. | |
size_t | GetSplitDimension () const |
Returns the dimension this parent's children are split on. | |
bool | IsLeaf () const |
Return whether or not this node is a leaf (true if it has no children). | |
size_t | LeafSize () const |
Return the leaf size. | |
BinarySpaceTree * | Left () const |
Gets the left child of this node. | |
double | MaxDistance (const BinarySpaceTree *other) const |
Return the maximum distance to another node. | |
double | MaxDistance (const arma::vec &point) const |
Return the maximum distance to another point. | |
double | MinDistance (const BinarySpaceTree *other) const |
Return the minimum distance to another node. | |
double | MinDistance (const arma::vec &point) const |
Return the minimum distance to another point. | |
size_t | NumChildren () const |
Return the number of children in this node. | |
size_t | NumPoints () const |
Return the number of points in this node (0 if not a leaf). | |
size_t | Point (const size_t index) const |
Return the index (with reference to the dataset) of a particular point in this node. | |
BinarySpaceTree * | Right () const |
Gets the right child of this node. | |
const StatisticType & | Stat () const |
Return the statistic object for this node. | |
StatisticType & | Stat () |
Return the statistic object for this node. | |
size_t | TreeDepth () const |
Obtains the number of levels below this node in the tree, starting with this. | |
size_t | TreeSize () const |
Obtains the number of nodes in the tree, starting with this. | |
Static Public Member Functions | |
static bool | HasSelfChildren () |
Returns false: this tree type does not have self children. | |
Private Member Functions | |
BinarySpaceTree (const size_t begin, const size_t count, BoundType bound, StatisticType stat, const int leafSize=20) | |
Private copy constructor, available only to fill (pad) the tree to a specified level. | |
BinarySpaceTree * | CopyMe () |
size_t | GetSplitIndex (MatType &data, int splitDim, double splitVal) |
Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value. | |
size_t | GetSplitIndex (MatType &data, int splitDim, double splitVal, std::vector< size_t > &oldFromNew) |
Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value. | |
void | SplitNode (MatType &data) |
Splits the current node, assigning its left and right children recursively. | |
void | SplitNode (MatType &data, std::vector< size_t > &oldFromNew) |
Splits the current node, assigning its left and right children recursively. | |
Private Attributes | |
size_t | begin |
The index of the first point in the dataset contained in this node (and its children). | |
BoundType | bound |
The bound object for this node. | |
size_t | count |
The number of points of the dataset contained in this node (and its children). | |
size_t | leafSize |
The leaf size. | |
BinarySpaceTree * | left |
The left child node. | |
BinarySpaceTree * | right |
The right child node. | |
size_t | splitDimension |
The dimension this node split on if it is a parent. | |
StatisticType | stat |
Any extra data contained in the node. |
A binary space partitioning tree, such as a KD-tree or a ball tree.
Once the bound and type of dataset is defined, the tree will construct itself. Call the constructor with the dataset to build the tree on, and the entire tree will be built.
This particular tree does not allow growth, so you cannot add or delete nodes from it. If you need to add or delete a node, the better procedure is to rebuild the tree entirely.
This tree does take one parameter, which is the leaf size to be used.
BoundType | The bound used for each node. The valid types of bounds and the necessary skeleton interface for this class can be found in bounds/. |
StatisticType | Extra data contained in the node. See statistic.hpp for the necessary skeleton interface. |
Definition at line 55 of file binary_space_tree.hpp.
typedef MatType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Mat |
So other classes can use TreeType::Mat.
Definition at line 79 of file binary_space_tree.hpp.
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | MatType & | data, |
const size_t | leafSize = 20 |
||
) |
Construct this as the root node of a binary space tree using the given dataset.
This will modify the ordering of the points in the dataset!
data | Dataset to create tree from. This will be modified! |
leafSize | Size of each leaf in the tree. |
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | MatType & | data, |
std::vector< size_t > & | oldFromNew, | ||
const size_t | leafSize = 20 |
||
) |
Construct this as the root node of a binary space tree using the given dataset.
This will modify the ordering of points in the dataset! A mapping of the old point indices to the new point indices is filled.
data | Dataset to create tree from. This will be modified! |
oldFromNew | Vector which will be filled with the old positions for each new point. |
leafSize | Size of each leaf in the tree. |
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | MatType & | data, |
std::vector< size_t > & | oldFromNew, | ||
std::vector< size_t > & | newFromOld, | ||
const size_t | leafSize = 20 |
||
) |
Construct this as the root node of a binary space tree using the given dataset.
This will modify the ordering of points in the dataset! A mapping of the old point indices to the new point indices is filled, as well as a mapping of the new point indices to the old point indices.
data | Dataset to create tree from. This will be modified! |
oldFromNew | Vector which will be filled with the old positions for each new point. |
newFromOld | Vector which will be filled with the new positions for each old point. |
leafSize | Size of each leaf in the tree. |
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | MatType & | data, |
const size_t | begin, | ||
const size_t | count, | ||
const size_t | leafSize = 20 |
||
) |
Construct this node on a subset of the given matrix, starting at column begin and using count points.
The ordering of that subset of points will be modified! This is used for recursive tree-building by the other constructors which don't specify point indices.
data | Dataset to create tree from. This will be modified! |
begin | Index of point to start tree construction with. |
count | Number of points to use to construct tree. |
leafSize | Size of each leaf in the tree. |
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | MatType & | data, |
const size_t | begin, | ||
const size_t | count, | ||
std::vector< size_t > & | oldFromNew, | ||
const size_t | leafSize = 20 |
||
) |
Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points.
The ordering of that subset of points will be modified! This is used for recursive tree-building by the other constructors which don't specify point indices.
A mapping of the old point indices to the new point indices is filled, but it is expected that the vector is already allocated with size greater than or equal to (begin_in + count_in), and if that is not true, invalid memory reads (and writes) will occur.
data | Dataset to create tree from. This will be modified! |
begin | Index of point to start tree construction with. |
count | Number of points to use to construct tree. |
oldFromNew | Vector which will be filled with the old positions for each new point. |
leafSize | Size of each leaf in the tree. |
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | MatType & | data, |
const size_t | begin, | ||
const size_t | count, | ||
std::vector< size_t > & | oldFromNew, | ||
std::vector< size_t > & | newFromOld, | ||
const size_t | leafSize = 20 |
||
) |
Construct this node on a subset of the given matrix, starting at column begin_in and using count_in points.
The ordering of that subset of points will be modified! This is used for recursive tree-building by the other constructors which don't specify point indices.
A mapping of the old point indices to the new point indices is filled, as well as a mapping of the new point indices to the old point indices. It is expected that the vector is already allocated with size greater than or equal to (begin_in + count_in), and if that is not true, invalid memory reads (and writes) will occur.
data | Dataset to create tree from. This will be modified! |
begin | Index of point to start tree construction with. |
count | Number of points to use to construct tree. |
oldFromNew | Vector which will be filled with the old positions for each new point. |
newFromOld | Vector which will be filled with the new positions for each old point. |
leafSize | Size of each leaf in the tree. |
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | ) |
Create an empty tree node.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::~BinarySpaceTree | ( | ) |
Deletes this node, deallocating the memory for the children and calling their destructors in turn.
This will invalidate any pointers or references to any nodes which are children of this one.
mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree | ( | const size_t | begin, |
const size_t | count, | ||
BoundType | bound, | ||
StatisticType | stat, | ||
const int | leafSize = 20 |
||
) | [inline, private] |
Private copy constructor, available only to fill (pad) the tree to a specified level.
Definition at line 359 of file binary_space_tree.hpp.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Begin | ( | ) | const |
Gets the index of the beginning point of this subset.
const BoundType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Bound | ( | ) | const |
Return the bound object for this node.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MaxDistance(), and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MinDistance().
BoundType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Bound | ( | ) |
Return the bound object for this node.
BinarySpaceTree& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Child | ( | const size_t | child | ) | const |
Return the specified child (0 will be left, 1 will be right).
If the index is greater than 1, this will return the right child.
child | Index of child to return. |
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe | ( | ) | [inline, private] |
Definition at line 372 of file binary_space_tree.hpp.
References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::begin, mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::BinarySpaceTree(), mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound, mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::count, mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::leafSize, and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::stat.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Count | ( | ) | const |
Gets the number of points in this subset.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::End | ( | ) | const |
Gets the index one beyond the last index in the subset.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::ExtendTree | ( | const size_t | level | ) |
Fills the tree to the specified level.
const BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::FindByBeginCount | ( | size_t | begin, |
size_t | count | ||
) | const |
Find a node in this tree by its begin and count (const).
Every node is uniquely identified by these two numbers. This is useful for communicating position over the network, when pointers would be invalid.
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::FindByBeginCount | ( | size_t | begin, |
size_t | count | ||
) |
Find a node in this tree by its begin and count.
Every node is uniquely identified by these two numbers. This is useful for communicating position over the network, when pointers would be invalid.
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::FurthestDescendantDistance | ( | ) | const |
Return the furthest possible descendant distance.
This returns the maximum distance from the centroid to the edge of the bound and not the empirical quantity which is the actual furthest descendant distance. So the actual furthest descendant distance may be less than what this method returns (but it will never be greater than this).
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::GetSplitDimension | ( | ) | const |
Returns the dimension this parent's children are split on.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::GetSplitIndex | ( | MatType & | data, |
int | splitDim, | ||
double | splitVal | ||
) | [private] |
Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value.
data | Dataset which we are using. |
splitDim | Dimension of dataset to split on. |
splitVal | Value to split on, in the given split dimension. |
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::GetSplitIndex | ( | MatType & | data, |
int | splitDim, | ||
double | splitVal, | ||
std::vector< size_t > & | oldFromNew | ||
) | [private] |
Find the index to split on for this node, given that we are splitting in the given split dimension on the specified split value.
Also returns a list of the changed indices.
data | Dataset which we are using. |
splitDim | Dimension of dataset to split on. |
splitVal | Value to split on, in the given split dimension. |
oldFromNew | Vector holding permuted indices. |
static bool mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::HasSelfChildren | ( | ) | [inline, static] |
Returns false: this tree type does not have self children.
Definition at line 352 of file binary_space_tree.hpp.
bool mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::IsLeaf | ( | ) | const |
Return whether or not this node is a leaf (true if it has no children).
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::LeafSize | ( | ) | const |
Return the leaf size.
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Left | ( | ) | const |
Gets the left child of this node.
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MaxDistance | ( | const BinarySpaceTree< BoundType, StatisticType, MatType > * | other | ) | const [inline] |
Return the maximum distance to another node.
Definition at line 303 of file binary_space_tree.hpp.
References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound, and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Bound().
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MaxDistance | ( | const arma::vec & | point | ) | const [inline] |
Return the maximum distance to another point.
Definition at line 315 of file binary_space_tree.hpp.
References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MinDistance | ( | const BinarySpaceTree< BoundType, StatisticType, MatType > * | other | ) | const [inline] |
Return the minimum distance to another node.
Definition at line 297 of file binary_space_tree.hpp.
References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound, and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Bound().
double mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MinDistance | ( | const arma::vec & | point | ) | const [inline] |
Return the minimum distance to another point.
Definition at line 309 of file binary_space_tree.hpp.
References mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::NumChildren | ( | ) | const |
Return the number of children in this node.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::NumPoints | ( | ) | const |
Return the number of points in this node (0 if not a leaf).
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Point | ( | const size_t | index | ) | const |
Return the index (with reference to the dataset) of a particular point in this node.
This will happily return invalid indices if the given index is greater than the number of points in this node (obtained with NumPoints()) -- be careful.
index | Index of point for which a dataset index is wanted. |
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Right | ( | ) | const |
Gets the right child of this node.
void mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitNode | ( | MatType & | data | ) | [private] |
Splits the current node, assigning its left and right children recursively.
data | Dataset which we are using. |
void mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::SplitNode | ( | MatType & | data, |
std::vector< size_t > & | oldFromNew | ||
) | [private] |
Splits the current node, assigning its left and right children recursively.
Also returns a list of the changed indices.
data | Dataset which we are using. |
oldFromNew | Vector holding permuted indices. |
const StatisticType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Stat | ( | ) | const |
Return the statistic object for this node.
StatisticType& mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::Stat | ( | ) |
Return the statistic object for this node.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::TreeDepth | ( | ) | const |
Obtains the number of levels below this node in the tree, starting with this.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::TreeSize | ( | ) | const |
Obtains the number of nodes in the tree, starting with this.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::begin [private] |
The index of the first point in the dataset contained in this node (and its children).
Definition at line 64 of file binary_space_tree.hpp.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().
BoundType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::bound [private] |
The bound object for this node.
Definition at line 69 of file binary_space_tree.hpp.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe(), mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MaxDistance(), and mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::MinDistance().
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::count [private] |
The number of points of the dataset contained in this node (and its children).
Definition at line 67 of file binary_space_tree.hpp.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::leafSize [private] |
The leaf size.
Definition at line 73 of file binary_space_tree.hpp.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::left [private] |
The left child node.
Definition at line 59 of file binary_space_tree.hpp.
BinarySpaceTree* mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::right [private] |
The right child node.
Definition at line 61 of file binary_space_tree.hpp.
size_t mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::splitDimension [private] |
The dimension this node split on if it is a parent.
Definition at line 75 of file binary_space_tree.hpp.
StatisticType mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::stat [private] |
Any extra data contained in the node.
Definition at line 71 of file binary_space_tree.hpp.
Referenced by mlpack::tree::BinarySpaceTree< BoundType, StatisticType, MatType >::CopyMe().