13 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP 14 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP 18 #include "../statistic.hpp" 49 template<
typename MetricType,
51 typename MatType = arma::mat,
53 template<
typename SplitBoundType,
typename SplitMatType>
91 template<
typename RuleType>
95 template<
typename RuleType>
98 template<
typename RuleType>
124 std::vector<size_t>& oldFromNew,
125 const size_t maxLeafSize = 20);
143 std::vector<size_t>& oldFromNew,
144 std::vector<size_t>& newFromOld,
145 const size_t maxLeafSize = 20);
157 const size_t maxLeafSize = 20);
172 std::vector<size_t>& oldFromNew,
173 const size_t maxLeafSize = 20);
191 std::vector<size_t>& oldFromNew,
192 std::vector<size_t>& newFromOld,
193 const size_t maxLeafSize = 20);
209 SplitType<BoundType<MetricType>, MatType>& splitter,
210 const size_t maxLeafSize = 20);
233 std::vector<size_t>& oldFromNew,
234 SplitType<BoundType<MetricType>, MatType>& splitter,
235 const size_t maxLeafSize = 20);
261 std::vector<size_t>& oldFromNew,
262 std::vector<size_t>& newFromOld,
263 SplitType<BoundType<MetricType>, MatType>& splitter,
264 const size_t maxLeafSize = 20);
285 template<
typename Archive>
288 const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
331 MetricType
Metric()
const {
return MetricType(); }
370 {
return (child == 0) ? left :
right; }
399 size_t Point(
const size_t index)
const;
404 return bound.MinDistance(other->
Bound());
410 return bound.MaxDistance(other->
Bound());
416 return bound.RangeDistance(other->
Bound());
420 template<
typename VecType>
425 return bound.MinDistance(point);
429 template<
typename VecType>
434 return bound.MaxDistance(point);
438 template<
typename VecType>
443 return bound.RangeDistance(point);
460 void Center(arma::vec& center) { bound.Center(center); }
470 SplitType<BoundType<MetricType>, MatType>& splitter);
480 void SplitNode(std::vector<size_t>& oldFromNew,
481 const size_t maxLeafSize,
482 SplitType<BoundType<MetricType>, MatType>& splitter);
494 friend class boost::serialization::access;
500 template<
typename Archive>
501 void Serialize(Archive& ar,
const unsigned int version);
508 #include "binary_space_tree_impl.hpp" 511 #include "../binary_space_tree.hpp" BinarySpaceTree *& Parent()
Modify the parent of this node.
BinarySpaceTree * left
The left child node.
void Serialize(Archive &ar, const unsigned int version)
Serialize the tree.
MatType * dataset
The dataset.
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
Linear algebra utility functions, generally performed on matrices or vectors.
MatType Mat
So other classes can use TreeType::Mat.
const BoundType< MetricType > & Bound() const
Return the bound object for this node.
BinarySpaceTree * right
The right child node.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
size_t NumDescendants() const
Return the number of descendants of this node.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
BinarySpaceTree * Left() const
Gets the left child of this node.
BoundType< MetricType > bound
The bound object for this node.
double & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
A binary space partitioning tree, such as a KD-tree or a ball tree.
double ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
BinarySpaceTree * Right() const
Gets the right child of this node.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
double minimumBoundDistance
The minimum distance from the center to any edge of the bound.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
A binary space partitioning tree node is split into its left and right child.
BinarySpaceTree *& Right()
Modify the right child of this node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
Hyper-rectangle bound for an L-metric.
double furthestDescendantDistance
The worst possible distance to the furthest descendant, cached to speed things up.
math::Range RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
MetricType Metric() const
Get the metric that the tree uses.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
const MatType & Dataset() const
Get the dataset which the tree is built on.
Simple real-valued range.
void Center(arma::vec ¢er)
Store the center of the bounding region in the given vector.
StatisticType & Stat()
Return the statistic object for this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
BinarySpaceTree()
A default constructor.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
BinarySpaceTree *& ChildPtr(const size_t child)
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
const StatisticType & Stat() const
Return the statistic object for this node.
BinarySpaceTree * Parent() const
Gets the parent of this node.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
size_t Begin() const
Return the index of the beginning point of this subset.
BoundType< MetricType > & Bound()
Return the bound object for this node.
size_t & Count()
Modify the number of points in this subset.
void SplitNode(const size_t maxLeafSize, SplitType< BoundType< MetricType >, MatType > &splitter)
Splits the current node, assigning its left and right children recursively.
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
size_t Count() const
Return the number of points in this subset.
size_t count
The number of points of the dataset contained in this node (and its children).
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
size_t & Begin()
Modify the index of the beginning point of this subset.
If value == true, then VecType is some sort of Armadillo vector or subview.
size_t NumChildren() const
Return the number of children in this node.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
Empty statistic if you are not interested in storing statistics in your tree.