MLPACK  1.0.8
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 
26 #include "../statistic.hpp"
27 
28 namespace mlpack {
29 namespace tree {
30 
49 template<typename BoundType,
50  typename StatisticType = EmptyStatistic,
51  typename MatType = arma::mat>
53 {
54  private:
63  size_t begin;
66  size_t count;
68  size_t leafSize;
70  BoundType bound;
72  StatisticType stat;
78  MatType& dataset;
79 
80  public:
82  typedef MatType Mat;
83 
86  template<typename RuleType>
88 
90  template<typename RuleType>
92 
100  BinarySpaceTree(MatType& data, const size_t leafSize = 20);
101 
112  BinarySpaceTree(MatType& data,
113  std::vector<size_t>& oldFromNew,
114  const size_t leafSize = 20);
115 
129  BinarySpaceTree(MatType& data,
130  std::vector<size_t>& oldFromNew,
131  std::vector<size_t>& newFromOld,
132  const size_t leafSize = 20);
133 
145  BinarySpaceTree(MatType& data,
146  const size_t begin,
147  const size_t count,
148  BinarySpaceTree* parent = NULL,
149  const size_t leafSize = 20);
150 
169  BinarySpaceTree(MatType& data,
170  const size_t begin,
171  const size_t count,
172  std::vector<size_t>& oldFromNew,
173  BinarySpaceTree* parent = NULL,
174  const size_t leafSize = 20);
175 
197  BinarySpaceTree(MatType& data,
198  const size_t begin,
199  const size_t count,
200  std::vector<size_t>& oldFromNew,
201  std::vector<size_t>& newFromOld,
202  BinarySpaceTree* parent = NULL,
203  const size_t leafSize = 20);
204 
211  BinarySpaceTree(const BinarySpaceTree& other);
212 
219 
231  const BinarySpaceTree* FindByBeginCount(size_t begin,
232  size_t count) const;
233 
245  BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
246 
248  const BoundType& Bound() const { return bound; }
250  BoundType& Bound() { return bound; }
251 
253  const StatisticType& Stat() const { return stat; }
255  StatisticType& Stat() { return stat; }
256 
258  bool IsLeaf() const;
259 
261  size_t LeafSize() const { return leafSize; }
263  size_t& LeafSize() { return leafSize; }
264 
266  size_t ExtendTree(const size_t level);
267 
269  BinarySpaceTree* Left() const { return left; }
271  BinarySpaceTree*& Left() { return left; }
272 
274  BinarySpaceTree* Right() const { return right; }
276  BinarySpaceTree*& Right() { return right; }
277 
279  BinarySpaceTree* Parent() const { return parent; }
281  BinarySpaceTree*& Parent() { return parent; }
282 
284  size_t SplitDimension() const { return splitDimension; }
286  size_t& SplitDimension() { return splitDimension; }
287 
289  const arma::mat& Dataset() const { return dataset; }
291  arma::mat& Dataset() { return dataset; }
292 
294  typename BoundType::MetricType Metric() const { return bound.Metric(); }
295 
297  void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
298 
300  size_t NumChildren() const;
301 
306  double FurthestPointDistance() const;
307 
315  double FurthestDescendantDistance() const;
316 
323  BinarySpaceTree& Child(const size_t child) const;
324 
326  size_t NumPoints() const;
327 
333  size_t NumDescendants() const;
334 
342  size_t Descendant(const size_t index) const;
343 
352  size_t Point(const size_t index) const;
353 
355  double MinDistance(const BinarySpaceTree* other) const
356  {
357  return bound.MinDistance(other->Bound());
358  }
359 
361  double MaxDistance(const BinarySpaceTree* other) const
362  {
363  return bound.MaxDistance(other->Bound());
364  }
365 
368  {
369  return bound.RangeDistance(other->Bound());
370  }
371 
373  double MinDistance(const arma::vec& point) const
374  {
375  return bound.MinDistance(point);
376  }
377 
379  double MaxDistance(const arma::vec& point) const
380  {
381  return bound.MaxDistance(point);
382  }
383 
385  math::Range RangeDistance(const arma::vec& point) const
386  {
387  return bound.RangeDistance(point);
388  }
389 
393  size_t GetSplitDimension() const;
394 
398  size_t TreeSize() const;
399 
404  size_t TreeDepth() const;
405 
407  size_t Begin() const { return begin; }
409  size_t& Begin() { return begin; }
410 
414  size_t End() const;
415 
417  size_t Count() const { return count; }
419  size_t& Count() { return count; }
420 
422  static bool HasSelfChildren() { return false; }
423 
424  private:
429  BinarySpaceTree(const size_t begin,
430  const size_t count,
431  BoundType bound,
432  StatisticType stat,
433  const int leafSize = 20) :
434  left(NULL),
435  right(NULL),
436  begin(begin),
437  count(count),
438  bound(bound),
439  stat(stat),
440  leafSize(leafSize) { }
441 
443  {
444  return new BinarySpaceTree(begin, count, bound, stat, leafSize);
445  }
446 
452  void SplitNode(MatType& data);
453 
461  void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
462 
471  size_t GetSplitIndex(MatType& data, int splitDim, double splitVal);
472 
483  size_t GetSplitIndex(MatType& data, int splitDim, double splitVal,
484  std::vector<size_t>& oldFromNew);
485  public:
489  std::string ToString() const;
490 
491 };
492 
493 }; // namespace tree
494 }; // namespace mlpack
495 
496 // Include implementation.
497 #include "binary_space_tree_impl.hpp"
498 
499 #endif
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
size_t & LeafSize()
Modify the leaf size.
BinarySpaceTree * right
The right child node.
BinarySpaceTree *& Parent()
Modify the parent of this node.
BinarySpaceTree *& Left()
Modify the left child of this node.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
size_t End() const
Gets the index one beyond the last index in the subset.
BinarySpaceTree * Parent() const
Gets the parent of this node.
BoundType bound
The bound object for this node.
BoundType::MetricType Metric() const
Get the metric which the tree uses.
void SplitNode(MatType &data)
Splits the current node, assigning its left and right children recursively.
BinarySpaceTree * left
The left child node.
std::string ToString() const
Returns a string representation of this object.
size_t splitDimension
The dimension this node split on if it is a parent.
BoundType & Bound()
Return the bound object for this node.
A binary space partitioning tree, such as a KD-tree or a ball tree.
size_t leafSize
The leaf size.
size_t GetSplitDimension() const
Returns the dimension this parent's children are split on.
const StatisticType & Stat() const
Return the statistic object for 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).
size_t SplitDimension() const
Get the split dimension for this node.
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 *& Right()
Modify the right child of this node.
BinarySpaceTree * Right() const
Gets the right child of this node.
size_t & Begin()
Modify the index of the beginning point of this subset.
size_t LeafSize() const
Return the leaf size.
BinarySpaceTree * Left() const
Gets the left child of this node.
size_t count
The number of points of the dataset contained in this node (and its children).
size_t NumDescendants() const
Return the number of descendants of this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
double MinDistance(const arma::vec &point) const
Return the minimum distance to another point.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
size_t & Count()
Modify the number of points in this subset.
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 Begin() const
Return the index of the beginning point of this subset.
size_t Count() const
Return the number of points in this subset.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
const BinarySpaceTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
size_t NumChildren() const
Return the number of children in this node.
MatType Mat
So other classes can use TreeType::Mat.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
MatType & dataset
The dataset.
StatisticType & Stat()
Return the statistic object for this node.
math::Range RangeDistance(const arma::vec &point) const
Return the minimum and maximum distance to another point.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
const arma::mat & Dataset() const
Get the dataset which the tree is built on.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
double furthestDescendantDistance
The distance to the furthest descendant, cached to speed things up.
const BoundType & Bound() const
Return the bound object for this node.
BinarySpaceTree(MatType &data, const size_t leafSize=20)
Construct this as the root node of a binary space tree using the given dataset.
size_t & SplitDimension()
Modify the split dimension for this node.
arma::mat & Dataset()
Modify the dataset which the tree is built on. Be careful!
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...
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
double MaxDistance(const arma::vec &point) const
Return the maximum distance to another point.
void Centroid(arma::vec &centroid)
Get the centroid of the node and store it in the given vector.
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
Simple real-valued range.
Definition: range.hpp:31
StatisticType stat
Any extra data contained in the node.
size_t ExtendTree(const size_t level)
Fills the tree to the specified level.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
Empty statistic if you are not interested in storing statistics in your tree.
Definition: statistic.hpp:34