11 #ifndef MLPACK_CORE_TREE_SPILL_TREE_SPILL_TREE_HPP
12 #define MLPACK_CORE_TREE_SPILL_TREE_SPILL_TREE_HPP
15 #include "../space_split/midpoint_space_split.hpp"
16 #include "../statistic.hpp"
66 template<
typename MetricType,
67 typename StatisticType = EmptyStatistic,
68 typename MatType = arma::mat,
69 template<
typename HyperplaneMetricType>
71 template<
typename SplitMetricType,
typename SplitMatType>
72 class SplitType = MidpointSpaceSplit>
81 typedef typename HyperplaneType<MetricType>::BoundType
BoundType;
95 arma::Col<size_t>* pointsIndex;
99 HyperplaneType<MetricType> hyperplane;
108 ElemType furthestDescendantDistance;
113 const MatType* dataset;
121 template<
typename RuleType,
bool Defeatist = false>
128 template<
typename RuleType,
bool Defeatist = false>
133 template<
typename RuleType>
137 template<
typename RuleType>
141 template<
typename RuleType>
145 template<
typename RuleType>
159 const double tau = 0,
160 const size_t maxLeafSize = 20,
161 const double rho = 0.7);
175 const double tau = 0,
176 const size_t maxLeafSize = 20,
177 const double rho = 0.7);
191 arma::Col<size_t>& points,
192 const double tau = 0,
193 const size_t maxLeafSize = 20,
194 const double rho = 0.7);
217 template<
typename Archive>
220 const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
235 const StatisticType&
Stat()
const {
return stat; }
237 StatisticType&
Stat() {
return stat; }
258 const MatType&
Dataset()
const {
return *dataset; }
261 bool Overlap()
const {
return overlappingNode; }
264 const HyperplaneType<MetricType>&
Hyperplane()
const {
return hyperplane; }
267 MetricType
Metric()
const {
return MetricType(); }
278 template<
typename VecType>
280 const VecType& point,
289 template<
typename VecType>
291 const VecType& point,
344 {
return (child == 0) ? left : right; }
373 size_t Point(
const size_t index)
const;
378 return bound.MinDistance(other.
Bound());
384 return bound.MaxDistance(other.
Bound());
390 return bound.RangeDistance(other.
Bound());
394 template<
typename VecType>
399 return bound.MinDistance(point);
403 template<
typename VecType>
408 return bound.MaxDistance(point);
412 template<
typename VecType>
417 return bound.RangeDistance(point);
424 void Center(arma::vec& center) { bound.Center(center); }
435 void SplitNode(arma::Col<size_t>& points,
436 const size_t maxLeafSize,
450 bool SplitPoints(
const double tau,
452 const arma::Col<size_t>& points,
453 arma::Col<size_t>& leftPoints,
454 arma::Col<size_t>& rightPoints);
465 friend class boost::serialization::access;
471 template<
typename Archive>
472 void Serialize(Archive& ar,
const unsigned int version);
479 #include "spill_tree_impl.hpp"
482 #include "../spill_tree.hpp"
void Serialize(Archive &ar, const unsigned int version)
Serialize the tree.
math::RangeType< ElemType > RangeDistance(const SpillTree &other) const
Return the minimum and maximum distance to another node.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
HyperplaneBase< bound::HRectBound< MetricType >, AxisParallelProjVector > AxisOrthogonalHyperplane
AxisOrthogonalHyperplane represents a hyperplane orthogonal to an axis.
SpillTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
size_t NumChildren() const
Return the number of children in this node.
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
MetricType Metric() const
Get the metric that the tree uses.
const HyperplaneType< MetricType > & Hyperplane() const
Get the Hyperplane instance.
const StatisticType & Stat() const
Return the statistic object for this node.
The core includes that mlpack expects; standard C++ includes and Armadillo.
A generic single-tree traverser for hybrid spill trees; see spill_single_tree_traverser.hpp for implementation.
size_t GetNearestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the nearest child node to the given query point (this is an efficient estimation ...
SpillTree()
A default constructor.
const BoundType & Bound() const
Return the bound object for this node.
size_t NumDescendants() const
Return the number of descendants of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
SpillTree *& Parent()
Modify the parent of this node.
bool Overlap() const
Distinguish overlapping nodes from non-overlapping nodes.
StatisticType & Stat()
Return the statistic object for this node.
A hybrid spill tree is a variant of binary space trees in which the children of a node can "spill ove...
A generic dual-tree traverser for hybrid spill trees; see spill_dual_tree_traverser.hpp for implementation.
ElemType MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
ElemType MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
SpillTree * Left() const
Gets the left child of this node.
MatType Mat
So other classes can use TreeType::Mat.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
~SpillTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
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 GetFurthestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the furthest child node to the given query point (this is an efficient estimation...
void Center(arma::vec ¢er)
Store the center of the bounding region in the given vector.
SpillTree *& Left()
Modify the left child of this node.
ElemType MaxDistance(const SpillTree &other) const
Return the maximum distance to another node.
ElemType MinDistance(const SpillTree &other) const
Return the minimum distance to another node.
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
BoundType & Bound()
Return the bound object for this node.
SpillTree * Parent() const
Gets the parent of this node.
HyperplaneType< MetricType >::BoundType BoundType
The bound type.
SpillTree *& ChildPtr(const size_t child)
MatType::elem_type ElemType
The type of element held in MatType.
ElemType 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).
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
SpillTree *& Right()
Modify the right child of this node.
If value == true, then VecType is some sort of Armadillo vector or subview.
math::RangeType< ElemType > RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
SpillTree * Right() const
Gets the right child of this node.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.