MLPACK  1.0.11
binary_space_tree.hpp
Go to the documentation of this file.
1 
21 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
22 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
23 
24 #include <mlpack/core.hpp>
25 #include "mean_split.hpp"
26 
27 #include "../statistic.hpp"
28 
29 namespace mlpack {
30 namespace tree {
31 
55 template<typename BoundType,
56  typename StatisticType = EmptyStatistic,
57  typename MatType = arma::mat,
58  typename SplitType = MeanSplit<BoundType, MatType> >
60 {
61  private:
70  size_t begin;
73  size_t count;
75  size_t maxLeafSize;
77  BoundType bound;
79  StatisticType stat;
90  MatType& dataset;
91 
92  public:
94  typedef MatType Mat;
95 
98  template<typename RuleType>
100 
102  template<typename RuleType>
104 
112  BinarySpaceTree(MatType& data, const size_t maxLeafSize = 20);
113 
124  BinarySpaceTree(MatType& data,
125  std::vector<size_t>& oldFromNew,
126  const size_t maxLeafSize = 20);
127 
141  BinarySpaceTree(MatType& data,
142  std::vector<size_t>& oldFromNew,
143  std::vector<size_t>& newFromOld,
144  const size_t maxLeafSize = 20);
145 
157  BinarySpaceTree(MatType& data,
158  const size_t begin,
159  const size_t count,
160  BinarySpaceTree* parent = NULL,
161  const size_t maxLeafSize = 20);
162 
181  BinarySpaceTree(MatType& data,
182  const size_t begin,
183  const size_t count,
184  std::vector<size_t>& oldFromNew,
185  BinarySpaceTree* parent = NULL,
186  const size_t maxLeafSize = 20);
187 
209  BinarySpaceTree(MatType& data,
210  const size_t begin,
211  const size_t count,
212  std::vector<size_t>& oldFromNew,
213  std::vector<size_t>& newFromOld,
214  BinarySpaceTree* parent = NULL,
215  const size_t maxLeafSize = 20);
216 
223  BinarySpaceTree(const BinarySpaceTree& other);
224 
231 
243  const BinarySpaceTree* FindByBeginCount(size_t begin,
244  size_t count) const;
245 
257  BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
258 
260  const BoundType& Bound() const { return bound; }
262  BoundType& Bound() { return bound; }
263 
265  const StatisticType& Stat() const { return stat; }
267  StatisticType& Stat() { return stat; }
268 
270  bool IsLeaf() const;
271 
273  size_t MaxLeafSize() const { return maxLeafSize; }
275  size_t& MaxLeafSize() { return maxLeafSize; }
276 
278  size_t ExtendTree(const size_t level);
279 
281  BinarySpaceTree* Left() const { return left; }
283  BinarySpaceTree*& Left() { return left; }
284 
286  BinarySpaceTree* Right() const { return right; }
288  BinarySpaceTree*& Right() { return right; }
289 
291  BinarySpaceTree* Parent() const { return parent; }
293  BinarySpaceTree*& Parent() { return parent; }
294 
296  size_t SplitDimension() const { return splitDimension; }
298  size_t& SplitDimension() { return splitDimension; }
299 
301  const MatType& Dataset() const { return dataset; }
303  MatType& Dataset() { return dataset; }
304 
306  typename BoundType::MetricType Metric() const { return bound.Metric(); }
307 
309  void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
310 
312  size_t NumChildren() const;
313 
318  double FurthestPointDistance() const;
319 
327  double FurthestDescendantDistance() const;
328 
330  double MinimumBoundDistance() const;
331 
334  double ParentDistance() const { return parentDistance; }
337  double& ParentDistance() { return parentDistance; }
338 
345  BinarySpaceTree& Child(const size_t child) const;
346 
348  size_t NumPoints() const;
349 
355  size_t NumDescendants() const;
356 
364  size_t Descendant(const size_t index) const;
365 
374  size_t Point(const size_t index) const;
375 
377  double MinDistance(const BinarySpaceTree* other) const
378  {
379  return bound.MinDistance(other->Bound());
380  }
381 
383  double MaxDistance(const BinarySpaceTree* other) const
384  {
385  return bound.MaxDistance(other->Bound());
386  }
387 
390  {
391  return bound.RangeDistance(other->Bound());
392  }
393 
395  template<typename VecType>
396  double MinDistance(const VecType& point,
397  typename boost::enable_if<IsVector<VecType> >::type* = 0)
398  const
399  {
400  return bound.MinDistance(point);
401  }
402 
404  template<typename VecType>
405  double MaxDistance(const VecType& point,
406  typename boost::enable_if<IsVector<VecType> >::type* = 0)
407  const
408  {
409  return bound.MaxDistance(point);
410  }
411 
413  template<typename VecType>
415  RangeDistance(const VecType& point,
416  typename boost::enable_if<IsVector<VecType> >::type* = 0) const
417  {
418  return bound.RangeDistance(point);
419  }
420 
424  size_t GetSplitDimension() const;
425 
429  size_t TreeSize() const;
430 
435  size_t TreeDepth() const;
436 
438  size_t Begin() const { return begin; }
440  size_t& Begin() { return begin; }
441 
445  size_t End() const;
446 
448  size_t Count() const { return count; }
450  size_t& Count() { return count; }
451 
453  static bool HasSelfChildren() { return false; }
454 
455  private:
460  BinarySpaceTree(const size_t begin,
461  const size_t count,
462  BoundType bound,
463  StatisticType stat,
464  const int maxLeafSize = 20) :
465  left(NULL),
466  right(NULL),
467  begin(begin),
468  count(count),
469  bound(bound),
470  stat(stat),
471  maxLeafSize(maxLeafSize) { }
472 
474  {
475  return new BinarySpaceTree(begin, count, bound, stat, maxLeafSize);
476  }
477 
483  void SplitNode(MatType& data);
484 
492  void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
493 
494  public:
498  std::string ToString() const;
499 
500 };
501 
502 }; // namespace tree
503 }; // namespace mlpack
504 
505 // Include implementation.
506 #include "binary_space_tree_impl.hpp"
507 
508 #endif
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
void SplitNode(MatType &data)
Splits the current node, assigning its left and right children recursively.
size_t NumChildren() const
Return the number of children in this node.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
BinarySpaceTree * left
The left child node.
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
BinarySpaceTree *& Parent()
Modify the parent of this node.
std::string ToString() const
Returns a string representation of this object.
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:31
size_t & Begin()
Modify the index of the beginning point of this subset.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
BinarySpaceTree * Left() const
Gets the left child of this node.
MatType & dataset
The dataset.
BinarySpaceTree *& Right()
Modify the right 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 TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
double minimumBoundDistance
The minimum distance from the center to any edge of the bound.
double furthestDescendantDistance
The worst possible distance to the furthest descendant, cached to speed things up.
BinarySpaceTree(const size_t begin, const size_t count, BoundType bound, StatisticType stat, const int maxLeafSize=20)
Private copy constructor, available only to fill (pad) the tree to a specified level.
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
BoundType bound
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).
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
const BinarySpaceTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
size_t SplitDimension() const
Get the split dimension for this node.
const StatisticType & Stat() const
Return the statistic object for this node.
size_t splitDimension
The dimension this node split on if it is a parent.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
size_t Count() const
Return the number of points in this subset.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
size_t ExtendTree(const size_t level)
Fills the tree to the specified level.
size_t NumDescendants() const
Return the number of descendants of this node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
A binary space partitioning tree, such as a KD-tree or a ball tree.
BinarySpaceTree * right
The right child node.
size_t & MaxLeafSize()
Modify the max leaf size.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
MatType Mat
So other classes can use TreeType::Mat.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
StatisticType & Stat()
Return the statistic object for this node.
size_t MaxLeafSize() const
Return the max leaf size.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
size_t maxLeafSize
The max leaf size.
BoundType & Bound()
Return the bound object for this node.
double & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
size_t Begin() const
Return the index of the beginning point of this subset.
size_t count
The number of points of the dataset contained in this node (and its children).
size_t & SplitDimension()
Modify the split dimension for this node.
size_t & Count()
Modify the number of points in this subset.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
A binary space partitioning tree node is split into its left and right child.
Definition: mean_split.hpp:38
BinarySpaceTree * Right() const
Gets the right child of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
double ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
BinarySpaceTree(MatType &data, const size_t maxLeafSize=20)
Construct this as the root node of a binary space tree using the given dataset.
BinarySpaceTree * Parent() const
Gets the parent of this node.
size_t GetSplitDimension() const
Returns the dimension this parent&#39;s children are split on.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
const BoundType & Bound() const
Return the bound object for this node.
size_t End() const
Gets the index one beyond the last index in the subset.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:45
void Centroid(arma::vec &centroid)
Get the centroid of the node and store it in the given vector.
BoundType::MetricType Metric() const
Get the metric which the tree uses.
Simple real-valued range.
Definition: range.hpp:31
Empty statistic if you are not interested in storing statistics in your tree.
Definition: statistic.hpp:34
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!