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(); }
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() const
Gets the parent of this node.
size_t NumDescendants() const
Return the number of descendants of this node.
BinarySpaceTree *& Parent()
Modify the parent of this node.
const StatisticType & Stat() const
Return the statistic object for this node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
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.
BinarySpaceTree * right
The right child node.
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 Count() const
Return the number of points in this subset.
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.
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another 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.
const BoundType< MetricType > & Bound() const
Return the bound object for this node.
BinarySpaceTree * Right() const
Gets the right child of this 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.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
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.
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()
Modify the right child of this node.
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
Hyper-rectangle bound for an L-metric.
double furthestDescendantDistance
The worst possible distance to the furthest descendant, cached to speed things up.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
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...
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
BinarySpaceTree * Left() const
Gets the left child of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
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)
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
MetricType Metric() const
Get the metric that the tree uses.
size_t Begin() const
Return the index of the beginning point of this subset.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
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 ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
size_t count
The number of points of the dataset contained in this node (and its children).
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
math::Range RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
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.
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.
size_t NumChildren() const
Return the number of children in this node.